一種快速精確的網(wǎng)絡(luò)鏈路丟包率算法研究

馬宏艷

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

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

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

0 引 言

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

1 多源測(cè)量技術(shù)

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

2 多源多播丟包率的算法

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

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

2.2 u-PMLE算法

5 結(jié) 語(yǔ)

本文結(jié)合PMLE算法和加權(quán)平均算法二者的優(yōu)勢(shì)，將基于u-PMLE算法的加權(quán)平均算法應(yīng)用于多源網(wǎng)絡(luò)中，推測(cè)出整個(gè)網(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] 吳文佳，張建中，張?jiān)i.基于丟包率的多播網(wǎng)絡(luò)拓?fù)渫茢嗨惴╗J].計(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)高雷.基于單播端到端測(cè)量的網(wǎng)絡(luò)性能參數(shù)估計(jì)方法研究[D].成都：電子科技大學(xué)，2012.

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