吳辰文，李培儒，茹俊年，劉香麗

蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

主動端到端離散式時延分布估計方法研究

吳辰文，李培儒，茹俊年，劉香麗

蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

隨著網(wǎng)絡(luò)信息化的快速發(fā)展，網(wǎng)絡(luò)性能測量逐漸成為一個重要的研究領(lǐng)域。而傳統(tǒng)的網(wǎng)絡(luò)測量方法受到安全因素的制約，只能測量權(quán)限范圍內(nèi)的網(wǎng)絡(luò)性能，因而一些研究者提出了一種新的網(wǎng)絡(luò)性能測量方法——網(wǎng)絡(luò)斷層掃描技術(shù)[1-3]，即NT技術(shù)（Network Tomography）。網(wǎng)絡(luò)斷層掃描技術(shù)是通過主動發(fā)送多播探測包獲得潛在的鏈路信息，應(yīng)用統(tǒng)計推斷的方法獲得網(wǎng)絡(luò)的時延、丟包率和拓?fù)浣Y(jié)構(gòu)等性能，已逐漸成為近年來網(wǎng)絡(luò)性能評價研究的熱點。

網(wǎng)絡(luò)性能測量中，時延性能檢測是網(wǎng)絡(luò)斷層掃描技術(shù)的一個重要研究內(nèi)容。目前的估計方法主要是基于連續(xù)時延模式[4]。國際國內(nèi)相關(guān)機構(gòu)不斷研究新的測量、估計方法，但是直接測量始終存在算法復(fù)雜度問題難以解決。在實際的測量過程中，大量網(wǎng)絡(luò)邊緣客戶接入點的計算量無法控制。從而導(dǎo)致連續(xù)時延模式估計算法無法適應(yīng)大規(guī)模網(wǎng)絡(luò)。

離散時延模式估計時延分布最早于2002年由Presti[5]等人提出，使用遞歸法估計時延分布情況。它并不是一般的最大似然估計MLE（Maximum Likelihood Estimator）問題，因為受到網(wǎng)絡(luò)規(guī)模等因素的限制，無法直接進(jìn)行計算。此后Liang和Yu提出了偽似然估計算法[6]，即MPLE算法（Maximum Pseudo Likelihood Estimation），它將路由矩陣劃分成數(shù)個區(qū)域，相比于原有的EM算法減小了計算的復(fù)雜度，但是針對不同的網(wǎng)絡(luò)拓?fù)渚仃嚾绾蝿澐?，劃分后如何合并的問題仍難以找到有效的解決方法。本文不使用單純的單播或者多播實驗，而描述一種較為靈活的組播探測實驗，將網(wǎng)絡(luò)拓?fù)鋭澐殖啥鄠€子樹，先后從廣度和深度兩個步驟研究鏈路時延的估計算法，探究最大似然估計問題的更快、更有效的解決方法。

1 離散時延估計原理

1.1 模型定義

網(wǎng)絡(luò)時延分布估計是將網(wǎng)絡(luò)抽象成樹狀邏輯網(wǎng)絡(luò)模型，即一個有向無環(huán)樹。用T=(V，E)來表示一棵樹，V表示節(jié)點集合，E表示鏈路集合。節(jié)點、鏈路遵循規(guī)范的編號方式，節(jié)點0表示根節(jié)點，所有鏈路用其末端節(jié)點所命名，如鏈路1表示節(jié)點0和節(jié)點1所鏈接的鏈路。 f(k)表示節(jié)點k∈V的父節(jié)點。在一棵樹中，除根節(jié)點0以外其余所有節(jié)點有唯一的父節(jié)點。遞歸定義fi(k)=f{fi?1(k)}，其中 f1(k)=f(k)。如果節(jié)點k在樹的L層上，則有 fL(k)=0。定義D(k)表示為節(jié)點k的子節(jié)點集合，集合中所有節(jié)點的父節(jié)點是節(jié)點k。用R表示葉子節(jié)點集合，即沒有子節(jié)點的集合。最后要說明一個概念，內(nèi)部節(jié)點是既擁有父節(jié)點，又擁有子節(jié)點的節(jié)點。如圖1所示，用一個簡單樹形結(jié)構(gòu)展示以上定義的概念。

網(wǎng)絡(luò)斷層掃描技術(shù)的時延分布推斷是一個大規(guī)模的逆概率估計問題。如圖1所示，可以使用9元的端到端的測量數(shù)據(jù)估計15條鏈路的時延分布情況，將構(gòu)成非滿序矩陣，無法求出時延分布的結(jié)果。而此9元測量數(shù)據(jù)之間的依賴關(guān)系則是解決問題的關(guān)鍵，通過對這種相互依賴關(guān)系的進(jìn)一步分析和挖掘，能夠為有效解決路徑時延到鏈路級信息的逆問題提供可行性途徑。因此，首先考慮使用最大似然估計算法MLE。

1.2 時延離散化

網(wǎng)絡(luò)時延狀況呈現(xiàn)隨機分布，但是可以將網(wǎng)絡(luò)中的時延簡單地看作好與差兩種狀態(tài)。探測包的時延保持在τ值以下時，網(wǎng)絡(luò)狀況被視為好；當(dāng)時延超過τ值，則網(wǎng)絡(luò)變得擁塞，網(wǎng)絡(luò)狀況被視為差，如圖2所示。

圖2 網(wǎng)絡(luò)時延狀況

然后，設(shè)定一個離散化的量化寬度值bin，根據(jù)bin尺寸的大小將時延τ進(jìn)行等長劃分[7]，如圖3所示。因此從根節(jié)點到葉子節(jié)點路徑上的時延Yr便可用離散數(shù)據(jù)來表示，其取值范圍為{0，q，2q，…，bq}，其中q是量化寬度bin的大小，b是最大離散時延值，q和b將用于所有鏈路Xk。本文將忽略丟失和差狀況下的時延數(shù)據(jù)。

圖3 時延離散化

雖然這個框架的設(shè)置看上去似乎很苛刻、死板，限制條件眾多，但是在實際應(yīng)用中卻不失其實用性。首先，根據(jù)實際的網(wǎng)絡(luò)流量數(shù)據(jù)顯示，網(wǎng)絡(luò)流量往往異于某一種或者幾種特定的網(wǎng)絡(luò)，如將網(wǎng)絡(luò)流量假設(shè)成泊松分布[8]并不能代表真實的網(wǎng)絡(luò)狀況，所以選擇一種特定的參數(shù)模型概括所有鏈路時延分布是非常困難的，實用性也并不強。其次，時延數(shù)據(jù)通常具有突發(fā)性的特點，在這種情況下末端分布是相當(dāng)有用的。離散模型對于首部共享鏈路過多的鏈路無法做任何假設(shè)，而通過發(fā)送足夠數(shù)量的探測包可估計末端分布估計。bin的大小可以通過收集來的數(shù)據(jù)做出相應(yīng)的調(diào)整，bin值較小時可以用來估計詳細(xì)信息分布；bin值較大時可用于獲取長尾信息。

定義P0，r為從節(jié)點0到節(jié)點r的路徑，路徑P0，r測得網(wǎng)絡(luò)時延是其經(jīng)過的各條鏈路時延累計的結(jié)果：

Y為測量所得路徑時延向量，X為鏈路時延向量，A為鏈路矩陣。例如，圖1中Y3=X1+X3。用αk(i)來表示鏈路k上時延等于iq的概率，即αk(i)=P(Xk=iq)，i=0，1，…，b。目的是用Yr的測量結(jié)果來估計一系列鏈路的時延分布情況，其中k∈E，i∈{0，1，…，b}。因此，αk= [αk(0)，αk(1)，…，αk(b)]為鏈路不同時延值概率向量，α= [α′0，α′1，…，α′|E|]′為各條鏈路的不同時延值的概率矩陣。用αu，v(i)來表示路徑Pu，v上的累計時延等于i的概率。

本文假設(shè)時延是時間獨立的，即在一段鏈路上的時延獨立于在另一段鏈路上的時延。只要發(fā)送的探測包之間的時間間隔足夠大，時間獨立的假設(shè)就是合理的。只要測試時間足夠短，對網(wǎng)絡(luò)情況不構(gòu)成重大改變，時間穩(wěn)定性也是合理的。

2 時延分布估計算法

2.1 組播發(fā)包策略

多播探測實驗易于實施，但它卻有計算量較大，難于計算的缺點。而單純的單播探測實驗很難將接收節(jié)點之間的相關(guān)性聯(lián)系起來，基于此原因使用組合單播探測包的方法可以改善這一不足，比如背靠背、三明治列車等組合單播策略[3]。而文中將會使用更加靈活的組播端到端測量[9-10]方法，該方法發(fā)送不同的探測包到不同的網(wǎng)絡(luò)區(qū)域，將網(wǎng)絡(luò)劃分成不同的子樹，探測包發(fā)送的強度不同可以取決于網(wǎng)絡(luò)服務(wù)質(zhì)量的不同。同時這種較為靈活的發(fā)包方法不同于以往依賴拓?fù)浠蛘邊?shù)分布狀況，它可以通過無參估計所有鏈路的時延分布情況。在實踐中，選擇的特定組播實驗將取決于不同的實際考慮。事實上可以改變組合方式，隨著時間的推移探索不同區(qū)域，不同強度取決于阻塞或其他可能出現(xiàn)的問題。其中對播策略是效率最高的，對播組將探測包經(jīng)過的路徑劃分成兩層三鏈子樹，將MLE問題規(guī)模始終控制為最佳。另一方面，相比多播實驗，對播策略使得探測包在網(wǎng)絡(luò)中的傳輸不影響網(wǎng)絡(luò)的負(fù)載狀況。因此，文中將以多對播策略作為主要研究手段。

每一種發(fā)包策略將從根節(jié)點0出發(fā)，而且接收節(jié)點必須覆蓋所有葉子節(jié)點。

定義1把從一個接收節(jié)點到k個指定接收節(jié)點的發(fā)包方式定義為k播組。

例如對1.1節(jié)中的圖1所示的邏輯網(wǎng)絡(luò)模型樹狀圖來說，假設(shè)定義＜2，12＞是一個對播（或2播）組，則＜8，9，13，14，15＞是一個5播組，其余的將分為一組，從而形成一個發(fā)包策略C，可表示為C={＜2，12＞，＜8，9，13，14，15＞，＜10，11＞}。而制定一個發(fā)包策略需要符合如下兩個條件：

（1）對于每一內(nèi)部節(jié)點s∈T{0，R}屬于至少一個k播組，k＞1。

（2）每一個接收節(jié)點r∈R至少屬于一種k播組。

2.2 分離子樹

通過設(shè)計不同的對播發(fā)包策略將樹狀網(wǎng)絡(luò)拓?fù)浞纸獬刹煌膬蓪尤溩訕?。此處所說的兩層三鏈子樹指的是對播實驗中探測包經(jīng)過的鏈路所組成的兩層的二叉樹，其中“鏈”并不是專指鏈路，它可能是鏈路也有可能是由多條鏈路組成的路徑。如圖4所示，以一個較為簡單的四層非對稱樹狀拓?fù)錇槔?，鏈路針對如圖4（a）所示樹狀網(wǎng)絡(luò)拓?fù)洌舭l(fā)包策略為C={＜2，5＞，＜3，6＞}，其中的對播組＜2，5＞將樹狀網(wǎng)絡(luò)拓?fù)浞蛛x為如圖4（b）所示的兩層三鏈子樹T2，5，“三鏈”分別由鏈路1、鏈路2和路徑 P1，5組成。同理，若C={＜2，3＞，＜5，6＞}，對播組＜5，6＞則可得到如圖4（c）所示的兩層三鏈子樹T5，6。

圖4 通過不同的發(fā)包策略分解成不同的兩層三鏈子樹

用T表示k播組的子樹，其中V表示節(jié)點，E表示鏈路。用 Xk={0，1，…，b}表示所有可能的鏈路時延。每個x∈X是一個|E|元。定義函數(shù) y(x，T)為在C策略中從x∈X中提升給端到端時延提升。把端到端時延的所有可能性定義為Y={y(x，T)|x∈X}。用γ(y)=P{Y=y}來定義端到端實驗結(jié)果的概率。

如圖4（b）所示，假設(shè)發(fā)送探測包到節(jié)點對＜2，5＞，b=1，那么 Xk∈{0，1}，鏈路E={1，2，4，5}，實際鏈路時延分別為0，1，0，1。則可以得x={0，1，0，1}，測得路徑時延為y=(1，1)，那么鏈路時延概率如下所示：

上述中測得路徑時延是所有可能鏈路時延情況概率之和，可以將上述等式泛化為普遍情況。因此，離散無參數(shù)分布框架可表示為路徑級數(shù)據(jù)多項式[11]。得到的觀測值包括多次觀測到的 y值，觀測次數(shù)用N來表示，則得到的似然等式如下所示：

這個問題是典型的不完整數(shù)據(jù)估計問題，此等式很難直接得到最大似然的估計結(jié)果。貝葉斯算法[11]已應(yīng)用到丟包率的分布估計之中，但是由于其依賴于先驗概率分布和不符合上述文中不選擇某一種特定的網(wǎng)絡(luò)參數(shù)模型概括所有鏈路時延分布的假設(shè)情況，EM算法[12]可以解決此問題，如果這些觀測數(shù)據(jù)是已知的，那么通過足夠多次的端到端的探測實驗，便可以很容易得到最大似然。

假設(shè)這些觀測數(shù)據(jù)是已知的，則可以通過足夠多次的端到端的探測實驗得到最大似然。得到最大似然的步驟（分為E步驟和M步驟）如下所示：

E步驟：假設(shè)已經(jīng)得到上一次迭代結(jié)果向量α(q-1)，首先，可以計算每條鏈路測量次數(shù)的期望值，得到的期望值如下所示：

然后利用這一期望值去計算鏈路k上探測包時延是i的次數(shù)N，得到的結(jié)果如下所示：

其中，公式（5）和公式（6）中的參數(shù)N表示實驗中觀測次數(shù)，公式（6）中的Mk，i是發(fā)包策略C中k鏈路上時延為i的總的數(shù)學(xué)期望。

M步驟：

其中，公式（7）中的參數(shù)mk是k鏈路上探測包測量的總次數(shù)。對于EM算法的迭代復(fù)雜度的研究，首先需要考慮對播組發(fā)包策略。每一個對播組實驗有|T|個鏈路時延可能結(jié)果，所以有b|T|個鏈路時延結(jié)果。而對所得的每個結(jié)果需要加入端到端鏈路時延的可能性計算之中，因此，每一棵子樹的E步驟的時間復(fù)雜度為O{b|T|}，而M步驟則由|Eb|個部分所組成。

2.3 移植算法

2.2節(jié)介紹的算法可較好地適應(yīng)樹狀網(wǎng)絡(luò)拓?fù)鋸V度規(guī)模的擴展，可估計得出發(fā)包策略C中所有兩層三鏈子樹三條“鏈”的時延分布，但是無法做到網(wǎng)絡(luò)拓?fù)涞纳疃孺溌窌r延估計，因為并不是每一條“鏈”都是鏈路，其中存在部分路徑，路徑由多條鏈路所組成，本節(jié)將使用移植算法剝離路徑中的鏈路時延。

移植算法GE（Grafting Estimation）的基本原理是用已知路徑和鏈路的時延分布推算未知鏈路的時延情況。如圖5所示，路徑P1，5為圖4（b）中兩層三鏈子樹T2，5中的一條“鏈”。其中，路徑P1，5的時延已由上一節(jié)估算可知，而鏈路5的時延也可通過其他發(fā)包策略得出，例如圖4（c）所示發(fā)包策略。因此，使用移植算法通過已知的路徑P1，5和鏈路5的時延計算未知鏈路4的時延情況。

圖5 移植算法

移植算法是一種固定點剝離方法，已知鏈路可能時延值的概率，將其固定，根據(jù)似然等式通過EM算法的多次迭代計算未知鏈路的值。在一條路徑上發(fā)送n個探測包，nd是路徑上時延值為d的次數(shù)。于是

E步驟：

其中，Mu是未知鏈路k上時延值為u的期望，α(u+v)是路徑時延為u+v的概率，α4(v)是鏈路4時延為v的概率，在公式（8）中α1，5是根據(jù)α4的更新而變化的。

M步驟：

普通的EM算法的計算量隨鏈路數(shù)量的不斷增長迭代次數(shù)呈指數(shù)增加。而移植算法的計算量隨各條鏈路中bin的增長鏈接所需的平均迭代次數(shù)呈線性增加。因此，通過不同發(fā)包策略的組合，此算法可以較好把握EM算法的尺度，復(fù)雜性為一個關(guān)于bin數(shù)量的三次多項式，從而可在一定程度上改進(jìn)最大似然計算的復(fù)雜程度，通過鏈路的移植使得計算速度也可響應(yīng)得以提高。

移植算法并不只適用于如圖5所示兩端鏈路的路徑，它可推廣于多段鏈路組成的路徑之中，依次剝離每一條鏈路。假設(shè)路徑 Pi，j由節(jié)點i，i+1，i+2，…，k，…，j組成，則剝離過程描述如下：

（1）已知路徑Pi，k時延，通過其他發(fā)包策略估計所得。

（2）將路徑Pi，j分解為路徑Pi，k和路徑Pk+1，j。

（3）通過已知的路徑 Pi，j和路徑 Pi，k的時延分布，使用移植算法估計路徑Pk+1，j時延情況，因此EM算法的公式（8）和公式（9）可演變?yōu)椋?/p>

E步驟：

（4）分別針對路徑Pi，k和路徑Pk+1，j重復(fù)（1）步驟，直到計算出路徑Pi，j中所有鏈路i，i+1，i+2，…，j的時延分布情況。

其中，若路徑Pi，j中 j=i+1，則路徑Pi，j表示鏈路j。

因此，設(shè)計不同的發(fā)包策略，在不同組播實驗中，對僅單一接收節(jié)點的單播實驗也可通過移植算法剝離確定每條鏈路的時延情況。

離散數(shù)據(jù)方程對一些鏈路可能導(dǎo)致估計值并不唯一。因為使用不同的發(fā)包策略或者不同發(fā)包策略組合可能計算出不同的時延估計值。針對這一問題，最簡單的解決方法是將這些計算結(jié)果用加權(quán)平均數(shù)的方法結(jié)合起來。

其中，n表示探測包個數(shù)，α⌒表示鏈路時延估計值。最終移植算法計算產(chǎn)生的估計是一致的或漸近的。

圖6 估計結(jié)果與真實值比較

該算法的復(fù)雜度較MLE算法直接估算有了明顯的簡化。根據(jù)公式（1）可知，根據(jù)測量數(shù)據(jù)Y和非滿序矩陣對向量X進(jìn)行逆估計較為困難，尤其是針對大規(guī)模網(wǎng)絡(luò)問題計算量更是呈指數(shù)上升。雖然MPLE算法一定程度上減少計算量，但鏈路矩陣的分塊問題并不容易解決。該算法將拓?fù)鋬刹絼澐?，首先劃分為兩層三鏈子樹，然后進(jìn)行路徑的分段，這就將最大似然的估計問題大大化簡，對兩步劃分子樹分別使用EM算法進(jìn)行計算，使得計算量始終維持在EM算法可計算的尺度之內(nèi)。

3 仿真實驗

針對以上文中提出的算法，下面將利用一個例子來說明，使用NS2模擬真實的網(wǎng)絡(luò)環(huán)境對其內(nèi)部鏈路時延分布進(jìn)行估計，以驗證之前提出算法的可行性。

對圖4（a）所示網(wǎng)絡(luò)拓?fù)溥M(jìn)行實驗。根節(jié)點0到節(jié)點1核心路由器之間的鏈路帶寬為500 Mb/s，葉子節(jié)點的帶寬為50 Mb/s，而其余路由器之間的連接使用300 Mb/s的帶寬，詳細(xì)實驗參數(shù)如表1所示。R核心路由器背景流量主要由TCP和UDP連接組成。TCP需要確認(rèn)是否連接成功或者接收數(shù)據(jù)包是否接收成功，因此TCP連接會響應(yīng)網(wǎng)絡(luò)擁塞狀況；而UDP連接并沒有上述確認(rèn)過程，因而UDP沒有邏輯連接狀態(tài)，從而基本不會影響網(wǎng)絡(luò)內(nèi)部狀態(tài)。在網(wǎng)絡(luò)內(nèi)部，背景流量由6個TCP連接和1個UDP連接構(gòu)成。探測包使用40位的組播UDP數(shù)據(jù)包。

表1 鏈路參數(shù)配置表

每1/10 s，隨機從方案C={＜2，3＞，＜5，6＞，＜3，5＞，＜2，6＞}中選擇一組做探測包發(fā)送實驗，如選中＜2，3＞，則從源節(jié)點0向葉子節(jié)點2和3發(fā)送組播探測包，節(jié)點2和3接收探測包并記錄下時延情況。每一組的探測過程持續(xù)30 s，先后做10組測試實驗，總共發(fā)送約3 000個探測包。同樣的實驗方法對其余3個測量節(jié)點對＜5，6＞，＜3，5＞，＜2，6＞進(jìn)行探測包發(fā)送實驗。用bin將測量所得數(shù)據(jù)離散化，其中假設(shè)q=0.25，p=0.2。圖6展示了估計的結(jié)果以及與真實情況的對比。

由圖6可以看出，在離散數(shù)據(jù)模式下，對于鏈路1、鏈路4、鏈路5三條鏈路，MPLE算法和移植算法兩種方法所得估計值均圍繞真實結(jié)果上下浮動，基本符合真實網(wǎng)絡(luò)狀況。兩者相比，MPLE算法更加精準(zhǔn)一些，但是精準(zhǔn)度沒有明細(xì)的差距。進(jìn)一步分析圖形分布可以看出，移植算法估計值與真實結(jié)果相比，普遍偏差最大的位置發(fā)生在時延為0值（即αk(0)）時，其估計值略小于真實值，而且隨著探測包在路徑中的傳送過程之中，偏差會進(jìn)行向下傳遞，使得偏差逐步增大。但是隨著時延值的增長偏差則越來越小，估計值趨于與真實結(jié)果重合。在不斷的實驗中摸索修正偏差的方法，調(diào)整bin值的大小，并根據(jù)不同的bin進(jìn)行相應(yīng)的矯正計算。

4 結(jié)束語

網(wǎng)絡(luò)鏈路時延分布估計始終基于時間和空間的獨立性這一假設(shè)。在此廣義的框架下，利用固定大小的bin將鏈路時延離散化。并不采取MPLE算法中將拓?fù)渚仃噭澐值姆椒?，轉(zhuǎn)而運用靈活發(fā)包策略將樹狀網(wǎng)絡(luò)拓?fù)溥M(jìn)行子樹劃分，該方法將大規(guī)模的逆概率估計問題分解成眾多子問題，簡化最大似然估計量。然后，針對不同的子樹劃分進(jìn)行深度估計的研究，剝離路徑時延以獲取路徑中每條鏈路的時延分布。與MPLE算法相比，減小了計算復(fù)雜度，計算速度也相應(yīng)縮減，其預(yù)測結(jié)果從圖6中可以看出依然保持較高的精準(zhǔn)度，一定程度上解決了原有EM算法無法適應(yīng)大規(guī)模網(wǎng)絡(luò)的問題。不僅能夠?qū)W(wǎng)絡(luò)斷層掃描的拓?fù)渫茢嗉夹g(shù)[13]做出更好的指導(dǎo)作用，而且還可用于實際服務(wù)質(zhì)量的監(jiān)測以及問題鏈路的定位[14]。其不足在于估計過程中bin大小的選擇，在內(nèi)部鏈路統(tǒng)計未知的情況下，準(zhǔn)確選擇bin的尺寸是比較困難的，需在反復(fù)的實驗中不斷調(diào)整bin值的大小，以達(dá)到誤差值與計算量的平衡點。

[1]錢峰.網(wǎng)絡(luò)層析成像研究綜述[J].計算機科學(xué)，2006，33（9）：12-17.

[2]Sun Yi，Li Dong，Sun Hongjie.Network tomography and improved methods for delay distribution inference[C]// ICACT，2007：1433-1437.

[3]趙洪華，陳嗚.基于網(wǎng)絡(luò)層析成像技術(shù)的拓?fù)渫茢郲J].軟件學(xué)報，2010，21（1）：133-146.

[4]Xia Ye，Tse D.Inference of link delay in communication network[J].IEEE Journal on Selected Areas in Communications，2006，24（12）：2235-2248.

[5]Presti F L，Duffield N G，Horowitz J，et al.Multicast-based inference of network-internal delay distributions[R].Univ Massachusetts，Amherst，MA，1999.

[6]Liang G，Yu B.Maximum pseudo likelihood estimation in network tomography[J].IEEE Trans on Signal Process，2003，51：2043-2053.

[7]李貴山，蔡皖東.網(wǎng)絡(luò)鏈路時延分布估計方法研究[J].計算機工程與應(yīng)用，2009，45（8）：20-22.

[8]Brian E，Gautam D，Paul B，et al.Toward the practical use of network tomography for Internet topology discovery[C]// 2010 Proceedings IEEE INFOCOM，2010：1-9.

[9]張宏莉，方賓興，胡銘曾.Internet測量與分析綜述[J].軟件學(xué)報，2003，14（1）：110-116.

[10]孫紅杰.基于主動測量的網(wǎng)絡(luò)性能分析[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2008.

[11]杜艷明，韓冰，肖建華.基于貝葉斯模型的IP網(wǎng)擁塞鏈路診斷算法[J].計算機應(yīng)用，2012，32（2）：347-351.

[12]Yolanda T，Mark C，Robert D N.Network delay tomography[J].IEEE Transactions on Signal Processing，2003，51（8）：2125-2136.

[13]Jin Xing，Tu Wangqing，Gary C S H.Scalable and efficient end-to-end network topology inference[J].IEEE Transactions on Parallel and Distributed System，2008，19（6）：837-850.

[14]趙佐，蔡皖東.基于簡單網(wǎng)絡(luò)斷層掃描的失效鏈路定位研究[J].計算機科學(xué)，2010，37（1）：108-110.

[15]Coates M，Nowak R.Network tomography for internal delay estimation[C]//IEEE Int Conf Acoust，Speech，and Signal Proc，2002.

WU Chenwen,LI Peiru,RU Junnian,LIU Xiangli

Institute of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China

The link performance inference is crucial to network quality assessment,however usually the present assessment methods can only infer the simple network with definite layer and can’t be applied to the large scale network.This paper proposes a maximum likelihood estimation based on incomplete data to estimate the delay distribution of the inside network. This method divides the tree-like network topology into different two-layer binary subtrees and estimates every chain’s delay of every subtree.And then the link delays are divided into every link through the transplantation algorithm and every subtree is done in this way with this method one by one,thus the link delays of the whole network are obtained.The feasibility and accuracy of the algorithm are verified through NS2 simulation.

network tomography;delay distribution;Expectation Maximization（EM）algorithm;grafting estimation;delay estimation

對于網(wǎng)絡(luò)質(zhì)量評估鏈路性能推測無疑是至關(guān)重要的，然而現(xiàn)有的估計方法通常只能推測層次數(shù)有限的簡單網(wǎng)絡(luò)，無法應(yīng)用于大規(guī)模網(wǎng)絡(luò)。提出了一種基于不完整數(shù)據(jù)極大似然估計算法，估計網(wǎng)絡(luò)內(nèi)部鏈路時延分布，該方法通過不同的發(fā)包策略將樹狀網(wǎng)絡(luò)拓?fù)鋭澐殖刹煌膬蓪尤溩訕洌槍γ總€子樹估計每條“鏈”的時延，隨后通過移植算法將路徑時延劃分到各鏈路中，逐一對每個子樹使用該方法計算從而得到整個網(wǎng)絡(luò)鏈路時延情況。利用NS2仿真實驗驗證了該算法的可行性和準(zhǔn)確性。

網(wǎng)絡(luò)斷層掃描；時延分布；最大期望（EM）算法；移植算法；時延估計

A

TP393

10.3778/j.issn.1002-8331.1301-0171

WU Chenwen,LI Peiru,RU Junnian,et al.Discrete delay distribution inference based on end-to-end measurement. Computer Engineering and Applications,2014,50（24）：76-80.

甘肅省自然科學(xué)基金（No.1308RJZA111）；蘭州市科技計劃基金資助項目（No.2009-1-5）。

吳辰文（1964—），男，教授，主研方向為網(wǎng)絡(luò)斷層掃描技術(shù)；李培儒（1984—），男，碩士研究生；茹俊年（1986—），男，碩士研究生；劉香麗（1986—），女，碩士研究生。

2013-01-16

2013-05-06

1002-8331（2014）24-0076-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-08-07，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130807.1540.003.html