TIE Breaking: Tunable Interdomain Egress Selection

Renata Teixeira, Timothy G. Griffin, Mauricio G. C. Resende, and Jennifer Rexford

IEEE/ACM Transactions on Networking,  vol. 15,  issue 4, pp. 761 - 774, 2007 [doi 10.1109/TNET.2007.893877]

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 two example optimization problems that use integer-programming and multicommodity-flow techniques, respectively, to tune our mechanism to satisfy network-wide objectives. Experiments with traffic, topology, and routing data from two backbone networks demonstrate that our solution is both simple (for the routers) and expressive (for the network administrators).
                                                                                
An earlier version of this paper appeared in CoNEXT'05.  The current paper adds the solution of the traffic engineering problem with TIE. We discuss and evaluate how to balance load in the network without changing the IGP metrics or BGP policies, by using multicommodity-flow techniques to move some traffic to different egress points. We have removed several simple examples of how to set the configurable parameters to manage a simple network to make space for the detailed analysis of the traffic engineering problem.


PDF file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 12 June 2008

Copyright Notice