Virtual Private Networks: Joint Resource Allocation and Routing Design

We consider the resource allocation problem in the design of intranets or virtual private networks (VPNs) that is faced by a service provider, which has service level agreements with various customers to carry their multiservice traffic. The design allocates bandwidth on each link to the VPNs such that, when the traffic of a customer is optimally routed over its VPN, a weighted aggregate measure of carried bandwidth over the service provider's infrastructure is maximized, subject to constraints that each VPN carries a specified minimum. Thus, this is a joint resource allocation and traffic routing problem. Multiplexing is across services and routes within each VPN, but not across VPNs, the latter in the interest of QoS protection. The traffic modeling is at the flow or call level, with random arrivals and holding times of calls and each call requiring (effective) bandwidth, which is characteristic of the call's service type, on all links in its route. The network is modeled as a multirate loss network. Scalability of the design process, i.e. , the ability to handle OC3 and higher rates, is an important contribution, and this is achieved by the systematic use of asymptotic techniques, specifically a Refined Uniform Asymptotic Approximation. Our software package VPN DESIGNER incorporates these results. We report on numerical results for problems with up to 8 VPNs on a network with 8 nodes, 24 OC3 links, 6 services and up to 640 routes.