Algorithms for Provisioning Virtual Private Networks in the Hose Model

Virtual Private Networks (VPNs) with QoS guarantees are an important service that Internet Service Providers are expected to provide in coming years. Most recent work on provisioning VPNs assumes the pipe model in which customers are required to specify QoS bandwidth requirements between every pair of VPN endpoints. However, as the number of VPN endpoints increases and communication patterns between endpoints become increasingly complex, predicting the traffic between each pair of endpoints is almost impossible. The recently proposed hose model alleviates the shortcomings of the pipe model by requiring customers to specify only one ingress and egress bandwidth per hose endpoint. In addition to ease of specification, the hose model allows for greater flexibility since it permits traffic to and from a hose endpoint to be arbitrarily distributed to other endpoints. In this paper, we develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree in NP-hard. However, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we propose an algorithm for computing the optimal tree whose time complexity is O(mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and devise an algorithm that is based on the primal- dual method. Finally, we extend our proposed algorithms for computing VPN trees to the case when network links have capacity constraints. We show that in the presence of link capacity constraints, computing the optimal VPN tree is NP-hard even when ingress and egress bandwidths of each endpoing are equal. Further, we also show that computing an approximate solution that is within a constant factor of the optimum is as difficult as computing the optimal VPN tree itself.