一种基于P2PSIP的双向四阶Chord模型研究

刘龙蛟, 黎忠文, 王　强

(1.西华大学 计算机与软件工程学院， 四川 成都　610039；

2.成都大学 信息科学与工程学院， 四川 成都　610106； 3.西华大学 理学院， 四川 成都　610039)



一种基于P2PSIP的双向四阶Chord模型研究

刘龙蛟1, 黎忠文2, 王强3

(1.西华大学 计算机与软件工程学院， 四川 成都610039；

2.成都大学 信息科学与工程学院， 四川 成都610106； 3.西华大学 理学院， 四川 成都610039)

摘要：基于SIP和P2P系统存在的不足以及P2PSIP系统所具有的优势，设计了分布式SIP信令控制协议和P2P网络相互独立的层次化P2PSIP通讯系统.在P2P网络下，对双向查询算法与四阶Chord算法进行了定量分析，在此基础上提出了双向四阶Chord模型，该模型使路由表的密度增加到了3Log44k，并用向量数组的概念对双向查询算法进行了成功的推导.模拟实验表明，以此减少路由指针转发次数，使其能够更快的指向目标节点.通过此分布式的SIP信令控制，可以大大提高P2PSIP系统的实效性.

关键词：分布式；P2PSIP；双向四阶；Chord；信令

0引言

近年来，随着计算机通信技术及因特网的迅猛发展，人们对通信业务的综合需求不断提高，需要构建一个能将语音、视频、数据等多种业务融合为一体的网络.目前，因特网工程任务组(IETF)、国际电信联盟电信标准化组织(ITU-T)已经制定并且完善了一系列标准协议，如会话初始协议[1](SIP)作为下一代网络(Next Generation Network,NGN)的核心协议，为用户提供了丰富多彩的业务.

SIP协议是建立、修改和终止一个或者多个参加者之间多媒体会话的应用层控制协议，其最初是由IETF的多媒体会话控制(MMUSIC)工作组在1999年提出的一个标准RFC2543.经过多年的研究和发展，又有许多RFC文档和草案作为核心协议的补充[2-3].由于SIP网络仍采用集中式的C/S(客户/服务器)通信模式，其应用在迅速增长的同时，也暴露出了一些缺点，如性能瓶颈、不易扩展、单点失效、抗毁性不足及自组性等.研究表明，分布式P2P网络就是解决以上问题最好的一种选择[4].P2P技术是近年来快速发展的一种分布式计算技术，其基本思路就是网络中不存在中心服务器.一个典型的P2P网络包括了Chord、Pastry、CAN、Kademlia等拓扑结构.为了能在P2P网络中精确快速地定位目的节点，通常采用经典的Chord网络.近年来，科研人员对Chord网络进行了定性研究[6-7]，同时，针对独立网络存在的不足，对P2PSIP网络进行了研究，并取得了一定的成果[8-9].

目前，构建基于P2P的SIP系统框架(P2PSIP)主要有2种方式：第一种对SIP协议进行扩展，用SIP信令来建立和维护P2P覆盖网络，即P2P-over-SIP[10]，将SIP和P2P完全融合在一起，并且放弃了P2P网络所使用的私有协议.对SIP协议进行扩展并修改P2P协议增加了协议的复杂度，并且无法重用已有的SIP与P2P模块，在系统规模较大的P2P-Chord网络中，必将产生大量的控制信息.而SIP相对于P2P被称为“重型"协议，是基于文本编码的协议，在此方案下势必会占用很大的网络带宽.第二种以分布式P2P覆盖网络中的节点来替代SIP的中心服务器，即SIP-using-P2P[11]，该方案属于真正的分布式无中心服务器网络，将节点呼叫建立过程和节点的信息维护相分离，使用P2P信息来维护P2P覆盖网络.从结构上分析，SIP协议层和P2P协议层是完全分离的，二者可以单独实现，互不影响，只通过接口API进行交互，并且这种模型还允许在P2P上使用SIP之外的协议.本研究是在第二种方案的基础上进行的，并且将节点分为超级节点(SN)和普通节点(ON).

1P2PSIP系统设计

在传统的SIP系统中，SIP实体发起呼叫时需要首先实现目的节点和用户的定位，此功能由SIP服务器实现.本研究将P2P网络模块与SIP模块结合为相互独立层次化的P2PSIP结构网络.而在P2PSIP系统中，由P2P分布式网络的超级节点构建一个P2P覆盖网络，每个超级节点能实现客户端与服务器的两重功能.将集中式SIP通信系统中中央服务器的功能，动态分布到带了P2PSIP系统的各个超级节点上，基于分布式P2P网络优良的资源定位服务，将其与SIP结合是最理想的选择.同时，本研究利用P2P-Chord模块采用DHT方式构建系统，系统架构如图1所示.

图1P2PSIP系统设计模块图

整个P2PSIP系统设置分为基础设备层、核心模块层与应用控制层.

1.1基础设备层

基础设备层主要为上层应用提供一些基础的功能设施，与系统的具体应用无关，可以另外用于其他的应用程序之中.这些模块主要包括：网络I/O、内存I/O、文件I/O及INI配置文件读写等.此类模块均具备跨平台操作的特性，以提高系统的可移植性.

1.2核心模块层

核心模块层建立在基础设备层之上，是实现本系统最主要的功能模块，包括P2P模块、SIP信令控制模块及多媒体流处理模块.

1.2.1P2P-Chord模块.

P2P的应用层路由网络作为其信令控制的Overlay(覆盖)网络.采用双向四阶Chord模型，节点分为超级节点(SN)和普通节点(ON).超级节点之间组成一个基于DHT的P2P网络，普通节点仅仅是用户代理，以此来实现P2P网络的分布式覆盖与维护接口，包括节点加入、节点离开及资源搜索等，从而为P2PSIP系统提供资源信息的分布式存储与定位.

1.2.2SIP信令控制模块.

SIP通信信令的控制以SIP协议栈为基础来实现.控制接口主要包括客户的注册与认证、呼叫控制、DNS定位及SDP媒体协商等.SIP以其简单、灵活的特性为P2PSIP系统提供呼叫信令控制功能.

1.3应用控制层

应用控制层在以上2大功能模块的基础上实现了一个完整的通信系统.利用P2P-Chord模块实现节点的定位与注册.利用分布式SIP信令控制协议实现用户的呼叫建立过程，实现多媒体流传输的实效性.

2双向四阶Chord模型

2.1双向二阶和双向三阶Chord算法

针对目前P2P网络中多媒体应用的时效性要求，为了提高系统的整体性能，本研究从P2P-Chord模块入手，首先对Chord的查询过程进行定性的观察分析.

1)通过哈希函数如SHA-1给每个节点与资源关键字分配m位的标识值.以2 m,3 m为模.节点标识值在Chord环上按顺时针方向从小到大排列.资源标识值k被分配到节点标识值等于k或者紧随k的首个节点上.

2)对需要查询的资源关键字k求hash(k)，得到资源标识值.

3)比较hash(k)与本节点的finger table是否存在目的节点.如果是，则直接查找.

4)如果不是，在本节点的finger table中找到最接近目的节点的合适节点地址.

5)把查询转发给该节点，继续上述3)、4)步骤，直到完成.

在Chord查询过程中，“2)”～“4)”步均是在本节点上完成的，时间复杂度为恒定值，对于现在的设备来说这些开销微不足道.而第“5)”步涉及到信息的转发.目前，P2P网络中的节点分布于全球各地，节点之间的数据延迟非常大，节点间的转发延迟就是通讯系统中Chord的最大性能瓶颈.因网络带宽匮乏的状况是无法改变的现实，所以要通过减少节点延迟以提高系统性能.

2.2四阶Chord算法

提高通讯系统中Chord路由性能的关键在于减少转发次数.对此，本研究提出一种四阶Chord算法使路由表的指针更加密集，能够更快速定位到目标节点.四阶Chord路由表结构如表1所示.

表1　四阶Chord路由表

在表1中，每个序号表示了路由表中的三项.这样每个节点所维护的存储空间复杂度由传统Chord中的O(Log2N)与O(Log3N)增加到了O(3Log4N)，并且四阶Chord保证了目的节点定位的时间复杂度为O(Log4N).

2.3双向Chord

为了提高查找效率，本研究使用双向查找算法，并且定义另外一张逆时针方向的路由表，即Anti finger表.这样每次在某个节点上检索下一跳路由时，就可以同时从顺时针和逆时针2个方向进行查找，这使得每一次进行路由选择时，可以选择出一条性能相对优良的路径.双向路由表中一个节点的全部路由表的定义如表2所示.

表2　双向finger表结构

(1)

向量的求模运算定义如下，

(2)

(3)

向量的模运算表示2个节点间的逻辑距离，可以理解为从一个节点到另一个节点所要经过的跳数.

2.4双向四阶Chord算法

在传统的Chord算法中，存在着查找跳数过多，效率低的性能瓶颈.因此，本研究进一步改进Chord的双向查找算法，并把Chord算法的路由表改为四阶，算法的具体步骤为：

1)如果关键字k存储于本节点，则返回本节点地址，查询成功.

2)沿着顺时针方向查询，如果k位于Q的hash值和Q.successor的hash值之间，即当Q

3)沿着逆时针方向查询，如果关键字k介于Q节点的hash值与Q节点沿逆时针方向的前驱节点的hash值之间,即Q.Antifinger[1].node≤k≤Q时，则查询方向为逆时针.查找成功，返回本地节点.否则转下一步.

4)查询关键字的hash值为k,从finger表中获得不同的2个节点Q1与Q2，在finger表中Q2位于Q1之后.Q1满足，

(4)

从Anti finger表中获得不同的2个节点Q3与Q4，在路由表中Q4位于Q3之后.且Q3满足，

(5)

定义向量数组，

(6)

向量的方向数组，

Dir=[1,0,0,1]

(7)

方向数组表示节点Q与关键字k的方位关系.Dir[i]=1时，表示k在Q节点的顺时针方向.Dir[i]=0时表示k在Q节点的逆时针方向.

查询数组B中的最小元素，如果B[i]是数组的最小元素，则Q[i]为其下一跳的路由节点.若Dir[i]=1,则下一跳的查询方向为顺时针方向，否则，下一跳查询方向为逆时针方向.之后转(1)直到查询到目的节点.

如图2所示，N2节点在表3中用双向四阶Chord算法查询定位资源关键字k=47的目的节点的过程为：

N2分析自身的路由表，fingertable找到N37、N59节点，Antifingertable找到N56、N45节点.其中，N45距离k=47最近，把查询信息转给N45,并且查询方向为顺时针.N45节点查询自己的路由表，发现k=47位于本节点与本节点的后继N52之间,因此，其把查询信息转发给N52，发现k=47存储于本地，查询成功.查找过程总共转发2次.

图2　双向四阶Chord查找过程

3P2PSIP系统的工作流程

本研究的系统架构中包含2种角色的节点：普通节点(ON)和超级节点(SN)，根据能力的不同，将不同的节点进行区分，不同能力的节点被赋予不同的任务.超级节点构成Chord环，普通节点仅仅只是连接到这些超级节点，充当用户端.任何节点根据它们的性能高低，既可以成为超级结点也可以成为普通节点.决定其成为超级节点或者普通节点均实现于本地区域内.

在P2PSIP网络结构中，普通节点并不能担当SIP服务器的角色，要加入P2PSIP网络必须向超级节点进行注册.任何节点之间若需要进行会话通讯，则首先必须完成用户节点的定位.而通过本研究所提出的双向四阶Chord算法进行定位，提高了通讯目的节点的查询定位效率，缩短了通信延迟.同时，为了提高网络的健壮性和可拓展性，P2PSIP分布式网络具有超级节点(SN)的自动加入或离开的功能.

4实验仿真

通过分析P2PSIP系统网络的特点与实际需求，在仿真实验中，本研究对分布式DHT建立每个节点的路由表，均采用NS2分析软件[12]对双向二阶Chord算法、双向三阶算法以及双向四阶算法进行模拟仿真， 并对大量数据进行分析， 比较3种算法各自的优缺点.

4.1平均查找路径长度

查找路径长度是指对某个资源关键字k进行查询时所经过的节点数，即跳数.双向二阶、双向三阶及双向四阶Chord算法的路径跳数的仿真实验如图3所示.

图3平均路径长度比较

实验结果表明，随着节点数的增加，3种算法的平均路径跳数均有所增加，双向四阶Chord算法的平均查找路径，较之原来2种算法的增长趋势更为平稳、更加缓慢.这表明双向四阶Chord算法在查询目标节点时所经过的跳数比原来2种算法要小，对查询效率有很大的提高.

4.2平均查找延时

平均查找延时是指定位平均网络目标节点时所需要的时间.双向二阶、双向三阶及双向四阶Chord算法在平均查找时延上的差异如图4所示.

图4平均查找延时

实验结果表明，随着节点数目的增加，3种算法的查找时延均有所增长，但双向四阶Chord算法比传统的2种算法在查找时延上均有很大的降低.

5结语

本研究所提出的P2PSIP系统在信令控制和媒体流传输两个方面均采用应用层P2P分布式覆盖网络，网络的自组织性、抗毁性及高扩展性等性能较高.在P2P-Chord网络中，双向四阶Chord算法在减少查找延时和查找路径两方面都有很大的提高.由于Chord阶数的升高所导致路由表的增长所带来的开销，但就目前计算机系统的现状及基于本研究所做的实验验证表明，这样的开销是可以被忽略的.

参考文献:

[1]穆栋.P2P-SIP通信系统研究与设计[D].西安:西安电子科技大学,2011.

[2]RosenbergJ,SshulzrinneH.RFC3262,Reliability of provisional responses in the session initiation protocol[S].USA:theInternetSociety,2002.

[3]ArkkoJ,TorvinenV,CamarilloG.RFC3329,Security mechanism agreement for the session initiation protocol[S].USA：theInternetSociety,2003.

[4]RosenbergJ,SshulzrinneH.RFC3263,Session initiation prowcol:Locaxing SIP[S].USA:theInternetSociety,2002.

[5]罗文杰.PeertoPeer综述[M].北京:中科院计算机技术研究所,2008.

[6]汪发宝.P2P网络Chord协议的分析与研究[D].成都:西南交通大学,2010.

[7]温忠志.高阶Chord:一种新型P2P查找策略[D].成都:四川大学，2005.

[8]王方金.SIP-P2P通信网络研究与设计[D].广州:中山大学,2010.

[9]陈世峰.基于P2P-SIP融合技术的VOIP系统设计研究[D].厦门:厦门大学,2009.

[10]白羽,洪飞.基于P2PSIP协议的即时通信系统[J].计算机系统应用,2009,19(2):14-17.

[11]李女原源.基于SIP的P2P工作模式研究[J].微电子学,2010,40(6):865-869.

[12]徐雷鸣，庞博，赵耀.NS与网络模拟[M].北京：人民邮电出版社，2003.

Two-way Fourth-order Chord Model Based on P2PSIP

LIULongjiao1,LIZhongwen2,WANGQiang3

(1.School of Computer and Software Engineering, Xihua University, Chengdu 610039, China;2.School of Information Science and Engineering, Chengdu university, Chengdu 610106, China;3.School of Science, Xihua University, Chengdu 610039, China)

Abstract:Based on the deficiency of SIP and P2P system and the advantages of P2PSIP system,the paper designs a hierarchical P2PSIP communication system with a distributed SIP signaling control protocol and P2P network which are independent of each other.Under the P2P network,quantitative analysis is done on the bidirectional query algorithm and four-order Chord algorithm.On this basis,the paper proposes that the bidirectional fourth-order Chord model.The model makes the density of the routing table increase to 3Log44k.Meanwhile,based on vector array,the bidirectional query algorithm is derived successfully.Simulation results show that,the model can reduce routing pointer forwarding frequency and make it point faster to the target node.Through this distributed SIP signaling control,the effectiveness of P2PSIP system is enhanced greatly.

Key words:distributed;P2PSIP;two-way fourth-order;Chord;signaling

中图分类号：TP393.02

文献标志码：A

作者简介：刘龙蛟(1985 — )， 男， 硕士研究生， 从事无线网络通信技术研究.

基金项目：四川省科技厅科技支撑计划(2014SZ0107、 2015GZ0333)资助项目.

收稿日期：2016-01-05.

文章编号：1004-5422(2016)01-0053-05