一種基于ＤＨＴ混合型對等發現服務的算法設計

摘 要：提出一種新的發現服務算法ROAD，嘗試采用混合策略來適應系統的不同變化程度；通過改善超級點的使用方式，構建加速路由表，加快發現服務的速度，降低消息轉發的延時；并通過冪次序組播算法改善對超級點的依賴性。選擇不同質量類型的超級點，ROAD可以擴展成滿足不同服務需要的發現機制。

關鍵詞：發現服務； 網絡波動； 混合路由； 組播； 分布式散列表

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)03-0034-03

基于DHT(Distributed Hash Table)的分布式資源組織、管理與發現服務目前已被應用于網格[1]、Web服務[2]、對等計算等分布式環境中，成為構建大規模分布式應用的基礎結構。然而不同網絡場景下節點和網絡連接的動態性不同，要求資源組織、管理與發現服務能夠適應系統的不同變化程度，保證部分節點或網絡失效時服務的可用性[3]。例如，Internet環境下一個10萬節點的Gnutella系統每秒鐘僅有19個成員關系變化[4]；而移動Ad hoc網絡的變化則相對較快[5]，尤其是未來P2P技術的重要應用場景、軍事戰術通信系統的變化程度更難以確定。

現有發現服務都有自己特有的網絡應用場景。其性能在某一種場景下運行良好，但可能會在另一種場景中下降。影響發現服務的因素包括網絡的波動（包括節點的加入、退出、失敗、遷移、并發加入過程、網絡分割等）、網絡延遲、傳輸帶寬和對等點的計算能力等[4]。目前，還沒有一種方法能夠適應不同的網絡環境和動態變化程度。

1 相關工作

目前大部分研究均采用DHT進行資源組織、管理與發現，如CAN、Chord[6]、Pastry、Tapestry、Koorde、Viceroy采用多跳路由算法進行發現服務，即路由表僅需要維護O(logN)或O(1)個節點狀態，發現服務僅需要O(logN)跳路由。某一個節點加入或退出網絡時，最少需要O(logN)或O(log²N)條消息維護路由表的一致性。每個節點維護有限的成員關系信息，有效地解決較大網絡波動問題，但它是以增加延時為代價的。由于它不必維護去往所有節點的路由，僅在沒有去往目的節點路由時才按需進行路由發現，可將這種發現服務稱為按需發現服務。

另外一種是Kelips系統[7]。A.T.Mizrak等人[8]及A.Gupta等人[9]采用基于超級點結構的單跳路由算法的發現服務，每個超級點路由表維護全局路由狀態，路由表開銷為O(N)或O（N），但每個發現服務僅需要O(1)跳。其發現速度快、延時小，但維護代價高，受網絡波動的影響大，稱之為主動發現服務。

在變化速度慢的網絡環境下主動路由的等待延時最小，且其查找速度快。隨著網絡波動加快，為了保持查找率，主動路由必須減少路由表的維護周期。由此它不僅加劇了維護開銷，使性能下降；而且其更新速度也無法跟上網絡波動速度。按需路由只需維護正確的鄰居關系，則可以保持查找率不變或平穩下降，但這是以增大延時為代價的。研究[4] 也發現Chord算法應用在DNS服務時，最差需要20跳才能解析DNS。導致跳數增大的主要因素是路由節點的失敗概率。只要選擇可靠性高的路由節點就可以大大減少路由鏈路長度。

因此，網絡波動速度處于靜止或緩慢時，可選擇主動發現服務的路由策略來提供快速準確的查找，獲得較小的延時；當網絡波動增大，則可選擇按需發現服務且通過選擇多條路由路徑來保持查找率不變或平穩下降；當網絡波動快速且劇烈時，只有選擇洪泛算法，因為也只有洪泛算法才能適應這種變化。

2 ROAD設計

選擇主動路由和按需路由構成一個新的混合路由算法——ROAD（Routing On Active and Demand）。它主要是在不同的波動情況下保持路由的效率，同時使請求的路由路徑盡量短，以此來獲得系統對波動程度高效率的反應。

2.1ROAD結構

如圖1所示，ROAD結構主要包括兩個部分，即主動路由和按需路由。對于一個有N個節點的P2P網絡，通過DHT算法使所有節點分布在一個環上（稱之為外環）。DHT算法為每個節點分配一個ID。環采用Chord路由算法，同時選擇M個超級點構成一個內環，內環采用主動路由算法。所有點采用同一種DHT算法分配ID。

2.2 ROAD路由

2.2.1 加速路由表構造算法

在路由信息的處理方式上，繼承了Chord對路由信息的劃分，即前驅（Predecessor）、后繼列表（Successor List）和Finger表。其中，把Finger表改造成了加速路由表（Qfinger）。令節點ID號的長度為m位，每個節點的Qfinger表最多包含m條記錄。Qfinger算法如下：

除了需要構建Qfinger表以外，超級點還要維護超級點表和負責的弧內普通點的索引表。一個超級點表和索引表如圖1(b)所示。

2.2.2 混合路由策略

如何在多種路由策略之間進行自適應的、平滑的切換是混合路由的關鍵[5]。ROAD采用了一種自動的切換機制，即當超級點表出現如下兩種狀態之一時，可以自動切換到按需路由策略：①沒有去往目的節點的超級點（可能是由于節點加入信息還沒有及時擴散）；②訪問負責目的節點的超級點失敗（可能是由于網絡波動速度加快導致查找失敗）。

大部分發現服務的路由算法都通過設定等待周期來判斷超級點訪問失敗。然而由于不同的網絡應用場景，很難找到一個通用的等待周期。可以通過借鑒工作[5]中的QoS度量方法來自適應地計算等待周期。

2.2.3 ROAD路由算法

基于加速路由表和切換機制，本文給出了ROAD路由算法。以下為超級點S_i路由算法的偽代碼（其中n為超級點數量，k為Qfinger表記錄數，src為前一跳的節點ID）：

此算法與Chord算法比較可以看出，(6)～(15)增加了主動路由功能，并根據網絡狀態自適應地調整等待周期，在獲得較快路由的同時沒有增加任何多余的網絡負載。算法的復雜度與Chord相同。

2.3路由恢復

節點加入或失敗的事件會導致路由表失效，從而降低路由的效率，因此需要恢復算法來定期更新路由表。

2.3.1 普通節點恢復

ROAD恢復算法類似Chord，即通過周期性地運行n.find_successor(n+2^i-1)來訪問Finger表每一條記錄內的節點。Finger表中有log²N條記錄，每條記錄的更新跳數為O(log N)，Chord恢復算法復雜度為log²N×O(log N)=O(log²N)[6]。

為了減少恢復算法帶來的開銷，ROAD在更新Finger表時不是訪問所有Finger節點，而是通過訪問一次所在弧的超級點表，即可更新Finger表內所有超級點的記錄。如果合適地選擇超級點的數量，可以獲得比按需路由低的維護代價。

命題1 ROAD中加速路由表的維護代價低于按需路由。

2.3.2 超級點恢復算法

主動路由對超級點依賴性大的主要原因是需要維護全局一致的超級點表。當出現節點加入或失敗時，必須更新所有超級點，因此維護代價遠高于按需路由。通過改進研究[10]的Chord廣播系統，本文提出了一種冪次序組播算法。與Gnutella采用的類似洪泛算法和主動路由[7，8]以及網格[11]采用的Gossip算法相比，冪次序組播算法不會產生重復消息，所有節點獲得消息的概率高，并且每級消息擴散數量k和擴算輪次i為最低。工作[11]證明Gossip算法在k=log M+c時，消息覆蓋所有節點的概率較高；并且當i>6時，轉發消息失敗的次數會明顯增加，即在107的網絡規模下無法正常工作。本文算法k=log M，i=log M/（log log M），并且延時最低。

命題2 ROAD中冪次序組播算法消息擴散輪次和相對延時為O(log M/（log log M）)。

證明 根據算法可知k=log M，即每輪消息擴散到log M個點。令擴算輪次為i，則有

3 結束語

基于混合策略的思想，本文提出了一種動態環境中的P2P發現服務算法，可以根據波動程度在不同的路由策略之間切換以適應不同的網絡場景。下一步的工作是以ROAD為基礎，研究基于最小延時的超級點選擇算法，使最小延時的超級點盡可能多地出現在路由路徑上，從而提供最短延時的發現服務。如果ROAD采用不同服務質量的超級點選擇算法，則可以擴展為面向不同服務的發現機制。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。