Resilient Virtual Private Networks

In this book, we focus on efficient provisioning of resilient Virtual Private Network (VPN) services. To provision a resilient quality of service (QoS) connection, two link-disjoint paths need to be computed across the provider network such that both paths meet the given QoS constraints. We propose a new framework in which both end-to-end delay and bandwidth constraints are considered simultaneously. The framework exploits the dependency between end-to-end delay, provisioned bandwidth and the chosen path. Given this framework, we present two new linear programming (LP) formulations for theoretical reference calculations and two new approximation algorithms suitable for production environments, even with very large networks. These algorithms iteratively use an algorithm that computes non-resilient QoS connections. As no sufficiently effective such algorithm is published we present new algorithms for computing non-resilient QoS connections too, with a run time comparable to Dijkstra s shortest-path algorithm. Our simulations show that exploiting the dependency between end-to-end delay, provisioned bandwidth and chosen path can significantly improve the network performance.