Published in

American Physical Society, Physical review E: Statistical, nonlinear, and soft matter physics, 3(75)

DOI: 10.1103/physreve.75.036105

Links

Tools

Export citation

Search in Google Scholar

Structural bottlenecks for communication in networks

This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Green circle
Published version: archiving allowed
Data provided by SHERPA/RoMEO

Abstract

We consider the effect of network topology on the optimality of packet routing which is quantified by gammac, the rate of packet insertion beyond which congestion and queue growth occurs. We show that for any network, there exists an absolute upper bound, expressed in terms of vertex separators, for the scaling of gammac with network size N, irrespective of the static routing protocol used. We then derive an estimate to this upper bound for scale-free networks and introduce a static routing protocol, the "hub avoidance protocol," which, for large packet insertion rates, is superior to the shortest path routing protocol.