假設(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)。