2nd International ICST Conference on Communications and Networking in China

Research Article

Constructing the Overlay Network by Tuning Link Weights

  • @INPROCEEDINGS{10.1109/CHINACOM.2007.4469347,
        author={Huijuan Wang and Piet Van Mieghem},
        title={Constructing the Overlay Network by Tuning Link Weights},
        proceedings={2nd International ICST Conference on Communications and Networking in China},
        publisher={IEEE},
        proceedings_a={CHINACOM},
        year={2008},
        month={3},
        keywords={Ad hoc networks  IP networks  Network topology  Peer to peer computing  Polynomials  Routing  Spine  Telecommunication traffic  Tree graphs  Virtual private networks},
        doi={10.1109/CHINACOM.2007.4469347}
    }
    
  • Huijuan Wang
    Piet Van Mieghem
    Year: 2008
    Constructing the Overlay Network by Tuning Link Weights
    CHINACOM
    IEEE
    DOI: 10.1109/CHINACOM.2007.4469347
Huijuan Wang1,*, Piet Van Mieghem1,*
  • 1: Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
*Contact email: H.Wang@ewi.tudelft.nl, P.VanMieghem@ewi.tudelft.nl

Abstract

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.