豆培培，何涇沙

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

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

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

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

1 仿真設(shè)計(jì)

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

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

圖2 兩個(gè)RTT序列Fig.2 Two RTT sequenceswith the same destination

2 端到端時(shí)延估算的模型

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

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

以圖1為例，R2是S1和S2到D的通過的第一個(gè)公共路由器，稱 L（S1，R2）、L（S1，R2）是拓?fù)鋱?chǎng)景的私有路徑，稱L（R2，D）是拓?fù)鋱?chǎng)景的公有路徑。

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

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

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

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

針對(duì)1 015種路徑組合的拓?fù)鋱?chǎng)景做類似仿真，通過分析得到斜率和截距，這些仿真結(jié)果存儲(chǔ)在服務(wù)層節(jié)點(diǎn)中。為了檢驗(yàn)用 RTT（S1，D）估算 RTT（S2，D）的精度，引入均方根誤差來衡量估算的誤差，p=1-RMSE作為估算精度。表1列出了對(duì)部分拓?fù)鋱?chǎng)景進(jìn)行仿真而得到兩個(gè)RTT序列的相關(guān)分析結(jié)果。

表1 一些拓?fù)鋱?chǎng)景的RTT相似度和估算精度結(jié)果Tab.1 Test results of sim ulation for som e topology scenarios

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

3 時(shí)延估測(cè)總體架構(gòu)

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

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

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

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

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

4 動(dòng)態(tài)時(shí)延估算算法

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

服務(wù)層節(jié)點(diǎn)在接收到一個(gè)節(jié)點(diǎn)S到D的端到端時(shí)延請(qǐng)求后的主要處理步驟如下：

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

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

3）直接返回歷史時(shí)延測(cè)量值，且返回精度是1）；

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

5）從網(wǎng)絡(luò)系統(tǒng)中的測(cè)量集合中選擇滿足估算精度最大的測(cè)量節(jié)點(diǎn)進(jìn)行估算，動(dòng)態(tài)選擇測(cè)量節(jié)點(diǎn)的標(biāo)準(zhǔn)是該測(cè)量節(jié)點(diǎn)與待測(cè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)組成拓?fù)鋱?chǎng)景的估算精度最高，即選擇與待測(cè)源節(jié)點(diǎn)S、目的節(jié)點(diǎn)D組成拓?fù)鋱?chǎng)景的公共路徑長度最大的測(cè)量節(jié)點(diǎn)來估算RTT（S，D），此時(shí)估算值可以利用對(duì)應(yīng)拓?fù)鋱?chǎng)景的仿真下的斜率和截距計(jì)算得到，并得到對(duì)應(yīng)的時(shí)延估算精度 e。 如果 e＞E，返回 RTT（S，D）和估算精度e；否則，表明網(wǎng)絡(luò)中部署的所有測(cè)量節(jié)點(diǎn)，都不能滿足該RTT請(qǐng)求的估算精度要求E，轉(zhuǎn)到步驟6）；

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

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

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

[1]邢長友，陳鳴.網(wǎng)絡(luò)距離預(yù)測(cè)技術(shù)[J].軟件學(xué)報(bào)，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ù)測(cè)技術(shù)研究[J].軟件學(xué)報(bào)，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í)跳數(shù)測(cè)量與分析[J].計(jì)算機(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.