一種網(wǎng)絡(luò)時(shí)延矩陣分布式自適應(yīng)重建算法

王 聰 張鳳荔王瑞錦 李 敏 楊曉翔

(電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731)

1 引言

互聯(lián)網(wǎng)環(huán)境下的許多重要應(yīng)用，包括內(nèi)容分發(fā)網(wǎng)絡(luò)(CDN)[1]，電子競(jìng)技[2,3]，云計(jì)算[4,5]等，其性能都強(qiáng)烈依賴于網(wǎng)絡(luò)時(shí)延矩陣的感知與獲取。點(diǎn)對(duì)點(diǎn)的測(cè)量雖然能夠精確填充時(shí)延矩陣的任一元素，但其測(cè)量復(fù)雜度達(dá)到O(n2)，難以擴(kuò)展到大規(guī)模網(wǎng)絡(luò)應(yīng)用。如何利用有限的測(cè)量數(shù)據(jù)盡可能精確地恢復(fù)時(shí)延矩陣，已引起了廣泛關(guān)注。

早期關(guān)于非測(cè)量方式的時(shí)延矩陣重建研究將節(jié)點(diǎn)嵌入到特定的度量空間，以節(jié)點(diǎn)在度量空間內(nèi)的距離擬合節(jié)點(diǎn)間的真實(shí)時(shí)延，此類研究成果通常被歸為網(wǎng)絡(luò)坐標(biāo)系統(tǒng)(Network Coordinate System,NCS)[6]。雖然 NCS能夠滿足一定程度上的性能需求，也已在工業(yè)環(huán)境下得到部分應(yīng)用，然而互聯(lián)網(wǎng)中廣泛存在的非對(duì)稱路由和非最短路徑路由現(xiàn)象卻違背了度量空間的定義，且NCS涉及的非凸優(yōu)化問(wèn)題也使其難以避免局部極小化現(xiàn)象。近期研究證明時(shí)延矩陣具備明顯的近似稀疏性，即矩陣僅有少數(shù)的特征值具有較大的模[7]。文獻(xiàn)[8]已就這種稀疏特征及其與 NCS度量空間的維度關(guān)系進(jìn)行了理論上的深入分析與闡述，從而將NCS歸結(jié)為某種意義上的時(shí)延矩陣稀疏逼近模型。根據(jù)Candes等人[9]的研究，盡管時(shí)延矩陣重建是一個(gè)欠定問(wèn)題，但在附加必要的稀疏性約束之后，該問(wèn)題可以高概率得到惟一的可行解。這種約束一般為矩陣的零范數(shù)或跡范數(shù)的極小化約束，以限制重建模型的復(fù)雜程度。然而在分布式環(huán)境下，如對(duì)等網(wǎng)絡(luò)或分布式控制系統(tǒng)，抽取一個(gè)全局一致的時(shí)延矩陣映像通常是困難的。一個(gè)折中的方法是定義一個(gè)可能滿足稀疏性約束的時(shí)延矩陣零范數(shù)先驗(yàn)估計(jì)，并將時(shí)延矩陣的左右特征向量分布在全網(wǎng)中共同維護(hù)，使得每個(gè)參與計(jì)算的節(jié)點(diǎn)均持有一個(gè)行向量和列向量，通過(guò)向量的點(diǎn)積運(yùn)算，任一節(jié)點(diǎn)都可以補(bǔ)全與其相關(guān)的元素。與基于內(nèi)積運(yùn)算的NCS模型相比，這種方法具備顯著良好的特性：一是容易轉(zhuǎn)化為凸優(yōu)化問(wèn)題求解；二是容易處理非最短路徑路由引起的三角違例(Triangle Inequality Violations, TIVs)現(xiàn)象；三是不要求重建矩陣嚴(yán)格對(duì)稱，因而容易處理非對(duì)稱路由問(wèn)題?；谶@種思想，文獻(xiàn)[10]首先提出了一種原型算法 IDES，但時(shí)延空間可能存在的多子流形特征[11]，以及先驗(yàn)估計(jì)的不精確性，使得向量維護(hù)和更新過(guò)程中難以避免病態(tài)矩陣的求逆運(yùn)算，導(dǎo)致計(jì)算精度難以滿足要求[12]，因而一直未能引起足夠的重視。直到Liao等人[13]通過(guò)引入正則化算子實(shí)現(xiàn)了基于最小均方誤差有偏估計(jì)的 DMF算法，重建算法的魯棒性才得到實(shí)質(zhì)性的提升。而Phoenix算法繼承了正則化處理的思路，并通過(guò)非負(fù)約束解決了重建矩陣中的負(fù)值元素問(wèn)題[14]。最近，包括1l損失函數(shù)和Huber損失函數(shù)在內(nèi)的兼顧魯棒性和異常數(shù)據(jù)處理能力的誤差優(yōu)化準(zhǔn)則也開始引起關(guān)注[15,16]。但受限于目標(biāo)函數(shù)的非光滑性和向量的非負(fù)約束，求解此類損失函數(shù)通常僅依賴于梯度下降法，收斂速度并不令人滿意。

本文提出一種支持多種誤差評(píng)價(jià)準(zhǔn)則的時(shí)延矩陣重建ADMC算法。通過(guò)引入伸縮因子實(shí)現(xiàn)對(duì)不同誤差評(píng)價(jià)準(zhǔn)則和生命周期不同階段下梯度下降步長(zhǎng)的自適應(yīng)搜索，在不損失計(jì)算精度的前提下，以較低的計(jì)算代價(jià)提升模型的泛化能力。

2 時(shí)延矩陣分布式重建的自適應(yīng)迭代算法

時(shí)延矩陣分布式重建的基本思想是，一個(gè)包含P個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)存在PP×的時(shí)延矩陣D，其中的任一元素,ijd 代表節(jié)點(diǎn)i到節(jié)點(diǎn)j的傳輸時(shí)延，受到網(wǎng)絡(luò)規(guī)模和計(jì)算資源的限制，一般情況下D會(huì)因?yàn)椴糠謹(jǐn)?shù)據(jù)的缺失而轉(zhuǎn)變?yōu)椴煌暾仃?'D ，時(shí)延矩陣重建的目的在于利用 'D 提供的有限信息，生成一個(gè)完整矩陣︿D，使之成為D的良好擬合，全局一致的不完整矩陣稀疏逼近已得到深入的研究[17,18]?？紤]到時(shí)延矩陣的近似稀疏性，這種思路顯然是合理的。但在完全去中心化的環(huán)境下，時(shí)延矩陣一致映像的抽取通常是難以完成的。一般而言，節(jié)點(diǎn)容易協(xié)商得到一致的重建矩陣︿D的零范數(shù)先驗(yàn)估計(jì)N，以確保稀疏性。此時(shí)零范數(shù)的極小化約束可松弛為等式約束，即求解如式(1)的約束優(yōu)化問(wèn)題：

其中Ω是 'D 所有未缺失元素的下標(biāo)子集，PΩ是Ω上的投影算子，即只取在Ω中的對(duì)應(yīng)元素進(jìn)行計(jì)算；是預(yù)定義的誤差損失函數(shù)；計(jì)算矩陣的零范數(shù)，即矩陣的非零特征值個(gè)數(shù)。易知可表示為兩個(gè)PN×的系數(shù)矩陣U和V的乘積：

于是,ijd可用的對(duì)應(yīng)元素,ijd?擬合：

由于U或V行向量之間的不存在交集元素，這使其易分布于全網(wǎng)共同進(jìn)行維護(hù)：令任一節(jié)點(diǎn)i持有U和V中對(duì)應(yīng)的行向量iu和iv，則節(jié)點(diǎn)只需獲得目標(biāo)節(jié)點(diǎn)持有的向量，便可計(jì)算與對(duì)方的近似時(shí)延，從而大大減少了網(wǎng)絡(luò)測(cè)量帶來(lái)的資源開銷。對(duì)應(yīng)地，式(1)可分解為如式(4)兩個(gè)耦合子問(wèn)題的聯(lián)立：

當(dāng)取l1損失函數(shù)作為誤差評(píng)價(jià)準(zhǔn)則時(shí)，有

此時(shí)，有

當(dāng)取l2損失函數(shù)作為誤差評(píng)價(jià)準(zhǔn)則時(shí)，有

此時(shí)，有

當(dāng)取Huber損失函數(shù)作為誤差評(píng)價(jià)準(zhǔn)則時(shí)，有

此時(shí)，有

根據(jù)文獻(xiàn)[19]的定理 2.1.6，當(dāng)損失函數(shù)為凸函數(shù)時(shí)，可保證式(5)為凸優(yōu)化問(wèn)題，此時(shí)式(5)的優(yōu)化過(guò)程與此類同，限于篇幅在此不予討論。接下來(lái)討論式(6)的求解。顯然地，系統(tǒng)生命周期的不同階段對(duì)ηu和ηv的要求是不同的：在系統(tǒng)生成初期或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生突變時(shí)，需要以較大的步長(zhǎng)快速收斂到最優(yōu)值附近；而當(dāng)系統(tǒng)進(jìn)入到穩(wěn)定狀態(tài)時(shí)，需要以較小的步長(zhǎng)進(jìn)行逐步求精，并能感知和快速適應(yīng)隨時(shí)可能發(fā)生的拓?fù)渫蛔?，如蜂集態(tài)(flash- crowd)等。對(duì)生命周期不同階段需求進(jìn)行折中，DMFSGD算法[16]提出了一種基于折半查找的步長(zhǎng)搜索策略，針對(duì)不同的損失函數(shù)的搜索上界maxη，通過(guò)實(shí)驗(yàn)給出了不同的定義。但該策略的缺點(diǎn)也顯而易見：當(dāng)較大時(shí)，算法在穩(wěn)定狀態(tài)下須經(jīng)過(guò)多輪查找才能得到恰當(dāng)?shù)闹?；而?dāng)maxη較小時(shí)，算法難以在可接受的時(shí)間內(nèi)收斂到穩(wěn)定狀態(tài)。我們注意到，系統(tǒng)生命周期的不同階段存在一定的延續(xù)性，即后一時(shí)刻的系統(tǒng)狀態(tài)與前一時(shí)刻往往不會(huì)有明顯的差異，換言之，相鄰兩個(gè)時(shí)刻的迭代步長(zhǎng)通常并不是條件獨(dú)立的?；谶@種假設(shè)，ADMC算法利用步長(zhǎng)搜索的歷史信息提出了一種基于上界倍增的步長(zhǎng)搜索策略，以上一輪迭代成功檢索的步長(zhǎng)因子的某個(gè)倍數(shù)為搜索上界，進(jìn)行折半查找，從而達(dá)到降低計(jì)算代價(jià)的目的。整個(gè) ADMC算法的實(shí)現(xiàn)偽代碼如表 1所示。

ADMC算法中，搜索上界的倍增因子定義為2。當(dāng)系統(tǒng)剛剛建立，或發(fā)生拓?fù)渫蛔儠r(shí)，該值足以確保迭代步長(zhǎng)呈指數(shù)級(jí)增長(zhǎng)，快速適應(yīng)新的網(wǎng)絡(luò)拓?fù)?。?1展現(xiàn)的細(xì)節(jié)顯示，與 DMFSGD算法相同，ADMC算法的計(jì)算復(fù)雜度同樣為，其中n是節(jié)點(diǎn)在構(gòu)造優(yōu)化函數(shù)時(shí)選取的參考節(jié)點(diǎn)數(shù)；m是梯度下降步長(zhǎng)搜索的輪數(shù)。可見ADMC算法的測(cè)量與計(jì)算代價(jià)與網(wǎng)絡(luò)規(guī)模無(wú)關(guān)，同樣適用于海量節(jié)點(diǎn)在線的網(wǎng)絡(luò)應(yīng)用。而相對(duì)于DMFSGD算法，ADMC基于歷史信息的步長(zhǎng)搜索策略通?？梢缘玫捷^小的m，因而其計(jì)算代價(jià)也顯著較低。

表1 ADMC重建算法的偽代碼

3 仿真實(shí)驗(yàn)

為了檢驗(yàn)?zāi)Ｐ偷乃俣?、精度與計(jì)算代價(jià)，本文以DMFSGD算法作為基準(zhǔn)算法與ADMC算法進(jìn)行性能對(duì)比。所有的算法均假定鄰居節(jié)點(diǎn)數(shù)為60個(gè)。實(shí)驗(yàn)以Planetlab數(shù)據(jù)集[20]為仿真基礎(chǔ)，該數(shù)據(jù)集測(cè)量了226個(gè)Planetlab節(jié)點(diǎn)之間4h內(nèi)的傳輸時(shí)延。在所有實(shí)驗(yàn)中，均取重建矩陣的零范數(shù)先驗(yàn)估計(jì)N=5，正則化因子λ=1。

首先定義距離計(jì)算相對(duì)誤差(Relative Error,RE)以評(píng)價(jià)系統(tǒng)性能，定義如式(13)：

與之相關(guān)地，引入相對(duì)誤差的 90%分位數(shù)(Ninetieth Percentile Relative Error, NPRE)作為算法整體性能評(píng)價(jià)指標(biāo)[21]。

3.1 l1損失函數(shù)性能分析

當(dāng)基于 l1損失函數(shù)進(jìn)行矩陣重建時(shí)，取推薦值，可得系統(tǒng)性能如圖1所示。其中，圖1(a)是每一輪迭代中步長(zhǎng)折半查找的次數(shù)，決定了算法的計(jì)算代價(jià)?？梢钥闯?，在系統(tǒng)的初始階段，DMFSGD算法基本無(wú)須折半查找，將搜索上界代入計(jì)算即可生成損失函數(shù)非遞增迭代序列。這表明，由于折中得到的搜索上界并非此時(shí)的最佳步長(zhǎng)。這一現(xiàn)象在圖1(b)和圖1(c)中也得到體現(xiàn)。如圖1(b)所示，以ADMC算法搜索得到的步長(zhǎng)為對(duì)比，當(dāng)?shù)介L(zhǎng)在0.15左右時(shí)，梯度下降算法才能得到相對(duì)令人滿意的收斂速度。圖 1(c)是系統(tǒng)初始階段的NPRE演進(jìn)曲線。得益于步長(zhǎng)的自適應(yīng)搜索策略，ADMC的收斂速度顯然較DMFSGD更快。需要指出的是，由于向量的初始化策略和 l1損失函數(shù)必然導(dǎo)致的誤差截?cái)?，使得在系統(tǒng)的起始階段無(wú)論ADMC抑或DMFSGD都存在一小段“冰凍”時(shí)期。但顯然ADMC的反應(yīng)更為敏捷，也有較高的收斂速度。由圖 1(a)可以看到：隨著時(shí)延矩陣重建算法逐漸收斂到穩(wěn)定的狀態(tài)，DMFSGD算法的計(jì)算代價(jià)隨之升高。每輪迭代中，DMFSGD平均需要搜索6~7次才能查找到恰當(dāng)?shù)牡介L(zhǎng)；反觀本文提出的ADMC算法，每輪迭代中折半查找次數(shù)始終維持在1.95~2.05次之間，計(jì)算代價(jià)較 DMFSGD降低約65%~70%。這一趨勢(shì)在圖1(b)中得到印證：當(dāng)系統(tǒng)趨于穩(wěn)定時(shí)，恰當(dāng)?shù)牡介L(zhǎng)穩(wěn)定在左右，恰好是DMFSGD算法進(jìn)行6~7次折半查找得到的值；而完成同樣的工作ADMC通常僅需兩次折半查找即可。雖然ADMC算法的計(jì)算代價(jià)大幅降低，但計(jì)算性能并未隨之產(chǎn)生下降。圖 1(c)中明顯看出，當(dāng)系統(tǒng)收斂時(shí)，ADMC和DMFSGD算法得到極為相似的NPRE演進(jìn)曲線。深入觀察此時(shí)的矩陣填充相對(duì)誤差累積分布如圖1(d)，可見兩種算法的累積分布曲線幾乎完全重合。由于凸優(yōu)化問(wèn)題僅存在一個(gè)極優(yōu)解暨全局最優(yōu)解，兩種不同的算法收斂到同一個(gè)解是必然的。

3.2 l2損失函數(shù)性能分析

圖1 l1損失函數(shù)算法性能

圖2 l2損失函數(shù)算法性能

當(dāng)以l2損失函數(shù)為評(píng)價(jià)準(zhǔn)則時(shí)，取推薦值，可得系統(tǒng)性能如圖2。不同于l1損失函數(shù)，l2損失函數(shù)的迭代步長(zhǎng)選取須考慮重建誤差的模，因此搜索上界較 l1損失函數(shù)更低，受網(wǎng)絡(luò)抖動(dòng)的影響卻大得多。動(dòng)態(tài)環(huán)境下的步長(zhǎng)平均搜索次數(shù)如圖2(a)所示?？梢钥闯觯軘?shù)據(jù)集內(nèi)蘊(yùn)的拓?fù)浣Y(jié)構(gòu)突變影響，DMFSGD算法的步長(zhǎng)搜索次數(shù)也隨之從4次左右跳變至6~8次；而ADMC的表現(xiàn)則較為魯棒，步長(zhǎng)搜索次數(shù)同樣維持在1.95~2.05次之間，與采用l1損失函數(shù)時(shí)幾乎相同，比DMFSGD平均下降 50%~80%。如圖 2(b)所示，無(wú)論 DMFSGD還是ADMC在歷輪迭代最終選取的步長(zhǎng)極為相似，在兩個(gè)不同的拓?fù)浣Y(jié)構(gòu)下，分別為和，說(shuō)明ADMC在l2損失函數(shù)被引入時(shí)對(duì)迭代步長(zhǎng)的搜索能力也不弱于 DMFSGD。雖然ADMC的計(jì)算代價(jià)明顯低于DMFSGD，重建精度和速度的表現(xiàn)卻不因此而降低：圖2(c)的NPRE演進(jìn)曲線顯示，ADMC可以取得和DMFSGD幾乎相同的收斂速度。可以看出，由于此時(shí)不存在對(duì)誤差的截?cái)?，盡管搜索上界減小了一個(gè)數(shù)量級(jí)，但相對(duì)于 l1損失函數(shù)，l2損失函數(shù)的引入依然顯著提升了DMFSGD和ADMC的收斂速度。值得注意的是，伴隨著收斂速度的提升，矩陣重建的精度卻不能盡如人意。如圖2(d)中的相對(duì)誤差累積分布曲線所示，l2損失函數(shù)作為評(píng)價(jià)準(zhǔn)則時(shí)，矩陣重建的誤差顯著高于 l1損失函數(shù)評(píng)價(jià)準(zhǔn)則?；谇捌诠ぷ鞯难芯浚烧J(rèn)為是由于 l2損失函數(shù)對(duì)于時(shí)延序列中存在的抖動(dòng)現(xiàn)象更加敏感，難以處理隨機(jī)延遲污染所致。

3.3 Huber損失函數(shù)性能分析

Huber損失函數(shù)是l1損失函數(shù)和l2損失函數(shù)的混合。實(shí)驗(yàn)中取。實(shí)驗(yàn)證明， Huber損失函數(shù)的引入能夠兼顧收斂速度和重建精度。如圖3(a)所示，基于 Huber損失函數(shù)作為評(píng)價(jià)準(zhǔn)則，ADMC的計(jì)算代價(jià)同樣遠(yuǎn)遠(yuǎn)低于DMFSGD。從算法運(yùn)行的初始階段開始直到穩(wěn)定階段，ADMC的迭代搜索次數(shù)除最初的數(shù)輪迭代中上升到2.1次左右，一直穩(wěn)定在1.95~2.05次之間，與其它損失函數(shù)被引入時(shí)幾乎沒(méi)有差異。相比之下，DMFSGD的平均步長(zhǎng)搜索次數(shù)從起初的 1次攀升至穩(wěn)定狀態(tài)時(shí)的6.5~6.8次，計(jì)算量遠(yuǎn)遠(yuǎn)高于ADMC。圖3(b)中可以看出，當(dāng)系統(tǒng)處于穩(wěn)定狀態(tài)時(shí)，雖然ADMC僅進(jìn)行少數(shù)幾次迭代，但搜索得到的迭代步長(zhǎng)與DMFSGD仍然十分接近：雖然在起始階段ADMC搜索得到的迭代步長(zhǎng)約為DMFSGD的一倍，但隨著算法的收斂最終ADMC和DMFSGD都將梯度下降算法的迭代步長(zhǎng)穩(wěn)定在區(qū)間內(nèi)，這表明 ADMC提出的步長(zhǎng)搜索策略具備較強(qiáng)的泛化能力，從側(cè)面驗(yàn)證了策略的有效性。圖 3(c)體現(xiàn)了算法的收斂速度?？梢钥闯?，雖然Huber損失函數(shù)同樣進(jìn)行了誤差截?cái)啵諗克俣葏s超過(guò)了采用 l1損失函數(shù)時(shí)的收斂速度。由于算法迭代初值位于原點(diǎn)附近，因此絕大部分計(jì)算誤差都落入 l1損失函數(shù)區(qū)間，于是Huber損失函數(shù)的ε參數(shù)在此起到了步長(zhǎng)放大的作用，提升了收斂速度；而當(dāng)算法趨于穩(wěn)定時(shí)，相當(dāng)部分的計(jì)算誤差則落入l2損失函數(shù)區(qū)間，此時(shí)Huber損失函數(shù)截?cái)嗔孙@著異常的計(jì)算誤差，從而有效過(guò)濾了時(shí)延毛刺所造成的延遲污染，達(dá)到較好的重建精度。而從圖3(d)中可以看出，此時(shí)矩陣重建的誤差與 l1損失函數(shù)不相上下，顯著優(yōu)于 l2損失函數(shù)。由以上實(shí)驗(yàn)可得，Huber損失函數(shù)的引入能夠兼顧收斂速度和異常數(shù)據(jù)處理能力，具備優(yōu)良的特性。

圖3 Huber損失函數(shù)算法性能

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

時(shí)延敏感型應(yīng)用的優(yōu)化強(qiáng)烈依賴于時(shí)延矩陣的感知與重建。不同于傳統(tǒng)的分布式時(shí)延矩陣重建算法，本文在關(guān)注矩陣重建精度的同時(shí)，著重考慮了算法的計(jì)算代價(jià)和泛化能力，以確保實(shí)時(shí)性和特殊環(huán)境下的算法性能。由此，本文試圖提出一種支持多種誤差評(píng)價(jià)準(zhǔn)則的時(shí)延矩陣重建算法：通過(guò)伸縮因子的引入來(lái)實(shí)現(xiàn)步長(zhǎng)搜索上界的自適應(yīng)升降，在滿足不同評(píng)價(jià)準(zhǔn)則和生命周期不同階段下，梯度下降步長(zhǎng)快速搜索的同時(shí)，以指數(shù)級(jí)的伸縮速率實(shí)現(xiàn)了對(duì)拓?fù)渫蛔兊拿艚葸m應(yīng)。進(jìn)一步地，本文引入了多種誤差損失函數(shù)，在不損失計(jì)算精度的前提下，以較低的計(jì)算代價(jià)提升了模型的泛化能力。

[1] Szymaniak M, Presotto D, Pierre G, et al.. Practical largescale latency estimation[J]. Computer Networks, 2008, 52(7):1343-1364.

[2] Agarwal S and Lorch R. Matchmaking for online games and other latency-sensitive P2P systems[C]. Proceedings of the ACM SIGCOMM 2009, Barcelona, 2009: 315-326.

[3] Armitage G and Heyde A. REED: optimizing first person shooter game server discovery using network coordinates[J].ACM Transactions on Multimedia Computing,Communications, and Applications, 2012, DOI:10.1145/21268996. 2169000.

[4] Agarwal S, Dunagan J, Jain N, et al.. Volley: automated data placement for geo-distributed cloud services[C]. Proceedings of the 7th USENIX Symposium on Networked Systems Design ＆amp; Implementation (NSDI), San Jose, 2010: 1-16.

[5] Ding C, Chen Y, Xu T, et al.. CloudGPS: a scalable and ISP-friendly server selection scheme in cloud computing environments[C]. Proceedings on the 20th International Workshop on Quality of Service (IWQoS), Coimbra, 2012: 5.

[6] 王占豐, 陳鳴, 邢長(zhǎng)友, 等. 因特網(wǎng)時(shí)延空間建模的研究[J].通信學(xué)報(bào), 2012, 33(7): 164-176.Wang Zhan-feng, Chen Ming, Xing Chang-you, et al..Research on the modeling of the Internet delay space[J].Journal on Communications, 2012, 33(7): 164-176.

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

[8] Candès E J and Plan Y. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[J]. IEEE Transactions on Information Theory,2011, 57(4): 2342-2359.

[9] Candès E J and Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics,2009, 9(6): 717-772.

[10] Mao Y, Saul L K, and Smith J M. IDES: an internet distance estimation service for large networks[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(12): 2273-2284.

[11] Wang Z F, Chen M, Xing C, et al.. Multi-manifold model of the Internet delay space[J]. Journal of Network and Computer Applications, 2013, 31(1): 211-218.

[12] Zhang R, Tang C, Hu Y C, et al.. Impact of the inaccuracy of distance prediction algorithms on Internet applications-an analytical and comparative study[C]. Proceedings on 25th IEEE INFOCOM, Barcelona, 2006: 1-12.

[13] Liao Y, Geurts P, and Leduc G. Network distance prediction based on decentralized matrix factorization[C]. Proceedings on the 9th International IFIP TC6 Networking Conference,Chennai, 2010: 15-26.

[14] Chen Y, Wang X, Shi C, et al.. Phoenix: a weight-based network coordinate system using matrix factorization[J].IEEE Transactions on Network and Service Management,2011, 8(4): 334-347.

[15] Tang L, Shen Z, Lin Q, et al.. Towards a robust framework of network coordinate systems[C]. Proceedings on the 9th International IFIP TC6 Networking Conference, Prague,2012: 331-343.

[16] Liao Y, Du W, Geurts P, et al.. DMFSGD: a decentralized matrix factorization algorithm for network distance prediction[J]. IEEE/ACM Transactions on Networking, 2013,21(5): 1511-1524.

[17] 史加榮, 焦李成, 尚凡華. 不完全非負(fù)矩陣分解的加速算法[J].電子學(xué)報(bào), 2011, 39(2): 291-295.Shi Jia-rong, Jiao Li-cheng, and Shang Fan-hua. Accelerated algorithm to incomplete nonnegative matrix dactorization[J].Acta Electronica Sinica, 2011, 39(2): 291-295.

[18] 張振躍, 趙科科. 數(shù)據(jù)缺損矩陣低秩分解的正則化方法[J]. 中國(guó)科學(xué): 數(shù)學(xué), 2013, 43(3): 249-271.Zhang Zhen-yue and Zhao Ke-ke. Regularization methods for low-rank factorization of matrices with missing data[J].SCIENTIA SINICA Mathematica, 2013, 43(3): 249-271.

[19] 胡毓達(dá). 凸分析與非光滑分析[M]. 上海: 上?？茖W(xué)技術(shù)出版社, 2000: 52.

[20] PlanetLabDataset[OL]. http://www.eecs.harvard.edu/~syrah /nc/sim/pings.4hr.stamp.gz. 2012.5.

[21] Wu S, Chen Y, Fu X, et al.. NCShield: securing decentralized,matrix factorization-based network coordinate systems[C].Proceedings on the 20th International Workshop on Quality of Service (IWQoS), Coimbra, 2012: 1.