Constructing the Overlay Network by Tuning Link Weights

When transport in networks follows the shortest paths, the union of all shortest path trees G∪spt can be regarded as the “transport overlay network”. Overlay networks such as peer-to-peer networks or virtual private networks can be considered as a subgraph of G∪spt. We construct two types of G∪spt: (a) G∪spt(α) where α is the extreme value index of polynomial link weights and (b) G∪spt(ρ) where ρ is the correlation coefficient of the 2-dimensional correlated uniformly distributed link weights in QoS routing. By tuning the extreme value index α of polynomial link weights, a phase transition occurs around a critical extreme value index αc of the link weight distribution. If α > αc, transport in the network traverses many links whereas for α < αc , all transport flows over a critical backbone: the Minimum Spanning Tree (MST). In QoS routing with 2-dimensional link weights, as we decrease the correlation coefficient ρ from 1 to −1, the overlay G∪spt becomes denser, and is equal to the substrate when ρ = −1. With the Erdös-Rényi random graph as the underlying topology, we show that the overlay G∪spt(ρ) is also close to an Erdös-Rényi random graph Gp (N), an observation with potential for mobile and wireless ad-hoc networks. The existence of such a controllable transition in the overlay structure may allow network operators to steer and balance flows in their network.