The Eureka Repository is closing down and will not be available after the end of 2020. All publications from current Faculty have now been migrated to Symplectic Elements. See the Sainsbury Library Blog for more information. ×

Structural Bottlenecks for Communication in Networks

Sreenivasan, Sameet, Cohen, Reuven, López, Eduardo, Toroczkai, Zoltán and Stanley, Eugene (2007) Structural Bottlenecks for Communication in Networks. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 75 (3). 036105.


We consider the effect of network topology on the optimality of packet routing which is quantified by γc, 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 γc 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.

Item Type: Article
Keywords: Transport; Routing; Network congestion
Subject(s): Complexity
Centre: CABDyN Complexity Centre
Date Deposited: 25 Feb 2012 21:28
Last Modified: 23 Oct 2015 14:06

Actions (login required)

Edit View Edit View