| Given the weighted graph G(V,E), let the weight of each link represents the bandwidth of that link. We define a Quality of Service Routing Tree (QoSRT) for the weighted graph G(V,E), 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, with all edges from E′, and the bottleneck of the path is maximized. We also define a virtual backbone (VBB) for the graph G′(V,E′) as a connected subgraph G′′(V′,E′), where V′⊆V, and each node in V is either in V′ or adjacent to at least one node in V′. In this paper, we propose a novel distributed algorithm to construct a QoSRT and its corresponding VBB. Both reactive and proactive efficient routing schemes are proposed to run over the QoSRT and its VBB, and to provide an optimal QoS path for any pair of nodes in the graph. The nodes of the VBB maintain the routing tables for proactive routing, and manage the routing discovery for reactive routing. The QoSRT and its VBB are constructed with optimal O(nlog n) messages. |