p2p原理與技術(編輯修改稿)

　

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