一种基于Pathload改进的网络可用带宽测量方法
2015-07-18李稚春
李稚春
摘 要：网络可用带宽是评价网络性能的重要指标之一，快速、准确地测量网络可用带宽对网络监测、拥塞控制、网络流量工程等具有重要意义。在分析传统Pathload测量网络可用带宽算法的基础上，针对其测量开销大、收敛速度慢等缺点，提出了一种改进方法。该方法完善了Pathload的判断准则，进一步改进了发送速率调整算法，NS2仿真结果表明，提出的改进算法在提高了测量准确性的同时，可以降低测量开销，收敛速度明显加快。
关键词：带宽测量；网络可用带宽；仿真；Pathload
中图分类号：TP393.1 文献标识码：A 文章编号：2095-1302（2015）05-00-03
0 引 言
网络带宽是指单位时间内链路上能够通过的最大数据位，可用带宽是指在不影响网络路径背景数据流的情况下，端到端通信所能获得的最大数据传输率[1]，二者的单位均为b/s。对于一个端到端网络传输系统，可用带宽具有很高的实用价值，网络可用带宽对网络负载均衡、传输速率控制、网络拥塞控制等有很重要的意义。设链路带宽为C b/s，带宽利用率为u b/s，端到端链路跳数为H，当前可用带宽为A b/s，则有：
（1）
（2）
（3）
目前，测量端到端链路可用带宽的方法主要分为单端测量和双端测量[2]，单端测量模式只需在测量的一端安装测试软件，便可得到链路的可用带宽；双端测量模式需要在客户端和服务器上都安装测试软件。两者相比，单端测量系统实现比较方便，但测量精度不如双端测量系统。表1列举了几种常见网络可用带宽的测量方法，其中单端测量方法包括：Cprobe[3]、Pipechar[2]、SProbe[4]、Abget[5]、ICMP-SLoPS[6]；双端测量方法包括：Delphi[7]，Pathload[1，8]，Pathchirp[9]，IGI[10]，Spruce[11]，TOPP[12]。
上述测量网络带宽的方法中，Pathload方法测量精度最高，但由于其采用自拥塞探测数据流方式，测量时间及测量开销较大，使用该方法测量一次可用带宽大约需要花费十几秒的时间，向网络中注入大约1 MB的探测包，在测量期间很难保证网络流量不发生变化。而用Pathchirp方法测量一次网络可用带宽只需花费几秒的时间，只需要向网络中注入200 kB左右的探测流数据。
表1 网络可用带宽测量分类 方法名称 通信协议 技术特点 年份
单
端
测
量 Cprobe ICMP 直接计算可用带宽 1996
Pipechar ICMP 包对测量技术 2001
SProbe TCP 基于TCP和HTTP协议 2002
Abget TCP 产生“伪造的”ACK信号 2005
ICMP-SLoPS ICMP 应用在IPv6网络 2008
双
端
测
量 Delphi UDP 指数递增分组探测 2000
Pathload TCP 自载周期流 2001
Pathchirp TCP 探测间隔呈指数递减 2002
IGI TCP 发送包对序列 2003
Spruce TCP 采用探测间隔模型 2004
TOPP TCP 分组对序列 2005
此外，上述测量方法都是基于2个假设条件：网络负载在路由节点呈先进先出队列；网络为流体模型，且背景流在测量周期内保持不变。
1 Pathload测量可用带宽原理
Pathload采用自载周期流探测技术（Self-Loading Periodic Streams，SLoPS）测量端到端链路的有效带宽。在发送端以一定速率R向接收端发送周期性探测流，通过分析数据包到达接收端的单向延时（One-Way Delay，OWD）的分布趋势，判断周期流的发送速率与端到端链路有效带宽之间的关系。通过二分法不断调整探测流的发送速率，使其逼近链路的有效带宽。
定义[1]：如果发送速率R>可用带宽A，则单向时延差ΔDk>0，呈现上升趋势；如果发送速率R <可用带宽A，则ΔDk≈0或者趋势不明显。
设R0为第1组数据包的发送速率，C1为第1个路由节点的带宽，A1为第1个路由节点的可用带宽容量，u1为第1个路由器的带宽利用率。
如果R0>A1，则：
A1=（1-u1）C1=C1-u1C1 （4）
R0+u1C1=R0+（C1-A1）=C1+（R0-A1）>C1 （5）
式（5）说明第1个路由节点已经开始出现数据包积压，即存在排队时延。设tk为第k个数据包的到达时间，T=L/R0，则在时间段[tk，tk+T]内路由队列为：
Δqk1=（L+u1C1T）-C1T=R0T-（1-u1）C1T
=（R0-A1）T>0 （6）
排队时延差：
（7）
同理，可以证明当探测数据流的发送速率R <可用带宽A时 ，单向时延差无明显上升趋势。通过图1（a）、图1（b）、图1（c）对这一特性进行进一步阐述，试验中发送端每次向接收端发送100个探测数据包，每次发送速率R均恒定，满足Ra
（a）RaA
图1 单向时延变化趋势
2 Pathload判定规则
Pathload利用两个参数SPCT（Pairwise Comparison Test）和SPDT（Pairwise Difference Test）判定单向时延是否存在递增趋势[1，8]，如式（8）所示：
（8）
其中，K表示数据流的长度（典型值为100），为了消除个别时延大幅波动带来的影响，引入滤波因子Γ，，将原始数据流进行分段，并用表示滤波后的每一组时延均值。当条件x成立时，函数I（x）为1，否则为零。不难看出，参数SPCT反映的是横轴上相邻两点具有上升趋势的概率，参数SPDT反映的是纵轴上最后1个点减去第1个点在相邻点时延累积和上所占的比例。Jain在文献[8]中指出由于时延具有随机波动性，最后一组滤波后的时延数据有可能与第一组时延数据大小相当，因此，这两个参数需要结合使用，才能正确判别时延是否具有上升趋势。
这里将文献[8]中提到的时延分布情况做了补充，如图2所示，图2（a）、图2（b）由文献中给出，图2（c）、图2（d）为本文补充。可以看出，当图2（b）中的第一组时延数据或者最后一组时延数据发生波动时，参数SPCT和SPDT均不能正确描述时延的上升趋势。为此，对参数SPDT进行改进，用时延的最大值代替最后1个点，用时延的最小值代替第1个点。同时，按照判别参数的物理意义，将SPCT定义为SPH（Probability in Horizontal），将SPDT定义为SPV （Proportion in Vertical），如式（9）所示，即分别从水平方向和垂直方向判别时延数据的上升趋势，二者具有互补性。从图2（c）、图2（d）中可以看出，当SPDT失效以后，SPV仍然可以对时延的上升趋势给出正确解释。
（9）
（a） （b）
（c） （d）
图2 单向时延统计分布
根据定义可知，0 表2 延上升趋势判别方法 SPH<0.54 0.54 SPV<0.45 无趋势 无趋势 无法判别 0.45 SPV>0.45 无法判别 上升趋势 上升趋势 3 可用带宽测量算法改进 根据Pathload测量可用带宽原理，自载周期流速率调整算法采用二分法计算下一次的发送速率，使其逼近端到端的可用带宽。初始化设置Gmin=Gmax=0；速率调整算法如下所示： （1）时延无上升趋势： （2）时延呈现上升趋势： （3）时延分布为灰色区域： 由于自载周期流速率调整算法收敛速度较慢，直接导致Pathload存在测量时间过长、带宽开销较大的缺陷，如果能够加快速率调整算法的收敛速度，就能从整体上提升Pathload算法的实用性。 由式（7）可知，第k+1个数据包离开第1个路由器与第k个路由器离开第1个路由器的时间差ΔT为： （10） 可以看出，相邻两个数据包离开路由器的时间与数据包的个数k无关，即第1组数据流离开第1个路由器的速率恒定： （11） 由此可以推断出分组数据流到达第i个路由器的速率Ri-1，与分组数据流离开第i个路由器的速率Ri以及该节点可用带宽Ai之间的关系满足式（12）： （12） 观察速率调整算法中的“时延呈现上升趋势”部分代码，当R（n）≥A时，如果用分组数据离开路由器的速率R*（n）代替，即Rmax=R*（n）（if（R（n）≥A）），可以有效降低速率的上限，使其与可用带宽之间的差值更小，从而加快速率调整算法的收敛速度，降低算法测量开销。 4 NS2仿真试验 为了评估改进后的判定准则及Pathload改进算法的性能，本节通过网络仿真软件NS2进行验证，参考文献[14]中试验方法设计端到端网络路径结构如图3所示，客户端与服务器之间共由5个路由节点组成，其中R3与R4之间为紧张链路，带宽容量为10 Mb/s，其余路由节点为正常链路，带宽容量为20 Mb/s。网络上的背景流量由具备自相似性特征的佩瑞多（Pareto）分布的源生成，α=1.9。其中，550 B的数据包占50%，40 B的数据包占40%，其余10%为1 500 B的数据包。 图3 端到端网络仿真拓扑图 将链路按照网络负载大小划分为几个不同的等级，分别为u1=20%，u2=40%，u3=60%和u4=80%四组，对应的真实有效带宽分别为8 Mb/s，6 Mb/s，4 Mb/s和2 Mb/s。试验中探测包的长度设置为300 B，设置精度参数ω=1 Mb/s，χ=0.2Mb/s，当发送10组探测数据流仍未收敛，则强行终止探测程序，并根据当前可用带宽的上下界给出一组最合适的估计值。 原始的测量方法并没有直接给出网络可用带宽的估计值，而是通过测量程序中的上下界给出一个区间，在这里将上下界相加取平均值，这样能够直接显示最终的测量结果，同时，也便于数据采集器网关利用该值进行发送速率调整。试验结果如表3所示，改进后的测量方法通过更新时延上界的下限，使测量结果的区间变窄，最终得到的可用带宽更接近真实的可用带宽值。此外，由于收敛速度变快，使得测量所需开销明显减小，对网络自身的影响相应降低。
表3 网络可用带宽测量结果比带宽
利用率 真实可用
带宽 Mb/s 原方法 改进方法
测量结果Mb/s 测量开销 Mb 测量结果
Mb/s 测量开销
Mb
u1=20% 8 2.24 13.44 1.99 6.72
u2=40% 6 4.47 13.19 4.23 7.41
u3=60% 4 6.5 12.78 6.31 8.72
u4=80% 2 8.31 11.52 8.18 9.6
5 结 语
本文针对Pathload测量网络可用带宽方法中存在的测量开销大、收敛速度慢等不足，从判断准则、发送速率调整两个方面入手对Pathload测量算法进行改进，加速更新可用带宽上下界， 从而加快收敛速度， 降低网络测量开销。NS2仿真试验结果证明了该方法的有效性，改进后的方法测量开销明显降低，收敛速度明显加快。
参考文献
[1] Jain M， Dovrolis C. End-to-End available bandwidth： Measurement methodology， dynamics， and relation with TCP throughput [J].IEEE/ACM Transactions on Networking， 2003，11 （4）：537-549.
[2] 周辉，李丹，王永吉.可用带宽度量系统中的若干基本问题[J].软件学报，2008，19（5）：1234-1255.
[3] Carter R L， Crovella M E. Measuring bottleneck link speed in packet-switched networks [J].Performance Evaluation， 1996，27–28：297-318.
[4] Saroiu S， Gummadi P K， Gribble S D. Sprobe： A fast technique for measuring bottleneck bandwidth in uncooperative environments[C].Proc. of the IEEE INFOCOM， IEEE，2002.
[5] Antoniades D， Athanatos M， Papadogiannakis A， et al. Available bandwidth measurement as simple as running wget[C].Proceedings of the Passive and Active Measurement Conference， 2006.
[6] 查新天，许晓东.IPv6中利用ICMP测量网络可用带宽[J].微计算机信息，2008，24（3）：121-123.
[7] Ribeiro V J， Coates M J， Riedi R H， et al. Multifractal Cross-Traffic estimation[C].Proc ITC Specialist Seminar on IP traffic Measurement， Modeling， and Management， Monterey， California： 2000.
[8] Jain M， Dovrolis C. Pathload： A measurement tool for End-to-End available bandwidth[C].In Proceedings of Passive and Active Measurements （PAM） Workshop， Fort Collins： 2002.
[9] Ribeiro V J， Riedi R H， Baraniuk R G， et al. PathChirp： Efficient available bandwidth estimation for network paths[C].Work shop on Passive and Active Measurement （PAM）， La Jolla， California： 2003.
[10] Hu N， Steenkiste P. Evaluation and characterization of available bandwidth probing techniques [J].IEEE Journal on Selected Areas in Communications， 2003，21 （6）：879-894.
[11] Strauss J， Katabi D， Kaashoek F. A measurement study of available bandwidth estimation tools[C].Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement， New York： ACM，2003.
[12] Melander B， Bjorkman M， Gunningberg P. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks[C].Global Telecommunications Conference， IEEE，2000，1：415-420.
[13] 曾彬，张大方，黎文伟，等.WPathload：一种改进的可用带宽测量方法[J].计算机研究与发展，2009，46（6）：898-904.
