內容尋址網絡中路徑緩存定向多播路由算法

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

(哈爾濱工業大學計算機科學與技術學院，哈爾濱150001，zwz@pact518.hit.edu.cn)

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

本文結合定向路由與廣播路由的優勢，闡述了內容尋址網絡中定向多播路由算法的基本原理.考慮內容尋址網絡的動態性與失效問題，引入擴展系數對定向多播路由算法進行空間維度擴展，降低集體失效的概率并避免路由失效發生.此外，為提高系統的可靠性和查詢效率，將路徑緩存技術與定向多播路由算法結合，進一步保證系統容錯性并提升尋址效率.

1 定向多播路由策略

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

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

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

然而，在二維的情況下如果結點10和結點13都失效，那么定向多播路由方法同樣不可行.對此，通過增加維度d來提升系統可靠性.在路由過程中比較坐標大小時，如果當前結點在第i維坐標已經大于目標結點，仍然向該方向轉發路由消息，但需要將這樣的消息進行標識.最多允許超過坐標區域轉發k次，k值可以根據網絡的動態情況來設定.所形成的路由消息覆蓋區域將包含原來的定向多播路由方式所覆蓋的區域.除非目標結點所有的鄰居都已經失效，否則路由消息一定能到達目的區域.圖2中短箭頭為原始的定向多播路由消息的流向圖，長箭頭是在k=1的情況下，擴展定向多播路由方法下路由消息的流向圖(數據流將覆蓋圖2中所示的灰色區域).通過圖2可以看出原始方法的路徑流向區域包含在擴展定向多播路由方法所覆蓋的區域中.因此，如果出現訪問結點14失效的情況那么只能是結點14的鄰居均已經失效.這種情況下，結點14無法訪問到的情況是不可避免的.

圖2 擴展定向多播路由消息流向示意圖

擴展的定向多播路由算法:

上述擴展定向多播路由算法中，設定擴展系數k=0則算法描述就是定向多播路由算法.

2 定向多播和路徑冗余的結合

數據的冗余將增加數據在網絡中的副本.有助于提高數據的查詢效率.而在傳統的冗余方法中，冗余的路徑單一，冗余具有明顯的偏向性——即對熱點數據的冗余備份數較多，而對于較少訪問的數據備份數量較少.為了解決這個問題，將路徑冗余方法和本文的定向多播路由方法相結合起來，形成了等概率路徑緩存定向多播算法.規定為:

1)數據加入網絡時，加入消息的轉發路徑按照定向多播路由策略提出的定向多播方式進行轉發;

2)數據查詢消息的路由轉發過程，也按照定向多播的方式進行轉發;

3)數據在加入網絡的過程中，按照概率p進行復制備份.

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

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

當另外的結點要訪問結點20上的數據時，按照規則2，查詢消息也按照定向路由的方式進行發送查詢消息，那么查詢消息過程如圖4所示.

結點8發出查詢結點20上數據的查詢消息.結點8—10—12—13—14—15—17—18—22所圍成區域為查詢消息按照定向多播方法轉發消息時覆蓋的邏輯區域.箭頭為查詢消息的流動情況.由于結點20上的數據在加入過程中，按照路徑冗余方法在結點9和結點18上保存了數據副本.因此當查詢消息由結點8發送出來時，僅需要通過一次消息發送就可以到達結點9，從而獲取到結點20保存的數據.而正常通過結點8—12—13—14—15—20這條查詢路徑所需的路由跳數為5次，是具備路徑冗余機制的系統中數據查詢路由跳數的5倍.

圖4 數據查詢示意圖

3 實驗與結果分析

以PlanetSim［12］作為仿真實驗平臺，首先測試了支持路徑緩存的定向多播路由策略與Sylvia等［13］提出的定向路由方法間的性能差異，然后通過查詢過程中路由跳數統計體現路由策略定位效率的高低.

3.1 定向多播路由與傳統方法性能比較

仿真實驗基于PlanetSim 3.0，加入系統的結點數為100結點，向系統中添加的數據資源對象為2 000個資源，CAN邏輯空間設置為2維，邏輯空間的區域范圍為0～220.

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

圖5 定向多播路由與傳統方法查詢開銷關系對比圖

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

3.2 資源查詢的路徑長度統計

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

圖6 資源查詢路由跳數統計圖

4 結論

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

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

［1］RATHASAMY S，FRANCIS 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］陳貴海，李振華.對等網絡:結構、應用與設計［M］.北京:清華大學出版社.2007:159-165.

［11］齊慶虎，李津生，洪佩琳，等.內容尋址網絡中內容的有效定位［J］.電路與系統學報，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，FRANCIS 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.