Algorithms for provisioning virtual private networks in the hose model

ABSTRACT

Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs 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 is NP hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise 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 develop an algorithm that is based on the primal-dual method. Our experimental results with synthetic network graphs indicate that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints.

REFERENCES

• 1: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. "Network Flows". Prentice Hall, 1993.
• 2: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 3: N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merive, A flexible model for resource management in virtual private networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.95-108, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 7: S. Kent and R. Atkinson. Security architecture for the internet protocol. RFC 2401, Nov. 1998.
• 8: A. Kumar, R. Rastogi, B. Yener, and A. Silberschatz. Algorithms for provisioning virtual private networks in the hose model. Technical Report 0112380-001023-23, Bell Laboratories, Murray Hill, 2000.
• 9: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 10: Maurice Queyranne, Structure of a simple scheduling polyhedron, Mathematical Programming: Series A and B, v.58 n.2, p.263-285, Feb. 2, 1993 [doi>10.1007/BF01581271]
• 11: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 12: B. M. Waxman. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):1617-1622, Dec. 1988.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks
          Nouns: Internet

General Terms:
Algorithms, Design, Experimentation, Performance