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. In order to meet specified bandwidth requirements, the network service provider (NSP) must reserve a sufficient amount of bandwidth on the data transmission paths between each endpoint pair of a VPN. In addition, reliability of a VPN depends on the reliability of 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. When any link failure on the VPN tree is detected, a backup path corresponding to the failed link can be activated to restore the disconnected VPN tree into a new one, and hence can ensure reliability of the given VPN. However, Italiano´s algorithm cannot guarantee the specified bandwidth requirement of the given VPN under the single-link failure model will be met. To address this issue a new backup path set selection algorithm called BANGUAD is proposed in this work. In addition, issues about establishing multiple bandwidth-guaranteed hose-model VPNs under the single-link failure model have not been investigated. In this paper, we propose a bandwidth sharing algorithm as well as three provisioning algorithms for establishing multiple bandwidth-guaranteed hose-model VPNs under the single-link failure model. Experimental simulations that compare the performance of the proposed algorithms are reported