Given the weighted graph G(V,E), where weights represent links' bandwidths. We define the Quality of Service Routing Tree (QoSRT) for G as a subgraph G'(V,E') such that G' is a tree, and for any pair of nodes u and v in G' there exist a path between u and v, where all intermediate edges form a subset of E', and the bottleneck of the path is maximized. In this paper, we propose a distributed algorithm to construct a QoSRT that adapts quickly to changes in links' bandwidths. The QoSRT is uniquely constructed for maintenance purposes, so a change to a link's bandwidth is handled within the local subtree. Then we propose both reactive and proactive routing schemes based on the QoSRT. A virtual backbone (VBB) which consists of a subset of the nodes is responsible for routing tables in the case of proactive routing. The QoSRT and its VBB are constructed using O(nlog n) messages in O(nlog n) time.