News & Events
The Advanced Network Colloquium Series

A thread of research dating to the mid-90s is concerned with the emulation of an output-queued (OQ) switch with a combined input- and output-queued (CIOQ) switch. It showed that in order to emulate an N port OQ switch under adversarial inputs, it is necessary and sufficient for the CIOQ switch to run at a speedup of 2 - (1/N). This result validated a belief that was prevalent among implementors and researchers.
However, the Stable Marriage algorithms developed in this work were considered too complicated to implement, and implementors contented themselves with the knowledge that 2 is "the right amount of speedup" and ignored the algorithms.
Recently, a combination of factors has made Stable Marriage algorithms very attractive to the practice. This talk narrates the story and gives the technical details. The reason it took 10 years for the algorithms to be practicable is interesting, and frustrating.

Balaji Prabhakar is an Associate Professor in the Departments of Electrical Engineering and Computer Science at Stanford University. His research interests are in network algorithms, stochastic network theory, applied probability and distributed algorithms for large random structures. He has recently been on leave from Stanford: on a sabbatical at MSRI, Berkeley, during Jan--May 2005, and at a data center networking startup from Fall 2005 where he has designed various algorithms.
He has been a Terman Fellow at Stanford University and a Fellow of the Alfred P. Sloan Foundation. He has received the NSF CAREER award, the Erlang Prize from the INFORMS Applied Probability Society, and the Rollo Davidson Prize for contributions to probability and its applications. He is a co-recipient of the 2004 Infocom best paper award.