Is Deadline Oblivious Scheduling Efficient for Controlling Real-Time Traffic in Cellular Downlink Systems?
Is Deadline Oblivious Scheduling Efficient for Controlling Real-Time Traffic in Cellular Downlink Systems?
复制标题
DOI：
10.1109/infocom41043.2020.9155523
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Sherif ElAzzouni;E. Ekici;N. Shroff
中科院分区：
文献类型：
--
作者：
Sherif ElAzzouni;E. Ekici;N. Shroff
5G网络中带宽密集型延迟关键流量的出现，如虚拟现实和云游戏，激发了人们对具有硬截止期限的流的无线资源分配问题的兴趣。试图解决这个问题带来了以下两个关键挑战：（i）流到达和无线信道状态信息对于基站（BS）是先验未知的，因此，需要以在线方式做出分配决策。(ii)试图在无线环境中最大化回报的资源分配算法可能是不公平的，导致某些用户无法接受的服务。在本文的第一部分中，我们将向截止日期敏感的流量分配资源的问题建模为在线凸优化问题，其中BS获得每请求奖励，该奖励取决于在所需截止日期内传输的流量量。我们解决的问题是，我们是否可以有效地解决这个问题，以低复杂性。特别是，我们是否可以设计一个恒定的竞争调度算法，是遗忘的请求的最后期限。为此，我们提出了一个原始-对偶截止日期不经意（DO）算法，并表明它是约3.6-竞争。此外，我们通过模拟表明，我们的算法非常密切地跟踪有先见之明的离线解决方案，显着优于以前提出的几种算法。我们的研究结果表明，即使调度器可能不知道每个流的最后期限，它仍然可以实现良好的理论和经验性能。在第二部分中，我们对分配施加随机约束，要求保证每个用户达到一定的及时吞吐量（在一段时间内的最后期限内交付的流量）。我们提出了一个修改后的版本，我们的算法，称为长期公平的最后期限遗忘（LFDO）算法的设置。我们结合联合收割机的随机优化的李雅普诺夫框架与原始对偶分析的在线算法，表明LFDO保留了DO的高性能，同时满足长期的随机约束。
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.