The scalability of routing in large scale networks, such as the Interne, is critical to achieve low delay and high throughput. The lack of scalability of routing protocols in large-scale networks results from the prohibitive overhead incurred during dissemination of path metric values across the network. This paper addresses this problem and proposes a cluster-based scheme, referred to as d-median, which strikes a balance between scalability and routing efficiency. In this scheme, the link metric information is exchanged on a per-cluster basis, rather than on a per-node basis thereby reducing considerably the routing overhead. The simulation results show that the scheme exhibits better performance compared to existing models.