基于網(wǎng)絡(luò)拓?fù)涞膭討B(tài)時延估算模型的研究

豆培培，何涇沙

（北京工業(yè)大學(xué) 北京 100124）

網(wǎng)絡(luò)時延測量技術(shù)是了解和研究互聯(lián)網(wǎng)的重要手段。由于在大規(guī)模網(wǎng)絡(luò)中完全實現(xiàn)端到端時延測量非常困難，在測量系統(tǒng)中引入估算可以大大降低主動測量對網(wǎng)絡(luò)造成的額外負(fù)荷，網(wǎng)絡(luò)時延估算已經(jīng)成為是網(wǎng)絡(luò)時延測量技術(shù)中重要內(nèi)容[1]。如何準(zhǔn)確地進(jìn)行網(wǎng)絡(luò)時延估測已經(jīng)成為網(wǎng)絡(luò)測量領(lǐng)域的研究熱點，具有重要的研究價值和現(xiàn)實意義。

目前針對時延估算的研究主要包括基于網(wǎng)絡(luò)結(jié)構(gòu)和基于網(wǎng)絡(luò)坐標(biāo)的時延估算技術(shù)的研究。IDMaps算法[2]是2001年Francis等人最早提出一種基于網(wǎng)絡(luò)結(jié)構(gòu)的大規(guī)模網(wǎng)絡(luò)時延估算機制。它以IP地址前綴作為劃分AP的標(biāo)準(zhǔn)，采用分布于網(wǎng)絡(luò)中的若干Tracer估算出Internet中任意兩個IP之間的網(wǎng)絡(luò)距離。2004年Dabek等人首次提出基于網(wǎng)絡(luò)坐標(biāo)的分布式的Vivaldi系統(tǒng)[3]，它通過某種嵌入方式將網(wǎng)絡(luò)空間嵌入到一個度量空間中，這樣網(wǎng)絡(luò)中節(jié)點都對應(yīng)于度量空間中的某個坐標(biāo)點，然后利用節(jié)點坐標(biāo)計算節(jié)點間的空間距離，以此作為節(jié)點間的估算時延。但是網(wǎng)絡(luò)坐標(biāo)系統(tǒng)存在節(jié)點抖動、坐標(biāo)漂移、鏈路抖動、三角不等式違例等內(nèi)在錯誤。由于網(wǎng)絡(luò)結(jié)構(gòu)充分考慮了網(wǎng)絡(luò)的路由拓?fù)浜吐窂竭x擇等網(wǎng)絡(luò)內(nèi)部特性，具有較高的估測精度。然而隨著網(wǎng)絡(luò)規(guī)模的不斷增大，基于網(wǎng)絡(luò)拓?fù)涞臅r延估算系統(tǒng)還有很多需要進(jìn)一步研究的問題，如提高時延估算精度，優(yōu)化系統(tǒng)的測量節(jié)點部署和提高系統(tǒng)容錯性等[4]。文中主要針對基于網(wǎng)絡(luò)拓?fù)涞臅r延估算進(jìn)行了研究。

文中在NS2網(wǎng)絡(luò)仿真環(huán)境中對典型的拓?fù)浣Y(jié)構(gòu)進(jìn)行時延測量和分析，得到網(wǎng)絡(luò)時延與網(wǎng)絡(luò)拓?fù)渲g的關(guān)系，建立了網(wǎng)絡(luò)時延估算的數(shù)學(xué)模型。提出了三層時延估測系統(tǒng)架構(gòu)，可以根據(jù)測量節(jié)點的測量時延來估算其他端節(jié)點到同一目的節(jié)點之間的網(wǎng)絡(luò)時延的算法。最后還給出了完整的動態(tài)時延估算算法，可以靈活地根據(jù)精度要求直接返回滿足要求的時延或者啟動自身的測量功能進(jìn)行測量。

1 仿真設(shè)計

本文網(wǎng)絡(luò)仿真在NS2.35環(huán)境中進(jìn)行，NS2是面向?qū)ο蟮木W(wǎng)絡(luò)模擬工具，具有完備的網(wǎng)絡(luò)協(xié)議，可以仿真整個網(wǎng)絡(luò)環(huán)境，并被廣泛使用的強大的開源仿真工具。文獻(xiàn)[5]研究表明：互聯(lián)網(wǎng)平均網(wǎng)絡(luò)路徑長度為15至19跳，國內(nèi)的平均網(wǎng)絡(luò)長度為14至15跳之間。我們在仿真實驗中設(shè)置最大路徑長度為15跳。本節(jié)主要考慮路徑長度與RTT的關(guān)系，仿真的網(wǎng)絡(luò)拓?fù)涫纠鐖D1所示，S0、S1、S2、D0和D是普通節(jié)點，中間R1、R2、R3、R4 和 R5是路由器節(jié)點。 源節(jié)點 S1、S2到目的節(jié)點D有兩條ICMP數(shù)據(jù)流。仿真得到節(jié)點S1到D，節(jié)點S2到D 的兩個時延序列分別記為 RTT（S1，D）和 RTT（S2，D）。 其中在S0和D0之間加入基于UDP傳輸協(xié)議的EXPOO背景流量，使仿真更具有動態(tài)性。EXPOO是NS2提供的背景流量產(chǎn)生器，它可以根據(jù)指數(shù)分布（On/Off）產(chǎn)生通信量，在On階段分組以固定速率發(fā)送，Off階段不發(fā)送分組，On/Off的分布符合指數(shù)分布，分組尺寸固定。兩個數(shù)據(jù)流的RTT序列如圖2所示，可以看出兩個時延序列的變化趨勢比較一致。

圖1 仿真網(wǎng)絡(luò)拓?fù)鋱DFig.1 Topology diagram of the simulation system

圖2 兩個RTT序列Fig.2 Two RTT sequenceswith the same destination

2 端到端時延估算的模型

定義1 RTT相似度：網(wǎng)絡(luò)中兩個源節(jié)點到同一個目的節(jié)點在同一時間段內(nèi)的兩個RTT序列的Pearson相關(guān)系數(shù)作為S1、S2和D的RTT相似度。

定義2路徑長度：定義為源節(jié)點到目的節(jié)點的跳數(shù)，即節(jié)點 S1 和 S2 到節(jié)點 D 的跳數(shù)，分別記作 L（S1，D）和 L（S2，D）。

以圖1為例，R2是S1和S2到D的通過的第一個公共路由器，稱 L（S1，R2）、L（S1，R2）是拓?fù)鋱鼍暗乃接新窂剑QL（R2，D）是拓?fù)鋱鼍暗墓新窂健?/p>

為了考察一種拓?fù)鋱鼍爸?個RTT序列之間的定量關(guān)系，本文利用線性回歸方法給出了具體的估算方法并對估算的精度進(jìn)行了定義。

設(shè)測量所得到的兩個 RTT 序列為 X=（x1，x2，…，xn）和 Y=（y1，y2，…，yn），其中 xi與 yi在時刻上一一對應(yīng)，則一元線性回歸模型可以表示為，

k為回歸方程的斜率，b為回歸方程的截距。它們的計算公式分別為

在網(wǎng)絡(luò)中端節(jié)點之間的路徑長度不大于15的假設(shè)下，本文主要通過改變仿真拓?fù)涞穆窂介L度，形成私有路徑L（S1，R2）、私有路徑 L（S2，R2）和公有路徑 L（R2，D）的長度組總共包含種。對于不同的路徑組合，都可以根據(jù)上述線性回歸的方式確定出斜率k和截距b，然后就能夠利用回歸方程對同一路徑組合下的時延情況進(jìn)行估算。

針對1 015種路徑組合的拓?fù)鋱鼍白鲱愃品抡妫ㄟ^分析得到斜率和截距，這些仿真結(jié)果存儲在服務(wù)層節(jié)點中。為了檢驗用 RTT（S1，D）估算 RTT（S2，D）的精度，引入均方根誤差來衡量估算的誤差，p=1-RMSE作為估算精度。表1列出了對部分拓?fù)鋱鼍斑M(jìn)行仿真而得到兩個RTT序列的相關(guān)分析結(jié)果。

表1 一些拓?fù)鋱鼍暗腞TT相似度和估算精度結(jié)果Tab.1 Test results of sim ulation for som e topology scenarios

從上面仿真數(shù)據(jù)發(fā)現(xiàn)，在私有路徑 L（S1，R2）和 L（S2，R2）固定時，公有路徑 L（R2，D）越大，估算精度越大，即得到的時延估算值具有較高的估算精度。在其他拓?fù)鋱鼍爸须S公有路徑增大，估算精度也具有增大的趨勢。此現(xiàn)象也驗證了Zhu等人[6]關(guān)于RTT相似度與路徑長度的關(guān)系的相關(guān)結(jié)論。

3 時延估測總體架構(gòu)

為了滿足基于網(wǎng)絡(luò)拓?fù)溥M(jìn)行時延估算的需要，本文提出的時延估測系統(tǒng)架構(gòu)，架構(gòu)分為三層：服務(wù)層、測量層和應(yīng)用層。時延估算系統(tǒng)的框圖如3所示。

圖3 時延估測系統(tǒng)框圖Fig.3 Structure diagram of the delay estimation system

服務(wù)層可由一個或多個具有較強計算能力和存儲能力的服務(wù)器組成，單個服務(wù)器可以看作是集中控制的系統(tǒng)，多個服務(wù)器可以組成一個分布式集群，它們之間進(jìn)行協(xié)調(diào)工作。每個節(jié)點由仿真結(jié)果存儲模塊和時延估算模塊構(gòu)成。服務(wù)層節(jié)點可以定期通過現(xiàn)有的網(wǎng)絡(luò)拓?fù)浞?wù)得到網(wǎng)絡(luò)拓?fù)洌⒋鎯Σ煌負(fù)鋱鼍皩?yīng)的估算公式和估算精度。由時延估算模塊提供端到端時延的估算服務(wù)。

測量層由一個或多個具有測量功能的主機組成，負(fù)責(zé)測量到其他檢測點和應(yīng)用層節(jié)點的RTT時延，并將結(jié)果發(fā)送給服務(wù)層節(jié)點。

應(yīng)用層由普通的端節(jié)點組成，根據(jù)需要向服務(wù)層請求到某個端節(jié)點的RTT時延，并且應(yīng)用層節(jié)點也可以根據(jù)需要啟動測量功能。

4 動態(tài)時延估算算法

基于拓?fù)渎窂介L度與RTT相似度和估算精度之間的關(guān)系，并結(jié)合上文提出的時延估測架構(gòu)，本文提出了一種動態(tài)的時延估算算法。假設(shè)測量層節(jié)點部署固定的情況下，應(yīng)用層節(jié)點S向服務(wù)層發(fā)出的端到端時延請求，要求得到RTT（S，D），并要求時延估算精度不小于E。則根據(jù)網(wǎng)絡(luò)拓?fù)渲泄新窂介L度與估算精度之間的關(guān)系，可以從網(wǎng)絡(luò)的測量節(jié)點集合中選擇所形成拓?fù)鋱鼍爸泄新窂阶畲蟮臏y量點M來估測RTT（S，D）。認(rèn)為M能比其他測量節(jié)點估算S到D的RTT更精確。該方法在已有測量節(jié)點不能滿足精度要求時，通過新增測量節(jié)點的方案，保證時延估測系統(tǒng)的靈活性和高效性。

服務(wù)層節(jié)點在接收到一個節(jié)點S到D的端到端時延請求后的主要處理步驟如下：

1）服務(wù)層節(jié)點在接收到節(jié)點S到D的時延請求后，首先判斷節(jié)點S是否為測量節(jié)點。如果是轉(zhuǎn)到步驟2），否則轉(zhuǎn)到步驟 5）；

2）直接查找S到D的測量時延；如果服務(wù)器中存在S到D的歷史時延測量結(jié)果，轉(zhuǎn)到步驟3），否則轉(zhuǎn)到步驟4）；

3）直接返回歷史時延測量值，且返回精度是1）；

4）服務(wù)層節(jié)點向測量節(jié)點S發(fā)送消息進(jìn)行RTT（S，D）立即測量，直接返回最新的測量值并加入服務(wù)層節(jié)點的時延歷史記錄中，返回時延測量值，且返回精度是1）；

5）從網(wǎng)絡(luò)系統(tǒng)中的測量集合中選擇滿足估算精度最大的測量節(jié)點進(jìn)行估算，動態(tài)選擇測量節(jié)點的標(biāo)準(zhǔn)是該測量節(jié)點與待測源節(jié)點和目的節(jié)點組成拓?fù)鋱鼍暗墓浪憔茸罡?，即選擇與待測源節(jié)點S、目的節(jié)點D組成拓?fù)鋱鼍暗墓猜窂介L度最大的測量節(jié)點來估算RTT（S，D），此時估算值可以利用對應(yīng)拓?fù)鋱鼍暗姆抡嫦碌男甭屎徒鼐嘤嬎愕玫?，并得到對?yīng)的時延估算精度 e。 如果 e＞E，返回 RTT（S，D）和估算精度e；否則，表明網(wǎng)絡(luò)中部署的所有測量節(jié)點，都不能滿足該RTT請求的估算精度要求E，轉(zhuǎn)到步驟6）；

6）此時需要更多的測量節(jié)點的加入。源節(jié)點S啟動自身的測量功能，加入測量節(jié)點集合，進(jìn)行直接測量，返回RTT（S，D）測量值和估算精度1，并將測量結(jié)果發(fā)送給服務(wù)層節(jié)點存儲。

為了更好地說明整個算法的流程，圖4給出了算法的流程圖。

圖4 時延估算算法流程圖Fig.4 Flow chartof the delay estimation algorithm

5 結(jié)束語

本文在NS2網(wǎng)絡(luò)仿真中分析了網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)與網(wǎng)絡(luò)時延之間的關(guān)系，對典型的拓?fù)浣Y(jié)構(gòu)進(jìn)行時延測量和分析，得到網(wǎng)絡(luò)時延RTT相似度與公有路徑長度之間的定量關(guān)系。在此基礎(chǔ)上，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)利用線性回歸的方法提出了時延估算的新方法。另外考慮到不同的估算精度要求，給出了動態(tài)的時延估算模型，一方面可以動態(tài)地選擇最優(yōu)的測量節(jié)點，另一方面還可以在測量節(jié)點都不能滿足精度要求的情況下啟動自身的測量功能。

[1]邢長友，陳鳴.網(wǎng)絡(luò)距離預(yù)測技術(shù)[J].軟件學(xué)報，2009，20（9）:2470-2482.XINGChang-you，CHENMing.Techniquesofnetwork distance prediction[J].Journal of Software，2009，20（9）:2470-2482.

[2]Paul F，Sugih J，Cheng J，et al.IDMaps:A global Internet host distance estimation service[J].IEEE/ACM Transaction on Networking，2001，9（5）:525-540.

[3]Frank DaBek，Russ Cox，F(xiàn)rans Kaashoek，et al.Vivaldi:A decentralized network coordinate system[C]//Proceedings of the 2004 conference on Application， technologies，architectures， and protocols for computer communications，New York:ACM Press，2004:15-26.

[4]王意潔，李小勇.網(wǎng)絡(luò)距離預(yù)測技術(shù)研究[J].軟件學(xué)報，2009，20（6）:1574-1590.WANG Yi-jie，LI Xiao-yong.Network distance prediction technology research[J].Journal of Software，2009，20 （6）:1574-1590.

[5]馬建國，席明賢，林益民，等.中國Internet路由級跳數(shù)測量與分析[J].計算機應(yīng)用研究，2008，25（7）:2112-2114.MA Jian-guo，XI Ming-xian，LIN Yi-min，et al.Chinese Internet router-level hop countmeasurement and analysis[J].Application Research ofComputers，2008，25（7）:2112-2114.

[6]ZHU Na-fei，HE Jing-sha.Effects of path length on the similarity of network nodes based on RTT[J].Journal of Networks，2012，7（9）:1423-1430.