基于霍夫曼樹的內容尋址網絡失效區域恢復機制*

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

（哈爾濱工業大學大學計算機科學與技術學院 哈爾濱 150001）

基于霍夫曼樹的內容尋址網絡失效區域恢復機制*

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

（哈爾濱工業大學大學計算機科學與技術學院 哈爾濱 150001）

針對內容尋址網絡多區域失效導致的覆蓋網結構破壞與子網割裂問題，提出了基于霍夫曼樹的內容尋址網絡失效恢復機制。采用霍夫曼樹對覆蓋網邏輯空間重新進行組織與優化，在失效結點檢測機制的基礎上，提出了單個區域與多個區域失效恢復機制。實驗證明，該機制可以確保完整地恢復整個邏輯空間，解決內容尋址網絡中結點和網絡不穩定的問題，能很好地適用于動態自組織網絡的管理，并可作為目前復雜多變的網絡環境的管理模型。

對等網絡；內容尋址網絡；失效恢復；霍夫曼樹

* 國家自然科學基金資助項目（No.60703014），國家重點基礎研究發展規劃資助項目（No.G2005CB321806），高等學校博士學科點專項科研基金資助項目（No.20070213044），中國博士后科學基金經費資助項目（No.20070410263），黑龍江省博士后資助經費資助項目（No.LBH-Z07108）

1 引言

內容尋址網絡（content addressable network，CAN）是基于多維空間結構的P2P網絡[1]，利用分布式哈希表將數據和結點映射為鍵值，完成多維笛卡爾空間中數據存儲與查詢。與基于帶弦環結構Chord網絡[2]、基于異或距離度量的Kademlia[3]和機遇跳表的 SkipNet[4]等結構相比較，基于多維空間的CAN可以結合網絡測量信息和地域信息，有助于解決P2P覆蓋網絡的拓撲不匹配問題[5]。

內容尋址網絡嚴格的拓撲結構導致其成員結點不正常行為的容忍度相對較低。覆蓋網通常可以采用數據冗余[6,7]、緩存和分片的方式來進行容錯[8,9]，但當前的研究多基于chord協議實現。Sylvia Ratnasamy在其論文[10]中提及了內容尋址網絡對于結點失效的處理方法：當結點發現鄰居失效的時候，結點就啟動TakeOver機制，并同時啟動一個計時器。當某一結點啟動的計時器超時的時候，該結點將發送包含自己區域大小信息的TAKEOVER消息到網絡中，消息將到達失效結點的所有鄰居結點。失效結點的鄰居結點接收到TAKEOVER消息后，如果自己負責的區域大于發送消息的結點，那么該結點就取消掉計時器和TakeOver機制。反之，回復一個TAKEOVER消息，負責的區域最小的結點將接管失效區域。然而這種協議在惡劣的情況下并不可靠。如果多個結點同時失效，很有可能不能完全恢復失效的區域；另外，如果TAKEOVER消息不能按照設想的情況發送到失效區域的鄰居，會發生區域重復被接管的情況，而研究者們并沒有針對這種情況提出處理方法。在更為特殊的情況下，如果內容尋址網絡由于大面積失效而被撕裂，當前協議難以恢復。本文擬設計一種新的失效恢復機制對這些不足之處加以改進。

本文首先利用霍夫曼樹重新組織內容尋址網絡的邏輯空間結構，為新的失效恢復機制建立了基礎。而后，提出了失效結點的探測機制，保障失效結點實時發現。針對單點失效和多點失效情況，提出了內容尋址網絡的失效恢復機制。最后通過實驗驗證了不同失效比例下，內容尋址網絡整體結構均可成功恢復。

2 基于霍夫曼樹的內容尋址網絡組織方式

內容尋址采用多維空間拓撲結構，多維空間被動態地分配給網絡中的結點，每個結點擁有一個屬于自己的區域并負責該區域中所有的點。每個節點維護一個路由表，記錄多維空間上的鄰居信息。內容尋址網絡的構建過程是新結點加入和舊結點退出的過程。本節分別針對結點加入過程中的空間劃分和結點退出過程中的空間合并進行優化，采用基于霍夫曼編碼的組織方式重新組織內容尋址空間，為失效區域恢復機制奠定基礎。

空間劃分規則中劃分維度i是一個小于邏輯空間參數d的正整數，其作用是：對該區域進行劃分時，該區域第i維的坐標區間一分為二，分別作為劃分后生成的兩個子區域的第i維坐標區間。劃分過程按照空間區域的維度由低維到高維劃分。例如，對空間區域Z進行劃分時首先從0維度劃分，第二次劃分時從1維劃分，當達到d-1維度劃分后，再次劃分又恢復到0維度劃分，即劃分維度為（i++）%d。標識初始空間編號“#”為根。假設有空間 Z，編號為str。當空間Z在第i維度上被劃分后，生成空間z1、z2。并且，z1在第i維上的坐標值小于z2在第i維上的坐標值。那么設其編號為 z1：str+0；z2：str+1。；假設 Z的編號 str為“#101”，則 z1的編號為“#1010”，而 z2的編號為“#1011”。因此如圖1所示，在劃分邏輯空間的過程中形成一顆霍夫曼樹，而樹的葉結點代表著每一塊空間區域。

空間合并是空間劃分的逆過程，指霍夫曼樹上兩個葉結點取消，其父親結點變為葉結點的過程。合并規則1：兩個區域可以合并當且僅當這兩個區域的編號在最后一位不相同 （即為霍夫曼樹中的兩個兄弟葉結點）。合并規則2：當兩個區域合并后，新產生區域的編號為兩個區域編號的共同前綴 （即兩個兄弟葉結點的父親結點的編號）。例如：區域 6：“#0110”與區域 7：“#0111”合并后的新區域其編號為：“#011”。需要注意的是，如果區域被合并后，該區域的劃分維度也需要改變。假如z1和z2空間區域的劃分維度為i，那么合并后的區域的劃分維度設置為(i-1)%d。

根據上述的邏輯空間劃分、合并方式，按照空間區域的編碼可以準確找出兩個可以合并的空間。這樣對于結點退出后尋找接管結點提供了極為便利的機制，也是失效區域能得以快速恢復的前提條件。

基于霍夫曼的空間組織方法，定義了如下概念。

·區域編號長度G(a)：編號字符串的字符串長度。例如區域a的編號為“#1010”，則G(a)=5。

·區域編號公共前綴P(a,b)：編號a和編號b的公共前綴，就是指兩個區域編號的字符串的公共前綴。例如：區域 a編號為 “#1010”，區域 b編號為“#111”，則 P(a,b)=2。P 具有特性 P(a,b)=P(b,a)。

· 區域編號距離 L(a,b)：定義 L(a,b)=G(a)-P(a,b)。a對b的編號距離是a的編號長度減去a和b的編號公共前綴長度所得的值。例如：L(a,b)=G(a)-P(a,b)=5-2=3 ；L(b,a)=G(b)-P(b,a)=4-2=2。L(a,b)與L(b,a)不一定相等。

·區域編號路徑：一個邏輯區域的編碼路徑是指在樹形結構上，由樹根按照編碼編號走向代表該區域的葉結點的路徑。

3 內容尋址網絡失效結點探測機制

結點正常退出時通知自己的鄰居結點，意外失效不會通知鄰居結點，而是需要靠鄰居結點來發現失效情況。本節設計了結點間相互探測的方法，方便內容尋址網絡中的各個結點能夠探測到自己鄰居的存活情況和鄰居結點狀態[10]。每一個結點都主動地周期性向鄰居發送探測（poke）消息并等待鄰居回復響應。探測過程主要分為以下步驟。

第一步：A發送poke請求消息給B，消息中包含自己的結點標識、自己負責的區域信息等。

第二步：B結點接收到消息后，檢測A的空間區域與自己的空間區域關系。如果A的區域包含在自己的區域中，則合并A的索引數據，回復消息給A要求A重新加入系統。如果A的區域和自己負責的區域一樣，判斷兩個結點和該區域中點的距離。如果自己的距離近，回復消息，要求A重新加入；否則恢復普通響應消息。如果A的區域不在自己的區域內而是鄰居，則回復包含自己的結點標識、負責的區域空間等信息的消息給A。如果A不是自己的鄰居，那么回復消息后，刪除鄰居表中關于A的記錄項。

第三步：A接收到響應消息后，如果發現消息讓自己重新加入，那么通過區域編號判斷標識是否合理（B的區域編號是A的區域編號的前綴）。如果判斷結果證明重新加入合理，結點A通知自己的鄰居取消鄰居表中關于自己的記錄項，并重新執行加入過程。如果消息沒有提示重新加入或判斷結果不合理，則結點A在鄰居表中標示B存活。更新B的記錄項。

另外，如果超時還沒接收到鄰居的回復消息，則檢測到結點暫時失效。針對該結點啟動計數器并繼續周期性探測，當對該結點的探測失敗次數達到指定閾值時，則認定為鄰居失效啟動恢復機制。當結點發送消息時，如果發現鄰居表中沒有存活的鄰居（即鄰居表內容為空），則將自己負責的區域擴大一倍 （模擬合并兄弟的過程），然后向Bootstrap（或超級結點）發送 Recovery Refresh（恢復更新）消息，再由Bootstrap（或超級結點）轉發到網絡中，通知其他網絡中存活的結點關于自己區域的變化情況。結點間的探測機制處理的算法如下。

探測機制的主要目的是為了探測鄰居結點的存活，但同時也承擔了系統行為的觸發器角色。探測機制的過程中，通過探測結果來觸發不同的結點行為可以更新路由表、鄰居表，可以消除區域重復等。另外，對于負責區域出現沖突的結點，通過觸發重新加入機制讓不太合理的結點重新加入網絡，對覆蓋網的整體性能起到了調優的作用。

4 內容尋址網絡單個區域失效恢復機制

單個區域失效是指僅有某個區域失效而與其相鄰區域均未失效，其恢復機制如下。

假定結點a意外退出，結點b為a的鄰居結點。當b探測到a意外退出后，首先計算a所負責區域的編號與自己所負責區域的編號的距離L(a,b)，并根據這個編號距離啟動一個倒計時（倒計時的時間長短與L(a,b)值成正比）。如果在倒計時期間接收到了關于失效區域的Recovery Refresh消息，那么取消倒計時。當倒計時超時，啟動恢復機制。

恢復機制啟動后，結點b首先判斷失效結點a所負責的區域是否可以和自己的區域進行合并（根據區域編號判斷）。如果兩個區域可以合并，則啟動合并機制合并失效區域。然后通知自己的鄰居這個合并事件，要求更新鄰居表和路由表。但是由于不知道失效結點a的鄰居，所以設置一個有TTL限制的Recovery Refresh消息向網絡中廣播，失效區域周圍的結點在接收到Recovery Refresh消息后，會檢查恢復區域與自己負責區域的關系。如果區域相鄰，就將結點b添加到鄰居表中，并且更新路由表。圖2中的粗實線箭頭標示了哪些結點能夠探測到區域4的失效情況，如圖中所示結點2、3、6、8都可以探測到失效區域。但是由于區域2、3、6、8的編號都不相同，和區域4編號的編號距離L(a,b)也不相同，因此啟動的倒計時時間不同。其中，由于結點3和結點4的編號距離最近，因此最先由結點3發起恢復機制。

如圖2所示，結點3啟動恢復機制后，將合并失效區域4，然后發送合并通知消息到自己的鄰居結點1和結點8（虛線箭頭所示），并向網絡中廣播了一條TTL為4的Recovery Refresh消息，以此來通知相應的結點該恢復事件。圖中的細實線箭頭表示了Recovery Refresh消息廣播經過的路徑。當結點2、6、8接收到Recovery Refresh消息后，將取消自己關于恢復區域4的倒計時器，并且更新自己的鄰居表和路由表。消息到達5、9、10、11的時候，將被這些結點所忽略。

如果檢測結點負責區域和失效區域這兩個區域不可以合并，則在正常情況下，檢測結點所負責的區域比失效區域小，那么檢測結點在霍夫曼樹上體現為失效結點兄弟子樹中的某一個葉節點。這種情況下，檢測結點需要查看自己的兄弟結點是否是葉節點（即查看鄰居表中有沒有結點所負責區域可以和自己的區域合并）。如果有可以合并的鄰居結點，那么情況如圖3（a）所示：結點10失效，檢測到并首先響應的結點是8和9。當結點8和9啟動恢復機制后，發現自己不能和結點10負責的區域合并，而同時發現與自己可以進行區域合并的結點在鄰居表中，那么結點將會計算邏輯空間的歐幾里得距離。如果結點8和結點10所負責區域中的距離比結點9和結點10所負責區域中的的距離要長，那么結點9將接管失效結點10所負責的區域，并且，結點9將自己的空間區域信息等內容發送給結點8，要求結點8合并。最終將形成結點9接管失效區域，結點8負責自己和結點9以前所負責的區域。

如果自己的鄰居表中沒有可以和自己所負責區域合并的結點，那么是圖3（b）所示的情況：如果結點1失效，那么探測到失效區域并首先啟動恢復機制的是結點3（圖中粗實線箭頭表示探測和啟動恢復機制）。但是結點3的鄰居表中卻沒有結點的負責區域可以和結點3的區域合并。因此，設計這樣的處理方法：結點3直接接管失效區域，并向自己的兄弟子樹中發送leave Request消息。結點4或結點5接收到這種消息后，后續的操作就和結點退出系統時接收到退出請求后的處理方法一樣。在上述的圖例中，最終的結果是結點3接管了失效區域，結點4接管了結點3的區域，而結點5合并了原來結點4的區域。這些改變都將通過合并通知和恢復通知消息通告給邏輯空間中的結點，以便調整鄰居表和路由表。

5 內容尋址網絡多個區域失效恢復機制

本節將闡述多個結點失效的情況下，如何進行失效恢復。根據圖4的劃分情況來分析多個結點失效的復雜情況下恢復機制的運行過程，并最終證明恢復機制是可行的。

第一種情況：兄弟結點同時失效。假設兩個兄弟區域7、8均失效，那么根據恢復機制，檢測到失效并最早啟動恢復機制的結點是結點9和結點10。根據上述的恢復區域選擇來說，無論是結點9還是結點10，要恢復的區域是區域7和區域8的合并區域。因此，這個問題就歸結到某一區域失效，其處理過程歸結為§4單節點失效問題處理機制。

第二種情況：多個非兄弟結點失效。假設區域4、6都失效。那么能檢測到失效區域的結點為1、5、11。而且，它們設計的倒計時長度分別為2T、1T和3T。因此，結點5在第一個倒計時周期內就可以先恢復區域6，然后恢復區域4。并且在恢復了區域6以后，結點11接收到關于區域6的Recovery Refresh消息后會取消自己的倒計時。而結點1在接收到關于區域6的Recovery Refresh消息后，就能知道在節點 4、5、6所在子樹中有存活結點，則結點 1也可以取消掉自己的倒計時。最終，將由結點5接管4、5、6區域。

第三種情況：有多個結點同時針對一個失效區域啟動恢復機制。例如區域11失效時，能檢測到區域失效的結點是 5、6、8、10。所設置的等待時間分別為 2T、2T、1T、1T。那么有可能結點8和結點10同時啟動對區域11的恢復。而且，按照前面所述，這種情況下，結點8和結點10都將直接接管區域11并且把自己的區域交給兄弟結點7和9合并。這時候，區域11的空間被結點8和結點10所接管，結點8和結點10分別能夠接收到對方發送出來的關于區域11的Refresh Recovery消息。

一個結點接收到Recovery Refresh消息后，首先檢測自己負責區域和恢復區域的關系。①如果自己負責的區域在恢復區域的內部，那么自己重新加入系統。②如果自己負責的區域和恢復區域相同，判斷自己結點坐標與區域中點距離和恢復結點坐標和區域中點的距離。如果自己遠，則重新加入系統；如果自己距離更近，則要求對方重新加入系統。③如果自己的負責區域和恢復區域鄰接，則取消自己關于該失效區域的恢復倒計時（如果有的話），更新自己的鄰居表和路由表。④如果自己負責的區域和恢復區域不相臨，則轉發該消息。

第四種情況：一個結點的所有鄰居都失效。例如區域2、3、5、7、8、10 和區域 11 都失效，那么結點 9 將成為一個孤立的結點。雖然按照恢復機制，結點9會恢復區域10。但是恢復之后仍然是一個孤立的結點，因此鄰居表不能夠正常地建立，從而不能再通過Poke機制自動觸發區域自擴展機制來恢復其他的失效區域。針對這種情況，設計了區域自擴展機制。即當一個結點發現自己的區域成為孤立區域后，將等待一段時間后自動地將自己的區域擴展一倍。擴展之后，再通過廣播機制廣播自己的區域。如果擴展后能夠和其他的存活結點負責的區域鄰接，那么區域將不再孤立。如果擴展后還處于孤立的情況，那么將重復上述的區域自擴展過程，直到不再孤立為止。

然而，當結點處于孤立的情況下，鄰居表為空，那么它的更新消息如何發送到內容尋址網絡中的其他結點呢？為了解決這個問題，在系統中保留了一個（或多個）周知結點（或超級結點[11]）。每個結點都知道這個周知結點，并且周知結點也知道邏輯空間中存活的所有結點。那么當結點被孤立的時候，它所發送的所有更新通知消息都將通過周知結點轉發到網絡中。這樣一來，孤立區域最后將恢復所有的失效區域，并再次融入到整個邏輯空間中。

區域恢復過程的情況如圖5所示。每一幅圖是一個處理周期后的情況。由圖5可知，當第一個周期過后，結點9恢復了兄弟結點的區域10，結點6恢復了兄弟結點區域5?；謴椭?，區域9仍然是鼓勵結點，因此，它會采取區域自擴展的方式擴張自己負責的區域。而同時，結點6關于失效區域11的倒計時結束，結點1關于失效區域2、3的倒計時也結束，于是都啟動了恢復機制。最后在第三個操作周期之后，形成了上述的區域劃分關系，整個邏輯空間得到了完整的恢復。

6 實驗與結果分析

本節以PlanetSim[12]作為仿真實驗平臺，加入系統的結點數為100結點，向系統中添加的數據資源對象為2 000個資源，內容尋址網絡邏輯空間設置為2維，邏輯空間的區域范圍為0～220。

為了測試失效恢復機制，在內容尋址網絡中，隨機地選取一定量的結點，并讓其意外退出，以此來模擬網絡中結點突然失效的情況。接下來，周期性地檢測網絡的覆蓋狀況，以此來判斷內容尋址網絡中剩余的結點對網絡失效區域的恢復情況。本文把實驗過程中的每一次檢測周期稱為一個時間步（time step）。實驗中分別嘗試了失效比例為10%、20%、30%和40%的情況，檢測的數據情況如圖6所示。

圖6中，第一時間步驟為結點集體失效，導致邏輯空間覆蓋區域比例下降，所以統計曲線急速下降。在第2～5這4個時間步驟內，失效結點周圍的鄰居結點正在探測和判斷結點的失效情況是否是實情。當鄰居結點確定區域失效的時候，將啟動恢復機制。因此在該區域，覆蓋網被覆蓋的比例保持失效后的情況不變。從第6個時間步驟開始，失效恢復機制開始體現作用，并隨著時間的推移，逐漸地將失效的區域分配給內容尋址網絡中存活結點接管，最終恢復內容尋址網絡的整體結構。

通過統計圖可以看出，失效結點越多，恢復其所接管區域耗費的時間就越長。但是無論如何，本文提出的恢復機制最終都能夠恢復覆蓋網的整體結構，實驗結果證明該恢復機制是有效可行的。在傳統的失效恢復方法下，在大量結點失效的情況下會出現覆蓋網結構破壞甚至撕裂而形成數個子網[13]，而本文所設計的失效恢復機制突破了傳統方法這一缺陷，解決了參考文獻[13]所提及的覆蓋網組織缺陷問題。

7 結束語

本文設計的基于霍夫曼編碼的內容尋址空間組織方式可以便捷準確地確定結點和鄰居的關系，并根據該編碼，指導恢復機制的運行，確保能夠完整地恢復整個邏輯空間，避免出現邏輯空間缺失區域的出現。本文所設計的恢復機制可以解決大量結點失效時出現的內容尋址網絡崩潰或覆蓋網斷裂的問題，保障其應用于互聯網環境之中的穩定性。

1 RathasamyS,FrancisP,HandleyM.A scalablecontentaddressable network.In:Proceedings of the ACM SIGCOMM’01,Washington,2001

2 Stoica I,Morris R,Karger D,et al.Chord:a scalable peer-topeer lookup service for Internet applications.Technical Report,TR-819,New York:MIT,2001

3 Maymounkov P, Mazieres D. Kademlia: a peer-to-peer information system based on the XOR metric.In:Proceedings of the 1st Int'l Workshop on Peer-to-Peer Systems (IPTPS 2002),New York,2002

4 Harvey N,Dunagan J,Jones M B,et al.SkipNet:a scalable overlay network with practical locality properties.In:Proceedings of the USENIX Symp on Internet Technologies and Systems(USITS),Seattle,2003

5 Ren S S,Guo L,Jiang S,et al.SAT-Match:a self-adaptive topology matching method to achieve low lookup latency in structured P2P overlay networks.In:Proceedings of the 18th Int’l Parallel and Distributed Processing Symp (IPDPS 2004),Santa Fe,New Mexico New York,2004

6 Cohen S S.Replication strategies in unstructured peer-to-peer networks.Edith Sigcomm,2002

7 Qin Lv,Pei Cao,Edith C,et al.Search and replication in unstructured peer-to-peer networks.In:Proceedings of the 16th ACM International Conference on Supercomputing (ICS),New York USA,June 2002

8 Boris M,Peter V R.A relaxed-ring for self-organising and fault-tolerant peer-to-peer networks.IEEE ComputerSociety,2007

9 Zhuang S Q,Zhao B Y,Joseph A D,et al.Bayeux:an architecture for scalable and fault-tolerantwide-area data dissemination.In:Proceedings of the NOSSDAV 2001,2001

10 Rathasamy S.A scalable content-addressable network.A dissertation submitted in partial satisfaction of the requirements.The Degree of Doctor of Philosophy in Computer Science in the Graduate Division of the University of California at Berkeley,Fall 2002

11 Beverly Y,Hector G M.Designing a super-peer network.In:19th InternationalConference on Data Engineering,IEEE computer society,Bangalore India,2003

12 Jordi P A,Marc S A,Pedro G L.PlanetSim user and developer tutorial,http://ants.etse.urv.es/planetsim,2008

13 Stefan S,Gummadi P K,Gribble S D.Measuring and analyzing the characteristics of napster and gnutella hosts.Multimedia Systems,2003,9(2):156～170

張偉哲，副教授，博士，主要研究方向為網絡計算、并行與分布式系統；張宏莉，哈爾濱工業大學大學博士生導師，主要研究方向為網絡安全、網絡計算；吳太康，碩士，主要研究方向為對等網絡；許笑，哈爾濱工業大學大學博士生，主要研究方向為對等網絡。

2010-06-30）