常數(shù)度的結(jié)構(gòu)化P2P 系統(tǒng)Cycloid 研究

徐麗新

（廣東工程職業(yè)技術(shù)學(xué)院信息工程學(xué)院，廣州510520）

0 引言

早期的基于DHT（分布式哈希表）的結(jié)構(gòu)化P2P系統(tǒng)模型典型的有Chord[1]、Pastry[2]、Tapestry[3]，其路由表大小和網(wǎng)絡(luò)直徑均為O（logN），而系統(tǒng)模型CAN[4]是O（d）和O（d*N1/d）。這些模型在大量節(jié)點(diǎn)的加入和離開網(wǎng)絡(luò)攪動劇烈時會產(chǎn)生巨大的開銷[5]，為了減少開銷，一些具有常數(shù)度（即節(jié)點(diǎn)只維護(hù)常數(shù)個鄰居）的P2P 系統(tǒng)被提出來如Cycloid[8-9]、Koorde[7]和Viceroy[6]等。這些系統(tǒng)具有O（logN）的網(wǎng)絡(luò)直徑，固定地維護(hù)較少的常數(shù)個鄰居，如Cycloid 和Viceroy 鄰居數(shù)均為7、Koorde 鄰居數(shù)最小為2。本文詳細(xì)介紹了Cycloid系統(tǒng)。

1 Cycloid的拓?fù)浣Y(jié)構(gòu)

Cycloid 的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是基于立方體連接環(huán)（CCC:Cube-Connected Cycle）圖。在Cycloid 系統(tǒng)中，最多可容納n=d*2d個節(jié)點(diǎn)，每個節(jié)點(diǎn)維護(hù)O（1）個鄰居節(jié)點(diǎn)，每個查詢要經(jīng)過O（d）跳路由轉(zhuǎn)發(fā)。Cycloid 系統(tǒng)不必是完全的，它可以有少于d*2d個節(jié)點(diǎn)。

一個d 維的立方體的每個頂點(diǎn)用d 個節(jié)點(diǎn)組成的環(huán)來代替就得到一個d 維的CCC 圖。它包含d*2d個度為3 的節(jié)點(diǎn)。每個節(jié)點(diǎn)用一對索引值（k，ad-1ad-2...a0）表示，其中k 是環(huán)索引，ad-1ad-2...a0是立方體索引。環(huán)索引是一個介于0 和d-1 之間的整數(shù)，立方體索引是一個介于0 和2d-1 之間的二進(jìn)制整數(shù)。如圖1。

圖1 三維CCC圖

2 相關(guān)術(shù)語

局部環(huán)（local cycle）：具有相同立方體索引值的節(jié)點(diǎn)根據(jù)k 值排序組成的循環(huán)。

遠(yuǎn)環(huán)（remote cycle）：遠(yuǎn)環(huán)是指不同立方體索引值的局部環(huán)。

主節(jié)點(diǎn)（primary node）：在局部環(huán)中環(huán)索引值最大的節(jié)點(diǎn)為這個環(huán)的主節(jié)點(diǎn)。

大環(huán)（large cycle）：根據(jù)立方體索引值排序的局部環(huán)組成的循環(huán)。

前導(dǎo)節(jié)點(diǎn)（predecessor）：在一個局部環(huán)中，逆時針方向遇到的第一個節(jié)點(diǎn)[10]。

后繼節(jié)點(diǎn)（successor）：在一個局部環(huán)中，順時針方向遇到的第一個節(jié)點(diǎn)[11]。

前導(dǎo)遠(yuǎn)環(huán)（preceding remote cycle）：在大環(huán)中，逆時針方向遇到的第一個局部環(huán)。

后繼遠(yuǎn)環(huán)（succeeding remote cycle）：在大環(huán)中，順時針方向遇到的第一個局部環(huán)。

3 關(guān)鍵字的分配

Cycloid 的DHT 使用一致性哈西函數(shù)在ID 空間上分配關(guān)鍵字，節(jié)點(diǎn)的ID 和關(guān)鍵字被一致的分布在一個d*2d的ID 空間中。關(guān)鍵字的分配和Pastry 很相似，只是Cycloid 的每個節(jié)點(diǎn)與一對環(huán)索引和立方體索引相關(guān)聯(lián)。對某個關(guān)鍵字，它要映射的節(jié)點(diǎn)的環(huán)索引被設(shè)置為它的哈西值模d，立方體索引被設(shè)置為它的哈西值除以d。如果Cycloid 的節(jié)點(diǎn)組成一個完整的CCC 圖，一致性哈西函數(shù)將把關(guān)鍵字k 映射到節(jié)點(diǎn)k。如果一個關(guān)鍵字的ID（k，ad-1ad-2...a0）不是一個活動節(jié)點(diǎn)，這個關(guān)鍵字會被分配到先是數(shù)字上最接近ad-1ad-2...a0，然后數(shù)字上最接近k 的節(jié)點(diǎn)上。例如，在（2，1101）和（2，1001）中，（1，1101）更接近（2，1101）。當(dāng)兩個節(jié)點(diǎn)到關(guān)鍵字ID 的距離相同時，關(guān)鍵字的后繼節(jié)點(diǎn)將負(fù)責(zé)存儲這個關(guān)鍵字[12]。

4 路由表結(jié)構(gòu)

在Cycloid 系統(tǒng)中，每個節(jié)點(diǎn)為了與系統(tǒng)的其余部分連接要維護(hù)一個有7 個入口的路由表。圖2 是一個8 維Cycloid 系統(tǒng)中節(jié)點(diǎn)（4，101-1-1010）的路由表。

一般情況下，節(jié)點(diǎn)（k,ad-1ad-2…a0）(k ≠0)有7 個鄰居節(jié)點(diǎn)。其中一個立方體鄰居（k-1,ad-1ad-2…akxx…x）(x任取0和1)，兩個循環(huán)鄰居（k-1,bd-1bd-2…bo）和（k-1,cd-1cd-2…c0）是環(huán)索引為k-1 mod d、立方體索引為第一個大于和小于ad-1ad-2...a0且最大不相同位的下標(biāo)值小于k 的節(jié)點(diǎn)。即：

(k-1,bd-1bd-2…b1b0)=min{?(k-1,yd-1yd-2…y1y0)|yd-1…y0≥ad-1…a1a0}

(k-1,cd-1cd-2…c1c0)=min{?(k-1,yd-1yd-2…y1y0）|yd-1…y0≤ad-1…a1a0}

環(huán)索引k=0 的節(jié)點(diǎn)沒有立方體鄰居和環(huán)鄰居。立方體索引為0 的節(jié)點(diǎn)沒有小的環(huán)鄰居，立方體索引為2d-1 的節(jié)點(diǎn)沒有大的環(huán)鄰居。在局部環(huán)中，左內(nèi)葉子集結(jié)點(diǎn)（left inside leaf set node）指向當(dāng)前節(jié)點(diǎn)的前導(dǎo)節(jié)點(diǎn)[13]，右內(nèi)葉子集節(jié)點(diǎn)（right inside leaf set node）指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)[14]。在大環(huán)中，左外葉子集結(jié)點(diǎn)（left outside leaf set node）指向當(dāng)前節(jié)點(diǎn)的前導(dǎo)遠(yuǎn)環(huán)的主節(jié)點(diǎn)，右外葉子集結(jié)點(diǎn)（right outside leaf set node）指向當(dāng)前節(jié)點(diǎn)后繼遠(yuǎn)環(huán)的主節(jié)點(diǎn)。換句話說，局部環(huán)將具有相同立方體索引的節(jié)點(diǎn)連接在一起，而大環(huán)連接了所有立方體索引不同的節(jié)點(diǎn)。一個環(huán)上的節(jié)點(diǎn)可以直接或間接地到達(dá)其他環(huán)上的節(jié)點(diǎn)。容易看出，如果所有的節(jié)點(diǎn)都是活動的那么網(wǎng)絡(luò)就是傳統(tǒng)的立方體連接環(huán)（CCC）。

5 路由算法

Cycloid 的路由算法模擬了CCC 的路由算法從源點(diǎn)（k，ad-1ad-2...a0）到目標(biāo)點(diǎn)（l，bd-1bd-2...b0），即使缺少許多節(jié)點(diǎn)，其余的節(jié)點(diǎn)仍然能夠被連接在一起，所以我們的鏈接模型是彈性的。路由過程如圖3。

Cycloid 的路由算法分為三個階段（N 表示當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的最大的不同位下標(biāo)）：

（1）上升階段：當(dāng)關(guān)鍵字k≤N 時，將該請求沿外葉子節(jié)點(diǎn)轉(zhuǎn)發(fā)直到環(huán)索引k≥N。

（2）下降階段：當(dāng)k=N 時，將請求轉(zhuǎn)發(fā)到立方體鄰居；否則，為了靠近目標(biāo)立方體索引，需將請求轉(zhuǎn)發(fā)到內(nèi)葉子節(jié)點(diǎn)和環(huán)鄰居中最接近目標(biāo)的節(jié)點(diǎn)。

（3）橫向階段：當(dāng)目標(biāo)id 在葉子集中，將請求轉(zhuǎn)發(fā)到最近葉子節(jié)點(diǎn)，直到最接近的節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)本身。

特別的，上升階段從外葉子集中選擇立方體索引數(shù)字上最靠近目標(biāo)的節(jié)點(diǎn)。在下降階段，當(dāng)k＞N 時，選擇立方體索引最靠近目標(biāo)的節(jié)點(diǎn)。當(dāng)k＜N 時，從環(huán)鄰居和內(nèi)葉子集中選擇更接近目標(biāo)的環(huán)鄰居。當(dāng)k=N時，前綴路由算法從左到右的將ad-1…a1a0改變?yōu)閎d-1…b1b0。沿著立方體鏈，信息被送到與關(guān)鍵字至少匹配更多一位前綴的節(jié)點(diǎn)。立方體鏈、環(huán)鏈或內(nèi)葉子集是可以交替使用的。在橫向階段，如果目標(biāo)在局部環(huán)中，信息將被送到內(nèi)葉子集中的一個節(jié)點(diǎn)；否則，信息將被轉(zhuǎn)發(fā)到外葉子集中數(shù)字上更靠近目標(biāo)的節(jié)點(diǎn)。如果最近的節(jié)點(diǎn)是它自己，那么就到達(dá)了目標(biāo)，搜索就完成了。在整個查詢過程中，如果某個節(jié)點(diǎn)不能找到或是已經(jīng)失效，那么將選擇葉子集中數(shù)字上更靠近目標(biāo)的節(jié)點(diǎn)。葉子集在路由算法中起的作用很大，它用來改進(jìn)路由的效率，檢查查詢的終止條件，并包圍關(guān)鍵字空間以防止超過目標(biāo)。

圖4 Cycloid路由實(shí)例

圖4 是一個4 維Cycloid 路由的實(shí)例，一個請求從節(jié)點(diǎn)（0，0100）路由到（2，1111）。節(jié)點(diǎn)（0，0100）與目標(biāo)的最大不同位下標(biāo)MSDB 是3。由于（0，0100）的環(huán)索引k=0 小于N，所以它處于上升階段，選擇外葉子集中的節(jié)點(diǎn)（3，0010）。（3，0010）的環(huán)索引k=3 等于N，所以處于下降階段，請求被轉(zhuǎn)發(fā)到它的立方體鄰居（2，1010）。（2，1010）的環(huán)索引k=2 等于它的MSDB，將請求轉(zhuǎn)發(fā)到它的立方體鄰居（1，1110）。因為目標(biāo)（2，1111）的立方體索引1111 在（1，1110）的葉子集中，所以將請求轉(zhuǎn)發(fā)到（3，1111）。與此相似，（3，1111）發(fā)現(xiàn)目標(biāo)在他的葉子集中，就將請求轉(zhuǎn)發(fā)到（2，1111），請求就到達(dá)了目的地。

路由過程三階段中的每一個的界都是O（d）跳，所以整個路徑的長度是O（d）。算法背后的思想是保持距離不斷的減小。文獻(xiàn)[4]用算法的收斂性和可達(dá)性證明了路由算法的正確。所謂收斂性是指路由的每一步都減少了到目標(biāo)的距離。所謂正確性是指每個相繼的節(jié)點(diǎn)都把信息轉(zhuǎn)發(fā)到下一個節(jié)點(diǎn)。因為每一步都是將查詢請求轉(zhuǎn)發(fā)到與關(guān)鍵字共享更長前綴的節(jié)點(diǎn)或共享相同前綴但數(shù)字上更接近目標(biāo)的節(jié)點(diǎn)，所以路由算法是收斂的。這個路由算法可以很容易的擴(kuò)充以增加容錯性。當(dāng)立方體鏈或環(huán)鏈為空或失效時，可以將信息轉(zhuǎn)發(fā)到葉子集中的節(jié)點(diǎn)。以上討論的是基于7 個入口的Cycloid，它可以被擴(kuò)展到在內(nèi)外葉子集中包括兩個前導(dǎo)和連個后繼節(jié)點(diǎn)。模擬顯示11 個入口的Cycloid具有更好的性能。

6 自組織

P2P 系統(tǒng)的高動態(tài)性意味著節(jié)點(diǎn)會經(jīng)常地加入或離開網(wǎng)絡(luò)。Cycloid 用分布式的算法處理節(jié)點(diǎn)的加入和離開，不需要知道整個網(wǎng)絡(luò)的信息。

6.1 節(jié)點(diǎn)加入

當(dāng)一個新節(jié)點(diǎn)加入時，首先用第3 節(jié)的方法得到自己的ID。然后，它初始化自己的路由表和葉子集[15]，并通知其他節(jié)點(diǎn)。像Chord 一樣，Cycloid 假設(shè)任何新節(jié)點(diǎn)都知道一個活動節(jié)點(diǎn)。假設(shè)已知的活動節(jié)點(diǎn)是A=（k，ad-1ad-2...a0），新節(jié)點(diǎn)是X=（l，bd-1bd-2...b0）。根據(jù)第5 節(jié)討論的路由算法，節(jié)點(diǎn)A 將把加入信息路由到其ID 在數(shù)字上最靠近X 的節(jié)點(diǎn)Z 上。Z 的葉子集將是X的葉子集的基礎(chǔ)。特別的，需要考慮下面兩種情況：

（1）如果X 和Z 在同一個環(huán)中，那么Z 的外葉子集將成為X 的外葉子集。X 的內(nèi)葉子集將根據(jù)Z 的內(nèi)葉子集進(jìn)行初始化。如果Z 是X 的后繼節(jié)點(diǎn)，Z 的前導(dǎo)和Z 是X 的內(nèi)葉子集中相應(yīng)的左節(jié)點(diǎn)和右節(jié)點(diǎn)。否則，Z 和Z 的后繼是左節(jié)點(diǎn)和右節(jié)點(diǎn)。

（2）如果X 是它的局部環(huán)中的唯一節(jié)點(diǎn)，那么Z 和X 不在同一個環(huán)中。在這種情況下，X 的內(nèi)葉子集中的兩個節(jié)點(diǎn)就是X 本身。X 的外葉子集根據(jù)Z 的外葉子集初始化。如果Z 的環(huán)是X 的后繼遠(yuǎn)環(huán)，那么Z 的左外葉子集節(jié)點(diǎn)和Z 所在環(huán)的主節(jié)點(diǎn)就是X 的外葉子節(jié)點(diǎn)中的左右節(jié)點(diǎn)。否則，Z 所在環(huán)的主節(jié)點(diǎn)和Z 的右外葉子節(jié)點(diǎn)是X 的外葉子集的左右節(jié)點(diǎn)。

節(jié)點(diǎn)加入系統(tǒng)之后，需要通知它的內(nèi)葉子集中的節(jié)點(diǎn)。如果他是局部環(huán)的主節(jié)點(diǎn)，則還要通知它的外葉子集中的節(jié)點(diǎn)。當(dāng)內(nèi)葉子集中的節(jié)點(diǎn)收到加入信息時，它們會更新自己的路由表。當(dāng)外葉子集節(jié)點(diǎn)收到加入信息時，除了更新自己的路由表之外，它們還要將此信息傳播到它的內(nèi)葉子集節(jié)點(diǎn)[16]。如此，加入信息沿著加入節(jié)點(diǎn)的鄰居遠(yuǎn)環(huán)傳播，直到所有的環(huán)都完成更新。

6.2 節(jié)點(diǎn)離開

在一個節(jié)點(diǎn)離開之前，它需要通知它的內(nèi)葉子集節(jié)點(diǎn)[17]。在Cycloid 中，一個節(jié)點(diǎn)只有出的連接而沒有入的連接。因此，將要離開的節(jié)點(diǎn)不能通知那些將它作為立方體鄰居或環(huán)鄰居的節(jié)點(diǎn)。如果該節(jié)點(diǎn)是局部環(huán)中的主節(jié)點(diǎn)，則還需要通知外葉子集中的節(jié)點(diǎn)。當(dāng)內(nèi)外葉子集節(jié)點(diǎn)收到節(jié)點(diǎn)的離開信息時都需要更新自己。而外葉子集節(jié)點(diǎn)還需要一個一個的通知它們的局部環(huán)中的其他節(jié)點(diǎn)，這個過程最多需要d 步。只有那些將這個要離開的節(jié)點(diǎn)作為內(nèi)葉子或外葉子的節(jié)點(diǎn)被更新。那些將這個離開節(jié)點(diǎn)作為立方體鄰居或環(huán)鄰居的節(jié)點(diǎn)不能被更新。

7 結(jié)語

CCC 圖的特性保證無論維數(shù)取多少，節(jié)點(diǎn)的度都保持為3，這成為Cycloid 的節(jié)點(diǎn)保持常數(shù)個鄰居的基礎(chǔ)。同樣的具有常數(shù)度的P2P 系統(tǒng)中Viceroy 使用butterfly 圖，Koorde 使用de bruijn 圖。模擬結(jié)果[6]顯示Cycloid 適合大規(guī)模的高動態(tài)的環(huán)境，具有更好的平均定位效率，在稀疏網(wǎng)絡(luò)情況下，具有更均勻的關(guān)鍵字分布和負(fù)載平衡性能。今后我們要進(jìn)一步研究更多的P2P 系統(tǒng)和互連網(wǎng)絡(luò)，尋找更好的適合P2P 的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。