Controlling congestion on complex networks: fairness, efficiency and network structure
arXiv:1512.09293 · doi:10.1038/s41598-017-09524-3
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 . 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.
published
References in corpus (8)
- Optimal routing on complex networks
- Robustness of Trans-European Gas Networks
- On the universality of the scaling of fluctuations in traffic on complex networks
- Accuracy in strategy imitations promotes the evolution of fairness in the spatial ultimatum game
- Resilience of natural gas networks during conflicts, crises and disruptions
- Impact of community structure on information transfer
- Transport in networks with multiple sources and sinks
- Critical behaviour in charging of electric vehicles