The Border Gateway Protocol (BGP) is the dominant inter-domain routing protocol in IP-based networks today. However, the requirements of emerging applications have exposed limitations in the current BGP protocol. In particular, 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 networks, 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 requirements posed on multi-domain QoS routing protocols that provide multiple classes of service with multidimensional QoS requirements and present how these requirements 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 decisions. 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 simulation results indicate the potential performance benefits of the introduced QoS enhancements to inter-domain routing.