pathload --有效的网络带宽估计方法

上一篇博客简述了现行的带宽估计的方法，分类，以及一些问题。

见：http://blog.****.net/ice110956/article/details/11071969

上文列出了13种现行的方法，这里首先介绍性能，准确性都较好的一个方法：pathload.

Pathload

首先介绍Pathload方法所属的类别

1.    正如上一篇blog所述，带宽估计的方法分为单端探测和两端探测，pathload属于两端探测；

2.    我们还可以根据发送的是包对，还是一系列紧相连的包，分为包对探测，包序列探测。Pathload属于包序列探测。如下图所示：

 

3.    接上篇blog的一幅图：

 

同样是包序列探测，还有许多不同的方法，比较直观的有两种：

一个是直接计算到达包的个数/秒，上图可得带宽为2packets/s.

另一个是用接收端到的时间-发送端发出的时间，具体到上图就是:

Da=t1+t2+0-0=t1+t2+0

Db=t1+t2+2-1=t1+t2+1

Dc=t1+t2+2

Dd=t1+t2+3;

接着再根据D来作进一步的计算，pathload就是用这种方法，具体实现下面介绍。

两个方法一个横向计算，一个纵向计算。

下面具体介绍pathload的方法。

一.判断是否过载

Pathload方法发送一个包序列，并记录发出时间以及到达时间。据证明，如果发送速率大于链路带宽，包的间隔会有增大的趋势；相反，发送速率小于链路带宽，没有这种趋势。发送端再根据这种趋势迭代地更新发送速率，直至收敛。

根据我们上面的图也能看出来，Da,Db,Dc,DD是直线上升的。

如下面两个图，横坐标是包间隔，纵坐标是单向的链路延时，即到达时间减去发送时间。

图1是在发送速率达于链路的情况下统计的，表明发送带宽达于链路带宽，D成增长趋势。

图2表明，小于的情况下，没有这种趋势。

图3表示网络带宽突然的增长导致曲线突然上升。

上面我们只是直观地判断是否有增长的趋势，下面具体提出两个指标公式。

PCT指标为增加的百分比；一直上升为1，不变为0；

PDT指标为绝对差值比去相对总浮动。直线上升为1，直线下降为-1，水平为0.

 

如上图所示，这两个指标有的时候是有差异以及盲点的。第一幅，虽然呈现上升趋势，当偶然的误差导致PDT为0；第二幅，同样也是上升，PCT却为4/11.

于是我们取如下的综合策略来进行综合评估。

1，  如果其中某个为上升，另一个是上升或不确定，则判断为上升。

2，  同样，如果其中一个为下降，另一个是下降或不确定，判断为下降。

3，  如果都为不确定，则判断为不确定

4，  一个上升，一个下降，结果丢弃。

pathload设置的PCT和PDT的阈值分别为：

PCT：0-0.54，下降；0.54-0.66，不确定；0.66-1，上升。

PDT：-1-0.45，下降；0.45-0.55，不确定；0.55-1，上升。

下面两个图分别展示着两个指标的准确度。

二．参数选择问题：

首先是包大小与发送周期的关系；

包的大小不能达于链路最小分包的大小，否则会被链路层切成小块；同样也不能过小，防止链路层填充包大小。

一般包大小为48-96byte.

发包的周期越小越好。

操作系统最小周期可达30us,pathload采用100us的周期。即间隔100us发送一个探测包。

于是首先确定要发送的包序列的带宽R，然后周期为T，再计算应该发送的包的大小，用如下的公式：

然后是序列的长度。序列过长导致路由阻塞丢包。过短不能有效判断带宽。这里的长度为K=100，这样的一个序列成为一个stream.

一个stream的判断准确度有限，pathload里面用N个stream来综合评定是否上升。

Stream之间有一个小的间隔，只为等待两端的计算处理。

pathload中N是12,这样的12个stream称为一个fleet.

最后，根据N个序列的结果，我们还要做一次综合评定。取f=70%为阈值，即这N个fleet里面，增长或减少的判断数要分别大于70%才能下结论，否者定为不确定。

三．二分法收敛到估计带宽

我们上面最后的计算结果过载，不确定，或不过载。那么我们要如何估计网络的具体带宽呢？pathload用二分法来收敛到网络带宽。

一个fleet用于判定是否过载，接下来要用多个fleet进行带宽准确估计。每个fleet得到一个判定后，用二分法迭代，直到满足一定的收敛条件，程序如下：

如上图，其中的R分别表示当前的发送速率，G表示当前的不确定区间。用二分法迭代收敛R和G，当满足一个阈值w，x的时候，表示收敛，可以得到最终的链路速率。这种方法最后确定的是一个速率区间。

四．几个注意事项：

1.接受方还要计算丢包率，当有丢包时，这个stream就被标记为不可用。如果多余一个stream丢包，或丢包率很大，直接把当前的速率作为上限，继续计算。

2.接受方还要计算两个包的发送间隔，间隔大于一定值时，接受端判断发送端发送线程被抢占，出现错误，以i为界限，把包分为两个部分，取大的一个部分继续计算，丢弃另一部分。如下图，只取后面的一段。

五．结果

最后取(Rmin+Rmax)/2作为带宽估计值。试验表明，带宽越高，需要的收敛时间越长，15Mbps的带宽大概需要10个fleet即12S的时间。

参考文献：

Pathload: a measurement tool for end-to-end availablebandwidth

http://www.ece.ucdavis.edu/~chuah/classes/EEC274/refs/02JD-pathload.pdf