常數(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é)點的加入和離開網(wǎng)絡(luò)攪動劇烈時會產(chǎn)生巨大的開銷[5]，為了減少開銷，一些具有常數(shù)度（即節(jié)點只維護常數(shù)個鄰居）的P2P 系統(tǒng)被提出來如Cycloid[8-9]、Koorde[7]和Viceroy[6]等。這些系統(tǒng)具有O（logN）的網(wǎng)絡(luò)直徑，固定地維護較少的常數(shù)個鄰居，如Cycloid 和Viceroy 鄰居數(shù)均為7、Koorde 鄰居數(shù)最小為2。本文詳細介紹了Cycloid系統(tǒng)。

1 Cycloid的拓撲結(jié)構(gòu)

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

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

圖1 三維CCC圖

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

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

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

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

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

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

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

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

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

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

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

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

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

一般情況下，節(jié)點（k,ad-1ad-2…a0）(k ≠0)有7 個鄰居節(jié)點。其中一個立方體鄰居（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且最大不相同位的下標值小于k 的節(jié)點。即：

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

5 路由算法

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

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

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

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

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

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

圖4 Cycloid路由實例

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

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

6 自組織

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

6.1 節(jié)點加入

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

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

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

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

6.2 節(jié)點離開

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

7 結(jié)語

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