EE Professor Javad Ghaderi and PhD Student Christos Tsanikidis Receive the 2020 IEEE INFOCOM Best Paper Award

In their work, Ghaderi and his student provide causal scheduling algorithms for any traffic (arrival and deadline) process that evolves as an ``unknown’’ Markov chain (without knowing what packets with what deadlines arrive in future). Their algorithms significantly outperform greedy maximal scheduling policies. They have shown that it is possible to achieve a constant fraction of ``real-time’’ throughput region in any general network topology, and for any traffic Markov chain, without knowing the Markov chain. Their proposed randomized algorithms achieve at least 0.63 of optimal for collocated networks, and at least 0.5 of optimal for general networks.

By
Eliese Lissner
July 15, 2020

The paper “On the Power of Randomization for Scheduling Real-Time Traffic in Wireless Networks”, coauthored by EE Professor Javad Ghaderi and his PhD student Christos Tsanikidis won the Best Paper Award at IEEE INFOCOM 2020.

IEEE INFOCOM (IEEE International Conference on Computer Communications) is a top ranked conference in the communications and networking areas. This year, the conference received 1,354 paper submissions, out of which 268 papers were accepted (acceptance rate: 19.7%), and three papers were awarded Best Paper.

Much of the prior work on scheduling algorithms for wireless networks focuses on maximizing long-term throughput. However, for many emerging real-time applications (e.g., IoT, vehicular networks, edge computing), delays and deadline guarantees on packet delivery are more important than just long-term throughput. In these applications, packets that are not received within their deadlines are of little or no use and are discarded.

“We have created a new class of randomized algorithms and techniques for scheduling deadline-constrained packets in wireless networks, which is significantly more challenging than traditional scheduling. I am honored that our result has been recognized by the INFOCOM Best Paper Award,” said Ghaderi.

The objective is to maximize the fraction of packets of each link which are delivered within their deadlines, which is referred to as delivery ratio. In the past 10 years, this problem had been studied under restrictive frame-based traffic models (where packet arrivals and their deadlines are known ahead of time), or greedy maximal scheduling schemes.

In their work, Ghaderi and his student provide causal scheduling algorithms for any traffic (arrival and deadline) process that evolves as an ``unknown’’ Markov chain (without knowing what packets with what deadlines arrive in future). Their algorithms significantly outperform greedy maximal scheduling policies. They have shown that it is possible to achieve a constant fraction of ``real-time’’ throughput region in any general network topology, and for any traffic Markov chain, without knowing the Markov chain. Their proposed randomized algorithms achieve at least 0.63 of optimal for collocated networks, and at least 0.5 of optimal for general networks.

In their work, Ghaderi and his student provide causal scheduling algorithms for any traffic (arrival and deadline) process that evolves as an ``unknown’’ Markov chain (without knowing what packets with what deadlines arrive in future). Their algorithms significantly outperform greedy maximal scheduling policies. They have shown that it is possible to achieve a constant fraction of ``real-time’’ throughput region in any general network topology, and for any traffic Markov chain, without knowing the Markov chain. Their proposed randomized algorithms achieve at least 0.63 of optimal for collocated networks, and at least 0.5 of optimal for general networks.