一種網絡時延矩陣分布式自適應重建算法

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

(電子科技大學計算機科學與工程學院 成都 611731)

1 引言

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

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

本文提出一種支持多種誤差評價準則的時延矩陣重建ADMC算法。通過引入伸縮因子實現對不同誤差評價準則和生命周期不同階段下梯度下降步長的自適應搜索，在不損失計算精度的前提下，以較低的計算代價提升模型的泛化能力。

2 時延矩陣分布式重建的自適應迭代算法

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

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

于是,ijd可用的對應元素,ijd?擬合：

由于U或V行向量之間的不存在交集元素，這使其易分布于全網共同進行維護：令任一節點i持有U和V中對應的行向量iu和iv，則節點只需獲得目標節點持有的向量，便可計算與對方的近似時延，從而大大減少了網絡測量帶來的資源開銷。對應地，式(1)可分解為如式(4)兩個耦合子問題的聯立：

當取l1損失函數作為誤差評價準則時，有

此時，有

當取l2損失函數作為誤差評價準則時，有

此時，有

當取Huber損失函數作為誤差評價準則時，有

此時，有

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

ADMC算法中，搜索上界的倍增因子定義為2。當系統剛剛建立，或發生拓撲突變時，該值足以確保迭代步長呈指數級增長，快速適應新的網絡拓撲。表 1展現的細節顯示，與 DMFSGD算法相同，ADMC算法的計算復雜度同樣為，其中n是節點在構造優化函數時選取的參考節點數；m是梯度下降步長搜索的輪數。可見ADMC算法的測量與計算代價與網絡規模無關，同樣適用于海量節點在線的網絡應用。而相對于DMFSGD算法，ADMC基于歷史信息的步長搜索策略通常可以得到較小的m，因而其計算代價也顯著較低。

表1 ADMC重建算法的偽代碼

3 仿真實驗

為了檢驗模型的速度、精度與計算代價，本文以DMFSGD算法作為基準算法與ADMC算法進行性能對比。所有的算法均假定鄰居節點數為60個。實驗以Planetlab數據集[20]為仿真基礎，該數據集測量了226個Planetlab節點之間4h內的傳輸時延。在所有實驗中，均取重建矩陣的零范數先驗估計N=5，正則化因子λ=1。

首先定義距離計算相對誤差(Relative Error,RE)以評價系統性能，定義如式(13)：

與之相關地，引入相對誤差的 90%分位數(Ninetieth Percentile Relative Error, NPRE)作為算法整體性能評價指標[21]。

3.1 l1損失函數性能分析

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

3.2 l2損失函數性能分析

圖1 l1損失函數算法性能

圖2 l2損失函數算法性能

當以l2損失函數為評價準則時，取推薦值，可得系統性能如圖2。不同于l1損失函數，l2損失函數的迭代步長選取須考慮重建誤差的模，因此搜索上界較 l1損失函數更低，受網絡抖動的影響卻大得多。動態環境下的步長平均搜索次數如圖2(a)所示。可以看出，受數據集內蘊的拓撲結構突變影響，DMFSGD算法的步長搜索次數也隨之從4次左右跳變至6~8次；而ADMC的表現則較為魯棒，步長搜索次數同樣維持在1.95~2.05次之間，與采用l1損失函數時幾乎相同，比DMFSGD平均下降 50%~80%。如圖 2(b)所示，無論 DMFSGD還是ADMC在歷輪迭代最終選取的步長極為相似，在兩個不同的拓撲結構下，分別為和，說明ADMC在l2損失函數被引入時對迭代步長的搜索能力也不弱于 DMFSGD。雖然ADMC的計算代價明顯低于DMFSGD，重建精度和速度的表現卻不因此而降低：圖2(c)的NPRE演進曲線顯示，ADMC可以取得和DMFSGD幾乎相同的收斂速度。可以看出，由于此時不存在對誤差的截斷，盡管搜索上界減小了一個數量級，但相對于 l1損失函數，l2損失函數的引入依然顯著提升了DMFSGD和ADMC的收斂速度。值得注意的是，伴隨著收斂速度的提升，矩陣重建的精度卻不能盡如人意。如圖2(d)中的相對誤差累積分布曲線所示，l2損失函數作為評價準則時，矩陣重建的誤差顯著高于 l1損失函數評價準則。基于前期工作的研究，可認為是由于 l2損失函數對于時延序列中存在的抖動現象更加敏感，難以處理隨機延遲污染所致。

3.3 Huber損失函數性能分析

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

圖3 Huber損失函數算法性能

4 結束語

時延敏感型應用的優化強烈依賴于時延矩陣的感知與重建。不同于傳統的分布式時延矩陣重建算法，本文在關注矩陣重建精度的同時，著重考慮了算法的計算代價和泛化能力，以確保實時性和特殊環境下的算法性能。由此，本文試圖提出一種支持多種誤差評價準則的時延矩陣重建算法：通過伸縮因子的引入來實現步長搜索上界的自適應升降，在滿足不同評價準則和生命周期不同階段下，梯度下降步長快速搜索的同時，以指數級的伸縮速率實現了對拓撲突變的敏捷適應。進一步地，本文引入了多種誤差損失函數，在不損失計算精度的前提下，以較低的計算代價提升了模型的泛化能力。

[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] 王占豐, 陳鳴, 邢長友, 等. 因特網時延空間建模的研究[J].通信學報, 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] 史加榮, 焦李成, 尚凡華. 不完全非負矩陣分解的加速算法[J].電子學報, 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] 張振躍, 趙科科. 數據缺損矩陣低秩分解的正則化方法[J]. 中國科學: 數學, 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] 胡毓達. 凸分析與非光滑分析[M]. 上海: 上海科學技術出版社, 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.