12:15PM, Thursday, October 7th 2004.
Gates 104

 Randomization and Heavy Traffic Theory: New Approaches to the Design and Analysis of Switch Algorithms


Devavrat Shah
Stanford University

About the talk:
High speed data networks, such as the Internet, present the algorithm designer with highly constrained problems: the algorithms need to work at a very high speed while providing good performance and accessing limited computing resources. Consequently, only the simplest algorithms are implementable. But such algorithms may perform rather poorly. This tension between implementability and goodness of performance is acutely experienced by the designer of switch scheduling algorithms.

The switch of a core router connects lines operating at a rate of 10 Gbps.  The fabric of such a switch needs to be configured by a scheduler, roughly every 50 ns, for the transfer of packets. This small amount of time and the computational constraints at a core router make the design of implementable, high performance schedulers a very challenging problem; especially in the next generation of routers which will operate at line rates of 40 Gbps.

In the first part of my talk I will show how randomization may be used to simplify the implementation of switch schedulers. Specifically, I will exhibit two simple randomized scheduling algorithms and prove that they deliver 100% throughput while providing low delay. The second part of my talk concerns a new approach for analyzing the packet delay induced by an algorithm. I shall explain why traditional approaches based, for example, on queueing and large deviation theories are inadequate, and advance a new approach based on Heavy Traffic Theory. This approach helps explain some intriguing observations other researchers have made about the delay of scheduling algorithms based on simulations. It also leads to the
characterization of a delay-optimal scheduling algorithm.

About the speaker:
Devavrat Shah is currently a Ph.D. candidate at Stanford University.  He will be joining departments of EECS and ESD at MIT as an assistant professor in Spring 2005. He received his Bachelor of Technology degree from Indian Institute of Technology, Bombay in 1999. His research interests are in the areas of network algorithms and large-scale networks like wireless sensor networks. He received the President of India Gold Medal at IIT-Bombay in 1999. He was a co-author of the paper that received the best paper award at Infocom 2004.