馬宏艷

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

關(guān)鍵詞：多播；網(wǎng)絡(luò)鏈路；丟包率；網(wǎng)絡(luò)仿真軟件

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2015）04-00-04

0 引 言

隨著網(wǎng)絡(luò)的迅速發(fā)展，各種類型網(wǎng)絡(luò)業(yè)務(wù)也不斷的增長，高質(zhì)量的網(wǎng)絡(luò)服務(wù)也迫在眉睫，對現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)的了解是高效管理的前提，因此網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)推測算法的研究成了重點(diǎn)。研究結(jié)果表明多源網(wǎng)絡(luò)結(jié)構(gòu)更接近實(shí)際的網(wǎng)絡(luò)，端到端的主動測量技術(shù)中，探測包之間具有很強(qiáng)的相關(guān)性，通過研究探測包的丟包率可以推斷網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

1 多源測量技術(shù)

多源測量[1-3]，也稱多點(diǎn)測量，多源測量技術(shù)是采用多個源節(jié)點(diǎn)對多個目的節(jié)點(diǎn)的端到端測量，是單源測量方法的擴(kuò)展。在實(shí)際網(wǎng)絡(luò)測量的過程中，許多網(wǎng)絡(luò)需要通過多源測量技術(shù)才能覆蓋到所有的鏈路。在圖1所示的網(wǎng)絡(luò)拓?fù)渲校袃蓚€發(fā)送源節(jié)點(diǎn)分別是0和1，節(jié)點(diǎn)2和3是網(wǎng)絡(luò)的內(nèi)部節(jié)點(diǎn)，節(jié)點(diǎn)4和5作為網(wǎng)絡(luò)的接收節(jié)點(diǎn)。如果采用單點(diǎn)測量技術(shù)，產(chǎn)生的測量子樹1并不能覆蓋網(wǎng)絡(luò)中的所有鏈路。同理，如果把節(jié)點(diǎn)1作為探測包的發(fā)送源時產(chǎn)生的測量子樹2也不能覆蓋所有的鏈路。這時，就需要用到多點(diǎn)測量技術(shù)，即從節(jié)點(diǎn)0和1同時發(fā)送數(shù)據(jù)包，才能得到完全的網(wǎng)絡(luò)性能參數(shù)。

2 多源多播丟包率的算法

多播丟包率推斷算法是利用探測包之間的相關(guān)性進(jìn)行估計。在一個深度大于1的網(wǎng)絡(luò)拓?fù)渲校瑥脑垂?jié)點(diǎn)發(fā)出的探測包到達(dá)每個分支節(jié)點(diǎn)后被復(fù)制，然后傳輸?shù)竭_(dá)下一個節(jié)點(diǎn)，直至目的節(jié)點(diǎn)。對于每一個探測包來說，如果這個包到達(dá)了目的節(jié)點(diǎn)，那么它一定先經(jīng)過內(nèi)部分支節(jié)點(diǎn)。接收端的每個探測包，在共享鏈路上一定具有完全相同的性能，即這些探測包之間是完全相關(guān)的，利用這種相關(guān)性就可以推導(dǎo)出給定節(jié)點(diǎn)的成功傳輸概率。常見算法包括DE（Direct Estimation）算法，EM（Expectation Maximum）算法和PMLE（Pseudo Maximum Likelihood Estimate）算法。DE和EM計算量大，計算效率低。PMLE算法，又稱為快速算法，它是極大似然估計算法的一種近似[4]。

重復(fù)以上過程計算出所有的網(wǎng)絡(luò)鏈路的探測包。但是當(dāng)多個子節(jié)點(diǎn)同時未收到探測包時，PMLE算法將默認(rèn)這些子節(jié)點(diǎn)的父節(jié)點(diǎn)也沒有收到探測包。多個子節(jié)點(diǎn)同時發(fā)生丟包的可能性很?。?PMLE算法的計算過程是自底向上的，當(dāng)對父節(jié)點(diǎn)的估計出現(xiàn)誤差后，這種誤差隨著拓?fù)浣Y(jié)構(gòu)中層級遞增而遞增，也會層間疊加。如果一個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的層級越多，使用PMLE算法推斷出的鏈路丟包率誤差越大。

2.2 u-PMLE算法

5 結(jié) 語

本文結(jié)合PMLE算法和加權(quán)平均算法二者的優(yōu)勢，將基于u-PMLE算法的加權(quán)平均算法應(yīng)用于多源網(wǎng)絡(luò)中，推測出整個網(wǎng)絡(luò)的丟包性能。比較得出基于PMLE的加權(quán)平均算法和基于u-PMLE的加權(quán)平均算法，證明提出的算法是更精確的網(wǎng)絡(luò)鏈路丟包率的算法。

參考文獻(xiàn)

[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] 吳文佳，張建中，張元鵬.基于丟包率的多播網(wǎng)絡(luò)拓?fù)渫茢嗨惴╗J].計算機(jī)工程，2010（1）：124-126.

[4] 何仁清.基于網(wǎng)絡(luò)透視技術(shù)的丟包率推理算法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2006.

[5] 林文.基于網(wǎng)絡(luò)層析的丟包率推斷算法研究[D].廈門：廈門大學(xué)，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] 費(fèi)高雷.基于單播端到端測量的網(wǎng)絡(luò)性能參數(shù)估計方法研究[D].成都：電子科技大學(xué)，2012.

[8] 吳光偉，劉雙艷，宋進(jìn).基于網(wǎng)絡(luò)斷層掃描的傳感器網(wǎng)絡(luò)鏈路丟包研究[J]. 計算機(jī)技術(shù)與發(fā)展，2012，22（3）：64-66，70.