Load Balancing by Network Curvature Control

Authors

  • Mingji Lou Western Digital Lake Forest, CA 92692, USA
  • Edmond Jonckheere University of Southern California Los Angeles, CA 90089-2563, USA
  • Francis Bonahon University of Southern California Los Angeles, CA 90089-2563, USA
  • Bhaskar Krishnamachari University of Southern California Los Angeles, CA 90089-2563, USA
  • Yuliy Baryshnikov Alcatel-Lucent Murray Hill, NJ 07974-0636, USA

Keywords:

network congestion, curvature, inertia, Gromov hyperbolic graphs, Poincaré disk, load balancing, Yamabe flow

Abstract

The traditional heavy-tailed interpretation of congestion is challenged in this paper. A counter example shows that a network with uniform degree can have significant traffic congestion when the degree is larger than 6. A profound understanding of what causes congestion is reestablished, based on the network curvature theorem. A load balancing algorithm based on curvature control is presented with network applications.

References

F. Ariaei and E. Jonckheere, Cooperative 'curvature-driven' control of mobile autonomous sensor agent network, IEEE Conference on Decision and Control, New Orleans, LA, December 2007, pp. 1453-1458. http://dx.doi.org/10.1109/cdc.2007.4435022

Y. Baryshnikov, On the curvature of the Internet, in Workshop on Stochastic Geometry and Teletraffic, Eindhoven, The Netherlands, April 2002.

L. M. Blumenthal, Theory and Applications of Distance Geometry, Oxford at the Clarendon Press, London, 1953.

M. Boguna, F. Papadopoulos and D. Krioukov, Sustaining the Internet with hyperbolic mapping, Nature Communications, volume 1, article number 62, September 2010. http://dx.doi.org/10.1038/ncomms1063

M. Bonk and O. Schramm, Embeddings of Gromov hyperbolic spaces, Geom. Funct. Analysis, volume 10, pp. 266-306, 2000. http://dx.doi.org/10.1007/s000390050009

D. Burago, Y. Burago, and S. Ivanov, A Course in Metric Geometry, volume 33 of Graduate Study in Mathematics, American Mathematical Society, Providence, Rhode Island, 2001.

Cisco, How Does Load Balancing Work? Cisco Document ID: 5212,2005. http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094820.shtml.

E. Ghys and P. de la Harpe, editors. Sur les groupes hyperboliques d'après Mikhael Gromov, Number 83 in Progress in Mathematics, Birkhauser, Boston, MA, 1990. (Papers from the Swiss Seminar on Hyperbolic Groups held in Bern, 1988.)

M. Gromov, Hyperbolic groups, in S. M. Gersten, editor, Essays in Group Theory, volume 8 of Mathematical Sciences Research Institute Publication, pages 75-263, Springer-Verlag, New York, 1987.

M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, volume 152 of Progress in Mathematics, Springer-Verlag, 1999.

S. D. Fisher, Function Theory on Planar Domains: A Second Course in Complex Analysis, John Wiley & Sons, New York, 1983.

J. Jost, Nonpositive Curvature: Geometric and Analytic Aspects, Birkhauser, Lectures in Mathematics, Basel-Boston-Berlin, 1997.

J. Jost, Riemannian Geometry and Geometric Analysis, Second Edition, Springer, Universitext, Berlin, Heidelberg, New York, 1998. http://dx.doi.org/10.1007/978-3-662-22385-7

M. Lou and E. A. Jonckheere, Tracking and mitigating piracy, American Control Conference, Minneapolis, MN, June 14-16, 2006, paper WeA20.2, Session: Networks and Control, pp. 656-661.

M. Lou, Traffic pattern analysis in negatively curved network, Ph.D. dissertation, Department of Electrical Engineering, University of Southern California, Los Angeles, Calif, USA, 2008.

F. Luo, Combinatorial Yamabe flow on surfaces, Communications in Contemporary Mathematics, volume 6, number 5, pp. 765-780, 2004. http://dx.doi.org/10.1142/S0219199704001501

L. Sun and X. Yu, Positively curved cubic plane graphs are finite, Journal of Graph Theory, volume 47, number 4, pp. 241-274, 2004. http://dx.doi.org/10.1002/jgt.20026

Published

2011-03-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.