Traffic engineering for provisioning restorable hose-model VPNs

Virtual Private Networks (VPNs) are overlay networks established on top of a public network backbone with the goal of providing a service comparable to Private Networks (PNs). The recently proposed VPN hose-model provides customers with flexible and convenient ways to specify their bandwidth requirements. To meet the specified bandwidth requirements, the Network Service Provider (NSP) must reserve sufficient bandwidth on the data transmission paths between each pair of endpoints in a VPN. In addition, the reliability of a VPN depends on the reliability of the data transmission paths. Italiano et al. proposed an algorithm that finds a set of backup paths for a given VPN (VPN tree) under the single-link failure model [1]. When a link failure is detected on a VPN tree, a backup path corresponding to the failed link can be activated to restore the disconnected VPN tree into a new one, thereby ensuring the reliability of the VPN. However, Italiano's algorithm cannot guarantee that the specified bandwidth requirement of the given VPN under the single-link failure model will be met. To address this issue, we propose a new backup path set selection algorithm called BANGUAD in this paper. In addition, the problem of establishing multiple bandwidth-guaranteed hose-model VPNs under the single-link failure model has not been investigated previously. However in this problem, bandwidth-sharing algorithms have the potential to improve the performance of a provisioning algorithm significantly. Therefore, we also propose a bandwidth sharing algorithm and three provisioning algorithms for establishing multiple bandwidth-guaranteed hose-model VPNs under the single-link failure model. Simulations that compare the performance of the proposed algorithms are reported.