周永福曾志

(1.河源职业技术学院 电信学院,广东河源 517000;2.惠州学院 计算机科学系,广东惠州 516007)

一种采用多层拓扑感知的移动P2P网络路由模型设计

周永福1曾志2

(1.河源职业技术学院 电信学院,广东河源 517000;2.惠州学院 计算机科学系,广东惠州 516007)

为解决媒体信息的实时传递，在分析已有P2P网络Chord模型算法的基础上，介绍了通过拓扑感知思想采用NAT节点作为子网节点管理的方法改进多层网络结构Chord模型，针对结构化P2P网络比较关心的节点加入、退出与维护算法提出了多层拓扑感知Chord模型，并将其应用于P2P网络多媒体即时通讯系统中，通过系统实现与仿真实验验证了该路由协议的有效性和高效性。

网络地址翻译；P2P点对点；多层拓扑感知；路由协议

随着计算机网络技术、通信技术和多媒体技术的快速发展与融合,人们对于多媒体信息的需求日趋复杂和多样,各种基于网络的新媒体应用形式应运而生。网络即时通信,由最初发送和接受文本信息发展到语音、视频等多媒体时代。P2P网络即时通信系统具有负载均衡、可扩展性强、系统鲁棒性好等特点,逐渐成为应用研究的主流[1]。然而,网络中节点之间直接连接的成功率和通信质量有时难以满足用户的需要。其中一个重要原因是P2P网络在实现应用层覆盖网络时对通信节点的异构性、动态性和网络层拓扑结构的考虑不足,从而大大降低了节点之间的连通性。

Chord具有负载均衡、可扩展性强的特点,是结构化P2P网络中经典的路由模型[2]。然而,Chord模型也存在绕路问题、路由瓶颈和路由表信息冗余严重等问题。目前主要有两种方法来解决结构化P2P系统的拓扑不匹配。文献[3-4]提出将节点分组并选取超级节点管理组内节点信息,从而提高系统路由效率。但当超节点的失效时,容易影响其它节点正常工作,引起额外系统开销,系统稳定性差。文献[5]提出建立系统全局信息图的方法。该方法的一个不足在于:系统中的每个节点的信息被多处保存,而且每个节点必须维护很多的信息,从而不利于系统的扩展。另外,有些文献[6]提出可以利用小世界网络提高路由效率。

已有算法在拓扑匹配的效果上不够理想,算法带来的额外开销较大,这些不足限制了拓扑匹配的效果和实用性。通过对P2P网络进行结构划分,运用拓扑感知原理优化Chord网络模型,提出了多层拓扑感知Chord模型(Multilayer Topology-Aware Chord,MTA-Chord)并应用于P2P网络多媒体即时通信,从而达到提高系统路由性能的目的。

1 Chord网络改进模型

1.1 Chord模型基本算法

Chord模型路由算法基于分布式散列表(DHT)思想实现。每个节点和资源都有一个m bit的标识符,标识符的范围在[0,2m-1],标识符形成一个一维的对2m取模的标识符环。节点的标识符ID是对节点的IP和其他一些状态信息的散列结果。资源标识符是对资源内容散列的结果,称为资源关键字K。在标识符大小顺时针增长的标识符环上,节点负责逆时针方向到上一个节点之间的所有关键字。在标识符环上某节点逆时针上一个节点称为该节点直接前驱,顺时针方向下一个节点为该节点的直接后续,表示为successor(n)。每个节点都会保持一个前驱指针和后续指针,如图1所示。

表1 Chord结点Finger Table定义

图1 结点N8的Finger Table表结点指向图

Chord网络中每个节点维护一个被称为指针表(finger table)的路由信息表,如图1所示。网络通过指针表进行路由,定位到负责特定资源关键字的节点。指针表里记录的是标识符环上其他节点的地址(IP地址、端口、ID等),按照以下的规则记录,m bit的标识符长度对应的指针表的项数最多也是m项,在节点n的指针表中,第i行记录着标识符n后至少2i-1远的第一个节点的地址,即successor(n+ 2i-1),其中0≤i≤m-1。当节点收到资源查询包时,节点首先判断该资源是否就在本节点,如果是直接返回资源给查询的发起节点;如果不是,通过比较资源关键字k和指针表中目的ID的大小,在指针表中寻找目的ID小于关键字而又最接近关键字K的项,将查询包转发给该项中的后续节点,也就是关键字K的在指针表中最近先驱节点。对于N个节点参与的Chord网络,平均的路由跳为O(log2N),平均查找需要1/2 log2N步[7]。

1.2 改进的多层拓扑感知Chord模型

MTA-Chord模型利用网络坐标测定和网络节点NAT层次结构探知对Chord模型进行优化[8-10],使覆盖网Chord模型能“感知”链路层网络拓扑,从而提高路由效率。基本思想是:将Chord节点标识符分成前缀和后缀两部分,公网节点利用树标识前缀构成Chord环,在公网节点间利用Chord路由的方式进行路由查找和维护,处于同一NAT下的节点构成一个NAT节点树,由一个公网节点充当树根节点维护节点树的所有节点信息,树内节点和对应树根节点共享树标识符前缀,并依据加入网络的时间顺序依次分配树内ID,通过树根节点进行资源查找。

处于同一子网下的节点前缀相同,前缀通过每个子网选取的一个网络距离临近的节点的坐标一维化生成,使节点的标识符既能反映子网的情况,又能反映节点间网络距离,从而提高Chord路由效率和点对点通信成功率。

由于只在公网节点中维持Chord环,当对资源ID前缀进行路由查找确定资源应该存放的节点时,该节点判断自身如果是普通节点的话,则保存资源;如果是树根节点时,则根据资源的树内ID确定整个ID的直接后续,将资源存放到直接后续上。通过树内节点存储相应资源可以减轻树根节点的存储负担。MTA-Chord协议的覆盖网拓扑图如图2所示。从图中可以看到,NAT树内节点n1、n2、n3与邻近公网节点N35共享标识符前缀,并由N35维护资源,N50负责NAT树内节点n4、n5,距离较近的公网节点之间标识符前缀相对接近。

图2 MTA-Chord协议的覆盖网示意图

2 移动P2P网络多媒体即时通讯路由模型

在移动P2P网络中,衡量数据的传递的效率通常有节点的跳数决定。下面分别以多层拓扑感知技术针对结构化Chord网络,从侧面研究反映P2P网络性能的节点查询、加入与退出等算法入手,研究P2P网络即时通讯路由模型。

2.1 路由表结构

MTA-Chord模型所有节点分为两种公网节点和NAT树内节点。公网节点保存原Chord系统中的Finger表,用结构〈keyID,nodeID,successor,IP〉表示,需要注意的是,Chord环中仅使用标识符前缀参与运算,路由查找算法与经典Chord模型相同。公网节点负责的NAT子节点通过维护一张NATnode表进行管理。NATnode表的结构为〈keyID,node ID,rootNodeIP,IP〉,若该节点无需要管理的树节点, NATnode表可为空,多层NAT子网结构也可在NATnode表中很好体现。

2.2 路由查找算法

为实现系统中任意用户间的通信,路由查找的目的是找到记录着通信用户所在节点信息的资源。算法1为用户S发起向用户T的通信的路由查找算法。

算法1

输入:用户T的资源ID散列后生成的关键字KT,用户S发起查询的节点NS。

输出:用户T所在的位置信息资源RT。

begin

(1)判断关键字KT前缀是否与查询发起节点NS前缀相同,是则说明查询发起节点与目标资源所在节点NT相同,转到(3),否则转到(2);

(2)通过关键字KT前缀,按照Chord路由算法进行路由查找,经若干次转发后找到用户T资源所在节点NT;

(3)解析关键字KT后缀,判断资源是否由节点NT直接负责,是则直接回复资源,否则通过NT的NATnode表查找KT后缀资源位置;

(4)end.

路由协议查询资源的整个过程如图3。

2.3 节点加入算法

MTA-Chord模型基于节点网络坐标构建公网Chord环,从而优化路由性能。网络坐标通过节点与路标节点(landmark node)间的往返时延(RTT)计算。节点坐标采用GNP全局网络定位系统计算。首先选取n个节点l1,l2…,ln作为路标节点,探测节点间的往返时延RTT,构成n×n的往返时延矩阵:

图3 MTA-Chord协议查询资源流程图

Rn其中rij表示路标节点i与路标节点j间的RTT。

通过最小化整体误差,利用Simplex Downhill算法求近似解,获得路标节点坐标。当用户S通过节点nS登录系统时,算法2为节点加入算法。

算法2

输入:用户S登录系统节点nS的地址信息。

输出:更新MTA-Chord环路由表。

begin

(1)nS进行NAT判断,确定节点是否在NAT后,如果是,转到(2),如果否,说明nS本身就是公网节点,nS=NS,转到(3);

(2)找到nS的树根节点NS;

(3)判断NS是否已经存在于公网Chord环中,如果是,转到(5),如果否,转到(4);

(4)节点NS根据和路标节点的时延数据进行二维坐标的计算,再使用空间填充曲线算法将二维坐标转化成一维数据,作为节点的树标识前缀,形成节点ID,生成节点ID后,执行基本Chord算法的加入操作,建立节点指针表、前驱指针、后续列表,通知相关节点修改finger表;

(5)如果nS=NS,转到(6),否则,查询NATnode表,为nS分配标识符后缀,将nS的地址信息和标识符加入到NS的NATnode表中,转到(6);

(6)end.

2.4 节点维护和退出算法

当节点失效时,可视为节点已退出网络,可采用与节点主动退出网络类似的维护机制。节点退出见算法3。

算法3

输入:要求退出系统的节点nE的地址信息。

输出:更新MTA-Chord环相关节点路由表。

begin

(1)判断节点nE的类型,如果是叶子节点,直接通知根节点NE,注销NATnode表中相关信息,转到(4),如果是父节点而非根节点,转到2,如果是树根节点(公网节点)转到3;

(2)通知树根节点为nE的子节点重新寻找父节点,并更新NATnode表;

(3)寻找最近的公网节点Nnear接管节点的NAT信息,执行基本Chord算法的退出操作,释放finger表,通知相关节点修改指针表;

(4)end.

3 系统实现和实验仿真

3.1 系统实现

为验证MTA-Chord模型在移动P2P网络的可行性,系统实现采用Eclipse、android 4.0平台开发完成。其中MTA-Chord模型实现的即时通信系统由注册服务器和移动终端两部分组成。嵌入式移动终端、固定终端都是使用通信功能的主机,注册服务器用于用户信息注册和维护、全网络NAT信息的维护。在系统中,部分终端充当路标节点,普通终端在路标节点协助下加入网络。普通主机之间基于DHT协议发送路由消息,并根据NAT环境实现点对点的通信。系统组成如图4所示。

图4 系统结构图

3.2 实验仿真

为了验证MTA-Chord模型的有效性,在.net环境下用C#编写了模拟仿真程序,仿真的重点包括“模型”和“实验”两个方面。实验环境模拟的网络模型共有90个节点,其中主机终端80台,公网节点25个,子网数量20个。

在已设置好的网络模型上采用RIP协议进行网络层仿真。为了简化仿真过程,仿真主机加入、退出网络和主机故障的过程,假设Chord覆盖网处于稳定状态。在相同环境下进行查找效率的比较。

由于实验设定的网络模型中一共有80个终端节点,Chord模型标识符长度设置为7,标识符范围[0,27-1]。模拟结果显示,覆盖网跳数0-6,由于跳数6的数据较少,在此不列入统计范围。对每个覆盖网络跳数对应的网络层跳数取平均数,得到表2与表3的仿真结果。

表2 传统Chord协议的仿真数据

表3 MTA-Chord协议的仿真数据

经对比可发现,改进后的改进后的MTA-Chord模型对应网络层跳数比经典Chord模型小,随着覆盖网路由跳数的增多,减小的幅度越来越大,这得益于拓扑感知对Chord环的优化作用。实践表明,模型应用于P2P网络即时通讯系统,网络规模足够大后,改进效果更加明显。

考虑到节点失效对路由效率的影响,模拟在不同网络规模下存在一定节点失效率的路由查找情况,记录网络中路由查找失效率。节点失效率假定为2%,网络中公网节点数与总节点数的比率记为网络伸缩比s,实验分别仿真MTA-Chord模型网络伸缩比s=0.8和s=0.6的情况,并将传统Chord模型仿真结果与MTA-Chord模型实验结果进行比较,结果如图5所示。

图5 节点失效对路由查找失效影响实验

从实验结果看,随着网络伸缩比s减小,查找失效率呈下降趋势,主要原因是由于公网Chord环缩小,平均路由跳数下降,路由失效风险降低。同时可以发现,网络伸缩比s减小时,路由失效率波动增大,稳定性变弱,主要是由于公网树根节点承担的任务变重,增加了整个P2P网络不确定性。

4 结语

文中针对现有P2P网络即时通讯系统路由模型存在的不足,阐述了拓扑感知方法改进Chord模型的具体思路,提出了基于拓扑感知Chord模型的P2P网络即时通讯系统路由模型设计方案。最后,对路由模型方案进行了实验仿真,证明了该方案的有效性和可行性。

[1] 范冶宇.基于WEB的移动P2P即时通讯系统的设计与实现[D].吉林:吉林大学,2011.

[2] Hu Ying-song,Guo Shou-lie.An Extended Algorithm for Hierarchical Low-Latency Chord Protocols[J].Computer Engineering&Science, 2007,99(4):74-77.

[3] 郭松梅.基于网络拓扑和节点异构的Chord系统[J].计算机科学,2009,36(3):90-92.

[4] 曾晓云.基于Chord协议的混合P2P模型[J].计算机工程,2010,36(7):112-115.

[5] Xu Z,Tang C,Zhang Z.Building topology-aware overlays using global soft-state[C]//Proceedings of the23rd int’1 Conf on Distributed Computing System(ICDCS 2003).New York:IEEE Press,2003:500-508.

[6] Xiao W J,He M X,Liang H M.CayleyCCC:a robust P2P overlay network with simple routing and small-world features[J].Journal of Networks,2011,6(9):1247-1253.

[7] Stoica I,Morris R,Karger D,et al.Chord:A Scalable Peer-to-peer lookup service for Internet applications[C]//Proc of ACM SIGCOMM’01.San Deigo:[s.n.],2001:149-160.

[8] 王必晴.Chord路由算法的研究与改进[J].计算机工程与应用,2010,46(14):112-115.

[9] Ratnasamy S,Handley M,Karp R,et al.Topologically-aware overlay construction and server selection[C].New York:In proceeding of IEEE INFOCOM＇02,2002.

[10] 曾志,刘仁义,杜震洪,等.云格环境下基于P2P的动态资源发现机制[J].浙江大学学报:理学版,2013,40(4):463-468.

Design of Router Model on Mobile P2P Using M TA Technology

ZHOU Yong-fu1ZENG Zh i2
(1.Electronic and information engineering institute of Heyuan Ploytecnic,Heyuan 517000,China; 2.Department of Computer Science,Huizhou University,Huizhou 516007,China)

To solve the real-time transmission of media information,this paper introduces the methods of subnet node adopted by NAT node using the topology-aware thought(MTA)as improved multilayer net work management Chord model structure,based on the analysis of the existing P2P net work model algorithm,proposing multilayer topology-aware Chord model which is applied to instant messaging system of P2P network multimedia,and validating effectiveness and efficiency the routing protocol through system implementation and simulation.

network address translation(NAT);P2P;multilayer topology-aware(MTA);router protocol

TP3

A

1009-0312(2015)01-0050-07

2014-09-10

河源市社会发展科技项目(2013-1131);博士启动基金项目(2009C33011)。

周永福(1981—),男,江西贵溪人,讲师,硕士,主要从事P2P网络应用研究。