Article (Scientific journals)
DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
Liao, Yongjun; Du, Wei; Geurts, Pierre et al.
2013In IEEE/ACM Transactions on Networking, 21 (5), p. 1511-1524
Peer Reviewed verified by ORBi
 

Files


Full Text
dmf_journal_ton_final_author.pdf
Author preprint (944.32 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
network distance prediction; matrix completion; matrix factorization; stochastic gradient descent
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 prediction problem as matrix completion where the unknown entries in a pairwise distance matrix constructed from a network are to be predicted. By assuming that the distance matrix has a low-rank characteristics, the problem is solvable by lowrank approximation based on matrix factorization. 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. 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 :
11 October 2013
Journal title :
IEEE/ACM Transactions on Networking
ISSN :
1063-6692
eISSN :
1558-2566
Publisher :
Institute of Electrical and Electronics Engineers, New York, United States - New York
Volume :
21
Issue :
5
Pages :
1511-1524
Peer reviewed :
Peer Reviewed verified by ORBi
European Projects :
FP7 - 223936 - ECODE - Experimental COgnitive Distributed Engine
Funders :
CE - Commission Européenne [BE]
Commentary :
Published electronically by the journal on December 13, 2012.
Available on ORBi :
since 05 December 2012

Statistics


Number of views
280 (35 by ULiège)
Number of downloads
232 (12 by ULiège)

Scopus citations®
 
69
Scopus citations®
without self-citations
67
OpenCitations
 
52

Bibliography


Similar publications



Contact ORBi