【正文】 e ?Avbaki, ?Entropia ?Napster ?Gnutella ?Free ?Publius ?Free Haven ?Magi ?Groove ?Jabber ?JXTA ?.NET ?.NETMyServices 2022/6/3 李之棠 HUST 21 P2P 多維視圖 分布式計(jì)算 －計(jì)算 文件共享 存儲(chǔ) Centerspan Cybiko 平臺(tái) .NET JXTA Globus Avaki Porivo Technology Entropia, DataSynapse SETIhome,United Device 通信與協(xié)同 帶寬 Jabber AiMster Gnutella,Free Mojo Nation Pointera OnSystems Napster Free Haven,Publius Groove Magi 2022/6/3 李之棠 HUST 22 P2P 應(yīng)用分類 P2P 應(yīng)用 并行化 內(nèi)容和文件管理 協(xié)同 計(jì)算密集 構(gòu)件化 構(gòu)件化 過濾挖掘 文件系統(tǒng) 即時(shí)消息 共享應(yīng)用 游戲 2022/6/3 李之棠 HUST 23 可并行化 P2P應(yīng)用 ?計(jì)算密集型：把一個(gè)大的任務(wù)分解成許多可在大量獨(dú)立對等端省并行執(zhí)行的子任務(wù)。 – 通常是那些使用不同參數(shù)的相同計(jì)算任務(wù) :如外星生命搜索 SETIhome，密碼破解，風(fēng)險(xiǎn)預(yù)測，市場和信譽(yù)評估，人口統(tǒng)計(jì)分析 ?構(gòu)件化應(yīng)用：還沒有廣泛認(rèn)著為 P2P應(yīng)用 – 在許多對等端上運(yùn)行 不同的構(gòu)件 – 如 Workflow , JavaBean, Web Services 2022/6/3 李之棠 HUST 24 內(nèi)容和文件管理 ?集中應(yīng)用 – 信息存儲(chǔ) – 信息查詢（來自網(wǎng)絡(luò)上各種 Peers） ?大眾模式：內(nèi)容交換 – 2022年： Napster和 Gnutella讓 Peers搜速和下載文件 – 當(dāng)前重點(diǎn)是提供可靠性：用戶下載文件時(shí)的智能選擇，重復(fù) DB – 協(xié)同過慮和挖掘開始出現(xiàn) 2022/6/3 李之棠 HUST 25 協(xié)同 ?什么是協(xié)同應(yīng)用？ – 允許用戶實(shí)時(shí)協(xié)同 – 不依賴中心服務(wù)器去搜集和轉(zhuǎn)發(fā)消息 ?應(yīng)用實(shí)例 – 實(shí)時(shí)消息： Yahoo!、 AOL和 Jabber已在各種計(jì)算機(jī)用戶之間廣泛使用 – 同行共享： Buzzpad,分布式 Power Point異地同時(shí)互動(dòng)評審、編輯同一信息 – P2P游戲： NetZ ,Scour Exchange,Cybiko游戲運(yùn)行在所有 Peer的計(jì)算機(jī)上，更新也分布在所有Peer端，不需要中心服務(wù)器 2022/6/3 李之棠 HUST 26 P2P 平臺(tái)環(huán)境 ?P2P平臺(tái) – 由 Inter、 Intra和 Adhoc網(wǎng)構(gòu)成 – 從撥號線到寬帶都可支持 P2P – 當(dāng)前結(jié)構(gòu)多是個(gè)人 家庭主機(jī) 、單位桌面機(jī)和個(gè)人移動(dòng)計(jì)算機(jī)（便攜和手持） ?歷史與現(xiàn)狀 – 早期 P2P系統(tǒng)多用家庭機(jī)進(jìn)行內(nèi)容共享，Napster,Gnutella Aimster – 分布式計(jì)算多基于桌面機(jī)， SETIhome – Adhoc手持網(wǎng)絡(luò)最近可用，專于協(xié)同計(jì)算 ，如Endeavors, Technologies Magi。如 CPU處理能力 ， 帶寬 ， 能量 和 磁盤空間 等等 2022/6/3 李之棠 HUST 35 可靠性 ?P2P系統(tǒng)中 困難的問題 – 固有的分布式特點(diǎn)使保障可靠性很困難 ?通常解是： 冗余 – 計(jì)算密集模式中，當(dāng)檢測到某機(jī)失效，則該任務(wù)可 啟動(dòng)其它可用計(jì)算機(jī) – 相同的任務(wù)可分配到 多個(gè) Peers上 – 在文件共享系統(tǒng)，可在許多 Peers上 部署重復(fù)DB – 丟失的消息可 重發(fā) 或沿著 多個(gè)通路同時(shí) 發(fā)送 2022/6/3 李之棠 HUST 36 類說明 ?兩類構(gòu)件 – 前面所討論的構(gòu)件是 可應(yīng)用 到 P2P結(jié)構(gòu) – 應(yīng)用類說明是構(gòu)件每類 P2P應(yīng)用的 功能抽象 或概要 ?類說明 – 調(diào)度：應(yīng)用于可并行化或計(jì)算密集類（任務(wù)分塊調(diào)度給Peers） – 元數(shù)據(jù)：應(yīng)用于內(nèi)容和文件管理，描述存儲(chǔ)在各 Peers上的內(nèi)容，并可被查閱以決定所求信息的位置 – 消息：應(yīng)用于協(xié)同，在各 Peers間發(fā)送以完成通信 – 管理：支持先行 P2P基礎(chǔ)設(shè)施的管理 2022/6/3 李之棠 HUST 37 應(yīng)用說明 ?構(gòu)成與功能 – 工具、例程和服務(wù) – 詳細(xì)描述應(yīng)用，以協(xié)調(diào)現(xiàn)行 P2P設(shè)施上的某些應(yīng)用 ?適應(yīng)于 – 分布式調(diào)度（科學(xué)、金融、生物計(jì)算） – 內(nèi)容和文件共享（音樂 MP3文件交換） – 運(yùn)行在協(xié)同和通信系統(tǒng)上面的特別應(yīng)用，如日歷、筆記、消息和聊天 2022/6/3 李之棠 HUST 38 模式與算法 ?集中目錄模式 – 最流行， Napster使用 – 群組的 Peers連接到發(fā)布其能提供共享內(nèi)容的中心目錄上，匹配請求與索引 – 文件直接交換在兩個(gè) Peers間進(jìn)行 – 需要一些可管理的設(shè)施（目錄服務(wù)器：記載群組所有參加者的信息） – 限制了規(guī)模的擴(kuò)大：大量用戶增加－ 大量請求 大服務(wù)器 存儲(chǔ)器 – 然 Napster經(jīng)驗(yàn)表明 ,除開法律問題外 ,該模式還很有效和強(qiáng)大 Index 1 2 3 5 4 搜索 下載 2022/6/3 李之棠 HUST 39 Napster原理 I have X! Publish insert(X, ) ... 2022/6/3 李之棠 HUST 40 Napster原理 Where is file A? Query Reply search(A) Fetch 2022/6/3 李之棠 HUST 41 洪泛請求模式 ?過程 – 每個(gè) Peer的請求直接廣播到連接的 Peers – 各 Peers又廣播到各自的 Peers – 直到收到應(yīng)答或 達(dá)到最大洪泛步數(shù) (典型 59) ?特點(diǎn) – 無廣告性共享資源 – Gnutella 使用該算法 ,限于公司內(nèi)通信有效 – 大量請求占用網(wǎng)絡(luò)帶寬 ,可擴(kuò)展性并不一定最好 ?改進(jìn) – Kazaa 設(shè)立 SuperPeer客戶軟件 ,以集中大量請求 – BT 文件分塊 – Cache最近請求 1 2 3 5 4 搜索 下載 6 2022/6/3 李之棠 HUST 42 Gnutella原理 I have file A. I have file A. Where is file A? Query Reply 2022/6/3 李之棠 HUST 43 KaZaA原理 I have X! Publish insert(X, ) ... 2022/6/3 李之棠 HUST 44 KaZaA原理 Where is file A? Query search(A) search(A) Replies 2022/6/3 李之棠 HUST 45 BitTorrent原理 Tracker A D C B 2022/6/3 李之棠 HUST 46 BitTorrent原理 A C B D 2022/6/3 李之棠 HUST 47 文件路由模式 ?過程 – 每個(gè)網(wǎng)上 Peer分配一個(gè)隨機(jī) ID,并知道其他 Peers的給定號碼 – 當(dāng)共享文件發(fā)布到系統(tǒng)上時(shí) ,根據(jù)文件名字和內(nèi)容 Hash成為 ID – 每個(gè) Peer將根據(jù) 該 ID向該文件路由 – 該過程重復(fù)執(zhí)行 ,直到最近的 PeerID是現(xiàn)行 Peer的 ID – 每個(gè)路由操作還 保持文件副本在本地 – 當(dāng) Peer請求某文件時(shí) ,該請求將 用該文件的 ID到達(dá) Peer,過程重復(fù)直到發(fā)現(xiàn)文件副本 ,最終文件下載到請求源端 2022/6/3 李之棠 HUST 48 4個(gè)算法實(shí)現(xiàn)文件路由 ?Chord/CAN/Tapestry/Pastry ?目標(biāo)相同 – 減少 路由到指定文件的 P2P跳數(shù) – 減少 每個(gè) Peer必須保持的 路由狀態(tài) ?算法異同 – 都保證算法的跳數(shù)與 Peer群組的大小相關(guān) – 或都指出算法能以高概率完成 – 方法上的差別很小 2022/6/3 李之棠 HUST 49 ?Chord – 每個(gè) Peer保持 LogN其他 Peer的蹤跡 (N是群組的全部 Peer數(shù) ) – 當(dāng) Peer加入或離開時(shí) ,高優(yōu)化算法版本僅需關(guān)注LogN個(gè) Peers的變化 ?CAN – 每個(gè) Peer保持 少于 LogN個(gè)其他 Peers的蹤跡 – 在插入和刪除時(shí)僅這些 Peers受影響 – 其路由表較小 ,但到達(dá)的路徑較長 – 可能 更適合動(dòng)態(tài)通信 ?Tapestry與 Pastry很相似 – 除減少跳數(shù)外 ,還積極削減每個(gè) P2P跳上的時(shí)延 2022/6/3 李之棠 HUST 50 路由表 ?路由表內(nèi)容 – id－文件標(biāo)識(shí)符 – next_hop－存儲(chǔ)文件 id的另一個(gè)節(jié)點(diǎn) – file－保存在本地的 id標(biāo)識(shí)文件 ?搜索過程 – 如果文件 id存儲(chǔ)在本地，停止搜索，上傳文件 – 如果不在本地， 搜索 路由表中 最接近的 id，將請求 轉(zhuǎn)到 next_hop – 如果所有節(jié)點(diǎn)都沒有找到，返回失敗，返回路由表 中下一個(gè)最接近的 id ID Next_hop file … 2022/6/3 李之棠 HUST 51 文件路由原理 4 n1 f4 12 n2 f12 5 n3 9 n3 f9 3 n1 f3 14 n4 f14 5 n3 14 n5 f14 13 n2 f13 3 n6 n1 n2 n3 n4 4 n1 f4 10 n5 f10 8 n6 n5 query(10) 1 2 4 4’ 5 ?網(wǎng)絡(luò)趨向于一個(gè)小世界－ small world,類似六度分隔（ Six Degrees of Separation）理論 ?因此，大部分查詢只需經(jīng)過少量跳數(shù) 2022/6/3 李之棠 HUST 52 Distributed Hash Table ?分布式數(shù)據(jù)結(jié)構(gòu)系統(tǒng)中，可以是環(huán)，樹，超立方體，跳表，蝶形網(wǎng)絡(luò) ... ?CFS, OceanStore, PAST, ChordDNS 分布式 Hash表 分布式應(yīng)用 get (key) data node node node …. put(key, data) 查找服務(wù) lookup(key) node IP address (文件共享 ) (DHash) (Chord) 2022/6/3 李之棠 HUST 53 ?結(jié)構(gòu)化 重疊路由 – 加入 ：開始時(shí)，聯(lián)系一個(gè) “ bootstrap”節(jié)點(diǎn)，加入分布式數(shù)據(jù)結(jié)構(gòu)， 獲得一個(gè)節(jié)點(diǎn) id – 發(fā)布 ：向數(shù)據(jù)結(jié)構(gòu)中最近的節(jié)點(diǎn)發(fā)布