王占豐，陳鳴，邢長(zhǎng)友，白華利，魏祥麟

（解放軍理工大學(xué) 指揮自動(dòng)化學(xué)院，江蘇 南京 210007）

1 引言

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

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

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

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

2 TIV對(duì)時(shí)延空間的影響

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

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

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

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

對(duì)稱(chēng)性：δ(x, y)=δ(y, x)

三角形不等式：

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

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

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

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

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

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

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

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

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

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

圖1 MDS算法分解的譜分量

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

3 因特網(wǎng)時(shí)延空間修復(fù)

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

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

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

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

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

圖2 基于空間修復(fù)實(shí)現(xiàn)無(wú)誤差空間嵌入

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

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

4 基于空間修復(fù)的時(shí)延空間嵌入算法

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

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

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

算法1 S-Vivaldi

輸入：D //距離矩陣

5 算法評(píng)價(jià)

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

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

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

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

5.2 S-Vivaldi的嵌入誤差

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

其中，dij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的RTT實(shí)測(cè)值，dij表示算法的預(yù)測(cè)值。

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

5.3 算法參數(shù)影響

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

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

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

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

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

5.4 誤差分析

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

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

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

由于

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

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

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

6 結(jié)束語(yǔ)

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

[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]. 北京:科學(xué)出版社, 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.