Conventional pipe-model VPNs and some previous MPLS-based hose-model VPN focus on bandwidth minimization for single VPN construction. These algorithms will have a scalability problem if the frequency of adding and deleting VPNs is high. The recently proposed non-blocking backbone architecture and the fast hose-model VPNs construction algorithms solve the scalability problem. However, in order to determine the optimal routing and the load distribution of traffic inside the non-blocking network, the physical topology and the link capacity between any pair of nodes have to be pre-determined. In this thesis, we consider topology design as an important extension to the design of non-blocking backbone network supporting hose-model VPNs. We present an optimal mixed-integer programming formulat...[ Read more ]

Conventional pipe-model VPNs and some previous MPLS-based hose-model VPN focus on bandwidth minimization for single VPN construction. These algorithms will have a scalability problem if the frequency of adding and deleting VPNs is high. The recently proposed non-blocking backbone architecture and the fast hose-model VPNs construction algorithms solve the scalability problem. However, in order to determine the optimal routing and the load distribution of traffic inside the non-blocking network, the physical topology and the link capacity between any pair of nodes have to be pre-determined. In this thesis, we consider topology design as an important extension to the design of non-blocking backbone network supporting hose-model VPNs. We present an optimal mixed-integer programming formulation for designing a non-blocking backbone with budget constraint. We also explain that budget constraints can be an important factor in designing a non-blocking network. In addition, to overcome the high complexity of the optimal approach, we also proposed heuristic algorithms for topology design and compared their performance with that of optimal solution based on mixed-integer programming.