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.
arXiv commentpublished
References in corpus (16)
- Statistical mechanics of complex networks
- Universal Behavior of Load Distribution in Scale-free Networks
- Optimal network topologies for local search with congestion
- Controlling edge dynamics in complex networks
- Optimal routing on complex networks
- Dynamical properties of model communication networks
- Communication Bottlenecks in Scale-Free 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
- Critical behaviour in charging of electric vehicles
- Transport in networks with multiple sources and sinks
- Transport of multiple users in complex networks
- Fair sharing of resources in a supply network with constraints