research-article

An Experimental Study of Internet Path Diversity

Authors:

Farnam JahanianAuthors Info & Claims

IEEE Transactions on Dependable and Secure Computing, Volume 3, Issue 4

Pages 273 - 288

https://doi.org/10.1109/TDSC.2006.43

Published: 01 October 2006 Publication History

Abstract

Several research studies have been devoted to improving the reliability and performance of the Internet by utilizing redundant communication paths between end points. Multihoming, coupled with intelligent route control, and overlay networks are two main streams in this area of research which attempt to leverage redundant connections of the Internet for increased reliability and performance. However, the effectiveness of these approaches depends on the natural diversity of redundant paths between two endhosts in terms of physical links, routing infrastructure, administrative control, and geographical distribution. Even in the case of redundant paths, if traffic between two hosts is not actually routed along completely disjoint paths, congestion or failure of a single shared link or router can adversely affect the end-to-end performance or availability of all paths. This paper presents an experimental study of path diversity on the Internet, focusing on the impact of path diversity on multihomed and overlay networks. We base our analysis on traceroutes and routing table data collected from several vantage points in the Internet including: looking glasses at 10 major Internet Service Providers (ISPs), RouteViews servers from 20 ISPs, and more than 50 PlanetLab nodes globally distributed across the Internet. Using this data, we quantify the extent of path diversity in multihoming and overlay networks, highlighting the limitations, and also identifying the source of the limitations in these architectures. From the analysis, we learn that both multihoming route control and current overlay networks are not able to ensure path diversity, which makes it very difficult to provide high-availability services even with the use of these systems. We believe that this work provides the insight into building future systems based on understanding path diversity.

References

[1]

A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman, “A Measurement-Based Analysis of Multihoming,” Proc. ACM SIGCOMM, 2003.

Digital Library

[2]

A. Akella, J. Pang, B. Maggs, S. Seshan, and A. Shaikh, “A Comparison of Overlay Routing and Multihoming Route Control,” Proc. ACM SIGCOMM, 2004.

Digital Library

[3]

D. Anderson, H. Balakrishnan, F. Kaashoek, and R. Morris, “Resilient Overlay Networks,” Proc. 18th ACM Symp. Operating Systems Principles, 2001.

Digital Library

[4]

D. Anderson, H. Balakrishnan, M.F. Kaashoek, and R.N. Rao, “Improving Web Availability for Clients with MONET,” Proc. Second Symp. Networked Systems Design and Implementation (NSDI), 2005.

Digital Library

[5]

D.G. Anderson, A.C. Snoeren, and H. Balakrishnan, “Best-Path vs. Multipath Overlay Routing,” Proc. Internet Measurement Conf., 2003.

Digital Library

[6]

R. Braynard, D. Kostic, A. Rodriguesz, J. Chase, and A. Vahdat, “Opus: An Overlay Peer Utility Service,” Proc. Fifth Int'l Conf. Open Architectures and Network Programming, 2002.

[7]

B. Chandra, M. Dahlin, L. Gao, and A. Nayate, “End-to-End WAN Service Availability,” Proc. Third Usenix Symp. Internet Technologies and Systems, 2001.

Digital Library

[8]

H. Chang, S. Jamin, and W. Willinger, “Internet Connectivity at the AS-Level: An Optimization-Driven Modeling Approach,” Proc. ACM SIGCOMM Workshop Models, Methods, and Tools for Reproducible Network Research, 2003.

Digital Library

[9]

A. Collins, “The Detour Framework for Packet Rerouting,” master's thesis, Univ. of Washington, 1998.

[10]

W. Cui, I. Stoica, and R.H. Katz, “Backup Path Allocation Based on a Correlated Link Failure Probability Model in Overlay Networks,” Proc. Int'l Conf. Network Protocols (ICNP), 2002.

Digital Library

[11]

P. Enriquez, A. Brown, and D.A. Patterson, “Lessons from the PSTN for Dependable Computing,” Proc. Workshop Self-Healing, Adaptive, and Self-Managed Systems, 2002.

[12]

N. Feamster, D. Anderson, H. Balakrishnan, and M.F. Kaashoek, “Measuring the Effects of Internet Path Faults on Reactive Routing,” Proc. ACM SIGMETRICS, 2003.

Digital Library

[13]

F. Guo, J. Chen, W. Li, and T. Chiueh, “Experience in Building a Multihoming Load Balancing System,” Proc. IEEE INFOCOM, 2004.

[14]

D.K. Goldenberg, L. Qiu, H. Xie, Y.R. Yang, and Y. Zhang, “Optimizing Cost and Performance for Multihoming,” Proc. ACM SIGCOMM, 2004.

Digital Library

[15]

K.P. Gummadi, H.V. Madhyastha, S.D. Gribble, H.M. Levy, and D. Wetherall, “Improving the Reliability of Internet Paths with One-Hop Source Routing,” Proc. Seventh Symp. Operating Systems Design and Implementation, 2004.

Digital Library

[16]

J. Han and F. Jahanian, “Impact of Path Diversity on Multihomed and Overlay Networks,” Proc. IEEE Int'l Conf. Dependable Systems and Networks, 2004.

Digital Library

[17]

J. Han, G. Malan, and F. Jahanian, “Fault-Tolerant Virtual Private Networks within an Autonomous System,” Proc. Symp. Reliable Distributed Systems, Oct. 2002.

[18]

J. Han, D. Watson, and F. Jahanian, “Topology Aware Overlay Networks,” Proc. IEEE INFOCOM, 2005.

[19]

G. Iannaccone, C. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot, “Analysis of Link Failures in an IP Backbone,” Proc. Internet Measurement Workshop, 2002.

Digital Library

[20]

InterNap,

[21]

Computer, vol. 30, no. 4, 1997.

Digital Library

[22]

C. Labovitz, A. Ahuja, and F. Jahanian, “Experimental Study of Internet Stability and Wide-Area Network Failures,” Proc. 29th Ann. Int'l Symp. Fault-Tolerant Computing (FTCS '99), 1999.

Digital Library

[23]

C. Labovitz, A. Ahuja, and F. Jahanian, “Delayed Internet Routing Convergence,” Proc. ACM SIGCOMM, 2000.

Digital Library

[24]

IEEE/ACM Trans. Networking, vol. 6, no. 5, pp. 515-528, 1998.

Digital Library

[25]

Z.M. Mao, R. Govindan, G. Varghese, and R. Katz, “Route Flap Damping Exacerbates Internet Routing Convergence,” Proc. ACM SIGCOMM, 2002.

Digital Library

[26]

Z.M. Mao, J. Rexford, J. Wang, and R. Katz, “Towards an Accurate AS-Level Traceroute Tool,” Proc. ACM SIGCOMM, 2003.

Digital Library

[27]

K. Nayak and D. McKernan, “Measuring Provider Path Diversity from Traceroute Data: Work in Progress,” Proc. CAIDA-ISMA Workshop, 2001.

[28]

V. Paxson, “End-to-End Routing Behavior in the Internet,” Proc. ACM SIGCOMM, 1996.

Digital Library

[29]

PlanetLab,

[30]

Radware, “Linkproof: A Traffic Manager for Multihomed Networks,”

[31]

RIPE-NCC Routing Information,

[32]

RouteScience,

[33]

RouteViews,

[34]

Skitter Project,

[35]

L. Subramanian, S. Agrawal, J. Rexford, and R.H. Katz, “Characterizing the Internet Hierarchy from Multiple Vantage Points,” Proc. IEEE INFOCOM, 2002.

[36]

R. Teixeira, K. Marzullo, S. Savage, and G.M. Voelker, “In Search for Path Diversity in ISP Networks,” Proc. Internet Measurement Conf., 2003.

Digital Library

[37]

sr-ally,

Cited By

Aydeger ASaputro NAkkaya K(2019)A moving target defense and network forensics framework for ISP networks using SDN and NFVFuture Generation Computer Systems10.1016/j.future.2018.11.04594:C(496-509)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1016/j.future.2018.11.045
Esposito CCotroneo D(2018)Resilient and Timely Event Dissemination in Publish/Subscribe MiddlewareInternational Journal of Adaptive, Resilient and Autonomic Systems10.4018/jaras.20100717011:1(1-20)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.4018/jaras.2010071701
Esposito CFicco MPalmieri FCastiglione A(2018)Interconnecting Federated Clouds by Using Publish-Subscribe ServiceCluster Computing10.1007/s10586-013-0261-z16:4(887-903)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10586-013-0261-z
Show More Cited By

Index Terms

An Experimental Study of Internet Path Diversity

Recommendations

Path-diversity P2P overlay retransmissioll for reliable IP-multicast

IP-multicast is a bandwidth efficient transmission mechanism for group communications. Reliability in IP-multicast, however, poses a set of significant challenges. To address the reliability and scalability issues in IP-multicast, this paper proposes a ...
X-BOT: A Protocol for Resilient Optimization of Unstructured Overlay Networks

Gossip, or epidemic, protocols have emerged as a highly scalable and resilient approach to implement several application level services such as reliable multicast, data aggregation, publish-subscribe, among others. All these protocols organize nodes in ...
On AS-level path inference
Performance evaluation review

The ability to discover the AS-level path between two end-points is valuable for network diagnosis, performance optimization, and reliability enhancement. Virtually all existing techniques and tools for path discovery require direct access to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Dependable and Secure Computing

IEEE Transactions on Dependable and Secure Computing Volume 3, Issue 4

October 2006

133 pages

ISSN:1545-5971

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 October 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aydeger ASaputro NAkkaya K(2019)A moving target defense and network forensics framework for ISP networks using SDN and NFVFuture Generation Computer Systems10.1016/j.future.2018.11.04594:C(496-509)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1016/j.future.2018.11.045
Esposito CCotroneo D(2018)Resilient and Timely Event Dissemination in Publish/Subscribe MiddlewareInternational Journal of Adaptive, Resilient and Autonomic Systems10.4018/jaras.20100717011:1(1-20)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.4018/jaras.2010071701
Esposito CFicco MPalmieri FCastiglione A(2018)Interconnecting Federated Clouds by Using Publish-Subscribe ServiceCluster Computing10.1007/s10586-013-0261-z16:4(887-903)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10586-013-0261-z
Esposito CCastiglione APalmieri F(2015)Dealing with Reliable Event-Based Communications by Means of Layered MulticastProceedings of the ICA3PP International Workshops and Symposiums on Algorithms and Architectures for Parallel Processing - Volume 953210.1007/978-3-319-27161-3_52(572-581)Online publication date: 18-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-27161-3_52
Esposito CBry FPaschke AEugster PFetzer CBehrend A(2012)A tutorial on reliability in publish/subscribe servicesProceedings of the 6th ACM International Conference on Distributed Event-Based Systems10.1145/2335484.2335537(399-406)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2335484.2335537
Zhang YWang CGao Y(2009)Weighted size-aware packet distribution for multipath live streamingProceedings of the 2009 IEEE international conference on Communications10.5555/1817271.1817503(1251-1255)Online publication date: 14-Jun-2009
https://dl.acm.org/doi/10.5555/1817271.1817503

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents