Article

A Framework for Measuring and Predicting the Impact of Routing Changes

Authors:

Jia WangAuthors Info & Claims

Proceedings of the IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications

Pages 339 - 347

https://doi.org/10.1109/INFCOM.2007.47

Published: 01 May 2007 Publication History

Abstract

Routing dynamics heavily influence Internet data plane performance. Existing studies only narrowly focused on a few destinations and did not consider the predictability of the impact of routing changes on performance metrics such as reachability. In this work, we propose an efficient framework to capture coarse-grained but important performance degradation as a result of BGP routing events using light-weight probing. We deployed our framework across six vantage points for 11 weeks and found that the data plane experienced serious performance degradation in the form of reachability loss and forwarding loops following a significant fraction of updates affecting many destination prefixes and networks across all vantage points studied. Specifically, more than 39% of updates resulted in reachability loss, some lasting for more than 300 seconds, impacting more than 72% of probed prefixes and more than 35% of all the prefixes on the Internet. We identified that more than half of the prefixes have predictable routing behavior. Based on the stationarity of the correlation between routing changes and the data plane performance, we developed a model to accurately predict the severity of the impact due to routing changes. Such a model is directly helpful for making informed decisions for improved routing schemes such as overlay routing and backup path selection.

References

[1]

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

Digital Library

[2]

F. Wang, Z. M. Mao, J. Wang, L. Gao, and R. Bush, A Measurement Study on the Impact of Routing Events on End-to-End Internet Path Performance, in Proc. ACM SIGCOMM, 2006.

Digital Library

[3]

Z. M. Mao, R. Bush, T. G. Griffin, and M. Roughan, BGP beacons, in Proc. ACM SIGCOMM Internet Measurement Conference, 2003.

Digital Library

[4]

A. Sridharan, Sue.B.Moon, and C. Diot, On the Correlation between Route Dynamics and Routing, in Proc. ACM SIGCOMM Internet Measurement Conference, October 2003.

Digital Library

[5]

University of Oregon Route Views Archive Project. http://www. routeview.org.

[6]

F. Wang, L. Gao, J. Wang, and J. Qiu, On Understanding of Transient Interdomain Routing Failures, in Proc. International Conference on Network Protocols, 2005.

Digital Library

[7]

J. Xia, L. Gao, and T. Fei, Flooding Attacks by Exploiting Persistent Forwarding Loops, in Proc. ACM SIGCOMM Internet Measurement Conference, 2005.

Digital Library

[8]

D. Pei, L. Wang, D. Massey, S. F. Wu, and LixiaZhang, A Study of Packet Delivery Performance during Routing Convergence, in Proc. of IEEE International Conference on Dependable Systems and Networks (DSN), 2003.

[9]

L. Z. Beichuan Zhang, Daniel Massey, Destination Reachability and BGP Convergence Time, in Proc. of IEEE Globecom, Global Internet and Next Generation Networks, 2004.

[10]

X. Zhao, B. Zhang, A. Terzis, D. Massey, and L. Zhang, The Impact of Link Failure Location on Routing Dynamics: A Formal Analysis, in Proc. of ACM SIGCOMM Asia Workshop, 2005.

[11]

N. Feamster, D. G. Andersen, H. Balakrishnan, and M. F. Kaashoek, Measuring the Effects of Internet Path Faults on Reactive Routing, in Proc. ACM SIGMETRICS, Jun 2003.

Digital Library

[12]

GNU Zebra-routing software. http : //www. zebra. org.

[13]

A. Zeitoun and S. Jamin, Rapid Exploration of Internet Live Address Space Using Optimal Discovery Path, in Proc. Global Communications Conference, 2003.

[14]

B. Zhang, V. Kambhampati, M. Lad, D. Massey, and L. Zhang, Identifying BGP Routing Table Transfers, in Proc. SIGCOMM Mining the Network Data (MineNet) Workshop, August 2005.

Digital Library

[15]

PlanetLab. http://www.planet-lab.org.

[16]

D. Andersen, H. Balakrishnan, M. Kaashoek, and R. Morris, Resilient Overlay Networks, in Proc. Symposium on Operating Systems Principles, 2001.

Digital Library

[17]

L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, Characterizing the Internet hierarchy from multiple vantage points, in Proc. IEEE INFOCOM, 2002.

[18]

Neil Spring and Ratul Mahajan and David Wetherall, Measuring ISP Topologies with Rocketfuel, in Proc. ACM SIGCOMM, 2002.

Digital Library

[19]

U. Hengartner, S. Moon, R. Mortier, and C. Diot, Detection and analysis of routing loops in packet traces, in Proc. ACM SIGCOMM Internet Measurement Workshop, 2002.

Digital Library

[20]

V. Paxson, End-to-end routing behavior in the Internet, in Proc. the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, vol. 26,4 of ACM SIGCOMM Computer Communication Review, ACM Press, 1996.

Digital Library

[21]

D. Pei, X. Zhao, D. Massey, and L. Zhang, A Study of BGP Path Vector Route Looping Behavior, in Proc. IEEE International Conference on Distributed Computing Systems, 2004.

Digital Library

[22]

Z. Zhong, R. Keralapura, S. Nelakuditi, Y. Yu, J. Wang, C.-N. Chuah, and S. Lee, Avoiding Transient Loops through Interface-Specific Forwarding, in Proc. IFIP/IEEE IWQoS, June 2005.

Digital Library

[23]

J. P. Egan, Signal Detection Theory and ROC Analysis. New York: Academic Press, 1975.

[24]

A. Bremler-Barr, E. Cohen, H. Kaplan, and Y. Mansour, Predicting and Bypassing End-to-End Internet Service Degradations, in Proc. ACM SIGCOMM Internet Measurement Conference, 2002.

Digital Library

[25]

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, in Proc. Symposium on Operating Systems Design and Implementation, 2004.

Digital Library

[26]

S. Agarwal, C. Chuah, S. Bhattacharyya, and C. Diot, Impact of BGP Dynamics on Intra-Domain Traffic, in Proc. ACM SIGMETRICS, 2004.

Digital Library

[27]

J. Li, R. Bush, Z. M. Mao, T. Griffin, M. Roughan, D. Stutzbach, and E. Purpus, Watching Data Streams Toward a Multi-Homed Sink Under Routing Changes Introduced by a BGP Beacon, in Proc. Passive and Active Measurement Workshop, 2006.

[28]

C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, Delayed internet routing convergence, in Proc. ACM SIGCOMM, 2000.

Digital Library

[29]

I. Avramopoulos and J. Rexford, Stealth probing: Efficient data-plane security for IP routing, in Proc. USENIX Annual Technical Conference, 2006.

Digital Library

[30]

M. Zhang, C. Zhang, V. Pai, L. Peterson, and R. Wang, PlanetSeer: Internet Path Failure Monitoring and Characterization in Wide-Area Services. in Proc. Symposium on Operating Systems Design and Implementation, 2004.

Digital Library

[31]

D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris, Resilient Overlay Networks, in Proc. Symposium on Operating Systems Principles, 2001.

Digital Library

[32]

D. Andersen, A. Snoeren, and H. Balakrishnan, Best-Path vs. MultiPath Overlay Routing, in Proc. ACM SIGCOMM Internet Measurement Conference, 2003.

Digital Library

Cited By

Holterbach TVissicchio SDainotti AVanbever L(2017)SWIFTProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098856(460-473)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098856
Di Donato VPatrignani MSquarcella CCostabile MBuono PMatera M(2016)NetForkProceedings of the International Working Conference on Advanced Visual Interfaces10.1145/2909132.2909245(92-99)Online publication date: 7-Jun-2016
https://dl.acm.org/doi/10.1145/2909132.2909245
Clad FVissicchio SMérindol PFrancois PPansiot J(2015)Computing minimal update sequences for graceful router-wide reconfigurationsIEEE/ACM Transactions on Networking10.1109/TNET.2014.233210123:5(1373-1386)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2332101
Show More Cited By

A Framework for Measuring and Predicting the Impact of Routing Changes
1. Networks
  1. Network protocols
    1. Network layer protocols

Recommendations

Impact of hot-potato routing changes in IP networks

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Network sensitivity to intradomain routing changes
An active approach to measuring routing dynamics induced by autonomous systems
ExpCS '07: Proceedings of the 2007 workshop on Experimental computer science

We present an active measurement study of the routing dynamics induced by AS-path prepending, a common method for controlling the inbound traffic of a multi-homed ISP. Unlike other inter-domain inbound traffic engineering methods, AS-path prepending not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications

May 2007

2599 pages

ISBN:1424410479

Copyright © 2007.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Holterbach TVissicchio SDainotti AVanbever L(2017)SWIFTProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098856(460-473)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098856
Di Donato VPatrignani MSquarcella CCostabile MBuono PMatera M(2016)NetForkProceedings of the International Working Conference on Advanced Visual Interfaces10.1145/2909132.2909245(92-99)Online publication date: 7-Jun-2016
https://dl.acm.org/doi/10.1145/2909132.2909245
Clad FVissicchio SMérindol PFrancois PPansiot J(2015)Computing minimal update sequences for graceful router-wide reconfigurationsIEEE/ACM Transactions on Networking10.1109/TNET.2014.233210123:5(1373-1386)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2332101
Cunha ÍTeixeira RVeitch DDiot C(2014)DTRACKIEEE/ACM Transactions on Networking10.1109/TNET.2013.226983722:4(1025-1038)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2269837
Khosla RFahmy SHu YNeville J(2011)Prediction models for long-term Internet prefix availabilityComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.00555:3(873-889)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1016/j.comnet.2010.10.005
Khosla RFahmy SHu YNeville J(2010)Predicting prefix availability in the internetProceedings of the 29th conference on Information communications10.5555/1833515.1833559(216-220)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833559
Jiang HGe ZJin SWang J(2010)Network prefix-level traffic profilingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.06.01354:18(3327-3340)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1016/j.comnet.2010.06.013
Wu QRao NLu XKwon K(2010)Stabilizing transport dynamics of control channels over wide-area networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.05.00454:15(2728-2743)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1016/j.comnet.2010.05.004
Watari MHei YAno SYamazaki K(2009)OSPF-based fast reroute for BGP link failuresProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811380.1811578(1199-1205)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811380.1811578

View Options

View options

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 Publication

Media

Figures

Other

Tables

View Table of Contents