We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such net-works have been used to effectively model input-queued switches and wireless networks. 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 provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a long-standing conjecture about optimal queue-size scaling for input-queued switches.
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 Operations Research Center (ORC). His research focus is on theory of large complex networks which includes network algorithms and statistical inference. He has received 2008 ACM Sigmetrics Rising Star Award and 2010 Erlang Prize from the Applied Probability Society of INFORMS. He currently serves as an associate editor of Operations Research.