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

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. Th...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Ľuboš Buzna, Rui Carvalho
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2017
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/4ca5f2ce5d8b48629998b03299501681
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:4ca5f2ce5d8b48629998b03299501681
record_format	dspace
spelling	oai:doaj.org-article:4ca5f2ce5d8b48629998b032995016812021-12-02T11:52:20ZControlling congestion on complex networks: fairness, efficiency and network structure10.1038/s41598-017-09524-32045-2322https://doaj.org/article/4ca5f2ce5d8b48629998b032995016812017-08-01T00:00:00Zhttps://doi.org/10.1038/s41598-017-09524-3https://doaj.org/toc/2045-2322Abstract 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.Ľuboš BuznaRui CarvalhoNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 7, Iss 1, Pp 1-15 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Ľuboš Buzna Rui Carvalho Controlling congestion on complex networks: fairness, efficiency and network structure
description	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.
format	article
author	Ľuboš Buzna Rui Carvalho
author_facet	Ľuboš Buzna Rui Carvalho
author_sort	Ľuboš Buzna
title	Controlling congestion on complex networks: fairness, efficiency and network structure
title_short	Controlling congestion on complex networks: fairness, efficiency and network structure
title_full	Controlling congestion on complex networks: fairness, efficiency and network structure
title_fullStr	Controlling congestion on complex networks: fairness, efficiency and network structure
title_full_unstemmed	Controlling congestion on complex networks: fairness, efficiency and network structure
title_sort	controlling congestion on complex networks: fairness, efficiency and network structure
publisher	Nature Portfolio
publishDate	2017
url	https://doaj.org/article/4ca5f2ce5d8b48629998b03299501681
work_keys_str_mv	AT lubosbuzna controllingcongestiononcomplexnetworksfairnessefficiencyandnetworkstructure AT ruicarvalho controllingcongestiononcomplexnetworksfairnessefficiencyandnetworkstructure
_version_	1718395101464494080

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

Ejemplares similares