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

（哈爾濱工業(yè)大學(xué)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150001）

基于霍夫曼樹的內(nèi)容尋址網(wǎng)絡(luò)失效區(qū)域恢復(fù)機制*

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

（哈爾濱工業(yè)大學(xué)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150001）

針對內(nèi)容尋址網(wǎng)絡(luò)多區(qū)域失效導(dǎo)致的覆蓋網(wǎng)結(jié)構(gòu)破壞與子網(wǎng)割裂問題，提出了基于霍夫曼樹的內(nèi)容尋址網(wǎng)絡(luò)失效恢復(fù)機制。采用霍夫曼樹對覆蓋網(wǎng)邏輯空間重新進行組織與優(yōu)化，在失效結(jié)點檢測機制的基礎(chǔ)上，提出了單個區(qū)域與多個區(qū)域失效恢復(fù)機制。實驗證明，該機制可以確保完整地恢復(fù)整個邏輯空間，解決內(nèi)容尋址網(wǎng)絡(luò)中結(jié)點和網(wǎng)絡(luò)不穩(wěn)定的問題，能很好地適用于動態(tài)自組織網(wǎng)絡(luò)的管理，并可作為目前復(fù)雜多變的網(wǎng)絡(luò)環(huán)境的管理模型。

對等網(wǎng)絡(luò)；內(nèi)容尋址網(wǎng)絡(luò)；失效恢復(fù)；霍夫曼樹

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

1 引言

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

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

本文首先利用霍夫曼樹重新組織內(nèi)容尋址網(wǎng)絡(luò)的邏輯空間結(jié)構(gòu)，為新的失效恢復(fù)機制建立了基礎(chǔ)。而后，提出了失效結(jié)點的探測機制，保障失效結(jié)點實時發(fā)現(xiàn)。針對單點失效和多點失效情況，提出了內(nèi)容尋址網(wǎng)絡(luò)的失效恢復(fù)機制。最后通過實驗驗證了不同失效比例下，內(nèi)容尋址網(wǎng)絡(luò)整體結(jié)構(gòu)均可成功恢復(fù)。

2 基于霍夫曼樹的內(nèi)容尋址網(wǎng)絡(luò)組織方式

內(nèi)容尋址采用多維空間拓撲結(jié)構(gòu)，多維空間被動態(tài)地分配給網(wǎng)絡(luò)中的結(jié)點，每個結(jié)點擁有一個屬于自己的區(qū)域并負責(zé)該區(qū)域中所有的點。每個節(jié)點維護一個路由表，記錄多維空間上的鄰居信息。內(nèi)容尋址網(wǎng)絡(luò)的構(gòu)建過程是新結(jié)點加入和舊結(jié)點退出的過程。本節(jié)分別針對結(jié)點加入過程中的空間劃分和結(jié)點退出過程中的空間合并進行優(yōu)化，采用基于霍夫曼編碼的組織方式重新組織內(nèi)容尋址空間，為失效區(qū)域恢復(fù)機制奠定基礎(chǔ)。

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

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

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

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

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

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

· 區(qū)域編號距離 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)不一定相等。

·區(qū)域編號路徑：一個邏輯區(qū)域的編碼路徑是指在樹形結(jié)構(gòu)上，由樹根按照編碼編號走向代表該區(qū)域的葉結(jié)點的路徑。

3 內(nèi)容尋址網(wǎng)絡(luò)失效結(jié)點探測機制

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

第一步：A發(fā)送poke請求消息給B，消息中包含自己的結(jié)點標(biāo)識、自己負責(zé)的區(qū)域信息等。

第二步：B結(jié)點接收到消息后，檢測A的空間區(qū)域與自己的空間區(qū)域關(guān)系。如果A的區(qū)域包含在自己的區(qū)域中，則合并A的索引數(shù)據(jù)，回復(fù)消息給A要求A重新加入系統(tǒng)。如果A的區(qū)域和自己負責(zé)的區(qū)域一樣，判斷兩個結(jié)點和該區(qū)域中點的距離。如果自己的距離近，回復(fù)消息，要求A重新加入；否則恢復(fù)普通響應(yīng)消息。如果A的區(qū)域不在自己的區(qū)域內(nèi)而是鄰居，則回復(fù)包含自己的結(jié)點標(biāo)識、負責(zé)的區(qū)域空間等信息的消息給A。如果A不是自己的鄰居，那么回復(fù)消息后，刪除鄰居表中關(guān)于A的記錄項。

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

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

探測機制的主要目的是為了探測鄰居結(jié)點的存活，但同時也承擔(dān)了系統(tǒng)行為的觸發(fā)器角色。探測機制的過程中，通過探測結(jié)果來觸發(fā)不同的結(jié)點行為可以更新路由表、鄰居表，可以消除區(qū)域重復(fù)等。另外，對于負責(zé)區(qū)域出現(xiàn)沖突的結(jié)點，通過觸發(fā)重新加入機制讓不太合理的結(jié)點重新加入網(wǎng)絡(luò)，對覆蓋網(wǎng)的整體性能起到了調(diào)優(yōu)的作用。

4 內(nèi)容尋址網(wǎng)絡(luò)單個區(qū)域失效恢復(fù)機制

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

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

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

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

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

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

5 內(nèi)容尋址網(wǎng)絡(luò)多個區(qū)域失效恢復(fù)機制

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

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

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

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

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

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

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

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

6 實驗與結(jié)果分析

本節(jié)以PlanetSim[12]作為仿真實驗平臺，加入系統(tǒng)的結(jié)點數(shù)為100結(jié)點，向系統(tǒng)中添加的數(shù)據(jù)資源對象為2 000個資源，內(nèi)容尋址網(wǎng)絡(luò)邏輯空間設(shè)置為2維，邏輯空間的區(qū)域范圍為0～220。

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

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

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

7 結(jié)束語

本文設(shè)計的基于霍夫曼編碼的內(nèi)容尋址空間組織方式可以便捷準(zhǔn)確地確定結(jié)點和鄰居的關(guān)系，并根據(jù)該編碼，指導(dǎo)恢復(fù)機制的運行，確保能夠完整地恢復(fù)整個邏輯空間，避免出現(xiàn)邏輯空間缺失區(qū)域的出現(xiàn)。本文所設(shè)計的恢復(fù)機制可以解決大量結(jié)點失效時出現(xiàn)的內(nèi)容尋址網(wǎng)絡(luò)崩潰或覆蓋網(wǎng)斷裂的問題，保障其應(yīng)用于互聯(lián)網(wǎng)環(huán)境之中的穩(wěn)定性。

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

張偉哲，副教授，博士，主要研究方向為網(wǎng)絡(luò)計算、并行與分布式系統(tǒng)；張宏莉，哈爾濱工業(yè)大學(xué)大學(xué)博士生導(dǎo)師，主要研究方向為網(wǎng)絡(luò)安全、網(wǎng)絡(luò)計算；吳太康，碩士，主要研究方向為對等網(wǎng)絡(luò)；許笑，哈爾濱工業(yè)大學(xué)大學(xué)博士生，主要研究方向為對等網(wǎng)絡(luò)。

2010-06-30）