Being an important and yet a challenging problem, the QoS-based routing in the converging Internet has received significant attention from the research community. However, most of the QoS-based routing research is conducted in the context of intra-domain routing, leaving QoS-based inter-domain routing relatively open. In this paper, we focus on QoS-based inter-domain routing and specifically investigate how to enhance the current inter-domain routing protocol (BGP) with QoS extensions. To support multiple QoS metrics, BGP speakers have to advertise multiple routes for each destination. However, this will increase the routing message overhead and make QoS-aware BGP unscalable. To provide scalability without significantly sacrificing the performance, we propose path reduction algorithms called contribution based reduction (CBR) algorithms. Extensive simulations show that the proposed schemes achieve high performance in finding feasible paths with low complexity in terms of message overhead and computation, making the QoS extension to BGP scalable. However, most of the QoS-based routing research has been conducted in the context of intra-domain routing, leaving QoS -based inter-domain routing relatively open. In this paper, we focus on QoS-based inter-domain routing and specifically investigate how to enhance the current inter-domain routing protocol (BGP) with QoS extensions. To support multiple QoS metrics, BGP However, this will increase the routing message overhead and make QoS-aware BGP unscalable. To provide scalability without significantly sacrificing the performance, we propose path reduction algorithms called contribution based reduction (CBR) algorithms. Extensive simulations show that the proposed schemes achieve high performance in finding feasible paths with low complexity in terms of message overhe ad and computation, making the QoS extension to BGP scalable.