趙玉琦，李 兵，2，熊燚銘，劉 暉 ，王 靜

1(武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430079)2(武漢大學(xué) 復(fù)雜網(wǎng)絡(luò)研究中心，武漢 430072)3(武漢大學(xué) 國(guó)家衛(wèi)星定位系統(tǒng)工程技術(shù)研究中心，武漢 430072)4(中國(guó)電子技術(shù)標(biāo)準(zhǔn)化研究院，北京100007)

1 引 言

隨著面向服務(wù)架構(gòu)的流行和分布式服務(wù)部署方式的出現(xiàn)，服務(wù)質(zhì)量成為了當(dāng)前重要的研究?jī)?nèi)容，而網(wǎng)絡(luò)性能是影響服務(wù)質(zhì)量(QoS，Quality of Service)重要因素.QoS的關(guān)鍵指標(biāo)主要包括：可用性、吞吐量、時(shí)延、時(shí)延變化(包括抖動(dòng)和漂移)和丟失，時(shí)延測(cè)量的研究可以有效提升網(wǎng)絡(luò)性能，進(jìn)而提高服務(wù)的質(zhì)量.基于Ping程序的時(shí)延測(cè)量方法存在網(wǎng)絡(luò)開(kāi)銷(xiāo)大的問(wèn)題，無(wú)法滿(mǎn)足測(cè)量需求.為了能夠在保證有效快速的獲取時(shí)延信息同時(shí)又僅花費(fèi)較小的開(kāi)銷(xiāo)，通過(guò)預(yù)測(cè)網(wǎng)絡(luò)節(jié)點(diǎn)間時(shí)延來(lái)獲取實(shí)際網(wǎng)絡(luò)中真實(shí)測(cè)量時(shí)延的近似值的方法，成為了研究熱點(diǎn).其中基于網(wǎng)絡(luò)坐標(biāo)系統(tǒng)的距離預(yù)測(cè)方案具有簡(jiǎn)單有效，開(kāi)銷(xiāo)小的特點(diǎn)，得到廣泛的研究.

網(wǎng)絡(luò)坐標(biāo)系統(tǒng)是一種具有可擴(kuò)展的互聯(lián)網(wǎng)距離預(yù)測(cè)方案，該方案將網(wǎng)絡(luò)節(jié)點(diǎn)距離空間映射到一個(gè)幾何空間之中，每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)應(yīng)幾何空間中一個(gè)坐標(biāo)點(diǎn)，節(jié)點(diǎn)間距離便可以依據(jù)它們的坐標(biāo)使用空間距離公式計(jì)算得出，從而把時(shí)間復(fù)雜度降低為O(N).因而，網(wǎng)絡(luò)坐標(biāo)系統(tǒng)能夠通過(guò)復(fù)雜度為O(N)的測(cè)量，來(lái)預(yù)測(cè)N(N-1)條鏈路的距離，從而有效的減少了大量端到端測(cè)量[1].通過(guò)網(wǎng)絡(luò)坐標(biāo)系統(tǒng)，高效地獲取時(shí)延，提升網(wǎng)絡(luò)性能.

2 相關(guān)工作

在現(xiàn)有的預(yù)測(cè)機(jī)制當(dāng)中，比較典型的研究有基于中心式的如GNP[2]、PIC[10]和基于非中心式的如NPS[11]、Vivaldi[3]等時(shí)延預(yù)測(cè)機(jī)制，上述研究?jī)?nèi)容都以如何有效快速的獲取網(wǎng)絡(luò)節(jié)點(diǎn)間時(shí)延作為研究重點(diǎn)，同時(shí)都將網(wǎng)絡(luò)節(jié)點(diǎn)放入N維的坐標(biāo)系統(tǒng)，通過(guò)計(jì)算節(jié)點(diǎn)坐標(biāo)距離作為網(wǎng)絡(luò)時(shí)延的預(yù)測(cè)值.GNP[2]是最早提出的網(wǎng)絡(luò)坐標(biāo)系統(tǒng)，將網(wǎng)絡(luò)中節(jié)點(diǎn)實(shí)測(cè)時(shí)延映射到數(shù)學(xué)的幾何空間上，將獲取網(wǎng)絡(luò)節(jié)點(diǎn)間時(shí)延轉(zhuǎn)化為獲取節(jié)點(diǎn)坐標(biāo)間距離.其思想是將網(wǎng)絡(luò)構(gòu)建在一個(gè)幾何空間上，如三維歐式空間，并用該幾何空間中的一個(gè)點(diǎn)作為網(wǎng)絡(luò)中任何一臺(tái)主機(jī)的位置.

Vivaldi一種完全分布式的算法[3]，節(jié)點(diǎn)僅需要獲得任何具有坐標(biāo)的鄰居節(jié)點(diǎn)的實(shí)測(cè)時(shí)延即可完成自身坐標(biāo)的更新.Vivaldi算法是公認(rèn)的具有優(yōu)秀性能的網(wǎng)絡(luò)坐標(biāo)系統(tǒng)構(gòu)建算法，其優(yōu)點(diǎn)在于其實(shí)現(xiàn)是全分布式的，無(wú)需額外設(shè)立基站設(shè)施，減少了網(wǎng)絡(luò)開(kāi)支.

J.Ledlie 等人研究延遲污染現(xiàn)象并提出MP-Filter抑制方法[8].該方法的主要思想是基于滑動(dòng)窗口濾波平滑時(shí)延，其網(wǎng)絡(luò)坐標(biāo)系統(tǒng)的各方面性能指標(biāo)是整體最優(yōu)的.MP-Filter的抑制方法在抑制隨機(jī)污染方面有一定成效，但該方法舍棄了部分實(shí)測(cè)時(shí)延，沒(méi)有保持原始的實(shí)測(cè)時(shí)延，這會(huì)使得其處理結(jié)果偏離實(shí)測(cè)時(shí)延，扭曲了節(jié)點(diǎn)坐標(biāo)，使得準(zhǔn)確度下降[9].

T-Vivaldi是對(duì)三角不等式違例(TIV)現(xiàn)象[5]造成網(wǎng)絡(luò)坐標(biāo)系統(tǒng)振蕩而提出的一種對(duì)TIV進(jìn)行檢測(cè)和抑制的方法.其主要思想是用三角不等式條件，隨機(jī)選取部分鄰居節(jié)點(diǎn)來(lái)檢測(cè)坐標(biāo)更新所依據(jù)的RTT值是否構(gòu)成TIV來(lái)檢測(cè)違例邊，并使用違例系數(shù)度量其違例程度.根據(jù)該系數(shù)的值抑制違例邊對(duì)坐標(biāo)的更新，從而達(dá)到了抑制TIV對(duì)坐標(biāo)系統(tǒng)的影響的目的.

文獻(xiàn)[6]則提出一種基于坐標(biāo)抖動(dòng)感知的慢啟動(dòng)抑制方法，將Vivaldi算法歸結(jié)成非線性方程組的迭代求解算法，并且基于方程組的矛盾性提出迭代因子的自適應(yīng)估計(jì)問(wèn)題.其原理是將Vivaldi算法的迭代步作為子步(Sup-step)，將多個(gè)子步聚合為一個(gè)超步，在超步中感知節(jié)點(diǎn)當(dāng)前狀態(tài)，收斂過(guò)程中超步會(huì)給定一個(gè)較大的迭代步長(zhǎng)加快收斂；收斂完成后，超步會(huì)減小迭代步長(zhǎng)以抑制坐標(biāo)抖動(dòng).

文獻(xiàn)[15]提出了一種能量更新抑制方法(Energy Method)，該方法的主要思想是：預(yù)先設(shè)置一個(gè)開(kāi)始窗口WS(Window Start)和一個(gè)當(dāng)前窗口WC(Window Current)，分別用于保存節(jié)點(diǎn)坐標(biāo)的歷史記錄.能量更新抑制方法適應(yīng)不同的網(wǎng)絡(luò)環(huán)境有一定的難度，計(jì)算也過(guò)于復(fù)雜，有較高的時(shí)間復(fù)雜度[9].

3 算法設(shè)計(jì)

針對(duì)在實(shí)際網(wǎng)絡(luò)坐標(biāo)系統(tǒng)中，由于各種隨機(jī)延遲污染以及三角不等式違例現(xiàn)象造成網(wǎng)絡(luò)坐標(biāo)振蕩等問(wèn)題，本文提出了一種基于Vivaldi算法的穩(wěn)定抑制Vivaldi算法(Stable inhibition Vivaldi).該算法分為三部分，第一部分是對(duì)隨機(jī)延遲污染的抑制，該部分使用了本文提出的TO-Filter抑制方法，第二部分是對(duì)網(wǎng)絡(luò)坐標(biāo)抖動(dòng)的檢測(cè)，第三部分是對(duì)坐標(biāo)抖動(dòng)進(jìn)行抑制.

3.1 TO-Filter方法

TO-Filter抑制方法(Timeout Filter)是本文提出的一種抑制隨機(jī)延遲污染的方法，其思想?yún)⒄樟薚CP超時(shí)重傳機(jī)制，通過(guò)計(jì)算測(cè)量來(lái)獲得當(dāng)前RTT的一個(gè)估計(jì)值，并以該RTT估計(jì)值為基準(zhǔn)來(lái)判定是否出現(xiàn)了隨機(jī)延遲污染.原理是：對(duì)于節(jié)點(diǎn)i，獲得來(lái)自節(jié)點(diǎn)j的每一個(gè)RTTi，j，計(jì)算MeanRTTi，j如公式(1).

MeanRTTi，j是RTTi，j的指數(shù)加權(quán)移動(dòng)平均 (Exponentially Weighted Moving Average，EWMA)，這種平均能很好的反映網(wǎng)絡(luò)的當(dāng)前擁堵情況，其中α的參考值是α=0.125.同時(shí)除了計(jì)算RTT的估計(jì)值，還要計(jì)算RTT的變化.定義DevRTTi，j，用于估計(jì)RTTi，j與MeanRTTi，j的偏離程度.DevRTTi，j是RTTi，j與MeanRTTi，j的差值的EWMA，這里β的默認(rèn)值為0.25.參數(shù)設(shè)置參考RFC標(biāo)準(zhǔn).

當(dāng)節(jié)點(diǎn)i獲得來(lái)自節(jié)點(diǎn)j的一個(gè)RTTi，j時(shí)，其估計(jì)值為MeanRTTi，j+4·DevRTTi，j.首先進(jìn)行隨機(jī)延遲污染的檢測(cè)，如果RTTi，j>MeanRTTi，j+4·DevRTTi，j則視為出現(xiàn)了隨機(jī)延遲污染，此時(shí)的RTTi，j可能是極大的，不具有可靠性，此時(shí)先計(jì)算DevRTTi，j與MeanRTTi，j的值，然后讓RTTi，j=MeanRTTi，j作為輸出.

MeanRTTi,j=(i-α)·MeanRTTi,j+α·RTTi,j

(1)

DevRTTi,j=(1-β)·DevRTTi,j+β·|RTTi,j-MeanRTTi,j|

(2)

(3)

DevRTTi,j=(1-β)·DevRTTi,j+β·|RTTi,j-MeanRTTi,j|

(4)

MeanRTTi,j=(1-α)·MeanRTTi,j+α·RTTi,j

(5)

3.2 三角不等式違例現(xiàn)象以及抑制方法

三角不等式違例現(xiàn)象是網(wǎng)絡(luò)坐標(biāo)振蕩的主要因素之一.對(duì)此，本文提出了一種坐標(biāo)抖動(dòng)感知方法.本文對(duì)該坐標(biāo)抖動(dòng)感知方法進(jìn)行改進(jìn)，將RTTi，j替換為MeanRTTi，j，替換的目的是減少個(gè)別不可靠的RTT對(duì)感知方法的準(zhǔn)確性的影響，同時(shí)不采用時(shí)間片的方法，而是使用計(jì)數(shù)的方法，當(dāng)累計(jì)獲得N個(gè)RTT后才進(jìn)行err的計(jì)算(N=|Neighbor(i)|，即節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù))，讓此時(shí)節(jié)點(diǎn)i的坐標(biāo)為xi(t)，本文的坐標(biāo)抖動(dòng)感知方法為公式(3).

當(dāng)errt>errt-1時(shí)，視為發(fā)生了抖動(dòng)，則會(huì)開(kāi)始執(zhí)行第三部分的抑制算法.要注意的是，坐標(biāo)抖動(dòng)感知方法只有在RTTi，j≤MeanRTTi，j+4·DevRTTi，j時(shí)才執(zhí)行，否則需要重新計(jì)數(shù).

3.3 穩(wěn)定抑制Vivaldi算法

對(duì)于節(jié)點(diǎn)i獲得來(lái)自節(jié)點(diǎn)j的一個(gè)RTTi，j，穩(wěn)定抑制算法的執(zhí)行步驟為：

步驟1.進(jìn)行初始化，讓d=1，計(jì)算器n=0，讓errt-1為一個(gè)極大數(shù)；

步驟2.對(duì)隨機(jī)延遲污染現(xiàn)象進(jìn)行檢測(cè)，如果RTTi，j>MeanRTTi，j+4·DevRTTi，j則執(zhí)行一次步驟1和步驟3，之后讓RTTi，j=MeanRTTi，j后，跳轉(zhuǎn)到步驟6；

步驟3.根據(jù)公式(4)和(5)計(jì)算DevRTTi，j與MeanRTTi，j的值：

步驟4.感知坐標(biāo)抖動(dòng)，若此時(shí)d不等于1，說(shuō)明已經(jīng)開(kāi)始抑制算法，跳轉(zhuǎn)到步驟6；否則計(jì)算器n=n+1，如果n<|Neightbor(i)|，跳轉(zhuǎn)到步驟6.

步驟5.讓n=0，利用公式(3)計(jì)算errt.若errt>errt-1則讓d=0，否則讓errt-1=errt.

步驟6.更新坐標(biāo).

4 實(shí)驗(yàn)實(shí)現(xiàn)及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

本文的時(shí)延數(shù)據(jù)來(lái)自華盛頓大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)系的King[注]https://pdos.csail.mit.edu/archive/p2psim/kingdata/數(shù)據(jù)集，該數(shù)據(jù)集有1953個(gè)節(jié)點(diǎn)，共97251194條記錄，這些節(jié)點(diǎn)都有至少9個(gè)鄰居節(jié)點(diǎn)，通過(guò)這些數(shù)據(jù)來(lái)進(jìn)行隨機(jī)延遲污染分析.在本實(shí)驗(yàn)中，兩個(gè)節(jié)點(diǎn)之間時(shí)延獲取的方式如下圖1，節(jié)點(diǎn)間通過(guò)最鄰近DNS服務(wù)器估算時(shí)延.

圖1 測(cè)試數(shù)據(jù)獲取方式示意圖Fig.1 Schematic diagram of test data acquisition

其中時(shí)延在0-100ms之間的記錄有約8830萬(wàn)條，約占總體90%，剩余約600萬(wàn)條記錄在100-500ms之間，有約90萬(wàn)條時(shí)延記錄在500-1000ms之間，1000-2000ms之間的有約64萬(wàn)條記錄，而3000以上也有近100萬(wàn)條記錄，這說(shuō)明了隨機(jī)延遲污染是普遍存在的.

4.2 實(shí)驗(yàn)設(shè)計(jì)

本文在Linux系統(tǒng)下進(jìn)行仿真，Ubuntu16.04，16GB內(nèi)存，代碼運(yùn)行環(huán)境為jdk1.7.0_67.為了檢測(cè)穩(wěn)定抑制Vivaldi算法的性能，本文采用的時(shí)延數(shù)據(jù)來(lái)自上述的實(shí)測(cè)時(shí)延數(shù)據(jù)集，并選取了其中231個(gè)節(jié)點(diǎn)，1907419條RTT記錄，這些節(jié)點(diǎn)都有至少9個(gè)鄰居節(jié)點(diǎn).將1907419條RTT記錄作為一次迭代，進(jìn)行20次迭代.

4.3 結(jié)果分析

根據(jù)實(shí)驗(yàn)設(shè)計(jì)進(jìn)行試驗(yàn)，其相對(duì)誤差RE累計(jì)分布圖如圖2所示.從圖2中可以看出，穩(wěn)定抑制Vivaldi算法中，相對(duì)誤差小于2的節(jié)點(diǎn)占了總體77.60%，而Vivaldi算法中，相對(duì)誤差小于1的節(jié)點(diǎn)占了總體73.32%，并且穩(wěn)定抑制Vivaldi算法的相對(duì)誤差RE累計(jì)分布始終比Vivaldi算法高，說(shuō)明了穩(wěn)定抑制Vivaldi算法的準(zhǔn)確性比Vivaldi算法更高.

除了使用相對(duì)誤差RE來(lái)度量算法的準(zhǔn)確性，本文還使用了另一種度量方法.對(duì)于節(jié)點(diǎn)i獲得來(lái)著節(jié)點(diǎn)j的一個(gè)RTT，在更新完坐標(biāo)后，此次更新誤差為公式(6).

(6)

則對(duì)于整個(gè)網(wǎng)絡(luò)坐標(biāo)系統(tǒng)中的n個(gè)測(cè)量RTT，定義整體誤差均值為公式(7).

(7)

則整體誤差均值e反映了整個(gè)網(wǎng)絡(luò)坐標(biāo)系統(tǒng)的誤差程度，整體誤差均值e越大，網(wǎng)絡(luò)坐標(biāo)系統(tǒng)的誤差越大.將1907419條RTT記錄作為一次迭代，計(jì)算每一次迭代的整體誤差均值，具體如圖3所示.

從圖3可以明顯看出Vivaldi算法以及穩(wěn)定抑制Vivaldi算法都在較少隨迭代次數(shù)內(nèi)隨著迭代次數(shù)增加而減少整體誤差，Vivaldi算法在第3次迭代后，其整體誤差均值在55.14上下波動(dòng)，而穩(wěn)定抑制Vivaldi算法在第3次迭代后，其整體誤差均值在53.29上下波動(dòng)，說(shuō)明了穩(wěn)定抑制Vivaldi算法比Vivaldi算法有著更高的準(zhǔn)確性，其準(zhǔn)確性提高了3.35%.同時(shí)穩(wěn)定抑制Vivaldi算法的整體誤差均值一直比Vivaldi算法低，說(shuō)明了穩(wěn)定抑制Vivaldi算法具有比Vivaldi算法更快的收斂能力.同樣將1907419條RTT記錄作為一次迭代，計(jì)算每一次迭代整體抖動(dòng)方差，具體如圖4所示.

圖2 相對(duì)誤差RE累計(jì)分布圖Fig.2 RE cumulative distribution

圖3 整體誤差均值Fig.3 Overall error mean

圖4 整體抖動(dòng)方差Fig.4 Jitter variance

圖4中反應(yīng)了算法剛開(kāi)始執(zhí)行時(shí)由于算法收斂造成坐標(biāo)的劇烈變化，Vivaldi算法第一次迭代的整體抖動(dòng)方差為141.35，而穩(wěn)定抑制Vivaldi算法第一次迭代的整體抖動(dòng)方差為222.34，這在一定程度上反應(yīng)了穩(wěn)定抑制Vivaldi算法有著比Vivaldi算法更快的收斂速度.而當(dāng)Vivaldi算法在第7次迭代后，其整體抖動(dòng)方差在17.25上下波動(dòng)，而穩(wěn)定抑制Vivaldi算法在第6次迭代后，其整體抖動(dòng)方差在15.75上下波動(dòng)，說(shuō)明穩(wěn)定抑制Vivaldi算法比Vivaldi算法有著更好的抑制抖動(dòng)能力，其抑制效果抖動(dòng)提升了8.7%.

5 結(jié) 論

網(wǎng)絡(luò)坐標(biāo)系統(tǒng)是一種網(wǎng)絡(luò)節(jié)點(diǎn)距離預(yù)測(cè)機(jī)制，能夠有效快速的獲取網(wǎng)絡(luò)節(jié)點(diǎn)間的時(shí)延信息，對(duì)于提升網(wǎng)絡(luò)性能，優(yōu)化網(wǎng)絡(luò)應(yīng)用有著很大的幫助.但由于網(wǎng)絡(luò)環(huán)境的復(fù)雜，網(wǎng)絡(luò)坐標(biāo)系統(tǒng)受到很多因素的影響，如由于網(wǎng)絡(luò)擁塞，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化，不同的數(shù)據(jù)包及其響應(yīng)可能沿不同路徑轉(zhuǎn)發(fā)而造成的隨機(jī)延遲污染，以及在將網(wǎng)絡(luò)節(jié)點(diǎn)放入幾何坐標(biāo)系時(shí)，產(chǎn)生的三角不等式違例現(xiàn)象，都可能造成了網(wǎng)絡(luò)坐標(biāo)的動(dòng)蕩，降低了網(wǎng)絡(luò)坐標(biāo)系統(tǒng)的準(zhǔn)確性.

Vivaldi是基于模擬的時(shí)延預(yù)測(cè)機(jī)制，是全分布式的，無(wú)需額外設(shè)立基站設(shè)施，對(duì)Internet拓?fù)渥兓休^好的適應(yīng)性.然而Vivaldi對(duì)于隨機(jī)延遲污染現(xiàn)象與TIV現(xiàn)象并沒(méi)有很好防范策略，本文則對(duì)這兩個(gè)方面展開(kāi)工作：

對(duì)于隨機(jī)延遲污染現(xiàn)象，本文介紹了隨機(jī)延遲污染抑制方法MP-Filter，同時(shí)提出了TO—Filter隨機(jī)延遲污染抑制方法.

其次對(duì)TIV現(xiàn)象，提出了穩(wěn)定抑制Vivaldi算法，其特點(diǎn)是同時(shí)考慮隨機(jī)延遲污染以及TIV現(xiàn)象，其思想是通過(guò)計(jì)算并保存節(jié)點(diǎn)獲得的每一個(gè)實(shí)測(cè)時(shí)延的估計(jì)值，通過(guò)比較實(shí)測(cè)延時(shí)與估計(jì)值，來(lái)判斷是否出現(xiàn)了隨機(jī)延遲污染，同時(shí)通過(guò)計(jì)算預(yù)測(cè)延時(shí)與均值估計(jì)值的差值均值來(lái)判斷是否出現(xiàn)了坐標(biāo)抖動(dòng)；在抑制抖動(dòng)方法中，選擇一種遞減函數(shù)作為抑制函數(shù)來(lái)減少坐標(biāo)更新程度.

通過(guò)搭建網(wǎng)絡(luò)坐標(biāo)系統(tǒng)，可以將服務(wù)中的要素在新的標(biāo)準(zhǔn)范圍內(nèi)度量，可以從全新的角度審視服務(wù)的發(fā)現(xiàn)、組合、協(xié)作、推薦和質(zhì)量等.同時(shí)在網(wǎng)絡(luò)坐標(biāo)系統(tǒng)內(nèi)，我們可以更加方便的度量服務(wù)質(zhì)量中的可用性、吞吐量、時(shí)延、時(shí)延變化(包括抖動(dòng)和漂移)和丟失問(wèn)題.進(jìn)一步，可以將構(gòu)建基于時(shí)空的網(wǎng)絡(luò)坐標(biāo)系統(tǒng)，通過(guò)高精準(zhǔn)定位和對(duì)時(shí)，實(shí)現(xiàn)對(duì)服務(wù)和服務(wù)要素的精準(zhǔn)定位和調(diào)控.