2015 • In

Peer Reviewed verified by ORBi

All documents in ORBi are protected by a user license.

copy to clipboard copied

Keywords :

rating-based network measurement; recommender system; matrix factorization; network inference

Abstract :

[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

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

Funders :

CE - Commission Européenne

Scopus citations^{®}

7

Scopus citations^{®}

without self-citations

without self-citations

6

OpenCitations

7

- 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.
- "Vuze Bittorrent," [Online]. Available: http://www.vuze.com/
- 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.
- "Gnutella," [Online]. Available: http://www.gnu.org/philosophy/gnutella.html
- 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.
- "Google TV," [Online]. Available: http://www.google.com/tv/
- 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.
- "Netflix Prize," 2009 [Online]. Available: http://www.netflixprize. com/
- 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.