寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)-PowerPointPre

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

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

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

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

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

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

7、，容錯(cuò)性較高12早期Gnutella網(wǎng)絡(luò)中，PING消息占所有消息的50%以上，顯示其自適應(yīng)機(jī)制低效。改進(jìn)后的Gnutella網(wǎng)絡(luò)，對(duì)用戶真正有用的Query消息占總消息的90%以上Gnutella覆蓋網(wǎng)絡(luò)與物理網(wǎng)絡(luò)的拓?fù)湟恢滦暂^低，影響工作效率13采用Gnutella協(xié)議的P2P網(wǎng)絡(luò)應(yīng)解決：結(jié)點(diǎn)異構(gòu)性：充分利用結(jié)點(diǎn)能力Free-Riding：鼓勵(lì)上傳，限制或剝奪Free-Rider的權(quán)利保持高容錯(cuò)性：高效的機(jī)制檢測(cè)和恢復(fù)網(wǎng)絡(luò)分割繼續(xù)優(yōu)化查詢機(jī)制，TTL的取值拓?fù)湟恢滦?4三、Napster與Gnutella的比較共同點(diǎn)P2P的文件共享思想系統(tǒng)中的對(duì)等實(shí)體(peer)之間是對(duì)稱的，既是客戶又是

8、服務(wù)器，既提供下載又提供上傳可擴(kuò)展性都不高：但Napster是因?yàn)镃/S結(jié)構(gòu)，Gnutella是因?yàn)榉汉樗阉鞑呗栽斐傻南到y(tǒng)開(kāi)銷都有結(jié)點(diǎn)異構(gòu)性問(wèn)題以及搭便車現(xiàn)象15不同點(diǎn)Napster有服務(wù)器，Gnutella沒(méi)有，因此工作機(jī)制完全不同網(wǎng)絡(luò)結(jié)構(gòu)不同：混合式與純分布式，Gnutella在Internet網(wǎng)上構(gòu)建了覆蓋網(wǎng)，這是后來(lái)的P2P網(wǎng)絡(luò)都會(huì)做的一項(xiàng)基礎(chǔ)性工作Napster中文件只要存在一般都能查詢到，Gnutella不一定Napster只在服務(wù)器故障時(shí)出錯(cuò)，Gnutella可能因?yàn)榻Y(jié)點(diǎn)信息陳舊而出錯(cuò)，最大的問(wèn)題是可能導(dǎo)致網(wǎng)絡(luò)分割16Gnutella協(xié)議0.6版層次化的無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)173.2

9、 KaZaA：基于超結(jié)點(diǎn)的無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)2000年7月，基于FastTrack協(xié)議Niklas及Friis，P2P創(chuàng)業(yè)家，Joltid, Altnet, SkypeFastTrack協(xié)議引入超結(jié)點(diǎn)SuperNode，開(kāi)發(fā)結(jié)點(diǎn)異構(gòu)性18一、KaZaA的工作原理KaZaA是私有協(xié)議，并對(duì)消息加密，對(duì)其理解基于測(cè)量與分析的結(jié)果19節(jié)點(diǎn)異構(gòu)性帶寬、處理能力、存儲(chǔ)容量、NAT訪問(wèn)方式超結(jié)點(diǎn)高帶寬、高處理能力、大存儲(chǔ)容量、不受NAT限制功能上類似Napster中的服務(wù)器，但并非專門(mén)、永久的，經(jīng)常由普通結(jié)點(diǎn)轉(zhuǎn)變而來(lái)20普通結(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)選擇一個(gè)“父超結(jié)點(diǎn)”，并維持一條半永久的TCP連接，將其共享的文件元數(shù)

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

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

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

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

14、網(wǎng)絡(luò)總結(jié)首次顯式開(kāi)發(fā)P2P網(wǎng)絡(luò)節(jié)點(diǎn)異構(gòu)性為緩解無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)的查詢局部性問(wèn)題，并保持KaZaA網(wǎng)絡(luò)的自適應(yīng)性，KaZaA用戶間頻繁地交換超結(jié)點(diǎn)更新列表，根據(jù)列表改變?cè)羞B接測(cè)量結(jié)果顯示KaZaA網(wǎng)絡(luò)考慮了局部性因素Free-Riding現(xiàn)象在KaZaA網(wǎng)絡(luò)中依然存在KaZaA通過(guò)使用動(dòng)態(tài)端口和連接反轉(zhuǎn)的方法，有效地穿透防火墻和NAT，拓寬了網(wǎng)絡(luò)適用范圍303.3 eDonkey/eMule：分塊下載的雙層無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)2000年eDonkey出現(xiàn)，特點(diǎn)：文件分塊，可并行下載使用文件內(nèi)容散列值驗(yàn)證數(shù)據(jù)完整性雙層無(wú)結(jié)構(gòu)，使用超結(jié)點(diǎn)作為“服務(wù)器”基于Overnet分布式搜索網(wǎng)絡(luò)eMule出現(xiàn)于2

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

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

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

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

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

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

21、，實(shí)現(xiàn)文件更新用CHK存儲(chǔ)文件，用SSK存儲(chǔ)一個(gè)間接文件，此文件的內(nèi)容就是CHK，相當(dāng)于指向真實(shí)文件的指針更新文件時(shí)，先用新的CHK存儲(chǔ)新文件，使用原來(lái)的SSK再存儲(chǔ)一個(gè)新的間接文件，原間接文件所在的結(jié)點(diǎn)發(fā)現(xiàn)文件標(biāo)識(shí)沖突，確認(rèn)簽名合法后更新間接文件42顯然，F(xiàn)reenet中的文件更新僅僅是間接文件的更新，新舊文件實(shí)際共存于網(wǎng)絡(luò)之中，后者可通過(guò)舊CHK訪問(wèn)CHK用于文件分割用戶將文件分成多個(gè)部分，每部分使用它自己的CHK來(lái)存儲(chǔ)，最后存儲(chǔ)一個(gè)間接文件（或者多層的間接文件）來(lái)指向文件的各個(gè)部分分割的好處：減少對(duì)單個(gè)結(jié)點(diǎn)存儲(chǔ)容量和帶寬的需求；對(duì)抗通信量分析43二、Freenet中數(shù)據(jù)的查詢與獲取基于文

22、件標(biāo)識(shí)的“導(dǎo)向路由”為獲取文件，用戶首先獲得或計(jì)算出文件標(biāo)識(shí)，同時(shí)設(shè)置好請(qǐng)求消息的跳數(shù)限制，然后在自己的路由表里查找與該文件標(biāo)識(shí)最接近的文件標(biāo)識(shí)并把請(qǐng)求發(fā)送給與之相應(yīng)的結(jié)點(diǎn)接收到請(qǐng)求的結(jié)點(diǎn)如果擁有該文件，則回送消息，否則按前述方法繼續(xù)轉(zhuǎn)發(fā)，若最終查詢文件被回送，該結(jié)點(diǎn)除了將文件回傳給請(qǐng)求者，還會(huì)在自己的數(shù)據(jù)庫(kù)里緩存該文件，并在自己的路由表里創(chuàng)建一個(gè)指向新項(xiàng)該文件的數(shù)據(jù)源44當(dāng)某個(gè)結(jié)點(diǎn)嘗試所有可路由結(jié)點(diǎn)仍無(wú)結(jié)果時(shí)，則返回失敗消息給自己的前一跳，由后者嘗試新的下一跳，即“深度優(yōu)先”搜索策略，直至達(dá)到跳數(shù)限制（注：跳數(shù)可在途中任意減少）安全路由路由表自適應(yīng)更新威脅到了網(wǎng)絡(luò)的安全性和匿名性Freene

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

24、庫(kù)中是否有該文件標(biāo)識(shí)，有則回送此文件，請(qǐng)求方據(jù)此判斷是該文件確實(shí)已經(jīng)存在還是文件標(biāo)識(shí)碰巧沖突，對(duì)前者用戶不需要再插入，對(duì)后者重新計(jì)算文件標(biāo)識(shí)再做插入48當(dāng)已達(dá)到跳數(shù)限制且未檢測(cè)到文件標(biāo)識(shí)沖突時(shí)，回送“一切順利”的消息，直至到達(dá)發(fā)出最初請(qǐng)求的用戶，該用戶沿此路徑插入文件，路徑上每個(gè)結(jié)點(diǎn)在其路由表中增加與此文件標(biāo)識(shí)相關(guān)的項(xiàng)（對(duì)應(yīng)結(jié)點(diǎn)為虛擬的文件源）49存儲(chǔ)機(jī)制與網(wǎng)絡(luò)性能文件通常被存儲(chǔ)到已經(jīng)擁有相近標(biāo)識(shí)文件的結(jié)點(diǎn)上，加強(qiáng)了“標(biāo)識(shí)集群”效應(yīng)新結(jié)點(diǎn)可以通過(guò)插入文件宣布自己的存在惡意結(jié)點(diǎn)不僅無(wú)法通過(guò)插入與已有文件標(biāo)識(shí)相同的垃圾文件來(lái)“排擠”原文件，反而促使原文件的信息在網(wǎng)絡(luò)中更廣泛傳播50數(shù)據(jù)管理結(jié)點(diǎn)的存

25、儲(chǔ)區(qū)（大小由用戶指定）按照最近使用優(yōu)先（least recently used,LRU）方式管理被替換掉的舊文件在路由表中對(duì)應(yīng)的項(xiàng)還會(huì)保留，直至路由表也發(fā)生超容量替換LRU對(duì)存儲(chǔ)的利用高效，但無(wú)法保證某個(gè)文件在網(wǎng)絡(luò)中至少有一份拷貝存在51數(shù)據(jù)私密性文件經(jīng)過(guò)加密后存放，存放結(jié)點(diǎn)用戶無(wú)法獲知文件內(nèi)容，滿足了數(shù)據(jù)的保密性需求，且Freenet用戶可以否認(rèn)對(duì)任何關(guān)于其數(shù)據(jù)庫(kù)中文件內(nèi)容的了解Freenet將網(wǎng)絡(luò)中所有用戶的存儲(chǔ)區(qū)組織成了一個(gè)巨大的分布式系統(tǒng)，并且這個(gè)系統(tǒng)對(duì)于每個(gè)用戶來(lái)說(shuō)都是透明和不可知的52四、Freenet網(wǎng)絡(luò)新結(jié)點(diǎn)加入Freenet新結(jié)點(diǎn)的標(biāo)識(shí)選取要求為了正確、高效地路由，該標(biāo)識(shí)應(yīng)該

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

27、各自的種子，所有種子的異或值就是新結(jié)點(diǎn)的標(biāo)識(shí)鏈上的每個(gè)結(jié)點(diǎn)將新結(jié)點(diǎn)的標(biāo)識(shí)加入路由表對(duì)“承諾”的檢查使得鏈中的每個(gè)結(jié)點(diǎn)都確認(rèn)其它結(jié)點(diǎn)所公布的種子是真實(shí)的，因此，F(xiàn)reenet所采用的鏈?zhǔn)椒椒▽?shí)際上產(chǎn)生了一個(gè)全局一致的隨機(jī)的結(jié)點(diǎn)標(biāo)識(shí)，并且這個(gè)標(biāo)識(shí)不可能被某個(gè)惡意加入者影響55五、Freenet協(xié)議細(xì)節(jié)Freenet協(xié)議面向數(shù)據(jù)包并且使用了相互獨(dú)立的消息，每條消息包含一個(gè)隨機(jī)產(chǎn)生的事務(wù)ID，因此結(jié)點(diǎn)可以追蹤插入、查詢消息的狀態(tài)一個(gè)跳數(shù)限制，減少攻擊者通過(guò)跳數(shù)限制所能獲得的信息，在跳數(shù)限制減少到1以后消息仍有繼續(xù)往前傳的概率（跳數(shù)限制一直為1）一個(gè)深度計(jì)數(shù)器，消息每走一跳深度計(jì)數(shù)器+1回復(fù)結(jié)點(diǎn)以此為依

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

29、用完，回送“未發(fā)現(xiàn)”消息；如果失敗但跳數(shù)未用完，通常是因?yàn)檎也坏娇尚械姆茄h(huán)的路徑，回送“繼續(xù)請(qǐng)求”消息，包含剩下的跳數(shù)，請(qǐng)求信息的發(fā)送者收到此消息后將嘗試新的下一跳58為存儲(chǔ)數(shù)據(jù)，用戶發(fā)送“插入請(qǐng)求”消息，包含事務(wù)ID、跳數(shù)限制、深度計(jì)數(shù)器和“建議”關(guān)鍵碼（用戶建議采用的文件標(biāo)識(shí)）如果插入導(dǎo)致文件標(biāo)識(shí)沖突，遠(yuǎn)處結(jié)點(diǎn)返回“發(fā)送數(shù)據(jù)”消息，并返回現(xiàn)存的文件“未找到”消息，表示現(xiàn)存文件未找到，但路由表有所指向如果沒(méi)有文件標(biāo)識(shí)沖突，但消息在跳數(shù)限制用完之前就跑完了所有的結(jié)點(diǎn)，遠(yuǎn)處結(jié)點(diǎn)將回送“繼續(xù)請(qǐng)求”消息，表示不能聯(lián)系到足夠多的結(jié)點(diǎn)導(dǎo)致失敗跳數(shù)限制用完且沒(méi)有文件標(biāo)識(shí)沖突時(shí)，返回“插入應(yīng)答”消息，文件

30、插入者發(fā)送“發(fā)送插入數(shù)據(jù)”消息，包含要插入的文件，沿途結(jié)點(diǎn)緩存該文件59六、Freenet性能分析路由效率結(jié)點(diǎn)的文件緩存、路由表都是逐步構(gòu)造出來(lái)的初期路由效率低，路由跳數(shù)大；后期“標(biāo)識(shí)集群”路由效率提高，直至平穩(wěn)可擴(kuò)展性P2P網(wǎng)絡(luò)中決定可擴(kuò)展性的最重要因素是路由跳數(shù)h與網(wǎng)絡(luò)結(jié)點(diǎn)總數(shù)N之間的關(guān)系，達(dá)到對(duì)數(shù)關(guān)系即認(rèn)為是高可擴(kuò)展的Freenet服從對(duì)數(shù)關(guān)系，即hO(logN)60七、Freenet的安全性和匿名性分析Freenet設(shè)計(jì)的目標(biāo)和初衷系統(tǒng)的匿名性：發(fā)送者匿名、接收者匿名、文件標(biāo)識(shí)匿名、關(guān)系匿名Freenet提供了很好的發(fā)送者匿名和接收者匿名，但無(wú)法進(jìn)行文件標(biāo)識(shí)匿名，因其依靠文件標(biāo)識(shí)路由；

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

32、存放者不知道內(nèi)容，這是Freenet安全的核心Freenet中文件查詢通過(guò)一條“代理結(jié)點(diǎn)鏈”從一個(gè)結(jié)點(diǎn)傳到另一個(gè)結(jié)點(diǎn)，路徑上的每個(gè)結(jié)點(diǎn)只知道該請(qǐng)求的前一跳結(jié)點(diǎn)和由它決定的后一跳結(jié)點(diǎn)，對(duì)路徑上的其他結(jié)點(diǎn)一無(wú)所知，這種“隧道路由”是Freenet匿名的核心Freenet能夠自適應(yīng)地將使用到的文件緩存到更接近使用者的服務(wù)器上，即自動(dòng)復(fù)制網(wǎng)上的內(nèi)容63Freenet中消息是通過(guò)結(jié)點(diǎn)路由表中保存的文件標(biāo)識(shí)來(lái)導(dǎo)向路由的，文件標(biāo)識(shí)有三種：KSK、SSK和CHK。消息路由采用改造過(guò)的圖的深度優(yōu)先算法Freenet中插入文件之前先要檢測(cè)是否存在文件標(biāo)識(shí)沖突。結(jié)點(diǎn)存儲(chǔ)區(qū)按照LRU方法更新，文件可以分割成多份保存在多個(gè)結(jié)點(diǎn)中。每個(gè)新結(jié)點(diǎn)加入Freenet網(wǎng)時(shí)，其結(jié)點(diǎn)標(biāo)識(shí)是由