Reference : DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/135818
DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
English
Liao, Yongjun [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques >]
Du, Wei [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques > >]
Geurts, Pierre [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation > >]
Leduc, Guy mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques >]
11-Oct-2013
IEEE/ACM Transactions on Networking
Institute of Electrical and Electronics Engineers
21
5
1511-1524
Yes (verified by ORBi)
International
1063-6692
1558-2566
New York
NY
[en] network distance prediction ; matrix completion ; matrix factorization ; stochastic gradient descent
[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.
Researchers ; Professionals
http://hdl.handle.net/2268/135818
10.1109/TNET.2012.2228881
Published electronically by the journal on December 13, 2012.
FP7 ; 223936 - ECODE - Experimental COgnitive Distributed Engine

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
dmf_journal_ton_final_author.pdfAuthor preprint922.19 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.