Uploaded February 2021 | Updated September 2026, 2 weeks ago
On the Power of Randomization for Scheduling Real-Time Traffic in Wireless Networks
Guest Speaker: Javad Ghaderi, Associate Professor of Electrical Engineering, Columbia University
Hosted By: Debasis Mitra, Professor of Electrical Engineering, Columbia University; and Chair of DSI Sense, Collect and Move Data Center
Abstract: Much of the prior work on scheduling algorithms for wireless networks focuses on maximizing throughput. However, for many real-time applications (e.g., vehicular networks, IoT, edge computing) delays and deadline guarantees on packet delivery can be more important than just long-term throughput. In this talk, we consider the problem of scheduling deadline-constrained packets in wireless networks, under a conflict-graph interference model. The objective is to guarantee that at least a certain fraction of packets of each link are delivered within their deadlines, which is referred to as delivery ratio. This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (Largest-Deficit First). In this talk, we pursue a different approach through a careful randomization over the choice of maximal links that can transmit at each time. We design randomized policies that can achieve delivery ratios much higher than what is achievable by deterministic policies such as LDF or MWS. Further, our results apply to traffic (arrival and deadline) processes that evolve as an unknown Markov chain. Hence, this work is an improvement with respect to both efficiency and traffic assumptions compared to the past work.
Joint work with PhD student Christos Tsanikidis.
Bio: Javad Ghaderi is an Associate Professor of Electrical Engineering at Columbia University. His research interests include algorithms, optimization, and stochastic processes with application to wireless networks and data centers. He received his B.Sc. from the University of Tehran, Iran, in 2006, M.Sc. from the University of Waterloo, Canada, in 2008, and Ph.D. from the University of Illinois at Urbana-Champaign in 2013. He spent a one-year Simons Postdoctoral Fellowship at the University of Texas at Austin before joining Columbia. He has received several awards including Best Student Paper Finalist at ACC 2013, Best Paper Award at ACM CoNEXT 2016, NSF CAREER Award in 2017, Best Student Paper Award at IFIP Performance 2020, and Best Paper Award at IEEE INFOCOM 2020.
On the Power of Randomization for Scheduling Real-Time Traffic in Wireless Networks
Guest Speaker: Javad Ghaderi, Associate Professor of Electrical Engineering, Columbia University
Hosted By: Debasis Mitra, Professor of Electrical Engineering, Columbia University; and Chair of DSI Sense, Collect and Move Data Center
Abstract: Much of the prior work on scheduling algorithms for wireless networks focuses on maximizing throughput. However, for many real-time applications (e.g., vehicular networks, IoT, edge computing) delays and deadline guarantees on packet delivery can be more important than just long-term throughput. In this talk, we consider the problem of scheduling deadline-constrained packets in wireless networks, under a conflict-graph interference model. The objective is to guarantee that at least a certain fraction of packets of each link are delivered within their deadlines, which is referred to as delivery ratio. This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (Largest-Deficit First). In this talk, we pursue a different approach through a careful randomization over the choice of maximal links that can transmit at each time. We design randomized policies that can achieve delivery ratios much higher than what is achievable by deterministic policies such as LDF or MWS. Further, our results apply to traffic (arrival and deadline) processes that evolve as an unknown Markov chain. Hence, this work is an improvement with respect to both efficiency and traffic assumptions compared to the past work.
Joint work with PhD student Christos Tsanikidis.
Bio: Javad Ghaderi is an Associate Professor of Electrical Engineering at Columbia University. His research interests include algorithms, optimization, and stochastic processes with application to wireless networks and data centers. He received his B.Sc. from the University of Tehran, Iran, in 2006, M.Sc. from the University of Waterloo, Canada, in 2008, and Ph.D. from the University of Illinois at Urbana-Champaign in 2013. He spent a one-year Simons Postdoctoral Fellowship at the University of Texas at Austin before joining Columbia. He has received several awards including Best Student Paper Finalist at ACC 2013, Best Paper Award at ACM CoNEXT 2016, NSF CAREER Award in 2017, Best Student Paper Award at IFIP Performance 2020, and Best Paper Award at IEEE INFOCOM 2020.
