Tradeoffs between Stretch Factor and Load Balancing Ratio in Routing on Growth Restricted Graphs

摘要

A graph has growth rate k if the number of nodes in any subgraph with diameter r is bounded by O(r~k). The communication graphs of wireless networks and peer-to-peer networks often have small growth rate. In this paper we study the tradeoff between two quality measures for routing in growth restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load balancing ratio, which measures how evenly the traffic is distributed. We show that if the routing algorithm is required to use paths with stretch factor c, then its load balancing ratio is bounded by O((n/c)~(1-1/k)), where k is the graph's growth rate. We illustrate our results by focusing on the unit disk graph for modeling wireless networks in which two nodes have direct communication if their distance is under certain threshold. We show that if the maximum density of the nodes is bounded by ρ, there exists routing scheme such that the stretch factor of routing paths is at most c, and the maximum load on the nodes is at most O(min((ρn/c)~(1/2), n/c)) times the optimum. In addition, the bound on the load balancing ratio is tight in the worst case. As a special case, when the density is bounded by a constant, the shortest path routing has a load balancing ratio of O(n~(1/2)). The result extends to k-dimensional unit ball graphs and graphs with growth rate k. We also discuss algorithmic issues for load balanced short path routing and for load balanced routing in spanner graphs.