对等网络中Chord路由算法的研究

程亚维,刘书伦

(济源职业技术学院信息工程系,河南济源459000)

对等网络中Chord路由算法的研究

程亚维,刘书伦

(济源职业技术学院信息工程系,河南济源459000)

随着互联网信息技术的不断发展,计算机硬件性能的更新、共享,基于对等网络信息定位和资源共享技术被广泛关注.针对对等网络拓扑结构的分类,对结构化P2P网络Chord路由算法进行了详细分析,论述了Chord算法的优势和不足,结合系统查询效率低下问题,提出优化下一跳节点选择方案,提高算法的查找效率.

对等网络;Chord;路由算法

随着互联网信息技术的不断发展,计算机硬件性能的更新、共享,基于对等网络信息定位和资源共享技术被广泛关注.在对等网络(P2P)网络中,深入挖掘网络节点的能力,将所有资源分布式存放在各个节点中,不经过中央服务器直接实现数据交换或服务技术.网络节点地位相同,既可以作为服务器也可以作为客户端.

P2P网络按照拓扑结构可以分为:以Napster系统为代表的依靠中央服务器管理存储所有节点共享信息和信息查询的集中式P2P网络,这种网络结构使网络可管理性得到了有效提高.当系统中网络节点规模不断扩展时,中央服务器很容易会出现单点故障,系统的可靠性不高;纯分布式P2P网络采用洪泛方式进行搜索[1],节点采用广播查询请求,当网络节点获取查询请求后搜索自身资源列表,例如Gnutella系统.该网络结构采用广播机制,节点覆盖率高,但网络中会产生大量冗余信息,系统负担过重难以扩展;混合式P2P网络集中式体系结构体现在局部,整体表现为分布式结构.根据网络节点在计算能力,存储空间等情况决定节点地位,典型代表有KaZaA系统;结构化P2P网络采用分布式散列表进行节点的映射和管理[2],每个网络节点仅需保存特定的节点索引信息就能够实现资源的查找,例如Chord系统、CAN系统、Pastry系统等.

1 Chord路由算法

1.1 Chord概述

Chord协议旨在提供一个适合P2P网络的分布式查找服务资源的环境,在2001年由麻省理工学院提出.在Chord网络中,通过一致性哈希函数对网络中的节点IP地址进行运算,获取每个节点的标识,即节点ID.对关键字进行哈希运算获得网络资源的标识,称为键值ID.对所有节点ID进行排序,按照从小到大以顺时针方向组成一个单向的Chord环.在Chord环中,每个网络节点都需要维护一张最多含有m个表项的路由表,路由表的第k条记录为在地址空间中和该节点的距离大等于2k(0≤k≤m,地址空间为0到2m-1)的最近节点[3].表1列出Chord节点n的路由表结构.

表1 Chord节点n的路由表结构

1.2 查询过程

当节点收到键值查询请求时,首先确定节点本身是否负责存储目标键值,如果没有,根据路由表的记录将查询请求转发到离存储目标键值最近的节点,如此下去,直到找到负责存储目标键值的节点.由n个节点组成的Chord环可以在O(log n)跳数内实现资源定位.节点n8根据路由表逐步查询键值k54的节点,见图1.

图1 Chord的节点路由表及查找

Chord网络对数据对象查询的伪代码如下:

//由节点n查找与数据对象ID匹配的后继节点

n.find_successor(id)

n'=find_predecessor(id);

return n'.successor;

//由节点n查找与数据对象ID匹配的前驱节点

n.find_predecessor(id)

n'=n;

while(id?(n',n'.successor])

n'=n'.closest_preceding_finger(id);

return n;

//返回路由表中里数据对象ID最近的节点

n.closest_preceding_finger(id);

for i=m down to 1

if(finger[i].node?(n,id))

return finger[i].node; return n;

1.3 节点的加入和退出

在Chord网络中,节点可以随时加入或离开,每个节点的后续节点始终正确.并且为了能够快速地找到资源,节点的路由表需要随时都是最新的.当节点n需要加入Chord网络时,首先定义节点n的前驱和路由表项,通过已知节点查找新节点n指针表的各表项.然后调用相关函数,完成对已存在节点的前驱及路由表的更新.最后告诉其后继节点将由节点n负责的资源关键字索引传递给n.

结点n加入Chord环时,通过调用join(n')函数来实现,节点加入算法伪代码如下:

#define successor finger[1].node

//节点n加入Chord环

n.join(n')

if(n')

init_finger_table(n');

update_other();

else

for i=1 tom

finger[i].node=n;

predecessor=n;

//初始化本地节点的路由表

n.init_finger_table(n')

finger[1].node=n'.find_successor(finger[1].start);

predecessor=successor.predecessor;

successor.predecessor=n;

for i=1 tom-1

if(finger[i+1].start∈[n.finger[i].node])

finger[i+1].node=n.finger[i].node;

else

finger[i+1].node=n'.find_successor(finger[i+1].start);

//更新Chord环中所有那些路由表因该引用n的节点状态

n.update_other()

for i=1 tom

p=find_predecessor(n-2i-1);

p.update_finger_table(n,i);

//如果n是p的路由表的第i项,则用n更新p的路由表

p.update_finger_table(n,i)

if(n∈[p,finger[i].node))

finger[i].node=n;

p=predecessor;

p.update_finger_table(n,i);

当节点n请求退出时,将节点n的路由表移交给的节点n的后继节点来维护.系统中的节点都拥有一张由r个最近的后继节点组成的列表,来保证在节点离开后系统的查询服务仍然得进行[4],并将列表中的第一个节点来替代退出的节点.

2 Chord算法分析

Chord算法具有5个优点:(1)Chord路由算法采用一致性散列算法,所有节点分担相同的系统负荷,避免某些节点负载过大.(2)节点之间地位平等且工作相同,具有很高的顽健性,能够抗御Dos攻击.(3)随着网络节点数量规模的不断扩展,Chord系统的开销将按照O(log(n))的比例不断增加[5].(4)各个节点能够根据网络的动态变化及时更新路由表,有效恢复路由关系,确保各节点之间查询能够可靠进行.(5)由于Chord算法不限定查询内容结构,应用层可以灵活地将内容映射到键值空间[6].

Chord算法虽然有明显的优势,但是它仍然存在不足之处:(1)在Chord系统中,不管各节点之间的性能差异多大,承担的责任都是相同的,例如资源存储、查询等.低性能节点的存在将导致请求响应时间增长,系统性能低下等问题.随着网络的不断扩大,网络节点也随之增多,由于各网络节点之间存着不同的性能差异,系统查询效率因性能较低的节点而受到影响,阻碍系统查找进度,从而引发系统性能瓶颈.(2)在P2P网络中,任何时刻都会有节点的加入或退出,为保证节点路由表的准确性,当有节点加入或退出时都需要及时对相关节点的路由表进行更新.由n个节点组成的Chord系统,当某一节点加入或离开系统时,需要通过O (log 2n)次信息交换来重建节点路由信息及分配相关文件.在系统中,如果节点加入或离开非常频繁的话,整个网络资源将会消耗在节点路由信息更新和文件重定位上,造成系统宽带浪费和查询效率降低.

结合Chord系统,低性能节点带来的系统查询效率低下问题,可通过在系统中添加对各节点之间物理延时的感知,选择最优的下一跳节点,从而减低查找时延,提高算法的查找效率.

3 结论

结合结构化P2P网络特征,将Chord算法与P2P网络综合运用,在详细分析Chord路由算法的基础上,对网络资源的查找及网络节点的加入和退出算法进行概述,并对Chord算法的优势和不足进行分析,提出优化下一跳节点选择方案,降低系统查找时延.

[1]王慧,王铮.基于新路由表的双向搜索Chord路由算法[EB/OL].(2013-04-18)[2013-08-18].http://www.cnki.net/kcms/detail/ 11.2127.TP.20130418.1618.017.htm l.

[2]徐丹阳.基于DHT的结构化P2P路由协议Chord的研究[D].北京:北京邮电大学硕士学位论文,2010.

[3]成培,胡峰松,粟智.基于Chord的结构化P2P路由改进算法[J].计算机工程与设计,2009,30(1):63-65.

[4]宗平,徐鸽.基于DHT的Chord路由算法改进[J].计算机技术与发展,2012,22(9):139-142.

[5]张文,赵子路.P2P网络技术原理与C++开发案例[M].北京:人民邮电出版社,2008.

[6]曹建.基于CHORD环的DHT全分布式P2P网络结构分析[J].苏州市职业大学学报,2012,23(3):42-45.

On the Chord in peer-to-peer network routing algorithm

CHENG Ya-wei,LIU Shu-lun
(Departmentof Information Engineering,Jiyuan Vocational and Technical College, Jiyuan 459000,Henan,China)

With the continuous development of the Internet information technology and computer hardware performance updating,sharing,network information positioning and resource sharing technology based on peerto-peer have been widely concerned.Based on the classification of the peer-to-peer network topology,Chord of structured P2P network routing algorithm is analyzed in detail,and the paper discusses the advantages and disadvantages of Chord algorithm by dealing with the system queries inefficiency problem,to propose to optimize the next hop node option to improve search efficiency of the algorithm.

peer-to-peer network;Chord;routing algorithm

TP393

:A

:1007-5348(2014)06-0016-04

(责任编辑:欧恺)

2014-03-28

河南省科技攻关计划项目(132102210229).

程亚维(1986-),女,回族,河南济源人,济源职业技术学院信息工程系教师,主要从事计算机网络方面的研究.