曲 桦 ，赵季红 ,2，王丽霞 ，董士奇

（1.西安交通大学电子与信息工程学院 西安 710049；2.西安邮电大学通信与信息工程学院 西安 710061）

VoIP业务在互联网上为用户建立端到端路径，需保证业务的时延小于150 ms[1]。为了保证VoIP业务的时延要求，在基于多自治域（autonomous domain，AS）的覆盖网络上为其建立端到端路由是目前发展趋势[2]。但覆盖网络中存在反三角现象，导致网络中两条路径的时延之和小于一条端到端路径的时延[3～5]，因此，需要在覆盖网络中研究中继技术，确定合适的中继节点，建立从源节点通过中继节点到目的节点的路径，使得该路径的时延最小，以承载VoIP业务，减少VoIP业务的时延，满足用户的业务请求[6]。

覆盖网络是应用层网络，不考虑或很少考虑物理层网络的问题，利用中介机构作为中继节点绕过性能下降的网络路径，可以提供多个路径并选择维持最好的网络条件[7]。目标节点通过中继节点到达目的节点的路径即中继路径。中继选择算法的目的就是搜索合适的中继节点以建立性能更优的中继路径。

中继选择算法主要有弹性覆盖网 （resilient overlay network，RON）、基于自治域感知的中继节点协议（AS-aware peer-relay protocol，ASAP）、最早发散规则（earliest divergence rule，EDR）、单跳启发式中继节点选择算法（heuristic relay node selection algorithm for one-hop overlay routing，HORNS）、基于meridian的中继选择算法 （meridian-based relay selection algorithm，MBRS）等。RON[8]算法是在物理路径发生故障时，在直连路径外寻找一个中继节点，通过中转路径恢复VoIP业务，该算法选中的中继节点不具有通用性，并不能解决网络中的普遍现象且过分依赖中央服务器，需要全局信息。ASAP[1]算法根据AS信息寻找合适的中继节点，该算法能提升链路性能，并能精准地找到中继节点，但依赖于全局网络AS分布图，应用中很难部署。EDR[9]算法依据路由源点发送探测针获取的周围AS级别的路径时延信息做出路由决策，该算法只需知道源节点到中继节点的时延和AS路径，无需其他中央服务器，但它没有考虑时延、分组丢失率方面的性能。HORNS[10]算法以源节点到中继节点的时延作为尺度，发现最优中继节点的分布规律，并按照这种比例分布在不同时延区域挑选不同数量的节点作为中继节点的候选者，该方法能更好地挑选中继节点，但没有考虑路径的差异性。MBRS[11]算法以meridian为基础来查找中继，它能找到一个距离目的节点较近的中继节点，但是路径时延不是最小，选出来的节点并不是最合适的中继节点。

鉴于现有算法存在的缺陷，提出基于路径优先度的VoIP中继选择算法 （a path-priority based relay selection algorithm for VoIP，PPBR）。该算法首先提出路径优先度概念，用以描述时延和与默认IP路径的差异性，再基于路径优先度构建中继路由表，从中选择最优中继节点；针对覆盖网络中普遍存在的“反三角现象”[3～5]，提出基于路径优先度的两跳中继选择算法，通过两个中继节点的转发减少时延。

2 路径优先度

2.1 问题描述

传统的IP网络采取的是尽力而为的传输方式，由路由策略决定唯一路径，而路由策略通常由AS之间的商业关系所决定，不同的AS可能采用不同的路由策略，因此存在AS间的路由不是最优的情况。而覆盖网络是基于应用层构建的，不考虑或很少考虑物理网络层的问题，可以在应用层选择多个中继节点来实现端到端的多路径传输，通过主动探测和监视节点之间的链路选择最优的中继路径，有效地避免IP网络的拥塞和时延抖动问题[12]。研究证明，应用层提供的中继路由能够得到比默认的IP直联路由更好的性能[13]。随机选择中继节点并不能保证路径与默认路径之间的差异性，75%的路径存在较严重的重叠，因此结合网络拓扑的中继节点选择算法成为研究重点[14]。

VoIP的通话质量主要受两个因素的影响:时延和分组丢失率。低时延路径在分组丢失率方面也具有较好的性能参数，其重要的原因是高时延的路径由于节点处于阻塞状态，导致时延，并伴随出现很多分组丢失现象，因此，在改善时延的同时可以改善分组丢失率参数。通过比较默认IP路径与覆盖网路由新路径上的重合节点数，可以定量地获得两条路径的差异性。而两个差异性大的路由同时发生链路失效和链路效能下降的概率较小，这样就可提高端到端路由的传输质量。同时，这也使得网络的流量分布于不同的路径，实现了网络系统的负载均衡。因此，本文所提基于路径优先度的VoIP中继选择算法的核心思想是:在给定的具有固定拓扑的多个AS互联的网络环境下，从源节点到目的节点之间的多条覆盖网端到端路径中选择一条时延能达到最小且与默认的IP路径有差异的路径。

综合时延和与默认的IP路径有差异性这两个指标提出路径优先度，依此作为选择标准。

2.2 路径优先度概念

对于每个VoIP业务请求，计算从源节点途径中继节点再到目的节点的时延以及这些路径与默认路径的重合度。依此设定一个权值参数θ，称其为路径优先度，定义如下:

其中，Ohops表示重合的节点跳数，Thops表示总的节点跳数。Rlatency表示中继路径的时延，Qlatency表示VoIP业务QoS参数中的时延要求，通常是150 ms。

因为时延和路径差异是中继路径选择的两个主要因素，θ用来衡量这两个因素的偏重度。θ越小，说明中继节点的时延效果和路径差异的效果越好。

3 基于路径优先度的VoIP中继选择算法

3.1 路由表的构建

把有lgN个邻居节点的节点作为最有潜力成为中继节点的节点，组织到一个路由表中。逐次查找路由表中的节点，只要找到符合要求的邻居节点，就可以完成中继节点的选择。

遵从贪婪算法，在选择节点的时候对于不同时延范围的节点选择的比例也不同。尽可能选择距离源节点时延小的节点，同时还要保证每个时延范围内都有节点被选到。选取节点与其所在AS距离源节点自治域的跳数和时延有关[15,16]，为每个节点选取20个中继候选节点。对每个范围内的候选节点，按照时延由小到大排序，并按照相应比例来选择。由候选节点的时延、AS和IP地址构成一个路由表，格式见表1。

表1 基于时延和路径差异性的路由表格式

构建路由表的算法如下。

其中ASs表示网络中所有的 AS，AS（p）表示节点 p所在的 AS。hop（AS1,AS2）表示自治域 AS1与 AS2之间的跳数。从距离源节点AS跳数为1的AS中选择3个候选节点，跳数为2的AS中选择2个候选节点。其他AS，每个选择一个候选节点。假设在每个AS选择时，先随机选择10个节点，然后通过一定的测量机制测量源节点到这些节点的时延大小，并且从低到高排序，进而按前面的原则选取节点。

图1显示了应用上述路由表构造算法在大规模多AS中选择中继节点的一个过程。对自治域AS1节点在构造路由表时，首先从距离 AS1一跳的自治域AS2、AS3、AS4内各选3个节点作为候选中继节点，例如从自治域AS3中选择节点1、3、4 作为候选。接着从距离AS1两跳的自治域 AS5、AS6、AS7、AS8中各选两个节点加入中继路由表。最后从距离自治域AS13跳以上的自治域内各挑选一个节点加入中继路由表，直到路由表设定的数目已满。当路由表中存储的某个中继失效时，AS会重新选择一个候选节点补充，例如AS3中节点3失效，则会选择节点2作为补充加到路由表中。

3.2 中继路径的选择过程

路由表构建完成后，即在此表中选择中继节点。首先计算从源节点到目的节点的默认路径，并且记录所经过的节点的ID和IP地址，然后在源节点路由表中除去，并由路由表中剩余节点组成一个新节点集；在新的节点集中选择θ最小的节点作为中继节点。具体算法如下。通过该算法，可找到满足条件的中继节点。

图1 路由表中的候选中继节点的选择示意

其中，Pde表示默认路径，Pr为中继路径。ns表示源节点，nt表示目的节点，Nrelay表示除去默认路径上节点的节点集合。Ohopsr表示默认路径与中继路径的重合节点数目，Ds,t表示中继路径时延。

3.3 基于路优先度的两跳的中继路径选择算法

网络有时可能出现“反三角现象”[3～5]，单跳的中继路径并不能很好地解决问题，而两跳的中继路径性能更好。两跳中继路径选择算法基本原理与一跳算法相似，具体算法如下。

4 仿真与性能

本文采用PPBR算法仿真查看算法能够查找到满足要求的中继节点的成功率，并计算PPBR算法的时延与默认路径的时延差值和时延改善率。仿真数据采用King数据集的1895个节点间时延[17]。从原始数据选取部分节点数据，根据IP地址与IP前缀获得AS号。实验进行50次随机选取一对源节点和目的节点；假设中继路由表节点数目为20个，节点总数范围为100～1000个。

4.1 路径时延

图2为采用一跳PPBR、两跳PPBR算法以及默认IP路径所得的时延。图中PPBR算法相比默认IP路径时延明显减小。很多情况下两跳算法的时延又明显优于一跳算法，表明采用两跳算法解决了“反三角现象”。

4.2 时延改善率

时延改善率指应用算法预测的时延与默认路径的时延相比，时延减少量相对默认路径时延的比率，表示算法性能的优劣。时延改善率越大，表示算法相对于默认路径的时延减少越多，性能越优。

图2 PPBR算法路径与默认IP路径时延的比较

PPBR算法与默认路径的时延差值，如图3（a）所示。PPBR对默认IP路径的时延减少量维持在5～20 ms。个别情况会出现PPBR算法的时延比较大的情况，这是因为有些自治域位于网络的边缘附近，网络连通性不够大，反而会导致构成的中继候选节点路由表中的节点绕路，增加了网络的时延。但是可以从图中看到大部分的实验都可以找到缩短时延的中继节点。图3（b）则显示了时延改善率，从图中可看到网络的时延可以改善5%～20%。

图3 PPBR算法的时延改善

5 结束语

在覆盖网络中部署VoIP业务，计算端到端路由时，需保证其时延要求，一般小于150 ms。鉴于覆盖网络中普遍存在的“反三角现象”且已有算法存在部署难、未考虑路径差异及结果不是最优等问题，本文通过基于路径优先度的VoIP中继选择算法，选择从源节点到通过中继节点到目的节点的最优路径。该算法首先提出路径优先度的概念，描述时延和默认IP路径的差异性，再基于路径优先度构建中继路由表，在中继路由表中挑选最优中继节点；提出基于路径优先度的两跳中继选择算法中继进一步减少转发时延。仿真证明所提算法能够减少VoIP业务的传输时延，保障VoIP业务的QoS，提升VoIP业务的用户体验。

1 Ren S,Guo L,Zhang X.ASAP:an AS-aware peer-relay protocol for high quality VoIP.Proceedings of the 26th IEEE International Conference on Distributed Computing Systems(ICDCS 2006),Lisboa,Portugal,2006

2 Amir Y,Danilov C,Goose S,et al.1-800-overlays:using overlay networks to improve VoIP quality. Proceedings of the International Workshop on Network and Operating Systems Support for Digital Audio and Video,Stevenson,Washington,USA,2005:51～56

3 Zheng H,Lua E K,Pias M,et al.Internet routing policies and round-trip-times.Passive and Active Network Measurement,Springer Berlin Heidelberg,2005:236～250

4 Lumezanu C,Baden R,Spring N,et al.Triangle inequality variations in the internet.Proceedings ofthe 9th ACM SIGCOMM Conference on Internet Measurement,Chicago,Illinois,USA,2009:177～183

5 Lumezanu C,Baden R,Spring N,et al.Triangle inequality and routing policy violation in the internet.Proceedings of the 10th International Conference on Passive and Active Network Measurement,Seoul,Korea,2009:45～56

6 Liu Y,Gu Y,Zhang H,et al.Application level relay for high-bandwidth data transport.Proceedings of GridNets,San Jose,CA,USA,2004

7 Wang G,Zhang C,Qiu X,et al.An efficient relay node selection scheme to improve the performance of P2P-based VoIP applications in Chinese internet. Multimedia Tools and Applications,2013,64(3):1～27

8 Andersen D,Balakrishnan H,Kaashoek F,et al.Resilient overlay networks.ACM SIGCOMM Computer Communication Review,2002,32(1)

9 Fei T,Tao S,Gao L,et al.Light-weight overlay path selection in a peer-to-peer environment.Proceedings of the 25th IEEE International Conference on Computer Communications,Barcelona,Catalunya,Spain,2006:1～6

10 Chen Y,Tang L,Li J.Heuristic relay node selection algorithm for one-hop overlay routing.Proceedings of the 28th International Conference on Distributed Computing Systems Workshops,Beijing,China,2008:465～470

11 Wang H,Zhang C,Qiu X,et al.MBRS:a meridian-based relay selection algorithm for P2P VoIP.Proceedings of the 3rd IEEE International Conference on Broadband Network and Multimedia Technology(IC-BNMT),Beijing,China,2010:965～969

12 Zhang X,Lei W,Zhang W.Using P2P network to transmit media stream in SIP-based system.Proceedings of the 9th International Conference for Young Computer Scientists,Zhangjiajie,China,2008:362～367

13 Baset S A,Schulzrinne H.An analysis of the skype peer-to-peer internet telephonyprotocol.Proceeding soft he 25th IEEE International Conference on Computer Communications,Barcelona,Spain,2006:1～11

14 Han J,Watson D,Jahanian F.An experimental study of internet path diversity.IEEE Transactions on Dependable and Secure Computing,2006,3(4):273～288

15 Chen Y,Tang L,Li J.Heuristic relay node selection algorithm for one-hop overlay routing.Proceedings of the 28th International Conference on Distributed Computing Systems Workshops,Beijing,China,2008:465～470

16 Bui Q D,Jennings A.Relay path selection approaches in peer-to-peer VoIP systems. Proceedings of Australasian Telecommunication Networks and Applications Conference,Adelaide,Australia,2008:361～366

17 Network coordinate research at Harvard.http//www.eecs.harvard.edu/～syrah/nc/,2014