TIE breaking: tunable interdomain egress selection

ABSTRACT

The separation of intradomain and interdomain routing has been a key feature of the Internet's routing architecture from the early days of the ARPAnet. However, the appropriate "division of labor" between the two protocols becomes unclear when an Autonomous System (AS) has interdomain routes to a destination prefix through multiple border routers---a situation that is extremely common today because neighboring domains often connect in several locations. We believe that the current mechanism of early-exit or hot-potato routing---where each router in an AS directs traffic to the "closest" border router based on the intradomain path costs---is convoluted, restrictive, and sometimes quite disruptive. In this paper, we propose a flexible mechanism for routers to select the egress point for each destination prefix, allowing network administrators to satisfy diverse goals, such as traffic engineering and robustness to equipment failures. We present one example optimization problem that uses integer-programming techniques to tune our mechanism to improve network robustness. Experiments with topology and routing data from two backbone networks demonstrate that our solution is both simple (for the routers) and expressive (for the network administrators).

REFERENCES

• 1: Y. Rekhter, T. Li, and S. Hares, "A Border Gateway Protocol 4 (BGP-4)." Internet Draft draft-ietf-idr-bgp4-26.txt, October 2004.
• 2: 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
• 3: R. Teixeira, N. Duffield, J. Rexford, and M. Roughan, "Traffic matrix reloaded: Impact of routing changes," in Proc. Passive and Active Measurement Workshop, March/April 2005.
• 4: 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]
• 5: G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP Restoration in a Tier-1 Backbone," IEEE Network Magazine, March 2004.
• 6: B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS Weights in a Changing World," IEEE J. Selected Areas in Communications, vol. 20, no. 4, pp. 756--767, 2002.
• 7: Lorenz Dean H. , Orda Ariel , Raz Danny , Author:, How good can IP routing be?, Certer for Discrete Mathematics & Theoretical Computer Science, 2001
• 8: B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, March 2000.
• 9: B. Fortz, J. Rexford, and M. Thorup, "Traffic Engineering with Traditional IP Routing Protocols," IEEE Communication Magazine, October 2002.
• 10: M. Ericsson, M. Resende, and P. Pardalos, "A genetic algorithm for the weight setting problem in OSPF routing," Journal of Combinatorial Optimization, vol. 6, pp. 299--333, 2002.
• 11: L. Buriol, M. Resende, C. Ribeiro, and M. Thorup, "A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing," Tech. Rep. TD-5NTN5G, AT&T Labs Research, 2003.
• 12: Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 13: S. Uhlig, "A multiple-objectives evolutionary perspective to interdomain traffic engineering in the Internet," in Workshop on Nature Inspired Approaches to Networks and Telecommunications, September 2004.
• 14: A. Nucci, B. Schroeder, N. Taft, and C. Diot, "IGP Link Weight Assignment for Transient Link Failures," in Proc. International Teletraffic Congress, August 2003.
• 15: B. Fortz and M. Thorup, "Robust optimization of OSPF/IS-IS weights," in Proc. International Network Optimization Conference, pp. 225--230, October 2003.
• 16: A. Sridharan and R. Guerin, "Making OSPF/IS-IS routing robust to link failures," in Proc. Networking'2005, (Ontario, Canada), May 2005.
• 17: E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol Label Switching Architecture." RFC 3031, January 2001.
• 18: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 19: Ilog S.A.,"Ilog Cplex 9.0 User's Manual", October 2003.
• 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: R. Teixeira, T. Griffin, M. Resende, and J. Rexford, "TIE Breaking: Tunable Interdomain Egress Selection," Tech. Rep. TD-69EJBE, AT&T Labs Research, February 2005.
• 22: Nick Feamster , Hari Balakrishnan , Jennifer Rexford , Aman Shaikh , Jacobus van der Merwe, The case for separating routing from routers, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016707.1016709]
• 23: O. Bonaventure, S. Uhlig, and B. Quoitin, "The Case for More Versatile BGP Route Reflectors." Internet Draft draft-bonaventure-bgp-route-reflectors-00.txt, July 2004.
• 24: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 25: Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 26: D. McPherson, V. Gill, D. Walton, and A. Retana, "Border gateway protocol (BGP) persistent route oscillation condition." RFC 3345, August 2002.
• 27: R. Chandra, P. Traina, and T. Li, "BGP communities attribute." RFC 1997, August 1996.
• 28: BGP policy accounting." http://www.cisco.com/univercd/cc/td/doc/product/software/ios122/122newf%t/122t/122t13/ft_bgppa.htm.
• 29: BGP cost community." http://www.cisco.com/en/US/products/sw/iosswrel/ps5207/products_feature%_guide09186a00801a7f74.html.
• 30: D. Katz, K. Kompela, and D. Yeung, "Traffic Engineering (TE) Extensions to OSPF Version 2." RFC 3630, September 2003.
• 31: H. Smit, "Intermediate System to Intermediate System (IS-IS) Extensions for Traffic Engineering (TE)." RFC 3784, June 2004.
• 32: D. Awduche, "MPLS and Traffic Engineering in IP Networks," IEEE Communication Magazine, December 1999.
• 33: Srikanth Kandula , Dina Katabi , Bruce Davie , Anna Charny, Walking the tightrope: responsive yet stable traffic engineering, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 34: T. Bressoud, R. Rastogi, and M. Smith, "Optimal configuration of BGP route selection," in Proc. IEEE INFOCOM, 2003.
• 35: Aditya Akella , Bruce Maggs , Srinivasan Seshan , Anees Shaikh , Ramesh Sitaraman, A measurement-based analysis of multihoming, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863995]
• 36: David K. Goldenberg , Lili Qiuy , Haiyong Xie , Yang Richard Yang , Yin Zhang, Optimizing cost and performance for multihoming, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 37: R. Mahajan, D. Wetherall, and T. Anderson, "Negotiation-based routing between neighboring ISPs," in Proc. USENIX Symposium on Networked Systems Design and Implementation, May 2005.
• 38: J. Winick, S. Jamin, and J. Rexford, "Traffic engineering between neighboring domains." http://www.cs.princeton.edu/ jrex/papers/interAS.pdf, July 2002.
• 39: Abilene Backbone Network." http://abilene.internet2.edu/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.3 Network Operations
          Subjects: Network management

General Terms:
Algorithms, Design, Management, Measurement, Performance

Keywords:
BGP, egress-point selection