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

| ||||||||||||||

All documents in ORBi are protected by a user license.