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

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

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

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

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

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

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

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

* 國(guó)家自然科學(xué)基金資助項(xiàng)目（No.60703014），國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃資助項(xiàng)目（No.G2005CB321806），高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金資助項(xiàng)目（No.20070213044），中國(guó)博士后科學(xué)基金經(jīng)費(fèi)資助項(xiàng)目（No.20070410263），黑龍江省博士后資助經(jīng)費(fèi)資助項(xià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é)點(diǎn)映射為鍵值，完成多維笛卡爾空間中數(shù)據(jù)存儲(chǔ)與查詢。與基于帶弦環(huán)結(jié)構(gòu)Chord網(wǎng)絡(luò)[2]、基于異或距離度量的Kademlia[3]和機(jī)遇跳表的 SkipNet[4]等結(jié)構(gòu)相比較，基于多維空間的CAN可以結(jié)合網(wǎng)絡(luò)測(cè)量信息和地域信息，有助于解決P2P覆蓋網(wǎng)絡(luò)的拓?fù)洳黄ヅ鋯?wèn)題[5]。

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

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

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

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

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

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

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

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

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

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

· 區(qū)域編號(hào)距離 L(a,b)：定義 L(a,b)=G(a)-P(a,b)。a對(duì)b的編號(hào)距離是a的編號(hào)長(zhǎng)度減去a和b的編號(hào)公共前綴長(zhǎng)度所得的值。例如：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ū)域編號(hào)路徑：一個(gè)邏輯區(qū)域的編碼路徑是指在樹(shù)形結(jié)構(gòu)上，由樹(shù)根按照編碼編號(hào)走向代表該區(qū)域的葉結(jié)點(diǎn)的路徑。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本節(jié)將闡述多個(gè)結(jié)點(diǎn)失效的情況下，如何進(jìn)行失效恢復(fù)。根據(jù)圖4的劃分情況來(lái)分析多個(gè)結(jié)點(diǎn)失效的復(fù)雜情況下恢復(fù)機(jī)制的運(yùn)行過(guò)程，并最終證明恢復(fù)機(jī)制是可行的。

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語(yǔ)

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

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

2010-06-30）