基于CHORD環(huán)的DHT全分布式P2P網(wǎng)絡(luò)結(jié)構(gòu)分析

曹 建

(蘇州工業(yè)職業(yè)技術(shù)學(xué)院 軟件與服務(wù)外包學(xué)院，江蘇 蘇州 215104)

基于CHORD環(huán)的DHT全分布式P2P網(wǎng)絡(luò)結(jié)構(gòu)分析

曹 建

(蘇州工業(yè)職業(yè)技術(shù)學(xué)院 軟件與服務(wù)外包學(xué)院，江蘇 蘇州 215104)

通過對CHORD算法的詳細研究和分析，結(jié)合DHT全分布式P2P網(wǎng)絡(luò)的結(jié)構(gòu)要求，給出了一種基于CHORD環(huán)的DHT全分布式P2P網(wǎng)絡(luò)算法，并給出了基礎(chǔ)算法的偽代碼.

DHT；P2P；CHORD；網(wǎng)絡(luò)協(xié)議

對等計算(Peer-to-Peer，簡稱P2P)技術(shù)作為一個新的網(wǎng)絡(luò)技術(shù)在近幾年得到迅速發(fā)展，并成為計算機界關(guān)注的熱門話題之一，財富雜志更將P2P技術(shù)列為影響Internet未來的四項科技之一.目前的拓?fù)浣Y(jié)構(gòu)關(guān)系可以將P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分為4種：中心化拓?fù)浣Y(jié)構(gòu)(centralized topology)，全分布式非結(jié)構(gòu)化結(jié)構(gòu)(decentralized unstructured topology)，半分布式結(jié)構(gòu)(partially decentralized topology)，全分布式結(jié)構(gòu)化結(jié)構(gòu)(decentralized structured topology).而全分布式結(jié)構(gòu)化結(jié)構(gòu)，也稱為DHT結(jié)構(gòu)，除了能夠自適應(yīng)結(jié)點的動態(tài)加入/退出，而且有著良好的可擴展性、魯棒性、結(jié)點ID分配的均勻性和自組織能力，同時由于其采用了確定的拓?fù)浣Y(jié)構(gòu)，DHT可以提供精確的發(fā)現(xiàn)功能，廣泛應(yīng)用于全分布式P2P網(wǎng)絡(luò)架構(gòu)設(shè)計.

1 CHORD算法分析

CHORD是一種基于DHT的分布式查詢算法，兩者之間的關(guān)系如圖1所示，2001年由麻省理工學(xué)院提出.CHORD協(xié)議使用同一個HASH算法為每個結(jié)點以及資源分別分配一個m位的標(biāo)識，所有標(biāo)識符分布在一個大小為2m的CHORD環(huán)結(jié)構(gòu)上，標(biāo)識符范圍為0到2m-1，每一個資源信息根據(jù)其Resource-ID被分配到第一個在標(biāo)識符空間里Node-ID值大于等于該Resource-ID的結(jié)點上.這個結(jié)點被稱為Resource-ID的后繼結(jié)點，即successor(Resource-ID)，資源相關(guān)信息就保存在這個后繼結(jié)點上.

1.1 CHORD邏輯結(jié)構(gòu)構(gòu)成

在CHORD算法中，所有結(jié)點根據(jù)其Node-ID大小，邏輯上形成首尾相連成一個環(huán)形結(jié)構(gòu)，在一個最大容量結(jié)點數(shù)為2m的CHORD環(huán)結(jié)構(gòu)內(nèi)，每個結(jié)點需要存儲和維護一個具有m個其他結(jié)點信息的表格，這些信息的集合被稱為路由表(finger table，也稱為查詢表)，表格中的結(jié)點不是直接相鄰的結(jié)點，它們的間距(ID間隔)將成2i的關(guān)系排列(i表示表中的數(shù)組下標(biāo)).圖2為一個m=6的CHORD環(huán)結(jié)構(gòu)P2P網(wǎng)絡(luò)示意圖，圖中結(jié)點ID和資源ID的標(biāo)識范圍為[0-63]，環(huán)中每個結(jié)點維護一個路由表，表中共m個表項.資源查詢定位是按照順時針方向跳躍式進行.

1.2 主要數(shù)據(jù)結(jié)構(gòu)描述

在詳細描述CHORD算法的定位和路由策略前，先定義CHORD算法所需要的幾個重要數(shù)據(jù)結(jié)構(gòu)：

1) 后繼結(jié)點列表(successor node list)，所謂后繼結(jié)點(successor)是指那些結(jié)點Node-ID值≥本結(jié)點Node-ID的結(jié)點(模運算)，其中最小的那個結(jié)點叫做直接后繼結(jié)點.后繼結(jié)點的主要作用在于形成CHORD環(huán)結(jié)構(gòu)，保證CHORD算法的正確運行.由于P2P網(wǎng)絡(luò)中的每一個結(jié)點都是完全獨立的，結(jié)點的加入和退出完全不受P2P網(wǎng)絡(luò)控制，為提高CHORD系統(tǒng)的正確性和可靠性，后繼結(jié)點列表由結(jié)點后續(xù)連續(xù)的若干個結(jié)點信息組成.從可靠性角度，后繼結(jié)點數(shù)目越多可靠性越高，但是后繼結(jié)點數(shù)目的增加同時會增加網(wǎng)絡(luò)數(shù)據(jù)流量，加重網(wǎng)絡(luò)負(fù)擔(dān).

2) 前驅(qū)結(jié)點(predecessor node)，指那些Node-ID值＜當(dāng)前結(jié)點Node-ID的結(jié)點(模運算)，其中最小的那個結(jié)點稱為直接前驅(qū)結(jié)點.前驅(qū)結(jié)點的主要作用在于保持和維護CHORD環(huán)結(jié)構(gòu)的穩(wěn)定性.

3) 路由表(finger table)結(jié)構(gòu)，主要用于提高結(jié)點和資源信息的查詢路由的速度，所以被稱為路由表.CHORD算法的所有查詢操作均通過操作路由表實現(xiàn)，路由表中各項分別保存一個跳躍區(qū)間[(n+2i-1)mod 2m，(n+2i)mod 2m)，并保存該區(qū)間內(nèi)起始ID編號后的第一個后繼結(jié)點信息和前驅(qū)結(jié)點信息，實現(xiàn)了2指數(shù)級跳躍式路由查詢.通過路由表操作，含有N個結(jié)點的網(wǎng)絡(luò)，查詢需要的跳數(shù)由O(N)減少到O(log2N).這樣即使在大規(guī)模的P2P網(wǎng)絡(luò)中(例如N＝100，000，000)，查詢的跳數(shù)也僅為O(8). 表1為路由表的邏輯結(jié)構(gòu)內(nèi)容[1]，但在實際存儲時，僅需要其中的start項、successor項、predecessor項.

表1 路由表邏輯結(jié)構(gòu)內(nèi)容

2 CHORD主要算法描述

CHORD算法的各項功能操作都直接或間接使用到路由表，在系統(tǒng)運行過程中，隨著結(jié)點和用戶的動態(tài)加入和退出，路由表也是動態(tài)變化的，為更好地表達查詢表操作算法，現(xiàn)設(shè)定以下幾個標(biāo)識：[2]

2.1 查詢算法

查詢算法是根據(jù)已知資源ID值(Resource-ID)找出保存該資源信息的結(jié)點，是CHORD算法的一個主要功能.最簡單的方法是從當(dāng)前結(jié)點以順時針方向逐個結(jié)點進行查找，但是這種查詢效率較低，在最壞的情況下，對于一個N個結(jié)點的CHORD環(huán)，需要查詢N次，算法復(fù)雜度O(N).[3]

CHORD查詢算法利用路由表進行跳躍式查詢，查詢過程是一個反復(fù)的過程，使得查詢結(jié)果越來越接近于目標(biāo)結(jié)點，并在O(log2N)算法復(fù)雜度內(nèi)找到目標(biāo)結(jié)點.首先判斷是否保存在自身結(jié)點，如果是，則直接返回自身結(jié)點；否則在路由表中查詢.具體算法偽代碼如下：對于圖3的CHORD環(huán)結(jié)構(gòu)中，假設(shè)在結(jié)點8上查找資源ID為40的資源信息，具體過程如下：1) 先在結(jié)點8上查找路由表，找到最近的匹配項為ID=32的結(jié)點.然后向結(jié)點32發(fā)送查找Resource-ID=40的資源信息的請求；

2) 結(jié)點32發(fā)現(xiàn)Resource-ID=40的資源信息沒有保存在本機，查詢自己的路由表，找到最接近的匹配項為ID=38的結(jié)點，返回ID=38的結(jié)點信息；

3) 重復(fù)1)、2)的過程，直到在結(jié)點42上找到Resource-ID=40的資源信息，因為結(jié)點42在目前的CHORD環(huán)結(jié)構(gòu)中是40的直接后繼，返回Resource-ID=40的資源信息給結(jié)點8，查詢過程結(jié)束，查詢示意圖如圖3所示.

在每一步查找中，距離目標(biāo)結(jié)點的距離都被大約縮小了一半，因此對于一個含有N個結(jié)點的環(huán)，整個查找復(fù)雜度為O(log2N).

2.2 結(jié)點加入與退出算法

在動態(tài)P2P網(wǎng)絡(luò)中，結(jié)點的加入和退出不受任何限制，而且結(jié)點的加入和退出都將局部破壞CHORD環(huán)結(jié)構(gòu)，加入退出算法必須能夠在這一動態(tài)過程中保持正確的查找效能.

結(jié)點的加入機制通過CHORD環(huán)結(jié)構(gòu)中的前驅(qū)結(jié)點指針實現(xiàn)，新結(jié)點的加入，CHORD環(huán)結(jié)構(gòu)必須完成3個內(nèi)容：

1) 初始化加入結(jié)點的指針表和前驅(qū)結(jié)點信息.當(dāng)一個結(jié)點申請加入CHORD環(huán)時，必須借助于一個已存在的環(huán)內(nèi)結(jié)點進行引導(dǎo)，且結(jié)點加入后必須保證CHORD環(huán)結(jié)構(gòu)的完整性和穩(wěn)定性，根據(jù)算法，接入結(jié)點應(yīng)該是加入結(jié)點的直接后繼結(jié)點.結(jié)點首先根據(jù)既定算法生成Node-ID，然后向環(huán)內(nèi)一個已存在結(jié)點發(fā)出加入申請，環(huán)內(nèi)結(jié)點根據(jù)加入結(jié)點的Node-ID判斷自己是否是正確的接入結(jié)點，如果是，則執(zhí)行結(jié)點注冊；如果不是，則查找正確的接入結(jié)點(查找過程與Resource-ID查找過程類似，只不過這里查找的是Node-ID，也是一個逐步靠近的過程，在O(log2N)事件復(fù)雜度內(nèi)找到正確接入結(jié)點)，執(zhí)行加入過程.申請加入結(jié)點根據(jù)返回消息判斷是否申請成功，若申請成功，則將正確接入結(jié)點的前驅(qū)結(jié)點設(shè)為自己的前驅(qū)結(jié)點，將正確結(jié)點加上舍去正確接入結(jié)點最后一個結(jié)點信息的后繼結(jié)點鏈設(shè)為加入結(jié)點的后繼結(jié)點鏈(正確結(jié)點設(shè)為直接后繼結(jié)點)，根據(jù)正確接入結(jié)點的路由表信息結(jié)合本地結(jié)點設(shè)置本地路由表；

2) 修改正確接入結(jié)點的前驅(qū)結(jié)點信息和路由表信息.新結(jié)點的加入局部破壞了CHORD環(huán)結(jié)構(gòu)，需要修改相應(yīng)指針恢復(fù)CHORD環(huán)結(jié)構(gòu).正確接入結(jié)點需修改其直接前驅(qū)結(jié)點為新加入結(jié)點，并需修改路由表信息，以反映新結(jié)點的加入，并在穩(wěn)定性進程到來時將該信息發(fā)送出去；

3) 轉(zhuǎn)發(fā)相應(yīng)資源信息.新結(jié)點加入后，還必須將應(yīng)該有新結(jié)點保存的資源信息從正確接入結(jié)點轉(zhuǎn)存到新加入結(jié)點中.

結(jié)點的退出主要通過CHORD環(huán)結(jié)構(gòu)中的后繼結(jié)點指針實現(xiàn)，CHORD環(huán)結(jié)構(gòu)僅需要將該結(jié)點內(nèi)所有保存資源信息轉(zhuǎn)存到其直接后繼結(jié)點，直接后繼結(jié)點修改其前驅(qū)結(jié)點指針，保證CHORD環(huán)結(jié)構(gòu)的完整性.

3 CHORD算法優(yōu)點分析

根據(jù)以上分析，基于CHORD算法的DHT-P2P網(wǎng)絡(luò)具有如下優(yōu)點：

1) 負(fù)載平衡，這一優(yōu)點來自于一致性哈希，也就是一致性哈希中提到的平衡性.所有的結(jié)點以同等的概率分擔(dān)系統(tǒng)負(fù)荷，從而可以避免某些結(jié)點負(fù)載過大的情況；

2) 分布性，CHORD是純分布式系統(tǒng)，結(jié)點之間完全平等并完成同樣的工作.這使得CHORD具有很高的魯棒性，可以抵御DoS攻擊；

3) 可擴展性，CHORD協(xié)議的開銷隨著系統(tǒng)規(guī)模(結(jié)點總數(shù)N)的增加而按照O(log2N)的比例增加.因此CHORD可以用于大規(guī)模的系統(tǒng)；

4) 可用性，CHORD協(xié)議要求結(jié)點根據(jù)網(wǎng)絡(luò)的變化動態(tài)的更新查詢表，因此能夠及時恢復(fù)路由關(guān)系，使得查詢可以可靠地進行；

5) 命名的靈活性，CHORD并未限制查詢內(nèi)容的結(jié)構(gòu)，因此應(yīng)用層可以靈活地將內(nèi)容映射到鍵值空間而不受協(xié)議的限制.

4 結(jié)論

通過對CHORD環(huán)結(jié)構(gòu)的基本分析，結(jié)合DHT-P2P網(wǎng)絡(luò)特征，將CHORD環(huán)結(jié)構(gòu)與DHT-P2P網(wǎng)絡(luò)綜合運用，在分析CHORD環(huán)結(jié)構(gòu)功能的基礎(chǔ)上，對P2P中網(wǎng)絡(luò)資源查找和結(jié)點加入退出所涉及的相關(guān)概念進行了重新定義，并對算法過程進行了詳細分析和闡述，最后對基于Chord環(huán)結(jié)構(gòu)的DHT-P2P網(wǎng)絡(luò)優(yōu)點進行了簡單的分析.

[1]BRYAN D，LOWEKAMP B，JENNINGS C. A P2P approach to SIP registration and resource location，draft-bryan-sipping-p2p-02[C]//Internet Engineering Task Force，College of William and Mary，Cisco Systems，San Diego：March 5，2006.

[2]JOHNSTON A，SINNREICh H. Draft-johnston-sipping-p2p-ipcom-02[C]//Internet Engineering Task Force，SIP，P2P，and Internet Communications，San Diego：March 5，2006

[3]STOICA I，MORRIS R，KARGER D，et al. A scalable Peer-to-Peer lookup service for internet applications[C].San Diego ：ACM SIGCOMM 2001，CA August 2001.

[4]SINGH K，SCHULZRINNE H. Peer-to-peer Internet telephony using SIP：technical report of CUCS-044-04[R]. New York： 2005.

Analysis the DHT-P2P Net Structure Based on CHORD

CAO Jian

(The Software and Service Outsourcing Section，Suzhou Institute of Industrial Technology，Suzhou 215104，China)

Through research and analysis the CHORD algorithm in detail，and combined with DHT distributed P2P network structure，the algorithm for DHT-P2P Net Structure which based on CHORD ring and the pseudo code are designed.

DHT；P2P；CHORD；network protocol

TP311

A

1008-5475(2012)03-0042-04

2012-04-20;

2012-05-29

上海市基礎(chǔ)研究重點資助項目(08JC1409200)

曹 建(1979-)，男，江蘇鹽城人，工程師，碩士，主要從事P2P網(wǎng)絡(luò)、多媒體網(wǎng)絡(luò)、網(wǎng)絡(luò)安全方向研究.

(責(zé)任編輯: 李 華)