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

Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, Bulent Yener

Research output: Contribution to journalConference articlepeer-review


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 of 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.

Original languageEnglish (US)
Pages (from-to)389-398
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2001
Event33rd Annual ACM Symposium on Theory of Computing - Creta, Greece
Duration: Jul 6 2001Jul 8 2001

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Provisioning a virtual private network: A network design problem for multicommodity flow'. Together they form a unique fingerprint.

Cite this