Other (Reports)
DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
Liao, Yongjun; Du, Wei; Geurts, Pierre et al.
2012
 

Files


Full Text
DMFSGD-arXiv1201.1174v1.pdf
Author preprint (1.02 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[en] The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a few pairs and to predict the other ones without actually measuring them. This paper formulates the distance prediction problem as matrix completion where unknown entries of an incomplete matrix of pairwise distances are to be predicted. The problem is solvable because strong correlations among network distances exist and cause the constructed distance matrix to be low rank. The new formulation circumvents the well-known drawbacks of existing approaches based on Euclidean embedding. A new algorithm, so-called Decentralized Matrix Factorization by Stochastic Gradient Descent (DMFSGD), is proposed to solve the network distance prediction problem. By letting network nodes exchange messages with each other, the algorithm is fully decentralized and only requires each node to collect and to process local measurements, with neither explicit matrix constructions nor special nodes such as landmarks and central servers. In addition, we compared comprehensively matrix factorization and Euclidean embedding to demonstrate the suitability of the former on network distance prediction. We further studied the incorporation of a robust loss function and of non-negativity constraints. Extensive experiments on various publicly-available datasets of network delays show not only the scalability and the accuracy of our approach but also its usability in real Internet applications.
Disciplines :
Computer science
Author, co-author :
Liao, Yongjun ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Du, Wei;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Geurts, Pierre ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Leduc, Guy ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Language :
English
Title :
DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
Publication date :
05 January 2012
Report number :
arXiv:1201.1174
Collection name :
arXiv.org/cs
European Projects :
FP7 - 223936 - ECODE - Experimental COgnitive Distributed Engine
Funders :
CE - Commission Européenne [BE]
Available on ORBi :
since 28 December 2012

Statistics


Number of views
78 (4 by ULiège)
Number of downloads
126 (1 by ULiège)

Bibliography


Similar publications



Contact ORBi