Constructing the Overlay Network by Tuning Link Weights

When transport in networks follows the shortest paths, the union of all shortest path trees G_cupspt 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_cupspt. We construct two types of G_cupspt: (a) G_{cupspt(alpha)} where alpha is the extreme value index of polynomial link weights and (b) G_cupspt(rho) where rho is the correlation coefficient of the 2-dimensional correlated uniformly distributed link weights in QoS routing. By tuning the extreme value index alpha of polynomial link weights, a phase transition occurs around a critical extreme value index ac of the link weight distribution. If alpha > alpha_c, transport in the network traverses many links whereas for alpha < alpha_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 rho from 1 to -1, the overlay GUSpt becomes denser, and is equal to the substrate when rho = -1. With the Erdos-Renyi random graph as the underlying topology, we show that the overlay G_cupspt(rho) is also close to an Erdos-Renyi random graph G_p (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.