Scheduling Periodic Messages on a Shared Link Without Buffering

Cloud-RAN is a recent architecture for mobile networks where the processing units are located indistant data centers while, until now, they were attached to antennas. The main challenge, to fulfillprotocol constraints, is to guarantee low latency for the periodic messages sent from each antenna toits processing unit and back. The problem we address is to find a periodic sending scheme of thesemessages without contention nor buffering, when all messages are of the same size and the period isfixed.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 ofclassical scheduling and packing problems, but the periodicity introduces a new twist. We studyhow the problem behaves with regard to the load of the shared link. The main contributions arepolynomial time algorithms which always find a solution for an arbitrary size of messages and loadat most 2/5 or for messages of size one and load at most ϕ − 1, the golden ratio conjugate. Wealso prove that a randomized greedy algorithm finds a solution on almost all instances with highprobability, explaining why most greedy algorithms work so well in practice