IP网带宽测量技术研究与进展

第7期2006年7月电 子 学 报AC TA ELECTRON I CA SI N ICAVo.l34 N o.7Ju l y 2006I P网带宽测量技术研究与进展韦安明,王洪波,林 宇,程时端(北京邮电大学网络与交换国家重点实验室,北京100876)摘 要: 网络带宽表征网络传输信息的能力,是衡量网络服务质量的重要指标.本文在分析I P网带宽测量的重要作用及其技术分类的基础上给出了链路/路径带宽、可用带宽、批量数据传输能力等测度定义,系统总结了当前最具代表性的各种I P网带宽测量技术,剖析了它们的内在机理及各自优缺点,同时介绍了多种对应的开源带宽测量工具,并对影响带宽测量收敛速度、准确度的因素进行了讨论,最后对带宽测量的应用前景和研究趋势进行了展望.关键词: 带宽测量;链路带宽;路径带宽;可用带宽;批量数据传输能力中图分类号: TN393 1 文献标识码: A 文章编号: 0372 2112(2006)07 1301 10The A chieve m ents of Band w i dth M easure m ent T echn i ques i n IP N et w orksW E I An m i n g,W ANG H ong bo,L I N Y u,CHENG Shi duan(S t a te Key Labo ra t ory o fNet w ork i ng and Sw itching,B eiji ng Un i versit y o f Po s ts&Telecomm un i cation s,B eiji ng100876,C h i na)Abst ract: B andw i dth is them etri c used to describe the net w or k infor m ati on tr ansfer capacity.It is an i m porta n t m easur e to eval uat e the quality of ser v ices in a net w or k.Th is paper e m phasizes the i m po rta n ce and cl assif i es the tec h niques of bandw i d t h m easur e m e n t for I P net w orks.It g i ves the def i n iti ons of m easures,such as li nk/pat h ba nd w idth,a vaila b le bandw i dth a nd bu l k data tra n sfer capacity,and anal yzes the p ri nciples and m erits of typical bandw i d t h m easur e m ent techn iques.It also i ntr oduces several correspond i ng open source too ls for these m easur e m e n ts.and disc u sses the m ai n factors w h i ch i m pact them easuring c onstri ngency s peed a nd acc uracy.It f i nall y g ives a v i e w o f further r esearch and a pp lication trend s i n t h is area.Key w ords: ba ndw idth m easur e m en;t li nk capacity;path capacity;avail ab le band w i d t h;bulk tr ansfer capacity1 引言在I P网中,带宽指的是链路或者路径的数据传输速率[1],用比特率度量其大小.网络带宽则是表征网络信息传输能力的测度(m etric),是反映网络服务质量(Quality of Ser v ice)的重要参数.例如在FTP(Fil e T ransfer Pr o t ocol)、P2P(Peer to Peer)等大量数据交换应用中,充足、稳定的网络带宽是Q oS得到保证的前提;网络多媒体应用需要根据可用带宽大小自动调整压缩码率,带宽大小直接影响音、视频效果;当用户从网络运营商购买了网络服务后,需要按照实际获得的带宽进行付费;网络运营商和用户签订服务等级合约(Service L evel A gr ee m ents)要参照运营商提供的网络带宽;网络拥塞检测、故障诊断、监测,流量工程,升级规划,以及运营商之间的对等连接服务[2]都需要了解网络带宽状况,这些应用都离不开带宽测量技术的支持.由于I n ter net是一个不断增长的、分布化(D istri bu ti ve)、不协作(Uncooperati ve)、异质(H eterogeneou s)的网络[3],具有诸多不确定因素,例如流量具有时变、突发的特征;端到端路由除了呈现非对称性(A sy mm etrical)外,还存在摆动(F la p)、中断(Ou tage)等不稳定现象[4,5];I P协议的设计者未考虑端到端性能分析的需要,没有为端到端性能分析提供控制通道,甚至连获取网络内部状态信息的基本手段都尚未提供[6,7];运营商基于保密和竞争的需要也没有为普通用户公开其网络内部的运行信息,从端主机进行的带宽测量不得不采用复杂的实现机制,通过端主机和节点路由器、端主机之间的紧密合作和进行大量的分析计算来完成测量任务.基于 简单网络,智能边缘的网络设计思想,带宽测量的目标是在缺少节点路由器协作的情况收稿日期:2005 10 12;修回日期:2006 5 15基金项目:国家自然科学基金(N o.90604019,60472067,60502037),973国家重点基础研究发展规划(N o.2006CB701306,2003CB314806),中国下一代互联网示范工程(N G I 04 8 1D).下,通过边缘主机对流经端到端路径的探测包进行时延特征分析,估测得出网络带宽的各个测度值.鉴于带宽测量的重要性,其获得了广泛、深入的研究.依据不同的划分标准,可对带宽测量技术进行分类:(1)按是否向网络内部注入探测包,可分为被动测量(PassiveM easure m ent)和主动测量(A ctive M easure m ent)技术.文献[8~10]研究了被动测量方式,但大多数带宽测量技术采用主动测量方式.主动测量中源主机首先按某种规律初始化探测包序列,然后将其顺序注入网络.探测包到达目的主机时,其间隔由于受传输时延、缓冲排队、流量整形、分组顺序重排[11]等因素的影响而发生改变.目的主机正是基于探测包中包间隔变化所携带的信息来估测网络带宽.主动测量技术的优点是可以灵活设计探测包的性状特征,按探测包结构分类有单包模型、包串模型、等长包对模型和非等长包对模型等;按探测包的发送形式,可以分为单播模型、组播模型,其缺点是向网络内部注入的探测包给网络带来了额外流量负载,轻者影响测量精度,重者影响网络的正常使用.(2)按测量过程是否需要节点路由器的协作,带宽测量技术可分为逐跳的链路带宽测量和端到端的路径带宽测量方式.链路带宽测量常用的方法是将UD P探测包的TTL(T i m e To L ife)值逐跳加一后注入网络,节点路由器在丢弃TTL为0的探测包后立即返回I CM P应答包,通过分析I CM P应答包到达时间和探测包发送时间的差值(RTT R ound T ri p T i m e)的特征可以估测出带宽;路径带宽测量通常不需要节点路由器的参与,直接由源、目的主机相配合完成测量.(3)按不同的测度,带宽测量可分为链路带宽(L i nkC apacit y)、路径带宽(Path C apacity)、可用带宽(A vailab l e B a ndw idth)和批量数据传输能力(BTC B ul k T ransfer C a pacity)测量技术.本文将按照此分类方法对若干带宽测量技术进行阐述,在第2节给出带宽测量测度定义,第3节介绍相关测量技术,第4节简单论述带宽测量技术的应用并就其未来发展趋势做了展望.2 测度定义2 1 链路/路径带宽链路带宽指网络层提供的最大数据传输能力.文献[1]给出了一种链路带宽定义,图1中,路由器Ri 到Ri+1称为一跳(hop),Ri 与Ri+1之间的网络层数据传输能力为C!i,称为第i跳链路带宽.R i到R i+1的一跳可由多个位于数据链路层的交换机或桥接器连接而成,称为段(seg m e n t).数据链路层通常以恒定的速率收发数据帧,例如10/100M bps以太网、2 048M bps E1线路均指数据链路层速率,其大小仅受传输媒介和收发器特性的影响,但该速率并非就是链路带宽.计算链路带宽需要考虑数据包(Packe,t网络层传输单位)封装成帧(Fr a m e,数据链路层传输单位)过程产生的额外协议字开销,其表达式形如式(1),其中C i为第i跳链路带宽,L L3为网络层待发数据包长度,H L2为数据链路层成帧过程的协议开销,C L2为数据链路层速率.可见链路带宽Ci与HL2和LL3之比有关,而HL2一般为常数,故实践中往往增加LL3以增大Ci,例如以太网发送M TU长度包可使链路带宽C i取得最大值.Ci=CL211+HL2LL3(1)路径(pat h)指源到目的的一条端到端数据通路,由一系列存储转发交换和路由节点构成,是多跳链路的集合.路径带宽则指零背景流量、无多径转发情况下端到端数据通路网络层的数据传输能力,例如一条由n跳链路构成的路径,路径带宽由最小链路带宽决定,表达式为Cp=m in{Ci,i=1,∀,n}.2 2 可用带宽另外在各种文献中,术语瓶颈链路(Bo ttle nec k L ink)不仅经常被用于指路径中具有最小带宽的链路,还被用于指具有最小可用带宽的链路,易造成误解,故引入术语狭窄链路(N arro w L ink)、紧凑链路(T igh t L i nk)以示区别.对于由n跳链路构成的路径,链路容量集合为{Ci,i=1,∀,n},链路可用带宽集合为{Ai,i=1,∀,n},狭窄链路指路径上具有最小链路带宽的那跳链路,其链路带宽表示为C NL= m in{C i,i=1,∀,n};紧凑链路指路径上具有最小可用带宽的那跳链路,其链路带宽表示为CTL={Ci,W henA i(i=1,∀,n)is m in i m um};1302电 子 学 报 2006年瓶颈链路专指同时具有狭窄链路和紧凑链路属性的那跳链路,瓶颈链路带宽C BL =C NL =C TL .按照定义,端到端路径中不一定存在瓶颈链路,图2[1]为一条没有瓶颈链路的路径拓扑示意图,1为狭窄链路,3为紧凑链路,瓶颈链路不存在.2 3 批量数据传输能力UDP 和TCP 是I P 网应用最广的两个传输层协议,更有90%的数据交换通过TC P 进行[15],其吞吐能力成为衡量网络性能的重要指标.由于TC P 实现机制[16,17]、参数选择[18]等因素的影响,精确测量TC P 吞吐能力十分困难.I ETF 提出了批量数据传输能力(BTC )概念以衡量网络吞吐能力.BTC 度量单个具有拥塞控制功能传输协议进行批量数据传输的能力.文献[19]对BTC 定义为在不可靠网络路径上,单个TCP 连接在时间间隔t 内可达到的最大平均数据传输速率.由于I ETF 认可多种传输层拥塞控制协议,故不能以某种既定的方法量化BTC.BTC 测量结果可靠、一致、可比的前提是源、目的主机传输层协议采用相同的拥塞控制算法.由于编码的历史继承性,I P 网广泛采用的TC P 协议的拥塞控制算法绝大多数源于文献[20,21].文献[19]给出了BTC 计算公式:BTC =D /t ,其中D 为已发送且可靠到达对端的数据总量,不包含协议帧封装时的字节开销,超时、错误重传的数据量只计算一次.文献[1,19]还讨论了影响BTC 测量的诸多因素,包括传输数据包的大小、无流控的UD P 流量、并发的多个TC P 连接、TCP 应答包所经路径的拥堵状况、TC P 收发两端套接字缓冲区大小、路由器缓冲大小、路径各跳链路的负载大小、TC P 实现的区别甚至TCP 初始窗口都会影响BTC 测量结果.3 带宽测量技术经过多年研究衍生出了多种测量算法,但由于拓扑和流量行为的复杂性,这些算法的实现都建立在测量周期T 中端到端路径P 的路由保持稳定,背景流量服从某种分布模型的假设之上,但不少研究[22~25]关注路由和背景流量动态变化给测量带来的噪声以提高算法的鲁棒性(r obust ness)和精度(accur ac y).3 1 链路/路径带宽测量技术总的来说,链路/路径带宽测量技术及工具都是通过向网络注入主动探测包以获取网络时延特性,并通过特定的模型估测出带宽.3 1 1 链路带宽测量技术单包模型是最早的链路带宽测量技术,它首先由文献[38]所提出,但文献[38]是从应用层估测链路带宽,测量结果容易受到端主机性能的影响.由Jacob s on 完成的测量工具Pathc har [30]是单包模型应用的典范,文献[28~30,32,34]提出的链路带宽测量技术都是改进的单包模型.单包模型可用图3表示,探测包的第一个比特从链路0发出到最后一个比特到达链路i 的时刻可用式(2)表示,d 0i=d 00+#i-1j=0s 0b j+q 0j +l j (2)其中d xi 表示探测包x 到达链路i 的时刻,s x表示探测包x 的长度,b j 表示链路j 的带宽,sxb j 表示探测包x 在链路j 上的传输时延,由探测包长和链路带宽决定,q 0j 为探测包x 在链路j 的排队时延,受背景流量影响,l j 表示探测包经过链路j 时所经历的等待时间,由媒介传播时延、路由表查找时间等组成,独立于探测包长度,为一常数值.对于单包模型,取x =0表示第1个探测包(也仅有一个探测包).考察背景流量很小的情况,q 0j 可以忽略不计.l j 为定值,只与媒介电气特性有关,d x i 可认为是探测包长度的线性函数.单包模型基于这样一个假设:向链路中为注入n 个长度为s 0l 的探测包(n 越大测量结果越精确,收敛时间也越长,占用网络带宽亦越大),至少有一个探测包的排队时延q 0j 可以忽略不计,得到该长度探测包组时延最小值,见图4中的纵轴散列点的下点.分别取l =1,∀,n,且令s 0l <s 0l+1,则由于链路转发时延的增加,得到n 个散列下点.对这n 个下点做线性拟合,得到一条直线,如图4,其斜率的倒数即为链路带宽.单包模型实现简单,不需要源、目的主机的协作即可完成链路带宽的测量,由于每次测量发送的是n 个探测包,而结果只取其中的最小时延值,减小了背景流量噪声对测量结果的影响.但单包模型依赖于I CM P ,出于安全和性能的原因,某些路由器却限制I CM P 的使用[43],致使测量失败,同时它有只适用于单向测量、误差累积、收敛1303第 7 期韦安明:IP 网带宽测量技术研究与进展慢[31,35]、带宽消耗大[23]等缺点.可见其缺乏速度、精度、灵活度.基于Pathchar 的改进方法[28,29,32,34]对单包模型的各个方面做了改进.文献[29]提高了Pathc har 的速度、精度,减小了探测流量.C link [34]与Pat hchar 不同的是它采用一种 奇偶 技术以产生交叉的链路带宽估测结果,当测量过程中路由不稳定时,C li nk 会跟随路由的变化,对使用每条路径进行跟踪测量,并采集相关的测量数据,直到其跟踪路径的测量数据满足统计需求.Pca h r [32]在Pat hchar 的基础上提供了三种不同的线性回归算法来获得链路带宽估值,且支持不同类型的探测包,在指定精度要求下动态调整测量次数.B i ng [28]和Pathc har 有相似的工作原理.为了克服单包模型的缺点,文献[8,31]提出了PT (Packet Tail gati ng)模型.其基本思想如下,对于链路i ,PT 模型向路径中注入两个连续的探测包,且第一个探测包的TTL 值为i 、长度远大于第二个探测包,即s 0 s 1.由于第二个探测包的传输时延s1b i 远小于第一个探测包的传输时延sb j ,保证了第二个探测包总是排于第一个探测包后.在链路j ,由于TTL 值耗尽,第一个探测包被路由器丢弃,而第二个探测包继续无排队地到达目的主机.依次递增TTL 值,可以得到任何链路的时延,从而可估算出链路带宽.PT 模型是文献[31]提出的多包模型的特例,如图5所示.对于n 跳链路,PT 模型的第二个探测包从链路0出发到达链路n 的时刻用式(3)表示,d x n =d x 0+#n 1j =0s xb j+l j +m ax(0,d x 1j+1-l j -d xj )(3)为了便于理解,用三阶段法将式(3)表示成式(4),d x n =[d x 0+#i 1j=0s x b j +l j ]+s x b i+d x 1i+1-d xi +#n-1j=i+1sxb j +d j(4)中括号内的式子依次表示探测包到达链路i 前时延、链路i 上转发时延、链路i 后时延.通过简化,链路的带宽由式(5)计算,式(5)中参量b n 1和l n 1在PT 模型的sig m a 阶段采用Pathchar 方法测出,其余参量由tailgati ng 阶段测量得到[31].x 15)P T 模型采用非路由器协作方式,摆脱了I CM P 的限制,以很少的探测流量获得和单包模型同等的测量精度,同时可以测量多通道链路(m ulti cha nnel li nk)网络环境,但PT 模型并未解决多链路误差累积问题.netti m er [8,31]链路带宽测量工具的实现就是基于PT 模型.文献[44]提出的方法类似于PT 模型,但不丢弃前包,而是利用探测包对沿路记录时戳,得到各跳链路的时延参数.文献[26]用前后两个包对(共4个探测包)的方式构造探测包串,以时延抖动分析代替了单包时延分析,重点考察背景流量引入的噪声,提出了类似Pat hchar 的ACC S I G 方法,但还是没能脱离I CM P 的支持.基于ACC S I G,文献[26]进一步提出了P Q 方法,它不依赖于I CM P ,避免了I CM P 包返回源主机过程引入的噪声.3 1 2 路径带宽测量技术应用最为广泛的路径带宽测量技术是由Jacob s on 等最早在文献[20]中提出的包对模型[22,40,41],但在研究早期由于缺乏有效滤波手段,时延抖动噪声的存在使得他们只能将包对模型更多地用于路径可用带宽测量[11,39].图6是包对模型的基本工作原理,向由n 跳链路组成的路径中注入背靠背、等长(L )的两个探测包,假设在第i 跳链路入口,探测包间隔为 T i n ,i ,链路单包转发时间为 T s,i .当 T in.i < T s .i 时,在链路上必定引发第二个探测包的排队,在链路出口处包对间隔为 T o ut.i ,且 T ou t .i > T i n .i ;当 T in.i > T s .i 时, T out.i = T i n .i ,包对间隔保持不变.探测包对经过多跳链路以后到达目的主机,包对间隔裂散为 T ou t =m i n i=1,∀,n T o ut.i ,由式(6)可估算出路径带宽.C =LT out(6)B o l o t 等在文献[40]中对包对模型进行扩展,得到的包串模型可用以分析路径时延、丢包特性.它向网络中注入等间距探测包,得到各探测包的RTT ,然后分析相邻探测包RTT 的时间特性得到路径带宽.C arter 等提出的Bp r obe 也采用包对模型[22],扩展了文献[40,41]的工作,克服了文献[40]方法的一些缺点.其本质是从源主机向目的主机发送一串探测包,原理类似于图6,在前向探测(dow n strea m pr obing)过程中包间隔在瓶颈链路处裂散到最大,后向探测(upstr ea m prob i ng)过程传送的是包长很小的I CM P 包,所以包间隔未受影响地传回源主机.理想状态下,包裂散间隔与路径瓶颈带宽成正比.通过对包间隔分布的分析由式(6)计算出路径带宽.1304电 子 学 报 2006年Bp r obe 采用了路由器协作机制(I CM P),只需布署在源主机上,但它是建立在假设路由器采用FI FO 队列、且探测包顺序到达瓶颈链路队列的基础上,对于其他队列、探测包丢失、瓶颈链路下游链路拥塞等情况,测量结果可能不正确.尽管包对模型可有效应用于路径带宽测量,但对网络环境要求较高[22],对路由变动、链路非对称等异常情况仍无能为力.Paxson 在文献[11,39]中指出包乱序分发、时钟粒度粗大、瓶颈链路动态改变及多通道链路等情况的存在限制了包对模型的应用,并提出了PB M 模型.PBM 模型通过调整探测包数、分析柱状图的峰值形态的变化以及采用启发式思维克服了包对模型的上述缺点[11,39],但PBM 实现过于复杂.文献[35,36]在研究包对模型的过程中使用了多个包对的包对串模式,他们发现多个探测包对注入路径后得出的测量结果呈现多峰态分布(见图7),并指出是背景流量的多模态引起了多峰现象,同时还采用分段测量法从多峰中定位正确结果并研究了探测包长度对结果的影响,发现早期研究提出的探测包越长越利于分析的结论不正确;并且发现增加包串中包对个数N 可使重复测量的结果趋于一致,当N 充分大时,测量样点呈现单峰态分布,且峰值收敛于ADR (A sy m ptotic D is persi on R at e),但ADR 并非路径带宽.文献[27]提出的Spr obe 使用TC P 协议的内在机制构造探测包对,可进行路径带宽的双向探测.对于前向探测,其基本思想如图8所示,向目的主机的无效端口发送两个背靠背的TC P 同步包(SYN ),修改SYN 包的长度(通常S YN 包长40B,Spr obe 将其修改为1500B )以使其在瓶颈链路上裂散出大间隔,目的主机TC P 收到无效端口的连接请求后返回复位(RST )包(包长40B ),源主机依收到的两个RST 包间隔即可估算出前向路径瓶颈带宽.对于后向探测,图9描述了其基本思想,在源、目的主机之间建立一条TC P 连接,源主机向目的主机发送H TTP GET 请求(目的主机假设为一W e d Ser ver),在TC P 慢启动阶段,目的主机会向源主机连续发送大小等于拥塞窗口的数据包,当拥塞窗口开启到1500B 时,源主机可将其中两个先后到达的数据包作为探测包对.SPr obe 解决了之前包对模型发送的探测包占用带宽过多的问题,但它局限于TC P 传输层协议,且无法穿越网络防火墙,后向探测还需要双端协作,给布署带来了困难.文献[24]提出的C apPr obe 方法更是综合分析了包对时延、包对间隔等因素,可有效剔除由背景流量引起的失真样本.在同等精度条件下,C apProbe 的收敛性能比Pathchar [30]和Pat h r ate [42]更好.链路/路径带宽测量过程会遇到非对称链路(AD SL ,卫星链路)的情况,会给双向探测带来困难.多数带宽测量方法只能完成前向探测,后向探测常常需要双端协作才能完成[27],文献[33,37]对非对称链路带宽探测进行了研究.3 2 可用带宽测量技术基于包对模型[20,40,41]和公平调度队列(Fair Q ueu i ng),K eshav 最早在文献[41]中进行了端到端可用带宽测量的尝试.而包串模型[22,45]对包对模型进行了扩展,其机理是向目的主机连续发送n 个长度为L 的探测包,然后由目的主机返回n 个长度为l 的应答包,且L l ,应用式A =(n*L )/T 得可用带宽,式中T 为源主机接受应答包所需的总时间.文献[22]提出的C pr obe 工具不局限于公平调度队列,文献[45]提出的P i pec har 和C p r obe 相似,但它们都被文献[35]证明测量到的不是真正的可用带宽,而是ADR (A sy m ptotic D ispersion Rate).之前尚未见到可精确估测每跳链路可用带宽的算法,文献[46]提出的基于RPT (Recursive Pac ket T rai n)的Pathnec k 工具也仅可粗略估测每跳链路的可用带宽的上限或者下限,因此本文只介绍端到端路径可用带宽测量方法.常见的可用带宽测量技术依探测方式可划分为直接探测[13,47,48]和迭代探测[13,14,47,49,50~53]两大类.3 2 1 直接探测P GM (Pr obe G ap M odel)模型是直接探测(D irect Pr o b i ng)的一种,它通过考察探测包对间隔变化来估测可用带宽,其基本方法如图10所示,源主机以速率R i 发送探测包串,探测包串到达目的主机的速率为R 0,可用带宽A 可由式(7)计算,A =C TL -R iC TLR 0-1,当R i >A (7)取{R i ,i=1,∀,n}进行n 次测量,得样本集{A i ,i=1,∀,n}.P GM模型实现简单易行、计算复杂度低,但只在R i >A 时成立.应用P GM 模型的前提是紧凑链路带宽C TL 为已知值,由紧1305第 7 期韦安明:IP 网带宽测量技术研究与进展凑链路定义可知其位置取决于各链路背景流量的大小,例如t 0时刻链路i 是紧凑的,但t 1时刻各跳链路的背景流量已经发生变化,链路j j ∃1可能取代成为新的紧凑链路.可见该条件并不易满足,尤其在广域网中P GM 模型的应用难度更大.文献[22]提供的B pr obe 可作为P GM 模型的前端,由它先行探测出路径的紧凑链路及其带宽.文献[48]提出的基于模型(M odel B ased)的D elph i 是另外一种直接探测方法,与之前的方法不同,D el phi 应用MWM (M u ltifractalW avel etM odel)[54]对背景流量进行建模,从而估测出路径可用带宽.文献[13]提出的I G I 方法虽然计算公式形似直接探测法,但测量过程则类似于下文阐述的迭代探测法.文献[47]提出的Spruce 方法构建探测包对串的方法与上述采用的等间距(指各包对之间的间距,而不是包对内部的间距)包对法稍有不同,如图11所示,它使用100个等间距包对,但包对与包对之间间隔 i n ter pa ir 服从指数分布,因此各包对到达目的主机的过程是一个泊松过程(Po iss on Pr ocess),包对到达事件相互独立.该方法的优点是包对之间的间距 i n ter pa ir 、包对内间距 i n tr a pa ir 是独立的,可根据需要调整,使背景流量对 i n tra pa ir 的影响减小,达到提高精度的目的.文献[55]的研究表明,相比于Pat h load 、D el ph i 和I G I ,Spruce 有更高的精度,探测包耗费的网络带宽更小,且实现更简单.3 2 2 迭代探测迭代探测的基本思路是用高速探测流量人为地制造路径拥塞,然后得到可用带宽.文献[13,14][47][49~52]实现的迭代探测(Iterative Prob i ng)都基于这个基本思路,向网络注入速率为R i 的突发包对串,当包对速率大于可用带宽时,路径发生瞬间拥塞,探测包间的时序关系发生改变,分析探测包的时延特征即可估测出路径可用带宽.由于可用带宽未知,测量过程实际上是包对速率不断变化的迭代过程,因此迭代探测也称为P R M (Pr obe R ate M odel)模型.与P GM 模型不同,迭代探测并不要求紧凑链路带宽C TL 为已知值,包对速率R i 可以是线性变化或按某种函数规律变化.P R M 测量过程采用如下判定条件,当测得R 0<R i 时,认为R i >A;当测得R 0=R i 时,认为R i %A;不可能出现R 0>R i .改变R i 进行迭代探测,找到R 0=R i 临界点,最终得到路径可用带宽A.M el ander 等于文献[49,52]中提出的ToPP (T rain o f Pac ket Pairs)方法是P RM 的典型代表,ToPP 以递增的速率向目的主机发送多个探测包对串(见图12、图13),每个包对串由n 个间隔为 T inter pa ir 的包对组成,包对内两个包间隔 T i n t r a pa ir 亦相等,改变包对速率指的是改变 T int r a pa ir ,例如图12中有t a>t b>t c,包对速率用式R i =L / T i n t ra pa ir 表示.由于需要进行迭代探测,P R M 模型在测量开始前先设定一个可用带宽分布域[R m in i ,R m axi ]作为包对速率递增的上、下限.当包对速率R i 以 R 递增时,迭代次数即为N =(R m axi-R m ini)/ R 次.假设链路j 处理长度为L的探测包的时间为 T s .j ,链路入口处包对到达间隔为 T int r a pa ir .i .j (i 表示第i 次探测),则当满足条件 T s .j > T int r a pa ir .i .j 时,链路出口处包对间隔裂散为 T s.j ,有 T int r a pa ir .i .j+1= T s .j .对测量结果做均值滤波,得包对间隔均值avg ( T intra pa ir.i )=#nj=1T intra pa ir.i.j ,通过式A i =L /avg( T int r a pa ir .i )计算链路可用带宽;如果 T s .j % T int r a pa ir .i .j ,则链路出口处包对间隔保持不变.由于只有当探测包对速率R i 大于链路可用带宽A 时,包对间隔才会裂散,故增大探测包对发送速率的过程就是发现具有相应可用带宽链路的过程,N 次探测的结果可能发现路径中的多跳拥塞链路.对于N 次测量结果集合{(R i ,A i )i=1,∀,N},使用式R i /A i = + R i 运用线性回归方法得到路径可用带宽,式 , 中为与路径容量及背景流量值相关的常系数.ToPP 方法的优点是其仅用很小的探测流量就可完成可用带宽的估测,同时可以探测到路径中的多个拥塞链路,图15为具有三段拥塞链路的可用带宽测量结果,但它需要双端布署、只能对单向路径进行测量,并且假设路径转发节点采用FCFS(F irst C o m e First Ser ve)及队尾随机丢包策略,对于其他策略则不一定成立.另外在背景流1306电 子 学 报 2006年。