1、2022-3-61P2P原理與技術簡介暨南大學計算機科學系周繼鵬2022-3-62P2P原理與技術的內容q P2P概念q P2P分類q 構件與算法q 關鍵技術特性q P2P分析與比較q 研究與未來2022-3-631、什么是P2P（Peer-to-Peer）nP2P：對等(網絡，計算);端到端n以非集中方式使用分布式資源來完成關鍵任務的一類系統和應用n資源包括計算能力、數據（存儲和內容）、網絡帶寬和場景（計算機、人和其它資源）n關鍵任務可能是分布式計算、數據/內容共享，通信和協同、或平臺服務n節點是服務和數據的提供者又是需求者n共享資源可被網絡上其他節點直接訪問2022-3-64P2P系統特點

2、n可擴展性、自組織、容錯性、高動態性可擴展性、自組織、容錯性、高動態性n數據的位置往往是不固定的數據的位置往往是不固定的n沒有統一的全局模式，查詢基于關鍵字沒有統一的全局模式，查詢基于關鍵字n節點可能不包含完整的數據，因此對于節點可能不包含完整的數據，因此對于查詢的回答往往不完整查詢的回答往往不完整2022-3-65P2P系統的應用n共享文件n流媒體系統n對等計算文件共享系統-maze,北京大學n視頻直播系統AnySee，華中科技大學n在線電視直播-PPLivenBT下載軟件n(如視頻直播的思想是直播系統中的節點既下在載數據也上傳數據.)2022-3-66如何找到指定的信息如何找到指定的信息

3、? ?ABCDEFE?2022-3-67P2PP2P的網絡基本構成的網絡基本構成LinuxTCP/IPBluetoothHTTPTCP/IPTCP/IPXP2022-3-68P2P覆蓋網絡的概念（1）覆蓋網絡的結點2022-3-69P2P覆蓋網絡的概念（2）2022-3-610P2P覆蓋網絡的路由（1）結點結點的完全圖2022-3-611P2P覆蓋網絡的路由（2）2022-3-612覆蓋網絡n在現有網絡體系結構上新加一層overlay networksn建立一個使用已有的Internet傳輸的虛擬網絡nInternet也曾經被部署為一個在電話網上的重疊網絡n也被成為ALNnApplicatio

4、n-Level Network.nFile storage and searchn挑戰n如何創新和部署 at scale2022-3-613覆蓋網絡模型 Overlay Network routing table peer 1 Internet: Supporting Netork A Generic Topological Model of P2P Systems routing and locating algorithm Data Storage Data Cache routing table peer 2 routing and locating algorithm Data Sto

5、rage Data Cache routing table peer n routing and locating algorithm Data Storage Data Cache 2022-3-614P2P系統分類n無結構P2P：文件位置與覆蓋網拓撲無關n有中心的：Napstern無中心的：Gnutella、Freenetn層次結構：KaZaAn結構化P2P：文件或文件索引的位置與覆蓋網的拓撲結構緊密相關n基于DHT：Chord、CAN、Pastry、Tapestry2022-3-615Napster原理(1)13245Server2022-3-616Napster原理(2)Where i

6、s file A?QueryReplysearch(A)Fetch目錄服務器2022-3-617Napster優缺點n優點：只維護目錄，結構簡單，效率高n缺點：單點失效，存在瓶頸，法律問題2022-3-618洪泛請求模式n過程n每個Peer的請求直接廣播到連接的Peersn各Peers又廣播到各自的Peersn直到收到應答或 達到最大洪泛步數n特點n無廣告性共享資源nGnutella 使用該算法,限于公司內通信有效n大量請求占用網絡帶寬,可擴展性并不一定最好n改進nKazaa 設立Super-Peer客戶軟件,以集中大量請求n文件分塊nCache最近請求2022-3

7、-619Gnutella原理 (1)Flooding: Loop Prevention2022-3-620Gnutella原理(2)I have file A.I have file A.Where is file A?QueryReply2022-3-621Gnutella優缺點n容錯性和健壯性好n覆蓋網拓撲維護簡單n查詢代價高，可擴展性差，flooding2022-3-622KaZaA原理n介于Napster和Gnutella之間n無中心，但有中心簇集n層次結構，一個節點是超級節點或屬于某超級節點的子節點n超級節點間采用flooding機制搜索2022-3-623KaZaA原理132Sup

8、er Nodes:1,2,32022-3-624KaZaA原理Where is file A?Querysearch(A)-8search(A)-0Replies802022-3-625有結構系統的文件路由模式n過程n每個網上Peer分配一個隨機ID,并知道其他Peers的給定號碼n當共享文件發布到系統上時,根據文件名字和內容Hash成為IDn每個Peer將根據該ID向該文件路由n該過程重復執行,直到最近的PeerID是現行Peer的IDn每個路由操作還保持文件副本在本地n當Peer請求某文件時,該請求將用該文件的ID

9、到達Peer,過程重復直到發現文件副本,最終文件下載到請求源端2022-3-626實現文件路由算法nChord/CAN/Tapestry/Pastryn目標相同n減少路由到指定文件的P2P跳數n減少每個Peer必須保持的路由狀態n算法異同n都保證算法的跳數與Peer群組的大小相關n或都指出算法能以高概率完成n方法上的差別很小2022-3-627四個算法的比較nChordn每個Peer保持LogN其他Peer的蹤跡(N是群組的全部Peer數)n當Peer加入或離開時,高優化算法版本僅需關注LogN個Peers的變化nCANn每個Peer保持少于LogN個其他Peers的蹤跡n在插入和刪除時僅這些

10、Peers受影響n其路由表較小,但到達的路徑較長n可能更適合動態通信nTapestry與Pastry很相似n除減少跳數外,還積極削減每個P2P跳上的時延2022-3-628路由表n路由表內容nid文件標識符nnext_hop存儲文件id的另一個節點nfile保存在本地的文件標識符為id的文件n搜索過程n如果文件id存儲在本地，停止搜索，上傳文件n如果不在本地，搜索路由表中最接近的id，將請求轉到next_hopn如果所有節點都沒有找到，返回失敗，返回路由表中下一個最接近的idIDNext_hopfile2022-3-629文件路由原理 4 n1 f412 n2 f12 5 n3 9 n3 f9

11、 3 n1 f314 n4 f14 5 n314 n5 f1413 n2 f13 3 n6n1n2n3n4 4 n1 f410 n5 f10 8 n6n5query(10)1234452022-3-630Distributed Hash Table（DHT）分布式分布式Hash表表分布式應用分布式應用get (key)datanodenodenode.put(key, data)查找服務查找服務lookup(key)node IP address(文件共享文件共享)(DHash)(Chord)2022-3-631結構化覆蓋網的路由q加入：開始時，聯系一個“bootstrap”節點，加入分布式數

12、據結構，獲得一個節點idq發布：向數據結構中最近的節點發布文件id的路由信息q搜索：向路由表中最近的節點查詢文件id，數據結構保證查詢會找到發布節點q獲?。簝蓚€選項n查詢到的節點保存有文件，則從查詢結束的節點獲取n查詢到的節點返回結果：節點x有文件，則從節點x獲取q DHT示例Chord:在一維空間（環）中給每個節點和文件一個唯一的idn例如從0.2m中選取n通常是文件和IP地址的hash2022-3-632ChordnChord系統提出了一個利用一致性的Hash函數將所有結點和文件對應到一個N個整數形成的邏輯環上的P2P系統。n每一個結點有一個代碼（node ID）表示在邏輯環上的位置。結點

13、代碼是利用結點IP通過一個Hash函數（node hash function）計算得到。n每一個文件用一個文件代碼（File ID）表示，文件代碼是文件名通過一個Hash函數（file hash function）計算得到。2022-3-633Chord環定義n在一個穩定狀態下，在有N個結點（peer）的系統中，每一個結點維護一個O（logN）個結點的路由狀態表。nVertex Set: 0N-1 : N is a power of 2nEdge Set: (u, v) | v-u is a power of 2nex: N=64, u=0, then the neighbors of u a

14、re 1, 2, 4, 8, 16, 322022-3-634Chord環定義qHash函數: node InodeID, data DdataIDqnodeID, dataID in 0, ., N -1 where N =2mqPut data D on node I, so that nodeID(I) is smallest nodeID larger than or equal to dataID(D)qGiven key=dataID(D), how to find successor(key) ? Lookup(key)=successor(key), find the firs

15、t live nodeID which is key.qFinger table: node k stores pointers to k+1, k+2, k+4 ., k +2m -1 (mod N) qFind node for every data in O(log(N) steps; O(log(N) storage per node0 1 2 3 4 . 7 8 9 . 14 15 16 . . . n-2 n-12022-3-635Chord環Chord環的 finger表121314171819202223302928272625211516240123456783191011A

16、ctual nodeNode identifier24345791217205767812121220201315141516202020281Node 1s finger tableNode 4s finger tableNode 12s finger tableStart = k + 2i (modulo 2m) IP addr of successor (start )A ring of 25 node Ids. m =5, i = 0m-1 .2022-3-637Chord環：路由算法When node k receives the lookup(key),If k key next(

17、k), return next(k) elseif key k at intermediate node k, return kelse forward to f such that f=MAXfingers|fingerskeyChord環：路由實例12131417181920222330292827262521151624012345678319101124345791217205767812121220201315141516202020281Node 1s finger tableNode 4s finger tableNode 12s finger tableStart = k +

18、2i (modulo 2m) IP addr of successor (start )Look up key=14,15,16,17 at node 1.2022-3-639CANn基于虛擬的d維笛卡爾坐標空間實現數據組織和查找功能。n利用類似網絡路由的方式來尋找文件所在的位置。n在CAN系統中，每一個結點利用一個坐標路由表(coordinate routing table)記錄在坐標空間中相鄰結點的IP地址和空間位置。n當收到一個文檔查詢的請求時，起始結點先利用Hash函數計算出此文件所在的坐標，并附在查詢請求中。n當一個結點收到此文件的查詢請求時，先看查詢文件是否存在，若存在，則返回此文

19、件；否則，利用查找路由表找出一個與查找文件位置最近的結點；以此繼續下去。2022-3-640CAN2022-3-641P2P的關鍵技術特性（的關鍵技術特性（1）（1）非集中化）非集中化:置疑置疑 C/S 模式模式n集中化n在訪問權限和安全上容易管理n但不可避免導致:低效/瓶頸/資源浪費n盡管硬件性能和成本有了改進,但建立和維護集中化知識庫成本高昂,需要人員智能化地建立,保持信息的相關和更新n非集中化:更強有力的思想n強調用戶端所有權,對數據和資源的控制n每個Peer都是平等的參與者n實現更困難(無全局服務器,看不到全局Peers及其文件)n這也是當前混合模式存在的原因2022-3-642（2）

20、可擴展性）可擴展性n可擴展性受限的主要原因n需要完成大量的集中化操作:如同步與一致n需要維護許多狀態n固有的并行性應用展開n用來表示計算的編程模式nP2P解決可擴展性問題nNapster在其服務的高峰用戶達到 600萬n然SETIhone2002年止用戶 僅接近350萬.因為它集中在并行度有限的任務上,依靠因特網上的可用計算力來分析從天文望遠鏡收集來的數據,搜索外星生命nAvaki通過提供分布式對象模型來解決可擴展性問題2022-3-643（3）匿名n目的目的n重要目的是讓人們使用系統時不用關心法律問題和其他節外重要目的是讓人們使用系統時不用關心法律問題和其他節外生枝的問題生枝的問題n進一步目

21、的可能使數字內容的審查制度形同虛設進一步目的可能使數字內容的審查制度形同虛設n匿名形式匿名形式n作者作者:可以不標識文件的作者或創建者可以不標識文件的作者或創建者n發布者發布者:可以不標識對系統而言的文件發行者可以不標識對系統而言的文件發行者n讀者讀者:可以不標識文件的讀者或其他消費數據者可以不標識文件的讀者或其他消費數據者n服務器服務器:可以不標識含有未被標識文件的服務器可以不標識含有未被標識文件的服務器n文件文件:服務器并不知道它存儲的是什么文件服務器并不知道它存儲的是什么文件n查詢查詢:服務器并不告訴它正用何文件在響應用戶的查詢服務器并不告訴它正用何文件在響應用戶的查詢2022-3-6446種不同技術-適合不同匿名方式n多播使接收者匿名