資源描述:
《一種chord路由表的改進(jìn)方法》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、工程科技《白訂陡院霉粕>2olo年第3期一種Chord路由表硇改進(jìn)方法王必晴(銅陵學(xué)院,安徽銅陵244000)摘要:資源的高效查找是P2P網(wǎng)絡(luò)研究中一個(gè)核心問(wèn)題。針對(duì)P2P資源查找協(xié)議Chord的路由表信息冗余、查找效率不高的問(wèn)題.提出了一種Chord路由表的改進(jìn)方法。在不增加路由表長(zhǎng)度的前提下,將路由表中的重復(fù)表項(xiàng)刪除,進(jìn)而增加經(jīng)過(guò)科學(xué)定義且具較大覆蓋面的有效路由信息。實(shí)驗(yàn)結(jié)果表明,該方法減少了平均查找跳數(shù),提高了查找效率,使提高查找效率和控制路由表長(zhǎng)度得到較好的統(tǒng)一。關(guān)鍵詞:對(duì)等網(wǎng)絡(luò):Chord;路由表
2、;查找;分布式哈希表中圖分類號(hào):TP393.02文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1672—0547(2010)03—0069—02目前,許多基于分布式哈希表(DHT)的P2P網(wǎng)絡(luò),如其后繼節(jié)點(diǎn)間的間距就大于1,則該節(jié)點(diǎn)的路由表必然會(huì)出現(xiàn)Chordeal,Tapestry日,CAN~3),和Pastryf41等,由于有著良好的健壯冗余信息。性和可擴(kuò)展性,正日益成為P2P網(wǎng)絡(luò)研究和應(yīng)用的熱點(diǎn)。Chor由MIT提出。對(duì)于一個(gè)有N:2n個(gè)節(jié)點(diǎn)的Chord網(wǎng)曰絡(luò),每個(gè)節(jié)點(diǎn)要維護(hù)一張有in個(gè)表項(xiàng)的路由表fingertable)
3、,平均查找跳數(shù)Y~(1ogN。但是該系統(tǒng)路由表中有近1左右的重復(fù)表項(xiàng)l圖1),查找效率不高,因此有一些文獻(xiàn)tsqq~rj-Chord做了進(jìn)一步的研究。文獻(xiàn)f51提出了雙向路由Chord的思想,使平均查找跳數(shù)減小到(1ogNy3,然而其路由表長(zhǎng)度是原始Chord的兩倍。文獻(xiàn)f6提出了One—Hop的算法,使所有的查找有可能只需要一跳完成,但是每個(gè)節(jié)點(diǎn)的路由表需要維護(hù)全體節(jié)點(diǎn)的信息。圖1節(jié)點(diǎn)8的路由表本文在Chord的基礎(chǔ)上,提出了一種Chord路由表的改進(jìn)2.Chord路由表改進(jìn)方法方法。在不增加路由表長(zhǎng)度的
4、前提下,將路由表中的重復(fù)表項(xiàng)如果我們把重復(fù)的路由信息刪除,在路由表的多出空間中刪除,進(jìn)而增加有效的路由信息。該方法較科學(xué)地定義了需要添加其他節(jié)點(diǎn)的信息,則必然可以提高查找效率。補(bǔ)充的路由,而且補(bǔ)充的路由具有較大的覆蓋面。這樣,可以消從圖1可看出標(biāo)準(zhǔn)Chord的路由表只能覆蓋『n0,NO+2這除路由表信息冗余,減少平均查找跳數(shù),提高查找效率,使提高半個(gè)環(huán)的區(qū)域,而沒(méi)有保存(nn+2一這另一半空間上任何查找效率和控制路由表長(zhǎng)度得到較好的統(tǒng)一。節(jié)點(diǎn)的信息。因此,如果我們?cè)谝驗(yàn)閯h除重復(fù)路由信息而騰出1.Chord路
5、由表研究的路由表空間中增添(n一,n區(qū)域中的節(jié)點(diǎn),就增加了以每個(gè)Chord節(jié)點(diǎn)都需要維護(hù)一張路由表。節(jié)點(diǎn)n。的路由前Chord中所沒(méi)有的信息,加快了查找的速度,提高了查找的表中的第i(1≤i≤m)項(xiàng)是Chord環(huán)上標(biāo)識(shí)符等于或大于(n_卜1)效率。mod2m的第~個(gè)節(jié)點(diǎn),即(nrood2m的后繼節(jié)點(diǎn),用successor假設(shè)Chord環(huán)的大小為2m,節(jié)點(diǎn)數(shù)為2n,且所有節(jié)點(diǎn)平均((rn10d2n1表示。路由表中的每一項(xiàng)既包含相關(guān)節(jié)點(diǎn),又包分布。則兩個(gè)節(jié)點(diǎn)間的平均間隔是2-/2~,每個(gè)節(jié)點(diǎn)路由表中的含該節(jié)點(diǎn)的
6、IP地址。如果關(guān)鍵字和節(jié)點(diǎn)用m位二進(jìn)制數(shù)表示,需要?jiǎng)h除的冗余信息數(shù)量為log2(2"/2")--m-n條。相應(yīng)地,需要補(bǔ)那么路由表中就有ii1個(gè)表項(xiàng)。顯然,這樣的路由表只能覆蓋,充的路由也是瑚_n條。no+2-~a]這半個(gè)環(huán)的區(qū)域。節(jié)點(diǎn)no的路由表中的補(bǔ)充路由條目按以下方法建立:任何一個(gè)節(jié)點(diǎn)收到查找關(guān)鍵宇k的請(qǐng)求時(shí),首先檢查自身(1)建立節(jié)點(diǎn)nn十2的路由表,將最后一項(xiàng)用no的前驅(qū)節(jié)節(jié)點(diǎn)是否等于k,如果是的話,就直接回應(yīng)查找節(jié)點(diǎn)。否則,檢查點(diǎn)替代。k是否落在該節(jié)點(diǎn)和它的后繼節(jié)點(diǎn)之間,如果是的話,這個(gè)后(21
7、當(dāng)1≤m時(shí),從節(jié)點(diǎn)n卜2一的路由表中由上到下依次繼節(jié)點(diǎn)就是存儲(chǔ)k的節(jié)點(diǎn)。否則,節(jié)點(diǎn)將查找它的路由表,找到選取不重復(fù)的且與節(jié)點(diǎn)no的路由表項(xiàng)不相同的n個(gè)表項(xiàng)當(dāng)表中最大但不超過(guò)k的第一個(gè)節(jié)點(diǎn),并將這個(gè)查找請(qǐng)求轉(zhuǎn)發(fā)給n>m/2時(shí),從節(jié)點(diǎn)n2的路由表中由上到下依次選取不重復(fù)該節(jié)點(diǎn)。通過(guò)重復(fù)這個(gè)過(guò)程,最終可以定位到k的后繼節(jié)點(diǎn),即的且與節(jié)點(diǎn)n的路由表項(xiàng)不相同的mr-n個(gè)表項(xiàng)。存儲(chǔ)有k的節(jié)點(diǎn)。圖1是一個(gè)m=6的Chord環(huán),節(jié)點(diǎn)8查找關(guān)(3每上一步所選取的表項(xiàng)添加到節(jié)點(diǎn)NO的路由表的尾部。鍵宇56,經(jīng)過(guò)3次轉(zhuǎn)發(fā),最終找
8、到56的后繼節(jié)點(diǎn)56。f41刪除節(jié)點(diǎn)n盯}2一的路由表。顯然,節(jié)點(diǎn)8的路由表中第2條和第3條路由信息都是需要說(shuō)明的是,為了定義需要補(bǔ)充的路由,即使標(biāo)識(shí)符n冗余的,冗余度達(dá)到了33%,勢(shì)必對(duì)查找效率造成影響。造成2處沒(méi)有節(jié)點(diǎn),也不妨假設(shè)其存在。同時(shí),由于節(jié)點(diǎn)n2一的冗余的原因是相對(duì)于2m的標(biāo)識(shí)符空間來(lái)說(shuō),節(jié)點(diǎn)的數(shù)目太過(guò)路由表的最后一項(xiàng)就是n。本身,所以用的前驅(qū)節(jié)點(diǎn)替代,可稀少。實(shí)際上,如果假設(shè)節(jié)點(diǎn)平均分布,只要n<