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

Date: 4:00pm, October 19, 2016
Location:  EE Conference Room, 1306 Mudd
Speaker: Siva Theja Maguluri, IBM T. J. Watson Research Center, and Georgia Tech

Abstract:  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.
 
Biography:  Siva Theja Maguluri is a Research Staff Member in the Mathematical Sciences Department at IBM T. J. Watson Research Center. He obtained his Ph.D. from the 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, Networks, and Game Theory. Next spring, he will start as an Assistant Professor in the School of Industrial and Systems Engineering at Georgia Tech.
 
Hosted by Professor Javad Ghaderi


500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University