TY - JOUR

T1 - Euclidean versus hyperbolic congestion in idealized versus experimental networks

AU - Jonckheere, Edmond

AU - Lou, Mingji

AU - Bonahon, Francis

AU - Baryshnikov, Yuliy

N1 - Funding Information:
This research was supprted by NSF Grant CNS-NetSE-1017881.
Publisher Copyright:
© Taylor & Francis Group, LLC.

PY - 2011/1/1

Y1 - 2011/1/1

N2 - This paper proposes a mathematical justification of the phenomenon of extreme congestion at a very limited number of nodes in very large networks. It is argued that this phenomenon occurs as a combination of the negative curvature property of the network together with minimum-length routing. More specifically, it is shown that in a large n-dimensional hyperbolic ball B of radius R viewed as a roughly similar model of a Gromov hyperbolic network, the proportion of traffic paths transiting through a small ball near the center is Θ(1), whereas in a Euclidean ball, the same proportion scales as Θ(1/Rn−1). This discrepancy persists for the traffic load, which at the center of the hyperbolic ball scales as volume2 (B), whereas the same traffic load scales as volume1+1/n (B) in the Euclidean ball. This provides a theoretical justification of the experimental exponent discrepancy observed by Narayan and Saniee between traffic loads in Gromov-hyperbolic networks from the Rocketfuel database and synthetic Euclidean lattice networks. It is further conjectured that for networks that do not enjoy the obvious symmetry of hyperbolic and Euclidean balls, the point of maximum traffic is near the center of mass of the network.

AB - This paper proposes a mathematical justification of the phenomenon of extreme congestion at a very limited number of nodes in very large networks. It is argued that this phenomenon occurs as a combination of the negative curvature property of the network together with minimum-length routing. More specifically, it is shown that in a large n-dimensional hyperbolic ball B of radius R viewed as a roughly similar model of a Gromov hyperbolic network, the proportion of traffic paths transiting through a small ball near the center is Θ(1), whereas in a Euclidean ball, the same proportion scales as Θ(1/Rn−1). This discrepancy persists for the traffic load, which at the center of the hyperbolic ball scales as volume2 (B), whereas the same traffic load scales as volume1+1/n (B) in the Euclidean ball. This provides a theoretical justification of the experimental exponent discrepancy observed by Narayan and Saniee between traffic loads in Gromov-hyperbolic networks from the Rocketfuel database and synthetic Euclidean lattice networks. It is further conjectured that for networks that do not enjoy the obvious symmetry of hyperbolic and Euclidean balls, the point of maximum traffic is near the center of mass of the network.

UR - http://www.scopus.com/inward/record.url?scp=80155171270&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80155171270&partnerID=8YFLogxK

U2 - 10.1080/15427951.2010.554320

DO - 10.1080/15427951.2010.554320

M3 - Article

AN - SCOPUS:80155171270

VL - 7

SP - 1

EP - 27

JO - Internet Mathematics

JF - Internet Mathematics

SN - 1542-7951

IS - 1

ER -