P2P原理與技術(shù)

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

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

3、? ?ABCDEFE?2022-3-67P2PP2P的網(wǎng)絡(luò)基本構(gòu)成的網(wǎng)絡(luò)基本構(gòu)成LinuxTCP/IPBluetoothHTTPTCP/IPTCP/IPXP2022-3-68P2P覆蓋網(wǎng)絡(luò)的概念（1）覆蓋網(wǎng)絡(luò)的結(jié)點2022-3-69P2P覆蓋網(wǎng)絡(luò)的概念（2）2022-3-610P2P覆蓋網(wǎng)絡(luò)的路由（1）結(jié)點結(jié)點的完全圖2022-3-611P2P覆蓋網(wǎng)絡(luò)的路由（2）2022-3-612覆蓋網(wǎng)絡(luò)n在現(xiàn)有網(wǎng)絡(luò)體系結(jié)構(gòu)上新加一層overlay networksn建立一個使用已有的Internet傳輸?shù)奶摂M網(wǎng)絡(luò)nInternet也曾經(jīng)被部署為一個在電話網(wǎng)上的重疊網(wǎng)絡(luò)n也被成為ALNnApplicatio

4、n-Level Network.nFile storage and searchn挑戰(zhàn)n如何創(chuàng)新和部署 at scale2022-3-613覆蓋網(wǎng)絡(luò)模型 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系統(tǒng)分類n無結(jié)構(gòu)P2P：文件位置與覆蓋網(wǎng)拓?fù)錈o關(guān)n有中心的：Napstern無中心的：Gnutella、Freenetn層次結(jié)構(gòu)：KaZaAn結(jié)構(gòu)化P2P：文件或文件索引的位置與覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)緊密相關(guān)n基于DHT：Chord、CAN、Pastry、Tapestry2022-3-615Napster原理(1)13245Server2022-3-616Napster原理(2)Where i

6、s file A?QueryReplysearch(A)Fetch目錄服務(wù)器2022-3-617Napster優(yōu)缺點n優(yōu)點：只維護目錄，結(jié)構(gòu)簡單，效率高n缺點：單點失效，存在瓶頸，法律問題2022-3-618洪泛請求模式n過程n每個Peer的請求直接廣播到連接的Peersn各Peers又廣播到各自的Peersn直到收到應(yīng)答或 達到最大洪泛步數(shù)n特點n無廣告性共享資源nGnutella 使用該算法,限于公司內(nèi)通信有效n大量請求占用網(wǎng)絡(luò)帶寬,可擴展性并不一定最好n改進nKazaa 設(shè)立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優(yōu)缺點n容錯性和健壯性好n覆蓋網(wǎng)拓?fù)渚S護簡單n查詢代價高，可擴展性差，flooding2022-3-622KaZaA原理n介于Napster和Gnutella之間n無中心，但有中心簇集n層次結(jié)構(gòu)，一個節(jié)點是超級節(jié)點或?qū)儆谀吵壒?jié)點的子節(jié)點n超級節(jié)點間采用flooding機制搜索2022-3-623KaZaA原理132Sup

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

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

10、Peers受影響n其路由表較小,但到達的路徑較長n可能更適合動態(tài)通信nTapestry與Pastry很相似n除減少跳數(shù)外,還積極削減每個P2P跳上的時延2022-3-628路由表n路由表內(nèi)容nid文件標(biāo)識符nnext_hop存儲文件id的另一個節(jié)點nfile保存在本地的文件標(biāo)識符為id的文件n搜索過程n如果文件id存儲在本地，停止搜索，上傳文件n如果不在本地，搜索路由表中最接近的id，將請求轉(zhuǎn)到next_hopn如果所有節(jié)點都沒有找到，返回失敗，返回路由表中下一個最接近的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表表分布式應(yīng)用分布式應(yīng)用get (key)datanodenodenode.put(key, data)查找服務(wù)查找服務(wù)lookup(key)node IP address(文件共享文件共享)(DHash)(Chord)2022-3-631結(jié)構(gòu)化覆蓋網(wǎng)的路由q加入：開始時，聯(lián)系一個“bootstrap”節(jié)點，加入分布式數(shù)

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

13、代碼是利用結(jié)點IP通過一個Hash函數(shù)（node hash function）計算得到。n每一個文件用一個文件代碼（File ID）表示，文件代碼是文件名通過一個Hash函數(shù)（file hash function）計算得到。2022-3-633Chord環(huán)定義n在一個穩(wěn)定狀態(tài)下，在有N個結(jié)點（peer）的系統(tǒng)中，每一個結(jié)點維護一個O（logN）個結(jié)點的路由狀態(tài)表。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環(huán)定義qHash函數(shù): 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環(huán)Chord環(huán)的 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環(huán)：路由算法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環(huán)：路由實例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維笛卡爾坐標(biāo)空間實現(xiàn)數(shù)據(jù)組織和查找功能。n利用類似網(wǎng)絡(luò)路由的方式來尋找文件所在的位置。n在CAN系統(tǒng)中，每一個結(jié)點利用一個坐標(biāo)路由表(coordinate routing table)記錄在坐標(biāo)空間中相鄰結(jié)點的IP地址和空間位置。n當(dāng)收到一個文檔查詢的請求時，起始結(jié)點先利用Hash函數(shù)計算出此文件所在的坐標(biāo)，并附在查詢請求中。n當(dāng)一個結(jié)點收到此文件的查詢請求時，先看查詢文件是否存在，若存在，則返回此文

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

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

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