摘要：對于網(wǎng)絡(luò)應(yīng)用管理中，如果知道了瓶頸鏈路的位置所在，可以在內(nèi)部或外部網(wǎng)絡(luò)中應(yīng)用通過流量工程來提高網(wǎng)絡(luò)路由。目前Path-neck是基于算法Recursive Packet Train（RPT）上的一種確定網(wǎng)路鏈路中瓶頸鏈路的工具，本文主要針對RPT的一些缺陷加以改進(jìn)，提出了RPT的改良算法。

關(guān)鍵詞：瓶頸鏈路；RPT；Path-neck；可用帶寬

中圖分類號：TN915 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 （2012） 15-0000-02

網(wǎng)絡(luò)中的傳輸路徑由從數(shù)據(jù)源到目的地的一系列存儲轉(zhuǎn)發(fā)鏈路組成。鏈路的帶寬或容量是指鏈路上數(shù)據(jù)報文的最大傳輸速率。網(wǎng)絡(luò)鏈路的瓶頸帶寬或容量是指源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間處理能力最低的鏈路所能達(dá)到的最大傳輸速率。傳輸路徑上帶寬/容量最小的鏈路稱為該路徑的瓶頸鏈路。

如果一條鏈路R0R1R2…Ri-1Ri…Rn-1Rn由n跳組成，其中R0表示數(shù)據(jù)源，Rn表示目的地。如果Ci表示鏈路Li（Ri-1Ri）為整條鏈路提供的容量，則有如下規(guī)則：

C1>=C2…<=Cn （1）

如果Ci-1>Ci（2<=i>=n），如圖1所示，則Li-1Li稱為阻塞鏈路（Chock Link）。一條鏈路上由若干的阻塞鏈路組成，其中最接近目的地節(jié)點(diǎn)的阻塞鏈路稱為瓶頸鏈路（圖2）。

Ri-1

一、Path-neck中的Recursive Packet Train算法

Recursive Packet Train（RPT）指的就是通過一組數(shù)據(jù)報序列來確定鏈路上瓶頸鏈路，如圖3所示。

Path-neck把數(shù)據(jù)分成了測量數(shù)據(jù)報和加載數(shù)據(jù)報兩種。Path-neck首先向目的節(jié)點(diǎn)發(fā)送30個TTL從1到30遞增的測量數(shù)據(jù)報，總字節(jié)數(shù)為30×60=1800；然 后再向目的節(jié)點(diǎn)發(fā)送60個TTL為255的加載數(shù)據(jù)報，總字節(jié)數(shù)為60×500=30000；最后向目的節(jié)點(diǎn)發(fā)送30個TTL從30到1遞減的測量數(shù)據(jù)報，總字節(jié)數(shù)為30×60=1800。測量數(shù)據(jù)報在源節(jié)點(diǎn)發(fā)出的總量中只占用了（1800+1800）/（1800+30000+1800）=10.7%，因此在計(jì)算這個數(shù)據(jù)報序列時，對測量數(shù)據(jù)報的大小忽略不計(jì)。每個IP數(shù)據(jù)報每經(jīng)過一個節(jié)點(diǎn)時，其TTL自動減1，當(dāng)TTL為0時，節(jié)點(diǎn)將向源節(jié)點(diǎn)返回ICMP錯誤數(shù)據(jù)報。源節(jié)點(diǎn)通過接受ICMP錯誤報來確定這個數(shù)據(jù)報序列剛到達(dá)節(jié)點(diǎn)Ri（1≤i≤n-1）的時間ti1與數(shù)據(jù)報序列完全通過此節(jié)點(diǎn)的時間ti2，從而計(jì)算出整個序列通過節(jié)點(diǎn)Ri（1≤i≤n-1）的時間為

ti=ti2-ti1 （2）

則根據(jù)式（1），有

t1≤t2≤…≤tn-1 （3）

各單鏈路的可用帶寬可以通過下式求得

Ai=總字節(jié)數(shù)/時間=30000/ti（其中1≤i≤n-1） （4）

通過式（3）（4），此鏈路上的各單鏈路的可用帶寬滿足如下條件：

A1≥A2≥…≥An-1 （5）

通過式（5）找到最后一個阻塞鏈路（Choke Link），即是Path-neck中的瓶頸鏈路。

2 Path-neck的不足

（1）在RTP算法中，當(dāng)TTL=0的數(shù)據(jù)報到達(dá)一路由器并且向下一鏈路傳送時，此時路由器將認(rèn)為此數(shù)據(jù)報為不可達(dá)數(shù)據(jù)報，將其丟棄并向源地址返回一個ICMP數(shù)據(jù)報，而源地址收到ICMP數(shù)據(jù)報來計(jì)算加載數(shù)據(jù)包序列通過該節(jié)點(diǎn)所花的時間（式（2））。但源節(jié)點(diǎn)接收不到來自目的節(jié)點(diǎn)的ICMP數(shù)據(jù)報。因此，最后一跳鏈路沒有辦法計(jì)算其可利用帶寬。

（2）ICMP數(shù)據(jù)報產(chǎn)生的時間和阻塞的ICMP傳輸?shù)穆窂娇赡軐?dǎo)致較大的誤差。

（3）ICMP數(shù)據(jù)報在傳輸?shù)倪^程中可能會丟失，所有的數(shù)據(jù)報也有可能不是通過同一條鏈路達(dá)到目的節(jié)點(diǎn)，可能會造成錯誤的測量。

（4）對于Internet中的某些節(jié)點(diǎn)路由安裝了阻止ICMP報通過的防火墻，導(dǎo)致了ICMP不能成功地被源節(jié)點(diǎn)接收到。

（5）由于在計(jì)算單鏈路的可用帶寬是用式（4）來進(jìn)行計(jì)算的，計(jì)算出的各單鏈路的可用帶寬小于實(shí)際帶寬，設(shè)Ai0（1≤i≤n-1）為單鏈路Ri-1Ri的實(shí)際可用帶寬，Ai1為其計(jì)算出的可用帶寬?？梢杂檬剑?）計(jì)算出Ai1，下面是計(jì)算實(shí)際可用帶寬的公式：

Ai0=流量/時間=[30000+60×（31-i）×2]/ti=（33720-120×i） / ti（1≤i≤n-1≤30） （6）

設(shè)△Ai（1≤i≤n-1）為測量可用帶寬與實(shí)際帶寬之差，則有下式：

△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測量出來的可用帶寬是越接近目的節(jié)點(diǎn)就越真實(shí)。因此它所測出的瓶頸鏈路趨向于較前的阻塞鏈路。

3 RPT算法的改進(jìn)

本文主要針對上面的第（5）點(diǎn)不足之處提出了RPT的改進(jìn)算法。本文把探測包序列由120個數(shù)據(jù)報組成（跟Path-neck一樣），所有數(shù)據(jù)報的大小是500Byte，即總字節(jié)數(shù)為500×120=60000Byte。前30個數(shù)據(jù)報的生命周期TTL從1遞增到30，中間60個數(shù)據(jù)報的生命周期TTL為255或64，最后30個數(shù)據(jù)報的生命周期TTL從30遞減到1，其中前后30個數(shù)據(jù)報的作用仍然是獲得整個數(shù)據(jù)報序列通過某個節(jié)點(diǎn)的時間。如圖4所示。

設(shè)ti1'， ti2’（ 1≤i≤n-1）分別為數(shù)據(jù)報序列到達(dá)第i個節(jié)點(diǎn)的時刻和所有數(shù)據(jù)報序列通過該節(jié)點(diǎn)的時刻，都是通過獲得第i個節(jié)點(diǎn)傳回的ICMP獲得，則此數(shù)據(jù)報序列通過該節(jié)點(diǎn)所花的時間由下式獲得

ti’=ti2’-ti1’ （8）

該節(jié)點(diǎn)接收到120-2×（i-1）=120-2×i+2=122-2×i個數(shù)據(jù)報，則該節(jié)點(diǎn)接收到的流量為

Si=數(shù)據(jù)報個數(shù)×數(shù)據(jù)報大小=（122-2×i）×500=61000-1000×I （9）

可以得到第i個（1≤i≤n-1）條鏈路的可用帶寬Ai’：

Ai’=流量/時間= Si+/ ti’=61000-1000i/（ ti2’-ti1’） （10）

該算法提高了計(jì)算可用帶寬的精確度以及提高了瓶頸鏈路的準(zhǔn)確度，但是并沒有解決Path-neck的其他四點(diǎn)不足。

4 改進(jìn)的RPT算法與RPT的測試比較

下載Pathneck-1.3的源碼，在此基礎(chǔ)上完成了Pathneck-1.3改進(jìn)版的源碼。Pathneck-1.3改進(jìn)版的輸入是目的地址IP，參數(shù)設(shè)置為confidence_threshold≥10%，Detection_rate≥50%，輸出結(jié)果是途徑的節(jié)點(diǎn)IP地址和兩個數(shù)據(jù)報序列通過該節(jié)點(diǎn)的時間間隔，本文用該應(yīng)用程序?qū)ww.163.com進(jìn)行了100此次測試，測試結(jié)果表明該鏈路途徑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）等九個節(jié)點(diǎn)。這100次探測的結(jié)果如表1所示。

表1 兩種RPT算法在經(jīng)過100次測試的成功記錄表

測試結(jié)果兩種均成功原RPT改進(jìn)RPT兩種均不成功

次數(shù)5826160

對測試的結(jié)果取兩種算法都成功的58次的原始數(shù)據(jù)作為研究對象，通過式（11）分別求得RPT和改進(jìn)的RPT通過第i（1≤i≤n-1）個節(jié)點(diǎn)的平均時間間隔值 和 ： （11）

再通過方差公式（11）計(jì)算時間間隔的平方差σ1i，σ2i：

當(dāng) >3σki（其中j表示第j次測試在第i個節(jié)點(diǎn)的時間間隔，k=1，2）時，可以認(rèn)為此次測試無效，將其丟棄。通過如此過濾后的測試次數(shù)為49次，于是可以通過式（11）求得的平均值作為通過該節(jié)點(diǎn)的時間間隔，再通過式（4）和式（10）分別求可用帶寬，如表2所示。

從表2可以看出，改進(jìn)后的可用帶寬明顯比原算法的帶寬大，其范圍正好符合式（7'）的要求。

5 結(jié)束語

上面的試驗(yàn)結(jié)果得出如下結(jié)論：改進(jìn)算法計(jì)算出來的可用帶寬比Pathneck-1.3更加準(zhǔn)確；改進(jìn)算法確定的瓶頸鏈路也更加準(zhǔn)確。