假設(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í)線(xiàn)箭頭表示。由于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將接收路由過(guò)程中所有節(jié)點(diǎn)的路由表，經(jīng)過(guò)整理后得到自己的路由表和葉子節(jié)點(diǎn)集合。
　　而一個(gè)新加入的點(diǎn)如何發(fā)現(xiàn)網(wǎng)絡(luò)上相近的Pastry節(jié)點(diǎn)，一種方法是使用一種叫“expanding ring”的IP組播方式，但這需要網(wǎng)絡(luò)支持組播。Pastry使用了一種有效的算法，它可以通過(guò)位于任何位置的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)后，路由表的距離屬性被用來(lái)成指數(shù)倍地減少靠近新加入的節(jié)點(diǎn)。這是通過(guò)在路由表中反復(fù)遞歸查找最近點(diǎn)實(shí)現(xiàn)的。Pastry最近節(jié)點(diǎn)查找方法的詳細(xì)說(shuō)明可參見(jiàn)參考文獻(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)的，原來(lái)網(wǎng)絡(luò)連接質(zhì)量好的節(jié)點(diǎn)，可能已經(jīng)離開(kāi)了組播組。如果它仍然在組播組中，將會(huì)極大提高該節(jié)點(diǎn)尋找到最佳節(jié)點(diǎn)的速度。
　　Pastry使用定時(shí)（每20分鐘）運(yùn)行的路由表管理任務(wù)來(lái)保證路由表中的每一入口都是nodeId滿(mǎn)足條件的節(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í)，可以馬上替換回來(lái)。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ù)定期保存到硬盤(pán)上，這樣當(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)沒(méi)有任何作用。
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)的可能性非常大。也就是說(shuō)，nodeId相鄰的兩個(gè)點(diǎn)很可能一個(gè)在網(wǎng)通，一個(gè)在電信。如果在這種條件下，仍然采用1.2節(jié)中的算法尋找最佳節(jié)點(diǎn)，就會(huì)耽誤很多時(shí)間。
經(jīng)過(guò)多年的測(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)狀況類(lèi)似中國(guó)的網(wǎng)絡(luò)才適用。
1.4.3? 算法的實(shí)現(xiàn)
　　實(shí)現(xiàn)過(guò)程：
?　　(1)在Scribe節(jié)點(diǎn)正常運(yùn)行中，定期地將節(jié)點(diǎn)的路由表、葉子節(jié)點(diǎn)集合、Ping包延時(shí)表等相關(guān)數(shù)據(jù)保存到硬盤(pán)上。當(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)原來(lái)就在本機(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í)，都使用類(lèi)似第2、3步的判斷方法：首先查看該點(diǎn)是否是本機(jī)保存的最佳節(jié)點(diǎn)，如果是，就直接跳到第12步，結(jié)束搜索過(guò)程。如果不是，則比較該點(diǎn)IP地址是否和本機(jī)屬于同一個(gè)ISP,如果不是，則跳過(guò)測(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及例子程序開(kāi)發(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)組播樹(shù)的根。其他的節(jié)點(diǎn)一旦加入Pastry就立刻加入組播組，并開(kāi)始接收數(shù)據(jù)。把N個(gè)節(jié)點(diǎn)一個(gè)一個(gè)地加入，計(jì)算每個(gè)節(jié)點(diǎn)從加入開(kāi)始到正常接收Scribe數(shù)據(jù)的時(shí)間，然后計(jì)算平均值。在不同的N值分別測(cè)試10次，以利用程序保存下來(lái)的歷史數(shù)據(jù)。把模擬試驗(yàn)所使用的N×N的延時(shí)矩陣文件，人為分為兩個(gè)部分，分別模擬兩大運(yùn)營(yíng)商。并在程序中給出類(lèi)似IP地址的區(qū)分判斷。由于試驗(yàn)設(shè)備的限制，本次試驗(yàn)的N的最大值為4 000。
　　以Pastry提供的網(wǎng)絡(luò)模擬器測(cè)試經(jīng)過(guò)優(yōu)化過(guò)的Scribe程序。作為比較，把沒(méi)有經(jīng)過(guò)優(yōu)化的Scribe程序也在相同的模擬器上運(yùn)行。由于模擬器本身對(duì)時(shí)間參數(shù)作了優(yōu)化，因此，時(shí)間的絕對(duì)值可能沒(méi)有什么參考價(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)加入需要交換的信息也越來(lái)越多所致。從兩種算法的比較可以看出，優(yōu)化的算法在節(jié)點(diǎn)數(shù)少時(shí)，沒(méi)有任何優(yōu)勢(shì)。這主要是因?yàn)楣?jié)點(diǎn)少，需要進(jìn)行測(cè)試的時(shí)間也比較少，加速優(yōu)勢(shì)體現(xiàn)不明顯。隨著節(jié)點(diǎn)的增多，可以看出，經(jīng)過(guò)優(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í)上，該算法不僅可以用來(lái)提高Scribe最佳節(jié)點(diǎn)的查找速度，也同樣適用于所有結(jié)構(gòu)化P2P網(wǎng)絡(luò)上的應(yīng)用層組播系統(tǒng)。