Frank Dabek
ABSTRACT
Large-scale Internet applications can benefit from an ability to predict round-trip times to other hosts without having to contact them first. Explicit measurements are often unattractive because the cost of measurement can outweigh the benefits of exploiting proximity information. Vivaldi is a simple, light-weight algorithm that assigns synthetic coordinates to hosts such that the distance between the coordinates of two hosts accurately predicts the communication latency between the hosts. Vivaldi is fully distributed, requiring no fixed network infrastructure and no distinguished hosts. It is also efficient: a new host can compute good coordinates for itself after collecting latency information from only a few other hosts. Because it requires little com-munication, Vivaldi can piggy-back on the communication patterns of the application using it and scale to a large number of hosts. An evaluation of Vivaldi using a simulated network whose latencies are based on measurements among 1740 Internet hosts shows that a 2-dimensional Euclidean model with height vectors embeds these hosts with low error (the median relative error in round-trip time prediction is 11 percent).
- BitTorrent. http://bitconjurer.org/BitTorrent/protocol.html.Google Scholar
- K. L. Calvert, M. B. Doar, and E. W. Zegura. Modeling Internet topology. IEEE Communications, 35(6):160--163, June 1997. Google ScholarDigital Library
- M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical Internet coordinates for distance estimation. In International Conference on Distributed Systems, Tokyo, Japan, March 2004. Google ScholarDigital Library
- R. Cox and F. Dabek. Learning Euclidean coordinates for Internet hosts. http://pdos.lcs.mit.edu/~rsc/6867.pdf, December 2002.Google Scholar
- R. Cox, F. Dabek, F. Kaashoek, J. Li, and R. Morris. Practical, distributed network coordinates. In Proceedings of the Second Workshop on Hot Topics in Networks (HotNets-II), Cambridge, Massachusetts, November 2003.Google Scholar
- F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proc. 18th ACM Symposium on Operating Systems Principles (SOSP '01), pages 202--205, Oct. 2001. Google ScholarDigital Library
- F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a DHT for low latency and high throughput. In Proceedings of the 1st USENIX Symposium on Networked Systems Design and Implementation (NSDI'04), San Francisco, California, March 2004. Google ScholarDigital Library
- 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 Transactions on Networking, Oct. 2001. Google ScholarDigital Library
- T. Gil, J. Li, F. Kaashoek, and R. Morris. Peer-to-peer simulator, 2003. http://pdos.lcs.mit.edu/p2psim.Google Scholar
- K. P. Gummadi, S. Saroiu, and S. D. Gribble. King: Estimating latency between arbitrary Internet end hosts. In Proc. of SIGCOMM IMW 2002, pages 5--18, November 2002. Google ScholarDigital Library
- H. Hoppe. Surface reconstruction from unorganized points. PhD thesis, Department of Computer Science and Engineering, University of Washington, 1994. Google ScholarDigital Library
- KaZaA media dekstop. http://www.kazaa.com/.Google Scholar
- P. Mockapetris and K. J. Dunlap. Development of the Domain Name System. In Proc. ACM SIGCOMM, pages 123--133, Stanford, CA, 1988. Google ScholarDigital Library
- J. C. Mogul. Efficient use of workstations for passive monitoring of local area networks. Research Report 90/5, Digital Western Research Laboratory, July 1990.Google ScholarDigital Library
- E. Ng. GNP software, 2003. http://www-2.cs.cmu.edu/~eugeneng/research/gnp/software.html.Google Scholar
- T. E. Ng and H. Zhang. A network positioning system for the Internet. In Proc. USENIX Conference, June 2004. Google ScholarDigital Library
- T. S. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of IEEE Infocom, pages 170--179, 2002.Google ScholarCross Ref
- V. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In Proc. ACM SIGCOMM, pages 173--185, San Diego, Aug. 2001. Google ScholarDigital Library
- M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for scalable distributed location. In IPTPS, 2003.Google ScholarCross Ref
- Planetlab. www.planet-lab.org.Google Scholar
- N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller. Anchor-free distributed localization in sensor networks. Technical Report TR-892, MIT LCS, Apr. 2003.Google Scholar
- N. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket Location-Support System. In Proc. 6th ACM MOBICOM Conf., Boston, MA, Aug. 2000. Google ScholarDigital Library
- A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing without location information. In ACM MobiCom Conference, pages 96--108, Sept. 2003. Google ScholarDigital Library
- R. Rinaldi and M. Waldvogel. Routing and data location in overlay peer-to-peer networks. Research Report RZ-3433, IBM, July 2002.Google Scholar
- C. Savarese, J. M. Rabaey, and J. Beutel. Locationing in distributed ad-hoc wireless sensor networks. In ICASSP, pages 2037--2040, May 2001.Google Scholar
- Y. Shavitt and T. Tankel. Big-bang simulation for embedding network distances in Euclidean space. In Proc. of IEEE Infocom, April 2003.Google ScholarCross Ref
- Y. Shavitt and T. Tankel. On the curvature of the Internet and its usage for overlay construction and distance estimation. In Proc. of IEEE Infocom, April 2004.Google ScholarCross Ref
- J. Stribling. All-pairs-ping trace of PlanetLab, 2004. http://pdos.lcs.mit.edu/ strib/.Google Scholar
- L. Tang and M. Crovella. Virtual landmarks for the Internet. In Internet Measurement Conference, pages 143--152, Miami Beach, FL, October 2003. Google ScholarDigital Library
- M. Waldvogel and R. Rinaldi. Efficient topology-aware overlay network. In Hotnets-I, 2002.Google Scholar
- L. Wang, V. Pai, and L. Peterson. The Effectiveness of Request Redirecion on CDN Robustness. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, Boston, MA USA, December 2002. Google ScholarDigital Library
Index Terms
- Vivaldi: a decentralized network coordinate system
Recommendations
Vivaldi: a decentralized network coordinate system
Large-scale Internet applications can benefit from an ability to predict round-trip times to other hosts without having to contact them first. Explicit measurements are often unattractive because the cost of measurement can outweigh the benefits of ...
Bounds for the Security of the Vivaldi Network Coordinate System
NETSYS '13: Proceedings of the 2013 Conference on Networked SystemsNetwork coordinate systems have gained much attention as they allow for an elegant estimation of distances between nodes in distributed systems. Their most prominent representative is Vivaldi, which is using a mass-spring-damper system to embed peers ...
Estimation of Data Propagation Time on the Bitcoin Network
AINTEC '19: Proceedings of the 15th Asian Internet Engineering ConferenceThe goal of this research is to estimate the data propagation time on the Bitcoin network. Using network coordinates, we estimate the communication latency between computers. Such latency estimation contributes future optimization of data propagation. ...
Comments