DOI 10.1007/s11235-006-6724-2 MTRA: An on-line hose-model VPN provisioning algorithm

Abstract Virtual private networks (VPNs) provide customers with a secure and manageable communication environment. The allocation of bandwidth for VPNs to meet the requirements specified by customers is now one of the most important research issues in the field of traffic engineering. A VPN resource-provisioning model called hose-model was developed to provide customers with a flexible and convenient way to specify the bandwidth requirements of a VPN. Several hose-model VPN provisioning algorithms have already been proposed. They focus on the bandwidth efficiency issue in the case of establishing a single hose-mode VPN. However, these algorithms cannot achieve a satisfactory rejection ratio when: (1) the residual bandwidths on links of the network backbone are finite and (2) multiple VPN setup requests are handled on-line. In this paper, we propose a new hose-model VPN provisioning algorithm called MTRA to address the issue. MTRA can process multiple VPN setup requests rapidly and reduce the rejection ratio effectively. Theoretical upper bounds of rejection ratios achieved by several VPN provisioning algorithms are also derived. The experiments verify that MTRA performs better in regards to the rejection ratio than other provisioning algorithms