Title: The VPN conjecture is true
Speaker: Navin Goyal (Georgia Tech)
We consider the following network design problem.
A group of nodes (terminals) in a large network wishes to reserve bandwidth to form a sub-network called
virtual private network (VPN). The VPN should be able to support various communication patterns that may
arise between the terminals. These communication patterns may change with time, and the only restriction on
them is that for each terminal there is an upper bound on the total amount of traffic handled by that
terminal. This leads to the well-studied VPN design problem wherein we must find paths between every pair of
terminals and reserve sufficient capacity on the edges on these paths so that all possible communication
patterns satisfying the given upper bounds can be routed. Each edge has cost proportional to the bandwidth
reserved on it. The goal is to minimize the total cost of the VPN.
Formally, we are given an undirected graph G=(V,E) with edges costs c(e) and a set of terminal nodes W. A
hose demand matrix for W is any symmetric matrix [D_{ij}] such that for each i, \sum_{j \neq i} D_{ij} \leq
1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every
hose matrix in the network. An oblivious routing template is a simple path P_{ij} for each pair i,,j \in W.
Given such a template, if we are to route a demand matrix D, then for each i,,j we send D_{ij} units of flow
along each P_{ij}.
A well-studied conjecture states that there exists an optimal VPN that is a tree, i.e., the union of paths
P_{ij} is a tree. In this talk, I will explain our recent proof of this conjecture.
This also yields the first polynomial time algorithm for computing the optimal VPN.
This is joint work with Neil Olver and Bruce Shepherd.