Estimating network proximity and latency

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' S³ (Scalable Sensing Service).

References

1. S. Banerjee, M. Pias, and T. Griffin. The interdomain connectivity of planetlab nodes. In Proceedings of the PAM 2004.
2. Chariot, http://www.netiq.com/products/chr/default.asp.
3. 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.
4. M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical internet coordinates for distance estimation. In Proceedings of the IEEE ICDCS 2004.
5. F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM 2004.
6. 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.
7. 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.
8. K. P. Gummadi, S. Saroiu, and S. D. Gribble. King: Estimating latency between arbitrary internet end hosts. In Proceedings of the ACM IMW 2002.
9. J. Ledlie, P. Pietzuch, and M. Seltzer. Stable and accurate network coordinates. In Proceedings of the IEEE ICDCS 2006.
10. H. Lim, J. C. Hou, and C.-H. Choi. Constructing internet coordinate system based on delay measurement. In Proceedings of the ACM IMC 2003.
11. T. S. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of the IEEE INFOCOM 2002.
12. 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.
13. M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for scalable distributed location. In Proceedings of the IPTPS 2003.
14. PlanetLab, http://www.planet-lab.org.
15. 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.
16. s3 scalable sensing service, http://networking.hpl.hp.com/s-cube/PL.
17. Scriptroute, http://www.cs.washington.edu/research/networking/scriptroute.
18. 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.
19. Y. Shavitt and T. Tankel. Big-bang simulation for embedding network distance in euclidean space. In Proceedings of the IEEE INFOCOM 2003.
20. S. Srinivasan and E. Zegura. M-coop: A scalable infrastructure for network measurement. In Proceedings of the IEEE WIAPP 2003.
21. 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.
22. L. Tang and M. Crovella. Virtual landmarks for the internet. In Proceedings of the ACM IMC, Miami Beach, FL, October 2003.
23. W. Theilmann and K. Rothermel. Dynamic distance maps of the Internet. In Proceedings of the IEEE INFOCOM 2000.
24. L. w. Lehman and S. Lerman. PCoord: Network position estimation using peer-to-peer measurements. In Proceedings of the IEEE NCA 2004.
25. M. Waldvogel and R. Rinaldi. Efficient topology-aware overlay network. In Proceedings of the ACM HotNets-I.
26. 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.
27. Z. Xu, P. Sharma, S.-J. Lee, and S. Banerjee. Netvigator: Scalable network proximity estimation. Technical Report HPL-2004-28R1, HP Laboratories, March 2005.
28. H. Zheng, E. K. Lua, M. Pias, and T. Griffin. Internet routing policies and round-trip-times. In Proceedings of the PAM 2005.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Networks

  • Network architectures

  • Network protocols

    • Transport protocols

  • Network services

    • Network monitoring

  • Network types

    • Public Internet