基于網絡拓撲的動態時延估算模型的研究

豆培培，何涇沙

（北京工業大學 北京 100124）

網絡時延測量技術是了解和研究互聯網的重要手段。由于在大規模網絡中完全實現端到端時延測量非常困難，在測量系統中引入估算可以大大降低主動測量對網絡造成的額外負荷，網絡時延估算已經成為是網絡時延測量技術中重要內容[1]。如何準確地進行網絡時延估測已經成為網絡測量領域的研究熱點，具有重要的研究價值和現實意義。

目前針對時延估算的研究主要包括基于網絡結構和基于網絡坐標的時延估算技術的研究。IDMaps算法[2]是2001年Francis等人最早提出一種基于網絡結構的大規模網絡時延估算機制。它以IP地址前綴作為劃分AP的標準，采用分布于網絡中的若干Tracer估算出Internet中任意兩個IP之間的網絡距離。2004年Dabek等人首次提出基于網絡坐標的分布式的Vivaldi系統[3]，它通過某種嵌入方式將網絡空間嵌入到一個度量空間中，這樣網絡中節點都對應于度量空間中的某個坐標點，然后利用節點坐標計算節點間的空間距離，以此作為節點間的估算時延。但是網絡坐標系統存在節點抖動、坐標漂移、鏈路抖動、三角不等式違例等內在錯誤。由于網絡結構充分考慮了網絡的路由拓撲和路徑選擇等網絡內部特性，具有較高的估測精度。然而隨著網絡規模的不斷增大，基于網絡拓撲的時延估算系統還有很多需要進一步研究的問題，如提高時延估算精度，優化系統的測量節點部署和提高系統容錯性等[4]。文中主要針對基于網絡拓撲的時延估算進行了研究。

文中在NS2網絡仿真環境中對典型的拓撲結構進行時延測量和分析，得到網絡時延與網絡拓撲之間的關系，建立了網絡時延估算的數學模型。提出了三層時延估測系統架構，可以根據測量節點的測量時延來估算其他端節點到同一目的節點之間的網絡時延的算法。最后還給出了完整的動態時延估算算法，可以靈活地根據精度要求直接返回滿足要求的時延或者啟動自身的測量功能進行測量。

1 仿真設計

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

圖1 仿真網絡拓撲圖Fig.1 Topology diagram of the simulation system

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

2 端到端時延估算的模型

定義1 RTT相似度：網絡中兩個源節點到同一個目的節點在同一時間段內的兩個RTT序列的Pearson相關系數作為S1、S2和D的RTT相似度。

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

以圖1為例，R2是S1和S2到D的通過的第一個公共路由器，稱 L（S1，R2）、L（S1，R2）是拓撲場景的私有路徑，稱L（R2，D）是拓撲場景的公有路徑。

為了考察一種拓撲場景中2個RTT序列之間的定量關系，本文利用線性回歸方法給出了具體的估算方法并對估算的精度進行了定義。

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

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

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

針對1 015種路徑組合的拓撲場景做類似仿真，通過分析得到斜率和截距，這些仿真結果存儲在服務層節點中。為了檢驗用 RTT（S1，D）估算 RTT（S2，D）的精度，引入均方根誤差來衡量估算的誤差，p=1-RMSE作為估算精度。表1列出了對部分拓撲場景進行仿真而得到兩個RTT序列的相關分析結果。

表1 一些拓撲場景的RTT相似度和估算精度結果Tab.1 Test results of sim ulation for som e topology scenarios

從上面仿真數據發現，在私有路徑 L（S1，R2）和 L（S2，R2）固定時，公有路徑 L（R2，D）越大，估算精度越大，即得到的時延估算值具有較高的估算精度。在其他拓撲場景中隨公有路徑增大，估算精度也具有增大的趨勢。此現象也驗證了Zhu等人[6]關于RTT相似度與路徑長度的關系的相關結論。

3 時延估測總體架構

為了滿足基于網絡拓撲進行時延估算的需要，本文提出的時延估測系統架構，架構分為三層：服務層、測量層和應用層。時延估算系統的框圖如3所示。

圖3 時延估測系統框圖Fig.3 Structure diagram of the delay estimation system

服務層可由一個或多個具有較強計算能力和存儲能力的服務器組成，單個服務器可以看作是集中控制的系統，多個服務器可以組成一個分布式集群，它們之間進行協調工作。每個節點由仿真結果存儲模塊和時延估算模塊構成。服務層節點可以定期通過現有的網絡拓撲服務得到網絡拓撲，并存儲不同拓撲場景對應的估算公式和估算精度。由時延估算模塊提供端到端時延的估算服務。

測量層由一個或多個具有測量功能的主機組成，負責測量到其他檢測點和應用層節點的RTT時延，并將結果發送給服務層節點。

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

4 動態時延估算算法

基于拓撲路徑長度與RTT相似度和估算精度之間的關系，并結合上文提出的時延估測架構，本文提出了一種動態的時延估算算法。假設測量層節點部署固定的情況下，應用層節點S向服務層發出的端到端時延請求，要求得到RTT（S，D），并要求時延估算精度不小于E。則根據網絡拓撲中公有路徑長度與估算精度之間的關系，可以從網絡的測量節點集合中選擇所形成拓撲場景中公有路徑最大的測量點M來估測RTT（S，D）。認為M能比其他測量節點估算S到D的RTT更精確。該方法在已有測量節點不能滿足精度要求時，通過新增測量節點的方案，保證時延估測系統的靈活性和高效性。

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

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

2）直接查找S到D的測量時延；如果服務器中存在S到D的歷史時延測量結果，轉到步驟3），否則轉到步驟4）；

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

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

5）從網絡系統中的測量集合中選擇滿足估算精度最大的測量節點進行估算，動態選擇測量節點的標準是該測量節點與待測源節點和目的節點組成拓撲場景的估算精度最高，即選擇與待測源節點S、目的節點D組成拓撲場景的公共路徑長度最大的測量節點來估算RTT（S，D），此時估算值可以利用對應拓撲場景的仿真下的斜率和截距計算得到，并得到對應的時延估算精度 e。 如果 e＞E，返回 RTT（S，D）和估算精度e；否則，表明網絡中部署的所有測量節點，都不能滿足該RTT請求的估算精度要求E，轉到步驟6）；

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

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

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

5 結束語

本文在NS2網絡仿真中分析了網絡內部結構與網絡時延之間的關系，對典型的拓撲結構進行時延測量和分析，得到網絡時延RTT相似度與公有路徑長度之間的定量關系。在此基礎上，根據網絡拓撲結構利用線性回歸的方法提出了時延估算的新方法。另外考慮到不同的估算精度要求，給出了動態的時延估算模型，一方面可以動態地選擇最優的測量節點，另一方面還可以在測量節點都不能滿足精度要求的情況下啟動自身的測量功能。

[1]邢長友，陳鳴.網絡距離預測技術[J].軟件學報，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，Frans 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]王意潔，李小勇.網絡距離預測技術研究[J].軟件學報，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路由級跳數測量與分析[J].計算機應用研究，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.