一种新型P2P应用层并行路径选择机制

刘 佳， 张 晨， 魏世民

(①北京邮电大学 自动化学院，北京 100876; ②中国移动通信集团设计院有限公司研究所，北京 100080)

0 引言

文件和数据传输是网格业务网络或 P2P网络最主要的业务类型之一。对于数据量巨大的文件和数据传输业务，业务本身的稳定性，吞吐量和可靠性变得非常重要。对于这两种网络，特别是跨自治域的时候，获知 IP层或者是更低层的网络拓扑是非常困难的，在这种情况下，可以选择在P2P层建立多条并行路径来实现并行路径的传输，也就是由一组对等体（peer）来组成多条传输路径，实现两个peer之间的文件传输[1-4]。

但是P2P层的并行路径可能在IP层或是更低的层面共享一到多条链路，以至于拥有相同的拥塞点，路径性能的变化规律趋同，使得并行路径难以实际达到提高文件传输性能的要求，还有可能加剧网络性能的波动[5]。

这里研究的目的是当网格业务网络或P2P网络在P2P层中使用并行路径来实现文件传输业务时，仅依靠P2P层的技术来实现在多条可行的并行路径间选择恰当的并行路径，切实提高业务的稳定性、可靠性和吞吐率。

1 并行路径选择算法与机制

1.1 定义

路径间的相关性：选定一个或一组影响传输路径的参数作为测量值，经过一段时间的观测后，在时间上，计算不同并行路径间的参数值的相关性为ρ，称为路径间的相关性。传输路径参数即业务在路径上的传输速率、抖动、延迟等参数。这里将以传输速率为例来说明相应的算法和机制是如何设计的。

弱相关路径：不同路径间的相关性，如果低于某一个阈值T，则认为这些路径彼此之间属于弱相关路径。

较优路径：假定路径a、b、c有相同的源、目的点，且为a与b为弱相关路径，相关系数值为ρab，a与c弱相关路径，值为ρab，以下条件中的任一条被满足时，则称b相对于c是a的较优路径：，或者但

1.2 优化模型

假设在路径间相关性的计算中，所使用的参数仅为业务在路径的传输速率。也可以使用其它可以反映路径性能的参数，如抖动和延迟，所遵循的算法和机制是相同的。下面给出这里的优化模型。

在一个网格业务网络或P2P网络中存在由peer构成的多个源、目的节点对，每对源、目的节点之间存在有多条可行并行路径。其中源、目的节点间在P2P层的直联路径，为必选路径。这里的优化对象为在各源、目的节点间传输任务。对这些传输任务进行实时优化，也就是说仅对正在发生的传输任务或是即将发生的传输任务进行优化。这里的优化目标为每一对源、目的节点对选择恰当的并行路径，使得每一对源、目的节点对间的每一个传输任务的传输速率最大化；每一对源、目的节点对间的并行路径间的相关性最小化。

在优化中，需要遵守如下约束条件：网络任一节点流量守恒；任一路径上的流量不小于0；任一路径上是没有闭环的。

1.3 路径间相关性的测量机制

为了实现优化模型，需要对两个子优化目标中的传输速率和路径间的相关性进行监测。在这里，采用网络测量中的被动测量方法对任一路径上的任一业务的传输速率进行监测，进而可以得到业务的总的传输速率和并行路径间的相关性[6-7]。

下面为属于同一源、目的之间任两条并行路径间相关性的测试量机制：

在目的节点根据单位时间内接收到的来自源节点的有效包的大小，测算不同路径的吞吐率，每x秒测量一次，经过周期t后，计算来同一源节点的任两条路径间的相关性各一次。

由目的节点发送相应的测试报告至源节点。

在路径间的相关性的计算公式，有如下两种可供选择：

测量公式 1 设两条路径p和o的任一时刻的吞吐率分别为随机变量 tp和 to，则在每一个测量周期内有n次测量值分别为 tp 1 , t p 2 ,… ,tpn 和to1 ,to 2 ,…,ton,其中1代表最早测量时间点，n代表最晚的时间测试量点。

定义各时间点的加权后的有效测量值为：

则两条路径间在第T周期的协方差为：

计算相关性的公式：

对测量结果加权的目的在于考虑到网络整体性能发生显著变化的可能性，强化最后几测量结果对于路径相关性的影响。

测量公式2 由两部分组成，前一次相关性的计算结果，这次的相关性的计算结果；这次相关性的计算结果，也是经过加权的相关性计算结果。

继续测量公式1的假设，但是 k 1 =k 2 =…=kn=1。

令两条路径间在第T周期的相关性为ρpoT，在第T-1周期的相关性为 ρ p o( T -1)，则记两条路径在第T周期的实际相关性为具体的参数是可以再调整的。

如果使用此公式，建议n的取值应当比使用测量公式 1时的值小。

1.4 并行路径间的选择机制

规定任一对源、目的节点对间的P2P层的直连路径是必选路径，只要还有传输业务，该路径就必须存在。根据优化目标和测量的结果，在源、目的节点对间选择并行路径的机制如下：

①在初始状态下，当一对源、目的节点对间有新业务需要传输时，从可行的并行路径集中，随机选择一到多条路径（推荐选择一条路径）与直连路径共同构成实际使用的并行路径集；

②同时开始针对有业务传输的路径的传输速率和路径间的相关性的测量和统计；

③当达到相对稳定的状态，对于已经正在传输的业务，要周期性的统计其使用的路径间的相关性，作为经验值不断累计，一定时间以前的相关性数据可以被更新掉；

④对于新建的业务，根据积累的数据，选择一条路径，如果积累的数据，是在给定的时间内统计得到的，否则，随机选择一条；

⑤如果对于正在传输的业务的两条路径的相关性或是吞吐速率不满意，则依照同样的规则重新选择路径，但是把已选择的路径排除在外。

2 仿真分析

2.1 仿真步骤简介

仿真采用的并行路径传输机制简称PRTG, 采用部分副本技术，拥有完整数据的源服务器和转发服务器（简称PRS）一起组成并行传输路径将数据传输到目的服务器[5]。

仿真工具采用网络模拟器NS-2[8]，对采用路径选择机制后的PRTG和未采用路径选择机制的PRTG进行对比分析。

仿真分两步进行。①在随机产生的任一拓扑下，同时发起多组业务。进行多次仿真传输。每次传输的同一大小的业务有相同的源和目的节点，但是不同的PRS，这样多次以后可获得不同路径间的相关系数。从而获得相关系数与业务传输周期之间的关系；②通过第一阶段获得的数据，采用路径选择机制选择较好路径进行传输，与随机选择路径进行传输的PRTG进行对比分析。主要比较业务周期和链路利用率。

图1、图2、图3都是在相同拓扑结构下的仿真结果。这种拓扑结构有18个节点（6个路由器和12个peer）和28条链路（10 kb/s 到 40 kb/s之间）。

2.2 阶段一

图 1显示采用不同相关性系数的并行路径进行文件传输时，所用时间（即业务周期）对比。结果表明选择相关系数小的并行路径业务周期更短。

图1 采用不同相关系数并行路径的业务周期对比

2.3 阶段二

图2和图3分别显示PRTG在采用新的路径选择算法前与采用新的路径选择算法后的业务周期和平均链路利用率对比。

图2 业务周期对比

图3 平均链路利用率对比

图3中横坐标轴时间需乘以50。结果表明在整个网络内采用路径选择算法后，能够增强网络的业务容量,获得更高的带宽利用率和更短的业务周期。

3 结语

针对网格业务网络或 P2P网络中的并行路径数据传输业务，提出了一种新的基于被动测量的 P2P并行路径选择算法与机制。该机制已经在中欧网格互联（EC-GIN）项目中的PRTG中被实现并在有几个自治系统的小的网络中被验证。仿真和真实结果都证明此算法和机制能够对采用并行路径的传输机制的性能进行优化。此机制主要是针对 P2P层并行路径的选择而设计的，但它也适用于解决开放式系统互联(OSI)七层协议中其它层面协议所遇到的多路径选择问题。

[1] LI M.The Grid： Core Technologies[M]. Wiltshire：Antony Bowe Ltd.2005：1-77.

[2] 聂荣，余建国，吕英华.国内对p2p网络的相关研究[J].通信技术，2008,41（07）：130-132..

[3] 韩桂华，李法冰. 网格计算安全性研究[J].信息安全与通信保密，2007(03)：116-117.

[4] 王伟，张利刚，吕彬.基于主动识别技术的网关p2p流量检测[J].信息安全与通信保密,2009(12)：91-92.

[5] ZHANG CHEN, GAO PENG, LIU TAO, et al. A Novel Bulk Data Transfer Mechanism on Partial Replica[C]. Beijing： Institute of Electrical and Electronics Engineers, 2009：766-770.

[6] 夏彪.端到端网络瓶颈测量研究[D].武汉：武汉科技大学,2009.

[7] 姚远程.网络时延测量中的时间同步系统应用研究[J].通信技术,2008, 41(08)：149-153.

[8] 包斌，詹自熬.ns2深度探索及在网络传输性能分析中的作用[J].通信技术,2009,42(05)：155-160.