尹文濤,楊京禮,姜守達,魏長安

(哈爾濱工業(yè)大學自動化測試與控制系,黑龍江哈爾濱 150080)

?

基于子樹丟包模式的鏈路丟包率快速推斷算法

尹文濤,楊京禮,姜守達,魏長安

(哈爾濱工業(yè)大學自動化測試與控制系,黑龍江哈爾濱 150080)

摘要：為提高網絡鏈路丟包率的測量速度,本文提出一種基于子樹丟包模式的鏈路丟包率推斷算法.該算法通過選擇合理的鏈路丟包率初始值以減少迭代次數;根據端到端測量結果將網絡拓撲劃分為傳輸狀態(tài)確定性區(qū)域和非確定性區(qū)域,避免確定性區(qū)域冗余分解造成的時間開銷;通過對非確定性區(qū)域子樹丟包模式按層分解,以子樹丟包模式為基本計算單元,減少非確定性區(qū)域鏈路丟包的重復分解過程,提高鏈路丟包率計算速度.仿真結果表明,該算法能在不損失測量精度的前提下,減少鏈路丟包率測量總時間,提高測量速度.

關鍵詞:網絡測量;網絡層析成像;鏈路丟包率;丟包模式

1引言

隨著計算機網絡規(guī)模的擴大,以及網絡安全需求的不斷提高,傳統(tǒng)的基于網絡中間節(jié)點協(xié)作的網絡測量方法面臨巨大挑戰(zhàn).網絡層析成像技術[1]將醫(yī)學上的計算機層析成像思想引入到計算機網絡測量中,根據在網絡邊界上獲得的端到端的測量數據來分析和推斷網絡拓撲結構[2]、鏈路丟包率[3,4]、鏈路時延[5]等網絡內部性能參數,對網絡中的故障鏈路進行診斷和定位.網絡層析成像技術可以在無需中間節(jié)點協(xié)作的條件下估計網絡內部鏈路參數,克服了傳統(tǒng)方法的不足,是目前大規(guī)模網絡性能測量最有前景的方法之一.

目前,有些學者已經提出一些基于網絡層析成像技術的鏈路丟包率推斷算法.文獻[3,6]提出兩種基于極大似然估計的鏈路丟包率推斷算法.其中文獻[3]提出的DE(Direct Estimator)算法通過求解高階方程計算鏈路丟包率;文獻[6]提出采用EM(Expectation Maximization)算法通過執(zhí)行一個迭代過程逐步搜索高維解空間進行求解.該類算法精度最高,但當網絡規(guī)模較大時,算法復雜度極高.文獻[7,9]首先搜索網絡中的擁塞鏈路,通過將非擁塞鏈路從路由矩陣中去除,以化簡路由矩陣,然后進行鏈路丟包率求解.該類算法具有較低的算法復雜度,但在鏈路丟包率計算過程中將部分丟包率不為零的鏈路從路由矩陣中去除,因此會產生一定的誤差,且該類算法均建立在網絡中擁塞鏈路比例較小的假設條件之下.文獻[10]提出一種自底向上的鏈路丟包率估計算法,首先估計葉鏈路丟包率,然后再自底向上逐層求解鏈路丟包率.該算法利用兄弟鏈路之間的相關性,直接給出解析解,極大地降低了算法復雜度,但在逐層求解的過程中引入累積誤差,導致算法精度有所降低.文獻[11]對自底向上的方法進行改進,在計算鏈路k的成功傳輸概率統(tǒng)計父節(jié)點收到探測包個數時,忽略了節(jié)點k的父節(jié)點收到,但同時在鏈路k和鏈路k的兄弟節(jié)點都丟包的探測包,影響了算法精度.文獻[12]將EM算法和自底向上算法合并,首先采用自底向上方法直接求解葉鏈路丟包率,然后將求解的葉鏈路丟包率作為初始值,采用EM算法推斷內部鏈路丟包率.該算法解決了自底向上方法內部鏈路丟包率估計引入累積誤差的問題,但估計內部鏈路時,仍通過執(zhí)行迭代過程搜索高維解空間進行求解,因而算法復雜度仍較高.文獻[13]提出的FPA(Fast Path-based Approach)算法利用子樹丟包之間的相關性,直接求解鏈路丟包率,該算法具有較低的算法復雜度,但由于該算法在求解過程中忽略了部分全局信息,算法精度有所降低.

本文根據網絡丟包的特性,提出了一種基于子樹丟包模式的鏈路丟包率推斷算法,在保證精度的前提下,提升推斷過程的計算速度,減少鏈路丟包率測量的總時間.

2模型與假設

2.1網絡模型

用T=(V,L)表示邏輯樹狀網絡拓撲模型[3,13],其中V為節(jié)點集合,代表網絡中的路由器和主機,L為連接節(jié)點的鏈路集合.節(jié)點O∈V為T的根節(jié)點.節(jié)點集合R?V(無子節(jié)點的節(jié)點)表示所有的葉節(jié)點,即探測報文接收節(jié)點,|R|為葉節(jié)點個數.每個非葉節(jié)點k都至少有一個子節(jié)點,節(jié)點k的子節(jié)點集合用c(k)表示.每個非根節(jié)點k有且僅有一個父節(jié)點,用f(k)表示.鏈路(f(k),k)∈L記為鏈路k.定義f1=f且fn(k)=f(fn-1(k)),其中n為正整數.用集合a(k)={i∈V|?n>0,i=fn(k)}表示節(jié)點k的祖先節(jié)點,用集合U=V{O}表示非根節(jié)點集合,用集合I=UR表示非葉節(jié)點非根節(jié)點集合,即網絡內部節(jié)點集合.T(k)=(V(k),L(k))表示以節(jié)點k為根的子樹,其葉節(jié)點集合為R(k)=R∩V(k);

2.2丟包模型假設

與大多數文獻[10～13]一樣,本文假設:

(1)在探測周期內,網絡拓撲結構不發(fā)生變化;

(2)鏈路丟包過程為相互獨立的伯努利(Bernoulli)過程,即同一探測包經過不同的鏈路的丟包事件相互獨立,不同探測包經過同一鏈路的丟包事件相互獨立.

對每一個鏈路k∈L,用αk(1)∈[0,1]表示探測包從節(jié)點f(k)經過鏈路k被成功傳輸的概率,即αk(1)=P{xk=1|xf(k)=1};αk(0)=1-αk(1)表示探測包經過鏈路k被丟失的概率,即鏈路丟包率.定義|L|(|L|為鏈路個數)維向量A=(α1(0),α2(0),…,α|L|(0))為全部鏈路的丟包率,A即為要通過統(tǒng)計方法推測的參數.

L(X;A)=lg(P(X;A))

(1)

通過極大似然估計,可得鏈路丟包率估計值為:

(2)

2.3基于EM的鏈路丟包率估計

在每次探測中,僅有葉節(jié)點的探測結果為可觀測數據(用Y=XR=(xk:k∈R)表示),而網絡內部節(jié)點的探測結果是未知的,因此不能使用式(2)直接求解鏈路的丟包率.文獻[6]提出用EM算法求解鏈路丟包率,主要通過以下兩步進行求解:

(3)

其中

(4)

(5)

可得鏈路k的丟包率估計值為:

(6)

3基于子樹丟包模式的鏈路丟包率推斷算法

3.1鏈路丟包率初始值計算

現有EM算法鏈路丟包率初始值一般任意給定,迭代次數較多.由于更精確的鏈路丟包率初始值能減少EM算法迭代次數,從而提高算法速度,本文提出一種快速鏈路丟包率估計算法,利用該算法求得的結果對EM算法鏈路丟包率進行初始化.

(7)

其中,nr1和nr2分別表示被分支r1、r2接收到的探測包個數,n(xr1=1,xr2=1)表示同時被分支r1、r2成功接收到的探測包個數.對所有的內部節(jié)點k,都可以根據式(7)計算出探測包在路徑p0,k上的成功傳輸概率.對于葉節(jié)點r,由于葉節(jié)點探測結果是可以觀測到的,故路徑p0,r上的成功傳輸概率估計值可以直接求出:

(8)

用式(7)和(8)求出所有非根節(jié)點的路徑成功傳輸概率后,即可根據父子節(jié)點的路徑成功傳輸概率關系求出所有鏈路的丟包率:

(9)

本文采用式(9)得出的鏈路丟包率估計值,作為EM算法鏈路丟包率初始值.

3.2網絡拓撲傳輸狀態(tài)獨立區(qū)域劃分

由于僅有葉節(jié)點的探測結果是可以觀測到的,而網絡內部節(jié)點的探測結果是不能觀測到的,故對于一次探測過程,僅有葉節(jié)點和成功接收到該探測包的葉節(jié)點的祖先節(jié)點的探測結果是可以確定的,其他節(jié)點的探測結果是不能確定的.對任意鏈路k=(f(k),k),根據葉節(jié)點探測結果可以得到該鏈路對應的父子節(jié)點的探測結果有如表1所示五種情況.其中第1、2種情況鏈路傳輸狀態(tài)是確定的,第3、4、5種情況鏈路的傳輸狀態(tài)是不確定的.根據鏈路傳輸狀態(tài)是否確定,將整個網絡鏈路分為兩個部分,傳輸狀態(tài)確定性區(qū)域A(L;y)和傳輸狀態(tài)非確定性區(qū)域B(L;y).在該次探測過程中,探測包在A(L;y)中的所有鏈路都被成功傳輸或丟失,而在B(L;y)中的所有鏈路上的傳輸狀態(tài)是不確定的.如圖2 所示拓撲,當葉節(jié)點探測結果為y=(1,0,1,0,0,0,0,1,0,0,0,0,0)時,探測包在圖中實線表示的鏈路上被成功傳輸,在虛線表示的鏈路上被丟失,在點劃線表示的鏈路上探測包的傳輸狀態(tài)不能確定.故A(L;y)為圖中實線和虛線表示的鏈路集合,B(L;y)為圖中點劃線表示的鏈路集合.

表1　節(jié)點探測結果及對應鏈路傳輸狀態(tài)

當節(jié)點k的探測結果不確定時,其全部非葉子孫節(jié)點的探測結果都是不確定的,由表1可得,當鏈路k的傳輸狀態(tài)不確定時,其全部的子孫鏈路的傳輸狀態(tài)都是不確定的.因此,B(L;y)中鏈路可構成一系列沒有公共節(jié)點的子樹.用Tf(k)表示節(jié)點k的父節(jié)點f(k)與子樹T(k)構成的子樹,則圖2中傳輸狀態(tài)不確定鏈路構成子樹Tf(2)和Tf(10).由鏈路丟包的獨立性假設,可得這些沒有公共節(jié)點的子樹傳輸狀態(tài)相互獨立.令Bk(L;y)=L(Tf(k)),可將B(L;y)進一步劃分成一系列傳輸狀態(tài)非確定性獨立區(qū)域{Bk(L;y)}k.圖2中B(L;y)可以劃分成獨立區(qū)域B2(L;y)和B10(L;y),如圖3所示.

3.3子樹丟包模式

(10)

(11)

(12)

故對于非葉節(jié)點所對應的丟包模式,用式(10)計算出葉節(jié)點對應丟包模式的概率后,即可按照式(12)自底向上計算出所有內部節(jié)點對應的丟包模式概率.

(13)

3.4鏈路丟包率計算

對于葉節(jié)點r,由于葉節(jié)點探測結果是可以觀測到的,故葉節(jié)點接收到的探測包個數:

(14)

令

(15)

代入式(4)可得

(16)

(17)

(18)

3.5算法復雜度分析

表2　丟包模式及計算相應變量所需乘法次數

4仿真

為對本文提出LIALP算法性能進行驗證,本文從鏈路丟包率測量精度與速度兩個方面對算法進行考察,并與現有EM算法[6]和FPA算法[13]進行比較.

4.1MATLAB模型仿真

為考察算法計算時間和誤差隨拓撲層數的變化,本文按圖5所示方法構造每層節(jié)點數目為3,拓撲層數分別為2至9的8個拓撲.所有拓撲的鏈路丟包率服從均勻分布:αk(0)～Uniform[0,0.2].對每個拓撲,均產生100個丟包率組合,重復進行100次實驗,探測包個數為500.圖6-7分別給出了本文提出的LIALP算法、EM算法和FPA算法鏈路丟包率測量計算時間和相對誤差隨網絡拓撲層數的變化.從圖6可以看出,本文提出的LIALP算法鏈路丟包率測量計算時間較現有EM算法有明顯降低,而且隨著拓撲層數的增加,這種優(yōu)勢更加明顯,當網絡拓撲層數為8時,LIALP算法計算時間(0.1182s)僅為EM算法計算時間(9.3563s)的1.26%.FPA算法利用子樹丟包之間的相關性直接求解鏈路丟包率,不需要迭代計算,故算法計算速度最快.但由于FPA算法在求解的過程中,將網絡拓撲拆分成單個子樹后進行計算,忽略了部分全局信息,使得算法精度有所降低.如圖7所示,當網絡拓撲層數為8時,FPA算法精度較LIALP算法降低19.5%.

為考察在網絡不同擁塞程度下算法精度的變化,本文采用圖2所示拓撲,所有鏈路丟包率服從均勻分布:αk(0)～Uniform[αave-0.02,αave+0.02],其中αave為丟包率均值,αave=0.05,0.10,…,0.30.探測包個數為500,重復100次試驗.圖8給出了鏈路丟包率測量相對誤差隨鏈路丟包率均值的變化情況.從圖可以看出,LIALP算法和EM算法測量相對誤差明顯小于FPA算法,三種算法測量相對誤差都隨鏈路丟包率均值的增大而增大,且FPA算法增大的更快.

4.2NS2仿真

增加探測包個數即增加采樣點數,能減小鏈路丟包率測量誤差,但是增加探測包個數會導致探測時間增加,從而導致測量總時間增加.本文采用NS2仿真進一步比較算法精度隨探測包個數的變化,以及在相同精度條件下鏈路丟包率測量總時間.采用NS2構建如圖2所示的網絡.該網絡包含20個節(jié)點和19條鏈路.所有鏈路的帶寬均為10Mbps,每條鏈路的物理傳播時延為10ms,隊列長度為50,排隊模型為FIFO(First In First Out),擁塞避免算法采用尾部丟棄(Drop-tail).仿真背景流由兩部分組成:(1)服從Pareto分布的On/Off模型120條UDP流和120條TCP流.發(fā)送節(jié)點和接收節(jié)點在所有節(jié)點中隨機選擇.(2)疊加在每條鏈路上的服從Pareto分布的On/Off模型UDP流和TCP流.每條鏈路上的UDP流和TCP流個數均為15至30之間的隨機整數.UDP流和TCP流的On期和Off期均為200ms,UDP流的速率為0.5Mbps,TCP流的速率為0.2Mbps.探測包為從根節(jié)點向全部葉節(jié)點發(fā)送的恒定速率多播包,其大小為50Byte,發(fā)送速率為0.2Mbps.

表3和圖9分別給出了探測包個數為500、1000、…、10000時,三種算法鏈路丟包率測量計算時間和相對誤差的變化情況.從中可以看出,三種算法計算時間都隨探測包個數的增加而增大,相對誤差都隨著探測包的個數的增加而降低.當探測包個數相同時,LIALP算法和EM算法精度最高,FPA算法計算時間最短,但誤差最大,故在相同測量精度條件下,FPA算法需要發(fā)送的探測包最多.所需探測包個數越多,則探測時間越長,從而導致鏈路丟包率測量總時間越長.表4給出了當相對誤差為1%時,三種算法所需探測包個數、鏈路丟包率計算時間和測量總時間.從表中可以看出,在誤差相同的條件下,FPA算法的鏈路丟包率計算時間(0.13s)最短,但需要的探測包個數(5000)較LIALP算法和EM算法(3300)多51.5%.LIALP算法鏈路丟包率測量速度最快,其測量總時間(7.23s)僅為現有EM算法(103.95s)的6.96%,FPA算法(10.13s)的71.37%.

表3　三種算法計算時間(s)隨探測包個數的變化

表4　三種算法探測包個數、計算時間和測量總時間

5結論

本文根據網絡鏈路丟包的特性,提出了一種基于子樹丟包模式的鏈路丟包率推斷算法.該算法能在保持現有EM算法較高精度的條件下,有效減少鏈路丟包率測量總時間,提高測量速度.在相同測量精度(相對誤差為1%)下,該算法測量速度較現有EM算法提高約13.4倍,較FPA算法提高40%.

參考文獻

[1]Coates A,Hero III A O,Nowak R,et al.Internet tomography[J].IEEE Signal Processing Magazine,2002,19(3):47-65.

[2]張潤生,李艷斌,李嘯天.基于合并分層聚類的網絡拓撲推斷算法[J].電子學報,2013,41(12):2346-2352.

Zhang Run-sheng,Li Yan-bin,Li Xiao-tian.Agglomeration hierarchical clustering based algorithm for network topology inference[J].Acta Electronica Sinica,2013,41(12):2346-2352.(in Chinese)

[3]Cáceres R,Duffield N G,Horowitz J,et al.Multicast-based inference of network-internal loss characteristics[J].IEEE Transactions on Information Theory,1999,45(7):2462-2480.

[4]Fei G,Hu G.Accurate and effective inference of network link loss from unicast end-to-end measurements[J].IET Communications,2012,6(17):2989-2997.

[5]Zhang Zhi-yong,Fei Gao-lei,Pan Shenli.Afast link delay distribution inference approach under a variable bin size model[J].IEICE Transactions on Communications,2013,96(2):504-507.

[6]Bu T,Duffield N,Presti F L,et al.Network tomography on general topologies[A].ACM SIGMETRICS Performance Evaluation Review[C].New York:ACM,2002.21-30.

[7]Nguyen H X,Thiran P.Network loss inference with second order statistics of end-to-end flows[A].Proceedings of ACM SIGCOMM’07[C].New York:ACM,2007.227-240.

[8]Qiao Yan,Qiu Xue-song,Meng Luo-ming,et al.Efficient loss inference algorithm using unicast end-to-end measurements[J].Journal of Network and Systems Management,2013,21(2):169-193.

[9]顧然,邱雪松,喬焰,等.基于非線性規(guī)劃的鏈路丟包率推理算法[J].電子與信息學報,2012,34(6):1425-1431.

Gu Ran,Qiu Xue-song,Qiao Yan,et al.Link loss inference algorithm with nonlinear programming[J].Journal of Electronics & Information Technology,2012,34(6):1425-1431.(in Chinese)

[10]Zhu W,Geng Z.A bottom-up inference of loss rate[J].Computer Communications,2005,28(4):351-365.

[11]Li Y J,Cai W D.Afast multicast-based approach to inferring loss performance[J].Journal of Communication and Computer,2006,3(3):19-24.

[12]Zhang Jian-zhong,Lin Wen,Lin Jun-wu.Multicast-based inference of network internal loss from end-to-end data[A].IEEE 9th International Conference on Signal Processing[C].Beijing:IEEE,2008.2045-2048.

[13]Su H,Li Y,Lin S,et al.Inference of link loss rates by explicit estimation[J].IET Communications,2010,4(5):540-550.

尹文濤男,1983年生于湖北孝感,哈爾濱工業(yè)大學自動化測試與控制系博士研究生.主要研究方向為網絡測量與網絡層析成像技術.

E-mail:huayichu@163com

楊京禮男,1984年生于山東日照,哈爾濱工業(yè)大學自動化測試與控制系講師.主要研究方向為網絡測量與網絡層析成像技術.

E-mail:icehit0615@163com

姜守達(通信作者)男,1964年出生黑龍江伊春,哈爾濱工業(yè)大學自動化測試與控制系教授.主要研究方向為虛擬試驗技術,網絡測量技術,數字信號處理等.

E-mail:jsd@hit.edu.cn

魏長安男,1981年生于河北承德,哈爾濱工業(yè)大學自動化測試與控制系講師.主要研究方向為虛擬試驗技術,自動測試技術等.

A Fast Network Link Loss Inference Algorithm Based on Subtree Loss Pattern

YIN Wen-tao,YANG Jing-li,JIANG Shou-da,WEI Chang-an

(AutomaticTestandControlInstitute,HarbinInstituteofTechnology,Harbin,Heilongjiang150080,China)

Abstract:In order to improve the efficiency of link loss inference algorithm,a novel inference algorithm based on subtree loss pattern is proposed.The iterations of the algorithm are reduced by obtaining a more appropriate initialization of loss rates.According to the outcomes of end-to-end measurements,this algorithm partitions the network topology into one area in which the transmission state is determinate,and several areas in which the transmission state is indeterminate.By decomposing all the indeterminate areas,a subtree loss pattern database is constructed.The loss rate is calculated based on the loss pattern.Through reducing the redundancy decomposition process,it can speed up the process of the inference of the link loss rate.Simulation results show that the algorithm can reduce the time of link loss rate inference with identical accuracy.

Key words:network measurement;network tomography;link packet loss rate;loss pattern

作者簡介

DOI:電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.011

中圖分類號:TP393

文獻標識碼：A

文章編號：0372-2112 (2016)03-0565-07

基金項目:黑龍江省博士后基金(No.LBHZ11171)

收稿日期:2014-05-08;修回日期:2014-08-27;責任編輯:梅志強