Bo Zhang
Abstract
Understanding the characteristics of the Internet delay space (i.e., the all-pairs set of static round-trip propagation delays among edge networks in the Internet) is important for the design of global-scale distributed systems. For instance, algorithms used in overlay networks are often sensitive to violations of the triangle inequality and to the growth properties within the Internet delay space. Since designers of distributed systems often rely on simulation and emulation to study design alternatives, they need a realistic model of the Internet delay space. In this paper, we analyze measured delay spaces among thousands of Internet edge networks and quantify key properties that are important for distributed system design. Our analysis shows that existing delay space models do not adequately capture these important properties of the Internet delay space. Furthermore, we derive a simple model of the Internet delay space based on our analytical findings. This model preserves the relevant metrics far better than existing models, allows for a compact representation, and can be used to synthesize delay data for simulations and emulations at a scale where direct measurement and storage are impractical. We present the design of a publicly available delay space synthesizer tool called DS2 and demonstrate its effectiveness.
- A. Acharya and J. Saltz, "A study of Internet round-trip delay," Univ. Maryland, Tech. Rep. CS-TR-3736, 1996.Google Scholar
- "Active measurement project," NLANR {Online}. Available: http://watt.nlanr.netGoogle Scholar
- M. Castro, P. Druschel, A. Ganesh, A. Rowstron, and D. S. Wallach, "Security for structured peer-to-peer overlay networks," in Proc. USENIX OSDI, Dec. 2002, pp. 299-314. Google Scholar
- M. Castro, P. Druschel, Y. Hu, and A. Rowstron, "Exploiting network proximity in peer-to-peer overlay networks," Microsoft Research, Tech. Rep. MSR-TR-2002-82, May 2002.Google Scholar
- M. Castro, P. Druschel, Y. Hu, and A. Rowstron, "Proximity neighbor selection in tree-based structured peer-to-peer overlays," Microsoft Research, Tech. Rep. MSR-TR-2003-52, Jun. 2003.Google Scholar
- M. Costa, M. Castro, A. Rowstron, and P. Key, "PIC: Practical Internet coordinates for distance estimation," Microsoft Research, Tech. Rep. MSR-TR-2003-53, Sep. 2003.Google Scholar
- F. Dabek, R. Cox, F. Kaashoek, and R. Morris, "Vivaldi: A decentralized network coordinate system," in Proc. ACM SIGCOMM, Aug. 2004, pp. 15-26. Google Scholar
- M. Doar, "A better model for generating test networks," in Proc. IEEE GLOBECOM, Nov. 1996, pp. 86-93.Google Scholar
- "DS
2," {Online}. Available: http://www.cs.rice.edu/~eugeneng/research/ds2/Google Scholar
- C. Faloutsos, M. Faloutsos, and P. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, Aug. 1999, pp. 15-26. Google Scholar
- M. Freedman, K. Lakshminarayanan, and D. Mazieres, "OASIS: Any-cast for any service," in Proc. USENIX NSDI, May 2006, p. 10. Google Scholar
- "FreePastry," {Online}. Available: http://freepastry.rice.edu/Google Scholar
- K. P. Gummadi, R. Gummadi, S. D. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, "The impact of DHT routing geometry on resilience and proximity," in Proc. ACM SIGCOMM, Aug. 2003, pp. 381-394. Google Scholar
- K. P. Gummadi, S. Saroiu, and S. D. Gribble, "King: Estimating latency between arbitrary Internet end hosts," in Proc. ACM IMW, Nov. 2002, pp. 5-18. Google Scholar
- K. Hildrum and J. Kubiatowicz, "Asymptotically efficient approaches to fault tolerance in peer-to-peer networks," in Proc. 17th Int. Symp. Distrib. Comput., Oct. 2003, pp. 321-336.Google Scholar
- D. R. Karger and M. Ruhl, "Finding nearest neighbors in growth-restricted metrics," in Proc. ACM STOC, May 2002, pp. 741-750. Google Scholar
- S. Lee, Z. Zhang, S. Sahu, and D. Saha, "On suitability of Euclidean embedding of Internet hosts," in Proc. ACM SIGMETRICS, Jun. 2006, pp. 157-168. Google Scholar
- L. Li, D. Alderson, W. Willinger, and J. Doyle, "A first-principles approach to understanding the Internet's router-level topology," in Proc. ACM SIGCOMM, Aug. 2004, pp. 3-14. Google Scholar
- H. Lim, J. Hou, and C.-H. Choi, "Constructing Internet coordinate system based on delay measurement," in Proc. ACM IMC, Oct. 2003, pp. 129-142. Google Scholar
- J. Møller and R. Waagepetersen, Statistical Inference and Simulation for Spatial Point Processes. London, U.K.: Chapman & Hall/CRC, 2004.Google Scholar
- E. Lua, T. Griffin, M. Pias, H. Zheng, and J. Crowcroft, "On the accuracy of embeddings for Internet coordinate systems," in Proc. ACM IMC, Oct. 2005, p. 11. Google Scholar
- H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services," in Proc. USENIX OSDI, Nov. 2006, pp. 367-380. Google Scholar
- T. S. E. Ng and H. Zhang, "Predicting Internet networking distance with coordinates-based approaches," in Proc. IEEE INFOCOM, June 2002, vol. 1, pp. 170-179.Google Scholar
- "p2psim," {Online}. Available: http://www.pdos.lcs.mit.edu/p2psim/Google Scholar
- M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti, "Lighthouses for scalable distributed location," presented at the IPTPS Feb. 2003.Google Scholar
- "PingER," {Online}. Available: http://www.slac.stanford.edu/comp/ net/wan-mon/tutorial.htmlGoogle Scholar
- V. Ramasubramanian and E. G. Sirer, "Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays," in Proc. USENIX NSDI, Mar. 2004, p. 8. Google Scholar
- S. Ranjan, R. Karrer, and E. Knightly, "Wide area redirection of dynamic content by Internet data centers," in Proc. IEEE INFOCOM, 2004, vol. 2, pp. 816-826.Google Scholar
- S. Ratnasamy, S. Shenker, and I. Stoica, "Routing algorithms for DHTs: Some open questions," presented at the IPTPS, Mar. 2002. Google Scholar
- R. Reiss, A Course on Point Processes, ser. Springer Series in Statistics. New York: Springer, 1993.Google Scholar
- "Route Views," {Online}. Available: http://www.routeviews.org/Google Scholar
- B. Bhattacharjee, S. Banerjee, and C. Kommareddy, "Scalable application layer multicast," in Proc. ACM SIGCOMM, Aug. 2002, pp. 205-217. Google Scholar
- S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson, "The end-to-end effects of Internet path selection," in Proc. ACM SIGCOMM, Aug. 1999, pp. 289-299. Google Scholar
- Y. Shavitt and T. Tankel, "Big-bang simulation for embedding network distances in Euclidean space," in Proc. IEEE INFOCOM, Mar. 2003, vol. 3, pp. 1922-1932.Google Scholar
- Y. Shavitt and T. Tankel, "On the curvature of the Internet and its usage for overlay construction and distance estimation," in Proc. IEEE INFOCOM, Mar. 2004, vol. 1.Google Scholar
- A. Singh, T. W. Ngan, P. Druschel, and D. S. Wallach, "Eclipse attacks on overlay networks: Threats and defenses," in Proc. IEEE INFOCOM, 2006, pp. 1-12.Google Scholar
- "Skitter," {Online}. Available: http://www.caida.org/tools/measurement/ skitter/Google Scholar
- A. Slivkins, "Distributed approaches to triangulation and embedding," in Proc. 16th ACM-SIAM SODA, Jan. 2004, pp. 640-649. Google Scholar
- A. Slivkins, J. Kleinberg, and T. Wexler, "Triangulation and embedding using small sets of beacons," in Proc. IEEE FOCS, Oct. 2004, pp. 444-453. Google Scholar
- 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, Aug. 2001, pp. 149-160. Google Scholar
- "Surveyor," {Online}. Available: http://www.advanced.org/csg-ippm/Google Scholar
- L. Tang and M. Crovella, "Virtual landmarks for the Internet," in Proc. ACM IMC, Oct. 2003, pp. 143-152. Google Scholar
- M. Waldvogel and R. Rinaldi, "Efficient topology-aware overlay network," presented at the ACM HotNets-I, October 2002.Google Scholar
- B. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.Google Scholar
- J. Winick and S. Jamin, "Inet-3.0: Internet topology generator," Univ. Michigan, Tech. Rep. UM-CSE-TR-456-02, 2002.Google Scholar
- B. Wong, A. Slivkins, and E. Sirer, "Meridian: A lightweight network location service without virtual coordinates," in Proc. ACM SIGCOMM, Aug. 2005, pp. 85-96. Google Scholar
- E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, "How to model an Internetwork," in Proc. IEEE INFOCOM, Mar. 1996, vol. 2, pp. 594-602. Google Scholar
- B. Zhang, T. S. E. Ng, A. Nandi, R. Riedi, P. Druschel, and G. Wang, "Measurement-based analysis, modeling, and synthesis of the Internet delay space," in Proc. ACM IMC, Oct. 2006, pp. 85-98. Google Scholar
- B. Zhao, J. Kubiatowicz, and A. Joseph, "Tapestry: An infrastructure for wide-area fault-tolerant location and routing," U.C. Berkeley, Tech. Rep. UCB//CSD-01-1141, 2001. Google Scholar
- H. Zheng, E. Luo, M. Pias, and T. Griffin, "Internet routing policies and round-trip time," in Proc. PAM, Mar. 2005, pp. 236-250. Google Scholar
Index Terms
- Measurement-based analysis, modeling, and synthesis of the internet delay space
Recommendations
Measurement based analysis, modeling, and synthesis of the internet delay space
IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurementUnderstanding the characteristics of the Internet delay space (i.e., the all-pairs set of static round-trip propagation delays among edge networks in the Internet) is important for the design of global-scale distributed systems. For instance, algorithms ...
Multi-manifold model of the Internet delay space
The network coordinate systems (NCSes) can assist the network applications to improve their performance by choosing preferred severs or constructing optimal overlay networks. However, the current NCSes cannot predict the end-to-end delay accurately, ...
Towards network triangle inequality violation aware distributed systems
IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurementMany distributed systems rely on neighbor selection mechanisms to create overlay structures that have good network performance. These neighbor selection mechanisms often assume the triangle inequality holds for Internet delays. However, the reality is ...
Comments