Tata Institute of Fundamental Research
Low-Complexity Scheduling Policies for Achieving Throughput and Delay Optimality in Multi-channel (OFDM) Downlink Systems
Seminar
Speaker:
Ness Shroff (The Ohio State University
Department of Electrical and Computer Engineering
205 Dreese Laboratories, 2015 Neil Avenue
Columbus 43210
United States of America)
Organiser:
Sandeep K Juneja
Date:
Wednesday, 11 Jun 2014, 12:00 to 13:00
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
Abstract: The dramatic increases in demands from multimedia applications have put an enormous strain on the current cellular system infrastructure. This has resulted in 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. Further, 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, which means that it is critical that scheduling policies must have low complexity. Thus, a major challenge in the development of next generation wireless networks is to design scheduling policies that can simultaneously provide high throughput, low delay, and low complexity. In this talk, I 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 general (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. 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, rendering 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)$, and are yet both throughput and rate-function delay optimal. We further develop two simpler greedy policies that are throughput-optimal and have are near delay-optimal. The efficacy of our schemes and comparisons with the state-of-the-art are also illustrated through simulations.
Bio: 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. 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. From 2009-2012, he served as a Guest Chaired professor of Wireless Communications at Tsinghua University,Beijing, China, and currently holds an honorary Guest professor at Shanghai Jiaotong University in 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. He currently serves as editor-at-large of IEEE/ACM Trans. on Networking, and on the editorial board of IEEE Trans. on Networked Control systems, IEEE Network Magazine, and the Networking Science journal. Dr. Shroff is a Fellow of the IEEE and an NSF CAREER awardee. His work has received numerous best paper awards for his research, e.g., at IEEE INFOCOM 2008, IEEE INFOCOM 2006, Journal of Communication and Networking 2005, and Computer Networks 2003 (his papers also received runner-up awards at IEEE INFOCOM 2005 and IEEE INFOCOM 2013), and also student best paper awards (from all papers whose first author is a student) at IEEE WiOPT 2013, IEEE WiOPT 2012, and IEEE IWQoS 2006. In 2014, he received the IEEE INFOCOM Achievement award for seminal contributions to scheduling and resource allocation in wireless networks.
| Speaker: | Ness Shroff (The Ohio State University Department of Electrical and Computer Engineering 205 Dreese Laboratories, 2015 Neil Avenue Columbus 43210 United States of America) |
| Organiser: | Sandeep K Juneja |
| Date: | Wednesday, 11 Jun 2014, 12:00 to 13:00 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
Abstract: The dramatic increases in demands from multimedia applications have put an enormous strain on the current cellular system infrastructure. This has resulted in 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. Further, 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, which means that it is critical that scheduling policies must have low complexity. Thus, a major challenge in the development of next generation wireless networks is to design scheduling policies that can simultaneously provide high throughput, low delay, and low complexity. In this talk, I 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 general (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. 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, rendering 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)$, and are yet both throughput and rate-function delay optimal. We further develop two simpler greedy policies that are throughput-optimal and have are near delay-optimal. The efficacy of our schemes and comparisons with the state-of-the-art are also illustrated through simulations.
Bio: 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. 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. From 2009-2012, he served as a Guest Chaired professor of Wireless Communications at Tsinghua University,Beijing, China, and currently holds an honorary Guest professor at Shanghai Jiaotong University in 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. He currently serves as editor-at-large of IEEE/ACM Trans. on Networking, and on the editorial board of IEEE Trans. on Networked Control systems, IEEE Network Magazine, and the Networking Science journal. Dr. Shroff is a Fellow of the IEEE and an NSF CAREER awardee. His work has received numerous best paper awards for his research, e.g., at IEEE INFOCOM 2008, IEEE INFOCOM 2006, Journal of Communication and Networking 2005, and Computer Networks 2003 (his papers also received runner-up awards at IEEE INFOCOM 2005 and IEEE INFOCOM 2013), and also student best paper awards (from all papers whose first author is a student) at IEEE WiOPT 2013, IEEE WiOPT 2012, and IEEE IWQoS 2006. In 2014, he received the IEEE INFOCOM Achievement award for seminal contributions to scheduling and resource allocation in wireless networks.
Bio: 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. 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. From 2009-2012, he served as a Guest Chaired professor of Wireless Communications at Tsinghua University,Beijing, China, and currently holds an honorary Guest professor at Shanghai Jiaotong University in 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. He currently serves as editor-at-large of IEEE/ACM Trans. on Networking, and on the editorial board of IEEE Trans. on Networked Control systems, IEEE Network Magazine, and the Networking Science journal. Dr. Shroff is a Fellow of the IEEE and an NSF CAREER awardee. His work has received numerous best paper awards for his research, e.g., at IEEE INFOCOM 2008, IEEE INFOCOM 2006, Journal of Communication and Networking 2005, and Computer Networks 2003 (his papers also received runner-up awards at IEEE INFOCOM 2005 and IEEE INFOCOM 2013), and also student best paper awards (from all papers whose first author is a student) at IEEE WiOPT 2013, IEEE WiOPT 2012, and IEEE IWQoS 2006. In 2014, he received the IEEE INFOCOM Achievement award for seminal contributions to scheduling and resource allocation in wireless networks.