結(jié)構(gòu)化P2P網(wǎng)絡(luò)中拓?fù)淦ヅ鋯栴}研究

摘要：本文以Tapestry系統(tǒng)為例討論了結(jié)構(gòu)化P2P網(wǎng)絡(luò)中覆蓋層與物理網(wǎng)絡(luò)不匹配問題，提出善于區(qū)域劃分和IP地址的標(biāo)識(shí)符分配方案，以及選取符合后綴匹配要求的最近節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)的策略來改善覆蓋層與物理網(wǎng)絡(luò)的匹配性，提高了路由效率。

關(guān)鍵詞：結(jié)構(gòu)化P2P網(wǎng)絡(luò) Tapestry系統(tǒng) 覆蓋層 物理網(wǎng)絡(luò) 匹配

中圖分類號(hào)：TP393.01 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1002-2422(2010)02-0026-02

1 結(jié)構(gòu)化P2P網(wǎng)絡(luò)的拓?fù)洳黄ヅ鋯栴}

1，1結(jié)構(gòu)化P2P網(wǎng)絡(luò)特點(diǎn)

資源定位是P2P網(wǎng)絡(luò)的首要問題，結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，資源和節(jié)點(diǎn)都通過Hash函數(shù)隨機(jī)獲得一個(gè)標(biāo)識(shí)符，資源信息映射到標(biāo)識(shí)符相匹配的節(jié)點(diǎn)上。由于結(jié)構(gòu)化P2P網(wǎng)絡(luò)可以在有限跳數(shù)內(nèi)定位到資源而成為當(dāng)前的研究熱點(diǎn)。

1，2 Tapestry系統(tǒng)

以Tapestry系統(tǒng)為例對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源定位機(jī)制進(jìn)行說明。系統(tǒng)中的節(jié)點(diǎn)和資源隨機(jī)獲取一個(gè)160位的全局唯一標(biāo)識(shí)符nodeID和obiectID。資源的定位信息存儲(chǔ)在根節(jié)點(diǎn)，即與資源標(biāo)識(shí)具有最長(zhǎng)后綴匹配的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都維護(hù)鄰居節(jié)點(diǎn)映射表、資源定位指針、熱點(diǎn)監(jiān)控器、向后指針列表和資源存儲(chǔ)這五部分信息，如圖1所示。節(jié)點(diǎn)M的鄰居節(jié)點(diǎn)映射表起到路由表的作用，在轉(zhuǎn)發(fā)資源定位消息時(shí)使用，該表有l(wèi)ogbN行，每行包含b項(xiàng)(N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，b為節(jié)點(diǎn)標(biāo)識(shí)符的基數(shù))，第j行第i項(xiàng)是以“i”+suffix(M，i-1)結(jié)尾的節(jié)點(diǎn)。資源定位指針列表存儲(chǔ)與節(jié)點(diǎn)M具有最長(zhǎng)后綴匹配的資源信息。資源存儲(chǔ)是M向網(wǎng)絡(luò)中其他節(jié)點(diǎn)提供的可共享資源。

Tapestry系統(tǒng)采用基于后綴匹配的資源定位機(jī)制。路由過程中到達(dá)的第n個(gè)節(jié)點(diǎn)和目的節(jié)點(diǎn)的標(biāo)識(shí)符后綴匹配長(zhǎng)度至少為n，這樣，每經(jīng)過一個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)，距離目的節(jié)點(diǎn)就更近一步。例如消息從***8到**98到*598到目的節(jié)點(diǎn)4598(*表示通配符)。Tapestry系統(tǒng)最多經(jīng)過logbN個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)即可實(shí)現(xiàn)資源定位。

1，3覆蓋層與物理網(wǎng)絡(luò)拓?fù)涞牟黄ヅ?/p>

結(jié)構(gòu)化P2P系統(tǒng)利用分布式哈希表構(gòu)建覆蓋層網(wǎng)絡(luò)，沒有過多考慮底層物理拓?fù)浣Y(jié)構(gòu)。資源定位是在覆蓋層進(jìn)行的，覆蓋層上的相鄰節(jié)點(diǎn)在網(wǎng)絡(luò)層可能相距很遠(yuǎn)，這樣在資源定位過程中會(huì)出現(xiàn)許多不必要的路由，甚至超時(shí)導(dǎo)致搜索失敗，大大降低資源定位的效率。例如資源定位信息從節(jié)點(diǎn)1傳送到節(jié)點(diǎn)4的過程，在物理網(wǎng)絡(luò)中從北京傳送到倫敦又到紐約，最后再回到上海(如圖2中實(shí)線所示)。顯然，理想的路由過程是直接從北京傳送到上海(如圖2中虛線所示)。

2 拓?fù)淦ヅ鋯栴}的改進(jìn)

為了改進(jìn)結(jié)構(gòu)化P2P網(wǎng)絡(luò)中覆蓋層與網(wǎng)絡(luò)層拓?fù)洳黄ヅ鋯栴}，提高資源定位效率，在分配節(jié)點(diǎn)標(biāo)識(shí)符和構(gòu)建路由表時(shí)應(yīng)考慮物理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

2，1基于區(qū)域劃分和IP地址的節(jié)點(diǎn)標(biāo)識(shí)符

目前結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點(diǎn)標(biāo)識(shí)都是隨機(jī)獲取的，這樣標(biāo)識(shí)接近的節(jié)點(diǎn)物理位置可能相距很遠(yuǎn)。為了改善這一情況，應(yīng)盡可能根據(jù)節(jié)點(diǎn)的實(shí)際位置分配標(biāo)識(shí)符。

將結(jié)構(gòu)化P2P網(wǎng)絡(luò)劃分若干個(gè)區(qū)域，依據(jù)物理位置鄰近的區(qū)域其編號(hào)也接近原則為每個(gè)區(qū)域進(jìn)行編號(hào)，各區(qū)域均有一個(gè)L1位的編號(hào)Ni。每個(gè)區(qū)域中選擇經(jīng)常在線、性能較為強(qiáng)大的節(jié)點(diǎn)作為區(qū)域界點(diǎn)，其中一個(gè)為主界點(diǎn)，其他為候選界點(diǎn)，當(dāng)主界點(diǎn)離開系統(tǒng)時(shí)新加入網(wǎng)絡(luò)的節(jié)點(diǎn)測(cè)試到達(dá)各個(gè)區(qū)域主界點(diǎn)的往返時(shí)延(測(cè)試k次取平均值)，該節(jié)點(diǎn)屬于具有最小時(shí)延的界點(diǎn)A所屬區(qū)域Ni。

由于主機(jī)的IP地址是由網(wǎng)絡(luò)號(hào)和主機(jī)號(hào)兩部分構(gòu)成，同一個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的IP地址具有相同的網(wǎng)絡(luò)號(hào)，因此物理位置鄰近的節(jié)點(diǎn)IP地址具有相同的前綴。

Tapestry系統(tǒng)是基于后綴匹配的，相鄰的節(jié)點(diǎn)標(biāo)識(shí)符具有共同的后綴。在為節(jié)點(diǎn)分配標(biāo)識(shí)符時(shí)，最后的t1位是其所在區(qū)域編號(hào)的逆序排列，左邊32位是節(jié)點(diǎn)IP地址的逆序，剩下的160-(32+t1)位則隨機(jī)分配。這樣，屬于同一個(gè)區(qū)域、在同一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)具有相同的后綴，而標(biāo)識(shí)符又包含隨機(jī)獲取的部分。節(jié)點(diǎn)的標(biāo)識(shí)既在標(biāo)識(shí)符空間平均分布而不會(huì)破壞其負(fù)載平衡的特性，又充分考慮了節(jié)點(diǎn)的實(shí)際位置，保證物理鄰近節(jié)點(diǎn)的覆蓋層標(biāo)識(shí)也鄰近。

2，2基于物理臨近的路由表構(gòu)建

Tapestry系統(tǒng)需要借助鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)來實(shí)現(xiàn)資源定位，隨機(jī)選取滿足后綴匹配要求的節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)的策略并未考慮鄰居節(jié)點(diǎn)的物理鄰近性。使得資源定位時(shí)容易出現(xiàn)在物理網(wǎng)絡(luò)進(jìn)行不必要路由的情況。在為新加入系統(tǒng)的節(jié)點(diǎn)構(gòu)建鄰居節(jié)點(diǎn)映射表時(shí)進(jìn)行優(yōu)化處理，測(cè)量其到各個(gè)滿足后綴匹配要求節(jié)點(diǎn)的往返時(shí)延(測(cè)試k次取平均值)，時(shí)延最小的那個(gè)節(jié)點(diǎn)和該節(jié)點(diǎn)物理位置最為接近，將它選作該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。這樣，在資源定位時(shí)，總是把消息轉(zhuǎn)發(fā)到物理位置盡可能鄰近的節(jié)點(diǎn)，提高路由效率。

3 結(jié)束語(yǔ)

在分析結(jié)構(gòu)化P2P網(wǎng)絡(luò)特點(diǎn)的基礎(chǔ)上，以Tapestry系統(tǒng)為例討論了覆蓋層與物理網(wǎng)絡(luò)拓?fù)洳黄ヅ涞膯栴}。提出采用區(qū)域劃分和節(jié)點(diǎn)IP地址的標(biāo)識(shí)符分配方法，以及構(gòu)建路由表時(shí)選取符合后綴匹配要求且在物理上最為鄰近的節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)的策略，構(gòu)造覆蓋層網(wǎng)絡(luò)時(shí)充分考慮其物理位置信息，使結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源定位效率得到提高。