Optimal customer provisioning in network-based mobile VPNs

A virtual private network (VPN) is an overlay network that uses the public network to carry data traffic between corporate sites and users, maintaining privacy through the use of tunnelling protocols and security procedures. In the network-based model, VPN-aware network elements are placed within the network to set up concatenated tunnels between the user/site and enterprise resources to offer intranet VPN and remote access VPN. This paper identifies the important differences between a traditional VPN and the mobile VPN and proposes a hierarchical network architecture to efficiently realize network-based mobile VPNs. We address the problem of optimally provisioning VPN-aware devices, called IP service gateways (IPSGs), in the hierarchical network architecture for mobile VPNs, while taking into account of (1) the cost of links over which VPN tunnels are established, (2) the cost of provisioning a VPN customer on an IPSG, and (3) redundancy in IPSG provisioning for fault tolerance. We develop generic yet powerful problem formulations for different scenarios described above while considering practical requirements of the network elements and business requirements of the VPN service provider. The formulation becomes a set of integer programming problems. We solve several instances of the problem for a few practical cases and discuss their applications in the overall network design.