Multi-path routing versus tree routing for VPN bandwidth provisioning in the hose model

In this paper we study the bandwidth provisioning of VPN service in the hose model with multi-path routing and tree routing. We have investigated the bandwidth efficiency and blocking performance of these two routing schemes. Our study shows that without any restriction on the maximum fraction of traffic on a path (MFTP), multi-path routing often turns out to be single path routing, and only reduces the total bandwidth requirement slightly at rare combination of network topologies and hose parameters. In order to alleviate the overprovisioning problem of the hose model, we propose the concept of sub-provisioning and study the blocking performance using static reduced provisioning. The results show that with full provisioning, the two routing schemes have almost the same blocking performance. However, with sub-provisioning and the variation of the MFTP constraint, multi-path routing is capable of delivering a significant improvement in blocking performance, often better than tree routing by a few orders of magnitude. The improvement is attributed to the multiple alternative paths brought in by the MFTP constraint. With sub-provisioning, the link bandwidth availability becomes the restricting factor in admitting a connection. Having multiple paths, a connection request is able to explore available bandwidth more thoroughly in the network, thus increasing its chances of being admitted. We employ both analytical model and discrete event simulation for the blocking performance study. The analytical model is developed based on the multi-rate reduced load approximation technique and the simulation is carried out using the OPNET simulator. The close agreement between analytical and simulation results indicate the validity of the approach.