一種快速精確的網絡鏈路丟包率算法研究

馬宏艷

摘 要：針對多源多播網絡鏈路丟包率的算法的研究，提出在多源多播網絡中，將修正后的PMLE算法和加權平均算法相結合的新算法，可以快速精確地計算網絡鏈路的丟包率，通過NS 2仿真實驗，驗證了新算法推測鏈路丟包率速度快，更接近真實值。

關鍵詞：多播；網絡鏈路；丟包率；網絡仿真軟件

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2015）04-00-04

0 引 言

隨著網絡的迅速發展，各種類型網絡業務也不斷的增長，高質量的網絡服務也迫在眉睫，對現有網絡結構的了解是高效管理的前提，因此網絡拓撲結構推測算法的研究成了重點。研究結果表明多源網絡結構更接近實際的網絡，端到端的主動測量技術中，探測包之間具有很強的相關性，通過研究探測包的丟包率可以推斷網絡的拓撲結構。

1 多源測量技術

多源測量[1-3]，也稱多點測量，多源測量技術是采用多個源節點對多個目的節點的端到端測量，是單源測量方法的擴展。在實際網絡測量的過程中，許多網絡需要通過多源測量技術才能覆蓋到所有的鏈路。在圖1所示的網絡拓撲中，有兩個發送源節點分別是0和1，節點2和3是網絡的內部節點，節點4和5作為網絡的接收節點。如果采用單點測量技術，產生的測量子樹1并不能覆蓋網絡中的所有鏈路。同理，如果把節點1作為探測包的發送源時產生的測量子樹2也不能覆蓋所有的鏈路。這時，就需要用到多點測量技術，即從節點0和1同時發送數據包，才能得到完全的網絡性能參數。

2 多源多播丟包率的算法

多播丟包率推斷算法是利用探測包之間的相關性進行估計。在一個深度大于1的網絡拓撲中，從源節點發出的探測包到達每個分支節點后被復制，然后傳輸到達下一個節點，直至目的節點。對于每一個探測包來說，如果這個包到達了目的節點，那么它一定先經過內部分支節點。接收端的每個探測包，在共享鏈路上一定具有完全相同的性能，即這些探測包之間是完全相關的，利用這種相關性就可以推導出給定節點的成功傳輸概率。常見算法包括DE（Direct Estimation）算法，EM（Expectation Maximum）算法和PMLE（Pseudo Maximum Likelihood Estimate）算法。DE和EM計算量大，計算效率低。PMLE算法，又稱為快速算法，它是極大似然估計算法的一種近似[4]。

重復以上過程計算出所有的網絡鏈路的探測包。但是當多個子節點同時未收到探測包時，PMLE算法將默認這些子節點的父節點也沒有收到探測包。多個子節點同時發生丟包的可能性很小； PMLE算法的計算過程是自底向上的，當對父節點的估計出現誤差后，這種誤差隨著拓撲結構中層級遞增而遞增，也會層間疊加。如果一個網絡拓撲結構的層級越多，使用PMLE算法推斷出的鏈路丟包率誤差越大。

2.2 u-PMLE算法

5 結 語

本文結合PMLE算法和加權平均算法二者的優勢，將基于u-PMLE算法的加權平均算法應用于多源網絡中，推測出整個網絡的丟包性能。比較得出基于PMLE的加權平均算法和基于u-PMLE的加權平均算法，證明提出的算法是更精確的網絡鏈路丟包率的算法。

參考文獻

[1] Rabbat M， Coates M， Nowak R. Multiple Source Internet Tomography[J]. IEEE Journal on Selected Areas in Communications，2006（12）：2221-2234.

[2] Yongjun Li， Wangdong Cai. A Fast Multicast-based Approach to Inferring Loss Performance[J]. Communication and Computer， 2006， 3（3）：19-24.

[3] 吳文佳，張建中，張元鵬.基于丟包率的多播網絡拓撲推斷算法[J].計算機工程，2010（1）：124-126.

[4] 何仁清.基于網絡透視技術的丟包率推理算法研究[D].哈爾濱：哈爾濱工業大學，2006.

[5] 林文.基于網絡層析的丟包率推斷算法研究[D].廈門：廈門大學，2009.

[6] Liao Hailiang， Hu Guangmin， Qian Feng， et al. Network Topology Inference Based on Traceroute and Tomography[J]. Journal of Software， 2010，21（1）： 133-146.

[7] 費高雷.基于單播端到端測量的網絡性能參數估計方法研究[D].成都：電子科技大學，2012.

[8] 吳光偉，劉雙艷，宋進.基于網絡斷層掃描的傳感器網絡鏈路丟包研究[J]. 計算機技術與發展，2012，22（3）：64-66，70.