"Low-Complexity Scheduling Policies for Achieving Throughput and Delay Optimality in Multi-channel (OFDM) Downlink Systems”


Professor Ness B. Shroff, Ohio Eminent Scholar in Networking and Communications
Chaired Professor of ECE and CSE

DateTime: 
Wednesday, April 25, 2012 - 10:00am - 12:00pm
Location: 

CoRE Building Lecture Hall

Abstract

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 4G multi-channel 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 multi-channel systems, such as OFDM, the Transmission Time Interval (TTI), within which the scheduling decisions need to be made, is typically on 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 will present a unifying framework for designing low-complexity scheduling policies in the downlink of multi-channel (e.g., OFDM-based) wireless networks that can provide optimal performance in terms of both throughput and delay. We first develop new easy-to verify sufficient conditions for rate-function delay-optimality in the many-channel many-user asymptotic regime. and for throughput-optimality in non-asymptotic settings.

The sufficient conditions enable us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. While a recently developed scheduling policy is both throughput-optimal and rate-function delay-optimal, it has a very high complexity of O(n^5), where n is the number of channels or users, which makes it impractical. By intelligently combining policies from the classes of OPF policies and MWF policies, we design hybrid 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 allows an explicit trade-off between complexity and delay performance.

Biography

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, IEEE Network Magazine, and the Networking Science 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.