Introduction

The Internet's two-tiered routing architecture was designed to have a clean separation between the intradomain and interdomain routing protocols. For example, the interdomain protocol allows the border routers to learn how to reach external destinations, whereas the intradomain protocol determines how to direct traffic from one router in the AS to another. However, the appropriate roles of the two protocols becomes unclear when the AS learns routes to a destination at multiple border routers--a situation that arises quite often today. Since service providers peer at multiple locations, essentially all of the traffic from customers to the rest of the Internet has multiple egress routers. In addition, many customers connect to their provider in multiple locations for fault tolerance and more flexible load balancing, resulting in multiple egress routers for these destinations as well. Selecting among multiple egress points is now a fundamental part of the Internet routing architecture, independent of the current set of routing protocols.

In the Internet today, border routers learn routes to destination prefixes via the Border Gateway Protocol (BGP). When multiple border routers have routes that are ``equally good'' in the BGP sense (e.g., local preference, AS path length, etc.), each router in the AS directs traffic to the closest border router, in terms of Interior Gateway Protocol (IGP) distances. This policy of early-exit or hot-potato routing is hard-coded in the BGP decision process implemented on each router [1]. Hot-potato routing allows a router to implement a simple decision rule, independently of the other routers, while ensuring that packets are forwarded to neighboring routers that have selected the same (closest) egress point. In addition, hot-potato routing tends to limit the consumption of bandwidth resources in the network by shuttling traffic to the next AS as early as possible.

We believe that the decision to select egress points based on IGP distances should be revisited, in light of the growing pressure to provide good, predictable communication performance for applications such as voice-over-IP, online gaming, and business transactions. We argue that hot-potato routing is:

• Too restrictive: The underlying mechanism dictates a particular policy rather than supporting the diverse performance objectives important to network administrators.

• Too disruptive: Small changes in IGP distances can sometimes lead to large shifts in traffic, long convergence delays, and BGP updates to neighboring domains [2,3].

• Too convoluted: Network administrators are forced to select IGP metrics that make ``BGP sense,'' rather than viewing the two parts of the routing system separately.

Selecting the egress point and computing the forwarding path to the egress point are two very distinct functions, and we believe that they should be decoupled. Paths inside the network should be selected based on some meaningful performance objective, whereas the egress selection should be flexible to support a broader set of traffic-engineering goals.

In this paper, we propose a new way for each router to select an egress point for a destination, by comparing the candidate egress points based on a weighted sum of the IGP distance and a constant term. The configurable weights provide flexibility in deciding whether (and how much) to base BGP decisions on the IGP metrics. Network management systems can apply optimization techniques to automatically set these weights to satisfy network-level objectives, such as balancing load and minimizing propagation delays. To ensure consistent forwarding through the network, we advocate the use of lightweight tunnels to direct traffic from the ingress router to the chosen egress point. Our new mechanism, called TIE (Tunable Interdomain Egress) because it controls how routers break ties between multiple equally-good BGP routes, is both simple (for the routers) and expressive (for the network administrators). Our solution does not introduce any new protocols or any changes to today's routing protocols, making it possible to deploy our ideas at one AS at a time and with only minimal changes to the BGP decision logic on IP routers. The paper makes the following research contributions:

• Flexible mechanism for egress-point selection: The TIE mechanism we propose is: (i) flexible in balancing the trade-off between sensitivity to IGP changes and adaptability to network events, (ii) computationally easy for the routers to execute in real time, and (iii) easy for a higher-level management system to optimize based on diverse network objectives.

• Optimization of network-wide objectives: We present example problems that can be solved easily using TIE. First, we show how to minimize sensitivity to internal topology changes, subject to a bound on propagation delay, using integer programming to tune the weights in our mechanism. Second, we show 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.

• Evaluation on two backbone networks: We evaluate the effectiveness of TIE for the two optimization problems, using traffic, topology, and routing data from two backbone networks (i.e., Abilene and a large tier-1 ISP). Our experiments show that TIE reduces sensitivity to internal topology changes while satisfying network-wide objectives for load and delay.

In the next section, we discuss the problems caused by hot-potato routing, and describe an alternative where each router has a fixed ranking of the egress points. Then, Section III presents the TIE mechanism for selecting egress points, along with several simple examples. Sections IV and V present the two optimization problems and evaluate our solutions on topology, traffic, and routing data from two backbone networks. In Section VI, we discuss how to limit the number of configurable parameters and how to deploy TIE without changing the existing routing protocols. After a brief overview of related work in Section VII, we conclude the paper in Section VIII with a discussion of future research directions. An Appendix describes how we determine the network topology, egress sets, and traffic demands from the measurement data collected from the two backbone networks.