Pathchirp—有效的带宽估计方法（二）

落日映苍穹つ 2021-12-14 00:03 277阅读 0赞

上一个blog介绍了有效带宽估计方法：pathload。[http://blog.csdn.net/ice110956/article/details/11126491][http_blog.csdn.net_ice110956_article_details_11126491]。

做一个小小的总结：pathload用等距离的包序列探测，通过网络延时的趋势来判定是否过载，再用二分法收敛到实际的剩余带宽。Pathload每次的带宽估计大概要5MB左右的探测包，12S的探测时间，虽然探测的准确率较高，但是消耗更大。

下面介绍另一个带宽估计的算法，pathchirp，它用少的多的包来进行探测，对比于pathload,在探测效率上有很大的提升。

基本模型

如下图，pathchirp用一个指数型递增的序列作为探测序列：

![SouthEast][]

这样的一个队列称为一个chirp. pathchirp用m个chirp来平均计算。

每个chirp中，每个包的发送间隔时间为：ΔK。每个包的链路总延时为：qk. 这个包的瞬时发送速率可以如下计算：

![SouthEast 1][]如果qk=qk-1,说明此时的发送速率要小于链路带宽，即![SouthEast 2][]

否则，大于链路带宽。

简单的图形说明如下：

![SouthEast 3][]

那么，我们就可以做如下简单的估计：

链路的瓶颈带宽等于qk开始增加的发送速率。如上图，D在第五个包后开始增长，带宽估计为20s一个包。

模型的优点

1.一个pathchirp通过N个包的序列，得到了N-1个包间隔，而同样要得到这么多间隔，一般的包对方法要用2\*N-2个包，而包序列方法则更多。

2.通过指数级增长，pathchirp包发送带宽从G1增长到GN，只用了\[logG1-logGN\]个包。

3.最重要的优势，pathchirp得到了链路延时中很重要的信息。

加权平均的带宽估计

根据上面所述，在理想状态下，我们只要找到带宽延时的拐点就行了，但是实际并不是这样。

但是由于突发的数据流，导致q并不是单调增长的。如下图：

![SouthEast 4][]

Pathchirp把突然连续地增长视为到了链路瓶颈带宽。图中一小段的上升和下降，pathchirp中认为是突发的数据流导致的，而实际的平稳带宽还是大于发送速率。

那么，我们要如何在有噪声的延时图上面找到实际的瓶颈带宽拐点呢？pathchirp使用一个加权平均的方式来计算真实带宽如下公式：

![SouthEast 5][]

Ek为包k发送时刻的链路估计带宽，Ek=B\[tk,tk+1\],D表示整个包序列chirp的加权带宽。

于是我们的估计再转化为计算每个包对应的带宽估计Ek

Ek直观地理解如下：

![SouthEast 6][]

公式说明，如果链路延时q呈下降趋势，那么此时的带宽要小于发送带宽。其他情况下，发送速率要大于链路瓶颈带宽。

划分离群区间

并不是所有的qk<qk+1我们都能推断链路发生了阻塞。直观上来说就是，只有不断增加的序列，我们才能推断链路发生了阻塞，而偶然的增加并不能说明这个问题。于是我们要划分一个q的离群区间，即增加区间。

Pathchirp的离群区间计算如下，其目的是寻找真实的链路延时开始点和结束点。

每一个qi<qi+1的i都是潜在的离群开始点。离群区间结束点j如下定义：

![SouthEast 7][]

F称为减小参数。

我们再定义一个参数L，j-i>=L时，我们说这个区间满足长度L要求，我们定义他为离群区间。

根据离群区间计算每个包估计带宽

通过上面离群区间的划分，我们划分了如下三种包：

1. 结束离群区间的包：

我们把它的链路带宽定义为自己发送速率。

2．处于离群区间的包：

我们把它的链路带宽定义为离群区间开始包的发送速率。

3.非离群区间的包：

我们把这时的带宽也定义为最后一个离群区间结束的包l的发送速率。

具体的算法

![SouthEast 8][]

![SouthEast 9][]

问题

1.    首先是系统时间的问题。执行pathchirp要求要有很高的时间精度。但是CPU时间等等问题是无法解决的。一个变更方案就是使用网卡的时间戳而不是应用层的时间戳。

2.    还有就是丢包问题，pathchirp把有丢失包的chirp直接丢弃。

效率与准确度

以下对比pathload的效果与准确度：

![SouthEast 10][]

相比pathload,pathchirp使用1/10的包数量，达到比较接近的精度，在一定的环境下有他的优势。

参考文献：pathChirp: Efficient Available BandwidthEstimationfor Network Paths

[http://www.slac.stanford.edu/pubs/slacpubs/9500/slac-pub-9732.pdf][http_www.slac.stanford.edu_pubs_slacpubs_9500_slac-pub-9732.pdf]

转载于:https://www.cnblogs.com/james1207/p/3315349.html

[http_blog.csdn.net_ice110956_article_details_11126491]: http://blog.csdn.net/ice110956/article/details/11126491
[SouthEast]: /images/20211213/a8063a6b1ad14627b2878ff6158e2ed5.png
[SouthEast 1]: https://img-blog.csdn.net/20130911143243718?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaWNlMTEwOTU2/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20211213/971d1b52db1b46e2a112cc434507adca.png
[SouthEast 3]: /images/20211213/f1a38ccd90ce46b391d37adc76f89881.png
[SouthEast 4]: /images/20211213/10b3b49a60d04211a01c7114017ff5a0.png
[SouthEast 5]: /images/20211213/f0593d4119d444d3bac70e1f2a611ecf.png
[SouthEast 6]: /images/20211213/ad7bd6d37dcd4f0988a306c5c550a6f6.png
[SouthEast 7]: /images/20211213/747aefae9e484dc8b02a38e111d57ced.png
[SouthEast 8]: /images/20211213/8b040d1c50af43deb4cb4078ea07b8cf.png
[SouthEast 9]: /images/20211213/74af17ad19ce4e808138bcf1f541fd11.png
[SouthEast 10]: /images/20211213/2156c9388b8a471e875bbeceb1d5465a.png
[http_www.slac.stanford.edu_pubs_slacpubs_9500_slac-pub-9732.pdf]: http://www.slac.stanford.edu/pubs/slacpubs/9500/slac-pub-9732.pdf