【文章內(nèi)容簡(jiǎn)介】 2022/6/3 李之棠 HUST 40 Napster原理 Where is file A? Query Reply search(A) Fetch 2022/6/3 李之棠 HUST 41 洪泛請(qǐng)求模式 ?過程 – 每個(gè) Peer的請(qǐng)求直接廣播到連接的 Peers – 各 Peers又廣播到各自的 Peers – 直到收到應(yīng)答或 達(dá)到最大洪泛步數(shù) (典型 59) ?特點(diǎn) – 無廣告性共享資源 – Gnutella 使用該算法 ,限于公司內(nèi)通信有效 – 大量請(qǐng)求占用網(wǎng)絡(luò)帶寬 ,可擴(kuò)展性并不一定最好 ?改進(jìn) – Kazaa 設(shè)立 SuperPeer客戶軟件 ,以集中大量請(qǐng)求 – BT 文件分塊 – Cache最近請(qǐng)求 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的給定號(hào)碼 – 當(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請(qǐng)求某文件時(shí) ,該請(qǐng)求將 用該文件的 ID到達(dá) Peer,過程重復(fù)直到發(fā)現(xiàn)文件副本 ,最終文件下載到請(qǐng)求源端 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，將請(qǐng)求 轉(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ā)布 文件 id的路由信息 – 搜索 ：向路由表中最近的節(jié)點(diǎn)查詢文件 id，數(shù)據(jù)結(jié)構(gòu)保證查詢會(huì)找到發(fā)布節(jié)點(diǎn) – 獲取 ：兩個(gè)選項(xiàng) ? 查詢到的節(jié)點(diǎn)保存有文件，則從查詢結(jié)束的節(jié)點(diǎn)獲取 ? 查詢到的節(jié)點(diǎn)返回結(jié)果：節(jié)點(diǎn) x有文件，則從節(jié)點(diǎn) x獲取 ?DHT示例－ Chord:在一維空間（環(huán)）中給每個(gè)節(jié)點(diǎn)和文件一個(gè)唯一的 id – 例如從 [0...2m]中選取 – 通常是文件和 IP地址的 hash 2022/6/3 李之棠 HUST 54 Chord：插入 N32 N90 N105 K80 K20 K5 Circular ID space Key 5 Node 105 2022/6/3 李之棠 HUST 55 Chord：查找 N32 N90 N105 N60 N10 N120 K80 “Where is key 80?” “N90 has K80” 2022/6/3 李之棠 HUST 56 4 P2P關(guān)鍵技術(shù)特性 非集中化 :置疑 C/S 模式 ?集中化 – 在訪問權(quán)限和安全上容易管理 – 但不可避免導(dǎo)致 :低效 /瓶頸 /資源浪費(fèi) – 盡管硬件性能和成本有了改進(jìn) ,但建立和維護(hù)集中化知識(shí)庫成本高昂 ,需要人員智能化地建立 ,保持信息的相關(guān)和更新 ?非集中化 :更強(qiáng)有力的思想 – 強(qiáng)調(diào)用戶端所有權(quán) ,對(duì)數(shù)據(jù)和資源的控制 – 每個(gè) Peer都是平等的參與者 – 實(shí)現(xiàn)更困難 (無全局服務(wù)器 ,看不到全局 Peers及其文件 ) – 這也是當(dāng)前混合模式存在的原因 2022/6/3 李之棠 HUST 57 ?全非集中化文件系統(tǒng) (Gnutella Free) – 發(fā)現(xiàn)網(wǎng)絡(luò)是很困難的 – 新節(jié)點(diǎn)必須知道其他節(jié)點(diǎn) – 或由主機(jī)列表知道其他 Peers的 IP地址 – 該節(jié)點(diǎn)通過和現(xiàn)行網(wǎng)絡(luò)中至少一個(gè) Peer建立連接而加入網(wǎng)絡(luò) – 從而能發(fā)現(xiàn)其他 Peers并 Cache它們的 IP地址在本地 專用單服務(wù)器 (通過 Master) 混合 SETI@home Avaki 純 所有節(jié)點(diǎn)相同 超級(jí) Peers/Masters 多個(gè)專用服務(wù)器 Kazaa Free Gnutella Napster 平臺(tái) 分布計(jì)算 協(xié)同通信 文件共享 非集中化程度 JXTA .NET 各種P2P系統(tǒng)按非集中化程度分類 2022/6/3 李之棠 HUST 58 可擴(kuò)展性 ?可擴(kuò)展性受限的主要原因 – 需要完成大量的集中化操作 :如同步與一致 – 需要維護(hù)許多狀態(tài) – 固有的并行性應(yīng)用展開 – 用來表示計(jì)算的編程模式 ?P2P解決可擴(kuò)展性問題 – Napster在其服務(wù)的高峰用戶達(dá)到 600萬 – 然 SETI@hone2022年止用戶 僅接近 350萬 .因?yàn)樗性诓⑿卸扔邢薜娜蝿?wù)上 ,依靠因特網(wǎng)上的可用計(jì)算力來分析從天文望遠(yuǎn)鏡收集來的數(shù)據(jù) ,搜索外星生命 – Avaki通過提供分布式對(duì)象模型來解決可擴(kuò)展性問題 2022/6/3 李之棠 HUST 59 ?Napster是通過故意保留許多集中化文件操作來實(shí)現(xiàn) 達(dá)到好的擴(kuò)展性并不是擴(kuò)大其它所希望的特點(diǎn) ?Gnutella和 Free:早期的 P2P系統(tǒng)具有 Adhoc的特點(diǎn) ,Peer必須把請(qǐng)求盲目發(fā)送到許多其他 Peers,促使它們搜索請(qǐng)求的文件 ?CAN,Chord,Oceanstore PST:最近的 P2P系統(tǒng) – 專注在目標(biāo)鍵和目標(biāo)節(jié)點(diǎn)間找到一致的映射 – 每個(gè)節(jié)點(diǎn)僅維護(hù)較少的系統(tǒng)節(jié)點(diǎn)信息及其狀態(tài) ,故增加了可擴(kuò)展性 – 這些系統(tǒng)設(shè)計(jì)規(guī)模是 數(shù) 10億用戶 ,數(shù)百萬服務(wù)器和 1014個(gè)文件 ?未來 :帶寬和計(jì)算能力繼續(xù)增長 ,P2P平臺(tái)能利用這些能力去完成人們感興趣的應(yīng)用 ,結(jié)構(gòu)將更自治可擴(kuò)展 ,提供更多的資源 ,展開更多的應(yīng)用 2022/6/3 李之棠 HUST 60 匿名 ?目的 – 重要目的是讓人們使用系統(tǒng)時(shí)不用關(guān)心法律問題和其他節(jié)外生枝的問題 – 進(jìn)一步目的可能使數(shù)字內(nèi)容的審查制度形同虛設(shè) ?匿名形式 – 作者 :可以不標(biāo)識(shí)文件的作者或創(chuàng)建者 – 發(fā)布者 :可以不標(biāo)識(shí)對(duì)系統(tǒng)而言的文件發(fā)行者 – 讀者 :可以不標(biāo)識(shí)文件的讀者或其他消費(fèi)數(shù)據(jù)者 – 服務(wù)器 :可以不標(biāo)識(shí)含有未被標(biāo)識(shí)文件的服務(wù)器 – 文件 :服務(wù)器并不知道它存儲(chǔ)的是什么文件 – 查詢 :服務(wù)器并不告訴它正用何文件在響應(yīng)用戶的查詢 2022/6/3 李之棠 HUST 61 ?必須在 通信對(duì)之間強(qiáng)迫執(zhí)行 3種匿名 ,才能達(dá)到上述匿名 (不管何種匿名形式 ) – 發(fā)送者匿名 :隱藏發(fā)送者的標(biāo)識(shí)符 – 接收者匿名 :隱藏接收者的標(biāo)識(shí)符 – 相互匿名 :隱藏發(fā)送者何接收者的標(biāo)識(shí)符 ,且雙方標(biāo)識(shí)符對(duì)其他 Peers也是隱藏的 ?匿名程度 – 絕對(duì)隱私 – 不可懷疑 :即使攻擊者能看到已發(fā)送消息的證據(jù) ,但 發(fā)送者似乎并不比系統(tǒng)潛在的發(fā)送者更像真正的發(fā)送者 – 大概無罪 – 可能曝光 2022/6/3 李之棠 HUST 62 6種不同技術(shù) 適合不同匿名方式 ?多播使接收者匿名 ?發(fā)送者地址欺騙 UDP偽造其地址 ?標(biāo)識(shí)符欺騙 改變通信參與者標(biāo)識(shí)符 ?隱蔽通道 通過某些中間節(jié)點(diǎn) ?難管的別名 代理服務(wù)器為客戶生成穩(wěn)固的別名 ?非志愿放置 文檔非志愿放置在承載(Hosting)主機(jī)上 2022/6/3 李之棠 HUST 63 項(xiàng)目 匿名技術(shù)與類型 發(fā)布者 讀者 服務(wù)器 文檔 Gnutella 組播 隱蔽通道 N/A N/A N/A