假設(shè)節(jié)點(diǎn)1001和1101還不是group1100的轉(zhuǎn)發(fā)器,。那么節(jié)點(diǎn)0111的加入將使得這個(gè)路由上的兩個(gè)節(jié)點(diǎn)成為該組的forwarder,并且把該點(diǎn)加入到它們的子表中,。假設(shè)節(jié)點(diǎn)0100決定加入這個(gè)組,，JOIN消息的路由在圖1中以點(diǎn)實(shí)線箭頭表示。由于1001點(diǎn)已經(jīng)是一個(gè)轉(zhuǎn)發(fā)器,，它把0100節(jié)點(diǎn)加到自己的子表中，JOIN消息就被中斷了,。
1.3 尋找最佳節(jié)點(diǎn)
　　從上面Scribe的節(jié)點(diǎn)加入機(jī)制可以看出,，Scribe最佳節(jié)點(diǎn)的選擇主要決定于Pastry將其JOIN消息路由到的第一個(gè)節(jié)點(diǎn),。而這一個(gè)點(diǎn)的選擇是依靠Pastry的路由表" title="路由表">路由表決定的,。所以,，為Scribe尋找最佳節(jié)點(diǎn)的工作,，其實(shí)就是在Pastry節(jié)點(diǎn)加入Pastry網(wǎng)絡(luò)時(shí)對(duì)節(jié)點(diǎn)路由表和葉子節(jié)點(diǎn)集合進(jìn)行的初始化上,。
　　在Pastry中，一個(gè)新節(jié)點(diǎn)X若加入Pastry網(wǎng)絡(luò),，必須知道一個(gè)在網(wǎng)絡(luò)上相近的節(jié)點(diǎn)A.X向A發(fā)出一個(gè)關(guān)鍵字為自己的路由請(qǐng)求,，這條信息將會(huì)一直轉(zhuǎn)發(fā)到在nodeId空間里離X最近的節(jié)點(diǎn)。X將接收路由過程中所有節(jié)點(diǎn)的路由表,，經(jīng)過整理后得到自己的路由表和葉子節(jié)點(diǎn)集合。
　　而一個(gè)新加入的點(diǎn)如何發(fā)現(xiàn)網(wǎng)絡(luò)上相近的Pastry節(jié)點(diǎn),，一種方法是使用一種叫“expanding ring”的IP組播方式,，但這需要網(wǎng)絡(luò)支持組播。Pastry使用了一種有效的算法,，它可以通過位于任何位置的Pastry節(jié)點(diǎn)找到離自己最近的節(jié)點(diǎn),。圖2的流程圖表示了Pastry的最佳節(jié)點(diǎn)發(fā)現(xiàn)算法,。這個(gè)算法使用了這樣一個(gè)屬性：種子(seed)節(jié)點(diǎn)的葉子節(jié)點(diǎn)集合的位置應(yīng)該在網(wǎng)絡(luò)上均勻地分布,。在葉子節(jié)點(diǎn)中找到較近節(jié)點(diǎn)后，路由表的距離屬性被用來成指數(shù)倍地減少靠近新加入的節(jié)點(diǎn),。這是通過在路由表中反復(fù)遞歸查找最近點(diǎn)實(shí)現(xiàn)的,。Pastry最近節(jié)點(diǎn)查找方法的詳細(xì)說明可參見參考文獻(xiàn)[2]。

?

　　從Pastry的節(jié)點(diǎn)加入算法可以看出,，Pastry保留了網(wǎng)絡(luò)鄰近性不變,。然而，在比較最近節(jié)點(diǎn)時(shí)是需要進(jìn)行實(shí)際測(cè)量的,，因此需要較長(zhǎng)的等待時(shí)間,。下面，將介紹如何縮短等待時(shí)間,。
1.4 優(yōu)化算法
1.4.1 歷史數(shù)據(jù)
　　任何一個(gè)Pastry節(jié)點(diǎn)在加入Pastry網(wǎng)絡(luò)之前,，對(duì)Pastry網(wǎng)絡(luò)的狀況都是一無(wú)所知的。但在加入這個(gè)網(wǎng)絡(luò)并平穩(wěn)運(yùn)行一段時(shí)間之后,，它會(huì)了解到對(duì)于它自己而言,，相對(duì)穩(wěn)定且臨近的Pastry節(jié)點(diǎn)和Scribe上層節(jié)點(diǎn)。因此在它退出之后,，再重新加入這個(gè)組播組時(shí),，這些歷史信息對(duì)它本身而言還是相對(duì)有效的,。但由于組成員是動(dòng)態(tài)的，原來網(wǎng)絡(luò)連接質(zhì)量好的節(jié)點(diǎn),，可能已經(jīng)離開了組播組,。如果它仍然在組播組中,，將會(huì)極大提高該節(jié)點(diǎn)尋找到最佳節(jié)點(diǎn)的速度,。
　　Pastry使用定時(shí)（每20分鐘）運(yùn)行的路由表管理任務(wù)來保證路由表中的每一入口都是nodeId滿足條件的節(jié)點(diǎn)當(dāng)中的最靠近自己的節(jié)點(diǎn)。當(dāng)發(fā)現(xiàn)比當(dāng)前節(jié)點(diǎn)更靠近自己的節(jié)點(diǎn)時(shí),，Pastry替換成更近的節(jié)點(diǎn),，并把原節(jié)點(diǎn)保留在一個(gè)備份列表中，以便當(dāng)最近節(jié)點(diǎn)失效時(shí),，可以馬上替換回來,。Pastry為每個(gè)入口最多保留10個(gè)備份節(jié)點(diǎn)，這些歷史數(shù)據(jù)對(duì)于該節(jié)點(diǎn)是非常寶貴的,，但是Pastry和Scribe只把這些數(shù)據(jù)保存在內(nèi)存中,，節(jié)點(diǎn)退出之后，這些數(shù)據(jù)就被釋放掉了,。而本算法則將這些數(shù)據(jù)定期保存到硬盤上,，這樣當(dāng)該節(jié)點(diǎn)再次進(jìn)入Pastry網(wǎng)絡(luò)時(shí)，可以充分利用這些歷史數(shù)據(jù),。
　　在后面的測(cè)試數(shù)據(jù)中可以看出,，在組播組的人數(shù)達(dá)到一定規(guī)模的穩(wěn)態(tài)時(shí)，該算法能夠有效提高最佳節(jié)點(diǎn)查找的速度,。但是這個(gè)算法對(duì)于第一次加入的節(jié)點(diǎn)沒有任何作用,。
1.4.2 IP地址庫(kù)
　　在我國(guó)，由于眾所周知的原因,，中國(guó)電信和中國(guó)網(wǎng)通兩大電信運(yùn)營(yíng)商之間的網(wǎng)絡(luò)互聯(lián)非常差,。而Pastry中nodeId的生成是不考慮實(shí)際網(wǎng)絡(luò)位置的。在nodeId空間中,，相鄰兩點(diǎn)在網(wǎng)絡(luò)位置上相距很遠(yuǎn)的可能性非常大,。也就是說，nodeId相鄰的兩個(gè)點(diǎn)很可能一個(gè)在網(wǎng)通,，一個(gè)在電信,。如果在這種條件下，仍然采用1.2節(jié)中的算法尋找最佳節(jié)點(diǎn),，就會(huì)耽誤很多時(shí)間,。
經(jīng)過多年的測(cè)試和搜集，已經(jīng)有人成功地搜集完中國(guó)電信,、中國(guó)網(wǎng)通以及其他中國(guó)主要ISP的IP地址網(wǎng)段,。如果在使用圖2的尋找方案中,，充分利用該IP地址庫(kù)，則可以有效降低等待網(wǎng)絡(luò)探測(cè)的時(shí)間,，加快最佳節(jié)點(diǎn)的尋找速度,。這一算法對(duì)提高新節(jié)點(diǎn)第一次加入組播組的速度會(huì)有一些幫助。但是,，這個(gè)算法只對(duì)中國(guó)或互聯(lián)網(wǎng)狀況類似中國(guó)的網(wǎng)絡(luò)才適用,。
1.4.3? 算法的實(shí)現(xiàn)
　　實(shí)現(xiàn)過程：
?　　(1)在Scribe節(jié)點(diǎn)正常運(yùn)行中，定期地將節(jié)點(diǎn)的路由表,、葉子節(jié)點(diǎn)集合,、Ping包延時(shí)表等相關(guān)數(shù)據(jù)保存到硬盤上。當(dāng)節(jié)點(diǎn)退出后再進(jìn)入時(shí),，首先載入這些歷史數(shù)據(jù)和IP地址數(shù)據(jù)庫(kù),，然后按照?qǐng)D3的流程進(jìn)行處理。
　　(2)圖3顯示了根據(jù)優(yōu)化算法對(duì)Pastry節(jié)點(diǎn)加入網(wǎng)絡(luò)初始化時(shí)的流程圖,。

?

　　圖3與圖2比較可以發(fā)現(xiàn),，第2、3,、5,、7、9步為修改的地方,。第2步,，如果種子節(jié)點(diǎn)原來就在本機(jī)保存的最佳節(jié)點(diǎn)紀(jì)錄中，直接返回最佳節(jié)點(diǎn),。第3步,，如果種子節(jié)點(diǎn)的IP地址和本機(jī)不屬于同一個(gè)電信運(yùn)營(yíng)商,，重新抓取另一個(gè)種子（系統(tǒng)通常會(huì)提供多個(gè)種子）,，但不屬于同一個(gè)ISP的兩點(diǎn)在網(wǎng)絡(luò)上相鄰的可能性很小。第5,、7,、9步，在從某個(gè)集合中挑選最近節(jié)點(diǎn)時(shí),，都使用類似第2,、3步的判斷方法：首先查看該點(diǎn)是否是本機(jī)保存的最佳節(jié)點(diǎn)，如果是,，就直接跳到第12步,，結(jié)束搜索過程。如果不是,，則比較該點(diǎn)IP地址是否和本機(jī)屬于同一個(gè)ISP,如果不是,，則跳過測(cè)試比較的步驟,，節(jié)省搜索時(shí)間；如果是,，則仍按照以前的步驟,，進(jìn)行測(cè)試比較。下面的實(shí)驗(yàn)表明,，該算法可以有效提高Scribe最佳節(jié)點(diǎn)的選擇速度,。
2 性能分析和測(cè)試
2.1 試驗(yàn)環(huán)境和機(jī)制介紹
　　Pastry提供的網(wǎng)絡(luò)模擬器是基于包級(jí)別的、離散的網(wǎng)絡(luò)模擬器,。這個(gè)模擬器可以模擬物理鏈路上的傳播延時(shí),，最多可以模擬10萬(wàn)個(gè)節(jié)點(diǎn)，但是不能模擬排隊(duì)延時(shí),、包丟失,。
　　實(shí)驗(yàn)使用Pastry的配置為b=4, 葉子節(jié)點(diǎn)集合大小l=16。利用Pastry/Scribe提供的API及例子程序開發(fā)一個(gè)小程序,。該程序設(shè)定所有的Pastry節(jié)點(diǎn)都運(yùn)行Scribe,，不運(yùn)行其他的P2P應(yīng)用。每個(gè)Scribe節(jié)點(diǎn)都加入同一個(gè)組播組,，第一個(gè)節(jié)點(diǎn)既當(dāng)信息發(fā)布源,，又當(dāng)組播樹的根。其他的節(jié)點(diǎn)一旦加入Pastry就立刻加入組播組,，并開始接收數(shù)據(jù),。把N個(gè)節(jié)點(diǎn)一個(gè)一個(gè)地加入，計(jì)算每個(gè)節(jié)點(diǎn)從加入開始到正常接收Scribe數(shù)據(jù)的時(shí)間,，然后計(jì)算平均值,。在不同的N值分別測(cè)試10次，以利用程序保存下來的歷史數(shù)據(jù),。把模擬試驗(yàn)所使用的N×N的延時(shí)矩陣文件,，人為分為兩個(gè)部分，分別模擬兩大運(yùn)營(yíng)商,。并在程序中給出類似IP地址的區(qū)分判斷,。由于試驗(yàn)設(shè)備的限制，本次試驗(yàn)的N的最大值為4 000,。
　　以Pastry提供的網(wǎng)絡(luò)模擬器測(cè)試經(jīng)過優(yōu)化過的Scribe程序,。作為比較，把沒有經(jīng)過優(yōu)化的Scribe程序也在相同的模擬器上運(yùn)行,。由于模擬器本身對(duì)時(shí)間參數(shù)作了優(yōu)化,，因此，時(shí)間的絕對(duì)值可能沒有什么參考價(jià)值，但優(yōu)化程序的加速比率卻有一定的參考意義,。
2.2 試驗(yàn)數(shù)據(jù)和結(jié)論
　　測(cè)試的結(jié)果如圖4所示,。從圖中可以看出，隨著節(jié)點(diǎn)數(shù)的增加,，節(jié)點(diǎn)選擇最佳節(jié)點(diǎn)的時(shí)間也在增加,。這主要是由于節(jié)點(diǎn)多時(shí)，節(jié)點(diǎn)加入需要交換的信息也越來越多所致,。從兩種算法的比較可以看出,，優(yōu)化的算法在節(jié)點(diǎn)數(shù)少時(shí)，沒有任何優(yōu)勢(shì),。這主要是因?yàn)楣?jié)點(diǎn)少,，需要進(jìn)行測(cè)試的時(shí)間也比較少，加速優(yōu)勢(shì)體現(xiàn)不明顯,。隨著節(jié)點(diǎn)的增多,，可以看出，經(jīng)過優(yōu)化的算法要比原算法有優(yōu)勢(shì),。原算法的最佳節(jié)點(diǎn)的平均尋找時(shí)間起伏比較大,，而優(yōu)化的算法則相對(duì)比較穩(wěn)定。新算法的節(jié)點(diǎn)加入速度大約是原算法的95%左右,。

?

　　本文介紹了利用歷史數(shù)據(jù)和IP地址庫(kù)提高Scribe最佳節(jié)點(diǎn)查找速度的一種算法,。模擬實(shí)驗(yàn)顯示，該算法對(duì)于中國(guó)的互聯(lián)網(wǎng)現(xiàn)狀還是有一定效果的,。下一步的工作,，應(yīng)當(dāng)充分考慮最佳節(jié)點(diǎn)的其他標(biāo)準(zhǔn)，統(tǒng)一優(yōu)化查找速度,。事實(shí)上,，該算法不僅可以用來提高Scribe最佳節(jié)點(diǎn)的查找速度，也同樣適用于所有結(jié)構(gòu)化P2P網(wǎng)絡(luò)上的應(yīng)用層組播系統(tǒng),。