Article

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

Authors:

Li ZhangAuthors Info & Claims

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

Pages 189 - 196

https://doi.org/10.1145/1011767.1011795

Published: 25 July 2004 Publication History

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 ρ, 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.

References

[1]

M. Andrews, D. Bhatia, T. Leighton, F. Makedon, C. H. Norton, and L. Zhang. Improved algorithms for routing on two-dimensional grids. Unpublished.

[2]

R. K. Anupam Gupta and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proc. 44th Symposium on Foundations of Computer Science (FOCS '03), pages 534--543, 2003.

Digital Library

[3]

J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line machine scheduling with applications to load balancing and virtual circuit routing. In Proc. 25th ACM Symposium on Theory of Computing, pages 623--631, 1993.

Digital Library

[4]

B. Awerbuch, Y. Azar, and S. A. Plotkin. Throughput-competitive on-line routing. In IEEE Symposium on Foundations of Computer Science, pages 32--40, 1993.

Digital Library

[5]

Y. Azar. On-line load balancing. In A. Fiat and G. Woeginger, editors, On-line Algorithms: The State of the Art, pages 178--195. LNCS 1442, Springer, 1998.

Digital Library

[6]

H. Badr and S. Podar. An optimal shortest-path routing policy for network computers with regular mesh-connected topologies. IEEE Transactions on Computers, 38(10):1362--1371, 1989.

Digital Library

[7]

Y. Bartal and S. Leonardi. On-line routing in all-optical networks. Theoretical Computer Science, 221(1--2):19--39, 1999.

Digital Library

[8]

A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.

Digital Library

[9]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1994.

Digital Library

[10]

D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry. North-Holland, 2000.

[11]

J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Discrete mobile centers. Discrete and Computational Geometry, 30(1):45--63, 2003.

[12]

J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Geometric spanner for routing in mobile networks. In Proc. 2nd ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 01'), pages 45--55, 2001.

Digital Library

[13]

J. Gao and L. Zhang. Load balanced short path routing in wireless networks. In Proc. IEEE INFOCOM'04, 2004.

[14]

A. Goldsmith and S. Wicker, editors. Special Issue: Energy-aware ad hoc wireless networks, volume 9. IEEE Wireless Comm., Auguest 2002.

Digital Library

[15]

C. E. Jones, K. M. Sivalingam, P. Agrawal, and J.-C. Chen. A survey of energy efficient network protocols for wireless networks. Wireless Networks, 7(4):343--358, 2001.

Digital Library

[16]

D. Karger and M. Ruhl. Find nearest neighbors in growth-restricted metrics. In Proc. ACM Symposium on Theory of Computing, pages 741--750, 2002.

Digital Library

[17]

R. Krauthgamer and J. R. Lee. The intrinsic dimensionality of graphs. In Proceedings of the 35th ACM symposium on Theory of computing, pages 438--447. ACM Press, 2003.

Digital Library

[18]

F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in Ocongestion+dilation steps. Combinatorica, 14:167--186, 1994.

[19]

T. Leighton. Methods for message routing in parallel machines. Theoretical Computer Science, 128(1--2):31--62, 1994.

Digital Library

[20]

X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed construction of planar spanner and routing for ad hoc networks. In IEEE INFOCOM, pages 1268--1277, 2002.

[21]

C. Mead and L. Conway. Introduction to VLSI systems. Addison-Wesley, 1980.

Digital Library

[22]

F. Meyer auf de Heide, C. Schindelhauer, K. Volbert, and M. Grünewald. Energy, congestion and dilation in radio networks. In Proceedings of the 14th ACM symposium on Parallel algorithms and architectures, pages 230--237. ACM Press, 2002.

Digital Library

[23]

E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proc. IEEE INFOCOM, pages 170--179, 2002.

[24]

C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. ACM Symposium on Parallel Algorithms and Architectures, pages 311--320, 1997.

Digital Library

[25]

P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comp. and System Sciences, pages 130--143, 1988.

Digital Library

[26]

P. Raghavan and C. D. Thompson. Provably good routing in graphs: regular arrays. In Proceedings of the 17th annual ACM Symposium on Theory of Computing, pages 79--87, 1985.

Digital Library

[27]

T.-H. Yeh, C.-M. Kuo, C.-L. Lei, and H.-C. Yen. Competitive source routing on tori and meshes. In ISAAC: 8th International Symposium on Algorithms and Computation, pages 82--91, 1997.

Digital Library

Cited By

Renda MResta GSanti P(2012)Load Balancing Hashing in Geographic Hash TablesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.29623:8(1508-1519)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.296
Gawrilow EKlimm MMöhring RStenzel B(2012)Conflict-free vehicle routingEURO Journal on Transportation and Logistics10.1007/s13676-012-0008-71:1-2(87-111)Online publication date: 8-May-2012
https://doi.org/10.1007/s13676-012-0008-7
Busch CMagdon-Ismail M(2012)Optimal Oblivious Routing in Hole-Free NetworksQuality, Reliability, Security and Robustness in Heterogeneous Networks10.1007/978-3-642-29222-4_30(421-437)Online publication date: 2012
https://doi.org/10.1007/978-3-642-29222-4_30
Show More Cited By

Index Terms

Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms

Recommendations

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

An unweighted graph has density \rho and growth rate k if the number of nodes in every ball with radius r is bounded by \rho r^{k}. The communication graphs of wireless networks and peer-to-peer networks often have constant bounded density and small ...
Routing with load balancing: increasing the guaranteed node traffics

In this paper we introduce the novel routing scheme based on load balancing and shortest-path routing. First, we present the linear program for routing optimization. The nonblocking network is considered, which only limits the traffic loads of the ...
Load balancing routing with bounded stretch
Special issue on wireless network algorithms, systems, and applications

Routing in wireless networks has been heavily studied in the last decade. Many routing protocols are based on classic shortest path algorithms. However, shortest path-based routing protocols suffer from uneven load distribution in the network, such as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

July 2004

422 pages

ISBN:1581138024

DOI:10.1145/1011767

General Chair:
Soma Chaudhuri
Iowa State University
,
Program Chair:
Shay Kutten
Technion

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC04

Sponsor:

PODC04: Principles of Distributed Computing 2004

July 25 - 28, 2004

Newfoundland, St. John's, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
491
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Renda MResta GSanti P(2012)Load Balancing Hashing in Geographic Hash TablesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.29623:8(1508-1519)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.296
Gawrilow EKlimm MMöhring RStenzel B(2012)Conflict-free vehicle routingEURO Journal on Transportation and Logistics10.1007/s13676-012-0008-71:1-2(87-111)Online publication date: 8-May-2012
https://doi.org/10.1007/s13676-012-0008-7
Busch CMagdon-Ismail M(2012)Optimal Oblivious Routing in Hole-Free NetworksQuality, Reliability, Security and Robustness in Heterogeneous Networks10.1007/978-3-642-29222-4_30(421-437)Online publication date: 2012
https://doi.org/10.1007/978-3-642-29222-4_30
Hesari MNarayanan LOpatrny J(2010)On average and maximum load of greedy routing in wireless ad hoc networksProceedings of the 7th international conference on Wireless on-demand network systems and services10.5555/1834182.1834204(113-120)Online publication date: 3-Feb-2010
https://dl.acm.org/doi/10.5555/1834182.1834204
Li FChen SWang Y(2010)Load balancing routing with bounded stretchEURASIP Journal on Wireless Communications and Networking10.1155/2010/6237062010(1-16)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1155/2010/623706
Sarkar RZeng WGao JGu XAbdelzaher TVoigt TWolisz A(2010)Covering space for in-network sensor data storageProceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks10.1145/1791212.1791240(232-243)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.1145/1791212.1791240
Hesari MNarayanan LOpatrny J(2010)On average and maximum load of greedy routing in wireless ad hoc networks2010 Seventh International Conference on Wireless On-demand Network Systems and Services (WONS)10.1109/WONS.2010.5437122(113-120)Online publication date: Mar-2010
https://doi.org/10.1109/WONS.2010.5437122
Busch CMagdon-Ismail MXi J(2010)Oblivious Routing for Sensor Network TopologiesTheoretical Aspects of Distributed Computing in Sensor Networks10.1007/978-3-642-14849-1_13(381-406)Online publication date: 8-Nov-2010
https://doi.org/10.1007/978-3-642-14849-1_13
Durocher SKranakis EKrizanc DNarayanan L(2008)Balancing traffic load using one-turn rectilinear routingProceedings of the 5th international conference on Theory and applications of models of computation10.5555/1791834.1791878(467-478)Online publication date: 25-Apr-2008
https://dl.acm.org/doi/10.5555/1791834.1791878
Li FWang Y(2008)Circular Sailing Routing for Wireless NetworksIEEE INFOCOM 2008 - The 27th Conference on Computer Communications10.1109/INFOCOM.2008.192(1346-1354)Online publication date: Apr-2008
https://doi.org/10.1109/INFOCOM.2008.192
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents