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 flexible and convenient ways to specify the bandwidth requirement 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 OHVPA to address the issue. OHVPA 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 OHVPA performs better in rejection ratio than other provisioning algorithms.