Chord路由算法的改進(jìn)與研究

歐陽竟成, 彭鄧華, 彭 鑫

?

Chord路由算法的改進(jìn)與研究

歐陽竟成, 彭鄧華, 彭 鑫

(湖南理工學(xué)院信息與通信工程學(xué)院, 湖南岳陽 414006)

針對(duì)原始Chord路由中查尋效率不高以及表項(xiàng)存在冗余信息的問題, 提出一種改進(jìn)的Chord路由算法, 利用對(duì)立節(jié)點(diǎn)建立順時(shí)針與逆時(shí)針兩個(gè)路由表, 實(shí)現(xiàn)了雙向查尋, 同時(shí)改進(jìn)了路由表構(gòu)造方法, 減少了冗余表項(xiàng). 理論分析與仿真實(shí)驗(yàn)表明, 該算法降低了查詢的平均路徑長度, 提高了查尋效率.

P2P網(wǎng)絡(luò); Chord; 路由表; 雙向查尋

引言

目前, P2P技術(shù)已經(jīng)成為互聯(lián)網(wǎng)中的重要應(yīng)用與服務(wù), 如分布式計(jì)算、文件交換、協(xié)同設(shè)計(jì)、即時(shí)通信等應(yīng)用系統(tǒng)都集成了P2P技術(shù)[1]. 近年來網(wǎng)絡(luò)流媒體播放系統(tǒng)也普遍地引入了P2P技術(shù)[2], 而承載這些應(yīng)用的重要機(jī)制是資源的搜索定位技術(shù).

按網(wǎng)絡(luò)中節(jié)點(diǎn)和資源的關(guān)系可以將P2P網(wǎng)絡(luò)分為兩大類, 一類為非結(jié)構(gòu)化P2P網(wǎng)絡(luò), 如Kazaa[3]與Gnutella[4]等; 另一類為結(jié)構(gòu)化P2P網(wǎng)絡(luò), 如Chord[5]與CAN[6]等. 非結(jié)構(gòu)化P2P網(wǎng)絡(luò)采用泛洪協(xié)議查尋資源, 查尋速度較慢而且消耗大量帶寬; 結(jié)構(gòu)化P2P網(wǎng)絡(luò)則利用分布式哈希表(Distributed Hash Table, DHT)查尋資源, 速度較快但查詢召回率較低. Chord協(xié)議[5]是美國麻省理工學(xué)院于2001年開發(fā)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)協(xié)議, 平均查尋路徑長度為O(log2()), 其中為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù). 為了提高路由效率, 許多學(xué)者對(duì)Chord算法做了進(jìn)一步的改進(jìn). Ganesan等人提出了一種雙向路由Chord算法[7], 基本思想是同時(shí)構(gòu)建當(dāng)前節(jié)點(diǎn)的順時(shí)針和逆時(shí)針方向路由表, 雙向路由Chord算法的平均查詢路徑長度可以降低到,為節(jié)點(diǎn)標(biāo)識(shí)符的二進(jìn)制長度(可認(rèn)為,為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)), 但它的缺點(diǎn)是路由表空間是原Chord算法的兩倍. 文[8]提出了一種基于雙向搜索Chord路由算法的NFT-chord, 引入路由因子構(gòu)造一種新的路由表, 消除了路由表中的絕大部分冗余信息, 并且實(shí)現(xiàn)了雙向查找, 但是該方法中查尋過程的每步都要試探順時(shí)針方向或逆時(shí)針方向, 算法復(fù)雜度太高.

本文提出一種改進(jìn)的Chord雙向路由算法, 利用對(duì)立節(jié)點(diǎn)建立順時(shí)針與逆時(shí)針兩個(gè)路由表, 實(shí)現(xiàn)了雙向查尋, 同時(shí)引入?yún)?shù)減少了路由表中的冗余項(xiàng)目. 理論分析與仿真實(shí)驗(yàn)證明, 本文的Chord路由算法可以進(jìn)一步減少查詢的平均路徑長度, 提高查尋效率.

1 Chord路由算法

Chord算法是一種基于DHT的分布式查尋算法, 它采用一致性哈希函數(shù)將網(wǎng)絡(luò)中的資源及節(jié)點(diǎn)都通過同一函數(shù)運(yùn)算得到各自的標(biāo)識(shí)符ID. 在哈希函數(shù)的hash值長度足夠長的前提下, 能夠充分保證資源及節(jié)點(diǎn)的ID不會(huì)被重復(fù)映射, 于是每個(gè)節(jié)點(diǎn)和關(guān)鍵字都分配一個(gè)位的唯一標(biāo)識(shí)符, 通過將標(biāo)識(shí)符對(duì)2取模后順序排列, 便形成了一個(gè)大小為2的圓環(huán), 該環(huán)稱為Chord環(huán). 每個(gè)節(jié)點(diǎn)維護(hù)一張路由表(finger table), 并且路由表有個(gè)表項(xiàng), 關(guān)鍵字標(biāo)識(shí)符為的資源被分配給Chord環(huán)上節(jié)點(diǎn)標(biāo)識(shí)符為的節(jié)點(diǎn); 如果該節(jié)點(diǎn)不存在, 則該資源被分配給Chord環(huán)上節(jié)點(diǎn)標(biāo)識(shí)符大于或等于鍵值ID為的第一個(gè)節(jié)點(diǎn), 即順時(shí)針方向距離最近的節(jié)點(diǎn). 存儲(chǔ)關(guān)鍵字的節(jié)點(diǎn)稱為關(guān)鍵字的后繼節(jié)點(diǎn), 用Successor()表示. 在Chord環(huán)上逆時(shí)針方向距離鍵值最近的節(jié)點(diǎn)稱為前繼節(jié)點(diǎn), 用Predecessor() 表示. Chord算法中節(jié)點(diǎn)的唯一標(biāo)識(shí)符記為, 其路由表的第項(xiàng)為:

Chord算法中節(jié)點(diǎn)N1的路由表(finger table)模型如圖1所示.

從圖1可以看出, Chord的路由查詢過程為: 如果節(jié)點(diǎn)N1要查找關(guān)鍵字50, 它發(fā)現(xiàn)關(guān)鍵字50沒有存儲(chǔ)在本地, 節(jié)點(diǎn)N1查找自己的路由表得到關(guān)鍵字50的最大后繼節(jié)點(diǎn)為N38, 節(jié)點(diǎn)N1將查詢請(qǐng)求轉(zhuǎn)發(fā)給節(jié)點(diǎn)N38, 如果本地有該關(guān)鍵字就立即響應(yīng)請(qǐng)求節(jié)點(diǎn), 查尋結(jié)束, 但是關(guān)鍵字50沒有存儲(chǔ)在本地, 節(jié)點(diǎn)N38檢查自己的路由表, 將查詢請(qǐng)求轉(zhuǎn)發(fā)給節(jié)點(diǎn)N48, 如此反復(fù), 直到路由至關(guān)鍵字50的后繼節(jié)點(diǎn)N51, 查詢結(jié)束. 查尋請(qǐng)求共需要經(jīng)歷3次轉(zhuǎn)發(fā)才能找到結(jié)果, 查詢效率不高, 并且路由表中存在冗余信息.

2改進(jìn)的Chord路由算法

2.1 路由表構(gòu)造

假定Chord環(huán)標(biāo)識(shí)符空間大小為2, 定義的范圍為, 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù). 一般情況下有, 即實(shí)際節(jié)點(diǎn)數(shù)遠(yuǎn)小于標(biāo)識(shí)空間大小, 同時(shí)一致性哈希算法(如SHA-1)的性質(zhì)能夠確保所有節(jié)點(diǎn)幾乎均勻分布于chord環(huán)空間. 若按照初始Chord路由方案, 必然會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)的路由表冗長, 并且前半部分呈現(xiàn)幾個(gè)路由項(xiàng)指向同一節(jié)點(diǎn)的現(xiàn)象, 從而降低了查尋速度, 文[9]對(duì)這種現(xiàn)象進(jìn)行了詳細(xì)分析. 本文提出順時(shí)針方向半環(huán)與逆時(shí)針方向半環(huán)雙重路由表的構(gòu)造方案. 首先選擇正向的最后一項(xiàng)標(biāo)識(shí)符為對(duì)應(yīng)的節(jié)點(diǎn)作為對(duì)立節(jié)點(diǎn), 從邏輯上將Chord環(huán)臨時(shí)分成兩個(gè)半環(huán), 實(shí)現(xiàn)雙向查尋, 在查尋的第一步就能夠確定目標(biāo)節(jié)點(diǎn)在Chord環(huán)的前半部分還是后半部分, 縮小查尋范圍, 提高查尋速度. 該方法第一步就是確定對(duì)立節(jié)點(diǎn), 用表示, 計(jì)算公式為

為了使路由表從第一項(xiàng)開始盡量降低冗余信息并且基本上確保路由表項(xiàng)節(jié)點(diǎn)的均勻分布, 仿照文[9]的方法, 引入一個(gè)參數(shù). 當(dāng)時(shí),, 其中, 即相鄰兩節(jié)點(diǎn)在Chord標(biāo)識(shí)空間上的平均距離. 取為, 因此, 構(gòu)造順時(shí)針的路由表公式為

同理, 構(gòu)造逆時(shí)針的路由表公式為

(4)

例如,= 6, 節(jié)點(diǎn)數(shù)為10個(gè), 23<10, 則取值為4, 計(jì)算得, 利用上述公式可得改進(jìn)后的路由表模型如圖2所示.

2.2 查詢過程

假定當(dāng)前節(jié)點(diǎn)為當(dāng)前, 其對(duì)立節(jié)點(diǎn)為, 查尋請(qǐng)求被哈希函數(shù)映射后的關(guān)鍵字為, 查找過程如下:

(1)當(dāng)前收到查尋關(guān)鍵字, 判斷是否存儲(chǔ)在本地, 如果是, 則直接響應(yīng)查尋請(qǐng)求節(jié)點(diǎn), 查詢結(jié)束; 否則, 繼續(xù)執(zhí)行.

(2) 判斷與的大小, 若, 轉(zhuǎn)(3); 否則, 判斷是否屬于(當(dāng)前, Successor(當(dāng)前)) , 如果是, 那么Successor(當(dāng)前)即為目標(biāo)節(jié)點(diǎn), 將查詢請(qǐng)求轉(zhuǎn)發(fā)給Successor(當(dāng)前), 返回(1); 否則, 查找Chord環(huán)的順時(shí)針路由表, 找到小于的最大鍵值ID所對(duì)應(yīng)的節(jié)點(diǎn)Node1, 將查詢請(qǐng)求轉(zhuǎn)發(fā)給Node1, 返回(1).

(3) 判斷是否屬于(當(dāng)前, Predecessor(當(dāng)前)) , 如果是, 那么Predecessor(當(dāng)前)即為所求的節(jié)點(diǎn), 將查詢請(qǐng)求轉(zhuǎn)發(fā)給Predecessor(當(dāng)前), 返回(1); 否則, 查找Chord環(huán)的逆時(shí)針路由表, 找到大于的最小鍵值ID所對(duì)應(yīng)的節(jié)點(diǎn)Node2, 將查詢請(qǐng)求轉(zhuǎn)發(fā)給Node2, 返回(1).

從圖2新構(gòu)造的路由表可以看出, 節(jié)點(diǎn)1要查找關(guān)鍵字50時(shí), 關(guān)鍵字不在本地, 于是它第一步就確定了從逆時(shí)針路由表查找, 定位到節(jié)點(diǎn)N51, 將查尋請(qǐng)求轉(zhuǎn)發(fā)給節(jié)點(diǎn)N51, 關(guān)鍵字50就存儲(chǔ)在節(jié)點(diǎn)N51上, 因此, 只需要一次查尋轉(zhuǎn)發(fā)(即一跳)就可以找到資源, 減少了查找跳數(shù), 從而提高了搜索效率.

3算法性能分析與仿真實(shí)驗(yàn)

3.1 算法性能分析

新構(gòu)建的路由算法有效減少了查尋的平均路徑長度. 初始Chord模型中, 若網(wǎng)絡(luò)中有2個(gè)節(jié)點(diǎn), 查詢的平均查找路徑長度為, 由文[5]的分析可知

設(shè)改進(jìn)后的Chord路由平均路徑長度為, 前半環(huán)的路徑長度為1, 后半環(huán)的長度為2, 而前半環(huán)的查詢性能與初始Chord相一致, 所以前半環(huán)的查詢路徑長度為

(6)

后半環(huán)路由表的構(gòu)造與前半環(huán)的一樣, 而原來的路由表沒有覆蓋后半環(huán)的路由信息, 因此可得后半環(huán)的平均查找路徑長度為

由于查尋關(guān)鍵字落在前半環(huán)或后半環(huán)的概率均為1/2, 因此得出改進(jìn)后的Chord路由查尋平均路徑長度為

(8)

假設(shè)為12, 可計(jì)算出初始Chord模型的平均查找路徑長度約為1.8, 改進(jìn)后的Chord算法的平均路徑長度約為1.29, 可見平均查尋路徑長度降低了, 查尋效率提高了.

同時(shí), 改進(jìn)的Chord路由表構(gòu)造方案基本上消除了原路由表中的冗余項(xiàng). 在大小為2的Chord環(huán)上, 網(wǎng)絡(luò)的實(shí)際節(jié)點(diǎn)數(shù)為2(), 且所有節(jié)點(diǎn)均勻分布在Chord環(huán)的網(wǎng)絡(luò)中, 由此可以得出任意兩個(gè)相鄰節(jié)點(diǎn)之間的間距為. 如果, 即, 則路由表中存在冗余信息, 并且在路由表中越靠前的表項(xiàng)中相鄰節(jié)點(diǎn)之間的邏輯距離越小, 就越容易出現(xiàn)信息冗余的情況, 但是, 當(dāng)時(shí), 路由表中出現(xiàn)冗余的概率小到可忽略不計(jì). 假設(shè)當(dāng)前節(jié)點(diǎn)為, 利用Chord算法構(gòu)造的路由表表項(xiàng)節(jié)點(diǎn)依次為+1,+2,+4,+8,…, 如果與的后繼節(jié)點(diǎn)在Chord環(huán)上相差的邏輯距離大于2, 路由表的第一項(xiàng)和第二項(xiàng)所對(duì)應(yīng)的節(jié)點(diǎn)就是相同的, 就出現(xiàn)信息冗余. 而對(duì)改進(jìn)后的Chord算法新構(gòu)造的路由表公式中加入?yún)?shù), 得到的路由表項(xiàng)節(jié)點(diǎn)依次為觀察公式可以看出, 不論順時(shí)針還是逆時(shí)針, 從第一項(xiàng)開始節(jié)點(diǎn)間的邏輯距離便大于等于, 在節(jié)點(diǎn)均勻分布的Chord網(wǎng)絡(luò)中很難出現(xiàn)路由表項(xiàng)信息冗余的情況.

3.2 仿真實(shí)驗(yàn)

使用PeerSim[10]平臺(tái), 再加入我們自己編寫的代碼, 實(shí)現(xiàn)本文的仿真實(shí)驗(yàn). PeerSim是一個(gè)基于JAVA語言的源代碼開放的P2P仿真平臺(tái), 其中包含了許多P2P組件, 用戶通過制作一個(gè)配置文件來調(diào)用若干組件完成仿真任務(wù). 該軟件包中已經(jīng)提供初始Chord協(xié)議, 我們只需要編寫改進(jìn)的Chord協(xié)議. 在實(shí)驗(yàn)環(huán)境中設(shè)置若干共享文件作為網(wǎng)絡(luò)資源, 即假設(shè)一個(gè)理想的文件共享網(wǎng)絡(luò), 任意節(jié)點(diǎn)可以訪問到它需要的任意文件; 并且能夠從擁有該資源的節(jié)點(diǎn)下載文件, 實(shí)驗(yàn)基于周期仿真. 仿真環(huán)境的具體配置見表1.

實(shí)驗(yàn)中設(shè)置= 18, 即Chord網(wǎng)絡(luò)標(biāo)識(shí)符空間大小為, 節(jié)點(diǎn)數(shù)取值從1000~10000, 在某一規(guī)模的網(wǎng)絡(luò)中, 節(jié)點(diǎn)隨機(jī)訪問文件并且進(jìn)行下載, 重復(fù)10個(gè)周期, 統(tǒng)計(jì)P2P覆蓋網(wǎng)的平均查找路徑長度, 數(shù)據(jù)如圖3所示.

從圖3可以看出, 改進(jìn)后的Chord路由算法比初始的Chord在查尋路徑長度上有較大減少, 與理論分析相符.

4結(jié)束語

本文針對(duì)Chord路由表中存在冗余信息與算法查尋效率不高等問題, 提出了一種改進(jìn)的Chord路由算法. 每個(gè)節(jié)點(diǎn)利用對(duì)立節(jié)點(diǎn)建立了順時(shí)針與逆時(shí)針兩個(gè)路由表, 以便在查尋資源的第一步就能夠確定目標(biāo)節(jié)點(diǎn)在Chord環(huán)的前半部分還是后半部分, 縮小了查尋范圍, 實(shí)現(xiàn)了雙向查尋, 同時(shí)引入?yún)?shù)減少了路由表中的冗余信息. 理論分析與仿真實(shí)驗(yàn)表明改進(jìn)后的Chord路由算法平均查尋路徑長度相對(duì)于初始Chord路由算法有較大的減少. 但是, 本文沒有考慮物理網(wǎng)絡(luò)中節(jié)點(diǎn)的加入與離開時(shí)覆蓋網(wǎng)的通信開銷與維護(hù)代價(jià), 這是進(jìn)一步研究中要解決的問題.

[1] Androutsellis-Theotokis S., SpinellisD..[J]. ACM Computing Surveys, 2004, 36(4):335~371

[2] 張明軍, 彭 婭, 俞文靜. P2P流媒體服務(wù)方案及其關(guān)鍵技術(shù)研究[J]. 計(jì)算機(jī)工程, 2013, 39(01): 125~130

[3] LTD S.N..KaZaa media desktop. http://www.KaZaa.com/,2006-09-12.

[4] Gnutella Protocol Specification, version 0.4. http://www.clip2.com/GnutellaProtocol04.pdf, 2005-09-18

[5] StociaI,MorirsR,KargerD,et al.[J]. IEEE/ACM Transaction on Networking, 2003, 11(1):17~32

[6] Ratnasamy S., Francis P., Handley M., et al.[C]. In: Proceedings of ACM SIGCOMM’2001. San Diego, California, USA: ACM Press, 2001: 161~172

[7] GANESAN P, MANKU GS. Optimal Routing in Chord[D]. Stanford University, SODA 2004

[8] 王 慧, 王 錚. 基于新路由表的雙向搜索chord路由算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2014, 50(23): 95~99

[9] 祁 玉, 張新有. chord 路由表結(jié)構(gòu)的分析與改進(jìn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2010, 31(6): 1170~1172

[10] PeerSim[EB/OL]. http://PeerSim.Sourceforge.net/, 2008-2-10

Improvement and Research on Routing Algoithm of Chord

OUYANG Jingcheng, PENG Denghua, PENG Xin

(College of Information and Communication Engineering, Hunan Institute of Science and Technology,Yueyang 414006, China)

In this paper, an improved Chord routing algorithm is proposed to solve problems of inefficient search and redundant information in original Chord routing. These clockwise and counter clockwise routing tables are established using the opposite node to implement bidirectional search. Meanwhile, the routing table construction method is improved to reduce redundant items in routing tables. Theoretical analysis and simulation results show that the proposed algorithm can reduce the average path length of queries and improve the search efficiency.

P2P network, Chord, routing table, bidirectional search

TP393

A

1672-5298(2017)01-0017-04

2017-01-10

湖南省科技計(jì)劃項(xiàng)目(2016TP1021); 湖南理工學(xué)院學(xué)位與研究生教育教改項(xiàng)目(YJG2017A004); 湖南省研究生科研創(chuàng)新項(xiàng)目(CX2016B671)

歐陽竟成(1967? ), 男, 湖南平江人, 博士, 湖南理工學(xué)院信息與通信工程學(xué)院副教授. 主要研究方向: 對(duì)等網(wǎng)絡(luò), 信息檢索與信息安全