R-Vivaldi：距離范圍感知的IP網絡坐標系統

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

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

1 引言

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

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

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

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

2 R-Vivaldi：距離范圍感知的IP網絡坐標系統

2.1 問題描述

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

根據選擇不同距離范圍內的節點作為鄰居節點，仿真的結果如圖1所示。

圖1 不同距離范圍內的鄰居節點對預測準確性的影響

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

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

2.2 算法思想

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

2.3 R-Vivaldi的實現

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

圖2 R-Vivaldi的實現過程

R-Vivaldi偽代碼

/*初始化，其中NC與NA分別是迭代次數和錨節點數目,α和β是調節參數，CA和CB分別是節點A與B的坐標*/

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

//計算兩節點A與B之間的距離

DAB=|| CA-CB||

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

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

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

3 算法仿真結果及分析

3.1 算法性能評價標準

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

3.2 仿真結果及分析

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

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

從圖 3(a)和圖 4(a)可以看出，本文提出的R-Vivaldi在預測距離準確性上大大優于Vivaldi算法，而且，在圖3(a)中，還可以看出，隨著迭代次數的增加，預測準確度也在提高；但是當迭代的次數達到一定的數目后，再增加迭代次數，預測的準確性也不會再有多大的改善。圖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時，整個坐標系統的相對誤差都是小于1的。

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

4 結束語

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

[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].