*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
March 10, 2008
Navin Goyal
ARC ThinkTank, Georgia Tech, College of Computing
Title: Network design under traffic uncertainty
Abstract: 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.
A well-known conjecture states that the optimal VPN 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.
