摘要：对于网络应用管理中，如果知道了瓶颈链路的位置所在，可以在内部或外部网络中应用通过流量工程来提高网络路由。目前Path-neck是基于算法Recursive Packet Train（RPT）上的一种确定网路链路中瓶颈链路的工具，本文主要针对RPT的一些缺陷加以改进，提出了RPT的改良算法。
关键词：瓶颈链路；RPT；Path-neck；可用带宽
中图分类号：TN915 文献标识码：A 文章编号：1007-9599 （2012） 15-0000-02
网络中的传输路径由从数据源到目的地的一系列存储转发链路组成。链路的带宽或容量是指链路上数据报文的最大传输速率。网络链路的瓶颈带宽或容量是指源节点到目的节点之间处理能力最低的链路所能达到的最大传输速率。传输路径上带宽/容量最小的链路称为该路径的瓶颈链路。
如果一条链路R0R1R2…Ri-1Ri…Rn-1Rn由n跳组成，其中R0表示数据源，Rn表示目的地。如果Ci表示链路Li（Ri-1Ri）为整条链路提供的容量，则有如下规则：
C1>=C2…Ci（2=n），如图1所示，则Li-1Li称为阻塞链路（Chock Link）。一条链路上由若干的阻塞链路组成，其中最接近目的地节点的阻塞链路称为瓶颈链路（图2）。
Ri-1
一、Path-neck中的Recursive Packet Train算法
Recursive Packet Train（RPT）指的就是通过一组数据报序列来确定链路上瓶颈链路，如图3所示。
Path-neck把数据分成了测量数据报和加载数据报两种。Path-neck首先向目的节点发送30个TTL从1到30递增的测量数据报，总字节数为30×60=1800；然 后再向目的节点发送60个TTL为255的加载数据报，总字节数为60×500=30000；最后向目的节点发送30个TTL从30到1递减的测量数据报，总字节数为30×60=1800。测量数据报在源节点发出的总量中只占用了（1800+1800）/（1800+30000+1800）=10.7%，因此在计算这个数据报序列时，对测量数据报的大小忽略不计。每个IP数据报每经过一个节点时，其TTL自动减1，当TTL为0时，节点将向源节点返回ICMP错误数据报。源节点通过接受ICMP错误报来确定这个数据报序列刚到达节点Ri（1≤i≤n-1）的时间ti1与数据报序列完全通过此节点的时间ti2，从而计算出整个序列通过节点Ri（1≤i≤n-1）的时间为
ti=ti2-ti1 （2）
则根据式（1），有
t1≤t2≤…≤tn-1 （3）
各单链路的可用带宽可以通过下式求得
Ai=总字节数/时间=30000/ti（其中1≤i≤n-1） （4）
通过式（3）（4），此链路上的各单链路的可用带宽满足如下条件：
A1≥A2≥…≥An-1 （5）
通过式（5）找到最后一个阻塞链路（Choke Link），即是Path-neck中的瓶颈链路。
2 Path-neck的不足
（1）在RTP算法中，当TTL=0的数据报到达一路由器并且向下一链路传送时，此时路由器将认为此数据报为不可达数据报，将其丢弃并向源地址返回一个ICMP数据报，而源地址收到ICMP数据报来计算加载数据包序列通过该节点所花的时间（式（2））。但源节点接收不到来自目的节点的ICMP数据报。因此，最后一跳链路没有办法计算其可利用带宽。
（2）ICMP数据报产生的时间和阻塞的ICMP传输的路径可能导致较大的误差。
（3）ICMP数据报在传输的过程中可能会丢失，所有的数据报也有可能不是通过同一条链路达到目的节点，可能会造成错误的测量。
（4）对于Internet中的某些节点路由安装了阻止ICMP报通过的防火墙，导致了ICMP不能成功地被源节点接收到。
（5）由于在计算单链路的可用带宽是用式（4）来进行计算的，计算出的各单链路的可用带宽小于实际带宽，设Ai0（1≤i≤n-1）为单链路Ri-1Ri的实际可用带宽，Ai1为其计算出的可用带宽。可以用式（4）计算出Ai1，下面是计算实际可用带宽的公式：
Ai0=流量/时间=[30000+60×（31-i）×2]/ti=（33720-120×i） / ti（1≤i≤n-1≤30） （6）
设△Ai（1≤i≤n-1）为测量可用带宽与实际带宽之差，则有下式：
△Ai= Ai0- Ai1=（33720-120×i）/ti-（30000/ti）=（3720-120×i）/ ti（1≤i≤n-1≤30） （7）
误差率Φi（1≤i≤n-1）可以通过式（7）得到
Φi=△Ai/Ai1=[（3720-120×i）/ti]/（30000/ti）=（3720-120×i）/30000=12.6%-（4×i/ 1000）（7’）
可以看出，△A1>△A2>…>△An-1，即Path-neck测量出来的可用带宽是越接近目的节点就越真实。因此它所测出的瓶颈链路趋向于较前的阻塞链路。
3 RPT算法的改进
本文主要针对上面的第（5）点不足之处提出了RPT的改进算法。本文把探测包序列由120个数据报组成（跟Path-neck一样），所有数据报的大小是500Byte，即总字节数为500×120=60000Byte。前30个数据报的生命周期TTL从1递增到30，中间60个数据报的生命周期TTL为255或64，最后30个数据报的生命周期TTL从30递减到1，其中前后30个数据报的作用仍然是获得整个数据报序列通过某个节点的时间。如图4所示。 设ti1"， ti2’（ 1≤i≤n-1）分别为数据报序列到达第i个节点的时刻和所有数据报序列通过该节点的时刻，都是通过获得第i个节点传回的ICMP获得，则此数据报序列通过该节点所花的时间由下式获得
ti’=ti2’-ti1’ （8）
该节点接收到120-2×（i-1）=120-2×i+2=122-2×i个数据报，则该节点接收到的流量为
Si=数据报个数×数据报大小=（122-2×i）×500=61000-1000×I （9）
可以得到第i个（1≤i≤n-1）条链路的可用带宽Ai’：
Ai’=流量/时间= Si+/ ti’=61000-1000i/（ ti2’-ti1’） （10）
该算法提高了计算可用带宽的精确度以及提高了瓶颈链路的准确度，但是并没有解决Path-neck的其他四点不足。
4 改进的RPT算法与RPT的测试比较
下载Pathneck-1.3的源码，在此基础上完成了Pathneck-1.3改进版的源码。Pathneck-1.3改进版的输入是目的地址IP，参数设置为confidence_threshold≥10%，Detection_rate≥50%，输出结果是途径的节点IP地址和两个数据报序列通过该节点的时间间隔，本文用该应用程序对www.163.com进行了100此次测试，测试结果表明该链路途径172.17.1.1（A），222.178.32.109（B），222.176.3.169（C），222.176.2.29（D），222.176.2.57（E），202.97.36.193（F），202.97.41.218（G），202.97.27.154（H），202.102.3.70（I）等九个节点。这100次探测的结果如表1所示。
表1 两种RPT算法在经过100次测试的成功记录表
测试结果 两种均成功 原RPT 改进RPT 两种均不成功
次数 58 26 16 0
对测试的结果取两种算法都成功的58次的原始数据作为研究对象，通过式（11）分别求得RPT和改进的RPT通过第i（1≤i≤n-1）个节点的平均时间间隔值 和 ： （11）
再通过方差公式（11）计算时间间隔的平方差σ1i，σ2i：
当 >3σki（其中j表示第j次测试在第i个节点的时间间隔，k=1，2）时，可以认为此次测试无效，将其丢弃。通过如此过滤后的测试次数为49次，于是可以通过式（11）求得的平均值作为通过该节点的时间间隔，再通过式（4）和式（10）分别求可用带宽，如表2所示。
从表2可以看出，改进后的可用带宽明显比原算法的带宽大，其范围正好符合式（7"）的要求。
5 结束语
上面的试验结果得出如下结论：改进算法计算出来的可用带宽比Pathneck-1.3更加准确；改进算法确定的瓶颈链路也更加准确。
