MIRO: Multi-path Interdomain ROutingWen Xu and Jennifer RexfordDepartment of Computer SciencePrinceton UniversityABSTRACTThe Internet consists of thousands of independent domains withdifferent, and sometimes competing, business interests. However,the current interdomain routing protocol (BGP) limits each routerto using a single route for each destination prefix, which may notsatisfy the diverse requirements of end users. Recent proposals forsource routing offer an alternative where end hosts or edge routersselect the end-to-end paths. However, source routing leaves transitdomains with very little control and introduces difficult scalabilityand security challenges. In thispaper, we present a multi-path inter-domain routing protocol called MIRO that offers substantial flexi-bility, while giving transit domains control over the flow of trafficthrough their infrastructure and avoiding state explosion in dissem-inating reachability information. In MIRO, routers learn defaultroutes through the existing BGP protocol, and arbitrary pairs of do-mains can negotiate the use of additional paths (bound to tunnelsin the data plane) tailored to their special needs. MIRO retains thesimplicity of BGP for most traffic, and remains backwards compat-ible with BGP to allow for incremental deployability. Experimentswith Internet topology and routing data illustrate that MIRO offerstremendous flexibility for path selection with reasonable overhead.Categories and Subject Descriptors:C.2.6 [Communication Networks]: InternetworkingGeneral Terms: Design, Experimentation.Keywords: BGP, flexibility, inter-domain routing, multipath rout-ing, scalability.1. INTRODUCTIONThe Internet consists of thousands of independently administereddomains (or Autonomous Systems) that rely on the Border Gate-way Protocol (BGP) to learn how to reach remote destinations. Al-though BGP allows ASes to apply a wide range of routing policies,the protocol requires each router to select a single “best” route foreach destination prefix from the routes advertised by its neighbors.This leaves many ASes with little control over the paths their traffictakes. For example, an AS might want to avoid paths traversing anAS known to have bad performance or filter data packets based onPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’06, September 11–15, 2006, Pisa, Italy.Copyright 2006 ACM 1-59593-308-5/06/0009 ...$5.00.DB CEFAFigure 1: Single-path routing to AS Ftheir contents. This is the situation in Figure 1, where thick linesrepresent the paths chosen to reach AS F. AS A does not want AS Eto carry its traffic, but it has no choice because B and D have bothselected paths through E. Simply asking B to switch to the routeBCF is not an attractive solution, since this would not allow AS Band its other neighbors to continue using BEF.Recent research has considered several alternatives to single-path routing, including source routing and overlay networks. Insource routing, an end user or AS picks the entire path the pack-ets traverse [1–5]. In overlay networks, packets can travel throughintermediate hosts to avoid performance or reliability problems onthe direct path [6]. However, these techniques do not give transitASes, such as Internet Service Providers (ISPs), much control overthe traffic traversing their networks. This control is important forASes to engineer their networks to run efficiently, and to maximizerevenue. The lack of control for ISPs is a significant impedimentto the eventual adoption of source routing. In addition, both sourcerouting and overlay networks may not scale to a network the sizeof the Internet. Instead, we explore an alternative solution wherethe interdomain routing protocol supports multi-path routing, whileproviding flexible control for transit ASes and avoiding state explo-sion in disseminating routing information.Our solution is motivated by several observations about today’sinterdomain-routing system:• Having each router select and advertise a single route foreach prefix is not flexible enough to satisfy the diverse per-formance and security requirements. In Figure 1, today’srouting system does not enable AS A to circumvent AS Ein sending traffic to AS F.• The existing routes chosen by BGP are sufficient for a largeportion of the traffic. In Figure 1, AS B and its other cus-tomers may be perfectly happy with the path BEF.• End users need control over the properties of the end-to-endpath, rather than complete control over which path is taken.In Figure 1, AS A only wants to avoid AS E and does notcare about the rest of the path.• The existing BGP protocol already provides many candidateroutes, although the alternate routes are not disseminated. InFigure 1, AS B has learned the route BCF but simply has notannounced it to AS A.• An AS selects routes based on business relationships withneighboring domains, but might be willing to direct trafficto other paths, for a price. In Figure 1, AS B may preferBEF for financial reasons, but may be willing to send AS A’straffic over BCF.• Today’s Internet provides limited methods for one AS to in-fluence another AS’s choice. For example, if AS F is a multi-homed stub AS which wants to control how much incomingtraffic traverse link CF and EF respectively, it can only adver-tise smaller prefixes or prepend its AS number [7]. Howeverthose methods may be easily nullified by other ASes’ localpolicy, making their effectiveness limited.Inspired by these observations, we propose a multi-path interdo-main routing protocol, called MIRO, with the following features:• AS-level path selection: An AS represents an institution,such as a university or company, and business relationshipsare easily defined at the AS level. This is simpler and morescalable than giving each end user fine-grain control overpath selection.• Negotiation for alternate routes: An AS learns one routefrom each neighbor and negotiates to learn alternate routesas needed. This leads to a scalable solution that is backwardscompatible with BGP, and it also allows policy interactionbetween arbitrary pairs of ASes.• Policy-driven