Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow

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.