Towards a Next Generation Inter-domain Routing Protocol

After a long period of neglect, there has been a recent resurgence of research on BGP, the current interdomain routing protocol. Some of these papers have provided valuable empirical data on the current state of inter-domain routing [3, 16, 13, 12, 14, 7]; others have proposed incremental modifications that would improve the status quo [15, 4]. However, there has been a relative paucity of papers exploring how to fundamentally redesign inter-domain routing. In this paper we venture into this void, proposing a clean-sheet redesign of BGP. Our proposal is a hybrid link-state path-vector routing protocol, called HLP, which we offer not as the final word on inter-domain routing but rather as a possible starting point for debates about the future architecture of inter-domain routing. There seems little disagreement that BGP is in need of eventual overhaul. In fact, the IRTF has convened two separate working groups to define the set of requirements for a future generation inter-domain routing protocol. From their combined set of specifications [9], we identified five problems of paramount importance, and describe the ways in which BGP fails to meet them: Scalability: Any future inter-domain routing protocol must gracefully accommodate the ongoing growth of the Internet. BGP fails this test, as its routing state and rate of churn (the rate at which routing announcements are received by a given router) grow linearly with the size of the network. Security: Given its critical role in today’s telecommunication infrastructure, it is paramount that the Internet be robust, both to benign misconfigurations and to malicious attacks. Unfortunately, as recent Internet outages have made clear, BGP, by blindly accepting as valid the routing announcements of peers, is vulnerable on both counts; a single compromised or misconfigured ∗EECS Department, University of California at Berkeley. Email:{lakme,mccaesar,ct-ee,istoica}@eecs.berkeley.edu †CS Department, University College, London. Email: mjh@cs.ucl.ac.uk ‡EECS Department, University of Michigan. Email:zmao@eecs.umich.edu §ICSI center for Internet Research, Berkeley. Email:shenker@icsi.berkeley.edu router can cause extensive damage by propagating bogus route advertisements. Convergence and Route Stability: To provide reliable reachability, Internet routes should be relatively stable and, when a change is necessary, the routes should quickly converge to their new steady-state. BGP, on the other hand, is known to suffer from significant route instabilities, route oscillations and long convergence times. Isolation: Isolation is related to the three issues discussed above, but important enough to single out. No design can be robustly scalable if a single localized fault can impact the entire network. In BGP, unfortunately, changes in a single route are frequently propagated globally and many updates observed at a router are largely a result of events far removed from the router. Diagnosis support: Routing protocols are designed to automatically adapt to faults, but they should also provide operators with enough information to quickly (and correctly) diagnose these faults, whether the cause is malicious or benign. BGP is notoriously deficient in this regard because the protocol conveys no information about the cause of a change or the intent of a peering. Also, the fact that a single failure or minor configuration change can be spread globally makes it difficult to localize the root-cause of routing problems. This listing of BGP’s flaws is hardly new, and several serious BGP flaws have already been dealt with by modest incremental modifications [15, 4, 19]. However, we contend that BGP’s basic protocol structure makes it inherently incapable of achieving the aforementioned goals. We make this argument by discussing, at a general level, five basic design issues (Section 2). For each issue we review BGP’s design choice, describe its impact on our goals, and then briefly describe HLP’s approach. We then give a more comprehensive and detailed description of HLP (Section 3), and conclude (Section 4) with a few comments about open questions.