Delay Optimality in Load Balancing Systems
Ness B. Shroff, Ohio State University
2019-11-06 10:00:00 ~ 2019-11-06 11:30:00
Room 1-418A, SEIEE Building
Haiming Jin, Assistant Professor, John Hopcroft Center for Computer Science
We are in the midst of a major data revolution. The total data generated by humans from the dawn of civilization until the turn of the new millennium is now being generated every other day. Driven by a wide range of data-intensive devices and applications, this growth is expected to continue its astonishing march, and fuel the development of new and larger data centers. In order to exploit the low-cost services offered by these resource-rich data centers, application developers are pushing computing and storage away from the end-devices and instead deeper into the data-centers. Hence, the end-users' experience is now dependent on the performance of the algorithms used for data retrieval, and job scheduling within the data-centers. In particular, providing low-latency services are critically important to the end-user experience for a wide variety of applications.
Our goal has been to develop the analytical foundations and methodologies to enable cloud storage and computing solutions that result in low-latency services. In this talk, I will focus on our efforts on reducing the latency through load balancing in large-scale data center systems. In our model each arrival is randomly dispatched to one of the servers with queue length below a threshold; if none exists, this arrival is randomly dispatched to one of the entire set of servers. We are interested in the fundamental relationship between the threshold and the delay performance of the system in heavy traffic. To this end, we first establish the following necessary condition to guarantee heavy-traffic delay optimality: the threshold will grow to infinity as the exogenous arrival rate approaches the boundary of the capacity region (i.e., the load intensity approaches one) but the growth rate should be slower than a polynomial function of the mean number of tasks in the system. As a special case of this result, we directly show that the delay performance of the popular pull-based policy Join-Idle-Queue (JIQ) lies strictly between that of any heavy-traffic delay optimal policy and that of random routing. We further show that a sufficient condition for heavy-traffic delay optimality is that the threshold grows logarithmically with the mean number of tasks in the system. This result resolves a generalized version of the 25 year old conjecture by Kelly and Laws.
Ness B. Shroff received his Ph.D. degree in Electrical Engineering from Columbia University in 1994. He joined Purdue university immediately thereafter as an Assistant Professor in the school of ECE. At Purdue, he became Full Professor of ECE in 2003 and director of CWSA in 2004, a university-wide center on wireless systems and applications. In July 2007, he joined The Ohio State University, where he holds the Ohio Eminent Scholar endowed chair in Networking and Communications, in the departments of ECE and CSE. He holds or has held visiting (chaired) professor positions at Tsinghua University, Beijing, China, Shanghai Jiao Tong University, Shanghai, China, and the Indian Institute of Technology, Bombay, India. Dr. Shroff is currently an editor at large of IEEE/ACM Trans. on Networking, a senior editor of the IEEE Transactions on Control of Networked Systems and an editor of the IEEE Networks Magazine. He has received numerous best paper awards for his research; most notably he received the IEEE INFOCOM best paper awards in 2006, 2008, and 2016, and runner up awards in 2005 and 2013. He also received the best paper of the year in the journal of Communication and Networking (2005) and in Computer Networks (2003). In addition, his papers have received the best student paper award (from all papers whose first author is a student) at ACM Sigmetrics 2017, IEEE WiOpt 2013, IEEE WiOpt 2012, and IEEE IWQoS 2006. Dr. Shroff is on the list of highly cited researchers from Thomson Reuters ISI (previously ISI web of Science) in 2014 and 2015 and in Thomson Reuters Book on The World’s Most Influential Scientific Minds in 2014. He also received the IEEE INFOCOM achievement award for seminal contributions to scheduling and resource allocation in wireless networks.