| Abstract: |
A virtual private network (VPN) provides private network connections over a publicly accessible shared network. Bandwidth provisioning for VPNs leads to challenging optimization problems. In
the hose model proposed by Duffield et al., each VPN endpoint specifies bounds on the total amount of traffic that it will send or receive at any time. The network provider must provision the VPN
so that there is sufficient bandwidth for any traffic matrix that is consistent with these bounds. While previous work has considered tree routing and single-path routing between the VPN
endpoints, we demonstrate that the use of multi-path routing offers significant advantages. On the one hand, we present an optimal polynomial-time algorithm that computes a bandwidth reservation
of minimum cost using multi-path routing. This is in contrast to tree routing and single-path routing, where the problem is computationally hard. On the other hand, we present experimental
results showing that the reservation cost using multi-path routing can indeed be significantly smaller than with tree or single-path routing. |
