论文标题
在共享链接上安排定期消息
Scheduling periodic messages on a shared link
论文作者
论文摘要
Cloud-Ran是移动网络的最新体系结构，处理单元位于遥远的数据中心，而到目前为止，它们已连接到天线。满足协议约束的主要挑战是确保从每个天线发送到其处理单元和背部的定期消息的延迟较低。我们要解决的问题是找到这些消息的定期发送方案\ emph {无争议或缓冲}时，当所有消息均具有相同的大小并且周期固定时。 我们研究了周期性的消息分配问题，将这种情况建模在共同拓扑上，其中争论源于所有天线共享的单个链接。问题是让人联想到耦合任务计划，但是周期性引入了新的转折。我们研究问题在共享链接的\ emph {load}方面的行为。主要贡献是多项式时间算法\ emph {始终}找到任意尺寸的消息和最多加载的解决方案，最多是$ 2/5 $，或者最多尺寸的消息和最多加载$ ϕ-1 $，黄金比率共轭。我们还证明，一种随机贪婪的算法在几乎所有具有很高可能性的实例上都找到了解决方案，这解释了为什么大多数贪婪的算法在实践中效果很好。
Cloud-RAN is a recent architecture for mobile networks where the processing units are located in distant data centers while, until now, they were attached to antennas. The main challenge, to fulfill protocol constraints, is to guarantee low latency for the periodic messages sent from each antenna to its processing unit and back. The problem we address is to find a periodic sending scheme of these messages \emph{without contention nor buffering}, when all messages are of the same size and the period is fixed. We study the periodic message assignment problem modeling this situation on a common topology, where contention arises from a single link shared by all antennas. The problem is reminiscent of coupled-task scheduling, but the periodicity introduces a new twist. We study how the problem behaves with regard to the \emph{load} of the shared link. The main contributions are polynomial-time algorithms which \emph{always} find a solution for an arbitrary size of messages and load at most $2/5$ or for messages of size one and load at most $ϕ- 1$, the golden ratio conjugate. We also prove that a randomized greedy algorithm finds a solution on almost all instances with high probability, explaining why most greedy algorithms work so well in practice.
