假設(shè)節(jié)點(diǎn)1001和1101還不是group1100的轉(zhuǎn)發(fā)器。那么節(jié)點(diǎn)0111的加入將使得這個路由上的兩個節(jié)點(diǎn)成為該組的forwarder,并且把該點(diǎn)加入到它們的子表中,。假設(shè)節(jié)點(diǎn)0100決定加入這個組,，JOIN消息的路由在圖1中以點(diǎn)實(shí)線箭頭表示。由于1001點(diǎn)已經(jīng)是一個轉(zhuǎn)發(fā)器,，它把0100節(jié)點(diǎn)加到自己的子表中,，JOIN消息就被中斷了。
1.3 尋找最佳節(jié)點(diǎn)
　　從上面Scribe的節(jié)點(diǎn)加入機(jī)制可以看出,，Scribe最佳節(jié)點(diǎn)的選擇主要決定于Pastry將其JOIN消息路由到的第一個節(jié)點(diǎn),。而這一個點(diǎn)的選擇是依靠Pastry的路由表" title="路由表">路由表決定的。所以,，為Scribe尋找最佳節(jié)點(diǎn)的工作,，其實(shí)就是在Pastry節(jié)點(diǎn)加入Pastry網(wǎng)絡(luò)時對節(jié)點(diǎn)路由表和葉子節(jié)點(diǎn)集合進(jìn)行的初始化上。
　　在Pastry中,，一個新節(jié)點(diǎn)X若加入Pastry網(wǎng)絡(luò),，必須知道一個在網(wǎng)絡(luò)上相近的節(jié)點(diǎn)A.X向A發(fā)出一個關(guān)鍵字為自己的路由請求，這條信息將會一直轉(zhuǎn)發(fā)到在nodeId空間里離X最近的節(jié)點(diǎn),。X將接收路由過程中所有節(jié)點(diǎn)的路由表,，經(jīng)過整理后得到自己的路由表和葉子節(jié)點(diǎn)集合,。
　　而一個新加入的點(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)算法。這個算法使用了這樣一個屬性：種子(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)時是需要進(jìn)行實(shí)際測量的,，因此需要較長的等待時間,。下面，將介紹如何縮短等待時間,。
1.4 優(yōu)化算法
1.4.1 歷史數(shù)據(jù)
　　任何一個Pastry節(jié)點(diǎn)在加入Pastry網(wǎng)絡(luò)之前,，對Pastry網(wǎng)絡(luò)的狀況都是一無所知的。但在加入這個網(wǎng)絡(luò)并平穩(wěn)運(yùn)行一段時間之后,，它會了解到對于它自己而言，相對穩(wěn)定且臨近的Pastry節(jié)點(diǎn)和Scribe上層節(jié)點(diǎn),。因此在它退出之后,，再重新加入這個組播組時，這些歷史信息對它本身而言還是相對有效的,。但由于組成員是動態(tài)的，原來網(wǎng)絡(luò)連接質(zhì)量好的節(jié)點(diǎn),，可能已經(jīng)離開了組播組,。如果它仍然在組播組中，將會極大提高該節(jié)點(diǎn)尋找到最佳節(jié)點(diǎn)的速度,。
　　Pastry使用定時（每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)時，Pastry替換成更近的節(jié)點(diǎn),，并把原節(jié)點(diǎn)保留在一個備份列表中,，以便當(dāng)最近節(jié)點(diǎn)失效時，可以馬上替換回來,。Pastry為每個入口最多保留10個備份節(jié)點(diǎn),，這些歷史數(shù)據(jù)對于該節(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ù)據(jù)。
　　在后面的測試數(shù)據(jù)中可以看出,，在組播組的人數(shù)達(dá)到一定規(guī)模的穩(wěn)態(tài)時，該算法能夠有效提高最佳節(jié)點(diǎn)查找的速度,。但是這個算法對于第一次加入的節(jié)點(diǎn)沒有任何作用,。
1.4.2 IP地址庫
　　在我國，由于眾所周知的原因,，中國電信和中國網(wǎng)通兩大電信運(yùn)營商之間的網(wǎng)絡(luò)互聯(lián)非常差,。而Pastry中nodeId的生成是不考慮實(shí)際網(wǎng)絡(luò)位置的。在nodeId空間中,，相鄰兩點(diǎn)在網(wǎng)絡(luò)位置上相距很遠(yuǎn)的可能性非常大,。也就是說，nodeId相鄰的兩個點(diǎn)很可能一個在網(wǎng)通,，一個在電信,。如果在這種條件下，仍然采用1.2節(jié)中的算法尋找最佳節(jié)點(diǎn),，就會耽誤很多時間,。
經(jīng)過多年的測試和搜集，已經(jīng)有人成功地搜集完中國電信,、中國網(wǎng)通以及其他中國主要ISP的IP地址網(wǎng)段,。如果在使用圖2的尋找方案中,，充分利用該IP地址庫,，則可以有效降低等待網(wǎng)絡(luò)探測的時間，加快最佳節(jié)點(diǎn)的尋找速度,。這一算法對提高新節(jié)點(diǎn)第一次加入組播組的速度會有一些幫助,。但是，這個算法只對中國或互聯(lián)網(wǎng)狀況類似中國的網(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包延時表等相關(guān)數(shù)據(jù)保存到硬盤上,。當(dāng)節(jié)點(diǎn)退出后再進(jìn)入時,，首先載入這些歷史數(shù)據(jù)和IP地址數(shù)據(jù)庫，然后按照圖3的流程進(jìn)行處理,。
　　(2)圖3顯示了根據(jù)優(yōu)化算法對Pastry節(jié)點(diǎn)加入網(wǎng)絡(luò)初始化時的流程圖,。

?

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

?

　　本文介紹了利用歷史數(shù)據(jù)和IP地址庫提高Scribe最佳節(jié)點(diǎn)查找速度的一種算法。模擬實(shí)驗(yàn)顯示,，該算法對于中國的互聯(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),。