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

Seminar
Friday, November 11, 2016
11:00am - 12:00pm
UTA 7.532

Today's era of cloud computing is powered by massive data centers. A data center network enables the 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 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.

Speaker

Photo: Siva Theja Maguluri
Assistant Professor
Georgia Institute of Technology

Siva Theja Maguluri is the Fouts Family Early Career Professor and an Assistant Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. Before that, he was a Research Staff Member in the Mathematical Sciences Department at IBM T. J. Watson Research Center. He obtained his Ph.D. and MS in ECE as well as MS in Applied Math from UIUC, and B.Tech in Electrical Engineering from IIT Madras. His research interests span the areas of Control, Optimization, Algorithms and Applied Probability. In particular, he works on Reinforcement Learning theory, scheduling, resource allocation and revenue optimization problems that arise in a variety of systems including Data Centers, Cloud Computing, Wireless Networks, Block Chains, Ride hailing systems, etc. He is a recipient of the biennial “Best Publication in Applied Probability” award in 2017 and the “CTL/BP Junior Faculty Teaching Excellence Award” in 2020.