TALK by Devavrat SHAH

October 4, 2012

Queue-size scaling in switched networks

Devavrat Shah (MIT, visiting Stanford)

We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches, wireless networks and more recently data-centers. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. As the main result, we shall discuss a new class of online scheduling policies that achieve optimal scaling for average queue-size for a class of switched networks including input-queued switches. Time permitting, we shall discuss various exciting open questions in the domain of stochastic networks.

This is based on joint work with Neil Walton (Univ of Amsterdam) and Yuan Zhong (MIT).


Devavrat Shah is currently a Jamieson Associate Professor with the Department of Electrical Engineering and Computer Science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and the Operations Research Center (ORC). His research focus is on the theory of large complex networks which includes network algorithms and statistical inference. He has received the 2008 ACM Sigmetrics Rising Star Award and the 2010 Erlang Prize from the Applied Probability Society of INFORMS. He currently serves as an associate editor of Operations Research, Queueing Systems and IEEE Transactions on Information Theory.