一种任意子路径的带宽测量方法

贾圣文， 高仲合， 赵金龙

（曲阜师范大学 计算机学院，山东 日照 276826）

0 引言

近年来，围绕网络带宽测量人们设计了大量的测量算法和系统，这些测试技术大致可以分为三类[1,3]：用简单网络管理协议(SNMP)基于网络设备 MIB/RMON查询方法，被动监听分析方法和主动测量方法。由于前两种方法都存在一系列的问题，不能准确、灵活的测量到带宽，因此人们的研究热点都集中在设计精确、高效、快速、健壮的主动带宽测量方法。

在主动测量方法中根据测量工具到底部署在测量路径的一端或者两端，分为单端测量和双端测量[1]。单端测量仅在发送端部署测量设施，利用探测包的往返时延计算带宽，双端测量[5]方法要求在发送端和接收端都部署测量设施，存在时钟同步问题[4]。无论是单端测量还是双端测量都存在网络测量设施部署困难问题，甚至网络中不允许在测量的端部署测量设施。

这里提出的任意子路径的瓶颈带宽测量方法可以在一条超路径的两端测量任意子路径的带宽，解决了无法在测量两端部署测量设施的问题。子路径就是指一条路径的一部分称为这条路径的子路径，这条路径称为子路径的超路径。对于一条跳数为 n的路径，L1,L2,…,Ln,则 Li,Li+1,…,Lj（1≤i＜j≤n）称为该路径的一条子路径，该路径称为子路径的超路径。

1 方法设计

对一条路径 L1,L2,…,Ln，各跳链路容量为 b1,b2,…,bn，目的是测量这条路径的任意子路径的瓶颈带宽，例如对任意的 i，j（i＜j≤n）计算 mini≤k≤jbk，用 bi,j表示子路径Li…Lj的瓶颈带宽。设计的测量思想基于主动测量中的包间隔模型[1,3,6]，探测报文采用包串和包列[2]。

为了测量计算方便，在测量过程中做了一些假设：①中间路由器采用存储转发和先来先服务（FCFS）模式；②源端和终端只有一条路径；③源端主机能够发送背靠背的探测包列。

1.1节和 1.2节分别描述 b1,i-1＞b1,j和b1,i-1=b1,j两种情况下测量bi,j的思想 。

1.1 测量前缀路径的平静带宽

设计方法测量两条子路径瓶颈带宽 b1,i-1、b1,j。所用的探测报文是包串，该包串由背靠背的 ttl受限的负载报文p、q和探测报文 m组成，其中用 s表示大小，D表示包达到的目的端。定义该包串格式为 [ p m{ p q}r-1pm]，s(p)＞s(q)=s(m), D(pi)= D(qi)=Li，D ( m )=Ln（说明：{pq}r-1表示r-1个[pq]背靠背包对）。

在发送端发送上述定义的包串，则在链路 Li-1处，负载报文p、q由于ttl值减为0被丢包，由包间隔模型可知两个探测报文m之间的时间间隔为：

那么在不考虑背景流量影响的情况下△将保持到目的端。由此可计算出b1,i-1即：

用同样的方法测量 b1,j。如果测得结果 b1,i-1＞ b1,j那么bi,j= b1,j，否则继续下面的工作。

1.2 测量任意子路径的平静带宽

对于 b1,i-1= b1,j的情况，上述方法就无能为力，对于这种情况要按照如下测量。所用的探测报文是一由 x（x = j-i+1）个背靠背的大小为r的包串组成的包列，每个包串由ttl受限制的负载报文p、q和探测报文m组成。例如要测量子路径 Li…Lj的瓶颈带宽，所用的探测包列是[p m{ p q }r-1pm{ p q }r-1pm… { p q }r-1pm]其中 s (p)＞i- 1ii i i+1 i+1 i+1 j j j s(q ) = s (m), D(pi) = D (qi) =Li，D(m ) = Ln，设计这样的探测列的目的是让所有的探测包 m到达链路 Ln，所有的负载报文p、q分别在Li到Lj的链路上逐跳丢弃。

由包间隔模型理论知道，对于 n跳的链路L1，L2…Ln,每跳链路的带宽 b1,b2…bn，如果 b1,i-1≤ bi,n，对 x = n-i+1，r =1的包列[pi-1mpimpi+1m…pnm],如果那么在负载包前后紧邻的两个探测报文m在链路 Lk处时间间隔是：

1.3 测量过程总结

②比较 b1,i-1和 b1,j大小，如果 b1,i-1≥b1,j，那么 bi,j=b1,j到此就测量出了子路径的瓶颈带宽bi,j。否则转到步骤③；

2 子路径瓶颈带宽的定位

在以上描述的子路径瓶颈带宽测量方法中，可以通过标识探测包 m，定位出瓶颈链路。在接收端收到探测包后，根据探测包的唯一的标识信息，得出是哪两个相邻探测包的时间间隔最大，时间间隔最大的即是探测包在通过子路径瓶颈链路时的时间间隔，那么两个探测包之间的负载报文的 ttl值对应的即为子路径的瓶颈链路。由此就可以方便的定位出瓶颈带宽。在仿真中这里通过用探测包的大小来唯一的标识探测包，在不影响测量精度的范围内，使各个探测包大小不同（相差不能太大，否则影响测量精度）。例如探测包列设计43，这样探测包相差很小几乎不影响精度，如果在终端得到 m1、m2的时间间隔最大那么瓶颈链路就是 L3，同样如果在终端测得m2、m3的时间间隔最大那么瓶颈链路就是L4。

3 实验仿真

在下列实验中使用 Ns2进行仿真，测量 b1,2、b1,5采用的探测包串 [ p m{ p q}r-1pm]，其中 s (p)= 1 500, s(q)=s(m) = 4 0, D (m)=L6，D(p ) = D (q)在两次测量中分别为L2和L5。测量b3,5采用的探测包列是

3.1 在路径平稳背景流量环境下测量b3,5

在路径平稳背景流量环境下测量b3,5(图1示)。

图1 路径平稳背景流量

在由 CBR固定比特率背景流量环境下,背景包大小为500 bytes，发送速率依次为 20 Mb/s、30 Mb/s、40 Mb/s、48 Mb/s。采用r =2，测量b1,2，100次得到值均为b1,2=49.97;取包串大小r =2测得b3,5的结果如表1。

表1 cbr流量产生器和指数分布流量产生器仿真结果

3.2 在每跳平稳背景流量环境下测量b3,5

在每跳平稳背景流量环境下测量b3,5(图2示)。

背景流量分别由指数分布流量产生器产生，其中“ON”“OFF”状态为 100 ms。在 n0,n1, … ,n5背景包的大小分别为 100、300、500、700、900、1 100,不同的链路利用率u下首先取r =3测量2,1b ，100次求平均值，然后分别取r =1和r =2测量b3,5各100次，最后通过子路径瓶颈带宽定位过滤掉那些由于背景流量影响测得不是瓶颈带宽的错误值。图3、图4分别是r =1、r =2的测量结果，横坐标为测量的次数，纵坐标为测量的值。

图2 每跳背景流量

图3 指数分布背景流量r=1测量结果

图4 指数分布背景流量r=2测量结果

试验仿真表明，在两种背景流量环境下，该方法都能准确的测量出任意子路径的瓶颈带宽，并且能够定位出此瓶颈链路。在每跳背景流量下测量结果相对路径背景流量较大，随着链路负载越重，所受影响也随之增大，但仍能测量出此瓶颈带宽。

4 结语

该测量方法能在一条路径的两端测量出这条路径上任意一条子路径的瓶颈带宽，并且能方便的定位出此瓶颈链路，解决了在测量路径两端无法部署测量设施的问题。这里首先介绍了此方法的基本思想，然后理论分析方法的可行性，最后通过在NS2不同背景流量下的仿真表明该方法准确有效。

[1] 杨家海，吴建平，安常青.互联网络测量理论与应用[M] 北京：人民邮电出版社，2009：131-145.

[2] KHALED HARFOUSH,AZER BESTAVROS,JOHN BYTERS. Measuring Capacity Bandwidth of Targeted Path Segments[J]. IEEE/ACM Transactions on Networking,2009,2(17)：80-92.

[3] KEVIN LAI,MARY BAKER. Measuring Link Bandwidths Using a Deterministic Model of Packet Delay[J].ACM SIGCOMM Computer Communication Review.2000,30(04)：283-294.

[4] 聂玉婷，高仲合.单向实验测量中的时钟同步问题[J].通信技术,2009，42(10)：125-127.

[5] 韩宾，黄玉清，梁靓.可用带宽测量算法改进[J].通信技术,2009,42(04)：90-92.

[6] 何 莉,余顺争. 一种测量任意链路可用带宽的方法[J]. 软件学报,2009,20(04)：997-1013.