1、第三章 第二代P2P網絡無結構P2P體系Gnutella、KaZaA、eDonkey、Freenet1章節內容3.1 Gnutella：純分布式無結構P2P網絡3.2 KaZaA：基于超節點的無結構P2P網絡3.3 eDonkey/eMule：分塊下載的雙層無結構P2P網絡3.4 Freenet：自由、安全、匿名的無結構P2P網絡3.5 無結構P2P網絡的特點23.1 Gnutella：純分布式無結構P2PGnutella的歷史Nullsoft公司，MP3播放軟件WinAmp的發明人Justin Frankel、Tom Pepper開發2000年3月14日在網站上公開Gnutella軟件一個半

2、小時后，母公司AOL(American Online)擔心步Napster后塵，關閉了網站數千名MP3迷下載了軟件并公開與改造其純分布式無結構P2P網絡思想廣泛流傳Gnutella已不單純對應具體軟件，而是當作一種典型的無結構P2P網絡協議3一、Gnutella體系的工作原理Gnutella協議0.4版(0.6版加入了超結點Ultrapeer，結構有變化)4協議開發者稱Peer為Servent(Server +Client)，網絡中只有peer，沒有serverGnutella覆蓋網上每個結點對應一臺實際的計算機每條連接對應一條點到點的鏈路覆蓋網上的連接由每個peer保存的“鄰居結點”信息確定

3、，有一個鄰居結點即對應有一條邊5新結點加入時，必須首先連接到“眾所周知”幾乎總是在線的Gnutella結點(稱為“自舉”結點、“入口結點”)Gnutella網中的消息可以被廣播或回播(back-propagate，沿廣播的反向路徑回傳消息)，協議設計的支持機制：每條消息具有一個隨機產生的全局唯一標識符GUID(16字節)以互相區分每個結點緩存最近路由的消息以支持回播并阻止不必要的重廣播每條消息都有TTL以避免過度消耗網絡資源6Gnutella的典型消息組成員消息：PING，PONG新結點加入時廣播PING消息，或用來探測其它結點是否仍然存在(心跳)結點收到PING消息后，可以決定是否回播PON

4、G消息，以及是否將PING轉發給鄰居，PONG消息包含結點IP,port,共享文件數量大小查詢消息：QUERY，QUERY RESPONSEQUERY消息用來查詢文件,包含查詢內容與最小響應速度等附加信息,但不包含源結點信息RESPONSE消息包含文件下載的必須信息及該結點的nodeID，沿QUERY消息路徑回播7文件傳輸消息：GET，PUSH結點收到QUERY RESPONSE消息后用GET消息請求獲得文件對處于防火墻后因而不能直接響應文件請求的結點，使用PUSH消息請求防火墻后的文件擁有者主動建立到自己的連接8Gnutella的文件檢索過程泛洪式搜索(flooding search)， 系

5、統開銷大有限深度TTL(Time to Live)， 不保證一定查詢到已有文件9Gnutella網絡的維護各結點使用PING、PONG消息探測其他結點存在與否，在收到PING消息后，可以自主決定是否回播PONG，并根據TTL數值決定是否繼續廣播PING消息具有一定的自組織和自適應性10二、Gnutella網絡的性能分析Ripeanu,2001,2002、Saroiu et al., 2002,2003、Adar & Huberman, 2002Gnutella用戶的連接帶寬僅在Query response消息中作為輔助信息回播，因此，Gnutella網絡中不共享文件的用戶或其共享的文件與查詢請

6、求一直不匹配的用戶，不會主動發布帶寬Gnutella網絡中結點功能平等，但能力有差異（異構性），如連接帶寬在無組織的Gnutella網絡組織方式下，70%的結點承受較高時延(280ms)11用戶連接時間與Napster類似，超過50%的用戶連接時間6h25%的用戶不共享任何文件，75%的用戶共享文件數低于100，僅7%共享文件超過1000，即文獻中的Free-Riding(搭便車)現象，對網絡的高效工作不利Gnutella網絡相當于社會網絡，可用冪律(Power-law)分布網絡近似，擁有連接數L的結點占網絡總結點的份額正比于L-a,a是取決于網絡本身的常數因子，Gnutella網絡a=2.3

7、，容錯性較高12早期Gnutella網絡中，PING消息占所有消息的50%以上，顯示其自適應機制低效。改進后的Gnutella網絡，對用戶真正有用的Query消息占總消息的90%以上Gnutella覆蓋網絡與物理網絡的拓撲一致性較低，影響工作效率13采用Gnutella協議的P2P網絡應解決：結點異構性：充分利用結點能力Free-Riding：鼓勵上傳，限制或剝奪Free-Rider的權利保持高容錯性：高效的機制檢測和恢復網絡分割繼續優化查詢機制，TTL的取值拓撲一致性14三、Napster與Gnutella的比較共同點P2P的文件共享思想系統中的對等實體(peer)之間是對稱的，既是客戶又是

8、服務器，既提供下載又提供上傳可擴展性都不高：但Napster是因為C/S結構，Gnutella是因為泛洪搜索策略造成的系統開銷都有結點異構性問題以及搭便車現象15不同點Napster有服務器，Gnutella沒有，因此工作機制完全不同網絡結構不同：混合式與純分布式，Gnutella在Internet網上構建了覆蓋網，這是后來的P2P網絡都會做的一項基礎性工作Napster中文件只要存在一般都能查詢到，Gnutella不一定Napster只在服務器故障時出錯，Gnutella可能因為結點信息陳舊而出錯，最大的問題是可能導致網絡分割16Gnutella協議0.6版層次化的無結構P2P網絡173.2

9、 KaZaA：基于超結點的無結構P2P網絡2000年7月，基于FastTrack協議Niklas及Friis，P2P創業家，Joltid, Altnet, SkypeFastTrack協議引入超結點SuperNode，開發結點異構性18一、KaZaA的工作原理KaZaA是私有協議，并對消息加密，對其理解基于測量與分析的結果19節點異構性帶寬、處理能力、存儲容量、NAT訪問方式超結點高帶寬、高處理能力、大存儲容量、不受NAT限制功能上類似Napster中的服務器，但并非專門、永久的，經常由普通結點轉變而來20普通結點加入網絡時選擇一個“父超結點”，并維持一條半永久的TCP連接，將其共享的文件元數

10、據(也稱“文件索引”)上傳文件索引分布在KaZaA的超結點中，作用是將文件標識符映射到文件所在的結點IP文件索引包括：文件名、文件大小、文件內容Hash值、文件描述符(如藝術家、專輯名)文件內容Hash值的作用：當下載失敗時，可自動搜索文件，不必再做關鍵詞查詢21用戶查詢文件向父超結點發送帶有文件關鍵詞的查詢消息超結點在自己的數據庫中尋找匹配的文件索引返回給用戶文件所在的IP地址、port、文件元數據超結點間局部保持著長期的TCP連接，構成超結點覆蓋網文件查詢局部性問題22二、KaZaA協議的應用KaZaA用戶應當具有4個軟件構件KMD(KaZaA Media Desktop)存儲在Windo

11、ws注冊表中的軟件環境信息，其中包含一個有200個超結點信息(IP、port)的列表(超結點列表緩存)DBB文件：包含用戶希望共享的文件的元數據DAT文件：每個DAT文件是一個部分下載的文件，下載完成后，將被重命名為下載的原始文件23KaZaA用戶間的4種TCP通信方式信號通信，包括：為建立連接的握手通信，將DBB文件從普通結點上傳到超結點，超結點列表更新、查詢和回復。所有的信號通信都加密文件傳輸通信：用戶間直接的文件傳輸，以HTTP消息發送，不加密商業廣告：通過HTTP發送實時消息通信：采用Base64編碼24三、KaZaA的技術細節自適應通過結點間交換超結點列表實現每次普通結點連接到超結點

12、，后者立刻回送超結點更新列表，其中第一項為自己的IP,port以及工作負載值相鄰的超結點間也交換超結點更新列表結點間的連接普通結點與超結點（一對多UDP，選擇父超結點）超結點之間2526KaZaA的防火墻穿透：動態端口KaZaA的NAT穿透A無法與NAT后的B建立直接的TCP連接A發送請求到B的父超結點S，S發送消息到B，通知B應該由B發出到A的連接請求，主動建立一條到A的TCP連接，A通過此連接從B下載文件。稱為“連接反轉”(connection reversal)27四、KaZaA的性能分析基于文獻Liang et al., 2004; 2005的測量結果KaZaA網絡的超結點數在2500

13、0-40000之間，每個超結點平均與40-60個超結點連接，與60-150個普通結點連接KaZaA覆蓋網動態性：連接保持時間ON-SN平均34min，38%低于30minSN-SN平均11min，32%低于30min結點主動改變連接，超結點頻繁交換列表28KaZaA網絡局部性60%的SN-SN連接RTT (往返時間round trip time)小于50ms，40%的ON-SN連接RTT小于5ms超結點返回給普通結點的超結點列表中，很高比例的超結點與該普通結點的IP前綴相似結論：采用了提高局部性的方法KaZaA索引管理13%的ON上傳了超過80%的元數據SN之間不交互索引信息29五、KaZaA

14、網絡總結首次顯式開發P2P網絡節點異構性為緩解無結構P2P網絡的查詢局部性問題，并保持KaZaA網絡的自適應性，KaZaA用戶間頻繁地交換超結點更新列表，根據列表改變原有連接測量結果顯示KaZaA網絡考慮了局部性因素Free-Riding現象在KaZaA網絡中依然存在KaZaA通過使用動態端口和連接反轉的方法，有效地穿透防火墻和NAT，拓寬了網絡適用范圍303.3 eDonkey/eMule：分塊下載的雙層無結構P2P網絡2000年eDonkey出現，特點：文件分塊，可并行下載使用文件內容散列值驗證數據完整性雙層無結構，使用超結點作為“服務器”基于Overnet分布式搜索網絡eMule出現于2

15、002年5月，是對eDonkey客戶端的出色改進31一、eDonkey工作原理32eDonkey客戶加入網絡首先連接到“入口服務器”列表中離自己最近(時延最小)的一臺服務器通過該入口服務器獲得一個普通服務器列表，從中選擇最合適的服務器建立連接并斷開與入口服務器的連接客戶將自己的共享文件信息發給服務器客戶從存放自己信息的服務器查詢文件，如無結果，則可以向其它服務器重新查詢33eDonkey客戶下載文件前，首先通過查詢獲得文件提供者列表，然后向列表中的每個文件提供者請求“上傳槽”(upload slot)文件提供者將請求放進上傳隊列的“等待列表”，等到條件滿足時才給該請求分配“上傳槽”并將它放進“

16、上傳列表”，此時提供者向請求者發起TCP連接，決定要發送哪些分塊，然后發送數據自適應性每個下載者必須周期性地(40s)向上傳者重發下載請求，否則原連接將被關閉eDonkey服務器間以較長周期交換服務器列表34二、eDonkey文件分塊類似BT的文件分片，實現了“多源下載”機制文件首先被分塊chunk，通常9500KB每個chunk分成多個片段segment，其大小取決于“智能錯誤處理”(intelligent corruption handling,ICH)機制用來進行比分塊更小的數據單元錯誤檢查，從而不必在出錯時丟棄整個分塊片段分成小塊block，通常180KB35三、eDonkey性能分析

17、部分類似KaZaA，部分類似BT，定性分析可參照二者4662端口專用于客戶間TCP連接下載連接傳輸總量占所有流傳輸總量的70.5%，不高在所建立的TCP連接中，只有2.24%用作下載連接，不如BT高效的重要原因36四、eDonkey網絡總結雙層：服務器層+客戶層，類似于KaZaA， 服務器提供文件索引和交換服務器列表，開發了結點異構性將文件逐級分成分塊、片段、小塊，從而提供了類似BT的多源文件下載機制，并且對文件的完整性檢查也有了更細的粒度為適應動態的網絡環境，eDonkey客戶通過上傳隊列來管理客戶間的連接，只有獲得上傳槽的連接才能真正傳遞數據，并且每個連接都有周期性檢測以處理異常中斷，提高

18、了工作效率靠服務器間周期性地更新服務器列表維護自適應性，eDonkey的流行性驗證了該機制是良好的373.4 Freenet：自由、安全、匿名的無結構P2P網絡自由網的概念由Clarke于1999年提出，2000年3月推出第一版，更新很慢Freenet的理念：共享Internet計算機資源，組建一個自由、安全、匿名的信息發布和獲取的平臺(不同于其它P2P網絡)Freenet結點劃出一部分硬盤作為公用存儲空間，但其中數據加密，僅對有權限者開放Freenet匿名性的本質在于其隧道路由機制Freenet過于自由、界面不友好限制其發展38一、Freenet的密碼學基礎Freenet中的文件以Hash值

19、作為標識，使用SHA-1安全散列函數生成Freenet使用三種不同類型的文件標識，KSK，SSK，CHK，分別完成不同的功能，是Freenet的核心設施，三者相互獨立，可以合并使用39KSKKeyword-signed key，關鍵詞簽名標識，用于構建Freenet的全局名空間用戶在網絡中存儲文件時，必須給文件指定一個很短的描述性字符串作為輸入產生一對非對稱密鑰，公鑰被Hash以產生文件標識，私鑰用來給文件做數字簽名，附帶提供了文件的完整性檢查字符串本身被作為密鑰來加密原來的文件為讓其他人獲取文件，只需發布該文件的描述性字符串問題：用戶選取的字符串容易相同從而文件標識相同40SSKSigned

20、-subspace key，簽名子空間標識，用以構建Freenet的個人名空間用戶通過隨機地產生一對非對稱密鑰來標識自己的名空間存儲文件時，首先也是指定一個很短的描述性字符串，然后分別Hash該字符串和名空間公鑰，再將兩個Hash值異或，再次Hash異或值產生文件標識；私鑰用來給文件簽名，但比KSK安全；字符串仍作為密鑰加密原來的文件發布文件時，同樣發布描述性字符串及文件標識即可41CHKContent-hash key，內容散列標識，實現文件的更新與分割，將文件直接Hash得到的散列值就是它的CHKCHK使用一個隨機產生的密鑰加密文件發布文件時，只需發布解密密鑰與文件標識通常與SSK一起使用

21、，實現文件更新用CHK存儲文件，用SSK存儲一個間接文件，此文件的內容就是CHK，相當于指向真實文件的指針更新文件時，先用新的CHK存儲新文件，使用原來的SSK再存儲一個新的間接文件，原間接文件所在的結點發現文件標識沖突，確認簽名合法后更新間接文件42顯然，Freenet中的文件更新僅僅是間接文件的更新，新舊文件實際共存于網絡之中，后者可通過舊CHK訪問CHK用于文件分割用戶將文件分成多個部分，每部分使用它自己的CHK來存儲，最后存儲一個間接文件（或者多層的間接文件）來指向文件的各個部分分割的好處：減少對單個結點存儲容量和帶寬的需求；對抗通信量分析43二、Freenet中數據的查詢與獲取基于文

22、件標識的“導向路由”為獲取文件，用戶首先獲得或計算出文件標識，同時設置好請求消息的跳數限制，然后在自己的路由表里查找與該文件標識最接近的文件標識并把請求發送給與之相應的結點接收到請求的結點如果擁有該文件，則回送消息，否則按前述方法繼續轉發，若最終查詢文件被回送，該結點除了將文件回傳給請求者，還會在自己的數據庫里緩存該文件，并在自己的路由表里創建一個指向新項該文件的數據源44當某個結點嘗試所有可路由結點仍無結果時，則返回失敗消息給自己的前一跳，由后者嘗試新的下一跳，即“深度優先”搜索策略，直至達到跳數限制（注：跳數可在途中任意減少）安全路由路由表自適應更新威脅到了網絡的安全性和匿名性Freene

23、t同意消息傳送路徑上的每一個結點都可以單方面修改消息，將消息原來的請求者或者文件源改成任意一個結點45簡單示例46這樣的數據查詢和獲取機制，可以極大提高效率，即，若某個結點在其他結點的路由表中被列為是與某個文件相關的結點，則很可能會收到越來越多的對該文件的請求或與該文件相近的文件請求，產生“標識集群”效應。隨著時間的推移，文件被復制得更多更優化，結點路由表表項也更多更“近”47三、Freenet中數據的存儲與管理存儲數據用戶使用文件標識中的一種（KSK, SSK, CHK）給文件計算標識，并設置請求消息的跳數限制，然后發送文件插入消息到Freenet網收到文件插入消息的結點，首先檢查自己的數據

24、庫中是否有該文件標識，有則回送此文件，請求方據此判斷是該文件確實已經存在還是文件標識碰巧沖突，對前者用戶不需要再插入，對后者重新計算文件標識再做插入48當已達到跳數限制且未檢測到文件標識沖突時，回送“一切順利”的消息，直至到達發出最初請求的用戶，該用戶沿此路徑插入文件，路徑上每個結點在其路由表中增加與此文件標識相關的項（對應結點為虛擬的文件源）49存儲機制與網絡性能文件通常被存儲到已經擁有相近標識文件的結點上，加強了“標識集群”效應新結點可以通過插入文件宣布自己的存在惡意結點不僅無法通過插入與已有文件標識相同的垃圾文件來“排擠”原文件，反而促使原文件的信息在網絡中更廣泛傳播50數據管理結點的存

25、儲區（大小由用戶指定）按照最近使用優先（least recently used,LRU）方式管理被替換掉的舊文件在路由表中對應的項還會保留，直至路由表也發生超容量替換LRU對存儲的利用高效，但無法保證某個文件在網絡中至少有一份拷貝存在51數據私密性文件經過加密后存放，存放結點用戶無法獲知文件內容，滿足了數據的保密性需求，且Freenet用戶可以否認對任何關于其數據庫中文件內容的了解Freenet將網絡中所有用戶的存儲區組織成了一個巨大的分布式系統，并且這個系統對于每個用戶來說都是透明和不可知的52四、Freenet網絡新結點加入Freenet新結點的標識選取要求為了正確、高效地路由，該標識應該

26、全局一致出于安全性考慮，不能讓其他結點通過某些屬性計算出結點標識（用于對網絡的惡意攻擊）Freenet采用加密協議選取標識新結點選擇一個隨機的“種子”并發送一條布告消息給某個現存的結點，其中包含自己的IP、種子的Hash值及跳數限制53收到該消息的結點也產生一個隨機的種子將該種子與消息中的Hash值異或對結果進行Hash產生一個“承諾”(commitment)從自己的路由表中隨機選擇一個結點發給它新的布告消息（其中包含“承諾”）這個過程一直繼續下去形成一條鏈，直至布告消息中的跳數限制清零最后一個收到布告消息的結點只產生自己的種子，不再做其他的事54整個過程結束以后，這條鏈中所有的結點都公布它們

27、各自的種子，所有種子的異或值就是新結點的標識鏈上的每個結點將新結點的標識加入路由表對“承諾”的檢查使得鏈中的每個結點都確認其它結點所公布的種子是真實的，因此，Freenet所采用的鏈式方法實際上產生了一個全局一致的隨機的結點標識，并且這個標識不可能被某個惡意加入者影響55五、Freenet協議細節Freenet協議面向數據包并且使用了相互獨立的消息，每條消息包含一個隨機產生的事務ID，因此結點可以追蹤插入、查詢消息的狀態一個跳數限制，減少攻擊者通過跳數限制所能獲得的信息，在跳數限制減少到1以后消息仍有繼續往前傳的概率（跳數限制一直為1）一個深度計數器，消息每走一跳深度計數器+1回復結點以此為依

28、據設置回復消息的跳數限制56Freenet事務一般從結點發送的握手消息開始，其中包含發送者的IP（可能是虛擬的）接收結點回復后，建立的連接可以持續幾個小時，在此期間兩結點之間隨后的事務不需要再次握手為獲取數據，用戶發送“請求數據”消息，包含事務ID、跳數限制、深度計數器和查詢關鍵碼；同時開啟一個定時器并根據跳數限制設定時間，若定時用完還未收到回復，就認為查詢失??；當請求數據的消息被處理時，遠處的結點可能會周期性地回發“重設定時器”消息，從而發送者可以繼續等待57如果數據請求成功，提供數據的結點會回送“發送數據”消息，包含請求者所要的數據和數據提供者的地址（可能虛擬）如果數據請求失敗，且跳數限制

29、用完，回送“未發現”消息；如果失敗但跳數未用完，通常是因為找不到可行的非循環的路徑，回送“繼續請求”消息，包含剩下的跳數，請求信息的發送者收到此消息后將嘗試新的下一跳58為存儲數據，用戶發送“插入請求”消息，包含事務ID、跳數限制、深度計數器和“建議”關鍵碼（用戶建議采用的文件標識）如果插入導致文件標識沖突，遠處結點返回“發送數據”消息，并返回現存的文件“未找到”消息，表示現存文件未找到，但路由表有所指向如果沒有文件標識沖突，但消息在跳數限制用完之前就跑完了所有的結點，遠處結點將回送“繼續請求”消息，表示不能聯系到足夠多的結點導致失敗跳數限制用完且沒有文件標識沖突時，返回“插入應答”消息，文件

30、插入者發送“發送插入數據”消息，包含要插入的文件，沿途結點緩存該文件59六、Freenet性能分析路由效率結點的文件緩存、路由表都是逐步構造出來的初期路由效率低，路由跳數大；后期“標識集群”路由效率提高，直至平穩可擴展性P2P網絡中決定可擴展性的最重要因素是路由跳數h與網絡結點總數N之間的關系，達到對數關系即認為是高可擴展的Freenet服從對數關系，即hO(logN)60七、Freenet的安全性和匿名性分析Freenet設計的目標和初衷系統的匿名性：發送者匿名、接收者匿名、文件標識匿名、關系匿名Freenet提供了很好的發送者匿名和接收者匿名，但無法進行文件標識匿名，因其依靠文件標識路由；

31、研究者提出“預定路由”的輔助路由方法，對消息加密并以此指定路由61防范DOS(denial of service,服務拒絕)攻擊攻擊者可能通過插入大量的垃圾文件破壞Freenet或降低其工作效率散列支付（hash cash），規定向Freenet網中插入文件的用戶在插入之前必須做一次耗時的計算作為插入文件的支付代價，降低插入速度將每個Freenet結點的存儲區分成兩部分，分別存放舊文件與新插入文件，這樣攻擊者無論插入多少垃圾文件，最多只能占用一般存儲區62八、Freenet體系總結突出特點：自由、安全、匿名的P2P網絡利用每個參加者作為一個結點，劃分一部分硬盤用作存儲空間，存放經過加密的數據，

32、存放者不知道內容，這是Freenet安全的核心Freenet中文件查詢通過一條“代理結點鏈”從一個結點傳到另一個結點，路徑上的每個結點只知道該請求的前一跳結點和由它決定的后一跳結點，對路徑上的其他結點一無所知，這種“隧道路由”是Freenet匿名的核心Freenet能夠自適應地將使用到的文件緩存到更接近使用者的服務器上，即自動復制網上的內容63Freenet中消息是通過結點路由表中保存的文件標識來導向路由的，文件標識有三種：KSK、SSK和CHK。消息路由采用改造過的圖的深度優先算法Freenet中插入文件之前先要檢測是否存在文件標識沖突。結點存儲區按照LRU方法更新，文件可以分割成多份保存在多個結點中。每個新結點加入Freenet網時，其結點標識是由