[en] This paper investigates the rating of network paths,
i.e. acquiring quantized measures of path properties such as
round-trip time and available bandwidth. Comparing to finegrained
measurements, coarse-grained ratings are appealing in
that they are not only informative but also cheap to obtain.
Motivated by this insight, we firstly address the scalable
acquisition of path ratings by statistical inference. By observing
similarities to recommender systems, we examine the applicability
of solutions to recommender system and show that our
inference problem can be solved by a class of matrix factorization
techniques. A technical contribution is an active and progressive
inference framework that not only improves the accuracy by
selectively measuring more informative paths but also speeds
up the convergence for available bandwidth by incorporating its
Then, we investigate the usability of rating-based network
measurement and inference in applications. A case study is
performed on whether locality awareness can be achieved for
overlay networks of Pastry and BitTorrent using inferred ratings.
We show that such coarse-grained knowledge can improve the
performance of peer selection and that finer granularities do not
always lead to larger improvements.
Author, co-author :
Du, Wei; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Liao, Yongjun ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Tao, Narisu; University of Göttingen > Computer Networks
Geurts, Pierre ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Algorith. des syst. en interaction avec le monde physique
Fu, Xiaoming; University of Göttingen > Computer Networks
Leduc, Guy ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Rating Network Paths for Locality-Aware Overlay Construction and Routing
Publication date :
Journal title :
IEEE/ACM Transactions on Networking
Institute of Electrical and Electronics Engineers, New York, United States - New York
Peer reviewed :
Peer Reviewed verified by ORBi
European Projects :
FP7 - 318627 - MPLANE - mPlane – an Intelligent Measurement Plane for Future Network and Application Management
M. Crovella and B. Krishnamurthy, Internet Measurement: Infrastructure, Traffic and Applications. New York, NY, USA: Wiley, 2006.
E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, "A survey and comparison of peer-to-peer overlay network schemes," IEEE Commun. Surveys Tuts., vol. 7, no. 2, pp. 72-93, 2nd Quart., 2005.
E. Marocco, A. Fusco, I. Rimac, and V. Gurbani, "Improving peer selection in peer-to-peer applications: Myths vs. reality," Internet Research Task Force Working Group, Dec. 2012 [Online]. Available: http://tools.ietf.org/html/rfc6821
T. S. E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," in Proc. IEEE INFOCOM, 2002, pp. 170-179.
F. Dabek, R. Cox, F. Kaashoek, and R. Morris, "Vivaldi: A decentralized network coordinate system," in Proc. ACM SIGCOMM, Portland, OR, USA, Aug. 2004, pp. 15-26.
Y. Chen, D. Bindel, H. Song, and R. H. Katz, "An algebraic approach to practical and scalable overlay network monitoring," Comput. Commun. Rev., vol. 34, no. 4, pp. 55-66, Aug. 2004.
D. B. Chua, E. D. Kolaczyk, and M. Crovella, "Network kriging," IEEE J. Sel. Areas Commun., vol. 24, no. 12, pp. 2263-2272, Dec. 2006.
H. H. Song, L. Qiu, and Y. Zhang, "NetQuest: A flexible framework for large-scale network measurement," in Proc. ACM SIGMETRICS, 2006.
Y. Mao, L. Saul, and J. M. Smith, "IDES: An Internet distance estimation service for large networks," IEEE J. Sel. Areas Commun., vol. 24, no. 12, pp. 2273-2284, Dec. 2006.
Y. Liao, W. Du, P. Geurts, and G. Leduc, "Decentralized prediction of end-to-end network performance classes," in Proc. CoNEXT, Tokyo, Japan, Dec. 2011, Art. no. 14.
Y. Liao, P. Geurts, and G. Leduc, "Network distance prediction based on decentralized matrix factorization," in Proc. IFIP Netw. Conf., Chennai, India, May 2010, pp. 15-26.
Y. Liao, W. Du, P. Geurts, and G. Leduc, "DMFSGD: A decentralized matrix factorization algorithm for network distance prediction," IEEE/ACM Trans. Netw., vol. 21, no. 5, pp. 1511-1524, Oct. 2013.
Y. Koren, R. Bell, and C. Volinsky, "Matrix factorization techniques for recommender systems," Computer, vol. 42, no. 8, pp. 30-37, 2009.
M. Jain and C. Dovrolis, "End-to-end available bandwidth: Measurement methodology, dynamics, and relation with TCP throughput," IEEE/ACM Trans. Netw., vol. 11, pp. 537-549, Aug. 2003.
V. J. Ribeiro, R. H. Riedi, R. G. Baraniuk, J. Navratil, and L. Cottrell, "Pathchirp: Efficient available bandwidth estimation for network paths," in Proc. Passive Active Meas., 2003.
A. Rowstron and P. Drusche, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems," in Proc. IFIP/ACM ICDSP (Middleware), 2001, pp. 329-350.
L. Tang and M. Crovella, "Virtual landmarks for the Internet," in Proc. ACM/SIGCOMM Internet Meas. Conf., Miami, FL, USA, Oct. 2003, pp. 143-152.
G. Gürsun, N. Ruchansky, E. Terzi, and M. Crovella, "Inferring visibility: Who's (not) talking to whom?," in Proc. ACM SIGCOMM, 2012, pp. 151-162.
G. Gürsun and M. Crovella, "On traffic matrix completion in the internet," in Proc. ACM/SIGCOMM Internet Meas. Conf., 2012, pp. 399-412.
M. Roughan, Y. Zhang, W. Willinger, and L. Qiu, "Spatio-temporal compressive sensing and internet traffic matrices," IEEE/ACM Trans. Netw., vol. 20, no. 3, pp. 662-676, Jun. 2012.
P. Maymounkov and D. Mazières, "Kademlia: A peer-to-peer information system based on the xor metric," in Proc. IPTPS, 2002, pp. 53-65.
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applications," in Proc. ACM SIGCOMM, 2001, pp. 149-160.
I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, "Freenet: A distributed anonymous information storage and retrieval system," in Proc. Int. Workshop Designing Privacy Enhancing Technol., Design Issues Anonymity Unobservability, 2001, pp. 46-66.
D. R. Choffnes and F. E. Bustamante, "Taming the torrent: A practical approach to reducing cross-ISP traffic in peer-to-peer systems," in Proc. ACM SIGCOMM, 2008, pp. 363-374.
H. Xie, Y. R. Yang, A. Krishnamurthy, Y. G. Liu, and A. Silberschatz, "P4P: Provider portal for applications," in Proc. ACM SIGCOMM, 2008, pp. 351-362.
A. Shriram et al., "Comparison of public end-to-end bandwidth estimation tools on high-speed links," in Proc. Passive Active Meas., 2005, pp. 306-320.
M. Jain and C. Dovrolis, "Ten fallacies and pitfalls on end-to-end available bandwidth estimation," in Proc. ACM/SIGCOMM Internet Meas. Conf., 2004, pp. 272-277.
J. Sommers, P. Barford, and W. Willinger, "Laboratory-based calibration of available bandwidth estimation tools," Microprocess. Microsyst., vol. 31, no. 4, pp. 222-235, Jun. 2007.
P. Yalagandula, P. Sharma, S. Banerjee, S. Basu, and S.-J. Lee, "S3: A scalable sensing service for monitoring large networked systems," in Proc. SIGCOMM Workshop Internet Netw. Manage., 2006, pp. 71-76.