梁永生，高波，鄒粵，張基宏，張乃通

（1. 深圳信息職業(yè)技術(shù)學(xué)院 可視媒體處理與傳輸深圳市重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518172；

2. 深圳大學(xué) 信息工程學(xué)院，廣東 深圳 518060；3. 哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，黑龍江 哈爾濱 150001）

1 引言

網(wǎng)絡(luò)時(shí)延是主要的網(wǎng)絡(luò)性能指標(biāo)之一，一般為數(shù)據(jù)從開始進(jìn)入網(wǎng)絡(luò)到離開網(wǎng)絡(luò)的傳輸時(shí)間。在不同的傳輸介質(zhì)和節(jié)點(diǎn)設(shè)備中，采用不同的網(wǎng)絡(luò)架構(gòu)和協(xié)議，網(wǎng)絡(luò)時(shí)延大小也就不同，一般分為鏈路時(shí)延和節(jié)點(diǎn)時(shí)延2種，等于節(jié)點(diǎn)處理時(shí)延、排隊(duì)時(shí)延、傳輸時(shí)延和傳播時(shí)延四者之和。本文中的網(wǎng)絡(luò)鏈路時(shí)延是指發(fā)生在不同地點(diǎn)的網(wǎng)絡(luò)時(shí)延的統(tǒng)稱。

網(wǎng)絡(luò)鏈路時(shí)延推測(cè)是IP網(wǎng)絡(luò)的熱點(diǎn)研究問題。傳統(tǒng)的網(wǎng)絡(luò)鏈路時(shí)延推測(cè)是基于路由器或者路由器協(xié)作的，但是通常情況下，網(wǎng)絡(luò)路由情況很難得到。端到端網(wǎng)絡(luò)鏈路時(shí)延推測(cè)就是根據(jù)已經(jīng)測(cè)量得到的端到端網(wǎng)絡(luò)路徑時(shí)延，推測(cè)出網(wǎng)絡(luò)內(nèi)部鏈路時(shí)延分布的過程，它能夠克服傳統(tǒng)方法的弊端。通過網(wǎng)絡(luò)鏈路時(shí)延推測(cè)能夠獲知網(wǎng)絡(luò)時(shí)延趨勢(shì)、了解網(wǎng)絡(luò)性能并可監(jiān)控、規(guī)劃和管理網(wǎng)絡(luò)。

目前，國內(nèi)外學(xué)者廣泛采用最大似然估計(jì)方法(MLE, maximum likelihood estimation)推測(cè)網(wǎng)絡(luò)鏈路時(shí)延，但是應(yīng)用該方法存在以下2個(gè)主要問題。

1) 應(yīng)用最大期望(EM, expectation maximization)算法求解似然函數(shù)，運(yùn)算量過大，計(jì)算復(fù)雜度過高，實(shí)際推測(cè)環(huán)境難以及時(shí)反映網(wǎng)絡(luò)狀態(tài)的要求。

2) 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和推測(cè)分組發(fā)送方式是時(shí)延推測(cè)有確定解的決定因素，如何確定適宜的發(fā)分組方式是需要重點(diǎn)考慮的問題。

基于上述分析，本文在2個(gè)假設(shè)——網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)已知且穩(wěn)定、鏈路性能時(shí)空獨(dú)立的前提下，給出了網(wǎng)絡(luò)時(shí)延推測(cè)模型和端到端路徑時(shí)延數(shù)據(jù)采集方法，提出了一種基于鏈路重構(gòu)—解構(gòu)的端到端網(wǎng)絡(luò)鏈路時(shí)延推測(cè)方法，首先應(yīng)用偽似然估計(jì)將原推測(cè)問題分解為若干獨(dú)立子問題分別求解。然后應(yīng)用鏈路重構(gòu)—解構(gòu)確定可求解的推測(cè)單元，控制平均采樣精度和減少推測(cè)單元鏈路數(shù)，從而顯著降低計(jì)算復(fù)雜度。解決了計(jì)算復(fù)雜度過高及不滿足有確定解拓?fù)湎碌那蠼鈫栴}。最后利用基于模型的計(jì)算和基于NS2的仿真實(shí)驗(yàn)進(jìn)行了驗(yàn)證研究。

2 國內(nèi)外研究現(xiàn)狀

眾多國內(nèi)外學(xué)者對(duì)網(wǎng)絡(luò)時(shí)延進(jìn)行研究。文獻(xiàn)[1]首次從硬件層面對(duì)IEEE標(biāo)準(zhǔn)容限內(nèi)的以太網(wǎng)轉(zhuǎn)發(fā)時(shí)延進(jìn)行測(cè)試和分析，推導(dǎo)了以太網(wǎng)交換機(jī)內(nèi)部轉(zhuǎn)發(fā)時(shí)延和頻偏時(shí)延的計(jì)算公式，進(jìn)行了以太網(wǎng)交換機(jī)一次、二次轉(zhuǎn)發(fā)時(shí)延測(cè)試，驗(yàn)證了時(shí)鐘頻偏是交換機(jī)轉(zhuǎn)發(fā)時(shí)延的主要影響因素。文獻(xiàn)[2]提出了一種啟發(fā)式算法，采用離散時(shí)延模型對(duì)時(shí)延進(jìn)行分片，但是計(jì)算復(fù)雜度較高。文獻(xiàn)[3]提出了一種快速鏈路時(shí)延分布推測(cè)方法，首先基于網(wǎng)絡(luò)子樹分割技術(shù)，通過準(zhǔn)確計(jì)算估計(jì)節(jié)點(diǎn)累積時(shí)延分布，然后由估計(jì)的累積時(shí)延分布得到單個(gè)鏈路時(shí)延分布；而且為了有效獲取鏈路時(shí)延的本質(zhì)特征，提出了一種可變二進(jìn)制大小的離散鏈路模型。文獻(xiàn)[4,5]提出了一種不需網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)協(xié)作，依靠端到端測(cè)量推測(cè)鏈路時(shí)延累積量的方法，根據(jù)鏈路時(shí)延累積量和路徑實(shí)驗(yàn)累積量的關(guān)系建立線性方程，然后求解方程得到鏈路時(shí)延累積量的最優(yōu)估計(jì)值。文獻(xiàn)[6]針對(duì)可以用指數(shù)隨機(jī)變量模型來描述的網(wǎng)絡(luò)鏈路時(shí)延，提出了一種最大似然估計(jì)器，應(yīng)用EM算法，在初始參數(shù)不是很大的情況下，求解較快。文獻(xiàn)[7]提出一種偽似然估計(jì)方法，降低了鏈路時(shí)延推測(cè)的指數(shù)級(jí)復(fù)雜度到，其中m為鏈路時(shí)延采樣精度，P為路徑的平均鏈路數(shù)，I為除發(fā)分組節(jié)點(diǎn)外的端節(jié)點(diǎn)數(shù)；西北工業(yè)大學(xué)的李貴山在偽似然估計(jì)算法的基礎(chǔ)上，采用重采樣技術(shù)優(yōu)化時(shí)延分布結(jié)果[8]。文獻(xiàn)[9]提出一種最優(yōu)EM算法，但是以損失推測(cè)精度為代價(jià)。文獻(xiàn)[10]提出用改進(jìn)的蟻群算法來加快 EM算法的收斂速度，這種方法可以用于大型網(wǎng)絡(luò)鏈路時(shí)延推測(cè)。文獻(xiàn)[11]提出了一個(gè)面向單條鏈路的傳輸控制協(xié)議(TCP, transmission control protocol)綜合傳輸性能測(cè)度R，分析其與同一時(shí)間粒度內(nèi)鏈路的占用帶寬和用戶數(shù)據(jù)報(bào)協(xié)議(UDP, user datagram protocol)流量比例間的關(guān)系，結(jié)果表明R 測(cè)度可表示為以占用帶寬和 UDP 流量比例為參數(shù)的正態(tài)分布的隨機(jī)過程。在推測(cè)中，遵從本文的2個(gè)假設(shè)，把邏輯多播樹轉(zhuǎn)換為依賴樹，從源節(jié)點(diǎn)發(fā)送探針分組，從葉子節(jié)點(diǎn)接收，采集端到端時(shí)延測(cè)量結(jié)果，推測(cè)鏈路的離散時(shí)延分布[12]。貝葉斯推斷的基本方法是將待估參數(shù)的先驗(yàn)信息和樣本的信息綜合，然后根據(jù)貝葉斯定理得到其后驗(yàn)信息，接下來根據(jù)后驗(yàn)信息去推測(cè)未知參數(shù)。貝葉斯方法可以用于網(wǎng)絡(luò)鏈路時(shí)延推測(cè)，但是推測(cè)的直接計(jì)算比較困難，目前一般的貝葉斯計(jì)算方法是 MCMC(Markov chain monte carlo)，其實(shí)質(zhì)就是利用Markov Chain進(jìn)行蒙特卡羅積分[13]。文獻(xiàn)[14]基于主干網(wǎng)絡(luò)時(shí)延測(cè)量，提出了一種應(yīng)用主成份分析的網(wǎng)絡(luò)時(shí)延結(jié)構(gòu)分析方法，把網(wǎng)絡(luò)時(shí)延時(shí)序分解為平滑的周期性態(tài)勢(shì)和一組稀疏的突發(fā)流量。文獻(xiàn)[15]提出了一種基于累積生成函數(shù) (CGF, cumulative generating function)的逆函數(shù)法，利用最小二乘法求解鏈路時(shí)延，結(jié)果接近極大似然估計(jì)方法的估計(jì)值，但需要特殊的發(fā)分組方案以構(gòu)造滿秩路由矩陣。北京郵電大學(xué)交換技術(shù)通信網(wǎng)國家重點(diǎn)實(shí)驗(yàn)室在時(shí)延分布估計(jì)，分組丟失率估計(jì)和網(wǎng)絡(luò)瓶頸推測(cè)等有比較深入的研究，焦利等應(yīng)用 CGF方法來推測(cè)網(wǎng)絡(luò)鏈路時(shí)延分布和確定網(wǎng)絡(luò)的瓶頸鏈路[16]。文獻(xiàn)[17]提出一種基于矩的估計(jì)方法，估計(jì)性能參數(shù)的N階矩，但在計(jì)算中只對(duì)某些特定的時(shí)延分布函數(shù)有較高效率。文獻(xiàn)[18]提出了一種改進(jìn)的基于矩的估計(jì)方法，采用 MLE和EM-MLE推測(cè)網(wǎng)絡(luò)鏈路時(shí)延，計(jì)算復(fù)雜度較高。文獻(xiàn)[19]提出分層處理網(wǎng)絡(luò)拓?fù)涞姆椒ǎ鶕?jù)公共鏈路之間關(guān)系和協(xié)方差屬性來估計(jì)鏈路時(shí)延數(shù)值，當(dāng)鏈路時(shí)延差距較大時(shí)，推測(cè)精度較高。

綜合國內(nèi)外研究現(xiàn)狀來看，如何降低偽似然估計(jì)算法的計(jì)算復(fù)雜度，并保證具有確定解，則成為網(wǎng)絡(luò)鏈路時(shí)延推測(cè)研究的關(guān)鍵。

3 相關(guān)工作

3.1 時(shí)延推測(cè)前提

網(wǎng)絡(luò)拓?fù)浍@取是鏈路時(shí)延推測(cè)算法中的首要問題，它決定了端時(shí)延特性與鏈路時(shí)延特性的映射關(guān)系。本文假設(shè)網(wǎng)絡(luò)拓?fù)湟阎曳€(wěn)定，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的獲取不列入本文研究內(nèi)容。

假設(shè)在推測(cè)過程中，Xm(p)是鏈路m上第 p個(gè)推測(cè)分組的累積時(shí)延，隨機(jī)變量Xm(p)服從某種分布[20]，則有

即不同推測(cè)分組p、q在同一鏈路m上的時(shí)延相互獨(dú)立，同一推測(cè)分組p在不同鏈路m、n上的時(shí)延也相互獨(dú)立?；诰W(wǎng)絡(luò)鏈路時(shí)空獨(dú)立性假設(shè)，可以簡化路徑時(shí)延與鏈路時(shí)延的關(guān)系，路徑時(shí)延分布可簡單看作鏈路時(shí)延分布的卷積。

3.2 時(shí)延推測(cè)模型

時(shí)延推測(cè)網(wǎng)絡(luò)模型如圖1所示，0為發(fā)送節(jié)點(diǎn)，1和2是中間節(jié)點(diǎn)，3、4、5和6是接收節(jié)點(diǎn)。發(fā)分組節(jié)點(diǎn)與接收節(jié)點(diǎn)之間構(gòu)成網(wǎng)絡(luò)路徑，發(fā)生在其上的網(wǎng)絡(luò)時(shí)延構(gòu)成路徑時(shí)延向量DP。發(fā)分組節(jié)點(diǎn)與中間節(jié)點(diǎn)、中間節(jié)點(diǎn)與接收節(jié)點(diǎn)之間構(gòu)成網(wǎng)絡(luò)鏈路，發(fā)生在其上的網(wǎng)絡(luò)時(shí)延構(gòu)成鏈路時(shí)延向量DL。本文研究的網(wǎng)絡(luò)鏈路時(shí)延推測(cè)就是根據(jù)路徑時(shí)延向量DP，推測(cè)出鏈路時(shí)延向量DL。其中，A是所有推測(cè)網(wǎng)絡(luò)路徑對(duì)應(yīng)的0-1路由矩陣，每一行對(duì)應(yīng)一條推測(cè)網(wǎng)絡(luò)路徑，由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)唯一確定；ε是時(shí)延推測(cè)誤差，在理想時(shí)延推測(cè)模型下，可以取ε=0。

圖1 時(shí)延推測(cè)網(wǎng)絡(luò)模型

網(wǎng)絡(luò)時(shí)延是網(wǎng)絡(luò)服務(wù)質(zhì)量 (QoS, quality of service)中的加性參數(shù)，對(duì)于接收節(jié)點(diǎn)r有

其中，0,rPd 是在發(fā)送節(jié)點(diǎn)0到接收節(jié)點(diǎn)r的路徑上測(cè)得的時(shí)延；di是以節(jié)點(diǎn)i為結(jié)尾的鏈路網(wǎng)絡(luò)時(shí)延，且節(jié)點(diǎn)i在路徑P0,r上。

由圖1可知，A顯然是4×6矩陣，為非滿秩矩陣，這樣向量DL無法通過向量DP與A的逆直接求解，這也正是本文研究的關(guān)鍵所在。

3.3 路徑時(shí)延數(shù)據(jù)采集

對(duì)于路徑時(shí)延數(shù)據(jù)采集，本文通過獲取 ICMP（Internet control message protocol）協(xié)議返回的時(shí)間戳進(jìn)行計(jì)算。圖2為RTT(round trip time)示意，其中ST是發(fā)送時(shí)間戳，RT1是接收時(shí)間戳，RT2是返回時(shí)間戳，AT是傳送時(shí)間戳。

圖2 RTT示意圖

通常情況下，發(fā)送端和接收端的系統(tǒng)時(shí)間不一致，所以不能簡單地通過AT-ST來計(jì)算網(wǎng)絡(luò)路徑時(shí)延[21,22]。

為了更精確測(cè)得網(wǎng)絡(luò)路徑時(shí)延，本文以發(fā)送端的系統(tǒng)時(shí)間為基準(zhǔn)，假定網(wǎng)絡(luò)在傳輸數(shù)據(jù)分組的一段時(shí)間內(nèi)保持穩(wěn)定，則可利用數(shù)據(jù)分組往返時(shí)間的一半來計(jì)算網(wǎng)絡(luò)路徑時(shí)延，如式(4)所示。

4 PLE推測(cè)方法

由3.2節(jié)可知，端到端網(wǎng)絡(luò)鏈路時(shí)延推測(cè)可以歸結(jié)為一個(gè)統(tǒng)計(jì)逆問題，為了降低計(jì)算復(fù)雜度，現(xiàn)有的經(jīng)典求解方法都是將原始的 MLE問題變換為PLE問題，將原來復(fù)雜的整體問題分解為一系列簡單的子問題，并通過分別求解子問題從而獲得整體問題的求解。

由此鏈路時(shí)延推測(cè)的似然函數(shù)如式(6)所示。

式(6)中參數(shù)θ的最大似然估計(jì)值通常通過最大化 Lp得到，但是由式(6)可知，直接通過(Lp;θ)'=0來求得θ是不易實(shí)現(xiàn)的。本文采用 EM 算法進(jìn)行迭代求解。假設(shè) XS是已知數(shù)據(jù)，且當(dāng)前參數(shù)為θ(k)，則目標(biāo)函數(shù)Q的第k+1次的取值為

這樣參數(shù)θ的最大似然估計(jì)值就可以通過最大化Q來得到。

本文中 Li表示以節(jié)點(diǎn) i結(jié)尾的網(wǎng)絡(luò)鏈路，表示第 m個(gè)推測(cè)分組在鏈路 Li上的網(wǎng)絡(luò)時(shí)延，其中n為推測(cè)分組總數(shù)。在推測(cè)過程中，設(shè)鏈路Li上可能出現(xiàn)的最大時(shí)延和推測(cè)精度分別為q，令，則鏈路時(shí)延的可能取值為

其中，k=0表示該推測(cè)分組在節(jié)點(diǎn)i上轉(zhuǎn)發(fā)隊(duì)列長度為 0。如果推測(cè)過程中發(fā)現(xiàn)分組丟失，則該次推測(cè)無效。對(duì)于iLd 的每一個(gè)取值，有

其中， PLi(k)表示鏈路Li上網(wǎng)絡(luò)時(shí)延為kq的概率。在3.1節(jié)的假設(shè)前提下，推測(cè)分組時(shí)延和鏈路時(shí)延在時(shí)序上相互獨(dú)立，這樣本文研究的問題進(jìn)一步轉(zhuǎn)化為：由邊緣接收節(jié)點(diǎn)組成的路徑時(shí)延 DP的概率分布，推測(cè)網(wǎng)絡(luò)內(nèi)部鏈路時(shí)延DL的概率分布。

假設(shè)鏈路Li上傳輸ni個(gè)推測(cè)分組，其中時(shí)延為kq的推測(cè)分組數(shù)量為 ai(k)，則

實(shí)際上，ni可由選取的推測(cè)單元直接得到，而ai(k)不能直接得到。如果已知所有鏈路的時(shí)延概率分布 PL，則 ai(k)就有一個(gè)期望最大值。設(shè)有一個(gè)推測(cè)單元 u∈U，鏈路 Li在推測(cè)網(wǎng)絡(luò)路徑中，即，rx和ry為u的2個(gè)接收節(jié)點(diǎn)，在一次網(wǎng)絡(luò)鏈路時(shí)延推測(cè)過程中，得到的時(shí)延二元組為

每一個(gè)推測(cè)單元的時(shí)延二元組構(gòu)成一種輸出模式，在推測(cè)過程中，假設(shè)該輸出模式出現(xiàn)的次數(shù)為C(Du)，則式(11)變?yōu)?/p>

其中，C(Du)可以通過統(tǒng)計(jì)推測(cè)單元的觀測(cè)數(shù)據(jù)得到，對(duì)于某一個(gè)推測(cè)單元的，有

在鏈路Li上，設(shè) dPf(i),rx、dPf(i),ry分別為其父節(jié)點(diǎn)f(i)到接收節(jié)點(diǎn) rx、ry的網(wǎng)絡(luò)時(shí)延。推測(cè)單元 u中的則可通過式(14)遞推得到。

設(shè)節(jié)點(diǎn)i的直接子節(jié)點(diǎn)為d(i)，則

同理可求得 P (Di,k,y)。

當(dāng)節(jié)點(diǎn)i為接收節(jié)點(diǎn)時(shí)，顯然有

計(jì)算時(shí)，首先確定一個(gè)初始分布PL，然后應(yīng)用式(12)迭代求解，直到推測(cè)誤差小于預(yù)先設(shè)定值，則停止迭代，求解結(jié)束。

5 鏈路重構(gòu)—解構(gòu)算法

第4節(jié)中的PLE推測(cè)方法，雖然能夠較為準(zhǔn)確地推測(cè)出網(wǎng)絡(luò)鏈路時(shí)延分布情況，但是仍有2個(gè)明顯不足。

2) 推測(cè)網(wǎng)絡(luò)必須滿足每一個(gè)內(nèi)部節(jié)點(diǎn)至少是一種推測(cè)單元的分支點(diǎn)，否則無法得到確定解。

為此，本文提出一種鏈路重構(gòu)—解構(gòu)算法，結(jié)合時(shí)延分發(fā)算法，在保證時(shí)延推測(cè)有確定解的同時(shí)，顯著降低計(jì)算復(fù)雜度。

5.1 有確定解的推測(cè)方案

網(wǎng)絡(luò)傳輸數(shù)據(jù)分組有單播和多播2種方式，簡言之，單播就是一對(duì)一的通信方式，而多播就是一對(duì)多的通信方式。在時(shí)延推測(cè)過程中，通過一次發(fā)分組，多播方式可以獲得多條推測(cè)路徑，所以多播方式的推測(cè)效率比單播方式高，但是實(shí)際上多播方式在網(wǎng)絡(luò)中的支持有限。

有確定解的推測(cè)方案是網(wǎng)絡(luò)鏈路時(shí)延推測(cè)的基礎(chǔ)，文獻(xiàn)[23]給出了滿足有確定解的推測(cè)方案的充要條件如下。

1) 每一個(gè)中間節(jié)點(diǎn)至少是一個(gè) k(k>1)播推測(cè)單元的分支點(diǎn)。

2) 接收節(jié)點(diǎn)必須被一個(gè)或者多個(gè)推測(cè)單元覆蓋。

由上述分析可知，推測(cè)方案有確定解的充要條件是當(dāng)且僅當(dāng)組成該推測(cè)方案的所有推測(cè)單元都有確定解。文獻(xiàn)[24]提出了一種模擬多播方式，本文就采用其中的背靠背發(fā)分組方式獲得路徑時(shí)延數(shù)據(jù)。圖3所示為本文采用的3種推測(cè)單元，圖 3(a)由一條鏈路組成，顯然推測(cè)單元的時(shí)延分布可以直接得到，所以這是有確定解的推測(cè)單元；圖 3(b)是常見的二鏈路單元，它的時(shí)延分布與鏈路不是一一對(duì)應(yīng)的，所以這是無確定解的推測(cè)單元；圖 3(c)是最簡單的有分叉網(wǎng)絡(luò)，它的時(shí)延分布與鏈路是一一對(duì)應(yīng)的，所以這也是有確定解的推測(cè)單元。

圖3 推測(cè)單元

對(duì)于圖3(b)，在鏈路時(shí)空相關(guān)性的假設(shè)下，首先推測(cè)包含節(jié)點(diǎn) 1的鏈路時(shí)延1LD ，然后推測(cè)包含節(jié)點(diǎn)1、2的路徑時(shí)延(1,2)PD ，則包含節(jié)點(diǎn)2的鏈路時(shí)延2LD 為

其中，(1/*)為反卷積運(yùn)算。

5.2 鏈路重構(gòu)—解構(gòu)

所謂鏈路重構(gòu)即是將首尾相連的若干鏈路看作一條邏輯鏈路，根據(jù)實(shí)際網(wǎng)絡(luò)拓?fù)?，可以在多處進(jìn)行鏈路的重構(gòu)，并不是所有首尾相連的鏈路都可以重構(gòu)，重構(gòu)的前提是重構(gòu)后的邏輯鏈路仍然滿足鏈路時(shí)延分布的獨(dú)立性假設(shè)，重構(gòu)的好處是可以降低計(jì)算復(fù)雜度；鏈路解構(gòu)則是劃分重構(gòu)后的邏輯推測(cè)單元，使得由這些推測(cè)單元組成的推測(cè)方案滿足有確定解的充要條件。

圖4 鏈路重構(gòu)—解構(gòu)

實(shí)際上，對(duì)于每一種輸出模式，建立對(duì)應(yīng)的鏈路時(shí)延檢索表，通過掃描該表可直接計(jì)算。對(duì)于網(wǎng)絡(luò)中的一個(gè)推測(cè)單元，可采用一種自上而下的分配方法得到鏈路時(shí)延的可能集，其基本思想就是每次都把推測(cè)單元映射成三層樹，接收節(jié)點(diǎn)為葉子節(jié)點(diǎn)，從第一條鏈路開始，每次確定一條鏈路的取值范圍，最后得到時(shí)延向量集S，從而

以圖4所示的推測(cè)單元為例，鏈路時(shí)延集為四維向量，引入R(i)表示包含在節(jié)點(diǎn)i的子節(jié)點(diǎn)中的接收節(jié)點(diǎn)，時(shí)延分發(fā)流程如圖5所示。

圖5 時(shí)延分發(fā)流程

6 實(shí)驗(yàn)研究及結(jié)果分析

6.1 基于模型的計(jì)算

基于模型的計(jì)算，首先設(shè)定推測(cè)網(wǎng)絡(luò)鏈路時(shí)延離散概率分布參數(shù)，然后應(yīng)用賭輪算法生成對(duì)應(yīng)的時(shí)延分布，保存網(wǎng)絡(luò)路徑時(shí)延數(shù)據(jù)，最后應(yīng)用上述算法推測(cè)網(wǎng)絡(luò)鏈路時(shí)延分布。

本文采用圖6所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行實(shí)驗(yàn)研究，其中發(fā)分組節(jié)點(diǎn) f是在圖1上添加而來，節(jié)點(diǎn) 0、1和 2是中間節(jié)點(diǎn)，推測(cè)單元分別選擇<3,4>和<5,6>，鏈路 L0的時(shí)延分布 PL0可直接得到。設(shè)定鏈路時(shí)延概率分布參數(shù)，由賭輪算法產(chǎn)生目標(biāo)時(shí)延分布，隨機(jī)選取某一推測(cè)單元的目標(biāo)節(jié)點(diǎn)發(fā)送 10 000個(gè)推測(cè)分組，設(shè)定推測(cè)誤差時(shí)迭代停止。很顯然圖 6中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不滿足有確定解的條件，所以首先應(yīng)用鏈路重構(gòu)，然后解構(gòu)出鏈路L1與L2，對(duì)應(yīng)的時(shí)延分布為 PL1與 PL2，其中 PL2的推測(cè)結(jié)果如圖7(a)所示。應(yīng)用重構(gòu)—解構(gòu)推測(cè)的鏈路L3的時(shí)延分布PL3的推測(cè)結(jié)果如圖7(b)所示。

圖7 鏈路時(shí)延推測(cè)結(jié)果

對(duì)于算法的收斂性，本文采用當(dāng)前參數(shù)與上一次迭代所得參數(shù)的均方誤差來判定算法每次迭代的收斂情況。當(dāng)次間差值接近0且基本穩(wěn)定時(shí)，則認(rèn)為算法已找到極值。

由圖7可知，k值不同時(shí)，推測(cè)值與真實(shí)值都較接近，這說明本文提出的算法是可行的。最大誤差出現(xiàn)在鏈路2中，當(dāng)K=3時(shí)，最大值為31.5%，這與初始值的選擇有關(guān)。在以后的推測(cè)過程中，可以根據(jù)一定的先驗(yàn)知識(shí)，選取適當(dāng)?shù)某跏贾祦斫鉀Q這個(gè)問題，本文在初始時(shí)取均勻分布。通過基于模型的計(jì)算結(jié)果分析可知，本文提出的方法在網(wǎng)絡(luò)鏈路時(shí)延推測(cè)方面具有應(yīng)用價(jià)值，可為網(wǎng)絡(luò)性能評(píng)價(jià)提供依據(jù)。

圖8 推測(cè)時(shí)間

6.2 基于NS2的仿真

在圖6中，各鏈路的帶寬設(shè)置為：BL0=4 Mbit/s、BL1=2 Mbit/s、BL2=2 Mbit/s、BL3=1 Mbit/s、BL4=1 Mbit/s、BL5=1 Mbit/s和BL6=1 Mbit/s。采用固定碼率(CBR,constants bit rate)發(fā)送背靠背推測(cè)分組模擬多播方式。為了模擬實(shí)際的網(wǎng)絡(luò)環(huán)境，實(shí)驗(yàn)網(wǎng)絡(luò)背景流量采用以下方式實(shí)現(xiàn)：在節(jié)點(diǎn)f上掛接一個(gè)1.5 Mbit/s的固定碼率數(shù)據(jù)發(fā)送；在節(jié)點(diǎn)0上掛接2個(gè)FTP服務(wù)，分別連到接收節(jié)點(diǎn) 4、節(jié)點(diǎn) 6。網(wǎng)絡(luò)鏈路的隊(duì)列長度為10 000，在鏈路時(shí)延不斷波動(dòng)的情況下，盡量保證推測(cè)分組成功到達(dá)接收節(jié)點(diǎn)。在仿真實(shí)驗(yàn)研究中，鏈路 L0的帶寬較寬、時(shí)延基本恒定，而其他鏈路的時(shí)延都會(huì)發(fā)生明顯的變化。

在實(shí)驗(yàn)研究中，推測(cè)精度 q可從大到小進(jìn)行嘗試選取，直到目標(biāo)鏈路時(shí)延分布精度滿足要求為止。離散化網(wǎng)絡(luò)時(shí)延時(shí)，通常通過觀察閑時(shí)目標(biāo)網(wǎng)絡(luò)來確定0點(diǎn)，但是觀察到的路徑時(shí)延最小值不能直接作為0點(diǎn)，最佳值應(yīng)為處理時(shí)延、傳輸時(shí)延和傳播時(shí)延三者之和。為了方便起見，本文直接將觀察到的最小路徑時(shí)延作為 0點(diǎn)處理。

應(yīng)用AWK腳本計(jì)算網(wǎng)絡(luò)路徑時(shí)延、統(tǒng)計(jì)網(wǎng)絡(luò)鏈路真實(shí)的時(shí)延分布情況。鏈路1和鏈路3上推測(cè)得到的與真實(shí)的時(shí)延分布情況如圖9所示。

圖9 鏈路時(shí)延仿真結(jié)果

由圖9可知，k值不同時(shí)，推測(cè)值與真實(shí)值都較接近，最大誤差出現(xiàn)在鏈路3中，當(dāng)K=4時(shí)，最大值為22.5%，這與選取的q值有關(guān)。對(duì)于可變采樣，時(shí)延變化較劇烈的鏈路3可采用更大的q值，本文取 q3=0.005，其他鏈路取 q=0.001。由于實(shí)際鏈路情況是未知的，q可從大到小試取，直到鏈路時(shí)延分布精度滿足要求為止，達(dá)到精度與復(fù)雜度的平衡。由NS2仿真結(jié)果分析可知，本文提出的方法在網(wǎng)絡(luò)鏈路時(shí)延推測(cè)方面具有應(yīng)用價(jià)值，可為網(wǎng)絡(luò)性能評(píng)價(jià)提供依據(jù)。

7 結(jié)束語

本文對(duì)端到端網(wǎng)絡(luò)鏈路時(shí)延推測(cè)方法進(jìn)行了研究，應(yīng)用偽似然估計(jì)將原推測(cè)問題分解為若干獨(dú)立子問題分別求解；應(yīng)用鏈路重構(gòu)—解構(gòu)確定可求解的推測(cè)單元；通過控制平均采樣精度和減少推測(cè)單元鏈路數(shù)，從而顯著降低計(jì)算復(fù)雜度，解決了運(yùn)算復(fù)雜度過高及不滿足有確定解拓?fù)湎碌木W(wǎng)絡(luò)鏈路時(shí)延推測(cè)求解問題。理論分析和實(shí)驗(yàn)研究結(jié)果表明，基于鏈路重構(gòu)—解構(gòu)的端到端網(wǎng)絡(luò)鏈路時(shí)延推測(cè)方法在保證有推測(cè)確定解的前提下，顯著降低計(jì)算復(fù)雜度。與經(jīng)典的基于CGF的網(wǎng)絡(luò)鏈路時(shí)延推測(cè)算法計(jì)算復(fù)雜度相當(dāng)，而且在推測(cè)過程中不必構(gòu)造滿秩路由矩陣。文中在2個(gè)假設(shè)的基礎(chǔ)上對(duì)普遍意義上的網(wǎng)絡(luò)模型進(jìn)行鏈路時(shí)延推測(cè)研究，如何反映實(shí)際網(wǎng)絡(luò)狀況有待進(jìn)一步研究。

[1] 梁永生, 張基宏, 張乃通. IEEE標(biāo)準(zhǔn)容限內(nèi)以太網(wǎng)轉(zhuǎn)發(fā)時(shí)延的測(cè)試與分析[J]. 電子學(xué)報(bào). 2008, 36(1): 46-50.LIANG Y S, ZHANG J H, ZHANG N T. Measurement and analysis of forwarding delay in ethernet architecture within tolerances of the IEEE specifications[J]. Acta Electronica Sinica, 2008, 36(1): 46-50.

[2] PRESTI F L, DUFFIELD N G, HOROWITZ J, et al. Multicast-based inference of network-internal delay distributions[J]. IEEE/ACM Transactions on Networking, 2002, 10(6): 761-775.

[3] ZHANG Z Y, FEI G L, PAN S L, et al. A fast link delay distribution inference approach under a variable bin size model[J]. IEICE Transactions on Communications, 2013, E96-B(2): 504-507.

[4] FEI G L, HU G M, JIANG X Y. Unicast-based inference of network link delay[A]. Proceedings of the 13th IEEE International Conference on Communication Technology (ICCT)[C]. Jinan, China, 2011. 146-150.

[5] 蔣小勇, 費(fèi)高雷, 胡光岷. 網(wǎng)絡(luò)鏈路時(shí)延統(tǒng)計(jì)量的層析成像方法[J].計(jì)算機(jī)工程與應(yīng)用, 2012, 48(3): 91-94, 208.JIANG X Y, FEI G L, HU G M. Network link delay statistics tomography[J]. Computer Engineering and Applications, 2012, 48(3):91-94, 208.

[6] XIA Y, TSE D. Inference of Link delay in communication networks[J].IEEE Journal on Selected Areas in Communications, 2006, 24(12):2235-2248.

[7] LIANG G, YU B. Maximum pseudo likelihood estimation in network tomography[J]. IEEE Transactions on Signal Processing, 2003, 8(51):2043-2053.

[8] 李貴山, 蔡皖東. 網(wǎng)絡(luò)鏈路時(shí)延分布估計(jì)方法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45(8): 20-22, 28.LI G S, CAI W D. Research on method for estimation of network link delay distributions[J]. Computer Engineering and Application, 2009,45(8): 20-22, 28.

[9] TSANG Y, COATES M, NOWAK R D. Network delay tomography[J].IEEE Transactions on Signal Processing, 2003, 8(51): 2125-2135.

[10] SUN H J. An improved ant-based EM algorithm for network link delay distributions inference[A]. Proceedings of the 2nd International Workshop on Education Technology and Computer Science(ETCS)[C].Wuhan, China, 2010. 48-51.

[11] 朱海婷, 丁偉, 繆麗華等. UDP 流量對(duì) TCP 往返延遲的影響[J].通信學(xué)報(bào), 2013, 34(1): 19-29.ZHU H T, DING W, LIAO L H, et al. Effect of UDP traffic on TCP’s round-trip delay[J]. Journal on Communications, 2013, 34(1): 19-29.

[12] 劉瑞芳, 謝東. 采用多播依賴樹模型估計(jì)鏈路時(shí)延分布[J]. 信息工程大學(xué)學(xué)報(bào), 2007, 8(4): 422-424.LIU R F, XIE D. Using dependence tree model for network delay tomography[J]. Journal of Information Engineering University, 2007,8(4): 422-424.

[13] GUO D, WANG X D. Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction[J].IEEE Transactions on Signal Processing, 2003, 8(51): 2205-2218.

[14] ABDELKEFI A, JIANG Y M. A structural analysis of network delay[A]. Proceedings of the 2011 Ninth Annual Communication Networks and Services Research Conference[C]. Ottawa, Canada,2011. 41-48.

[15] SHIH M F, HERO A O. Unicast inference of network link delay distributions from edge measurements[A]. Proceedings of the IEEE International Conference on Accost Speech and Signal Processing[C].Salt Lake City, USA, 2001. 3421-3424.

[16] 焦利, 林宇, 王文東等. 一種負(fù)載均衡網(wǎng)絡(luò)中內(nèi)部鏈路時(shí)延估計(jì)算法[J]. 軟件學(xué)報(bào), 2005, 16(5): 886-893.JIAO L, LIN Y, WANG W D, et al. A novel algorithm for link delay inference in the networks with load-balancing routing[J]. Journal of Software, 2005, 16(5): 886-893.

[17] LAWRENCE E, MICHAILIDIS G, NAIR V N. Fast, moment-based estimation methods for delay network tomography[J]. IEEE Transactions on Signal Processing, 2008, (9): 1-22.

[18] LIN J W, ZHANG J Z, LIN W. The improved method of moment for multicast-based delay distribution inference in network tomography[A].Proceedings of 2010 2nd International Conference on Advanced Computer Control(ICACC)[C]. Shenyang, China, 2010. 486- 489.

[19] LIN J W, ZHANG J Z. A High-efficiency algorithm for delay estimate in network tomography[J]. Journal of Computational Information Systems , 2010, 6(10): 3217-3226.

[20] COATES M, HERO A O, NOWAK R D, et al. Internet tomography[J].IEEE Signal Processing Magazine, 2002, 19(3): 47-65.

[21] LIANG Y S, ZHANG N T. The determination of the link with the smallest end-to-end network latency in ethernet architecture[J].Journal of Harbin Institute of Technology, 2007, 14(4): 489-495.

[22] CHOI J H, YOO C. Analytical derivation of one-way delay[J].Electronics Letters, 2003, 39 (25): 1871 -1872.

[23] LAWRENCE E, MICHAILIDIS G, NAIR V N. Network delay tomography using flexicast experiments[J]. Journal of the Royal Statistical Society, Series B, 2006, (68): 785-813.

[24] COATES M, NOWAK R D. Network tomography for internal delay estimation[A]. Proceedings of the IEEE International Conference on Accost Speech and Signal Processing[C]. Salt Lake City, USA, 2001.3409-3412.