Advanced Networks Colloquium: Ness Shroff, "Low-Complexity Scheduling Policies for OFDM"
Friday, February 24, 2012
1146 A.V. Williams Building
301 405 6579
Advanced Networks Colloquium
Low-Complexity Scheduling Policies for Achieving Throughput and Delay Optimality in OFDM Downlink Systems
Ohio Eminent Scholar in Networking and Communications
Professor of ECE and CSE
The Ohio State University
| video |
The dramatic increases in demands from multimedia applications are putting an enormous strain on current cellular system infrastructure. Hence, we are witnessing significant research and development efforts on fourth generation (4G) OFDM-based wireless cellular systems (e.g., LTE and WiMax) that target new ways to achieve higher data rates, lower latencies, and a much better user experience. An important requirement for achieving these goals is to design efficient scheduling policies that can simultaneously provide high throughput and low delay. In these OFDM systems, the Transmission Time Interval (TTI), within which the scheduling decisions need to be made, is typically in the order of a few milliseconds. On the other hand, there are hundreds of orthogonal channels that can be allocated to different users. Hence, many decisions have to be made within a short scheduling cycle and it is critical that scheduling policies must be of low complexity.
In this talk, we focus on developing a unifying framework on designing low-complexity scheduling policies for a single-cell OFDM downlink system that can provide optimal performance in terms of both throughput and delay. We first characterize the sufficient conditions for throughput-optimality in general settings and for rate-function delay-optimality (i.e., maximizing the decay-rate of the probability that the largest head-of-line packet delay in the system exceeds a certain threshold) in a many-user many-channel regime. The sufficient conditions enable us to prove throughput-optimality for a large class of scheduling policies and rate-function delay-optimality for a class of Oldest Packets First (OPF) policies, respectively. In the current literature, there is no existing policy that is both throughput-optimal and rate-function delay-optimal, with a complexity better than O(n^5), where n is the number of users or channels. We design scheduling policies that have a low complexity of O(n^2.5 log n), without losing either throughput-optimality or rate-function delay-optimality. We further develop two simpler greedy policies that are both throughput-optimal and have a positive rate-function. We show through simulations that empirically these simpler mechanisms have near-optimal value of rate-function in various scenarios. Finally, we propose a class of throughput-optimal policies with even lower complexity that allow an explicit trade-off between complexity and delay performance.
Ness 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 professorship in Networking and Communications, in the departments of ECE and CSE. Since 2009, he also serves as a Guest Chaired professor of Wireless Communications at Tsinghua University, Beijing, China. His research interests span the areas of communication, social, and cyberphysical networks. He is especially interested in fundamental problems in the design, control, performance, pricing, and security of these networks. Dr. Shroff is a past editor for IEEE/ACM Trans. on Networking and the IEEE Communication Letters. He currently serves on the editorial board of the Computer Networks Journal. He has chaired various conferences and workshops and co-organized workshops for the NSF to chart the future of communication networks. Dr. Shroff is a Fellow of the IEEE and an NSF CAREER awardee. He has received numerous best paper awards for his research, e.g., at IEEE INFOCOM 2008, IEEE INFOCOM 2006, IEEE IWQoS 2006, Journal of Communication and Networking 2005, Computer Networks 2003, and one of two runner-up papers at IEEE INFOCOM 2005.