Provisioning a virtual private network: a network design problem for multicommodity flow

ABSTRACT

Consider a setting in which a group of nodes, situated in a large underlying network, wishes to reserve bandwidth on which to support communication. Virtual private networks (VPNs) are services that support such a construct; rather than building a new physical network on the group of nodes that must be connected, bandwidth in the underlying network is reserved for communication within the group, forming a virtual “sub-network.”Provisioning a virtual private network over a set off terminals gives rise to the following general network design problem. We have bounds on the cumulative amount of traffic each terminal can send and receive; we must choose a path for each pair of terminals, and a bandwidth allocation for each edge of the network, so that any traffic matrix consistent with the given upper bounds can be feasibly routed. Thus, we are seeking to design a network that can support a continuum of possible traffic scenarios.We provide optimal and approximate algorithms for several variants of this problem, depending on whether the traffic matrix is required to be symmetric, and on whether the designed network is required to be a tree (a natural constraint in a number of basic applications). We also establish a relation between this collection of network design problems and a variant of the facility location problem introduced by Karger and Minkoff; we extend their results by providing a stronger approximation algorithm for this latter problem.

REFERENCES

• 1: Karen Aardal , Gavián A. Chudak , David B. Shmoys, A 3-approximation algorithm for the k-level uncapacitated facility location problem, Information Processing Letters, v.72 n.5-6, p.161-167, Dec. 30, 1999 [doi>10.1016/S0020-0190(99)00144-1]
• 2: Matthew Andrews , Lisa Zhang, The Access Network Design Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.40, November 08-11, 1998
• 3: Esther M. Arkin , Magnús M. Halldórsson , Refael Hassin, Approximating the tree and tour covers of a graph, Information Processing Letters, v.47 n.6, p.275-282, Oct. 18, 1993 [doi>10.1016/0020-0190(93)90072-H]
• 4: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 5: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 6: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 7: 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
• 8: Shivi Fotedar , Mario Gerla , Paola Crocetti , Luigi Fratta, ATM virtual private networks, Communications of the ACM, v.38 n.2, p.101-109, Feb. 1995 [doi>10.1145/204826.204852]
• 9: 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
• 10: M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
• 11: Martin Grotschel, Laszlo Lovasz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, 1988.
• 12: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 13: Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.448, November 08-11, 1998
• 14: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 15: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 16: Jyh-Han Lin , Jeffrey Scott Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, v.44 n.5, p.245-249, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90208-D]
• 17: 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]
• 18: Laszlo Lovasz and Michael D. Plummer. Matching theory. North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29.
• 19: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 20: F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Buy-at-bulk network design: approximating the single-sink edge installation problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 05-07, 1997, New Orleans, Louisiana, United States
• 21: Charles Scott , Paul Wolfe , Mike Erwin, Virtual private networks, O'Reilly & Associates, Inc., Sebastopol, CA, 1998
• 22: 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]
• 23: David Paul Williamson, On the design of approximation algorithms for a class of graph problems, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 24: David P. Williamson , Michel X. Goemans , Milena Mihail , Vijay V. Vazirani, A primal-dual approximation algorithm for generalized Steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.708-717, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167268]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Design, Performance, Theory, Verification