## Abstract

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 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 language | English (US) |
---|---|

Pages | 189-196 |

Number of pages | 8 |

DOIs | |

State | Published - 2004 |

Externally published | Yes |

Event | Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing - St. John's, Nfld., Canada Duration: Jul 25 2004 → Jul 28 2004 |

### Conference

Conference | Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing |
---|---|

Country/Territory | Canada |

City | St. John's, Nfld. |

Period | 7/25/04 → 7/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