1202.0213 (Chi Ho Yeung et al.)

The Competition for Shortest Paths on Sparse Graphs    [PDF]

Chi Ho Yeung, David Saad

Optimal paths connecting randomly selected network nodes and fixed routers
are studied analytically in the presence of non-linear overlap cost that
penalizes congestion. Routing becomes increasingly more difficult as the number
of selected nodes increases and exhibits ergodicity breaking in the case of
multiple routers. A distributed linearly-scalable routing algorithm is devised.
The ground state of such systems reveals non-monotonic complex behaviors in
both average path-length and algorithmic convergence, depending on the network
topology, and densities of communicating nodes and routers.

View original: http://arxiv.org/abs/1202.0213