內(nèi)容尋址網(wǎng)絡(luò)中路徑緩存定向多播路由算法

張偉哲，張宏莉，許 笑，吳太康

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150001，zwz@pact518.hit.edu.cn)

內(nèi)容尋址網(wǎng)絡(luò)(Content Addressable Network，CAN)是基于多維空間結(jié)構(gòu)的P2P網(wǎng)絡(luò)［1］，利用分布式哈希表將數(shù)據(jù)和結(jié)點(diǎn)映射為鍵值，完成多維笛卡爾空間中數(shù)據(jù)存儲(chǔ)與查詢.與基于帶弦環(huán)結(jié)構(gòu)Chord網(wǎng)絡(luò)、基于異或距離度量的Kademlia和機(jī)遇跳表的SkipNet等［2-4］結(jié)構(gòu)相比較，基于多維空間的CAN網(wǎng)絡(luò)可以結(jié)合網(wǎng)絡(luò)測(cè)量信息和地域信息，有助于解決P2P覆蓋網(wǎng)絡(luò)的拓?fù)洳黄ヅ鋯栴}［5］.內(nèi)容尋址網(wǎng)絡(luò)上的路由策略是當(dāng)前的研究熱點(diǎn).高效的路由機(jī)制可以快速地進(jìn)行資源定位，降低資源加入和退出的帶寬消耗.傳統(tǒng)的路由方法主要包括:1)廣播.當(dāng)結(jié)點(diǎn)接收到查詢消息的時(shí)候，將其轉(zhuǎn)發(fā)到路由表中的每一項(xiàng).這種方法缺點(diǎn)是網(wǎng)絡(luò)中轉(zhuǎn)發(fā)了大量無用消息，消耗了網(wǎng)絡(luò)帶寬，給系統(tǒng)引入了巨大的負(fù)擔(dān)［6-7］.2)定向路由.根據(jù)網(wǎng)絡(luò)延遲或鄰居位置來選擇一個(gè)轉(zhuǎn)發(fā)目的地，通過貪心的方法逐漸接近目的結(jié)點(diǎn)［8-9］.此種方法雖然效果不錯(cuò)，但當(dāng)被選中路徑上出現(xiàn)結(jié)點(diǎn)失效時(shí)，必須通過回退的方法重新探測(cè)一條新的路徑.回退再探測(cè)的過程非常消耗時(shí)間，難以做到快速路由響應(yīng)和定位.此外，Wu等［10-11］提出通過增加路由表項(xiàng)來提高路由效率:每個(gè)結(jié)點(diǎn)在路由表中除包含自己的鄰居外，還包含鄰居的鄰居，每個(gè)結(jié)點(diǎn)負(fù)責(zé)維護(hù)的路由表項(xiàng)數(shù)急劇增加;而且當(dāng)網(wǎng)絡(luò)中結(jié)點(diǎn)狀態(tài)變化頻繁時(shí)，結(jié)點(diǎn)更新各自路由表系統(tǒng)開銷增大.

本文結(jié)合定向路由與廣播路由的優(yōu)勢(shì)，闡述了內(nèi)容尋址網(wǎng)絡(luò)中定向多播路由算法的基本原理.考慮內(nèi)容尋址網(wǎng)絡(luò)的動(dòng)態(tài)性與失效問題，引入擴(kuò)展系數(shù)對(duì)定向多播路由算法進(jìn)行空間維度擴(kuò)展，降低集體失效的概率并避免路由失效發(fā)生.此外，為提高系統(tǒng)的可靠性和查詢效率，將路徑緩存技術(shù)與定向多播路由算法結(jié)合，進(jìn)一步保證系統(tǒng)容錯(cuò)性并提升尋址效率.

1 定向多播路由策略

定向多播路由策略建立在內(nèi)容尋址網(wǎng)絡(luò)之上.其路由方法以多維空間邏輯結(jié)構(gòu)為基礎(chǔ).假設(shè)多維空間的維度為d，那么邏輯空間中每個(gè)結(jié)點(diǎn)的路由表的項(xiàng)數(shù)至少有2d項(xiàng)(空間邊界結(jié)點(diǎn)除外).在d維邏輯空間中，兩個(gè)結(jié)點(diǎn)的位置關(guān)系在d維的坐標(biāo)上存在偏序關(guān)系.因此，在轉(zhuǎn)發(fā)消息的時(shí)候，如果目標(biāo)在第i維度上的坐標(biāo)值大于當(dāng)前結(jié)點(diǎn)坐標(biāo)的第i維，則向第i維正向鄰居轉(zhuǎn)發(fā)消息即可，不需要向負(fù)方向的鄰居發(fā)送消息.圖1是在二維邏輯空間下定向多播路由方法示意圖.圖1中的路由起始點(diǎn)為結(jié)點(diǎn)3，路由的目標(biāo)結(jié)點(diǎn)為結(jié)點(diǎn)14.箭頭為路由消息的流向.由圖1可見，路由消息將流經(jīng)結(jié)點(diǎn)3和結(jié)點(diǎn)14兩個(gè)結(jié)點(diǎn)之間的所有結(jié)點(diǎn).形成一個(gè)矩形路由區(qū)域.由于查詢者和查詢目標(biāo)都是隨機(jī)的分布在多維空間中，因此查詢結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的距離統(tǒng)計(jì)平均值應(yīng)該接近于邏輯空間對(duì)角線長度的1/2.而查詢結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)之間包含的區(qū)域統(tǒng)計(jì)均值將接近(其中，d為空間維度，Size為邏輯空間整體的大小).假設(shè)空間中有N個(gè)結(jié)點(diǎn)，那么查詢結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)之間包含的結(jié)點(diǎn)數(shù)統(tǒng)計(jì)平均值為所以，定向多播路由給系統(tǒng)帶來的消息負(fù)載應(yīng)該是級(jí)別.相對(duì)于廣播模式的O(N)有了明顯的性能提升.當(dāng)結(jié)點(diǎn)數(shù)量巨大(N值大)并且邏輯空間維度高(d值大)的情況下，定向多播路由方法相比廣播模式降低了系統(tǒng)開銷.

相對(duì)于定向路由的方法，定向多播路由方法對(duì)于結(jié)點(diǎn)失效具備更強(qiáng)的容錯(cuò)性，能夠容忍路由過程中結(jié)點(diǎn)失效的情況.假設(shè)圖1中結(jié)點(diǎn)12，結(jié)點(diǎn)9均失效.定向路由算出來的最佳路徑為3—8—12—13—14.當(dāng)按照定向路由的方法轉(zhuǎn)發(fā)消息時(shí)，結(jié)點(diǎn)8轉(zhuǎn)發(fā)消息到結(jié)點(diǎn)12.遇到結(jié)點(diǎn)12失效的時(shí)候，結(jié)點(diǎn)8將進(jìn)行重新探測(cè)，并將消息由結(jié)點(diǎn)8轉(zhuǎn)發(fā)到結(jié)點(diǎn)9.然而結(jié)點(diǎn)9也失效，因此將進(jìn)行路由回退重新探測(cè)的過程.路由路徑回退到結(jié)點(diǎn)3，而結(jié)點(diǎn)3重新選擇將路由消息發(fā)給結(jié)點(diǎn)5.結(jié)點(diǎn)5收到消息后，計(jì)算的下一跳路由又為失效結(jié)點(diǎn)9，因此當(dāng)結(jié)點(diǎn)5發(fā)現(xiàn)轉(zhuǎn)發(fā)向結(jié)點(diǎn)9不可行時(shí)將再次選擇將消息轉(zhuǎn)發(fā)給結(jié)點(diǎn)6.最后通過路徑3—5—6—10—14將消息送達(dá)目的.上述過程中，需要探測(cè)等待3次，路徑回退1次.這4個(gè)過程將會(huì)降低系統(tǒng)的響應(yīng)速度.而按照定向多播的方式當(dāng)結(jié)點(diǎn)3要尋找結(jié)點(diǎn)14時(shí)，由于結(jié)點(diǎn)14在x，y坐標(biāo)上的值都大于結(jié)點(diǎn)13，因此結(jié)點(diǎn)13會(huì)向x，y正方向上的鄰居(結(jié)點(diǎn)5和結(jié)點(diǎn)8)發(fā)送路由消息.后面每個(gè)結(jié)點(diǎn)都通過這種坐標(biāo)比較的方法來確定發(fā)送方向，并把消息轉(zhuǎn)發(fā)到確定方向上的所有鄰居.形成消息的流如圖1中箭頭所示的情況.當(dāng)結(jié)點(diǎn)9和結(jié)點(diǎn)12失效的時(shí)候，僅打斷了其中兩條路徑，而路由消息會(huì)通過路徑3—5—6—10—14到達(dá)目的.因此結(jié)點(diǎn)的失效并沒有影響路由查詢的效率和結(jié)果.

圖1 定向多播路由消息流向示意圖

然而，在二維的情況下如果結(jié)點(diǎn)10和結(jié)點(diǎn)13都失效，那么定向多播路由方法同樣不可行.對(duì)此，通過增加維度d來提升系統(tǒng)可靠性.在路由過程中比較坐標(biāo)大小時(shí)，如果當(dāng)前結(jié)點(diǎn)在第i維坐標(biāo)已經(jīng)大于目標(biāo)結(jié)點(diǎn)，仍然向該方向轉(zhuǎn)發(fā)路由消息，但需要將這樣的消息進(jìn)行標(biāo)識(shí).最多允許超過坐標(biāo)區(qū)域轉(zhuǎn)發(fā)k次，k值可以根據(jù)網(wǎng)絡(luò)的動(dòng)態(tài)情況來設(shè)定.所形成的路由消息覆蓋區(qū)域?qū)瓉淼亩ㄏ蚨嗖ヂ酚煞绞剿采w的區(qū)域.除非目標(biāo)結(jié)點(diǎn)所有的鄰居都已經(jīng)失效，否則路由消息一定能到達(dá)目的區(qū)域.圖2中短箭頭為原始的定向多播路由消息的流向圖，長箭頭是在k=1的情況下，擴(kuò)展定向多播路由方法下路由消息的流向圖(數(shù)據(jù)流將覆蓋圖2中所示的灰色區(qū)域).通過圖2可以看出原始方法的路徑流向區(qū)域包含在擴(kuò)展定向多播路由方法所覆蓋的區(qū)域中.因此，如果出現(xiàn)訪問結(jié)點(diǎn)14失效的情況那么只能是結(jié)點(diǎn)14的鄰居均已經(jīng)失效.這種情況下，結(jié)點(diǎn)14無法訪問到的情況是不可避免的.

圖2 擴(kuò)展定向多播路由消息流向示意圖

擴(kuò)展的定向多播路由算法:

上述擴(kuò)展定向多播路由算法中，設(shè)定擴(kuò)展系數(shù)k=0則算法描述就是定向多播路由算法.

2 定向多播和路徑冗余的結(jié)合

數(shù)據(jù)的冗余將增加數(shù)據(jù)在網(wǎng)絡(luò)中的副本.有助于提高數(shù)據(jù)的查詢效率.而在傳統(tǒng)的冗余方法中，冗余的路徑單一，冗余具有明顯的偏向性——即對(duì)熱點(diǎn)數(shù)據(jù)的冗余備份數(shù)較多，而對(duì)于較少訪問的數(shù)據(jù)備份數(shù)量較少.為了解決這個(gè)問題，將路徑冗余方法和本文的定向多播路由方法相結(jié)合起來，形成了等概率路徑緩存定向多播算法.規(guī)定為:

1)數(shù)據(jù)加入網(wǎng)絡(luò)時(shí)，加入消息的轉(zhuǎn)發(fā)路徑按照定向多播路由策略提出的定向多播方式進(jìn)行轉(zhuǎn)發(fā);

2)數(shù)據(jù)查詢消息的路由轉(zhuǎn)發(fā)過程，也按照定向多播的方式進(jìn)行轉(zhuǎn)發(fā);

3)數(shù)據(jù)在加入網(wǎng)絡(luò)的過程中，按照概率p進(jìn)行復(fù)制備份.

按照上述規(guī)則進(jìn)行數(shù)據(jù)備份，冗余數(shù)據(jù)在數(shù)據(jù)加入起始結(jié)點(diǎn)和數(shù)據(jù)加入目的結(jié)點(diǎn)這兩個(gè)結(jié)點(diǎn)坐標(biāo)所包圍的一個(gè)d維矩形區(qū)域內(nèi)都存在冗余數(shù)據(jù).如圖3所示，數(shù)據(jù)資源從結(jié)點(diǎn)5開始，加入到網(wǎng)絡(luò)中，并最終將數(shù)據(jù)索引存放到結(jié)點(diǎn)20處.按照定向多播路由方法，消息將流經(jīng)結(jié)點(diǎn)5—6—10—13—14—15—18—22所圍區(qū)域.在數(shù)據(jù)經(jīng)過上述區(qū)域中的每一個(gè)結(jié)點(diǎn)的時(shí)候，按照一定的概率p確定是否要進(jìn)行數(shù)據(jù)冗余備份.最后，在此區(qū)域中將會(huì)散布著結(jié)點(diǎn)5處加入的數(shù)據(jù)的副本(圖2中的結(jié)點(diǎn)5，結(jié)點(diǎn)19，結(jié)點(diǎn)20，結(jié)點(diǎn)21所形成的方塊).

圖3 定向多播方式下路徑冗余方法效果示意圖

當(dāng)另外的結(jié)點(diǎn)要訪問結(jié)點(diǎn)20上的數(shù)據(jù)時(shí)，按照規(guī)則2，查詢消息也按照定向路由的方式進(jìn)行發(fā)送查詢消息，那么查詢消息過程如圖4所示.

結(jié)點(diǎn)8發(fā)出查詢結(jié)點(diǎn)20上數(shù)據(jù)的查詢消息.結(jié)點(diǎn)8—10—12—13—14—15—17—18—22所圍成區(qū)域?yàn)椴樵兿凑斩ㄏ蚨嗖シ椒ㄞD(zhuǎn)發(fā)消息時(shí)覆蓋的邏輯區(qū)域.箭頭為查詢消息的流動(dòng)情況.由于結(jié)點(diǎn)20上的數(shù)據(jù)在加入過程中，按照路徑冗余方法在結(jié)點(diǎn)9和結(jié)點(diǎn)18上保存了數(shù)據(jù)副本.因此當(dāng)查詢消息由結(jié)點(diǎn)8發(fā)送出來時(shí)，僅需要通過一次消息發(fā)送就可以到達(dá)結(jié)點(diǎn)9，從而獲取到結(jié)點(diǎn)20保存的數(shù)據(jù).而正常通過結(jié)點(diǎn)8—12—13—14—15—20這條查詢路徑所需的路由跳數(shù)為5次，是具備路徑冗余機(jī)制的系統(tǒng)中數(shù)據(jù)查詢路由跳數(shù)的5倍.

圖4 數(shù)據(jù)查詢示意圖

3 實(shí)驗(yàn)與結(jié)果分析

以PlanetSim［12］作為仿真實(shí)驗(yàn)平臺(tái)，首先測(cè)試了支持路徑緩存的定向多播路由策略與Sylvia等［13］提出的定向路由方法間的性能差異，然后通過查詢過程中路由跳數(shù)統(tǒng)計(jì)體現(xiàn)路由策略定位效率的高低.

3.1 定向多播路由與傳統(tǒng)方法性能比較

仿真實(shí)驗(yàn)基于PlanetSim 3.0，加入系統(tǒng)的結(jié)點(diǎn)數(shù)為100結(jié)點(diǎn)，向系統(tǒng)中添加的數(shù)據(jù)資源對(duì)象為2 000個(gè)資源，CAN邏輯空間設(shè)置為2維，邏輯空間的區(qū)域范圍為0～220.

圖5中0%重復(fù)率為采用傳統(tǒng)的定向路由方法(無多播無冗余);20%、50%、70%和90%重復(fù)率分別為在資源加入路徑上以概率0.3、0.5、0.7和0.9進(jìn)行資源冗余(定向多播概率冗余).

圖5 定向多播路由與傳統(tǒng)方法查詢開銷關(guān)系對(duì)比圖

隨著資源冗余的程度加強(qiáng)，尋找資源所需的跳數(shù)減少，0，1，2跳就能到達(dá)的資源數(shù)量隨著冗余的概率增長迅速，而通過多跳才能到達(dá)的資源的數(shù)量相應(yīng)的減少.在資源不冗余的情況下，尋找資源所需的跳數(shù)主要集中在3～8跳區(qū)域.以0.5的概率進(jìn)行冗余時(shí)，尋找資源所需的跳數(shù)集中在0～6跳區(qū)域，而以0.9的概率進(jìn)行冗余時(shí)，尋找資源所需的跳數(shù)集中在0～4跳區(qū)域.說明了數(shù)據(jù)冗余的方法相比于傳統(tǒng)的路由定位方法對(duì)于系統(tǒng)中的資源查詢效率有很大的提高.試驗(yàn)證明系統(tǒng)中存儲(chǔ)多個(gè)數(shù)據(jù)備份，可以用來提高查詢效率，降低查詢開銷.通過與傳統(tǒng)的無冗余方法進(jìn)行比較，可以得出本文提出的定向多播和路徑冗余相結(jié)合的方法在定位效率和查詢負(fù)載上比其他的傳統(tǒng)方法有更優(yōu)秀的表現(xiàn).

3.2 資源查詢的路徑長度統(tǒng)計(jì)

系統(tǒng)查詢開銷所需要的路由跳數(shù)可以體現(xiàn)系統(tǒng)的開銷，也直接體現(xiàn)了定位效率的高低.內(nèi)容尋址網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)包含了2×d個(gè)方向的鄰居表.從一個(gè)結(jié)點(diǎn)轉(zhuǎn)發(fā)消息到目的過程中，轉(zhuǎn)發(fā)路徑的下一跳最多有d個(gè)選擇，因此，路由跳數(shù)應(yīng)該是.其中，N為結(jié)點(diǎn)數(shù)，d為維度.試驗(yàn)中采用了2維空間，加入的結(jié)點(diǎn)數(shù)為100，因此維度d= 2，結(jié)點(diǎn)數(shù)N=100，資源查詢過程中的查詢消息的轉(zhuǎn)發(fā)次數(shù)應(yīng)該在=10跳左右.試驗(yàn)中隨機(jī)選擇結(jié)點(diǎn)訪問每一個(gè)資源，最終統(tǒng)計(jì)隨機(jī)訪問所有資源的過程中查詢消息被的轉(zhuǎn)發(fā)次數(shù).通過圖6可以看出，絕大部分資源的訪問消息轉(zhuǎn)發(fā)跳數(shù)集中在2～8跳，具有較好的分布情況，符合理論預(yù)期值.

圖6 資源查詢路由跳數(shù)統(tǒng)計(jì)圖

4 結(jié)論

1)提出基于CAN模型定向多播路由方法改善了傳統(tǒng)的P2P系統(tǒng)中路由效率低下，路由開銷大的問題.

2)提出定向多播路由和路徑冗余相結(jié)合的方法，明顯提高了系統(tǒng)的查詢效率.

［1］RATHASAMY S，F(xiàn)RANCIS P，HANDLEY M.A scalable content-addressable network［C］//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication. New York，NY:ACM，2001:161-172.

［2］STOICA I，MORRIS R，KARGER D，et al.Chord:A scalable peer-to-peer lookup service for internet applications［C］//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York，NY:ACM，2001:149-160.

［3］MAYMOUNKOV P，MAZIERES D.Kademlia:A peerto-peer information system based on the XOR metric［C］//Revised Papers from the First International Workshop on Peer-to-Peer Systems.London，UK:Springer-Verlag，2002:53-65.

［4］NICHOLAS J A，HARVEY N，JONES M B，et al. SkipNet:A scalable overlay network with practical locality properties［C］//Proceedings of the 4th Conference on USENIX Symposium on Internet Technologies and Systems.Berkeley，CA:USENIX Association，2003: 29-38.

［5］REN S S，GUO L，JIANG S，et al.SAT-match:A selfadaptive topology matching method to achieve low lookup latency in structured P2P overlay networks［C］//Proceedings of the 18th International Parallel and Distributed Processing Symposium.New York:IEEE Press，2004:83-91.

［6］RATNASAMY S，STOICA I，SHENKER S.Routing algorithms for DHTs:Some open questions［C］//Revised Papers from the First International Workshop on Peer-to-Peer Systems.London，UK:Springer-Verlag，2002: 45-52.

［7］ROWSTRON A，DRUSCHEL P.Pastry:Scalable，distributed object location and routing for large scale peerto-peer systems［C］//Proceedings of the 18th IFIP/ ACM International Conference on Distributed System Platforms.New York:IEEE，2001:329-350.

［8］ZHAO B Y，KUBIATOWICZ J D，JOSE A D.Tapestry:An Infrastructure for Fault-tolerant Wide-area Location and Routing［D］.Berkeley，CA:University of California at Berkeley，2001.

［9］WU Z D，RAO W X，MA F Y.Efficient topology-aware routing in peer-to-peer network［C］//Proceedings of the GCC2002.New York:IEEE，2002:172-185.

［10］陳貴海，李振華.對(duì)等網(wǎng)絡(luò):結(jié)構(gòu)、應(yīng)用與設(shè)計(jì)［M］.北京:清華大學(xué)出版社.2007:159-165.

［11］齊慶虎，李津生，洪佩琳，等.內(nèi)容尋址網(wǎng)絡(luò)中內(nèi)容的有效定位［J］.電路與系統(tǒng)學(xué)報(bào)，2004，9(5): 67-71.

［12］Jordi Pujol Ahulló，Marc Sánchez Artigas，Pedro García López.PlanetSim User and developer tutorial［EB/ OL］.［2008-10-20］.http://ants.etse.urv.es/ planetsim.

［13］RATHASAMY S，F(xiàn)RANCIS P，HANDLEY M，et al.A scalable content-addressable network［C］//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York，NY:ACM，2001:161-172.