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 specifically investigate how to extend the current inter-domain routing protocol (BGP) to support multiple QoS metrics. With multiple metrics, a BGP speaker has to advertise multiple routes for each destination to its peer. This will increase the routing message overhead and make QoS-aware BGP unscalable to large networks. Therefore, our focus in this paper is to bring QoS extensions to the original BGP while simultaneously providing high performance and scalability. In response to this, we propose path reduction algorithms, i.e., Contribution Based Reduction (CBR) algorithms, to reduce the number of routes advertised by BGP speakers while maximizing the routing success ratio. Extensive simulations show that our schemes achieve high performance with low complexity in terms of message overhead and computation, making the QoS extension to BGP scalable.