Trade-Offs between Stretch Factor and Load-Balancing Ratio in Routing on Growth-Restricted Graphs

Jie Gao, Li Zhang

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

An unweighted graph has density p and growth rate k if the number of nodes in every ball with radius r is bounded by prk. The communication graphs of wireless networks and peer-to-peer networks often have constant bounded density and small growth rate. In this paper, we study the trade-off 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 the evenness of the traffic distribution. 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(ρ1/k(n/c)1–1/k), and the bound is tight in the worst case. We show the application and extension of the trade-off to the wireless network routing and VLSI layout design. We also present a load-balanced routing algorithm with the stretch factor constraint in an online setting, in which the routing requests come one by one.

Original languageEnglish (US)
Pages (from-to)171-179
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Volume20
Issue number2
DOIs
StatePublished - Feb 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Routing
  • growth-restricted graphs
  • load balancing
  • wireless networks

Fingerprint

Dive into the research topics of 'Trade-Offs between Stretch Factor and Load-Balancing Ratio in Routing on Growth-Restricted Graphs'. Together they form a unique fingerprint.

Cite this