【文章內容簡介】 2022/5/26 李之棠 HUST 40 Napster原理 Where is file A? Query Reply search(A) Fetch 2022/5/26 李之棠 HUST 41 洪泛請求模式 ?過程 – 每個 Peer的請求直接廣播到連接的 Peers – 各 Peers又廣播到各自的 Peers – 直到收到應答或 達到最大洪泛步數 (典型 59) ?特點 – 無廣告性共享資源 – Gnutella 使用該算法 ,限于公司內通信有效 – 大量請求占用網絡帶寬 ,可擴展性并不一定最好 ?改進 – Kazaa 設立 SuperPeer客戶軟件 ,以集中大量請求 – BT 文件分塊 – Cache最近請求 1 2 3 5 4 搜索 下載 6 2022/5/26 李之棠 HUST 42 Gnutella原理 I have file A. I have file A. Where is file A? Query Reply 2022/5/26 李之棠 HUST 43 KaZaA原理 I have X! Publish insert(X, ) ... 2022/5/26 李之棠 HUST 44 KaZaA原理 Where is file A? Query search(A) search(A) Replies 2022/5/26 李之棠 HUST 45 BitTorrent原理 Tracker A D C B 2022/5/26 李之棠 HUST 46 BitTorrent原理 A C B D 2022/5/26 李之棠 HUST 47 文件路由模式 ?過程 – 每個網上 Peer分配一個隨機 ID,并知道其他 Peers的給定號碼 – 當共享文件發(fā)布到系統(tǒng)上時 ,根據文件名字和內容 Hash成為 ID – 每個 Peer將根據 該 ID向該文件路由 – 該過程重復執(zhí)行 ,直到最近的 PeerID是現行 Peer的 ID – 每個路由操作還 保持文件副本在本地 – 當 Peer請求某文件時 ,該請求將 用該文件的 ID到達 Peer,過程重復直到發(fā)現文件副本 ,最終文件下載到請求源端 2022/5/26 李之棠 HUST 48 4個算法實現文件路由 ?Chord/CAN/Tapestry/Pastry ?目標相同 – 減少 路由到指定文件的 P2P跳數 – 減少 每個 Peer必須保持的 路由狀態(tài) ?算法異同 – 都保證算法的跳數與 Peer群組的大小相關 – 或都指出算法能以高概率完成 – 方法上的差別很小 2022/5/26 李之棠 HUST 49 ?Chord – 每個 Peer保持 LogN其他 Peer的蹤跡 (N是群組的全部 Peer數 ) – 當 Peer加入或離開時 ,高優(yōu)化算法版本僅需關注LogN個 Peers的變化 ?CAN – 每個 Peer保持 少于 LogN個其他 Peers的蹤跡 – 在插入和刪除時僅這些 Peers受影響 – 其路由表較小 ,但到達的路徑較長 – 可能 更適合動態(tài)通信 ?Tapestry與 Pastry很相似 – 除減少跳數外 ,還積極削減每個 P2P跳上的時延 2022/5/26 李之棠 HUST 50 路由表 ?路由表內容 – id－文件標識符 – next_hop－存儲文件 id的另一個節(jié)點 – file－保存在本地的 id標識文件 ?搜索過程 – 如果文件 id存儲在本地，停止搜索，上傳文件 – 如果不在本地， 搜索 路由表中 最接近的 id，將請求 轉到 next_hop – 如果所有節(jié)點都沒有找到，返回失敗，返回路由表 中下一個最接近的 id ID Next_hop file … 2022/5/26 李之棠 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 ?網絡趨向于一個小世界－ small world,類似六度分隔（ Six Degrees of Separation）理論 ?因此，大部分查詢只需經過少量跳數 2022/5/26 李之棠 HUST 52 Distributed Hash Table ?分布式數據結構系統(tǒng)中，可以是環(huán)，樹，超立方體，跳表，蝶形網絡 ... ?CFS, OceanStore, PAST, ChordDNS 分布式 Hash表 分布式應用 get (key) data node node node …. put(key, data) 查找服務 lookup(key) node IP address (文件共享 ) (DHash) (Chord) 2022/5/26 李之棠 HUST 53 ?結構化 重疊路由 – 加入 ：開始時，聯系一個 “ bootstrap”節(jié)點，加入分布式數據結構， 獲得一個節(jié)點 id – 發(fā)布 ：向數據結構中最近的節(jié)點發(fā)布 文件 id的路由信息 – 搜索 ：向路由表中最近的節(jié)點查詢文件 id，數據結構保證查詢會找到發(fā)布節(jié)點 – 獲取 ：兩個選項 ? 查詢到的節(jié)點保存有文件，則從查詢結束的節(jié)點獲取 ? 查詢到的節(jié)點返回結果：節(jié)點 x有文件，則從節(jié)點 x獲取 ?DHT示例－ Chord:在一維空間（環(huán)）中給每個節(jié)點和文件一個唯一的 id – 例如從 [0...2m]中選取 – 通常是文件和 IP地址的 hash 2022/5/26 李之棠 HUST 54 Chord：插入 N32 N90 N105 K80 K20 K5 Circular ID space Key 5 Node 105 2022/5/26 李之棠 HUST 55 Chord：查找 N32 N90 N105 N60 N10 N120 K80 “Where is key 80?” “N90 has K80” 2022/5/26 李之棠 HUST 56 4 P2P關鍵技術特性 非集中化 :置疑 C/S 模式 ?集中化 – 在訪問權限和安全上容易管理 – 但不可避免導致 :低效 /瓶頸 /資源浪費 – 盡管硬件性能和成本有了改進 ,但建立和維護集中化知識庫成本高昂 ,需要人員智能化地建立 ,保持信息的相關和更新 ?非集中化 :更強有力的思想 – 強調用戶端所有權 ,對數據和資源的控制 – 每個 Peer都是平等的參與者 – 實現更困難 (無全局服務器 ,看不到全局 Peers及其文件 ) – 這也是當前混合模式存在的原因 2022/5/26 李之棠 HUST 57 ?全非集中化文件系統(tǒng) (Gnutella Free) – 發(fā)現網絡是很困難的 – 新節(jié)點必須知道其他節(jié)點 – 或由主機列表知道其他 Peers的 IP地址 – 該節(jié)點通過和現行網絡中至少一個 Peer建立連接而加入網絡 – 從而能發(fā)現其他 Peers并 Cache它們的 IP地址在本地 專用單服務器 (通過 Master) 混合 SETI@home Avaki 純 所有節(jié)點相同 超級 Peers/Masters 多個專用服務器 Kazaa Free Gnutella Napster 平臺 分布計算 協(xié)同通信 文件共享 非集中化程度 JXTA .NET 各種P2P系統(tǒng)按非集中化程度分類 2022/5/26 李之棠 HUST 58 可擴展性 ?可擴展性受限的主要原因 – 需要完成大量的集中化操作 :如同步與一致 – 需要維護許多狀態(tài) – 固有的并行性應用展開 – 用來表示計算的編程模式 ?P2P解決可擴展性問題 – Napster在其服務的高峰用戶達到 600萬 – 然 SETI@hone2022年止用戶 僅接近 350萬 .因為它集中在并行度有限的任務上 ,依靠因特網上的可用計算力來分析從天文望遠鏡收集來的數據 ,搜索外星生命 – Avaki通過提供分布式對象模型來解決可擴展性問題 2022/5/26 李之棠 HUST 59 ?Napster是通過故意保留許多集中化文件操作來實現 達到好的擴展性并不是擴大其它所希望的特點 ?Gnutella和 Free:早期的 P2P系統(tǒng)具有 Adhoc的特點 ,Peer必須把請求盲目發(fā)送到許多其他 Peers,促使它們搜索請求的文件 ?CAN,Chord,Oceanstore PST:最近的 P2P系統(tǒng) – 專注在目標鍵和目標節(jié)點間找到一致的映射 – 每個節(jié)點僅維護較少的系統(tǒng)節(jié)點信息及其狀態(tài) ,故增加了可擴展性 – 這些系統(tǒng)設計規(guī)模是 數 10億用戶 ,數百萬服務器和 1014個文件 ?未來 :帶寬和計算能力繼續(xù)增長 ,P2P平臺能利用這些能力去完成人們感興趣的應用 ,結構將更自治可擴展 ,提供更多的資源 ,展開更多的應用 2022/5/26 李之棠 HUST 60 匿名 ?目的 – 重要目的是讓人們使用系統(tǒng)時不用關心法律問題和其他節(jié)外生枝的問題 – 進一步目的可能使數字內容的審查制度形同虛設 ?匿名形式 – 作者 :可以不標識文件的作者或創(chuàng)建者 – 發(fā)布者 :可以不標識對系統(tǒng)而言的文件發(fā)行者 – 讀者 :可以不標識文件的讀者或其他消費數據者 – 服務器 :可以不標識含有未被標識文件的服務器 – 文件 :服務器并不知道它存儲的是什么文件 – 查詢 :服務器并不告訴它正用何文件在響應用戶的查詢 2022/5/26 李之棠 HUST 61 ?必須在 通信對之間強迫執(zhí)行 3種匿名 ,才能達到上述匿名 (不管何種匿名形式 ) – 發(fā)送者匿名 :隱藏發(fā)送者的標識符 – 接收者匿名 :隱藏接收者的標識符 – 相互匿名 :隱藏發(fā)送者何接收者的標識符 ,且雙方標識符對其他 Peers也是隱藏的 ?匿名程度 – 絕對隱私 – 不可懷疑 :即使攻擊者能看到已發(fā)送消息的證據 ,但 發(fā)送者似乎并不比系統(tǒng)潛在的發(fā)送者更像真正的發(fā)送者 – 大概無罪 – 可能曝光 2022/5/26 李之棠 HUST 62 6種不同技術 適合不同匿名方式 ?多播使接收者匿名 ?發(fā)送者地址欺騙 UDP偽造其地址 ?標識符欺騙 改變通信參與者標識符 ?隱蔽通道 通過某些中間節(jié)點 ?難管的別名 代理服務器為客戶生成穩(wěn)固的別名 ?非志愿放置 文檔非志愿放置在承載(Hosting)主機上 2022/5/26 李之棠 HUST 63 項目 匿名技術與類型 發(fā)布者 讀者 服務器 文檔 Gnutella 組播 隱蔽通道 N/A N/