Constructing the Overlay Network by Tuning Link Weights
Huijuan Wang, Piet Van Mieghem · 2007
When transport in networks follows the shortest paths, the union of all shortest path trees G⋃sptcan 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 αcof 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⋃sptbecomes denser, and is equal to the substrate when ρ = -1. With the Erdos-Renyi random graph as the underlying topology, we show that the overlay G⋃spt(ρ)is also close to an Erdos-Renyi 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.