Protected virtual private networks in the hose model

Abstract

A Virtual Private Network (VPN) is a service by a Telecommunication (TSP) or Internet Service Provider (ISP) to emulate a private network for a customer. The hose model is for VPNs where the customer is not required to know the exact pair wise traffic pattern between VPN sites, but specifies the maximum traffic rate that can originate or terminate at each VPN site. Hose VPNs protected from single link failures are considered. Two strategies for protection - Path and Line are described, and mixed integer linear programming problems (MILP) are formulated to determine the bandwidth requirements of the protection schemes. Comparisons are performed for path and line protection using simulations on topologies like a 12-node ring, NSFNET16 and Euroring. Path protection is found to be the most bandwidth-efficient strategy and requires approximately 100% or more additional bandwidth than an unprotected optimal tree, whereas line protection requires approximately 200% or more additional bandwidth. To compute the bandwidth required for protected VPN trees, a naive strategy of first computing optimal unprotected VPN trees and then determining the protection bandwidth is used. We also investigate the efficiency of this naive approach, by formulating a simple heuristic that iteratively constructs different trees for a given set of VPN sites and determines the cost of path protection for each of the trees. This heuristic determines a VPN tree that requires the minimum total bandwidth. Experimental results on NSFNET16 and Euroring show that this heuristic results in average savings of about 5% of the total bandwidth from the naive strategy.