Chord路由算法的改进与研究

欧阳竟成, 彭邓华, 彭 鑫



Chord路由算法的改进与研究

欧阳竟成, 彭邓华, 彭 鑫

(湖南理工学院信息与通信工程学院, 湖南岳阳 414006)

针对原始Chord路由中查寻效率不高以及表项存在冗余信息的问题, 提出一种改进的Chord路由算法, 利用对立节点建立顺时针与逆时针两个路由表, 实现了双向查寻, 同时改进了路由表构造方法, 减少了冗余表项. 理论分析与仿真实验表明, 该算法降低了查询的平均路径长度, 提高了查寻效率.

P2P网络; Chord; 路由表; 双向查寻

引言

目前, P2P技术已经成为互联网中的重要应用与服务, 如分布式计算、文件交换、协同设计、即时通信等应用系统都集成了P2P技术[1]. 近年来网络流媒体播放系统也普遍地引入了P2P技术[2], 而承载这些应用的重要机制是资源的搜索定位技术.

按网络中节点和资源的关系可以将P2P网络分为两大类, 一类为非结构化P2P网络, 如Kazaa[3]与Gnutella[4]等; 另一类为结构化P2P网络, 如Chord[5]与CAN[6]等. 非结构化P2P网络采用泛洪协议查寻资源, 查寻速度较慢而且消耗大量带宽; 结构化P2P网络则利用分布式哈希表(Distributed Hash Table, DHT)查寻资源, 速度较快但查询召回率较低. Chord协议[5]是美国麻省理工学院于2001年开发的结构化P2P网络协议, 平均查寻路径长度为O(log2()), 其中为网络中的节点数. 为了提高路由效率, 许多学者对Chord算法做了进一步的改进. Ganesan等人提出了一种双向路由Chord算法[7], 基本思想是同时构建当前节点的顺时针和逆时针方向路由表, 双向路由Chord算法的平均查询路径长度可以降低到,为节点标识符的二进制长度(可认为,为网络中节点数), 但它的缺点是路由表空间是原Chord算法的两倍. 文[8]提出了一种基于双向搜索Chord路由算法的NFT-chord, 引入路由因子构造一种新的路由表, 消除了路由表中的绝大部分冗余信息, 并且实现了双向查找, 但是该方法中查寻过程的每步都要试探顺时针方向或逆时针方向, 算法复杂度太高.

本文提出一种改进的Chord双向路由算法, 利用对立节点建立顺时针与逆时针两个路由表, 实现了双向查寻, 同时引入参数减少了路由表中的冗余项目. 理论分析与仿真实验证明, 本文的Chord路由算法可以进一步减少查询的平均路径长度, 提高查寻效率.

1 Chord路由算法

Chord算法是一种基于DHT的分布式查寻算法, 它采用一致性哈希函数将网络中的资源及节点都通过同一函数运算得到各自的标识符ID. 在哈希函数的hash值长度足够长的前提下, 能够充分保证资源及节点的ID不会被重复映射, 于是每个节点和关键字都分配一个位的唯一标识符, 通过将标识符对2取模后顺序排列, 便形成了一个大小为2的圆环, 该环称为Chord环. 每个节点维护一张路由表(finger table), 并且路由表有个表项, 关键字标识符为的资源被分配给Chord环上节点标识符为的节点; 如果该节点不存在, 则该资源被分配给Chord环上节点标识符大于或等于键值ID为的第一个节点, 即顺时针方向距离最近的节点. 存储关键字的节点称为关键字的后继节点, 用Successor()表示. 在Chord环上逆时针方向距离键值最近的节点称为前继节点, 用Predecessor() 表示. Chord算法中节点的唯一标识符记为, 其路由表的第项为:

Chord算法中节点N1的路由表(finger table)模型如图1所示.

从图1可以看出, Chord的路由查询过程为: 如果节点N1要查找关键字50, 它发现关键字50没有存储在本地, 节点N1查找自己的路由表得到关键字50的最大后继节点为N38, 节点N1将查询请求转发给节点N38, 如果本地有该关键字就立即响应请求节点, 查寻结束, 但是关键字50没有存储在本地, 节点N38检查自己的路由表, 将查询请求转发给节点N48, 如此反复, 直到路由至关键字50的后继节点N51, 查询结束. 查寻请求共需要经历3次转发才能找到结果, 查询效率不高, 并且路由表中存在冗余信息.

2改进的Chord路由算法

2.1 路由表构造

假定Chord环标识符空间大小为2, 定义的范围为, 网络节点数. 一般情况下有, 即实际节点数远小于标识空间大小, 同时一致性哈希算法(如SHA-1)的性质能够确保所有节点几乎均匀分布于chord环空间. 若按照初始Chord路由方案, 必然会导致每个节点的路由表冗长, 并且前半部分呈现几个路由项指向同一节点的现象, 从而降低了查寻速度, 文[9]对这种现象进行了详细分析. 本文提出顺时针方向半环与逆时针方向半环双重路由表的构造方案. 首先选择正向的最后一项标识符为对应的节点作为对立节点, 从逻辑上将Chord环临时分成两个半环, 实现双向查寻, 在查寻的第一步就能够确定目标节点在Chord环的前半部分还是后半部分, 缩小查寻范围, 提高查寻速度. 该方法第一步就是确定对立节点, 用表示, 计算公式为

为了使路由表从第一项开始尽量降低冗余信息并且基本上确保路由表项节点的均匀分布, 仿照文[9]的方法, 引入一个参数. 当时,, 其中, 即相邻两节点在Chord标识空间上的平均距离. 取为, 因此, 构造顺时针的路由表公式为

同理, 构造逆时针的路由表公式为

(4)

例如,= 6, 节点数为10个, 23<10, 则取值为4, 计算得, 利用上述公式可得改进后的路由表模型如图2所示.

2.2 查询过程

假定当前节点为当前, 其对立节点为, 查寻请求被哈希函数映射后的关键字为, 查找过程如下:

(1)当前收到查寻关键字, 判断是否存储在本地, 如果是, 则直接响应查寻请求节点, 查询结束; 否则, 继续执行.

(2) 判断与的大小, 若, 转(3); 否则, 判断是否属于(当前, Successor(当前)) , 如果是, 那么Successor(当前)即为目标节点, 将查询请求转发给Successor(当前), 返回(1); 否则, 查找Chord环的顺时针路由表, 找到小于的最大键值ID所对应的节点Node1, 将查询请求转发给Node1, 返回(1).

(3) 判断是否属于(当前, Predecessor(当前)) , 如果是, 那么Predecessor(当前)即为所求的节点, 将查询请求转发给Predecessor(当前), 返回(1); 否则, 查找Chord环的逆时针路由表, 找到大于的最小键值ID所对应的节点Node2, 将查询请求转发给Node2, 返回(1).

从图2新构造的路由表可以看出, 节点1要查找关键字50时, 关键字不在本地, 于是它第一步就确定了从逆时针路由表查找, 定位到节点N51, 将查寻请求转发给节点N51, 关键字50就存储在节点N51上, 因此, 只需要一次查寻转发(即一跳)就可以找到资源, 减少了查找跳数, 从而提高了搜索效率.

3算法性能分析与仿真实验

3.1 算法性能分析

新构建的路由算法有效减少了查寻的平均路径长度. 初始Chord模型中, 若网络中有2个节点, 查询的平均查找路径长度为, 由文[5]的分析可知

设改进后的Chord路由平均路径长度为, 前半环的路径长度为1, 后半环的长度为2, 而前半环的查询性能与初始Chord相一致, 所以前半环的查询路径长度为

(6)

后半环路由表的构造与前半环的一样, 而原来的路由表没有覆盖后半环的路由信息, 因此可得后半环的平均查找路径长度为

由于查寻关键字落在前半环或后半环的概率均为1/2, 因此得出改进后的Chord路由查寻平均路径长度为

(8)

假设为12, 可计算出初始Chord模型的平均查找路径长度约为1.8, 改进后的Chord算法的平均路径长度约为1.29, 可见平均查寻路径长度降低了, 查寻效率提高了.

同时, 改进的Chord路由表构造方案基本上消除了原路由表中的冗余项. 在大小为2的Chord环上, 网络的实际节点数为2(), 且所有节点均匀分布在Chord环的网络中, 由此可以得出任意两个相邻节点之间的间距为. 如果, 即, 则路由表中存在冗余信息, 并且在路由表中越靠前的表项中相邻节点之间的逻辑距离越小, 就越容易出现信息冗余的情况, 但是, 当时, 路由表中出现冗余的概率小到可忽略不计. 假设当前节点为, 利用Chord算法构造的路由表表项节点依次为+1,+2,+4,+8,…, 如果与的后继节点在Chord环上相差的逻辑距离大于2, 路由表的第一项和第二项所对应的节点就是相同的, 就出现信息冗余. 而对改进后的Chord算法新构造的路由表公式中加入参数, 得到的路由表项节点依次为观察公式可以看出, 不论顺时针还是逆时针, 从第一项开始节点间的逻辑距离便大于等于, 在节点均匀分布的Chord网络中很难出现路由表项信息冗余的情况.

3.2 仿真实验

使用PeerSim[10]平台, 再加入我们自己编写的代码, 实现本文的仿真实验. PeerSim是一个基于JAVA语言的源代码开放的P2P仿真平台, 其中包含了许多P2P组件, 用户通过制作一个配置文件来调用若干组件完成仿真任务. 该软件包中已经提供初始Chord协议, 我们只需要编写改进的Chord协议. 在实验环境中设置若干共享文件作为网络资源, 即假设一个理想的文件共享网络, 任意节点可以访问到它需要的任意文件; 并且能够从拥有该资源的节点下载文件, 实验基于周期仿真. 仿真环境的具体配置见表1.

实验中设置= 18, 即Chord网络标识符空间大小为, 节点数取值从1000~10000, 在某一规模的网络中, 节点随机访问文件并且进行下载, 重复10个周期, 统计P2P覆盖网的平均查找路径长度, 数据如图3所示.

从图3可以看出, 改进后的Chord路由算法比初始的Chord在查寻路径长度上有较大减少, 与理论分析相符.

4结束语

本文针对Chord路由表中存在冗余信息与算法查寻效率不高等问题, 提出了一种改进的Chord路由算法. 每个节点利用对立节点建立了顺时针与逆时针两个路由表, 以便在查寻资源的第一步就能够确定目标节点在Chord环的前半部分还是后半部分, 缩小了查寻范围, 实现了双向查寻, 同时引入参数减少了路由表中的冗余信息. 理论分析与仿真实验表明改进后的Chord路由算法平均查寻路径长度相对于初始Chord路由算法有较大的减少. 但是, 本文没有考虑物理网络中节点的加入与离开时覆盖网的通信开销与维护代价, 这是进一步研究中要解决的问题.

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

[2] 张明军, 彭 娅, 俞文静. P2P流媒体服务方案及其关键技术研究[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]. 计算机工程与应用, 2014, 50(23): 95~99

[9] 祁 玉, 张新有. chord 路由表结构的分析与改进[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

湖南省科技计划项目(2016TP1021); 湖南理工学院学位与研究生教育教改项目(YJG2017A004); 湖南省研究生科研创新项目(CX2016B671)

欧阳竟成(1967− ), 男, 湖南平江人, 博士, 湖南理工学院信息与通信工程学院副教授. 主要研究方向: 对等网络, 信息检索与信息安全