1 of 7 QoS ENHANCEMENTS TO BGP IN SUPPORT OF MULTIPLE CLASSES OF SERVICE Lotfi Benmohamed 1, Chieh-Jan Mike Liang 2, Eric Naber 1, Andreas Terzis 2 1 Johns Hopkins University Applied Physics Laboratory Laurel, Maryland, USA 2 Johns Hopkins University Computer Science Department Baltimore, Maryland, USA ABSTRACT The Border Gateway Protocol (BGP) is the dominant in-ter-domain routing protocol in IP-based networks today. However, the requirements of emerging applications have exposed limitations in the current BGP protocol. In par-ticular, future military IP networks, exemplified by the Global Information Grid (GIG), will carry a diverse mix of applications with widely different Quality of Service (QoS) requirements. At the same time, the GIG includes a diverse set of component networks, such as tactical ad-hoc net-works, with highly dynamic QoS characteristics. In this paper we investigate the problem of enhancing BGP to discover routing paths with QoS characteristics that match application requirements. We explore the re-quirements posed on multi-domain QoS routing protocols that provide multiple classes of service with multi-dimensional QoS requirements and present how these re-quirements map to BGP. We discuss enhancements to BGP that allow nodes to discover multiple paths with associated QoS attributes. In particular, we discuss a dominant path selection algorithm that allows nodes to discover the minimum set of paths needed to make QoS routing deci-sions. We present details of the proposed BGP changes and identify the modifications needed at each stage of the BGP path selection process. We implemented the proposed enhancements in the NS-2 simulator. Preliminary simula-tion results indicate the potential performance benefits of the introduced QoS enhancements to inter-domain routing. 1. INTRODUCTION The Border Gateway Protocol (BGP) is the ubiquitous in-ter-domain routing protocol used to exchange reachability information among the Internet's Autonomous Systems (ASes). Given that BGP must operate in Internet-wide scale, it must generate minimal traffic overhead as well as have minimal routing state requirements. Moreover, it needs to account for restrictions imposed by commercial relationships among Internet Service Providers and be-tween providers and their customers. Finally, the reluc-tance of competing service providers to share details of their network internals further limits the type of informa-tion that can be exchanged. For these reasons, BGP is a path vector protocol: the only information sent by an AS to its neighbors is the set of network prefixes reachable from that AS and, for each such prefix, the sequence of ASes on the path to that destination. BGP is a single-path routing protocol, meaning that at most one route is advertised by an AS for any given desti-nation. Specifically, after an AS (more accurately a router at the boundary between two ASes running BGP) receives multiple advertisements (UPDATEs in BGP parlance) from its upstream neighbors, it applies its routing policies to select the single neighbor used to reach that destination, and finally advertises this decision to its downstream neighbors. In this respect, BGP is application-agnostic be-cause all traffic to a particular destination follows the same path. On the other hand, IP networks currently under de-velopment for civilian as well as military operations, will carry a mix of applications with diverse Quality of Service (QoS) requirements. At the same time, some of these internets will have a diverse set of component networks (wireless and wireline, fixed and mobile with different de-grees of mobility, long lived and short term) and some of the component networks will be very dynamic in their ser-vice capabilities. Thus, different end-to-end routes be-tween the same end points may offer very different QoS capabilities and these may vary over time. As a result, the ability to select among multiple routing paths based on the applications' QoS requirements will become an important need in emerging IP networks, especially in networks such as the Global Information Grid (GIG). In our previous work, we proposed a set of extensions to the BGP protocol designed to expose paths with diverse QoS attributes to end-user applications [1]. Specifically, we allow for more than one route to be propagated in BGP UPDATE messages and the information propagated in-volves more QoS metrics than a simple sequence of ASes. In this follow-up work we report our results from an im-plementation of the proposed extensions based on the popular NS-2 network simulator. Our results indicate that2 of 7 Figure 1. Support for an application class whose relevant metrics are bandwidth and propagation delay. the proposed extensions can indeed calculate the sets of dominant paths to each destination with only a moderate increase in overhead. The rest of the paper is structured as follows: In Section 2 we summarize the proposed extensions while in Section 3 we provide a proof showing that the extensions can accu-rately detect the list of dominant paths for each destination. Section 4 elaborates on our implementation and Section 5 presents our evaluation results. We close with a summary in Section 6. 2. BGP ENHANCEMENTS There are five enhancements to BGP that enable multi-path and QoS-aware routing: (1) exchanging potentially multiple paths per prefix, (2) maintaining QoS parameters for each path, (3) pruning the set of known paths to a dominant set while maintaining optimality, (4) choosing a particular path from this dominant set that best satisfies the unique QoS requirements of a particular application, and (5) enforcing the selected path. Enhancements (1), (2), (3), and (5) were discussed in-depth in our previous work [1]. As such, we will briefly review these four enhancements and then focus on fourth enhancement. 2.1. REVIEW BGP restricts each router to advertise to its neighbors only one route per destination prefix. This information hiding behavior can prevent a router from learning the particular path that most appropriately provides the QoS require-ments for a given traffic class. Enhancement (1) removes this limitation, allowing each BGP router to advertise a set of dominant paths. The notion of dominant paths is im-plemented through enhancement (3), and it prevents each BGP router from advertising every path it knows. Domi-nant paths are selected by the dominant path selection al-gorithm (DPSA), which is discussed