Skip to main content

Research Repository

Advanced Search

Controlling congestion on complex networks: fairness, efficiency and network structure

Buzna, Ľuboš; Carvalho, Rui

Controlling congestion on complex networks: fairness, efficiency and network structure Thumbnail


Authors

Ľuboš Buzna



Abstract

We consider two elementary (max-flow and uniform-flow) and two realistic (max-min fairness and proportional fairness) congestion control schemes, and analyse how the algorithms and network structure affect throughput, the fairness of flow allocation, and the location of bottleneck edges. The more realistic proportional fairness and max-min fairness algorithms have similar throughput, but path flow allocations are more unequal in scale-free than in random regular networks. Scale-free networks have lower throughput than their random regular counterparts in the uniform-flow algorithm, which is favoured in the complex networks literature. We show, however, that this relation is reversed on all other congestion control algorithms for a region of the parameter space given by the degree exponent γ and average degree 〈k〉. Moreover, the uniform-flow algorithm severely underestimates the network throughput of congested networks, and a rich phenomenology of path flow allocations is only present in the more realistic α-fair family of algorithms. Finally, we show that the number of paths passing through an edge characterises the location of a wide range of bottleneck edges in these algorithms. Such identification of bottlenecks could provide a bridge between the two fields of complex networks and congestion control.

Citation

Buzna, Ľ., & Carvalho, R. (2017). Controlling congestion on complex networks: fairness, efficiency and network structure. Scientific Reports, 7(1), Article 9152. https://doi.org/10.1038/s41598-017-09524-3

Journal Article Type Article
Acceptance Date Jul 18, 2017
Online Publication Date Aug 22, 2017
Publication Date Aug 22, 2017
Deposit Date Sep 1, 2017
Publicly Available Date Sep 1, 2017
Journal Scientific Reports
Publisher Nature Research
Peer Reviewed Peer Reviewed
Volume 7
Issue 1
Article Number 9152
DOI https://doi.org/10.1038/s41598-017-09524-3

Files

Published Journal Article (5.4 Mb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Open Access. This article is licensed under a Creative Commons Attribution 4.0 International
License, which permits use, sharing, adaptation, distribution and reproduction in any medium or
format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative
Commons license, and indicate if changes were made. Te images or other third party material in this
article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the
material. If material is not included in the article’s Creative Commons license and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/.
© The Author(s) 2017





You might also like



Downloadable Citations