Communication Bottlenecks in Scale-Free Networks

Abstract

We consider the effects of network topology on the optimality of packet routing quantified by ${\gamma }_c$, the rate of packet insertion beyond which congestion and queue growth occurs. The key result of this paper is to show that for any network, there exists an absolute upper bound, expressed in terms of vertex separators, for the scaling of ${\gamma }_c$ with network size $N$, irrespective of the routing algorithm used. We then derive an estimate to this upper bound for scale-free networks, and introduce a novel static routing protocol which is superior to shortest path routing under intense packet insertion rates.

5 pages, 3 figures

References in corpus (1)

• Efficient routing on complex networks

Cited by in corpus (45)

• Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
• Predicting commuter flows in spatial networks using a radiation model based on temporal ranges
• The Large Scale Curvature of Networks
• Scaling breakdown in flow fluctuations on complex networks
• Transport optimization on complex networks
• Resource allocation pattern in infrastructure networks
• A limited resource model of fault-tolerant capability against cascading failure of complex network
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Efficient routing strategies in scale-free networks with limited bandwidth
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Impact of community structure on information transfer
• Collectively optimal routing for congested traffic limited by link capacity
• Congestion diffusion and decongestion strategy in networked traffic
• Centrality scaling in large networks
• Limited path percolation in complex networks
• Cascading failures in spatially-embedded random networks
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Fluctuation-driven capacity distribution in complex networks
• Transport in networks with multiple sources and sinks
• Jamming transition in traffic flow under the priority queuing protocol
• Optimal transport on wireless networks
• Distributed flow optimization and cascading effects in weighted complex networks
• Optimization of transport protocols with path-length constraints in complex networks
• Discovering Network Structure Beyond Communities
• Controlling congestion on complex networks: fairness, efficiency and network structure
• Sensitive Dependence of Optimal Network Dynamics on Network Structure
• Exploring complex networks by means of adaptive walkers
• Self Avoiding Paths Routing Algorithm in Scale-Free Networks
• Optimal transport on supply-demand networks
• Fair sharing of resources in a supply network with constraints
• The Gradient Mechanism in a Communication Network
• Partition of Networks into Basins of Attraction
• Geographical networks stochastically constructed by a self-similar tiling according to population
• Evolutionary Construction of Geographical Networks with Nearly Optimal Robustness and Efficient Routing Properties
• Enhancing Transport Efficiency by Hybrid Routing Strategy
• Structural efficiency of percolation landscapes in flow networks
• Weighted projected networks: mapping hypergraphs to networks
• Internet data packet transport: from global topology to local queueing dynamics
• Study of dynamic and static routing for improvement of the transportation efficiency on small complex networks
• Link power coordination for energy conservation in complex communication networks
• Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
• On The Critical Packet Injection Rate Of A Preferential Next-Nearest Neighbor Routing Traffic Model On Barabasi-Albert Networks
• Local search on protein residue networks
• Random walk with priorities in communication-like networks
• Optimal coupling patterns in interconnected communication networks