Title: The VPN Conjecture is True
Speaker: Navin Goyal, Georgia Institute of Technology
Date: Monday, April 21, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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 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.