自适应的端到端可用带宽测量方法.doc

第12期周安福等：自适应的端到端可用带宽测量方法45自适应的端到端可用带宽测量方法周安福，刘敏，李忠诚，谢高岗(中国科学院 计算技术研究所，北京 100190)摘 要：提出了一种轻负载的、自适应的端到端可用带宽测量方法。在低负载链路下，计算探测包对距离增大的概率，结合输出探测包距离分布，得到可用带宽。在此基础上通过探测包输出包距离对称度区分链路负载情况，自适应地采用合适的可用带宽计算方法。仿真实验表明，相比之前方法，本方法测量时间少、准确性高、测量开销小。关键词：网络测量；可用带宽；主动探测；包距离模型 中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)12-0037-09Self adaptive method for end-to-end available bandwidth estimationZHOU An-fu, LIU Min, LI Zhong-cheng, XIE Gao-gang(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China)Abstract: A low overhead, self adaptive method for end-to-end available bandwidth estimation was proposed. Firstly, on low utilization path, the mathematic equation between the probability that input probe gap increases caused by CT packets and the distribution of output probe gap was set up, and then CT load was derived from the equation. Secondly, a metric called gap symmetry (GS) was proposed to weigh the busyness degree of a network path, and the self adaptive available bandwidth estimation method based on GS was presented. NS-2 simulations show that compared with previous methods, our method shows its advantages in terms of measurement time, accuracy, and overhead. Key words: network measurement; available bandwidth; active probing; probe gap model1 引言收稿日期：2008-08-09；修回日期：2008-11-20基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB310702）Foundation Item: The National Basic Research Program of China (973 Program) (2007CB310702)可用带宽（AB, available bandwidth）是衡量网络性能的一个重要参数，在许多互联网应用中起到关键作用，如覆盖网络路由1，自适应流传输2，服务质量控制3和网络故障检测4等。目前存在多种可用带宽测量方法，根据文献5中的分类方法可分为两类：第一类方法基于包速率模型（PRM），包括Topp6、Pathload7、Pathchirp8、PTR9；第二类方法基于包距离模型（PGM），包括Delphi10、IGI9和Spruce5。PRM方法的基本思想是：发送一系列速率不等的探测包队列，当发送速率高于可用带宽时，探测包的单向延迟存在上升的趋势。PRM方法根据单向延迟上升时刻对应的探测包速率来估算可用带宽。PRM方法虽然具备较高的准确性，但会消耗所有的可用带宽资源，造成网络阻塞。PGM方法使用速率固定的探测包对，通过探测包的输入包对距离和输出包对距离间的数学关系来推算可用带宽。这类方法需要“忙假设”（BA，busy assumption）前提条件，即探测包对必须落在路由器上的同一个忙碌时间段。在本文称BA条件下的测量方法为“忙测量”（BE, busy estimation）。显然，当网络负载较低时，BA通常不成立，因此Delphi在低负载网络路径上的测量并不准确10。IGI和Spruce分别对Delphi方法做了改进，采用特别的探测包发送机制以满足BA。然而，这些改进方法带来了负面效果：IGI耗费大量的网络带宽，Spruce非常有侵略性5。在现有技术分析中本文将进一步的介绍PGM方法。另外，也有文献对可用带宽测量进行了深入的理论分析1115。文献11,12,15对突发数据流情况下探测包距离所包含的信息进行了深入的统计分析。文献13研究如何测量背景流的分布规律。文献14基于takas integro-differential方程对包距离进行了模型化的分析。本文研究忙假设不成立的情况下的网络可用带宽测量方法。首先，对PGM模型进行详细的分析，提出了一种在“非忙假设”（NBA，non busy assumption）的条件下的可用带宽测量方法，称之为“非忙测量”（NBE，non busy estimation）。NBE的基本思想是：计算背景流（CT，cross traffic）造成探测包对的包距离增大的概率，建立该概率值与输出探测包距离分布的数学关系式，通过对该式的计算得到可用带宽。仿真结果表明，NBE在低利负载网络路径上的测量结果非常准确。再者，提出了一种新的度量单位包距离对称度（GS，gap symmetry），以衡量所探测网络路径的负载程度。GS的提出基于一个新的发现：当链路负载较低时，探测包输出包距离的分布呈现高度的对称性；随着链路负载程度的增加，这种对称性逐步降低。最后，根据GS结合NBE与BE，提出了一种新的可用带宽测量方法A_ABE（adaptive available bandwidth estimation）。本文使用NS-216仿真实验验证A_ABE，实验中的CT来自于在互联网上收集的真实数据的回放。与以前的方法相比，A_ABE在准确性、测量时间、测量开销上都存在着较大优势。2 现有技术分析2.1 基本概念网络传输路径由从数据源到目的地的一系列存储转发链路所组成。链路的带宽值是该链路上数据报文的最大传输速率，网络路径的瓶颈带宽（bottleneck bandwidth）是源节点到目的节点间的处理能力最低的链路传输速率。以w表示一条网络路径的跳数，用表示链路i（）的带宽，那么该路径的瓶颈带宽可以表示为：。如果用（）表示链路i的利用率，那么链路i上的可用带宽可以表示为，整条路径的可用带宽为：。包距离（也称包间距）指的是两个数据包间的时间间隔，以表示探测包在发送时的包距离，称之为输入包距离，以表示探测包到达接收方时的包距离，称之为输出包距离。探测包的包大小用表示，则探测包在瓶颈链路上的传输时间为。2.2 PGMPGM方法假设网络路径的拥塞只发生在瓶颈链路上，即瓶颈链路的可用带宽为整个网络路径的可用带宽，包距离的改变也只发生在瓶颈链路上。PGM方法的前提条件是忙假设BA：两个连续的探测包（探测包对）必须落在瓶颈链路的同一忙碌期，即在一对探测包中的第一个包离开链路至第二个包到达链路的时间段内，链路必须一直处于忙的状态5。在BA假设条件下，在第一个包离开至第二个包到达的时间内，链路一直在传输背景流，传输时间为，因此这段时间内的背景流速率为(1)则可用带宽为(2)为使BA成立，探测包的速率通常需要特殊的设定。IGI的研究表明，当探测包的输出包距离平均值与输入包距离相等时，能取得较好的测量效果。同时，为了提高准确度，IGI使用了包含n+1个数据包的包队列（包含n个包间距），并把式（2）改进为(3)其中，表示大于的的值（设有m个），其集合表示为。然而，文献8中的研究表明，IGI包队列耗尽了所探测网络路径的可用带宽，造成网络拥塞和严重的丢包。在另外一个基于PGM的探测方法Spruce中，发送方以瓶颈带宽的速率发送大小为1 500byte的探测包对，这保证了“忙假设”条件的成立。Spruce使用式(2)计算可用带宽，为提高准确度，Spruce发送由100个包对组成的包队列，取其平均值。包对间的距离被设定服从指数分布以满足PASTA性质5。分析表明，Spruce占用的带宽约为瓶颈带宽的5%，远小于IGI。文献17的研究表明，Spruce的这种大探测数据包对CT造成的影响较大，并且对于探测包的发送方来说，其主机需要支持瓶颈带宽的网络速度。3 NBE3.1 NBE的推导在本节中，提出低负载链路上的可用带宽测量方法，称为非忙测量。如图1所示，NBE发送包队列探测网络路径，探测包的输入间距满足式（4）(在3.2节中将对输入包间距的设置做出解释)。(4)图1 NBE方法假设低负载链路的CT包到达过程满足如下NBA假设。在两个连续的探测包间距内，到达的CT包数目不大于1（即没有或只有一个CT包），如果在某一探测包间距内有CT包到达，则其到达时间的概率分布是一个0，间的平均分布。如图1中，在与间或与间，不能有多于1个CT包，的到达时间分布为与间的平均分布。以数据包的大小对CT包进行分类，假设有种数据包，第j种数据包的长度用表示，包数目在CT包中所占比例用Pj表示()。现在，计算探测包经过瓶颈链路时，包距离增大的概率。定义Ppgi=Pa probe gap increasesPctpa=Pa cross traffic packet arrives during a probe gapPpgi|ctpa=Prrobe gap increases |a cross traffic packet arrives during the gap由条件概率理论，可得Ppgi = Ppgi|ctpaPctpa(5)探测包距离的改变由CT包的大小及其到达时间决定。当CT包到达时间与下一个探测包到达时间的间隔小于该CT包在链路上的传输时间时，探测包距离才会增大。以为例，设包长度为，则在瓶颈链路上的传输时间为，可见只有当的到达时间落在时间区域，（称之为delay area）内，探测包距离才会增大（才会大于）。根据非忙假设，的到达时间分布为与间的平均分布，所以的到达时间落在delay area的概率为，再乘以，则得到第j种CT包造成探测包间距增大的概率，对所有k种CT包取和，得到Ppgi|etpa(6)则Ppgi为(7)在第2节中，定义了表示大于的输出探测包距离的集合，则对于一个探测包队列，包距离增大的频率为(8)其中，n代表包距离的个数（n+1为包队列的探测包数目）。在式（9）和式（10）间建立等式，有(9)做一个简单的变形，有(10)可见，式(10)左边为背景流在时间段内的平均值，则可用带宽为(11)3.2 探测包间距和探测包大小在本节内讨论探测包间距和探测包大小的取值。如式（4）要求，NBE要求探测包输入间距必须不小于。这是因为，只有这样设置，才能使式（11）的推导过程成立。假如设置(L1 500byte)，则对于长度大于L的数据包，其造成探测包距离增大的概率，不符合概率的基本要求，因而后续的推导过程将都不成立。同时，也不能设置的太大，因为随着的增大，对于同样的背景流负载，非忙假设条件将越来难以满足，从而造成NBE的实效。综上，设置(12)从式（11）易知，探测包的大小不会影响NBE测量结果。因此，可取任意的值。本文设置为互联网上最小数据包的长度，以尽可能地减小网络测量本身对网络链路的影响。3.3 NBE仿真试验NBE的推导基于非忙假设。当链路负载增大时，非忙假设条件将难以满足，NBE测量也将不准确。本节以NS-2仿真说明NBE在低负载链路上的准确性，及NBE在高负载链路上的局限性。仿真拓扑如图2所示，探测包从Ps发往Pd，背景流从Cs发往Cd，瓶颈链路设置为R1与R2之间，瓶颈带宽设置为10Mbit/s。在第一组试验中，设置背景流为一个UDP流，数据包大小为1 200byte，数据包的到达时间分布为0，间的平均分布，称这种背景流设置为NS-2 setting-1。可见，NS-2 setting-1较好地符合非忙假设，对NBE来说是较理想的背景流。改变背景流的包间距，使得背景流的占用带宽从1Mbit/s增长到9Mbit/s。图3给出了试验结果，从中可以看出，当背景流小于5Mbit/s时，NBE的测量结果很准确；当背景流大于5Mbit/s时，NBE低估了可用带宽。图2 NBE仿真拓扑图3 NS-2 Setting-1仿真结果在第二组实验中，背景流由3条到达过程服从Poisson分布的UDP流组成，包大小分别为40byte、500byte和1 500byte，称这种背景流设置为NS-2 setting-2。背景流大小从1Mbit/s增大至9Mbit/s。NBE的测量结果如图4所示，与第一组实验结果类似，随着背景流的增大，NBE逐渐失去准确性。不同的是，这一次NBE的准确与否的拐点在2Mbit/s。图4 NS-2 Setting-2仿真结果从上述两组实验结果可以看出，非忙假设条件的成立不完全取决于背景流的大小，也取决于背景流数据的分布情况。因此，一个固定的背景流值不是用来判断非忙假设成立的依据。在下一节中，将提出了一个新的度量单位包距离对称度，来衡量所探测网络路径的忙碌程度，以判断非忙假设是否成立。4 包距离对称度与自适应的可用带宽测量4.1 包距离对称度首先分析CT包导致探测包距离的变化情况，以此为启发，给出包距离对称度。以图1中的两个探测包距离（至，至）为例，定义 (13)则输出包距离为(14)(15)由式(14)和式(15)得(16)可见，如果以为基准点，则两个连续的输出探测包距离对称的。推广至包队列中的所有包距离，则知：以为基准线，输出包距离的分布函数是对称的。图5给出了在NS-2 setting-1实验中输出包距离的分布图，容易看出，图5(a)和图5(b)具有高度的对称性，而随着背景流的增加，非忙假设条件逐渐破坏，式（14）不再成立，对称性随之消失。在其他背景流条件下的实验结果也与之符合，限于篇幅不再列出。基于以上发现，本文提出包距离对称度的概念(17)容易看出，随着对称性的破坏而增加，所以，GS的值与包距离的对称性成反比关系，能够有效描述网络对非忙条件的支持程度。实验表明，当GS0.02时，非忙假设条件基本成立，NBE测量结果相当准确。(a) CT=0.5Mbit/s(b) CT=1Mbit/s(c) CT=2Mbit/s (d) CT= 4Mbit/s(e) CT=6Mbit/s(f) CT=8Mbit/s图5 输出包距离分布表1BE和NBE的测量误差率CT /(Mbits-1)BE的EER /%NBE的EER /%0.533.454.21130.3121.523.539.15218.3611.822.512.617.438.6520.843.7627.655.2326.475.8239.0817.545.3918.846.34.2 自适应的可用带宽测量方法以上章节主要论述了NBE适合于非忙链路，GS可以描述链路的忙碌程度。在本节中，讨论NBE的探测方法和BE计算方法的结合，来获取忙链路情况下的可用带宽。根据2.2节，当链路忙时，“忙假设”条件满足，探测包对落在链路同一忙碌期的概率很大，因此式（2）成立，BE能取得准确的测量结果。下面，以仿真实验来观察在NBE的探测包发送模式下，BE的测量结果。实验拓扑和背景流情况与NS-2 setting-2实验的设置一样，为更精确地对比NBE与BE的测量结果，定义了EER (estimation error rate，测量误差率)为(18)BE与NBE在不同背景流负载下的EER如表1所示，从表1可以清晰地看到当链路非忙时，NBE测量误差小，当链路忙时，BE测量更准确。根据以上讨论，得到A_ABE算法的大体思路：当链路非忙（GS0.02），A_ABE使用NBE作为计算可用带宽，当链路忙时（GS0.02），A_ABE使用BE计算可用带宽。5 性能评价在本节中，以真实网络数据的回放作为背景流对A_ABE进行性能评价。所使用的3个网络数据集的大致情况如表2所示，普遍认为这些数据集能代表互联网中数据流的动态变化情况，文献17使用这些数据集作为标准测试例测试各种可用带宽测量方法。因为Spruce是单瓶颈链路情况下最准确的可用带宽测量方法之一17，并且是最快的基于包距离的方法，本文将比较A_ABE与Spruce的测量时间、准确性和测量开销。5.1 单跳网络情形在单跳网络情形下，网络拓扑与图2一样。因为表2中的数据都是从容量为1Gbit/s的链路上截获，设置图5中各条链路的带宽也为1Gbit/s，在这样高链路带宽条件下进行可用带宽测量也是对3.3节中低带宽条件下测量的有益补充。.表2网络数据集数据集名称链路类型平均流量/(Mbits-1)IbiblioWeb Server access link167UNC28University access link369KSCYInternet2 backbone link485注：这里的平均流量值与文献17中的值略有不同，因为文献17中的值为整个网络数据集的平均值，本文取数据集前30s平均值。MT（measurement timescale，测量时间）和SI（sampling intensity, 采样密度）是可用带宽测量方法测量的两个重要参数17。因为Spruce和A_ABE都是基于 PGM的方法，它们都只发送一次探测流，所以只用到MT。在下面的实验中，分别取MT为10ms、100ms、500ms，Spruce和A_ABE在表2中不同的数据集和不同的MT下的测量结果如图6图8所示。5.1.1 稳定性和测量时间从图6图8可以看出，在同样的MT值下，Spruce测量结果的取值范围要远大于A_ABE测量结果的取值范围，特别是当MT为10ms或100ms时。这表明在相同的测量时间下，A_ABE要比Spruce稳定。为了更精确地比较稳定性，本文比较这两种测量方法测量误差的Std（standard deviation，标准差），即。在不同数据集和不同MT取值下的和见表3表5。可见，随着MT的增加，两种方法测量误差的Std值随之下降，说明测量结果随着测量时间的增加趋于稳定。而在相同MT取值下，小于 ，说明A_ABE比Spruce稳定。在相(a) MT=10ms(b) MT=100ms(c) MT=500ms图6 Ibibilo测量结果对比(a) MT=10ms(b) MT=100ms(c) MT=500ms图7 UNC28测量结果对比(a) MT=10ms(b) MT= 100ms(c) MT=500ms图8 KSCY测量结果对比同稳定性的要求下，A_ABE所需的测量时间约为Spruce的1/5（MT=100ms条件下的约等于MT=500ms条件下的）。表3Ibibilo测量结果标准差MT/ms1076.9122.61008.036.65004.119.2表4UNC28测量结果标准差MT/ms1030.8110.110016.836.750015.017.3表5KSCY 测量结果标准差 MT/ms1049.6131.110013.745.25009.3 准确性在MT=100ms时间尺度下比较A_ABE与Spruce方法准确度，这两种方法在3个数据集下的测量误差率见表6。可见，A_ABE的测量准确性高于Spruce，尤其是在低速率背景流数据集Ibibilo下。表6 Spruce和A_ABE测量误差率(单跳 MT=100ms)TraceSpruce 的EER/%A_ABE 的EER/%Ibibilo18.43.7UNC288.26.6KSCY7.67.1A_ABE具有一个良好性质是：A_ABE测量方法对背景流的变化十分敏感，能够正确地描述网络背景流的变化趋势与幅度。如图7(c)、图8(c)所示，当背景流曲线在波峰时，A_ABE测量结果曲线也在波峰；当背景流曲线在波谷时，A_ABE测量结果曲线也在波谷。这种趋势在低速率背景流条件下更为明显，如图6(c)所示，A_ABE测量结果曲线与背景流曲线几乎重合。5.1.3 测量开销Spruce方法的发包速率为瓶颈链路带宽的5%5；A_ABE的发包速率为瓶颈链路带宽的2.6% ()。可见，A_ABE的测量开销约为Spruce的1/2。更为重要的是，Spruce的探测包以首尾相接的大包（1 500byte）包对的方式发送，这种发包方式具有相当的侵略性，会对网络背景流造成较大的负面影响17，而A_ABE的探测包很小(40byte)，探测包之间存在较大的间距，因此，其对网络背景流造成的影响非常小。5.2 多跳网络情形多跳网络的仿真拓扑如图9所示，与5.1节一样，链路容量都被设置为Gbit/s，.探测流从Ps发往Pd，测量时间设为100ms。设置两条背景流：从Cs1发往Cd1的称之为CT-1，从Cs2发往Cd2的称之为CT-。在仿真中，CT-1被设置为Ibibilo数据集的回放，CT-2从另外两个数据集中选取。仿真结果如图10、图11所示，图的名称中包含了仿真中CT-2所对应的数据集。从图中可见，A_ABE的测量结果曲线比Spruce测量结果曲线更接近背景流曲线，即A_ABE比Spruce准确度高。为量化两者的测量准确性，给出图10和图11两次测量对应图9 多跳仿真拓扑 的测量误差率，见表7。与表6中的单跳网络测量结果相比，多跳网络下的测量准确性确实受到旁路背景流CT-1的影响，但A_ABE受到的影响要远小于Spruce。表7 Spruce和A_ABE测量误差率(多跳MT=100ms) TraceSpruce的EER/%A_ABE的EER/%UNC2837.917.5KSCY28.26.6图10 多跳仿真(CT-2: UNC28)图11 多跳仿真(CT-2: KSCY)6 结束语在以前的可用带宽测量方法中，“忙假设”是一个普遍要求的条件。为满足“忙假设”，以前的方法需要使用较高的探测包发送速率。本文提出了基于包距离模型的自适应的端到端带宽测量方法A_ABE。A_ABE首次提出了在“非忙假设”条件下的可用带宽测量方法NBE，仿真表明NBE在低负载链路上相当准确。另外，在A_ABE方法的探测包发送方式下，探测包输出包距离分布具备一项有用的性质：当链路负载较低时，输出包距离的分布呈现高度对称性，随着链路负载的增加，包距离分布对称性逐渐降低。基于该性质，提出了一种新的度量GS来衡量当前测量链路的忙碌程度。根据GS的值，A_ABE在不同的忙碌程度的链路下分别使用NBE或BE，从而适应性地测量可用带宽。在NS2仿真实验中，本文采用真实网络数据集回放的方式模拟背景流。实验结果表明，相比其他可用带宽测量方法，A_ABE在准确性、测量时间、测量开销上都存在着较大优势，另外，在多跳网络、旁路背景流存在的情形下，A_ABE方法体现出了较高的健壮性。在下一步的工作中，将在真实网络环境中进行可用带宽测量实验。另外，鉴于A_ABE方法较快的测量速度和较低的探测负载，应将考虑把A_ABE作为一种实时的可用带宽监测工具，用于提高音视频等实时应用的服务质量。参考文献：1ANDERSEN D G, BALAKRISHNAN H, KAASHOEK M F, et al. Resilent overlay networksA. Proc ACM SOSPC. Banff, Alberta, Canada,2001.131-1452CHOU P, MIAO Z. Rate-Distortion Optimized Streaming of Packetized MediaR. Microsoft Reserrch Technical Report MSR-TR_ 2001-35, February 2001.3Real-time SLA monitoring toolsEB/OL. http:/www.nwfusion. com/ news/ tech/2001/0115tech.html,Jan 24, 20084SHRIRAM A, KAUR J. Identifying bottleneck links using distributed end-to-end available bandwidth measurementA. First ISMA Bandwidth Estimation WorkshopC. SanDiego, Californie, USA, 2003.5STRAUSS J, KATABI D, KAASHOEK F. A measurement study of available bandwidth estimation toolsA. Proceedings of ACM SIGCOMM Conference on Internet MeasurementC. Karlsruhe, Germany, 2003.39-44.6MELANDER B, BJORKMAN M, GUNNINGBERG P. A new end-to-end probing and analysis method for estimating bandwidth bottlenecksA. IEEE Global Internet SymposiumC. San Francisco, USA, 2000.415-4207JAIN M, DOVROLIS C. End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughputJ. IEEE/ACM Transactions on Networking, 2003, 11(4): 537-549.8RIBEIRO V, RIEDI R, BARANIUK R, et al. PathChirp: efficient available bandwidth estimation for network path A. Proceedings of Passive and Active Measurements (PAM) WorkshopC. San Diego, CA, USA, 2003.1-11.9HU N, STEENKISTE P. Evaluation and characterization of available bandwidth probing techniquesJ. IEEE Journal on Selected Areas in Communications, 2003,21(6): 879-894.10RIBEIRO V, COATES M, RIEDI R, et al. Multifractal cross-traffic estimationA. Proceedings ITC Specialist Seminar on IP Traffic Measurement, Modeling,