TITLE:  Delay-Optimal Scheduling for Data Center Networks and Input Queued Switches in Heavy Traffic

ABSTRACT:

Today's era of cloud computing is powered by massive data centers. A data center network enables exchange of data in the form of packets among the servers within these data centers. Given the size of today's data centers, it is desirable to to design low complexity scheduling algorithms which result in a fixed average packet delay, independent of the size of the data center. We consider the scheduling problem in an input-queued switch, which is a good abstraction for a data center network. In particular, we study the queue length (equivalently, delay) behavior under the so-called MaxWeight scheduling algorithm, which has low computational complexity. Under various traffic patterns, we show that the algorithm achieves optimal scaling of the heavy-traffic scaled queue length with respect to the size of the switch. This settles one version of an open conjecture that has been a central question in the area of stochastic networks. We obtain this result by using a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expected total queue length in the network, in steady-state.

Bio

Siva Theja Maguluri is a Research Staff Member in the Mathematical Sciences and Analytics Department at IBM T. J. Watson Research Center. He obtained his PhD from University of Illinois at Urbana Champaign, in Electrical and Computer Engineering where he worked on resource allocation algorithms for cloud computing and wireless networks. Earlier, he received an MS in ECE and an MS in Applied Math from UIUC and a B.Tech in Electrical Engineering from IIT Madras. His research interests include Stochastic Processes, Optimization, Cloud Computing, Data Centers, Resource Allocation and Scheduling Algorithms, Wireless Networks, and Game Theory