article

Measurement-based analysis, modeling, and synthesis of the internet delay space

Authors:

Tze Sing Eugene Ng,

Rudolf H. Riedi,

Peter Druschel,

Guohui WangAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 1

Pages 229 - 242

https://doi.org/10.1109/TNET.2009.2024083

Published: 01 February 2010 Publication History

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 DS² and demonstrate its effectiveness.

References

[1]

A. Acharya and J. Saltz, "A study of Internet round-trip delay," Univ. Maryland, Tech. Rep. CS-TR-3736, 1996.

[2]

"Active measurement project," NLANR {Online}. Available: http://watt.nlanr.net

[3]

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.

[4]

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.

[5]

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.

[6]

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.

[7]

F. Dabek, R. Cox, F. Kaashoek, and R. Morris, "Vivaldi: A decentralized network coordinate system," in Proc. ACM SIGCOMM, Aug. 2004, pp. 15-26.

[8]

M. Doar, "A better model for generating test networks," in Proc. IEEE GLOBECOM, Nov. 1996, pp. 86-93.

[9]

"DS ²," {Online}. Available: http://www.cs.rice.edu/~eugeneng/research/ds2/

[10]

C. Faloutsos, M. Faloutsos, and P. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, Aug. 1999, pp. 15-26.

[11]

M. Freedman, K. Lakshminarayanan, and D. Mazieres, "OASIS: Any-cast for any service," in Proc. USENIX NSDI, May 2006, p. 10.

[12]

"FreePastry," {Online}. Available: http://freepastry.rice.edu/

[13]

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.

[14]

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.

[15]

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.

[16]

D. R. Karger and M. Ruhl, "Finding nearest neighbors in growth-restricted metrics," in Proc. ACM STOC, May 2002, pp. 741-750.

[17]

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.

[18]

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.

[19]

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.

[20]

J. Møller and R. Waagepetersen, Statistical Inference and Simulation for Spatial Point Processes. London, U.K.: Chapman & Hall/CRC, 2004.

[21]

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.

[22]

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.

[23]

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.

[24]

"p2psim," {Online}. Available: http://www.pdos.lcs.mit.edu/p2psim/

[25]

M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti, "Lighthouses for scalable distributed location," presented at the IPTPS Feb. 2003.

[26]

"PingER," {Online}. Available: http://www.slac.stanford.edu/comp/ net/wan-mon/tutorial.html

[27]

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.

[28]

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.

[29]

S. Ratnasamy, S. Shenker, and I. Stoica, "Routing algorithms for DHTs: Some open questions," presented at the IPTPS, Mar. 2002.

[30]

R. Reiss, A Course on Point Processes, ser. Springer Series in Statistics. New York: Springer, 1993.

[31]

"Route Views," {Online}. Available: http://www.routeviews.org/

[32]

B. Bhattacharjee, S. Banerjee, and C. Kommareddy, "Scalable application layer multicast," in Proc. ACM SIGCOMM, Aug. 2002, pp. 205-217.

[33]

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.

[34]

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.

[35]

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.

[36]

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.

[37]

"Skitter," {Online}. Available: http://www.caida.org/tools/measurement/ skitter/

[38]

A. Slivkins, "Distributed approaches to triangulation and embedding," in Proc. 16th ACM-SIAM SODA, Jan. 2004, pp. 640-649.

[39]

A. Slivkins, J. Kleinberg, and T. Wexler, "Triangulation and embedding using small sets of beacons," in Proc. IEEE FOCS, Oct. 2004, pp. 444-453.

[40]

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.

[41]

"Surveyor," {Online}. Available: http://www.advanced.org/csg-ippm/

[42]

L. Tang and M. Crovella, "Virtual landmarks for the Internet," in Proc. ACM IMC, Oct. 2003, pp. 143-152.

[43]

M. Waldvogel and R. Rinaldi, "Efficient topology-aware overlay network," presented at the ACM HotNets-I, October 2002.

[44]

B. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

[45]

J. Winick and S. Jamin, "Inet-3.0: Internet topology generator," Univ. Michigan, Tech. Rep. UM-CSE-TR-456-02, 2002.

[46]

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.

[47]

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.

[48]

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.

[49]

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.

[50]

H. Zheng, E. Luo, M. Pias, and T. Griffin, "Internet routing policies and round-trip time," in Proc. PAM, Mar. 2005, pp. 236-250.

Cited By

Tian HGuo KGuan X(2024)Statistical behavioral characteristics of network communication delay in IPv4/IPv6 InternetTelecommunications Systems10.1007/s11235-024-01111-y85:4(679-698)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s11235-024-01111-y
Kuang YLi DHuang XZhou M(2022)On the Modeling of RTT Time Series for Network Anomaly DetectionSecurity and Communication Networks10.1155/2022/54990802022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/5499080
Yue MWang MWu Z(2021)Low-High Burst: A Double Potency Varying-RTT Based Full-Buffer Shrew Attack ModelIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2019.294816718:5(2285-2300)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1109/TDSC.2019.2948167
Show More Cited By

Index Terms

Recommendations

Measurement based analysis, modeling, and synthesis of the internet delay space
IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement

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 ...
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 measurement

Many 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 1

February 2010

332 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2010

Revised: 05 June 2008

Received: 21 July 2007

Published in TON Volume 18, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
198
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tian HGuo KGuan X(2024)Statistical behavioral characteristics of network communication delay in IPv4/IPv6 InternetTelecommunications Systems10.1007/s11235-024-01111-y85:4(679-698)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s11235-024-01111-y
Kuang YLi DHuang XZhou M(2022)On the Modeling of RTT Time Series for Network Anomaly DetectionSecurity and Communication Networks10.1155/2022/54990802022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/5499080
Yue MWang MWu Z(2021)Low-High Burst: A Double Potency Varying-RTT Based Full-Buffer Shrew Attack ModelIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2019.294816718:5(2285-2300)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1109/TDSC.2019.2948167
Liu YWei WXu H(2019)Efficient multi-resource scheduling algorithm for hybrid cloud-based large-scale media streamingComputers and Electrical Engineering10.1016/j.compeleceng.2019.02.00775:C(123-134)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1016/j.compeleceng.2019.02.007
Jia YWu CLi ZLe FLiu ALi ZJia YWu CLe FLiu A(2018)Online Scaling of NFV Service Chains Across Geo-Distributed DatacentersIEEE/ACM Transactions on Networking10.1109/TNET.2018.280040026:2(699-710)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2800400
Fontugne RPelsser CAben EBush RUhlig SMaennel O(2017)Pinpointing delay and forwarding anomalies using large-scale traceroute measurementsProceedings of the 2017 Internet Measurement Conference10.1145/3131365.3131384(15-28)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1145/3131365.3131384
Anglano CGaeta RGrangetto M(2017)Securing Coding-Based Cloud Storage Against Pollution AttacksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.261968628:5(1457-1469)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2619686
Fu YBiersack EYongquan Fu Biersack E(2017)MCRIEEE/ACM Transactions on Networking10.1109/TNET.2017.271533125:5(3016-3029)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1109/TNET.2017.2715331
Huang GMiller MAkopian D(2017)Inference of network delays for SUPL 3.0-based assisted GNSSGPS Solutions10.1007/s10291-016-0549-621:2(651-661)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10291-016-0549-6
Maddahi YLiao SFung WSepehri N(2016)Position referenced force augmentation in teleoperated hydraulic manipulators operating under delayed and lossy networksRobotics and Autonomous Systems10.1016/j.robot.2016.04.00683:C(231-242)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.robot.2016.04.006
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents