Impact of hot-potato routing changes in IP networks

ABSTRACT

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, a router selects the one with the closest egress point, based on the intradomain path cost. Under such hot-potato routing, an intradomain event can trigger BGP routing changes. To characterize the influence of hot-potato routing, we propose a technique for associating BGP routing changes with events visible in the intradomain protocol, and apply our algorithm to a tier-1 ISP backbone network. We show that (i) BGP updates can lag 60 seconds or more behind the intradomain event; (ii) the number of BGP path changes triggered by hot-potato routing has a nearly uniform distribution across destination prefixes; and (iii) the fraction of BGP messages triggered by intradomain changes varies significantly across time and router locations. We show that hot-potato routing changes lead to longer delays in forwarding-plane convergence, shifts in the flow of traffic to neighboring domains, extra externally-visible BGP update messages, and inaccuracies in Internet performance measurements.

REFERENCES

• 1: Y. Rekhter, T. Li, and S. Hares, "A border gateway protocol 4 (BGP-4)," RFC 4271, Jan. 2006.
• 2: J. Moy, "OSPF version 2," RFC 2328, Apr. 1998.
• 3: R. W. Callon, Use of OSI IS-IS for routing in TCP/IP and dual environments, RFC Editor, 1990
• 4: David Watson , Farnam Jahanian , Craig Labovitz, Experiences With Monitoring OSPF on a Regional Service Provider Network, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.204, May 19-22, 2003
• 5: Aman Shaikh , Chris Isett , Albert Greenberg , Matthew Roughan , Joel Gottlieb, A case study of OSPF behavior in a large enterprise network, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637236]
• 6: Gianluca Iannaccone , Chen-nee Chuah , Richard Mortier , Supratik Bhattacharyya , Christophe Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637238]
• 7: Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
• 8: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 9: Sharad Agarwal , Chen-Nee Chuah , Supratik Bhattacharyya , Christophe Diot, The impact of BGP dynamics on intra-domain traffic, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 10: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
• 11: J. Scudder, "BGP Monitoring Protocol," Expired Internet Draft, draft-scudder-bmp00.txt, 2005.
• 12: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]
• 13: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002
• 14: Sam Halabi , Danny McPherson, Internet Routing Architectures, Second Edition, Cisco Systems, 2000
• 15: Aman Shaikh , Albert Greenberg, OSPF monitoring: architecture, design and deployment experience, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.5-5, March 29-31, 2004, San Francisco, California
• 16: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 17: Configure Router Calculation Timers. Cisco [Online]. Available: http://www.cisco.com/univercd/cc/td/doc/product/software/ios120/12cgcr/np1_c/1cprt1/1cospf.html#xtocid2712621
• 18: Understanding BGP Processes on Cisco. Cisco [Online]. Available: http://www.cisco.com/warp/public/459/highcpu-bgp.html#topic1
• 19: C. Rossenhovel, "40-Gig Router Test Results," Light Reading, Nov. 2004 [Online]. Available: http://www.lightreading.com/document.asp?site=testing&doc_id=63606&page%_number=6
• 20: Renata Teixeira , Aman Shaikh , Tim Griffin , Geoffrey M. Voelker, Network sensitivity to hot-potato disruptions, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 21: B. Quoitin and S. Uhlig, "Modeling the routing of an autonomous system with C-BGP," IEEE Network Mag., vol. 19, Nov. 2005.
• 22: G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP restoration in a tier-1 backbone," IEEE Network Mag., Mar. 2004.
• 23: R. Teixeira and J. Rexford, "Managing routing disruptions in internet service provider networks," IEEE Commun. Mag., Mar. 2006.
• 24: Sampled Netflow. Cisco [Online]. Available: http://www.cisco.com/ univercd/cc/td/doc/product/software/ios120/120newft/120limit/120s/ 120s11/12s_sanf.htm
• 25: R. Teixeira, N. Duffield, J. Rexford, and M. Roughan, "Traffic matrix reloaded: Impact of routing changes," in Proc. Passive and Active Measurement Workshop, Boston, MA, Mar. 2005, Lecture Notes in Computer Science, vol. 3431, pp. 251-264.
• 26: Urs Hengartner , Sue Moon , Richard Mortier , Christophe Diot, Detection and analysis of routing loops in packet traces, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637217]
• 27: C. Alaettinoglu, V. Jacobson, and H. Yu, "Toward milli-second IGP convergence," Expired Internet Draft, draft-alaettinoglu-isis-convergence-00.txt, 2000.
• 28: Pierre Francois , Clarence Filsfils , John Evans , Olivier Bonaventure, Achieving sub-second IGP convergence in large IP networks, ACM SIGCOMM Computer Communication Review, v.35 n.3, July 2005 [doi>10.1145/1070873.1070877]
• 29: Route Views Project. [Online]. Available: http://www.routeviews.org
• 30: RIPE NCC RIS. [Online]. Available: http://www.ripe.net/ripencc/pub-services/np/ris-index.html
• 31: M. Caesar, L. Subramanian, and R. H. Katz, "Towards localizing root causes of BGP dynamics," UC, Berkeley, Tech. Rep. CSD-03-1292, 2003.
• 32: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 33: Renata Teixeira , Jennifer Rexford, A measurement framework for pin-pointing routing changes, Proceedings of the ACM SIGCOMM workshop on Network troubleshooting: research, theory and operations practice meet malfunctioning reality, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016687.1016704]
• 34: 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
• 35: Sharad Agarwal , Antonio Nucci , Supratik Bhattacharyya, Measuring the Shared Fate of IGP Engineering and Interdomain Traffic, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.236-245, November 06-09, 2005 [doi>10.1109/ICNP.2005.22]
• 36: Renata Teixeira , Timothy G. Griffin , Mauricio G. C. Resende , Jennifer Rexford, TIE breaking: tunable interdomain egress selection, IEEE/ACM Transactions on Networking (TON), v.15 n.4, p.761-774, August 2007 [doi>10.1109/TNET.2007.893877]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Performance attributes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Measurement, Performance