Onset of traffic congestion in complex networks

Liang Zhao, Ying-Cheng Lai, Kwangho Park, and Nong Ye
Phys. Rev. E 71, 026125 – Published 24 February 2005

Abstract

Free traffic flow on a complex network is key to its normal and efficient functioning. Recent works indicate that many realistic networks possess connecting topologies with a scale-free feature: the probability distribution of the number of links at nodes, or the degree distribution, contains a power-law component. A natural question is then how the topology influences the dynamics of traffic flow on a complex network. Here we present two models to address this question, taking into account the network topology, the information-generating rate, and the information-processing capacity of individual nodes. For each model, we study four kinds of networks: scale-free, random, and regular networks and Cayley trees. In the first model, the capacity of packet delivery of each node is proportional to its number of links, while in the second model, it is proportional to the number of shortest paths passing through the node. We find, in both models, that there is a critical rate of information generation, below which the network traffic is free but above which traffic congestion occurs. Theoretical estimates are given for the critical point. For the first model, scale-free networks and random networks are found to be more tolerant to congestion. For the second model, the congestion condition is independent of network size and topology, suggesting that this model may be practically useful for designing communication protocols.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 30 August 2004

DOI:https://doi.org/10.1103/PhysRevE.71.026125

©2005 American Physical Society

Authors & Affiliations

Liang Zhao1,2, Ying-Cheng Lai1,3, Kwangho Park1, and Nong Ye4

  • 1Department of Mathematics and Statistics, Arizona State University, Tempe, Arizona 85287, USA
  • 2Institute of Mathematics and Computer Science, University of São Paulo, São Carlos, Brazil
  • 3Department of Electrical Engineering and Department of Physics, Arizona State University, Tempe, Arizona 85287, USA
  • 4Department of Industrial Engineering and Department of Computer Science and Engineering, Arizona State University, Tempe, Arizona 85287, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 71, Iss. 2 — February 2005

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×