[Brown CS Talks] Brown CS Seminar: Amit Kumar in Lubrano on 3/18/02 at noon

[talks-admin@list.cs.brown.edu]

			      CS Seminar
		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			      Amit Kumar

			  Cornell University

		    Monday, March 18, 2002 at noon
	       Lubrano Conference Room (CIT 4th floor)
	       Refreshments will be served at 11:45 am
			       

		  Algorithms for Network Management


			       Abstract

Communication networks have witnessed phenomenal growth in recent
years. The issues raised by the introduction of new technology and
protocols have led to problems which are both theoretically
fundamental and relevant to current applications.  In this talk, I
shall focus on two key themes, namely, virtual private networks (VPN)
and the Border Gateway Protocol (BGP).

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 general network design problem: We have
bounds on the cumulative amount of traffic each terminal can send and
receive; we must reserve enough bandwidth on the network so that any
pair-wise traffic matrix consistent with these bounds can be routed.

BGP is the standard protocol for exchanging information between border
routers of autonomous systems (AS) in the Internet. Within an AS,
border routers exchange externally learned route information. Naive
solutions for this peering between the border routers simply cannot
scale to the sizes of modern AS networks.  Carefully designed route
reflector configurations can drastically reduce the communication
costs needed by such peering sessions. We give the first algorithmic
approach towards designing such configurations.

We show connections of these problems with facility location problems
and give efficient algorithms with provable performance guarantees.


		      Host:  Professor Eli Upfal