Scheduling Periodic Messages on a Shared Link without Buffering

Cloud-RAN, a novel architecture for modern mobile networks, relocates processing units from
antenna to distant data centers. This shift introduces the challenge of ensuring low latency
for the periodic messages exchanged between antennas and their respective processing units.
In this study, we tackle the problem of devising an efficient periodic message assignment
scheme under the constraints of fixed message size and period without contention nor buffering.
We address this problem by modeling it on a common network topology, wherein contention arises
from a single shared link servicing multiple antennas. While reminiscent of coupled-task scheduling, the introduction of periodicity adds a unique dimension to the problem. We study how the
problem behaves with regard to the load of the shared link, and we focus on proving that,
for load as high as possible, a solution always exists and it can be found in polynomial time.
The main contributions of this article are two polynomial-time algorithms, which find a
solution for messages of any size 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, shedding light on the effectiveness of greedy algorithms in practical applications.