主動(dòng)端到端離散式時(shí)延分布估計(jì)方法研究

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

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

主動(dòng)端到端離散式時(shí)延分布估計(jì)方法研究

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

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

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

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

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

1 離散時(shí)延估計(jì)原理

1.1 模型定義

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

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

1.2 時(shí)延離散化

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

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

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

圖3 時(shí)延離散化

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

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

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

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

2 時(shí)延分布估計(jì)算法

2.1 組播發(fā)包策略

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

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

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

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

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

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

2.2 分離子樹(shù)

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

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

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

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

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

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

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

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

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

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

M步驟：

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

2.3 移植算法

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

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

圖5 移植算法

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

E步驟：

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

M步驟：

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

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

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

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

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

E步驟：

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[1]錢峰.網(wǎng)絡(luò)層析成像研究綜述[J].計(jì)算機(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é)報(bào)，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ò)鏈路時(shí)延分布估計(jì)方法研究[J].計(jì)算機(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測(cè)量與分析綜述[J].軟件學(xué)報(bào)，2003，14（1）：110-116.

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

[11]杜艷明，韓冰，肖建華.基于貝葉斯模型的IP網(wǎng)擁塞鏈路診斷算法[J].計(jì)算機(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]趙佐，蔡皖東.基于簡(jiǎn)單網(wǎng)絡(luò)斷層掃描的失效鏈路定位研究[J].計(jì)算機(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

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

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

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）；蘭州市科技計(jì)劃基金資助項(xiàng)目（No.2009-1-5）。

吳辰文（1964—），男，教授，主研方向?yàn)榫W(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