Yuan Zhong

 

We consider a switched network, a general queueing network model in which there are constraints on which queues may be served simultaneously; this model has been used successfully to model the detailed packet-level dynamics in communication networks, such as input-queued switches and wireless networks.

A scheduling policy for this model specifies which queues to serve at any point in time. The main challenge is finding scheduling policies that achieve optimal steady-state queue sizes. In this work, we propose a new class of online scheduling policies with optimal queue-size scaling for a large class of switched networks, including the input-queued switches. As a consequence, we establish the validity of a conjecture [Shah, Tsitsiklis and Zhong 2011] about optimal queue-size scaling for input-queued switches.