R-Vivaldi：距離范圍感知的IP網(wǎng)絡坐標系統(tǒng)

王大彬，黃瓊，陽小龍，隆克平

(1. 重慶郵電大學 移動通信技術重點實驗室，重慶 400065；2. 電子科技大學 光互聯(lián)網(wǎng)及移動信息網(wǎng)絡研究中心，四川 成都 611731；3. 北京科技大學 計算機與通信工程學院，北京 100083）

1 引言

在實際的網(wǎng)絡中，時延（即網(wǎng)絡距離）是一個非常重要的參數(shù)，已把它看作為網(wǎng)絡路徑的一個基本屬性，與網(wǎng)絡拓撲和路由密切相關。如果獲得了節(jié)點之間的時延信息，則對提高網(wǎng)絡應用（如媒體文件共享、內(nèi)容訪問網(wǎng)絡等）的性能有很大的幫助。Ping方式是獲取該信息的最直接方法，它簡單直觀，但是效率低、開銷大、可擴展性差，其時間復雜度為O(N2)。為此，提出了虛擬坐標系統(tǒng)的概念，它的基本思想是將網(wǎng)絡距離空間映射到一個幾何空間中，每個網(wǎng)絡節(jié)點對應幾何空間中一個坐標點，節(jié)點間距離可以根據(jù)它們的坐標值通過空間距離公式計算得出。因此，虛擬坐標系統(tǒng)能大幅度降低測量開銷。

目前，文獻提出了很多不同的虛擬坐標算法，可以大致劃分為基于錨節(jié)點(landmark-based)[1～3]和基于物理模擬(simulation-based)[4,5]2類?；阱^節(jié)點的坐標系統(tǒng)需要事先配置一定數(shù)目的錨節(jié)點，其余節(jié)點的坐標通過最小化這些節(jié)點到錨節(jié)點的實際距離與預測距離的相對誤差之和計算得出；基于物理模擬的坐標系統(tǒng)則是將網(wǎng)絡模擬為一種物理模型，例如 Vivaldi算法，它將距離預測誤差之和最小化問題模擬為彈簧系統(tǒng)勢能最小化問題。盡管這些算法的時延預測相對誤差都不大，但是即使很小的預測誤差，也會對網(wǎng)絡應用的性能產(chǎn)生非常明顯的影響[6]。因此，如何提高它們的時延預測準確度，成為該領域的一個研究熱點。

對該問題目前最常見的解決方案是增加坐標空間維度或增加錨節(jié)點數(shù)。該方案對維度或者錨節(jié)點數(shù)較少的坐標系統(tǒng)，即使維數(shù)或錨節(jié)點數(shù)有少許增加，其預測準確性就會有明顯的改善。但是當坐標維數(shù)為7以后，其預測準確性改善就不再明顯，而同時測量開銷和坐標計算開銷反而會增大。例如：文獻[1]對GNP(global network positioning)方案的預測誤差進行了仿真分析，其結果為：坐標系統(tǒng)從2維增加到3維，其時延預測的相對誤差最大改善可達5%；而從7維到8維、10維等，則幾乎沒有任何改善。鑒于此，一些研究者則從錨節(jié)點的選擇入手，根據(jù)被選擇的錨節(jié)點構造出相應的網(wǎng)絡坐標系統(tǒng)。例如文獻[7～9]提出的分層選擇錨節(jié)點和文獻[10]提出的混合選擇錨節(jié)點的方案。其中混合選擇錨節(jié)點方案是選擇一部分鄰近節(jié)點并在剩余的節(jié)點中，隨機選擇一部分節(jié)點共同作為錨節(jié)點來計算節(jié)點的坐標。此方案能提高短距離的預測準確性，但是同時會降低長距離的預測準確性，并且對整個坐標系統(tǒng)準確性的改善也不明顯；分層選擇錨節(jié)點方案如下。1）按照一定的規(guī)則將節(jié)點劃分到不同的層中，然后節(jié)點選擇自己所在層內(nèi)的節(jié)點作為錨節(jié)點計算自己在該層的坐標。2）在每次預測節(jié)點間的距離時，選擇相對“正確”的層坐標來預測節(jié)點間的距離。此分層選取錨節(jié)點方案的優(yōu)勢在于：不僅能提高短距離的預測準確度，而且對長距離的預測準確度也不會產(chǎn)生影響。同時還可以從文獻[7]的仿真結果中得出。分層選擇錨節(jié)點的方案比混合選擇錨節(jié)點的方案具有更高的預測準確性。但是，文獻[7,8]所提出的方案需要一些固定的錨節(jié)點來形成簇結構，所以坐標系統(tǒng)的準確性受到所選擇固定錨節(jié)點影響；而文獻[9]提出的分層方案，在網(wǎng)絡拓撲改變時，健壯性很差。

由上述可知分層選擇錨節(jié)點機制在提高距離預測的準確度上，優(yōu)于其他機制，而且經(jīng)過研究發(fā)現(xiàn)，該機制在一定程度上克服了預測準確度不一致性問題，此問題是指對于長距離和短距離節(jié)點坐標預測準確度不能到達一致，從而不能達到全局最優(yōu)的問題。但該機制也存在很大的局限性，為了使距離預測準確性不受固定錨節(jié)點和網(wǎng)絡拓撲改變的影響，且進一步提高距離預測的準確性，本文對分層選擇錨節(jié)點機制進行了擴展，提出了一種距離范圍感知的IP網(wǎng)絡坐標系統(tǒng)。它是根據(jù)虛擬坐標系統(tǒng)中的一種現(xiàn)象而提出的，即對被預測的節(jié)點間時延，若選擇在該時延范圍附近的節(jié)點作為錨節(jié)點，則能提高該時延預測準確度。仿真結果表明，與Vivaldi算法相比，此方法有效地提高了距離預測的準確性，而且在一定程度上克服預測準確度不一致性問題。

2 R-Vivaldi：距離范圍感知的IP網(wǎng)絡坐標系統(tǒng)

2.1 問題描述

從文獻[7～10]可知，選擇不同距離范圍內(nèi)的節(jié)點作為錨節(jié)點，對坐標系統(tǒng)的準確性影響很大。本文選取了Planetlab的一組真實數(shù)據(jù)[11]，以當前最典型的網(wǎng)絡坐標 Vivaldi算法為例，對該結論進行驗證分析。該組數(shù)據(jù)包括了226個主機節(jié)點，將其中在RTT(round-trip time)小于100ms范圍內(nèi)找不到一定數(shù)目鄰居節(jié)點的節(jié)點剔除。在選擇鄰居節(jié)點時，鄰居節(jié)點數(shù)不宜過多或過少，前者會導致更多的節(jié)點在指定的距離范圍內(nèi)找不到規(guī)定的節(jié)點數(shù)目，從而使結論失去一般性；后者會使得計算出的坐標不夠準確，導致結論不夠準確。本文仿真中折衷選擇16個鄰居節(jié)點。

根據(jù)選擇不同距離范圍內(nèi)的節(jié)點作為鄰居節(jié)點，仿真的結果如圖1所示。

圖1 不同距離范圍內(nèi)的鄰居節(jié)點對預測準確性的影響

圖1(a)描述的是節(jié)點間鏈路時延分布情況，可以看出節(jié)點間的時延基本上是小于500ms的。從圖1(b)描述的相對誤差分布情況來看，對于隨機選擇鄰居節(jié)點的 Vivaldi而言，若選擇的鄰居節(jié)點RTT＜100ms時，提高了時延小于100ms的鏈路預測的準確性，但是在此值之后隨著鏈路時延的增大，相對誤差急劇上升，即劣化了對長距離預測的準確性。而當選擇的鄰居節(jié)點 RTT＞100ms時，劣化了時延小于290ms的鏈路預測的準確性，但是在此值之后隨著鏈路時延的增大，提高了長距離的預測準確度。當選擇的鄰居節(jié)點100ms ＜RTT＜300ms時，提高了距離在 100ms～270ms之間的鏈路預測的準確性。所以得出：對被預測的節(jié)點間時延，選擇在該時延范圍附近的節(jié)點作為錨節(jié)點有利于提高該時延的預測準確性。

但是，怎么知道被預測時延的大致范圍，以便能取得在該時延范圍附近的節(jié)點作為錨節(jié)點呢？另外一個問題是如何使錨節(jié)點的可選擇空間隨被預測時延的取值范圍動態(tài)調(diào)整呢？針對這 2個問題，本文提出了R-Vivaldi系統(tǒng)。

2.2 算法思想

由上可知，選擇不同距離范圍的節(jié)點作為錨節(jié)點，對坐標系統(tǒng)的準確性影響很大。若在較小距離范圍內(nèi)選擇錨節(jié)點，則可提高相互鄰近的節(jié)點間時延的預測準確度；若在較大距離范圍內(nèi)選擇錨節(jié)點，則可提高相距較遠的節(jié)點間時延的預測準確度?？傊灰苓x取在被預測時延范圍附近的節(jié)點作為錨節(jié)點，就能有效地提高被預測時延的準確性。由此現(xiàn)象可知：提高節(jié)點間時延的預測準確度的關鍵在于，如何知道被預測時延的大致范圍，以便能取得在該時延范圍附近的節(jié)點作為錨節(jié)點和如何使錨節(jié)點的可選擇空間隨被預測時延的取值范圍動態(tài)調(diào)整。為此，本文提出了一種距離范圍感知的IP網(wǎng)絡坐標系統(tǒng)。其主要思路為：根據(jù)被預測的節(jié)點間時延的大致取值范圍，在與該取值范圍相近的一個距離半徑的空間內(nèi)，重新選擇錨節(jié)點而得到它的一個新取值范圍。依照該過程，被預測時延的取值范圍更加明晰，并不斷地動態(tài)調(diào)整錨節(jié)點的選擇，直至節(jié)點間時延的預測誤差滿足一定要求。

2.3 R-Vivaldi的實現(xiàn)

該系統(tǒng)的實現(xiàn)過程如圖2所示，且以預測節(jié)點A與B的距離為例。首先，節(jié)點被嵌入到某個幾何空間中并擁有了一個幾何坐標，記該坐標為全局坐標，此時的狀態(tài)如圖2(a)所示；接下來，如圖2(b)所示，根據(jù)2個節(jié)點的全局坐標計算2個節(jié)點間的距離 DAB，然后在以節(jié)點 A（或 B）為中心的一個環(huán)形區(qū)域內(nèi)選取其中節(jié)點作為錨節(jié)點（標記為1的節(jié)點），計算A（或B）的第1層坐標。該環(huán)形區(qū)域是以節(jié)點 A(或 B)為中心，半徑為(1+α)×DAB（其中α是調(diào)節(jié)參數(shù)）的圓形區(qū)域減去以節(jié)點 A(或 B)為中心，半徑為(1-α)×DAB的圓形區(qū)域所得。依此類推，如圖2(c)所示，根據(jù)兩節(jié)點第n-1層坐標更新節(jié)點間的距離 DAB，然后再以節(jié)點 A（或 B）為中心的一個環(huán)形區(qū)域內(nèi)選取其中節(jié)點作為錨節(jié)點（標記為n的節(jié)點），計算A（或B）的第n層坐標，該環(huán)形區(qū)域定義同上。依照該過程，使節(jié)點A與B的時延取值范圍更加明晰。該過程在預測距離穩(wěn)定即預測距離的準確度達到一定程度或者出現(xiàn)異常時停止，并利用最后一層的坐標預測兩節(jié)點間的距離。

圖2 R-Vivaldi的實現(xiàn)過程

R-Vivaldi偽代碼

/*初始化，其中NC與NA分別是迭代次數(shù)和錨節(jié)點數(shù)目,α和β是調(diào)節(jié)參數(shù)，CA和CB分別是節(jié)點A與B的坐標*/

TA=CA，TB=CB，NC=n，NA=m，α=α'，β=β'

//計算兩節(jié)點A與B之間的距離

DAB=|| CA-CB||

//在[(1－α)* DAB，(1＋α)* DAB]內(nèi)，選擇新錨節(jié)點

//如果在[(1－α)·DAB，(1＋α)·DAB]內(nèi)，選擇的錨節(jié)點的數(shù)目達不到NA，算法停止

其中，α和β是調(diào)節(jié)參數(shù)且它們的取值都有一定的要求。α取值決定了環(huán)行區(qū)域的寬度，所以α值過大，環(huán)行區(qū)域也就越大，導致算法收斂速度慢；而過小，環(huán)行區(qū)域越窄，易導致程序因為節(jié)點在該環(huán)行區(qū)域內(nèi)找不到足夠的滿足條件的錨節(jié)點而停止，使得結果不夠準確。β取值決定了坐標準確度應該滿足的條件，它的值太大易使結果不準確，而太小使得程序收斂速度慢。

3 算法仿真結果及分析

3.1 算法性能評價標準

評價一個虛擬坐標系統(tǒng)的準確性總是使用相對誤差，它反映了預測距離與測量時延之間的誤差，定義如下：

3.2 仿真結果及分析

此處，仿真數(shù)據(jù)來源于網(wǎng)絡中測量的真實數(shù)據(jù)——Planetlab數(shù)據(jù)，它包括了226個主機。仿真中，隨機選擇了其中80個節(jié)點，組成了80×80的時延矩陣，鄰居節(jié)點的數(shù)目設為16，坐標維度為5維，調(diào)節(jié)參數(shù)α的取值分別為0.1、0.3、0.5、0.7；調(diào)節(jié)參數(shù)β的取值，本處為了仿真的方便，設它的值為0；該算法迭代的次數(shù)NC，取值分別為1、2、3、4。仿真結果如圖3和圖4所示。

圖3 不同的NC對預測準確性的影響（α的值為0.5）

從圖 3(a)和圖 4(a)可以看出，本文提出的R-Vivaldi在預測距離準確性上大大優(yōu)于Vivaldi算法，而且，在圖3(a)中，還可以看出，隨著迭代次數(shù)的增加，預測準確度也在提高；但是當?shù)拇螖?shù)達到一定的數(shù)目后，再增加迭代次數(shù)，預測的準確性也不會再有多大的改善。圖4(a)描述了不同的α值對預測準確度的影響：α值越小，預測準確度越高。從圖3(a)中，可以看到在Vivaldi算法中，相對誤差為0.5和1.0時，相對誤差累積分布值分別為56%和74%，而R-Vivaldi相對應的值為82%和96%（在NC=4時）。在圖4(a)中，在相對誤差為0.5和1.0時，相對誤差累積分布的值為84%和92%(在α=0.1 時)。

圖3(b)和圖4(b)描述了相對誤差的分布情況，可從圖中看出被預測的鏈路時延小于 100ms時，R-Vivaldi大幅度地減少了相對誤差值，而且如圖3(b)所示，在鏈路時延大于5ms時，整個坐標系統(tǒng)的相對誤差都是小于1的。

圖4 不同的α值對預測準確性的影響（NC的值為1）

4 結束語

在本文中，為了提高網(wǎng)絡距離預測的準確性和克服現(xiàn)有的一些分層選擇錨節(jié)點機制的不足，提出了一種距離范圍感知的IP網(wǎng)絡坐標系統(tǒng)。對被預測的節(jié)點間時延，選擇在該時延范圍附近的節(jié)點作為錨節(jié)點，能有效地提高該時延預測的準確性。仿真結果顯示，本方案能有效提高距離預測準確性，而且在一定程度上克服預測準確度不一致性問題。但是，該系統(tǒng)對長距離的預測相對誤差并沒有改善，而且短距離的預測相對誤差還是相對較高，如圖3(b)所示，在鏈路時延小于5ms時，相對誤差還是比較高。所以，在以后的工作中，繼續(xù)完善本系統(tǒng)，使它進一步提高距離預測的準確性。

[1] NG T, ZHANG H. Predicting Internet network distances with coordinate-based approaches[A]. Proc of IEEE INFOCOM’02[C]. New York,2002.170-179.

[2] LEE S, SAHU S. A cluster based approach for network distance embedding[A]. Proc of the 9th International Conference on Communications and Information Technologies[C]. Icheon, 2009.1040-1045.

[3] ZHANG Y, ZHANG H. A steady network coordinate system for network distance estimating[A]. Proc of the 2009 15th International Conference on Parallel and Distributed Systems[C]. Shenzhen, China,2009. 860-863

[4] DABEK F, COX R, KAASHOEK F, et al. Vivaldi: a decentralized network coordinate system[A]. Proc of ACM SIGCOMM’04[C].Portland, OR, 2004.15-26.

[5] SHAVITT Y, TANKEL T. Big-bang simulation for embedding network distances in euclidean space[J]. IEEE/ACM Transactions on Networking, 2004, 12 (6): 993-1006.

[6] ZHANG R, TANG C, HU Y. Impact of the inaccuracy of distance prediction algorithms on Internet applications—an analytical and comparative study[A]. Proc of the IEEE INFOCOM[C]. Barcelona,2006. 1-12.

[7] ZHANG R, HU Y, LIN X, et al. A hierarchical approach to Internet distance prediction[A]. Proc of ICDCS[C]. Lisboa, Portugal, 2006. 73.

[8] CHEN Y, XIONG Y, SHI X. Pharos: a decentralized and hierarchical network coordinate system for Internet distance prediction[A]. Proc IEEE GLOBECOM[C]. Washington, DC, 2007.26-30.

[9] YE Z, LIU Y, CHEN S. A new hierarchical network coordinate algorithm based on community structure[A]. International Conference on Computational Science and Engineering[C]. Vancouver, 2009. 418-423.

[10] COSTA M, CASTRO M, ROWSTRON A. PIC: practical Internet coordinates for distance estimation[A]. Proc of IEEE ICDCS[C].Washington, DC, 2004. 178-187.

[11] https://www.planet-lab.org/, 2006[EB/OL].