[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
measurement methodology.
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.
Disciplines :
Computer science
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
Language :
English
Title :
Rating Network Paths for Locality-Aware Overlay Construction and Routing
Publication date :
October 2015
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 :
23
Issue :
5
Pages :
1661-1673
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.
E. J. Candès and Y. Plan, "Matrix completion with noise," Proc. IEEE, vol. 98, no. 6, pp. 925-936, Jun. 2010.
V. K. Adhikari, S. Jain, Y. Chen, and Z.-L. Zhang, "Vivisecting YouTube: An active measurement study," in Proc. IEEE INFOCOM, 2012, pp. 2521-2525.
B. Wong, A. Slivkins, and E. Sirer, "Meridian: A lightweight network location service without virtual coordinates," in Proc. ACM SIGCOMM, Philadelphia, PA, USA, Aug. 2005, pp. 85-96.
G. Takács, I. Pilászy, B. Németh, and D. Tikk, "Scalable collaborative filtering approaches for large recommender systems," J. Mach. Learning Res., vol. 10, pp. 623-656, Jun. 2009.
J. D. M. Rennie and N. Srebro, "Fast maximum margin matrix factorization for collaborative prediction," in Proc. Int. Conf. Mach. Learning, 2005, pp. 713-719.
D. D. Lee and H. S. Seung, "Algorithms for non-negative matrix factorization," in Proc. Adv. Neural Inf. Process. Syst., Vancouver, BC, Canada, 2001, pp. 556-562.
T. G. Dietterich, "Ensemble learning," in The Handbook of Brain Theory and Neural Networks. Cambridge, MA, USA: MIT Press, 2002.
M. Wu, "Collaborative filtering via ensembles of matrix factorizations," in Proc. KDD Cup & Workshop 13th ACM SIGKDD, 2007.
J. Surowiecki, TheWisdom of Crowds. New York, NY, USA: Anchor, 2005.
J. Ledlie, P. Gardner, and M. I. Seltzer, "Network coordinates in the wild," in Proc. USENIX Symp. Netw. Syst. Design Implementation, Apr. 2007, pp. 22-35.
B. Settles, "Active learning literature survey," University of Wisconsin-Madison, Madison, WI, USA, Tech. Rep. 1648, 2010.
