S-Vivaldi：一種基于空間修復的因特網(wǎng)時延空間嵌入算法

王占豐，陳鳴，邢長友，白華利，魏祥麟

（解放軍理工大學 指揮自動化學院，江蘇 南京 210007）

1 引言

在因特網(wǎng)時延空間中，違反三角形不等式(TIV,triangle inequality violation)的現(xiàn)象已被許多網(wǎng)絡(luò)測量數(shù)據(jù)集所證實[1～5]。TIV是指以節(jié)點間的往返時延(RTT, round trip time)作為距離測度，則網(wǎng)絡(luò)中任意3個節(jié)點構(gòu)成的三角形中2邊之和不大于第3個邊。通常認為 TIV現(xiàn)象是由低效路由策略（routing inefficiency）和網(wǎng)絡(luò)結(jié)構(gòu)導致的[1～3]。TIV現(xiàn)象使得因特網(wǎng)時延建模變得舉步維艱，TIV現(xiàn)象嚴重的數(shù)據(jù)集嵌入時誤差較大[4]。如何消除或緩解TIV的影響成為當前因特網(wǎng)時延空間建模（或網(wǎng)絡(luò)坐標系統(tǒng)）研究的熱點。

文獻[1]利用時延較小時 TIV嚴重性較輕這一現(xiàn)象，提出了一種基于時延閾值的層次化 Vivaldi因特網(wǎng)時延空間模型。文獻[5]進一步分析了時延大小和TIV的關(guān)系，發(fā)現(xiàn)這種關(guān)系并不明顯，為減小TIV導致的預測誤差，每個節(jié)點在選擇鄰居節(jié)點時，選擇那些使預測誤差最小的節(jié)點作為鄰居節(jié)點，以獲得最佳嵌入坐標。文獻[6]分析了因特網(wǎng)時延空間的聚簇（cluster）特性，指出TIV在不同的節(jié)點簇之間比較嚴重，而在簇內(nèi)則比較輕。這種方法雖然保證了坐標系統(tǒng)的穩(wěn)定性，卻限制了該算法的適用范圍。文獻[7]同樣利用因特網(wǎng)時延空間TIV的聚簇特性，提出了一種雙層因特網(wǎng)時延空間模型。文獻[8]使用一種基于決策樹的有監(jiān)督學習方法來判定TIV是否發(fā)生，其原理是將時延系統(tǒng)的預測值與實際測量值的統(tǒng)計量作為輸入樣本，通過標記的TIV來訓練決策樹，最后給出一顆TIV判定樹。

上述算法盡管表現(xiàn)形式不同，但都是通過將因特網(wǎng)時延空間劃分為不同粒度的子空間，以減輕數(shù)據(jù)集中的TIV嚴重程度。然而，對于如何減少劃分后數(shù)據(jù)子集內(nèi)的TIV比例和嚴重程度卻沒有提出明確的解決方案。本文主要貢獻是分析了TIV導致因特網(wǎng)時延空間嵌入誤差的機理，引入一種基于指數(shù)變換的空間修復方法，提了一種基于空間修復的因特網(wǎng)時延空間嵌入算法S-Vivaldi。

本文結(jié)構(gòu)如下：第2節(jié)分析TIV影響因特網(wǎng)時延空間模型精度的機理；第3節(jié)給出因特網(wǎng)時延空間的修復方法；第4節(jié)提出基于空間修復的因特網(wǎng)時延空間嵌入算法S-Vivaldi；第5節(jié)使用測量數(shù)據(jù)集對S-Vivaldi進行驗證和討論；第6節(jié)是結(jié)束語。

2 TIV對時延空間的影響

先引入相關(guān)的定義和定理。

定義1 因特網(wǎng)時延空間：對于一個具有n個節(jié)點N={N1, N2, N3,…, Nn}的網(wǎng)絡(luò)，任一節(jié)點Ni到網(wǎng)絡(luò)中所有節(jié)點的時延組成一個n維距離向量di=(di1, di2,…, din)，將所有節(jié)點的距離向量所構(gòu)成的空間D={ d1, d2,…, dn}稱為網(wǎng)絡(luò)時延空間。相應地，由因特網(wǎng)某個節(jié)點集合的距離向量所構(gòu)成的空間稱為因特網(wǎng)時延空間。

定義2 度量空間：設(shè)X是某個集合，δ:X×X→R+是一個二元映射，并且?x, y, z∈X滿足

非負性：δ(x, y)＞0?x≠y

對稱性：δ(x, y)=δ(y, x)

三角形不等式：

δ(x, y)≤δ(x, z)+δ(z, y)

則稱δ是X上的度量(距離)函數(shù)，稱M( X,δ)為度量空間。特別地，若X為有限集合，則稱M( X,δ)為有限度量空間。

定義3 半度量空間：若定義在X上的度量函數(shù)δ具有自反性、對稱性，但不滿足三角形不等式則稱M(X,δ)為半度量空間。

由此，可知因特網(wǎng)時延空間是一個半度量空間而非度量空間。

定義4 等距同構(gòu)：設(shè)(X,δ), (X1,δ1) 2個度量空間，如存在映射ψ：X→X1，滿足：1) ψ滿射；2)δ(x,y)=δ1(ψ(x), ψ(y)) (x, y∈X)則稱(X,δ)，(X1,δ1)是等距同構(gòu)的。

因特網(wǎng)時延空間建模是為了建立數(shù)學模型以描述因特網(wǎng)時延空間的拓撲結(jié)構(gòu)，進而使用度量公式計算和預測任意2個節(jié)點間的時延，即尋找因特網(wǎng)時延空間的等距同構(gòu)空間。具體說，就是構(gòu)造一個網(wǎng)絡(luò)節(jié)點到m維向量的映射f:N→Rm，將具有n個網(wǎng)絡(luò)節(jié)點的網(wǎng)絡(luò)N={N1, N2, N3,…, Nn}映射為m維幾何空間中的n個坐標點H={H1, H2, H3,…, HN}，同時使得坐標點之間的距離與實際網(wǎng)絡(luò)測量得到的時延誤差值最小，如式(1)所示。其中，ξ表示嵌入誤差，ijd表示實測時延，表示預測時延。

定理1 任意一個具有n個節(jié)點的有限度量空間M( X,δ)均可以以O(shè)(logn)的扭曲度嵌入到一個O(logn)維歐氏空間中[9]。

定理1說明如果一個空間可以以較小的誤差嵌入到歐氏空間中，則必須要求原始空間為度量空間。然而，由于因特網(wǎng)時延空間是一個半度量空間，存在大量TIV現(xiàn)象，使得因特網(wǎng)時延空間D不存在到歐氏空間的同構(gòu)映射，從而引入了較大的嵌入誤差。下面使用經(jīng)典的空間嵌入算法MDS來分析TIV對因特網(wǎng)時延空間嵌入誤差的影響。

MDS算法分為3步：1) 獲得節(jié)點間平方距離矩陣D(2)=[]；2) 對D(2)進行中心化，BD=-(1/2)JD(2)J，其中，J=I-n-1E，其中，I為單位矩陣，E為全為1的矩陣；3) BD分解得BD=Q∧QT，其中，Q為BD分解后的奇異向量，∧=[λi]為特征值的降序排列，選取其中的正特征值∧+，則Y=Q∧為各個節(jié)點的坐標。由此可見，其中的負特征值∧-引入的誤差為

此時，可以根據(jù)嵌入誤差e是否小于預期的閾值來選擇嵌入維數(shù)r。如果D來自于一個r維歐氏空間Er(r＜＜n)，則BD為一個半正定矩陣，∧中不存在負特征值且其前r個特征值為正。此時，若嵌入維數(shù)為大于等于r，可以無誤差地進行嵌入。然而，由于因特網(wǎng)時延空間中TIV的存在，則BD的特征值集合∧中存在小于0的特征值。圖1是采用MDS算法對因特網(wǎng)時延數(shù)據(jù)集Harvard、InetDim（參見5.1節(jié)的相關(guān)解釋）和歐氏空間數(shù)據(jù)集分解后獲得的特征值歸一化結(jié)果，圖中給出了其前30個特征值的情況。Harvard和InetDim 2個因特網(wǎng)時延數(shù)據(jù)集分解后都存在負特征值，而來自于5維歐氏空間的數(shù)據(jù)集分解后獲得的特征值均為非負值。

圖1 MDS算法分解的譜分量

可見，TIV是導致嵌入誤差的一個重要因素。然而，以往的網(wǎng)絡(luò)坐標系統(tǒng)無論是采用具有一定曲率的空間進行嵌入[10]，還是通過將時延空間劃分為較小的子空間，都無法消除TIV引入的誤差。為了解決由TIV產(chǎn)生的較大因特網(wǎng)時延空間嵌入誤差的問題，本文提出一種基于空間修復的因特網(wǎng)時延空間嵌入算法。

3 因特網(wǎng)時延空間修復

基于空間修復的因特網(wǎng)時延空間嵌入算法基本思想如下:設(shè)存在一個同構(gòu)的映射T:D→D'，即將因特網(wǎng)時延空間D修復為一個度量空間D'，并假設(shè)D'存在一個與其等距同構(gòu)的k(k＜＜n)維歐氏空間Rk。若D'嵌入到Rk后的坐標集合為C，這樣就可以建立從網(wǎng)絡(luò)節(jié)點N到坐標空間C的一個映射。當需要估計或者預測網(wǎng)絡(luò)中任意2個節(jié)點間的距離時，可以通過逆變換計算出嵌入后節(jié)點間的距離矩陣D?（其中，δ為度量函數(shù)）。算法的關(guān)鍵在于能否找到一個映射T，且T存在一個單射的逆變換T '。

空間修復技術(shù)是一種將非度量空間變換為度量空間的映射T，通過空間修復可以獲得與原始空間同構(gòu)且不存在TIV現(xiàn)象的映射空間。將半度量空間變換為度量空間主要有2種空間修復技術(shù)：最短路法和指數(shù)修復法[11]。最短路法就是通過尋找任意2點之間的最短距離作為修復后2點間距離，該最短距離可用式(3)定義，最短距離可以使用Dijkstra等算法來計算，其中，x、y表示2個節(jié)點，ni表示從x到y(tǒng)路徑上的節(jié)點，Dis(ni,ni+1)表示節(jié)點間的距離。然而這種變換卻無法確定從修復后的距離矩陣D'到原始距離矩陣D的逆變換。

指數(shù)修復法則不存在無法進行逆變換的問題，進行逆變換時只需要對修復后矩陣的元素進行逆指數(shù)變換即可。對于一個距離矩陣而言，若Dis(x, y)代表節(jié)點x和y之間的距離，當節(jié)點之間距離出現(xiàn)違反三角形不等式約束情況時，若進行變換Dis′( x, y):=Dis( x, y)1/ω，即可消除這些節(jié)點間的TIV問題，其中，修復系數(shù)為ω=maxx,y,z∈Nlb(Dis(x,z)/Dis(x,y))。這是由于對于任何距離矩陣，當ω→∞時，?x? y( x≠y→Dis( x, y)=1)，此時肯定不存在TIV現(xiàn)象。這種變換的最大優(yōu)點是能在滿足保序性的前提下實現(xiàn)空間修復，即節(jié)點在原始空間中的距離臨近度關(guān)系不因變換而改變；缺點是當修復系數(shù)ω取值過大時，會使數(shù)據(jù)喪失一些原有屬性，如聚簇特性。

2.2.3 多水塘技術(shù) 尹澄清首先提出多水塘系統(tǒng)的概念，主要內(nèi)容包括水塘和滯留池[13]。修建暴雨滯留池是控制農(nóng)業(yè)面源污染的重要方法[14]，也是歐美國家中污染控制的有效方法。多水塘系統(tǒng)能截留94%以上農(nóng)業(yè)中的氮、磷污染負荷[15]。尹澄清等學者發(fā)現(xiàn)，人工多水塘系統(tǒng)具有很強的截留面源污染物的能力，能截留大部分無機態(tài)銨態(tài)氮和正磷酸根態(tài)磷。

下面通過一個簡單示例闡述如何通過指數(shù)變換將距離本來不滿足三角形不等式約束的網(wǎng)絡(luò)節(jié)點無誤差地嵌入到二維歐氏空間中。圖2(a)中由于節(jié)點間距離違反三角形不等式約束Dis(B,C)＞Dis(A, B)+Dis(A,C)，因此在嵌入(如使用Vivaldi算法)到圖2(b)二維歐氏空間中時始終存在誤差，其誤差為在圖2(c)中，當修復系數(shù)ω=2時即可使得節(jié)點滿足三角形不等式，從而使節(jié)點無誤差地嵌入到圖2(d)所示二維歐氏空間中。由此可見，在選擇合適修復系數(shù)的前提下，空間修復能夠有效地消除TIV現(xiàn)象對空間嵌入的影響，進而提高距離預測精度。

圖2 基于空間修復實現(xiàn)無誤差空間嵌入

利用指數(shù)變換的空間修復技術(shù)，分別采用不同的修復系數(shù)對Harvard數(shù)據(jù)集和InetDim數(shù)據(jù)集進行了空間修復，結(jié)果如表1所示。結(jié)果表明，隨著修復系數(shù)ω增大2個數(shù)據(jù)集中的TIV比例都明顯地減小。這說明空間修復技術(shù)能夠有效減少因特網(wǎng)時延中的TIV現(xiàn)象，從而減輕TIV對距離預測精度的影響。

表1 采用不同修復系數(shù)后的TIV比例

4 基于空間修復的時延空間嵌入算法

將一個空間坐標嵌入到某目標空間的方法有多種，常用的算法有半定規(guī)劃 (SDP, semi-definite programming) 方法、MDS、單純型下降 (DHS,down-hill simplex) 算法、Lipschit嵌入算法、Vivaldi[12]以及BBS[10]算法等。本文在最常用的網(wǎng)絡(luò)坐標系統(tǒng)嵌入算法 Vivaldi基礎(chǔ)之上，提出一種基于空間修復的因特網(wǎng)時延空間嵌入算法 S-Vivaldi(scaling-Vivaldi)。

Dabek認為，節(jié)點坐標嵌入的過程本質(zhì)上就是最小化全局誤差的過程，而這一全局最小化過程與物理上通過調(diào)整彈簧端點位置最小化彈簧的彈性勢能非常類似[12]。Vivaldi算法將距離預測誤差之和最小化問題類比為彈簧彈性勢能最小化問題來進行求解。節(jié)點在加入系統(tǒng)前隨機測量到系統(tǒng)中一組節(jié)點的距離，然后根據(jù)測量結(jié)果確定自己的初始坐標值。每個節(jié)點 Ni與其鄰居節(jié)點 Nj都通過一個虛擬彈簧相連，彈簧在彈性勢能的作用下伸長或壓縮，最終彈簧在系統(tǒng)預測誤差最小時達到一個平衡狀態(tài)，此時節(jié)點的坐標即為最優(yōu)嵌入坐標。S-Vivaldi的基本思路是在進行節(jié)點嵌入前，首先對因特網(wǎng)時延空間 D進行空間修復，然后對修復后的空間 D'采用Vivaldi算法進行嵌入。

S-Vivaldi算法僅在嵌入之前引入因特網(wǎng)時延空間的指數(shù)變換，其復雜度與 Vivaldi的復雜度相同，為O(r(L2+LH))。其中，L為基準節(jié)點數(shù)目，H為網(wǎng)絡(luò)中節(jié)點總數(shù)，r為迭代的次數(shù)。

算法1 S-Vivaldi

輸入：D //距離矩陣

5 算法評價

5.1 數(shù)據(jù)集

獲得用于研究時延空間嵌入和時延空間性質(zhì)的數(shù)據(jù)集大致有2種方法：一是直接測量，二是間接估計。采用直接測量的方式，需要部署大量的測量點，測量點間通過ping或traceroute等方法來測量往返時延。用這種方式獲得的數(shù)據(jù)集最接近真實情況，但需要借助分布式測量平臺（如PlanetLab、DIMES等）的支持。由于這些測量平臺部署的測量點數(shù)目有限，獲得的數(shù)據(jù)集規(guī)模較小。采用間接估計的方式不需要部署測量點，而是通過某種機制來估計2個節(jié)點間的時延。例如測量工具 King，就是通過測量靠近2個 IP地址的DNS服務器間的時延來估計IP地址對間的時延。測量主機可以位于網(wǎng)絡(luò)的任何位置，而與被測對象的位置無關(guān)，但測量數(shù)據(jù)與真實情況存在一定差異。利用間接測量的方法往往可以獲得較大規(guī)模的數(shù)據(jù)集。

本文使用了通過直接測量獲取的Harvard數(shù)據(jù)集和間接測量獲取的 InetDim數(shù)據(jù)來分別驗證S-Vivaldi算法，其相關(guān)信息見表2。

表2 時延數(shù)據(jù)集

5.2 S-Vivaldi的嵌入誤差

因特網(wǎng)時延空間嵌入算法的精確度是通過嵌入誤差來度量的，誤差越小則說明算法的精度越高，反之則說明精度越低。嵌入誤差定義為

其中，dij表示節(jié)點i與節(jié)點j之間的RTT實測值，dij表示算法的預測值。

圖3是在2個數(shù)據(jù)集上，采用S-Vivaldi算法和Vivaldi算法實驗效果的對比。在實驗中，設(shè)置的嵌入數(shù)為10，鄰居數(shù)目25，迭代次數(shù)為105輪。S-Vivaldi-middle是S-Vivaldi算法的中間結(jié)果，即修復矩陣 D'在 Vivaldi算法下的嵌入誤差。將 D'進行反變換則得到S-Vivaldi曲線，可以看出這時誤差會放大。比較Vivaldi與S-Vivaldi曲線，發(fā)現(xiàn)在數(shù)據(jù)集Harvard上誤差較小時，Vivaldi算法優(yōu)于 S-Vivaldi算法，而當誤差大于 0.3以后，S-Vivaldi 的精度大于 Vivaldi算法的精度；而在數(shù)據(jù)集 InetDim上，S-Vivaldi的精度一直優(yōu)于Vivaldi算法。在Harvard數(shù)據(jù)集上，當誤差為0.5時，S-Vivaldi算法精度高于Vivaldi算法精度約7%；在 InetDim數(shù)據(jù)集上，當誤差為 0.4時，S-Vivaldi算法精度高于 Vivaldi算法精度約20%。造成這種預測結(jié)果差異的原因是Harvard數(shù)據(jù)中存在大量未知數(shù)據(jù)，不響應節(jié)點間的時延設(shè)置為-1，對嵌入結(jié)果產(chǎn)生了負面影響，而在數(shù)據(jù)集 InetDim不響應節(jié)點相對較少，進一步分析見5.4節(jié)。

5.3 算法參數(shù)影響

下面考察嵌入維數(shù)對于 S-Vivaldi算法精度的影響。圖4比較了S-Vivaldi算法在2個數(shù)據(jù)上選擇不同嵌入維數(shù)時的精度，可以看到隨著嵌入維數(shù)增加則誤差隨之減小。但當嵌入維數(shù)大于 10時，嵌入誤差減小的不是十分明顯，因而選擇嵌入維數(shù)10較為合適。

圖3 S-Vivaldi與Vivaldi算法在Harvard數(shù)據(jù)集上的嵌入誤差

下面分析 S-Vivaldi算法在不同修復系數(shù)(ω)下的嵌入誤差。在實驗中，為ω設(shè)置了許多不同的取值，為了能更加明顯地顯示S-Vivaldi算法在不同修復系數(shù)下的變化趨勢，僅列出了4組代表性的數(shù)據(jù)。圖 5是 Harvard數(shù)據(jù)集在 4個不同修復系數(shù)時S-Vivaldi的嵌入誤差，結(jié)果表明嵌入誤差隨著ω增大而增大。這是因為當ω→∞時，所有節(jié)點間修復后的距離將都為1，成為一個N維的超立方體，無法保持原有距離矩陣中的信息。因此，修復系數(shù)一般不宜過大，實驗證明當修復系數(shù)設(shè)為2時能獲得較好性能。

圖4 不同嵌入維數(shù)下的嵌入誤差

圖5 在不同的修復系數(shù)下S-Vivaldi的嵌入誤差

5.4 誤差分析

因特網(wǎng)時延空間的低維特性是保證嵌入精度的基本前提[14]。實際上空間修復技術(shù)僅能消除時延空間中的 TIV，并不能保證修復后的時延矩陣 D'保持原有時延空間D的維數(shù)特征。因而采用主成分分析 (PCA, principal component analysis) 法來觀察2個數(shù)據(jù)集修復前后的維數(shù)特征。設(shè)(λ1, λ2, …, λN)為用PCA算法所求得的時延矩陣D的特征值的降序排列，則前n個主軸的累積貢獻率為

在圖 6中，直方圖表示每一個維度的單獨貢獻率，曲線表示前幾維的累積貢獻率。從圖中可以看出2個數(shù)據(jù)集修復前后的維數(shù)特征變化是相反的。Harvard數(shù)據(jù)集修復前，前10維的累積貢獻率幾乎達到100%，且前5維的單獨貢獻率較大；而修復后前10維的累積貢獻率明顯不足100%，且前5維的單獨貢獻率也沒有以前明顯。因此，導致了修復后S-Vivaldi在嵌入誤差較小時，不如Vivaldi算法精度高。InetDim數(shù)據(jù)集修復前后變化卻是相反的，因此S-Vivaldi的精度一直高于 Vivaldi。從總體上看，Harvard數(shù)據(jù)集修復前后前幾維貢獻率都高于InetDim數(shù)據(jù)集，因而2個算法在Harvard數(shù)據(jù)集上精度都高于在InetDim上的嵌入結(jié)果。這表明數(shù)據(jù)集修復前后維數(shù)的變化會影響S-Vivaldi算法的精度。

下面分析導致2個數(shù)據(jù)維數(shù)特征變化的原因。通過統(tǒng)計，Harvard數(shù)據(jù)集和InetDim數(shù)據(jù)集中的不響應數(shù)據(jù)分別占所在數(shù)據(jù)集的3.5%和0.1%，雖然兩者的比例都不高，但是前者卻是后者的35倍。下面分析不響應數(shù)據(jù)如何影響數(shù)據(jù)集的特征值分布規(guī)律。設(shè)節(jié)點間的真實時延矩陣為D，而測得數(shù)據(jù)集為D', B為不響應節(jié)點間的時延矩陣，則D'=D-B。若D、D'特征值分別為(λ1, λ2,…, λN)、(λ'1, λ'2,…, λ'N)，根據(jù)矩陣的擾動理論[15]，損失的特征值為

由于

因此當||B||2越小時，則|λi-λ'i|越小，變換后損失的特征值信息越少。由于不響應節(jié)點的時延矩陣B中節(jié)點較少，低維特征明顯，特征值主要集中在前幾維，從而導致測量數(shù)據(jù)集的前幾維特征值損失較大，累積貢獻率下降，出現(xiàn)維數(shù)增加。要減小||B||2的值，就要減少測量中的不響應節(jié)點。

圖6 數(shù)據(jù)集修復前后的維數(shù)特征

在部署S-Vivaldi系統(tǒng)時，要減少測量的不響應節(jié)點，可以通過以下2種措施來實現(xiàn)：一是S-Vivaldi系統(tǒng)不允許加入不響應的節(jié)點，二是通過引入如Htrae系統(tǒng)中基于地理信息的時延估計方法來對系統(tǒng)進行初始化[16]。

6 結(jié)束語

大量網(wǎng)絡(luò)測量證實了TIV在因特網(wǎng)時延空間中廣泛存在，它嚴重地影響因特網(wǎng)時延空間模型和網(wǎng)絡(luò)坐標系的精度。目前的研究通過選擇帶有一定曲率的空間進行嵌入或是將因特網(wǎng)時延空間劃分為不同粒度的子空間，都無法解決TIV引入的嵌入誤差。由此，本文提出了基于空間修復的因特網(wǎng)時延嵌入算法S-Vivaldi，通過引入指數(shù)變換來對因特網(wǎng)時延空間進行修復，大大減少了修復后因特網(wǎng)時延空間的TIV比例，并使用矩陣擾動理論分析了在不同數(shù)據(jù)集上嵌入誤差的原因，使得S-Vivaldi算法更易部署使用。實驗分析也驗證了S-Vivaldi算法的可行性，該方法同樣適用于先前提出的層次化網(wǎng)絡(luò)坐標系統(tǒng)[2,7,17]。下一步將在因特網(wǎng)中加以部署應用，并做進一步改進。

[1] WANG G, ZHANG B, NG T S E. Towards network triangle inequality violation aware distributed systems[A]. Proceedings of IMC2007[C]. San Diego, CA, USA, 2007. 175-188.

[2] MOHAMED A K, BAMBA G, FRANCOIS C, et al. Towards a two-tier internet coordinate system to mitigate the impact of triangle inequality violations[A]. Proceedings of IFIP Networking Singapore[C]. 2008.397-408.

[3] ZHENG H, LUA E K, PIAS M, et al. Internet routing policies and round-trip-times[A]. Proceedings of PAM[C]. Boston, USA, 2005. 236-250.

[4] LEE S, ZHANG Z L, SAHU S, et al. On suitability of euclidean embedding for host-based network coordinate systems[J]. IEEE/ACM Transactions on Networking, 2010, 18(1): 27-40.

[5] WANG G, ZHANG B, NG T S E. Towards network triangle inequality violation aware distributed systems[A]. Proceedings of IMC2007[C]. San Diego, CA, USA, 2007.175-188.

[6] ZHANG B, NG T S E, NANDI A, et al. Measurement-based analysis,modeling, and synthesis of the internet delay space[A]. Proceedings of IMC2006[C]. Rio de Janeiro, Brazil, 2006.

[7] ZHU Y, CHEN Y, ZHANG Z, et al. Taming the triangle inequality violations with network coordinate system on real internet[A]. Pro-ceedings of ReArch'10 Conjunction with CoNEXT'10[C]. Philadelphia,USA, 2010.

[8] LIAO Y, MOHAMED A, GUEYE K B, et al. Work in Progress:Detecting Triangle Inequality Violations in Internet Coordinate Systems by Supervised Learning[R]. Technical Rseport, 2009.

[9] MATOUSEK J. Lectures on Discrete Geometry[M]. New York,Springer-Verlag, 2002.212.

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

[11] CLARKSON K. Nearest-Neighbor Searching and Metric Space Dimensions. Nearest-Neighbor Methods for Learning and Vision: Theory and Practice[M]. Cambridge, Massachusetts, USA: MIT Press,2006.

[12] DABEK F, COX R, KAASHOEK F, et al. Vivaldi: a decentralized network coordinate system[A]. Proceedings of SIGCOMM2004[C].Portland, OR, USA, 2004.15-26.

[13] NC research group at Harvard[EB/OL]. http://www.eecs.harvard.edu/syrah/nc, 2008.

[14] ABRAHAO B, KLEINBERG R. On the Internet delay space dimensionality[A]. Proceedings of IMC[C]. Vouliagmeni, Greece, 2008. 157-168.

[15] 戴華. 矩陣論[M]. 北京:科學出版社, 2005. 189-198.DAI H. Theory of Matrices[M]. Beijing: Science Press, 2005. 189-198.

[16] AGARWAL S, LORCH J R. Matchmaking for online games and other latency-sensitive P2P systems[A]. Proceedings of SIGCOMM2009[C].Barcelona, Spain, 2009.315-326.

[17] ZHANG R, HU Y, LIN X, et al. A hierarchical approach to internet distance prediction[A]. Proceedings of ICDS2006[C]. Washington,DC, USA, 2006.73-80.