刘震宇，曾 彬，张 玫,，黎文伟

(1.中南林业科技大学计算机信息与工程学院，中国 长沙 410004；2.湖南移动长沙分公司，中国 长沙 410001;3.湖南大学软件学院，中国 长沙 410082)

端到端路径可用带宽是路径上的剩余带宽，或者说是路径上未被利用的带宽，决定了在不影响背景流量的条件下，端到端路径能够提供的最大传输速率．对一条路径而言，其中带宽最低点决定了任何时刻的传输速度．而不同时刻网络不断发生的动态改变使得带宽测量的结果差异很大，这使得对可用带宽的精确测量成为一个相当棘手的问题[1]．文献[2～3]将已有的测量可用带宽的方法分为2类：基于探测包间隔(Probe Gap Model， PGM模型)的方法和基于探测流速率(Probe Rate Model，PRM模型)的方法．其中，PGM方法通过考察探测包对间隔变化来估测可用带宽，耗费的网络带宽小，且实现简单．但对于一定长度的探测包对，其测量结果的稳定性和准确性直接依赖于带宽估算者计算包对时间间隔的准确性，而包对时间间隔容易受到背景流量、包异常等因素的干扰．当前的研究大多集中在如何调整测量模式，以过滤背景流量[4-7]．但少有文献去分析和总结存在背景流量等干扰因素下，包丢失等探测包对在传输过程的行为对测量结果精度的影响，缺乏对这些干扰因素与测量结果准确性之间关联规律的定量分析．

1 相关概念

首先定义相关变量，如表1所示．

表1 变量定义

图1 PGM模型中的包对测量带宽原理

PGM模型假设端到端路径上的紧张链路与瓶颈链路是同一跳链路，通过建立数据包对的时间间隔与背景流量的函数关系，计算端到端路径可用带宽．如图1所示[1]，如果在数据包对的第1个数据包离开瓶颈链路之后，到数据包对的第2个数据包到达瓶颈链路之前的这段时间内，瓶颈链路的队列没有被清空．则数据包对到达目的端时的时间间隔Δout应等于瓶颈链路处理探测包对的第2个数据包，以及处理Δin时间内到达瓶颈链路的背景流量一所共用的时间．其中处理背景流量所用的时间为Δout-Δin，则背景流量的平均速率为C(Δout-Δin)/Δin．因此端到端路径的可用带宽为：

(1)

如果已知端到端瓶颈带宽C，源端通过合理的设置数据包对发送时的时间间隔Δin，使背景流量在瓶颈链路插入到数据包对的两个数据包之间，然后测量数据包对到达目的端时的时间间隔Δout，PGM模型就可以通过式(1)计算端到端路径有效带宽．

包传输行为主要是指探测包在网络中传输时表现出来的行为特性，如包丢失、包乱序等．探测包的行为特性也是影响包对测量结果准确性的重要因素．另外，如果一个探测数据包在途中被意外破坏了，那么系统很可能由于无法识别它的特征信息而将它误认为是背景数据包，这同样会影响到测量的准确性．本次测量和分析的包传输行为指标主要有包丢失(packet loss)、包大小(packet length)和时钟精度(clock precise)．

2 实验设置

图2 仿真实验环境结构图

实验配置如图2，由左到右分别为测量源端，带双网卡的路由器和测量目的端．由于数据量小，因此路由器是采用Red Hat 9自带的软件路由：在一台普通PC机上安装双网卡，分别连接源和目的端，设置静态路由表，开启IP包转发．这样源端就可以通过路由器访问目的端了．再在本机器上安装网络仿真控制NIST Net软件[8]，可以仿真网络环境中各种参数的变化，譬如丢包率、延迟、抖动、带宽等等．

我们在测量源端运行一种典型的PGM测量带宽工具IGI[5],其形成的探测包对在流经NIST Net形成的仿真网络时，通过改变NIST Net上的参数，模拟网络变化，在目的端收集最终的相关测量信息，观察这些变化对测量结果准确性的影响．

3 测量结果分析

下面着重分析这些因素存在环境下包对表现出的行为特性．

3.1 包丢失

首先给出端到端路径数据包丢失统计指标的形式化定义：

实验中从源端连续发送包对到目的端，数据包流经由NIST Net网络仿真器模拟的网络．使用NIST Net，我们可以控制路径上总的丢包率及背景流量．观察在不同丢包率的情况下，包对表现出的行为特征．

表2 包对丢失情况统计测量

从表2中可以看出，随着路径总丢失率的增加，包对丢失率及包对流丢失率相应增加．当路径总丢失率处于轻度丢包(0～1%)情形，包对丢包率总体上控制在4%以内，对最后结果的统计分析几乎没有影响；当路径总丢失率处于中等丢包(0～2%)情形，包对丢包率总体上控制在10%以内，对最后结果的准确性有一定影响；当路径总丢失率处于严重丢包(2%以上)情形，包对丢包率随着迅速增加，使得测量无法继续进行．因此，可以得到结论：

结论1设D为成功测量次数的计数器，p为计数概率，p的取值与测量方法对结果的精度要求、运行时间要求等有如下关系：

文献[9]指出包丢失是一种比较突出存在的包异常行为．如果测量工具所发送的探测数据包引发了数据包丢失现象，而这些现象又同待测路径本身就存在的数据包丢失现象重叠在一起，那么从终端主机的角度要想准确获知造成包异常的原因，并正确判断探测包对时间间隔是非常困难的．本文的实验分析结论为提高测量工具在包丢失方面的抗干扰能力提供了直接依据．

3.2 包大小与时钟精确度

进一步分析探测包大小对测量结果的影响．共进行3组实验，各组的背景流量数据包的大小分别设置为56、512和1 024 bytes，每组中探测包大小均匀分布[56,1 300](bytes)的范围内．图3是实验结果，横坐标是探测包的包大小，纵坐标是每次测量得到的包对延迟差．其中图3(a)、(b)、(c)分别对应的是背景流量数据包大小为56、512和1 024 bytes的情况．

通过对比图3(a)、(b)、(c)，可以发现3组实验分析图存在以下共同的特点：随着探测包大小的增加，包对延迟差总体上呈增大趋势，即对带宽测量产生低估效应．换言之，当采用较小包长的数据包对测量路径带宽时，相对于采用较大包长的数据包对，前者得到的结果更接近于真实值．

设端到端路径由n段链路组成，第i跳为瓶颈链路，l为探测包长度，Cr为背景流量，Cr[i]是在该跳加入到探测包对间的背景流量，Δi为探测包对离开瓶颈链路时的包对间隔，则有：

(2)

根据PGM模型的假设，包对间隔将保持不变直到目的节点，最后Δout=Δi．但实际上，在后续链路上，探测包对可能继续排队，即：

(3)

(4)

另外，图3(a)中探测包大小在接近256 bytes 时得到的测量结果比较接近理想值，而且比较稳定；以推断探测包长度与背景流量数据包长度比较接近同样地，图3(b)和图3(c)中探测包大小在接近512 bytes和1 024 bytes时测量结果比较准确．

为了说明时钟精确度，假定接收端的时钟精确度为Cpr，tstart是终端主机将数据包中的所有字节通过网卡从物理媒介上完整接收进来的时刻，并设tend是系统所记录的它完成这一操作的时刻，则时钟精确度Cpr可以表示为：

Cpr=|tstart-tend|.

(5)

设理论上的包对时间间隔为Δt．显然，时钟精确度的值至少不能比探测包对间隔低，否则包对时间间隔是无法测量得到的，也即是：Cpr≥Δt.

(a)背景流量数据包大小256 bytes (b)背景流量数据包大小512 bytes (c)背景流量数据包大小1 024 bytes图3 不同包长度条件下包对延迟差测量结果的分布

又设探测包大小为l，路径的瓶颈带宽为Cp，由PGM原理可知 Δt=l/Cp，则有：l≥Cp·Cpr.

综合上述分析，可以得到结论2：

结论2设lcross为背景流量包大小的期望值，lmin为探测包能取到的最小值．则要提高测量的精确度，对于探测包大小的选择需满足：(1)探测包的最小值要大于路径瓶颈带宽与时钟精确度的乘积，即l≥Cp·Cpr；(2)探测包尽可能取小包，即l→lmin；(3)探测包大小尽可能与背景流量的数据包大小比较接近，即l≈lcross．

4 结束语

PGM计算端到端路径可用带宽方法的优点在于能通过发送少量的探测包，比较稳定和准确地实现对被测路径带宽的测量．但探测包对间隔容易受到路径上存在数据包异常等的干扰，从而造成对可用带宽的高估或低估．本文利用理论分析和实验验证的方法，针对包传输行为，对探测包对的行为特征分别进行了定量分析与总结，分析得到了一系列有价值的结论，为PGM测量工具的改进与完善提供依据．

参考文献：

[1] ZHOU H, WANG Y J, WANG X L,etal. Difficulties in estimating available bandwidth:Proc of IEEE International Conference on Communications, Istanbul, Turkey, 2006[C].Istanbul:[s.n.],2006.

[2] 曾 彬, 张大方, 黎文伟, 等. WPathload：一种改进的可用带宽测量方法[J].计算机研究与发展, 2009, 46(6): 898-904.

[3] 韦安明, 王洪波, 林 宇, 等. IP网带宽测量技术研究与进展[J]. 电子学报, 2006, 34(7) :1 301-1 310.

[4] JALN M, DOVROLIS C．End-to-End available bandwidth: measurement methodology, dynamics, and relation with TCP throughput[J]．IEEE/ACM Trans on Networking, 2003, 11(4): 537-549.

[5] HU N, STEENKISTE P. Evaluation and Characterization of available bandwidth probing techniques[J]. IEEE Journal on Selected Areas in Communication: Special Issue in Internet and WWW Measurement, Mapping, and Modeling, 2003, 21(6):879-894.

[6] 黄国伟, 吴功宜, 徐敬东. 基于排队分析的端到端路径可用带宽的测量[J].计算机研究与发展, 2007, 44 (1) : 85-91.

[7] 刘星成, 何莉, 余顺争. 网络可用带宽的高精度测量算法[J].电子学报, 2007, 35 (1) : 68-72.

[8] MARK CARSON, DARRIN SANTAY. NIST Net: a Linux-based network emulation tool[J]. ACM SIGCOMM Computer Communication Review, 2003,33(3): 111-126.

[9] 周 辉, 李 丹, 王永吉,等.可用带宽度量系统中的若干基本问题研究[J].软件学报,2008,19(5):1 234-1 255.