Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs

Jie Gao, Li Zhang

Research output: Contribution to conferencePaperpeer-review

15 Scopus citations

Abstract

A graph has growth rate k if the number of nodes in any subgraph with diameter r is bounded by O(rk). 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 p, 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, 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). 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.

Original languageEnglish (US)
Pages189-196
Number of pages8
DOIs
StatePublished - 2004
Externally publishedYes
EventProceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing - St. John's, Nfld., Canada
Duration: Jul 25 2004Jul 28 2004

Conference

ConferenceProceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing
Country/TerritoryCanada
CitySt. John's, Nfld.
Period7/25/047/28/04

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Growth restricted graphs
  • Load balancing
  • Routing
  • Wireless networks

Fingerprint

Dive into the research topics of 'Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs'. Together they form a unique fingerprint.

Cite this