Internet routing resilience to failures: analysis and implications

ABSTRACT

Internet interdomain routing is policy-driven, and thus physical connectivity does not imply reachability. On average, routing on today's Internet works quite well, ensuring reachability for most networks and achieving reasonable performance across most paths. However, there is a serious lack of understanding of Internet routing resilience to significant but realistic failures such as those caused by the 911 event, the 2003 Northeast blackout, and the recent Taiwan earthquake in December 2006. In this paper, we systematically analyze how the current Internet routing system reacts to various types of failures by developing a realistic failure model, and then pinpoint reliability bottlenecks of the Internet. For validity of our simulation results, we generate topology graphs by addressing concerns over the incompleteness of topology and the inaccuracy of inferred AS relationships. By focusing on the impact of structural and policy properties, our analysis provides guidelines for future Internet design. The simulation tool we provide for analyzing routing resilience is also efficient to scale to Internet-size topologies.

REFERENCES

• 1: "Internet Routing Behavior on 9/11." http://www.renesys.com.
• 2: "Asia scrambles to restore communications after quake." http://www.iht.com/articles/2006/12/28.
• 3: Hao Wang , Yang Richard Yang , Paul H. Liu , Jia Wang , Alexandre Gerber , Albert Greenberg, Reliability as an interdomain service, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 4: "University of Oregon Route Views Archive Project." http://www.routeview.org.
• 5: "RIS Raw Data." http://www.ripe.net/projects/ris/rawdata.html.
• 6: "Public route servers." http://www.bgp4.net.
• 7: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002.
• 8: R. Cohen and D. Raz, "The Internet dark matter - on the missing links in the as connectivity map," in Proc. IEEE INFOCOM, April 2006.
• 9: Y. He, G. Siganos, M. Faloutsos, and S. Krishnamurthy, "A systematic framework for unearthing the missing links: Measurements and impact," in Proc. NSDI, April 2007.
• 10: "CAIDA AS Relationships." http://as-rank.caida.org/data/.
• 11: Xenofontas Dimitropoulos , Dmitri Krioukov , Marina Fomenkov , Bradley Huffaker , Young Hyun , kc claffy , George Riley, AS relationships: inference and validation, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198259]
• 12: J. Xia and L. Gao, "On the Evaluation of AS Relationship Inferences," in Proc. IEEE Global Internet Symposium, 2000.
• 13: L. Gao, "On Inferring Autonomous System Relationships in the Internet," in Proc. IEEE Global Internet Symposium, 2000.
• 14: Z. Morley Mao , Lili Qiu , Jia Wang , Yin Zhang, On AS-level path inference, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 15: G. Battista, M. Patrignani, and M. Pizzonia, "Computing the Types of the Relationships Between Autonomous Systems," in Proc. IEEE INFOCOM, March 2003.
• 16: Wolfgang Mühlbauer , Steve Uhlig , Bingjie Fu , Mickael Meulle , Olaf Maennel, In search for an appropriate granularity to model routing policies, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 17: Xenofontas Dimitropoulos , George Riley, Modeling Autonomous-System Relationships, Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.143-149, May 24-26, 2006 [doi>10.1109/PADS.2006.26]
• 18: L. Gao, T. G. Griffin, and J. Rexford, "Inherently safe backup routing with BGP," in Proc. IEEE INFOCOM, 2001.
• 19: "Internet Routing Resilience Project Page." http://www.eecs.umich.edu/~wujz/irrf/.
• 20: S. M. Bellovin and E. R. Gansner, "Using Link Cuts to Attack Internet Routing." May 2003.
• 21: Jian Wu , Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang, Finding a needle in a haystack: pinpointing significant BGP routing changes in an IP network, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.1-14, May 02-04, 2005
• 22: "The backhoe: A real cyberthreat." http://www.wired.com/science/discoveries/news/2006/01/70040.
• 23: "ISP spat blacks out Net connections." http://www.networkworld.com.
• 24: "NANOG mailing list." http://www.merit.edu/mail.archives/nanog/.
• 25: "UUnet backbone problems slow down the Net." http://www.itworld.com.
• 26: "Impact of Hurricane Katrina on Internet infrastructure." http://www.renesys.com.
• 27: "PlanetLab." http://www.planet-lab.org.
• 28: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 29: "NetGeo - The Internet Geographic Database." http://www.caida.org/tools/utilities/netgeo/index.xml.
• 30: R. Albert, H. Jeong, and A.-L. Barabasi, "Error and attack tolerance of complex networks," Nature, 2000.
• 31: R. Cohen, K. Erezl, D. ben Avraham, and S. Havlin, "Resilience of the Internet to Random Breakdowns," Phys. Rev. Lett., 2000.
• 32: X. Zhao, B. Zhang, A. Terzis, D. Massey, and L. Zhang, "The Impact of Link Failure Location on Routing Dynamics: A Formal Analysis," in Proceedings of ACM SIGCOMM Asia Workshop, 2005.
• 33: Wolfgang Mühlbauer , Anja Feldmann , Olaf Maennel , Matthew Roughan , Steve Uhlig, Building an AS-topology model that captures route diversity, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 34: Renata Teixeira , Keith Marzullo , Stefan Savage , Geoffrey M. Voelker, Characterizing and measuring path diversity of internet topologies, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 35: T. Erlebach, A. Hall, L. Moonen, A. Panconesi, F. Spieksma, and D. Vukadinovic, "Robustness of the Internet at the Topology and Routing Level," Lecture Notes in Computer Science, vol. 4028, 2006.