Spring 2005 Seminar Series

DATE: Thursday, February 17, 2005
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Devavrat Shah
Post Doctoral Associate
Department of Statistics
Stanford University

TITLE
New Approaches For Switch Algorithms

ABSTRACT
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.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.