一种端到端网络通信路径中瓶颈链路的度量方法

摘要

本发明涉及一种端到端网络通信路径中瓶颈链路的度量方法，包括S1、捕获探测数据包队列在每一个链路上的平均传输间隔，从而确认拥塞链路；S2、度量拥塞链路的容量；S3、计算拥塞链路的可用带宽；S4、在拥塞链路中找出待测路径的瓶颈链路，并输出它的位置、容量和可用带宽信息。通过发送一组探测数据包队列，该组数据包队列从源节点传送到目标节点，跟踪该队列在每一段链路上的内部数据包传输间隔，捕获探测数据包队列在每一个链路上的平均传输间隔即PPD值，确认拥塞链路；在一个度量周期内，获知端到端通信路径中瓶颈链路的位置、可用带宽、带宽物理容量上限；且基于主动探测机制，无需在网络路径的沿途各节点中安装软件，适用范围广泛。

说明书

技术领域

本发明属于计算机网络领域，应用于网络通信行业，具体涉及一种端到端网络通 信路径中瓶颈链路的度量方法。

背景技术

度量网络通信路径中的拥塞情况，并获得瓶颈链路的位置、可用带宽、以及带宽 上限等信息，是一种非常重要的能力。这种能力，在计算机网络的拥塞控制、流媒体 应用、QoS、覆盖型网络，以及流量控制等很多领域都有广泛的应用空间。

现有的算法能够获知瓶颈链路的位置，通信路径的可用带宽，以及通信路径的带 宽上限，但却是由不同的度量工具分别获得的。由于不同工具所采用的数学模型，以 及探测技术并不兼容，因此当前没有一个技术能够同时度量瓶颈链路的这三个属性。 如果运行三款不同的工具，把度量分成三个步骤来做的话，又会生成大量的冗余的探 测数据包，且度量时间太长，准确性将下降。

发明内容

有鉴于此，本发明的目的在于克服现有技术的不足，提供一种端到端网络通信路 径中瓶颈链路的度量方法。该方法可在一个度量周期内，获知端到端通信路径中瓶颈 链路的位置、可用带宽以及带宽物理容量上限；且本发明基于主动探测机制，无需在 网络路径的沿途各节点中安装软件，适用范围广泛。

为实现上述目的，本发明采取以下技术方案：一种端到端网络通信路径中瓶颈链 路的度量方法，该方法包括如下步骤：

S1、捕获探测数据包队列在每一个链路上的平均传输间隔即PPD值，从而确认哪 些链路是拥塞链路；

S2、度量拥塞链路的容量；

S3、计算拥塞链路的可用带宽；

S4、在拥塞链路中找出待测路径的瓶颈链路，并输出它的位置、容量和可用带宽 信息。

进一步的，所述的步骤S1中，队列在各个链路上的平均传输间隔即PPD值的估计 方法如下：

定义探测数据包队列包括2N个数据包(1≤N≤255)，每一个数据包的大小都相同 (S字节)。每一个方框都是UDP数据包，方框中的数字是该数据包的存活值 (Time-To-Live,TTL)，这个值从两边往中间依次递增。

源节点R0以背靠背(back-to-back[Hu03])的方式，尽可能紧凑地把一组数据包 队列往目标节点Rn发送过去。当该队列抵达第一个路由器，也就是R1时，队列的头 和尾两个数据包由于TTL值为1，就被R1丢弃了，丢弃的同时R1会发送两个ICMPError 包给R0。该队列中其余的探测数据包，在TTL值都被R1减1之后，就被传送到R2。

后续的中间节点(也即路由器)，包括R2在内，会一直重复R1的操作，直到该队 列抵达终点Rn。这样下来，每一个中间节点都会给R0发送一对ICMPError包，源节 点记录下来它接收这两个包的时间间隔，即可估计队列在各个链路上的平均传输间隔。

队列在每一个链路上的传输间隔，与队列在该链路上的探测数据包数量成正比；

定义：PPD代表了每两个相邻数据包的最后一个字节间的距离；

队列在链路Li上的间隔是Δ_i，而PPD在Li上的值是pi，则有：

$p_i=\frac{{\Delta }_i}{2·(N-i)-1}.(0\le i\le n-1)---\left(1\right)$

此外，以p-1来表示当队列被R0发送出去时的PPD值，使用PPD值来探索数据包 队列和各链路的关系。

需要进一步说明的是，使用队列探测该路径一次，并收集返回的ICMP报错包以计 算所有链路的PPD值；所以，一次探测就得到一个PPD序列：p-1，p0，p1…pn-2；

由于前向的后向的背景数据流会给PPD序列带来很多噪音，所以在使用PPD来定 位拥塞队列时，需先采用填充PPD序列中的山峰和低谷的方法来处理PPD序列，具体 处理方法如下：

S11、一个山峰指的是在连续的PPD三元组(p1,p2,p3)中，p1<p2>p3成立。低 谷指的是满足p1>p2<p3的一个三元组。在这样的三元组中，山峰和低谷都被与它数值 最接近的p1或者p3所替代，因为我们认为山峰和低谷是由网络噪音带来的；

S12、通过划分PPD序列，构造临时的分组来找到PPD值被扩大的链路，也即拥塞 链路。规则是这样的：每一个PPD值都被分类到一个组中；每个组中至少包含一个PPD； 队列中所有的PPD都需要满足|p1-pi|<threshold，这里p1是队列中的第一个PPD， 而pi是队列中的任一其他PPD。

每组PPD中第一个PPD对应的下标，就是对应的拥塞链路的下标。再获得拥塞链 路的下标也即位置之后，即可转入步骤S2和S3度量每一个拥塞链路的容量和可用带 宽。

进一步的，所述步骤S2中度量拥塞链路的容量具体方法如下：

定义：Di表示一个数据包从R0到Ri的传输延迟；Ci表示链路Li的容量；di表 示链路Li的物理传输延迟；S表示数据包的大小；Qi表示该数据包在链路Li中被缓 冲延迟的时间；

则，$D_i=\underset{k=0}{\overset{i-1}{\Sigma }}\frac{S}{C_k}+Q_k+d_k---\left(2\right)$

为了度量Di的值，源节点R0生成一个数据包，把数据包的TTL值设为i，然后 向目的节点发送；该数据包会被Ri丢弃，同时Ri返回一个ICMP报错包给R0。通过 这种方法，R0就获知了从它到Ri的往返时间差，该时间差约等于2Di，然后即可计算 出Di。

在所有发往Ri的数据包计算出的Di中，最小的那个Di值，包含的缓冲延迟最小； 通过这的方法，Qk可以根据统计从公式(2)中去掉：使用最小的Di值；

在实际的探测中，相邻数据包还需要按一定的间隔I分开来，以避免重叠；

I＝max{pi,-1≤i<n-1}(3)

探测链路Li的两端，也即Ri和Ri+1；使用的都是大小为S的数据包，得了一组 Di和Di+1值；于是数据包在链路Li上的传输延迟就等于

${\mathrm{DL}}_i\left(S\right)=min\left(D_{i+1}\right)-min\left(D_i\right)=\frac{S}{C_i}+d_i---\left(4\right)$

根据上面的分析，为了获得Ci，源节点R0需要按照不同的大小，发送多组数据 包到目标链路Li的两端Ri和Ri+1，画出每组数据包发射后获得的min(Di+1)-min(Di) 除以数据包的大小S，得到的直线的斜率的倒数，就是Ci。

进一步的，所述的步骤S3中计算拥塞链路的可用带宽具体方法如下：

设定：在链路Li上的背景数据流的传输速率为

根据定义因为在度量过程中被认为是固定不变的，可以认为背景数据 流被平均分布到每两个相邻探测数据包之间；那么，在一个pi-1间隔内，进入链路 Li的背景数据流是同时，仅有一个探测数据包抵达Li，即结果 是，链路Li在一个pi-1的间隔里，接收的数据是Xi+S。

在一个pi-1的间隔里，链路Li能够传输的数据量是C_i·p_i-1；

当时，$X_i+S=(r_p^{i-1}+r_c^i)·p_{i-1}\le (A_i+r_c^i)·p_{i-1}=C_i·p_{i-1}---\left(5\right)$

这意味着所有进来的数据包，都会被Li传送出去且没有缓冲延迟，于是PPD的值 保持不变，即pi＝pi-1；

当时，PPD被扩大了，即pi>pi-1且Li被认为是拥塞链路；这意味着Li 需要比pi-1更多的时间来传送出在pi-1间隔内进入它的数据包；在这种情况下，Li 把pi-1扩大为：

$p_i=\frac{X_i+S}{C_i}---\left(6\right)$

通过公式(6)，以及和推出Ai为

$A_i=\frac{S+C_i·(p_{i-1}-p_i)}{p_{i-1}}---\left(7\right)$

公式(7)中的参数pi-1，pi和Ci，以及S都能在前面的步骤中度量出来，那么Ai 就能直接计算。

进一步的，所述的步骤S3中，所述的瓶颈链路即为可用带宽最小的拥塞链路。

本发明采用以上技术方案，发送一组探测数据包队列，这一组数据包队列从源节 点传送到目标节点，跟踪该队列在每一段链路上的内部数据包传输间隔，捕获探测数 据包队列在每一个链路上的平均传输间隔即PPD值，确认拥塞链路；本发明可在一个度量 周期内，获知端到端通信路径中瓶颈链路的位置、可用带宽、带宽物理容量上限；且 本发明基于主动探测机制，无需在网络路径的沿途各节点中安装软件，适用范围广泛。

附图说明

图1是本发明端到端网络路径的简化模型；

图2是本发明端到端网络通信路径中瓶颈链路的度量方法流程图；

图3是本发明探测数据包队列的结构；

图4是本发明探测数据包队列在相邻两段链路上的PPD示意图；

图5是本发明传输延迟和带宽容量度量过程的示意图。

具体实施方式

下面结合附图和实施例对本发明进行详细的描述。

可用带宽，指的是在不影响网络路径中背景数据流的情况下，端到端通信所能够 获得的最大数据传输率[Jain]。可用带宽是计算机网络的核心概念之一，它在协议设 计、网络管理、QoS部署、组播通信和多媒体传输等诸多方面有着重要意义。

例如，TCP协议的一个主要设计目标就是在不堵塞网络的情况下，最大限度地利 用可用带宽。在每一个网络中，管理员都需要监测各个链路的负载情况进而合理地配 置网络资源，可用带宽正是网络监测和配置的重要参考依据。而且，能否获得预期的 可用带宽也是网络运营商(ISP)部署QoS的关键考核指标。与此同时，大量的网络应用 也迫切需要具备快速度量可用带宽的能力。组播通信就需要在占用最小网络资源(包括 可用带宽)的情况下，协同多个网络节点以维护高效的组播路由树。多媒体应用如点对 点视频会议，同样需要快速感知各节点间可用带宽的变化，并据此及时调整数据压缩 算法和传输策略。

可用带宽是在网络路径的上下文中定义的。网络路径由一序列存储转发链路组成， 它能够把数据包从源终端主机(R0)通过一系列中间节点R1,R2,…,Rn-1传输到目标终 端主机(Rn)。链路Li是从Ri到Ri+1的数据传输通道，这里0≤i≤n-1。在t时刻Li 的利用率Ui(t)为

当Ui(t)＝0时，Li的传输速率为0，反之Li以固定的速率Ci传输数据包。这里 Ci又被称为Li的物理传输速率或带宽容量(capacity)，它是由链路的物理特性决定 的，与时间t无关。端到端(R0到Rn)数据传输率的上限CP，由最小的链路带宽容量 决定：

$C_P=\underset{i=0...n-1}{min}\left\{C_i\right\},---\left(9\right)$

决定CP的那段链路被称为狭窄链路(narrowlink)[Jain]，同一网络路径中可能 存在多条狭窄链路。在某一时段[t,t+τ]内链路Li的利用率为

$U_i(t,t+\tau )=\frac{1}{\tau }{\int }_t^{t+\tau }\left(t\right)dt,---\left(10\right)$

易知Ui(t,t+τ)∈[0,1]。在时段[t,t+τ]内Li的平均数据传输率为

λ_i＝C_i·U_i(t,t+τ).(11)

一般称λi为Li中背景数据流(cross-traffic)的传输速率。背景数据流即Li正 常传输的数据流，这么称呼是为了把它们跟度量系统出于探测目的而发送的探测数据 流(probe-traffic)区分开来。

在时段[t,t+τ]内Li的可用带宽Ai指的是Li的平均空闲传输速率，即

$A_i(t,t+\tau )=\frac{1}{\tau }{\int }_t^{t+\tau }(C_i-{\lambda }_i(t\left)\right)dt.---\left(12\right)$

本发明所关注的可用带宽，并非单个链路的可用带宽，而是待测网络路径的端到 端可用带宽AP，它由路径中最小的链路可用带宽决定：

$A_P(t,t+\tau )=\underset{i=\mathrm{0...}n-1}{\min }\left\{A_i\right(t,t+\tau \left)\right\}.---\left(13\right)$

决定AP的那段链路常被称为紧凑链路(tightlink)[Hu]或瓶颈链路(bottleneck link)[Zhou]。与狭窄链路不同的是，在一个网络路径中瓶颈链路往往只有一条，且其 位置还会随着网络负载的不同而变化。

在实际度量过程中，时间τ并不是固定的值，按照惯例它等于度量系统的一个度 量周期(即运行一次系统以度量AP所用的时间)[Jain]。所以对于不同的度量系统而 言，时间τ通常不同；即使是同一个系统，在软硬件配置或者待测路径的属性变化时 τ也会随着变化。

如图1所示，是上述概念的简单示例。其中R0和Rn作为源终端主机和目标终端 主机分别位于路径的首尾两端，链路Li的可用带宽Ai等于带宽容量Ci减去背景数据 流的传输速率λi。对于一个中间节点而言，背景数据流可以有多个来源(source)和去 处(sink)。

在过去的15年里，业界基于主动探测机制研发了大量的软件系统。其中常被讨论 和比较的有Abget[Antoniades],BFind[Akella],[Zhou],Cprobe[Carter],Delphi [Ribeiro00],IGI[Hu],Netest[Netest],Pathchirp[Ribeiro03],Pathload[Jain], Pipechar[Netest],SProbe[Saroiu],Spruce[Strauss]和TOPP[Melander]等 十三个系统。

按照运行模式的不同，这些系统可以分为单终端系统和双终端系统两类。它们的 主要区别是单终端系统仅需在R0上安装软件，而双终端系统要求在R0和Rn上都安装。 相比之下，双终端系统的度量结果更准确，这是因为它能够利用R0和Rn的协作简化 度量过程，而不像单终端系统那样必须面对反向路径(Rn到R0)的干扰。但是双终端系 统的应用范围非常有限，原因是用户往往只能在R0(一般是用户自己的机器)上安装软 件，而不具备在远程的Rn上安装软件的权限。与此相反，单终端系统只需要安装在 R0上，就能用来度量以R0为源终端主机的绝大多数网络路径的可用带宽。

第一个单终端系统是CProbe[Carter]，它同时也是最早的可用带宽度量系统。 CProbe充分利用了ICMP协议的请求－应答机制[Postel]。具体地，CProbe从R0向 Rn发送多组用于探测的IP包(IP包中的time-to-live域被设置为从1到n之间的值， 且destinationport域设置成一个非监听端口)；这些IP包触发了节点的ICMP错误 处理流程，所以R1,…,Rn会向R0发送ICMPtime-exceeded(TE)和 destination-unreachable(DU)包；CProbe接收到ICMPTE和DU包后，将根据接收 时间推算探测IP包在每段链路上传输速率的变化情况，进而估算可用带宽。

在CProbe之后，Pipechar[Netest]也采用了基于ICMP协议的方法，而 SProbe[Saroiu]则是基于TCP和HTTP协议开发的，它们都有目的地利用了协议的特性 以获取远程节点的反馈，并挖掘应答数据包的间隔变化规律进而估算可用带宽。

但文献[Dovrolis]中的工作证明了CProbe和Pipechar所度量的其实并不是可用 带宽，而是非对称分散速率(asymptoticdispersionrate)。所以在CProbe和Pipechar 之后的单终端系统，都必须证明它们所度量的确实是可用带宽。在后续的系统中，常 被讨论的有Abget[Antoniades]，BFind[Akella]和BNeck[Zhou]。

最典型的双终端系统是Pathload[Jain]。Pathload的程序分为pathload_snd 和pathload_rcv两部分，其中pathload_snd安装在R0上，而pathload_rcv安装在 Rn上。初始状态下，Pathload认为可用带宽属于区间[0,C0]。然后pathload_snd以 速率x＝C0/2发送y组探测数据包(默认情况下y＝6)。Rn上的pathload_rcv在接收到 每一组数据包后，计算相邻探测数据包的间隔是否呈递增趋势。

如果多组数据包的间隔都呈递增趋势，那么Pathload认为x>AP且AP∈[0,x]， 否则x≤AP且AP∈[x,C0]。假设在一次探测完后AP∈[a,b]，那么pathload_snd会以 x＝(a+b)/2的速率发送y组数据包再一次探测网络路径并缩小可用带宽的所属区间。 当(b-a)<σ(或出现了意外)时，Pathload才停止探测并输出[a,b]，这里σ是事先设 定的阀值。需要注意的是Pathload最终输出的是一个带宽区间，而不是单一数值。除 了Pathload外，常见的双终端系统还有Delphi[Ribeiro00],IGI[Hu],Netest [Netest],Pathchirp[Ribeiro03],Spruce[Strauss]和TOPP[Melander]。

如图2所示，本发明提供一种端到端网络通信路径中瓶颈链路的度量方法，该方 法包括如下步骤：

S1、捕获探测数据包队列在每一个链路上的平均传输间隔即PPD值，从而确认哪 些链路是拥塞链路；

S2、度量拥塞链路的容量；

S3、计算拥塞链路的可用带宽；

S4、在拥塞链路中找出待测路径的瓶颈链路，并输出它的位置、容量和可用带宽 信息。

本实施例的核心思想是：快速定位通信路径中的拥塞链路，并度量其属性。具体 的，本技术发送一组探测数据包队列，这一组数据包队列从源节点传送到目标节点， 跟踪该队列在每一段链路上的内部数据包传输间隔。根据经验，当这个数据包队列流 经一个链路时，如果链路的可用带宽低于包队列的传输速度，那么该队列会被减速， 也即内部数据包的平均传输间隔会被加大。根据定义，拥塞的链路正是扩大数据包传 输间隔的链路。

本发明的工作，主要集中在度量拥塞链路的属性上。这是因为，瓶颈链路就是路 径中的拥塞链路之一，它的可用带宽在所有拥塞链路中是最低的。

为了获得数据包队列在每个链路上的内部平均传输间隔(per-linkdispersion, PPD)，需要设计一种全新的数据包队列，如图3所示。

这个队列包括2N个数据包(1≤N≤255)，每一个数据包的大小都相同(S字节)。 每一个方框都是UDP数据包，方框中的数字是该数据包的存活值(Time-To-Live,TTL)， 这个值从两边往中间依次递增。这种设计，能够允许该队列通过最多包含了N个路由 器的路径。尽管队列中数据包的数量决定了该队列将带给网络的负载，但数量越大则 表示该队列与背景数据流的交互越深。因此，使用一个相对较长的队列还是有好处的。

源节点R0以背靠背(back-to-back[Hu03])的方式，尽可能紧凑地把一组数据包 队列往目标节点Rn发送过去。当该队列抵达第一个路由器，也就是R1时，队列的头 和尾两个数据包由于TTL值为1，就被R1丢弃了，丢弃的同时R1会发送两个ICMPError 包给R0。该队列中其余的探测数据包，在TTL值都被R1减1之后，就被传送到R2。

后续的中间节点(也即路由器)，包括R2在内，会一直重复R1的操作，直到该队 列抵达终点Rn。这样下来，每一个中间节点都会给R0发送一对ICMPError包，源节 点记录下来它接收这两个包的时间间隔，就可以估计队列在各个链路上的平均传输间 隔。

需注意的是：最后一个链路(Ln-1)的ICMPError包一般不被采用。这是因为， 队列中的每一个数据包都把目标端口设成了一个没有被Rn监听的值，所以队列中剩下 多少个数据包，节点Rn就可能会返回多少个ICMPport-unreachable的Error包， 而不仅仅是两个。当节点短期内产生大量的ICMP包时，这些包之间可能会有额外的延 迟，Rn也可能出于安全的考虑而不为所有的错误生成ICMP包。

那么，队列在每一个链路上的传输间隔，与队列在该链路上的探测数据包数量成 正比。因为每一个中间的节点都会把头和尾数据包丢弃，所以在计算平均传输间隔时， 我们需要考虑探测队列在特定链路上，有多少个数据包。我们引入平均数据包间隔 (Per-PacketDispersion,PPD)，来更准确地表达我们希望考虑的因素。PPD代表了 每两个相邻数据包的最后一个字节间的距离。队列在链路Li上的间隔是，而PPD在 Li上的值是pi，那么有：

$p_i=\frac{{\Delta }_i}{2·(N-i)-1}.(0\le i\le n-1)---\left(1\right)$

此外，以p-1来表示当队列被R0发送出去时的PPD值。既然拥塞的链路会扩大队列 的传输间隔，那么它同样会扩大PPD的值。所以，PPD允许我们探索数据包队列和各 链路的关系。

如图4所示，本发明提供如下的小试验，用一组队列来反复地探测一有7个链路 的通信路径。该路径在我们的监管之下，它连接了中科院软件所和中科院研究生院的 两台服务器。在路由器上的日志表明：如果Ai小于该队列在Li上的传输速率的话， 那么PPD就被按照一定的比例扩大了，而如果那么该队列的PPD保持不变。 这是个非常重要的结论，其效果如图4所示。

需要进一步说明的是，本实施例中使用队列探测该路径一次，并收集返回的ICMP 报错包以计算所有链路的PPD值；所以，一次探测就得到一个PPD序列：p-1，p0，p1… pn-2；

理想的情况下，当一个链路没有足够的可用带宽以容纳快速进入的队列时，PPD 的值会增加；当该链路有足够的带宽空间以容纳队列时，PPD的值保持不变。因此， PPD永远都不会减少。然而，在实际情况中，由于前向的后向的背景数据流会给PPD 序列带来很多噪音，所以在使用PPD来定位拥塞队列时，需先采用填充PPD序列中的 山峰和低谷的方法来处理PPD序列，具体处理方法如下：

S11、本实施例中采用的处理方法是填充PPD序列中的山峰和低谷。一个山峰指的 是在连续的PPD三元组(p1,p2,p3)中，p1<p2>p3成立。低谷指的是满足p1>p2<p3 的一个三元组。在这样的三元组中，山峰和低谷都被与它数值最接近的p1或者p3所 替代，因为我们认为山峰和低谷是由网络噪音带来的；

S12、接下来，通过划分PPD序列，构造临时的分组来找到PPD值被扩大的链路， 也即拥塞链路。规则是这样的：每一个PPD值都被分类到一个组中；每个组中至少包 含一个PPD；队列中所有的PPD都需要满足|p1-pi|<threshold，这里p1是队列中的 第一个PPD，而pi是队列中的任一其他PPD。

结果是，每组PPD中第一个PPD对应的下标，就是对应的拥塞链路的下标。再获 得拥塞链路的下标也即位置之后，即可转入步骤S2和S3度量每一个拥塞链路的容量 和可用带宽。

本实施例中，所述步骤S2中度量拥塞链路的容量具体方法如下：

定义：Di表示一个数据包从R0到Ri的传输延迟；Ci表示链路Li的容量；di表 示链路Li的物理传输延迟；S表示数据包的大小；Qi表示该数据包在链路Li中被缓 冲延迟的时间；

则，$D_i=\underset{k=0}{\overset{i-1}{\Sigma }}\frac{S}{C_k}+Q_k+d_k---\left(2\right)$

为了度量Di的值，源节点R0生成一个数据包，把数据包的TTL值设为i，然后 向目的节点发送；该数据包会被Ri丢弃，同时Ri返回一个ICMP报错包给R0。通过 这种方法，R0就获知了从它到Ri的往返时间差，该时间差约等于2Di，然后即可计算 出Di。

计算机网络中有一个现象，即由背景数据流导致的缓冲延迟，只会延长传输延迟， 而绝不会缩短。所以，在所有发往Ri的数据包计算出的Di中，最小的那个Di值，包 含的缓冲延迟最小；通过这的方法，Qk可以根据统计从公式(2)中去掉：使用最小 的Di值；

在实际的探测中，相邻数据包还需要按一定的间隔I分开来，以避免重叠；

I＝max{pi,-1≤i<n-1}(3)

本发明系统探测链路Li的两端，也即Ri和Ri+1；使用的都是大小为S的数据包， 得了一组Di和Di+1值；于是数据包在链路Li上的传输延迟(不包含缓冲延迟的)就 等于

${\mathrm{DL}}_i\left(S\right)=min\left(D_{i+1}\right)-min\left(D_i\right)=\frac{S}{C_i}+d_i---\left(4\right)$

如图5所示，根据上面的分析，为了获得Ci，源节点R0需要按照不同的大小， 发送多组数据包到目标链路Li的两端Ri和Ri+1，画出每组数据包发射后获得的 min(Di+1)-min(Di)除以数据包的大小S，得到的直线的斜率的倒数，就是Ci。如图5 (b)所示，该图展示了这个计算过程。

本实施例中所述的步骤S3中计算拥塞链路的可用带宽具体方法如下：

在链路Li上(从Ri到Ri+1)的背景数据流的传输速率为

根据定义因为在度量过程中被认为是固定不变的，可以认为背景数据 流被平均分布到每两个相邻探测数据包之间；那么，在一个pi-1间隔内，进入链路 Li的背景数据流是同时，仅有一个探测数据包抵达Li，即结果 是，链路Li在一个pi-1的间隔里，接收的数据是Xi+S。

在一个pi-1的间隔里，链路Li能够传输的数据量是C_i·p_i-1；

当$r_p^{i-1}\le A_i$时，$X_i+S=(r_p^{i-1}+r_c^i)·p_{i-1}\le (A_i+r_c^i)·p_{i-1}=C_i·p_{i-1}---\left(5\right)$

这意味着所有进来的数据包，都会被Li传送出去且没有缓冲延迟，于是PPD的值 保持不变，即pi＝pi-1；

当时，PPD被扩大了，即pi>pi-1且Li被认为是拥塞链路；这意味着Li 需要比pi-1更多的时间来传送出在pi-1间隔内进入它的数据包；在这种情况下，Li 把pi-1扩大为：

$p_i=\frac{X_i+S}{C_i}---\left(6\right)$

通过公式(6)，以及和推出Ai为

$A_i=\frac{S+C_i·(p_{i-1}-p_i)}{p_{i-1}}---\left(7\right)$

公式(7)中的参数pi-1，pi和Ci，以及S都能在前面的步骤中度量出来，那么Ai 就能直接计算。需要注意的是An-1不在可计算范围内，这是因为我们无法捕获pn-1。 但在实际网络环境中，瓶颈链路是通信路径途中的某一段链路，但一般都不会是最后 的一段。

进一步的，所述的步骤S3中，所述的瓶颈链路即为可用带宽最小的拥塞链路。

在所述步骤S4中，可知，可用带宽最小的拥塞链路，就是所要找的瓶颈链路。本 实施例至此，即可在一个度量周期内输出瓶颈链路的位置(也即下标)，容量和可用带 宽。

上述实施例中，通过发送一组探测数据包队列，这一组数据包队列从源节点传送 到目标节点，跟踪该队列在每一段链路上的内部数据包传输间隔，捕获探测数据包队列 在每一个链路上的平均传输间隔即PPD值，确认拥塞链路；本发明可在一个度量周期内， 获知端到端通信路径中瓶颈链路的位置、可用带宽、带宽物理容量上限；且本发明基 于主动探测机制，无需在网络路径的沿途各节点中安装软件，适用范围广泛。

本发明不局限于上述最佳实施方式，任何人在本发明的启示下都可得出其他各种 形式的产品，但不论在其形状或结构上作任何变化，凡是具有与本申请相同或相近似 的技术方案，均落在本发明的保护范围之内。