Note the new location for the seminar.


Thursday, January 22nd, 2004
Room 202, Packard Building

 Design and Analysis of Switch Scheduling Algorithms


Devavrat Shah

Stanford University

About the talk:
 
I will describe simple-to-implement high throughput scheduling algorithms for Input Queued(IQ) switches in this talk. I will present two approaches, both based on randomization, to design such algorithms. The first approach is a randomized approximation to Maximum Weight Matching, a well known scheduling algorithm, while the second approach is based on a randomized edge coloring algorithm for bipartite multigraph. Next, I will present a method to compare performance of algorithms in terms of delay. This method is based on heavy traffic performance analysis technique.

About the speaker:
 
Devavrat Shah is a PhD candidate at the Computer Science department, Stanford University. He received his bachelors degree from IIT-Bombay in 1999. Since then he has been at Stanford. His interests are in network algorithms, wireless networks, stochastic networks and information theory.