Is Deadline Oblivious Scheduling Efficient for Controlling Real-Time Traffic in Cellular Downlink Systems?

The emergence of bandwidth-intensive latency-critical traffic in 5G Networks, such as Virtual Reality and Cloud Gaming, has motivated interest in wireless resource allocation problems for flows with hard-deadlines. Attempting to solve this problem brings about the following two key challenges: (i) The flow arrival and the wireless channel state information are not known to the Base Station (BS) apriori, thus, the allocation decisions need to be made in an online manner. (ii) Resource allocation algorithms that attempt to maximize a reward in the wireless setting will likely be unfair, causing unacceptable service for some users. In the first part of this paper, we model the problem of allocating resources to deadline-sensitive traffic as an online convex optimization problem, where the BS acquires a per-request reward that depends on the amount of traffic transmitted within the required deadline. We address the question of whether we can efficiently solve that problem with low complexity. In particular, whether we can design a constant-competitive scheduling algorithm that is oblivious to requests' deadlines. To this end, we propose a primal-dual Deadline-Oblivious (DO) algorithm, and show it is approximately 3.6-competitive. Furthermore, we show via simulations that our algorithm tracks the prescient offline solution very closely, significantly outperforming several algorithms that were previously proposed. Our results demonstrate that even though a scheduler may not know the deadlines of each flow, it can still achieve good theoretical and empirical performance. In the second part, we impose a stochastic constraint on the allocation, requiring a guarantee that each user achieves a certain timely throughput (amount of traffic delivered within the deadline over a period of time). We propose a modified version of our algorithm, called the Long-term Fair Deadline Oblivious (LFDO) algorithm for that setup. We combine the Lyapunov framework for stochastic optimization with the Primal-Dual analysis of online algorithms, to show that LFDO retains the high-performance of DO, while satisfying the long-term stochastic constraints.