Abstract
Network proximity and latency estimation is an important component in discovering and locating services and applications. With the growing number of services and service providers in the large-scale Internet, accurately estimating network proximity/latency with minimal probing overhead becomes essential for scalable deployment. Although there exist a number of network distance estimation schemes, they either rely on extensive infrastructure support, require the IP address of the potential targets, falsely cluster distant nodes, or perform poorly with even few measurement errors. We propose Netvigator, a scalable network proximity and latency estimation tool that uses information obtained from probing a small number of landmark nodes and intermediate routers (termed milestones) that are discovered en route to the landmarks, to identify the closest nodes. With very little additional probing overhead, Netvigator uses distance information to the milestones to accurately locate the closest nodes. We developed a Netvigator prototype and report our performance evaluation on PlanetLab and in the intranet of a large enterprise. Netvigator is a running service on PlanetLab as a part of HP Labs' S3 (Scalable Sensing Service).
- S. Banerjee, M. Pias, and T. Griffin. The interdomain connectivity of planetlab nodes. In Proceedings of the PAM 2004.Google ScholarCross Ref
- Chariot, http://www.netiq.com/products/chr/default.asp.Google Scholar
- Y. Chen, K. H. Lim, R. H. Katz, and C. Overton. On the stability of network distance estimation. ACM Performance Evaluation Review, 30(2):21--30, September 2002. Google ScholarDigital Library
- M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical internet coordinates for distance estimation. In Proceedings of the IEEE ICDCS 2004. Google ScholarDigital Library
- F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM 2004. Google ScholarDigital Library
- R. Fonseca, P. Sharma, S. Banerjee, S.-J. Lee, and S. Basu. Distributed querying of internet distance information. In Proceedings of the 8th IEEE Global Internet Symposium, Miami, FL, March 2005.Google ScholarCross Ref
- P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. IDMaps: A global internet host distance estimation service. IEEE/ACM Trans. Networking, 9(5):525--540, October 2001. Google ScholarDigital Library
- K. P. Gummadi, S. Saroiu, and S. D. Gribble. King: Estimating latency between arbitrary internet end hosts. In Proceedings of the ACM IMW 2002. Google ScholarDigital Library
- J. Ledlie, P. Pietzuch, and M. Seltzer. Stable and accurate network coordinates. In Proceedings of the IEEE ICDCS 2006. Google ScholarDigital Library
- H. Lim, J. C. Hou, and C.-H. Choi. Constructing internet coordinate system based on delay measurement. In Proceedings of the ACM IMC 2003. Google ScholarDigital Library
- T. S. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of the IEEE INFOCOM 2002.Google ScholarCross Ref
- T. S. E. Ng and H. Zhang. A network positioning system for the internet. In Proceedings of USENIX Annual Technical Conference, Boston, MA, June 2004. Google ScholarDigital Library
- M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for scalable distributed location. In Proceedings of the IPTPS 2003.Google ScholarCross Ref
- PlanetLab, http://www.planet-lab.org.Google Scholar
- S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically-aware overlay construction and server selection. In Proceedings of the IEEE INFOCOM, New York, NY, June 2002.Google ScholarCross Ref
- s3 scalable sensing service, http://networking.hpl.hp.com/s-cube/PL.Google Scholar
- Scriptroute, http://www.cs.washington.edu/research/networking/scriptroute.Google Scholar
- Y. Shavitt, X. Sun, A. Wool, and B. Yener. Computing the unmeasured: An algebraic approach to internet mapping. IEEE J. Select. Areas Commun., 22(1):67--78, January 2004. Google ScholarDigital Library
- Y. Shavitt and T. Tankel. Big-bang simulation for embedding network distance in euclidean space. In Proceedings of the IEEE INFOCOM 2003.Google ScholarCross Ref
- S. Srinivasan and E. Zegura. M-coop: A scalable infrastructure for network measurement. In Proceedings of the IEEE WIAPP 2003. Google ScholarDigital Library
- C. Tang, Z. Xu, and S. Dwarkadas. Peer-to-peer information retrieval using self-organizing semantic overlay networks. In Proceedings of the ACM SIGCOMM, Karlsruhe, Germany, August 2003. Google ScholarDigital Library
- L. Tang and M. Crovella. Virtual landmarks for the internet. In Proceedings of the ACM IMC, Miami Beach, FL, October 2003. Google ScholarDigital Library
- W. Theilmann and K. Rothermel. Dynamic distance maps of the Internet. In Proceedings of the IEEE INFOCOM 2000.Google ScholarCross Ref
- L. w. Lehman and S. Lerman. PCoord: Network position estimation using peer-to-peer measurements. In Proceedings of the IEEE NCA 2004. Google ScholarDigital Library
- M. Waldvogel and R. Rinaldi. Efficient topology-aware overlay network. In Proceedings of the ACM HotNets-I.Google Scholar
- B. Wong, A. Slivkins, and E. Sirer. Meridian: A lightweight network location service without virtual coordinates. In Proceedings of the ACM SIGCOMM, Philadelphia, PA, August 2005. Google ScholarDigital Library
- Z. Xu, P. Sharma, S.-J. Lee, and S. Banerjee. Netvigator: Scalable network proximity estimation. Technical Report HPL-2004-28R1, HP Laboratories, March 2005.Google Scholar
- H. Zheng, E. K. Lua, M. Pias, and T. Griffin. Internet routing policies and round-trip-times. In Proceedings of the PAM 2005. Google ScholarDigital Library
Index Terms
- Estimating network proximity and latency
Recommendations
Network distance estimation with dynamic landmark triangles
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsThis paper describes an efficient and accurate approach to estimate the network distance between arbitrary Internet hosts. We use three landmark hosts forming a triangle in two-dimensional space to estimate the distance between arbitrary hosts with ...
Network distance estimation with dynamic landmark triangles
SIGMETRICS '08This paper describes an efficient and accurate approach to estimate the network distance between arbitrary Internet hosts. We use three landmark hosts forming a triangle in two-dimensional space to estimate the distance between arbitrary hosts with ...
Estimation of network distances using off-line measurements
Several emerging large-scale Internet applications such as Content Distribution Networks, and Peer-to-Peer networks could potentially benefit from knowing the underlying Internet topology and the distances (i.e., round-trip-time) between different ...
Comments