Efficient algorithm for routing optimization via statistical mechanics

Chi Ho Yeung*

*Corresponding author for this work

Research output: Chapter in Book/Published conference outputConference publication

Abstract

Many practical routing algorithms are heuristic, adhoc and centralized, rendering generic and optimal path configurations difficult to obtain. Here we study a scenario whereby selected nodes in a given network communicate with fixed routers and employ statistical physics methods to obtain optimal routing solutions subject to a generic cost. A distributive message-passing algorithm capable of optimizing the path configuration in real instances is devised, based on the analytical derivation, and is greatly simplified by expanding the cost function around the optimized flow. Good algorithmic convergence is observed in most of the parameter regimes. By applying the algorithm, we study and compare the pros and cons of balanced traffic configurations to that of consolidated traffic, which provides important implications to practical communication and transportation networks. Interesting macroscopic phenomena are observed from the optimized states as an interplay between the communication density and the cost functions used.

Original languageEnglish
Title of host publication2013 IEEE International Conference on Communications Workshops, ICC
EditorsDong-In Kin, Peter Müller
Place of PublicationPiscataway, NJ (US)
PublisherIEEE
Pages1420-1424
Number of pages5
ISBN (Print)978-1-4673-5753-1
DOIs
Publication statusPublished - 2013
Event2013 IEEE International Conference on Communications - Budapest, Hungary
Duration: 9 Jun 201313 Jun 2013

Conference

Conference2013 IEEE International Conference on Communications
Abbreviated titleIEEE ICC 2013
Country/TerritoryHungary
CityBudapest
Period9/06/1313/06/13

Fingerprint

Dive into the research topics of 'Efficient algorithm for routing optimization via statistical mechanics'. Together they form a unique fingerprint.
  • Fluctuation-driven traffic congestion in a scale-free model of the Internet

    Yurkevich, I. V., Stepanenko, A. S., Constantinou, C. C. & Lerner, I. V., 2013, 2013 IEEE International Conference on Communications Workshops, ICC. Kin, D-I. & Müller, P. (eds.). Piscataway, NJ (US): IEEE, p. 1425-1428 4 p.

    Research output: Chapter in Book/Published conference outputConference publication

Cite this