Practical, distributed network coordinates

ABSTRACT

Vivaldi is a distributed algorithm that assigns synthetic coordinates to internet hosts, so that the Euclidean distance between two hosts' coordinates predicts the network latency between them. Each node in Vivaldi computes its coordinates by simulating its position in a network of physical springs. Vivaldi is both distributed and efficient: no fixed infrastructure need be deployed and a new host can compute useful coordinates after collecting latency information from only a few other hosts. Vivaldi can rely on piggy-backing latency information on application traffic instead of generating extra traffic by sending its own probe packets.This paper evaluates Vivaldi through simulations of 750 hosts, with a matrix of inter-host latencies derived from measurements between 750 real Internet hosts. Vivaldi finds synthetic coordinates that predict the measured latencies with a median relative error of 14 percent. The simulations show that a new host joining an existing Vivaldi system requires fewer than 10 probes to achieve this accuracy. Vivaldi is currently used by the Chord distributed hash table to perform proximity routing, replica selection, and retransmission timer estimation.

REFERENCES

• 1: Planetlab. www.planet-lab.org.
• 2: BitTorrent. http://bitconjurer.org/BitTorrent/protocol.html.
• 3: Miguel Castro, Peter Druschel, Y. C. Hu, and Antony Rowstron. Exploiting network proximity in peer-to-peer overlay networks. Technical Report MSR-TR-2002-82, Microsoft Research, June 2002.
• 4: Russ Cox and Frank Dabek. Learning Euclidean coordinates for Internet hosts. www.pdos.lcs.mit.edu/~rsc/6867.pdf, December 2002.
• 5: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: Paul Francis , Sugih Jamin , Cheng Jin , Yixin Jin , Danny Raz , Yuval Shavitt , Lixia Zhang, IDMaps: a global internet host distance estimation service, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.525-540, October 2001 [doi>10.1109/90.958323]
• 7: Thomer Gil, Jinyang Li, Frans Kaashoek, and Robert Morris. Peer-to-peer simulator, 2003. Source available at: cvs.pdos.lcs.mit.edu.
• 8: Krishna P. Gummadi , Stefan Saroiu , Steven D. Gribble, King: estimating latency between arbitrary internet end hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637203]
• 9: Hugues Hoppe, Surface reconstruction from unorganized points, University of Washington, Seattle, WA, 1995
• 10: KaZaA media dekstop. http://www.kazaa.com/.
• 11: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 12: P. Mockapetris , K. J. Dunlap, Development of the domain name system, Symposium proceedings on Communications architectures and protocols, p.123-133, August 16-18, 1988, Stanford, California, United States
• 13: Eugene Ng. Gnp software, 2003. Source available at: http://www-2.cs.cmu.edu/~eugeneng/research/gnp/software.html.
• 14: T. S. Eugene Ng and Hui Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of IEEE Infocom 2002, 2002.
• 15: Marcelo Pias, Jon Crowcroft, Steve Wilbur, Tim Harris, and Salem Bhatti. Lighthouses for scalable distributed location. In IPTPS, 2003.
• 16: N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller. Anchor-free distributed localization in sensor networks. Technical Report TR-892, MIT LCS, April 2003.
• 17: Ananth Rao , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 18: Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-aware overlay construction and server selection. In Proceedings of IEEE Infocom 2002, 2002.
• 19: Roberto Rinaldi and Marcel waldvogel. Routing and data location in overlay peer-to-peer networks. Research Report RZ-3433, IBM, July 2002.
• 20: Yuval Shavitt and Tomer Tankel. Big-bang simulation for embedding network distances in Euclidean space. In Proc. of IEEE Infocom, April 2003.
• 21: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 22: Marcel Waldvogel and Roberto Rinaldi. Efficient topology-aware overlay network. In Hotnets-I, 2002.
• 23: Limin Wang, Vivek Pai, and Larry Peterson. The Effectiveness of Request Redirection on CDN Robustness. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, Boston, MA USA, December 2002.