Seminar by Prof. Amit Kumar
Simple Algorithms for Provisioning a Virtual Private Network
Prof. Amit Kumar
Department of Computer Science and Engineering
Indian Institute of Technology Delhi
New Delhi, India
Date: Monday, September 15, 2003
Time: 2:30 PM
Venue: CS-101
Abstract
Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. Provisioning a VPN over a set of terminals gives rise to the following problem. We have bounds on the cumulative 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. The goal of such a solution is to minimize the total bandwidth reserved in the network. In this talk, I shall describe this problem and show that it has connections with classical facility location problems. This problem turns out to be computationally hard. I shall then describe a simple and easy to analyze randomized approximation algorithm for this problem.
About the speaker
Dr Amit Kumar is an Assistant Professor at IIT Delhi. He received his B.Tech from IIT Kanpur in 1997 and PhD in computer science from Cornell University in 2002. Before joining IIT Delhi, he was a member of technical staff at the Internet Management Research Department, Bell Laboratories. His research interest lies in design and analysis of algorithms, and their applications to network management.