# Scheduling periodic messages on a shared link without buffering

Maël Guiraud, Yann Strozecki

<figure><img src="image_1.png" /></figure>

## To cite this version:

Maël Guiraud, Yann Strozecki. Scheduling periodic messages on a shared link without buffering. Journal of Scheduling, 2024, 10.1007/s10951-024-00813-0. hal-04727150

HAL Id: hal-04727150

https://hal.science/hal-04727150v1

Submitted on 17 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Scheduling Periodic Messages on a Shared Link without Buffering

Maël Guiraud

LINEACT Laboratory, Campus CESI Nanterre - Paris 93 boulevard de la Seine BP 602 Cedex
92006 Nanterre, France

mguiraud@cesi.fr

Yann Strozecki

DAVID Laboratory, Université de Versailles-Saint-Quentin, 45 Avenue des Etats-Unis, Versailles,
France

yann.strozecki@uvsq.fr

## Abstract

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 *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 classical scheduling and packing problems, but the periodicity introduces a new twist. We study how the problem behaves with regard to the *load* of the shared link. The main contributions are polynomial time algorithms which *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 $\phi - 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.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** Periodic Scheduling, Greedy Algorithm, Randomized Algorithm, Experimental Algorithms, C-RAN

**Digital Object Identifier** 10.4230/LIPIcs...

## 1 Introduction

The Radio Access Networks (RAN) architecture is the part of the mobile phone network which communicates with mobile handsets. It is composed of base stations managing radio emissions and multiple computations, connected to the core network [1]. An objectives of 5G+ is to split a base station in two parts: The Remote Radio Head (RRH), in charge of the radio emissions, and the BaseBand Unit (BBU<fnref n="1" />) in charge of the computations. In the Cloud RAN architecture (C-RAN), to reduce maintenance and energy consumption costs [2, 3, 4], the BBUs are gathered in one or several datacenters and are connected to the RRHs via the *fronthaul* network. The main challenge of C-RAN is to reach a latency compatible with transport protocols [5], to support functions like HARQ (Hybrid Automatic Repeat reQuest) in only 3ms [1]. The latency is measured between the sending of a message by an RRH and the reception of the answer, computed by a BBU in the cloud. In addition to the latency constraint, the specificity of C-RAN is the periodicity of the data transfer in

<figure><img src="image_3.png" /></figure>

<footnote n="1">¹ Others terminologies exist in the literature. The results of this work are fully compatible with any variation of the C-RAN architecture.</footnote>
XX:2 Scheduling Periodic Messages on a Shared Link without Buffering

the fronthaul network between RRHs and BBUs: messages need to be emitted and received each millisecond [6, 7, 8].

Our aim is to operate a C-RAN on a low-cost shared switched network: several (tens of) antennas share a high-speed link to send their periodic messages to one (or several) data center. This shared link is the only contention point for a message going to the data center and it is also the contention point for the answer sent back by the data center to the antenna. This model with two contention points (one for the message and one for its answer) also captures other periodic systems such as processors communicating over a bus or sensors doing periodic radio transmissions on the same frequency.

We address the following question: *is it possible to schedule periodic messages on a shared link without using buffers?* Eliminating this source of latency leaves us with more time budget for latency due to the physical length of the routes in the network, and thus allows for wider deployment areas. Our proposed solution is to compute beforehand a *periodic and deterministic* sending scheme, which completely avoids contention.

The algorithmic problem studied, called *Periodic Message Assignment* or PMA, is as follows: Given a period, a message size and, for each message a delay between the two contention points, set a departure time in the period for each message so that they go through both contention points without collision. It is similar to the two flow shop scheduling problem [9] with periodicity. The periodicity adds more constraints, since the sending pattern for a single period must be repeated without creating collision at contention points. In flow shop problems, the aim is usually to minimize the makespan or schedule length, but in our periodic variant, this quantity is infinite. Hence, we choose to look for any periodic schedule without buffering between the two contention points, to minimize the trip time of each message.

The load of a network with a link shared by all messages is the load of this link, defined as the ratio of the bandwidth used to the bandwidth available. In our context, it is the time used by messages on the link in a period, divided by the period. When the load is small, it is easier to design sending scheme without collision, as already noted in [10]. The aim of this article is to understand up to which load, it is always possible to find a sending scheme and to give fast algorithms to produce it. Increasing this load, we can have more antennas sharing the same link, which reduces the cost of deployment of the fronthaul network. Moreover, a method to mix the traffic of the antennas with random sources of traffic requires to find sending schemes for a load as high as possible [11].

Related Works

The model we study was recently introduced in [10, 11] to find sending schedules for C-RAN messages, with buffering allowed. This problem has also been studied for a cycle topology instead of a shared link [12]. In these articles, the main results are heuristics, using classical scheduling algorithms as subroutines, and FPT algorithms which find a sending scheme with minimal latency. The problem of finding sending schemes with no additional latency, which is the subject of this article under the name PMA, is also briefly introduced and studied in [11]. In this article, we propose several new polynomial time algorithms which dramatically improve on the greedy algorithm used to solve PMA in [11], in the worst case or for random instances, both for large and small messages. While a sending scheme without buffering is simpler and less expensive to implement in C-RAN networks than one with buffering, it may not exist. However, we prove in this article that when the load is not too high, there is always a solution without buffering. Moreover, we explain in Sec. 5.2 that to solve the problem of finding sending schedules with small latency, we can solve PMA on normalized
instances, which are easier to solve by the algorithms we present.

Variations on the problem of minimizing latency of periodic messages in networks have been considered and practically solved, using mixed-integer programming [13, 14] or an SMT solver [15], but without theoretical guarantees on the quality of the produced solutions nor on the computation time. Typical applications cited in these works (out of C-RAN) are sensor networks communicating periodically inside cars or planes, or logistic problems in production lines, which can also be captured in our model.

To our knowledge, periodic scheduling problems studied in the literature are quite different from the problem studied in this article. In some works [16, 17], the aim is to minimize the number of processors on which the periodic tasks are scheduled, while our problem corresponds to two processors and a constraint similar to makespan minimization. In cyclic scheduling [18], the aim is to minimize the period of a schedule to maximize the throughput, while our period is fixed. The train timetabling problem [19] and in particular, the periodic event scheduling problem [20] are generalizations of our problem since they take the period as input and can express the fact that two trains (like two messages) should not cross. However, they are much more general: the trains can vary in size, speed, the network can be more complex than consecutive single tracks and there are precedence constraints. Hence, the numerous variants of train scheduling problems are very hard to solve. Therefore, some delay is allowed in different parts of the network to make these problems solvable and most of the research done [19] is devising practical algorithms using branch and bound, mixed-integer programming, genetic algorithms, etc.

## Organization of the Paper

In Sec. 2, we explain how the network is modeled and we introduce the problem PMA. In Sec. 3, we present several greedy algorithms and prove they always find a solution to PMA for moderate loads. These algorithms rely on schemes to build compact enough solutions, to bound measures of the time wasted when scheduling messages.

In Sec. 4 we present deterministic and probabilistic algorithms for messages of size 1, which work for much higher loads than the algorithms designed for arbitrary messages. The deterministic algorithm is not greedy, contrarily to algorithms of Sec. 3, since it uses a swap mechanism that moves already scheduled messages.

In Sec. 5, we prove that hypotheses on the period and the message size can be relaxed. We also show that PMA captures periodic message scheduling in networks with many contention points, as long as the routing is coherent. Finally, we present the performance of all algorithms on random inputs, both on large messages in Sec. 6.1 and small messages in Sec. 6.2. It shows that the algorithms of this article work for random instances with a much higher load than what has been proved in the worst case.

## 2 Modeling a C-RAN Network

In this article, we model a simple network in which periodic messages flow through a single bidirectional link. Each RRH sends messages through the link to its BBU and two messages cannot go at once in the link: this is the first contention point, represented in Fig. 1. Upon receiving a message, a BBU sends an answer back to its RRH, which goes through the link in the other direction: this is the second contention point represented in Fig. 1. Since the answer must be sent back as soon as a message arrives, we see this process
XX:4 Scheduling Periodic Messages on a Shared Link without Buffering

<figure><img src="image_4.png" /><figcaption>Figure 1 C-RAN network with a single shared link modeled by two contention points and delays</figcaption></figure>

as a single message going from an RRH to its BBU and back to the RRH, while traversing
two contention points.

Messages using the link in two different directions do not interact, since the link we model
is full-duplex. In the C-RAN context we consider, *all messages are of the same kind*, hence
they are all of the same size denoted by $\tau$. This **size** represents the time needed to send a
message through a contention point of the network, here the beginning of the link shared by
all antennas.

We denote by $n$ the number of messages, which are numbered from 0 to $n-1$. A message $i$ is characterized by its **delay** $d_i$: when message number $i$ arrives at the beginning of the shared link (first contention point) at time $t$, it returns to the other end of the link on its way back (second contention point) at time $t+d_i$. The model and problem can easily be generalized to any topology, that is any directed acyclic multigraph with any number of contention points, see [11]. We choose here to focus on a realistic network with a single shared link, which is simple enough to obtain theoretical results. It turns out that algorithms solving the problem for a single shared link can be used on networks with many contention points, as long as the routing is coherent, see Sec. 5.3.

The time is *discretized* and the process we consider is *periodic* of fixed integer *period* *P*.
We use the notation [*P*] for the set {0, ..., *P*−1}. A message is emitted an infinite number of
times periodically, hence it is enough to consider any interval of *P* units of time to completely
represent the state of our system by giving the times, in this interval, at which each message
goes through the two contention points. We call the representation of an interval of *P* units
of time in the first contention point the **first period** and the **second period** for the second
contention point.

An **offset** of a message is a choice of time at which it arrives at the first contention point (i.e. in the first period). Let us consider a message $i$ of offset $o_i$, it uses the interval of time $[i]_1 = \{(o_i + t) \mod P \mid 0 \le t < \tau\}$ in the first period and $[i]_2 = \{(d_i + o_i + t) \mod P \mid 0 \le t < \tau\}$ in the second period. Two messages $i$ and $j$ **collide** if either $[i]_1 \cap [j]_1 \ne \emptyset$ or $[i]_2 \cap [j]_2 \ne \emptyset$. If $t \in [i]_1$ (resp. $t \in [i]_2$), we say that message $i$ uses time $t$ in the first period (resp. in the second period).

Our objective is to send all messages so that there is no collision in the shared link. To
-do that, we can choose the offset of each message. An **assignment** $A$ is a function from $[n]$
to $[P]$. The value $A(i)$ is the offset of the message $i$. We say that an assignment is **valid** if
*no pair of messages collide*, as shown in Fig. 2.

Let **Periodic Message Assignment** or PMA be the following problem: given $n$ messages of delays $d_0, \dots, d_{n-1}$, a period $P$ and a size $\tau$, find a valid assignment or decide there is none. When a valid assignment is found, we say the problem is solved **positively**.

It is yet unknown whether PMA is NP-hard. However, it has been proven that, when parameterized by $n$ the number of messages, the problem is FPT [10]. A slight generalization of PMA presented in Sec. 5.3, with more contention points, but each message only going
<figure><img src="image_5.png" /><figcaption>Figure 2 An instance of PMA with 3 messages, $P = 10$, $\tau = 2$, and one assignment</figcaption></figure>

through two of them as in PMA, is NP-hard [10]. If the shared link is not full-duplex, that is, there is a single contention point and each message goes through it twice, it is also NP-hard, since we can encode a similar non-periodic problem [21]. Hence, we conjecture that PMA is NP-hard.

Because we are interested in PMA when it can be solved positively, we study it when the load of the system is small enough. The **load** is defined as the number of units of time used in a period by all messages divided by the period that is $n\tau/P$. There cannot be an assignment when the load is larger than one; we prove in this article that, for moderate loads, there is always an assignment and that it can be found by polynomial time algorithms. This kind of result is helpful when solving the following optimization version of PMA: given a set of messages, find the largest subset which admits an assignment. A weighted version, where the messages have different values can also be considered. An optimal solution to the optimization problem is a set of messages corresponding to a load of at most 1. Assume we have an algorithm that always finds an assignment for an instance of load $\lambda$. Then, such an algorithm finds an assignment for any subset of load $\lambda$ and is an approximation algorithm for the optimization problem with approximation ratio $\lambda$.

## 3 Greedy Algorithms for Arbitrary Messages

In this section, we study the case of arbitrary values for $\tau$. When modeling a C-RAN network, we choose the time granularity, and we could set it so $\tau = 1$ for simplicity. However, the size of a link and thus the delay of a message is typically of the same magnitude as $\tau$, therefore setting $\tau = 1$ is a too coarse granularity to faithfully model the network.

A **partial assignment** $A$ is a function defined from a subset $S$ of $[n]$ to $[P]$. The cardinality of $S$ is the **size** of partial assignment $A$. A message in $S$ is **scheduled** (by $A$), and a message not in $S$ is **unscheduled**. We only build valid partial assignments: no pair of messages of $S$ collide. If $A$ has domain $S$, and $i \notin S$, we define the extension of $A$ to the message $i$ by the offset $o$, denoted by $A[i \to o]$, as $A$ on $S$ and $A[i \to o](i) = o$.

All presented algorithms build an assignment incrementally, by growing the size of a partial assignment. Moreover, algorithms in this section are *greedy*: Once an offset is chosen for a message, it is never changed. In the rest of the paper, we sometimes compare the relative position of messages to detect collisions, but one should remember that the time is periodic and these are relative positions on a circle. In some remarks and computations, we may omit to write *mod P*, in order to not overburden the presentation.

### 3.1 First Fit

Consider some partial assignment $A$, in the first period, the message $i$ uses times in $[i]_1 =$ $[A(i), A(i) + \tau - 1 \mod P]$. If a message $j$ is scheduled by $A$, with $A(j) < A(i)$, then the
XX:6 Scheduling Periodic Messages on a Shared Link without Buffering

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

last time it uses in the first period is $A(j) + \tau - 1$ and it should be less than $A(i)$, which implies that $A(j) \le A(i) - \tau$. Symmetrically, if $A(j) > A(i)$, to avoid collision between messages $j$ and $i$, we have $A(j) \ge A(i) + \tau$. Hence, message $i$ forbids the interval $[A(i) - \tau + 1 \mod P, A(i) + \tau - 1 \mod P]$ as offsets for messages still not scheduled, because of its use of time in the first period. The same reasoning shows that $2\tau - 1$ offsets are also forbidden because of the times used in the second period. Hence, if $|S|$ messages are already scheduled, then at most $|S|(4\tau - 2)$ offsets are forbidden for an unscheduled message. The real number of forbidden offsets may be smaller since the same offset can be forbidden both because of a message on the first and on the second period.

To formalize the idea of the previous paragraph, we introduce FO($A$), which is the number of offsets forbidden by $A$. Let $A$ be a partial assignment defined over $S$ and $i \notin S$, FO($A$) is the maximum over all values of $d_i \in [P]$ of $|\{o \in [P] | A[i \to o] \text{ has a collision}\}|$. In the previous paragraph, we have proved that FO($A$) is at most $(4\tau - 2)|S|$.

Let First Fit be the following algorithm: for each unscheduled message (in the order they are given), try all offsets from 0 to $P - 1$ until one does not create a collision with the current assignment and use it to extend the assignment. If FO($A$) < $P$, then whatever the delay of the message we want to extend $A$ with, there is an offset to do so. Since FO($A$) $\le (4\tau - 2)|S|$ and $|S| < n$, First Fit (or any greedy algorithm) always succeeds when $(4\tau - 2)n \le P$, that is when the load $n\tau/P$ is less or equal to $1/4$. It turns out that First Fit always creates compact assignments (as defined in [11]), that is a message is always next to another one in one of the two periods. Hence, we can prove a better bound on FO($A$), when $A$ is built by First Fit, as stated in the following theorem.

230

**▶ Theorem 1.** *First Fit solves PMA positively on instances of load at most 1/3.*

231

232

233

234

235

236

237

238

239

240

241

242

*Proof.* We show by induction on the size of $S$, that FO($A$) $\le |S|(3\tau - 1) + \tau - 1$. For $|S| = 1$, it is clear since a single message forbid at most $(3\tau - 1) + \tau - 1 = 4\tau - 2$ offsets, as explained before. Now, assume FO($A$) $\le |S|(3\tau - 1) + \tau - 1$ and consider a message $i \notin S$ such that First Fit builds $A[i \to o]$ from $A$. By definition of First Fit, choosing $o-1$ as offset creates a collision. W.l.o.g. say it is a collision in the first period. It means that there is a scheduled message between $o - \tau$ and $o-1$, hence all these offsets are forbidden by $A$. The same offsets are also forbidden by the choice of $o$ as offset for $i$, hence at most $3\tau - 1$ new offsets are forbidden, that is FO($A[i \to o]$) $\le$ FO($A$) + $(3\tau - 1)$, which proves the induction. The value of FO($A$) is increasing during First Fit, hence it is maximal when the last element is scheduled when it is bounded by $(n-1)(3\tau - 1) + \tau - 1 < 3n\tau$. Therefore First Fit succeeds when FO($A$) < $P$, which happens when $3n\tau \le P$, i.e. when the load is less or equal to $1/3$. ◀

<figure><img src="image_6.png" /></figure>

243

244

245

246

247

A naïve implementation of First Fit is in $O(nP)$, since for each of the $n$ messages $P$ offsets could be tried. However, it is not useful to consider every possible offset at each step. By maintaining a list of increasing positions of scheduled messages in the first and second period, we can skip all positions corresponding with a collision with the same message, and only $O(n)$ offsets must be considered. Hence, First Fit can be implemented in time $O(n^2)$.

248

## 3.2 Meta-Offset

249

250

251

252

The method of this section is described in [11] and it achieves the same bound on the load using a different method. It is recalled here as an introduction to the algorithms of the next section. The idea is to restrict the possible offsets at which messages can be scheduled. It seems counter-intuitive since it decreases artificially the number of available offsets to
schedule new messages. However, it allows reducing the number of forbidden offsets for unscheduled messages. A **meta-offset** is an offset of value $i\tau$, with $i$ an integer from 0 to $\lceil P/\tau \rceil - 1$. We call **Meta Offset** the greedy algorithm which works as **First Fit**, but consider only meta-offsets when scheduling messages.

To study Meta Offset, we introduce a variant of FO($A$) restricted to meta-offsets. Let $A$ be a partial assignment defined over $S$ and $i \notin S$, we let FMO($A$) be the maximum over $i \in [n]$ of $|\{j \in [[P/\tau]] | A[i \to j\tau] \text{ has a collision}\}|$. By definition, two messages with a different meta-offset cannot collide in the first period. Hence, FMO($A$) can be bounded by $3|S|$ and we obtain the following theorem.

**Theorem 2 (Proposition 3 of [11]).** *Meta Offset solves PMA positively on instances of load at most 1/3.*

The complexity of Meta Offset is in $O(n^2)$, since for each of the $n$ messages at most $3n$ meta-offsets must be checked in constant time.

## 3.3 Compact Pairs

We present in this section a family of greedy algorithms which solve PMA positively for larger loads. We combine the good properties of the two previous algorithms: the compactness of the assignments produced by First Fit and the absence of collision in the first period of Meta Offset. The idea is to schedule several messages at once, using meta-offsets, to maximize the compactness of the obtained solution. We describe an algorithm that schedules pairs of messages, which is then extended to any tuple of messages.

For clarity of exposition, we assume from now on that the period $P$ is a multiple of $\tau$: we let $P = m\tau$. We show in Sec. 5 that this hypothesis can be relaxed to the price of a very small increase of the load.

When all delays are multiple of $P$, Meta Offset schedules the messages compactly and solves PMA for a load of $1/2$. Hence, we are interested in the remainder modulo $\tau$ of the delays. Let $d_i = d'_i\tau + r_i$ be the Euclidean division of $d_i$ by $\tau$. We now assume that messages are sorted by increasing $r_i$.

The gap between message $i$ and message $j$, is defined as $g = d'_i + 1 - d'_j \bmod m$. A **Compact pair** is a pair of messages $(i, j)$, with $i < j$ and their gap is different from 0. A compact pair $(i, j)$ is scheduled using meta-offsets such that $A(i) + (d'_i + 1)\tau = A(j) + d'_j\tau$, i.e. the beginning of $j$ is less than $\tau$ unit of times after the end of $i$ in the second period, see Fig. 3. The gap is interpreted as the distance in meta-offsets between $i$ and $j$ in the first period, when they are scheduled as a compact pair.

<figure><img src="image_7.png" /><figcaption>**Figure 3** The compact pair $(0, 1)$ with $d'_0 = 2$ and $d'_1 = 0$</figcaption></figure>

**Lemma 3.** *Given three messages (1, 2, 3) in order of increasing delay modulo $\tau$, then either (1, 2), (1, 3) or (2, 3) is a compact pair.*

*Proof.* If the first two messages or the first and the third message form a compact pair, we are done. If not, then by definition $d'_1 = 1 + d'_2 = 1 + d'_3$. Hence, messages 2 and 3 have the same delay divided by $\tau$ and form a compact pair of gap 1.
XX:8 Scheduling Periodic Messages on a Shared Link without Buffering

<figure><img src="image_8.png" /><figcaption>Figure 4 Positions forbidden by a scheduled compact pair (in blue) when scheduling another compact pair (in red) with larger $r_i$'s</figcaption></figure>

Let **Compact Pairs** be the following greedy algorithm: A sequence of at least $n/3$ compact pairs is built by considering triples of messages in order of increasing $r_i$, and applying Lemma 3 to each triple. Compact pairs are scheduled in the order they have been built using meta-offsets. If at some point all compact pairs are scheduled or the current one cannot be scheduled, the remaining messages are scheduled as in **Meta Offset**. The analysis of **Compact Pairs** relies on the evaluation of the number of forbidden meta-offsets. In the first phase of **Compact Pairs**, we evaluate the number of forbidden offsets when scheduling any compact pair, that we denote by $FMO_2(A)$. In the second phase, we need to evaluate $FMO(A)$. When scheduling a message in the second phase, a scheduled compact pair only forbids three meta-offsets in the second period, while two messages scheduled independently forbid four meta-offsets, which explains the improvement from **Compact Pairs**. We state the previous facts as Lemma 4, see an illustration in Fig. 4.

**Lemma 4.** Let $C_1$ be compact pair. Let $C_2$ be a compact pair and $i$ a single message which are scheduled by **Compact Pairs** after $C_1$. Then, because of collisions in the second period, $C_1$ forbids at most four meta-offsets to $C_2$ and three meta-offsets to $i$.

**Theorem 5.** **Compact Pairs** solves PMA positively on instances of load at most 3/8.

**Proof.** Let $n$ be the number of messages to schedule. In the first phase of **Compact Pairs**, $n_2$ compact pairs are scheduled to build a partial assignment $A$. Let us first assume that there are more compact pairs built using the method of Lemma 3 than compact pairs which are scheduled. When scheduling a new compact pair, the position of the first $n_2$ compact pairs on the first period forbid $4n_2$ offsets for a compact pair. In the second period, we use Lemma 4 to bound the number of forbidden offsets by $4n_2$. Hence, $FMO_2(A) \le 8n_2$. By definition of $FMO_2(A)$, there are offsets to schedule compact pairs while $FMO_2(A) < m$. Thus, $A$ can be extended if $8n_2 < m$. Since exactly $n_2$ pairs are scheduled, $n_2 \ge m/8$.

Let $n_1$ be the number of messages remaining to be scheduled by **Compact Pairs** using meta-offsets, after the $n_2$ compact pairs have been scheduled. By Lemma 4, a compact pair forbids 3 meta-offsets in the second period. It also forbids 2 meta-offsets in the first period. The $n_1$ messages scheduled as in **Meta Offset** forbids 3 meta-offsets each, as explained in the previous section. Therefore, we have $FMO(A) \le 5n_2 + 3n_1$.

Assume now that **Compact Pairs** fails to schedule the $n_1$ messages of the second phase. Since **Compact Pairs** can schedule new messages when $FMO(A) < m$, we obtain $5n_2 + 3(n_1 - 1) \ge m$. We have already proved $n_2 \ge m/8$, by summing both inequations, we obtain

$$6n_2 + 3n_1 > 9m/8 + 2.$$

By definition $n = 2n_2 + n_1$, hence

$$2n > 9m/8.$$

Therefore, when **Compact Pairs** fails, $n > (3/8)m$, i.e. the load is larger than 3/8.
Let us now assume that the first phase stops because the algorithm runs out of compact pairs. They are built using Lemma 3, for each triple of messages at least a compact pair is produced. Hence, we obtain at least $n/3$ compact pairs, which are all scheduled. We have $n_2 > n/3$ and $n = 2n_2 + n_1$, which implies that $n_1 + n_2 \le 2n/3$. Assume now that **Compact Pairs** fails to schedule all messages, then $5n_2 + 3n_1 > m$. By substitution in the previous inequation, we have $8n/3 > m$, i.e the load is larger than 8/3, which proves the theorem. ◀

## 3.4 Compact Tuples

Algorithm **Compact Pairs** can be improved by forming compact tuples instead of compact pairs. Recall that a delay $d_i$ is equal to $d'_i\tau + r_i$, we call $d'_i$ the **meta-delay**. The algorithm we describe relies only on meta-delays and the fact that values $r_i$ are increasing.

**Definition 6.** Let $i_1 < \dots < i_k$ be a sequence of messages with $i_1, \dots, i_k$ increasing. It is a compact $k$-tuple, if there is a valid partial assignment of these messages, such that messages in the second period are in order $i_1, \dots, i_k$ and for all $l$, $A(i_l) + (d'_{i_l+1})\tau \mod P = A(i_{l+1}) + d'_{i_{l+1}}\tau \mod P$.

Scheduling a compact $k$-tuple is choosing a meta-offset for the first message of the tuple, the offsets of the other messages are also fixed by this choice. The algorithm **Compact k-tuples** works by scheduling compact $k$-tuples using meta-offsets while possible, then scheduling compact $(k-1)$-tuples and so on until $k=1$.

**Lemma 7.** Given $k + k(k-1)(2k-1)/6$ messages, $k$ of them always form a compact $k$-tuple and we can find them in time $O(k^3)$.

**Proof.** We assume the messages are sorted by increasing $r_i$s. We prove the lemma by induction on $k$. Lemma 3 already proves the lemma for $k=2$. Now assume that we have found $C$ a compact $(k-1)$-tuple in the first $k-1+(k-1)(k-2)(2k-3)/6$ messages. Consider the next $(k-1)^2+1$ messages: if $k$ of them have the same meta-delay, then they form a compact $k$-tuple and we are done. Otherwise, there are at least $k$ different meta-delays in those $(k-1)^2+1$ messages. Each of the $k-1$ elements of $C$ forbids one possible meta-delay for an additional $k$-th message in $C$. By pigeonhole principle, one of the $k$ messages with distinct meta-delays can be used to extend $C$. We can thus build a compact $k$-tuple from at most $(k-1)+(k-1)(k-2)(2k-3)/6+(k-1)^2+1$ messages, that is $k+k(k-1)(2k-1)/6$ messages which proves the induction. ◀

**Theorem 8.** **Compact $8$-tuples** always solves PMA positively on instances of load at most $2/5$ and with more than $205$ messages.

**Proof.** We use the following fact, which generalizes Lemma 4: A $k$-tuples forbids $k+j+1$ offsets in the second period when scheduling a $j$-tuple. It enables us to compute a lower bound on the number of scheduled $i$-tuples for $i$ equal $k$ down to 1 by bounding $FMO_i(A)$, the number of forbidden meta-offsets when scheduling compact $i$-tuples in the algorithm. If we denote by $n_i$ the number of compact $i$-tuples scheduled by the algorithm, we have the following equation:

$$FMO_i(A) \le \sum_{j=i}^{k} n_j (j+1) * (i+1).$$

The equation for $n_1$ is slightly better:

$$FMO(A) \le \sum_{j=1}^{k} n_j (2j + 1).$$
XX:10 Scheduling Periodic Messages on a Shared Link without Buffering

A bound on $n_i$ can be computed, using the fact that $A$ can be extended while $FMO_i(A) < m$ and assuming we know the value of the $n_j$'s with $j > i$. Lemma 7 ensures that enough compact $i$-tuples can be built, when $n+n_i - \sum_{j \le i \le 8} j * n_j$ is larger than $i + \frac{(i-1)(2i-1)}{6}$. A numerical computation of the $n_i$'s shows that Compact 8-tuples always finds an assignment when the load is at most 2/5 and for $n \ge 205$. ◄

The code computing the $n_i$'s can be found on one author's website<fnref n="2" />. Th. 8 is obtained for $k=8$. Taking arbitrary large $k$ and using refined bounds on $FMO_i(A)$ is not enough to get an algorithm working for a load of 41/100 (and it only works from larger $n$). To produce a compact 8-tuples by Lemma 7, there must be 148 messages, hence the restriction of $n \ge 205$ to be able to produce enough compact 8-tuples. The bound of Lemma 7 can be refined, by using better algorithms to construct $k$-tuples, e.g. a simple case analysis shows that, in the worst case, 7 messages are necessary to construct a compact 3-tuple and not 8. However, the restriction on $n$ is not relevant in practice, since on random instances, the probability that $k$ messages do not form a compact $k$-tuples is low, and thus we can build the $k$-tuples greedily. For instance, with $P = 50\tau$ and thus $n \le 50$, there is a probability larger than 55% that 8 random messages form a compact 8-tuples, 86% for 9 messages and 96% for 10 messages.

4 Messages of Size One

We consider the special case $\tau = 1$. While $\tau > 1$ for a C-RAN application, other applications such as sensors communicating with a base station through a low bandwidth channel may be modeled with $\tau = 1$. Moreover, in Sec. 5.2, we prove that any instance with $\tau > 1$ can be transformed into an instance with $\tau = 1$, by increasing the load or the delays.

When $\tau = 1$ and the load is less than $1/2$, any greedy algorithm solves PMA positively since $FO(A) \le (4\tau - 2)|S| = 2|S|$ where $S$ is the set of scheduled messages. In this section, we give a polynomial time algorithm that always finds a valid assignment when the load is less than $1/2 + (\sqrt{5}/2 - 1)$.

4.1 Deterministic Algorithm

We define the notion of potential of a partial assignment, which indirectly measures how many offsets are left available by this assignment for all messages of the instance. To go above 1/2 of load, messages are scheduled greedily, and when the unscheduled messages have no available offset, the potential is optimized by local operations on the partial assignment, to get more available offsets.

► **Definition 9.** Let $i$ be a message of delay $d$ and let $A$ be a partial assignment. The potential of $i$ for $A$, denoted by $pot_{msg}(i)$, is the number of integers $p \in [P]$ such that $p$ is used in the first period and $p+d \mod P$ is used in the second period.

The computation of the potential of a message of delay 3, is illustrated in Fig. 5. The potential of a message counts how many forbidden offsets are avoided by the message given a partial assignment $A$. Indeed, when $p$ is used in the first period and $p+d \mod P$ is used in the second period, then the same offset is forbidden twice for a message of delay $d$. Hence, the potential of a message is related to the number of possible offsets as stated in the following lemma.

<footnote n="2">² https://yann-strozecki.github.io/textesmaths.html</footnote>
Delay of the message $d_i = 3$ $\tau = 1$

<figure><img src="image_9.png" /><figcaption>■ **Figure 5** A partial assignment A with scheduled messages in gray. Message i of delay 3 has potential 2 because of positions 0 and 3 in the first period.</figcaption></figure>

<table><tr><td>Message <i>i</i></td><td>0</td><td>1</td><td>2</td><td>3</td></tr><tr><td>Delays (<i>d</i><sub><i>i</i></sub>)</td><td>2</td><td>3</td><td>0</td><td>1</td></tr></table>

<figure><img src="image_10.png" /><figcaption>■ **Figure 6** A partial assignment A with scheduled messages in gray. Position $p = 2$ is of potential 2 because there is a collision in $A[1 \to p]$ and $A[3 \to p]$.</figcaption></figure>

► **Lemma 10.** Given a partial assignment A of size $s$, and a message $i$, then the set $\{o | A[i \to o] \text{ has no collision}\}$ is of size $P - 2s + \text{pot}_{\text{msg}}(i)$.

**Proof.** Each of the $s$ messages scheduled by A forbids at most two offsets for $i$, that is $2s$ in total. In these $2s$ forbidden offsets, exactly $\text{pot}_{\text{msg}}(i)$ are counted twice by definition of the potential of the message $i$. Since there are $P$ possible values for the offset $o$ of the message $i$, there are $P - 2s + \text{pot}_{\text{msg}}(i)$ of these values which do not create a collision when scheduling $i$. ◀

We define a global measure of the quality of a partial assignment. Given a partial assignment A, the sum of potentials of all messages in the instance is called **the potential** of the assignment A and is denoted by $\text{Pot}(A)$.

► **Definition 11.** Let $p \in [P]$ be a position in the first period, and let A be a valid partial assignment. The potential of $p$, denoted by $\text{pot}_{\text{pos}}(p)$, is the number of messages $i \in [n]$, such that there is a collision in $A[i \to p]$.

The potential of a position is illustrated in Fig. 6. Instead of decomposing the global potential as a sum over messages, it can be interpreted as a sum over positions, as stated in the next lemma.

► **Lemma 12.** The sum of potentials of all positions used in the first period by messages scheduled by A is equal to $\text{Pot}(A)$.

**Proof.** Let us denote by $1(o, d)$ the indicator function which is equal to one if and only if for A, $o$ is used in the first period and $o + d$ is used in the second period.

By definition of potential of an assignment,

$$ \text{Pot}(A) = \sum_{i \in [n]} \text{pot}_{\text{mes}}(i). $$

By definition of the potential of a message,

$$ \text{Pot}(A) = \sum_{i \in [n]} \sum_{o \in [P]} 1(o, d_i). $$
XX:12 Scheduling Periodic Messages on a Shared Link without Buffering

By exchanging the summation order, we obtain

$$Pot(A) = \sum_{o \in [P]} \sum_{i \in [n]} 1(o, d_i).$$

Let $O$ be the set of offsets used by $A$. When $o$ is not in $O$, it contributes nothing to the sum, thus

$$Pot(A) = \sum_{o \in O} \sum_{i \in [n]} 1(o, d_i).$$

Then, by definition of potential of a position we obtain

$$Pot(A) = \sum_{o \in O} pot_{pos}(o).$$

The sum of the potentials of all positions can easily be computed and only depends on the size of the partial assignment.

**Lemma 13.** *The sum of potentials of all positions of a partial assignment of size $k$ is $nk$.*

**Proof.** We want to compute $\sum_{o \in [P]} pot_{pos}(o)$ which is by definition

$$\sum_{o \in [P]} \sum_{i \in [n], o+d_i \text{ is used in the second period}} 1.$$

Remark that for one position $p$ used in the second period, and one message $i$, there is exactly one offset $o$ such that $p = o + d_i \mod P$. Hence, each used position of the second period contributes 1 for each message in the double sum, that is $n$ in total. Since $A$ is of size $k$, there are $k$ used positions and the sum is equal to $kn$.

As a consequence of this lemma, $Pot(A) \le nk$. Let us define a **Swap operation**, which guarantees to obtain at least half the maximal value of the potential. Let $A$ be some partial assignment of size $s$ and let $i$ be an unscheduled message. Assume that $i$ cannot be used to extend $A$. The Swap operation is the following: select a free position $p$ in the first period, remove the message which uses the position $p+d_i$ in the second period from $A$, and extend $A$ by $i$ with offset $p$. We denote by $Swap(i, p, A)$ the partial assignment obtained by this operation.

**Lemma 14.** *Let $A$ be some partial assignment of size $k$ and let $i$ be an unscheduled message. If $i$ cannot be used to extend $A$, then either $Pot(A) \ge kn/2$ or there is $p \in [P]$ such that $Pot(Swap(i, p, A)) > Pot(A)$.*

**Proof.** The positions in the first period can be partitioned into $P_u$ the positions used by some scheduled message and $P_f$ the free positions. Let $V_f$ be the sum of the potentials of the positions in $P_f$ and let $V_u$ be the sum of the potentials of the positions in $P_u$. By Lemma 13, since $P_f$ and $P_u$ partition the positions, we have $V_f + V_u = kn$. Moreover, by Lemma 12, $Pot(A) = V_u$, then $V_f + Pot(A) = kn$.

By hypothesis, $i$ cannot be scheduled, then, for all $p \in P_f$, $p+d_i$ is used in the second period. Let $F$ be the function which associates to $p \in P_f$ the position $A(j)$ such that there is $j$ a scheduled message which uses $p+d_i$ in the second period, that is $A(j) + d_j = p+d_i \mod P$. The function $F$ is an injection from $P_f$ to $P_u$. Remark that, in both $Swap(i, p, A)$ and $A$, the same positions are used in the second period. Hence, the potential of each position
remains the same after the swap. As a consequence, doing the operation *Swap(i, p, A)* adds

to *Pot(A)* the potential of the position *p* and removes the potential of the position *F(p)*.

442

443

Assume now, to prove our lemma, that for all $p$, $Pot(\text{Swap}(i, p, A)) \leq Pot(A)$. It implies that for all $p$, the potential of $p$ is smaller than the potential of $F(p)$. Since $F$ is an injection from $P_f$ to $P_u$, we have that $V_f \leq V_u = Pot(A)$. Since $V_f + Pot(A) = kn$, we have that $Pot(A) \geq kn/2$. ◀

444

445

446

447

Let us now describe the algorithm **Swap and Move**, which is based on the idea of optimizing the potential of a partial assignment by local modifications, to be able to extend it.

448

449

Algorithm **Swap and Move** schedules messages using **First Fit** while possible. Then, it applies the Swap operation while it increases the potential. When the potential cannot be improved by a Swap anymore, **Swap and Move** try to schedule a new message at each position. When scheduling the message at some position, it is in conflict with one or two already scheduled messages, which are moved to another offset if possible. If **Swap and Move** fails to schedule the message it stops, otherwise the whole procedure is repeated.

450

451

452

453

454

455

Algorithm **Swap and Move** is not greedy, since we allow to change the offset of a message, either to improve the potential or to free an offset for scheduling a new message. While computing the potential requires knowing all delays in advance, **Swap and Move** can be adapted to work online by considering the potential of a partial assignment to be the sum of the scheduled messages.

456

457

458

459

460

**► Theorem 15.** *Swap and Move* solves PMA positively, in time $O(n^3)$, for instances with $\tau = 1$ and load at most $(\sqrt{5}-1)/2 \approx 0.618$.

461

462

**Proof.** We determine for which value of the load **Swap and Move** always finds an assignment. We consider the situation when $n-1$ messages are scheduled by $A$ out of $n$ and **Swap and Move** tries to schedule the last one. The proof that the algorithm schedules the previous messages is the same. We let $n-1 = (1/2 + \varepsilon)P$ be the number of messages, hence the load we achieve is $1/2 + \varepsilon$.

463

464

465

466

467

Let $d$ be the delay of the last unscheduled message, w.l.o.g. we assume that $d=0$. Let $P_f$ be the set of $p \in [P]$ which are free in the first period. Let $P_u^1$ be the set of $p \in [P]$, such that $p$ is used in the first period but $p$ is free in the second period. Let $P_u^2$ be the set of $p \in [P]$, such that $p$ is used in the first period and $p$ is used in the second period.

468

469

470

471

Since there are $n-1$ messages scheduled by $A$, considering the positions used in the first period, we have $n-1 = |P_u^1| + |P_u^2|$. To prove a lower bound on the load, we assume that the last message cannot be scheduled greedily by **Swap and Move**. Hence, if $p \in P_f$, then $p$ is used in the second period. By considering the used positions in the second period, we have $n-1 = |P_u^2| + |P_f|$. Hence, because the three sets partition $[P]$, $|P_u^2| = 2(n-1) - P = 2\varepsilon P$ and $|P_u^1| = |P_f| = (1/2 - \varepsilon)P$.

472

473

474

475

476

477

Consider a position $p \in P_u^1$, then $p$ is used in the first period by some message $i$. If the offset of $i$ can be changed in $A$ to obtain a valid assignment, then **Swap and Move** does it and succeeds because the last message can now be scheduled at offset $p$. By Lemma 10, the number of offsets which can be used by some message $i$ is $P - 2(n-1) + \text{pot}_{\text{msg}}(i)$. Since the offset of $i$ cannot be changed, this number is zero and we have $\text{pot}_{\text{msg}}(i) = 2(n-1) - P = 2\varepsilon P$. For the same reason, a message $i$ with $(A(i) + d_i) \bmod P) \in P_f$ has the same potential.

478

479

480

481

482

483

Consider a position $p \in P_u^2$, then $p$ is used by a message $i$ in the first period and $p$ is used by a message $j$ in the second period. If both $i$ and $j$ can be scheduled elsewhere, then **Swap and Move** moves them and succeeds. By Lemma 10, both messages can be scheduled when one is of potential at least $2\varepsilon P + 1$ and the other at least $2\varepsilon P + 2$. Since a message is of

484

485

486

487
XX:14 Scheduling Periodic Messages on a Shared Link without Buffering

potential at most $n-1$, both messages can always be rescheduled when the sum of the two potentials is at least $2\epsilon P + n$. Hence, we may assume that their sum is less than $2\epsilon P + n$.

By definition, $Pot(A)$ is the sum of the potential of the messages, that we can write as

$$ Pot(A) = \sum_{\substack{i \in [n] \\ A(i) \in P_u^1}} pot_{msg}(i) + \sum_{\substack{i \in [n] \\ A(i) \in P_u^2}} pot_{msg}(i). $$

We may also divide the sum according to the positions in the second period,

$$ Pot(A) = \sum_{\substack{i \in [n] \\ A(i)+d_i \in P_f}} pot_{msg}(i) + \sum_{\substack{i \in [n] \\ A(i)+d_i \in P_u^2}} pot_{msg}(i). $$

By summing both equalities, using $|P_u^1| = |P_f| = (1/2 - \epsilon)P$ and $pot_{msg}(i) = 2\epsilon P$ for $A(i) \in P_u^1$ and $A(i) + d(i) \in P_f$, we obtain

$$ 2Pot(A) = 2(1/2 - \epsilon)P \times 2\epsilon P + \sum_{\substack{i \in [n] \\ A(i) \in P_u^2}} pot_{msg}(i) + \sum_{\substack{i \in [n] \\ A(i)+d_i \in P_u^2}} pot_{msg}(i). $$

We have proved that $pot_{msg}(i) + pot_{msg}(j) < 2\epsilon P + n$ when $A(i) \in P_u^2$ and $A(i) = (A(j) + d_j \mod P)$. Since $|P_u^2| = 2\epsilon P$, we have

$$ \sum_{\substack{i \in [n] \\ A(i) \in P_u^2}} pot_{msg}(i) + \sum_{\substack{i \in [n] \\ A(i)+d_i \in P_u^2}} pot_{msg}(i) < 2\epsilon P(2\epsilon P + n). $$

Using this inequality and simplifying the expression, we obtain

$$ Pot(A) < \epsilon P(P + n). $$

This bound is obtained when **Swap and Move** fails to schedule the last message. On the other hand, by Lemma 14, we know that $Pot(A) \ge n(n-1)/2$, hence **Swap and Move** must succeed when

$$ n(n-1)/2 \ge \epsilon P(P + n - 1). $$

By expanding and simplifying the previous inequation, we obtain a second-degree inequation in $\epsilon$, $1/4 - 2\epsilon - \epsilon^2 \ge 0$. Solving this inequation yields $\epsilon \le \sqrt{5}/2 - 1$.

Let us prove that **Swap and Move** is in polynomial time. All Swap operations strictly increase the potential. Moreover, when one or two messages are moved, the potential may decrease but a message is added to the partial assignment. The potential is bounded by $O(n^2)$ and the move operations all together can only remove $O(n^2)$ to the potential, hence there are at most $O(n^2)$ Swap operations during **Swap and Move**. A Swap operation can be performed in time $O(n)$, since, for a given message, all free offsets must be tested and the potential is evaluated in time $O(1)$ (by maintaining the potential of each position). This proves that Swap and Move is in $O(n^3)$. ◀

Consider a partial assignment of size $n-1 = (1/2 + \epsilon)P$, and a last message of delay $d$ to schedule. We have seen that if a scheduled message cannot be rescheduled, its potential is equal to $2\epsilon P$, it is larger otherwise. Hence, the best possible upper bound on the potential of the assignment is $2\epsilon Pn$. On the other hand, Lemma 14 guarantees that the potential of an assignment is at least $n(n-1)/2$. Therefore, improving the analysis at best yields $\epsilon = 1/6$ and load $2/3$.
To go further, the analysis in Lemma 14 may be improved: $2\epsilon P$ positions in $P_u$ are not taken into account in the proof. When the delays are distinct we can indeed improve the result. However, there is an instance (found by a bruteforce search) with 8 messages and $P = 10$ for which there is no assignment, hence the largest $\lambda$ for which PMA has always a solution is strictly less than $8/10$.

## 4.2 Randomized Algorithm for Random Instances

We would like to better understand the behavior of greedy algorithms on instances drawn uniformly at random. To this aim, we analyze the algorithm Greedy Uniform, defined as follows: for each message in the order of the input, choose one of the offsets, which does not create a collision with the current partial assignment, uniformly at random.

We analyze Greedy Uniform over random instances: all messages have their delays drawn independently and uniformly in $[P]$. We compute the probability of success of Greedy Uniform over all random choices by the algorithm and all possible instances. It turns out that this probability, for a fixed load strictly less than one, goes to one when $P$ grows. To simplify the analysis of Greedy Uniform, we introduce the notion of trace of an assignment.

**Definition 16.** Let $A$ be a partial assignment of size $k$, its trace is a pair of subsets $(S_1, S_2)$ of $[P]$ of size $k$ such that $S_1$ are the time used by $A$ in the first period and $S_2$ the time used by $A$ in the second period.

We now prove that traces are produced uniformly by Greedy Uniform.

**Theorem 17.** The distribution of traces of assignments produced by Greedy Uniform when it succeeds, from instances drawn uniformly at random, is also uniform.

**Proof.** The proof is by induction on $n$, the number of messages. It is clear for $n = 1$, since the delay of the first message is uniformly drawn and all offsets can be used. Assume now the theorem true for some $n > 1$. By induction hypothesis, Greedy Uniform has produced uniform traces from the first $n$ messages. Hence, we should prove that, if we draw the delay of the $n + 1^{th}$ message randomly, extending the trace by a random possible offset produces a random distribution on the traces of size $n + 1$.

If we draw an offset uniformly at random (among all $P$ offsets) and then extend the trace by scheduling the last message at this offset or fail, the distribution over the traces of size $n + 1$ is the same as what produces Greedy Uniform. Indeed, all offsets which can be used to extend the trace have the same probability to be drawn. Since all delays are drawn independently, we can assume that, given a trace, we first draw an offset uniformly, then draw uniformly the delay of the added message and add it to the trace if it is possible. This proves that all extensions of a given trace are equiprobable. Thus, all traces of size $n + 1$ are equiprobable, since they each can be formed from $(n + 1)^2$ traces of size $n$ by removing one used time from the first and second period. This proves the induction and the theorem. ◀

Since Greedy Uniform can be seen as a simple random process on traces by Th. 17, it is easy to analyze its probability of success.

**Theorem 18.** The probability over all instances with $n$ messages and period $P$ that Greedy Uniform solves PMA positively is $$ \prod_{i>P/2}^{n-1} \left(1 - \frac{\binom{n}{2i-P}}{\binom{P}{i}}\right) $$

**Proof.** We evaluate $Pr(P,n)$ the probability that Greedy Uniform fails at the $n^{th}$ step assuming it has not failed before. It is independent of the delay of the $n^{th}$ message. Indeed,
XX:16 Scheduling Periodic Messages on a Shared Link without Buffering

the operation which adds one to all times used in the second period is a bijection on the set of traces of size $n-1$. It is equivalent to removing one to the delay of the $n^{th}$ message. We can thus assume that the delay is zero.

Let $S_1$ be the set of times used in the first period by the $n-1$ first messages and $S_2$ the set of times used in the second period. We can assume that $S_1$ is fixed, since all subsets of the first period are equiprobable and because $S_2$ is independent of $S_1$ by Th. 17. There is no possible offset for the $n^{th}$ message, if and only if $S_1 \cup S_2 = [P]$. It means that $S_2$ has been drawn such that it contains $[P] \setminus S_1$. By Th.17, $S_2$ is uniformly distributed over all sets of size $n-1$. Hence, the probability that $[P] \setminus S_1 \subseteq S_2$ is the probability to draw a set of size $n-1$ which contains $P-n+1$ fixed elements. This proves $\text{Pr}(P, n) = \frac{\binom{2(n-1)-P}{n}}{\binom{P}{n-1}}$.

From the previous expression, we can derive the probability of success of Greedy Uniform by a simple product of the probabilities of success $(1 - \text{Pr}(P, i))$ at step $i$, for $i \le n$. The product is over $P/2 < i \le n$, because for $i \le P/2$, the probability of success of Greedy Uniform is one. $\quad \blacksquare$

If we fix the load $\lambda = n/P$, we can bound $\text{Pr}(P, n)$ using Stirling formula. The computation yields a constant $C_{\lambda}$ such that $\text{Pr}(P, n) \le C_{\lambda} \left( \frac{\lambda^{2\lambda}}{(2\lambda-1)^{2\lambda-1}} \right)^P$. As an illustration, with $\lambda = 2/3$, $\text{Pr}(P, n) < 1, 16 \times (0, 84)^P$.

We let $f(\lambda) = \frac{\lambda^{2\lambda}}{(2\lambda-1)^{2\lambda-1}}$. The derivative of $f$ is strictly positive for $1/2 < \lambda < 1$ and $f(1) = 1$, hence $f(\lambda) < 1$ when $\lambda < 1$. By a union bound, the probability that Greedy Uniform fails is bounded by $C_{\lambda}\lambda P f(\lambda)^P$. For any fixed $\lambda$, the previous expression goes to zero, exponentially quickly, when $P$ goes to infinity. It explains why Greedy Uniform is good in practice for large $P$, even when the load is large. For instance, with $n = 8$ and $P = 12$ (thus $\lambda = 2/3$), the probability of success of Greedy Uniform is larger than 0,92 (see Sec. 6.2 for more values).

## 5 Generalizations

In this section, we prove that several hypotheses made in the previous sections can be relaxed and that the problem PMA captures periodic message scheduling in more complex networks.

### 5.1 Period Multiple of the Message Size

We prove that we can assume that $P$ is a multiple of $\tau$ in Lemma 19. This hypothesis was done to make the analysis of algorithms based on meta-offsets simpler and tighter.

**Lemma 19.** Let $I$ be an instance of PMA with $n$ messages of size $\tau$, period $P$ and $m = \lfloor P/\tau \rfloor$. There is an integer $\tau'$ and an instance $J$ with $n$ messages of size $\tau'$ and period $P' = m\tau'$ such that any assignment of $J$ can be transformed into an assignment of $I$ in polynomial time.

**Proof.** Fig. 7 illustrates the reductions we define in this proof on a small instance. Let $P = m\tau + r$ with $r < \tau$. We define the instance $I'$ as follows: $P' = mP$, $d_i' = md_i$ and $\tau' = m\tau + r$. With this choice, we have $P' = m(m\tau + r) = m\tau'$. Consider an assignment $A'$ of the instance $I'$. We let $\tau'' = m\tau$, then $A'$ is also an assignment for $I'' = (P', \tau''$, $(d_0', \dots, d_{n-1}')$). Indeed, the size of each message, thus the intervals of time used in the first and second period begin at the same position but are shorter, which cannot create collisions.
We consider the assignment $A'$ seen as an assignment of $I''$ and denote it by $A'_0$. We describe a compactification procedure which produces a sequence of assignments from $A'_0$, such that, in the last assignment, any message has a position multiple of $m$ in the first and second period. See Th.4 of [11] for a similar method, used to design an exponential time algorithm to solve PMA.

W.l.o.g., we assume that message 0 is at offset zero in $A'_0$. The first time message 0 uses in the second period is a multiple of $m$ since its delay is by construction a multiple of $m$. Consider the following shift of $A'_0$: $A'_1(0) = 0$ and for $i > 0$, $A'_1(i) = A'_0(i) - s$. We let $s$ be a non negative integer such that $A'_0$ shifted by $s$ is a valid assignment, while $A'_0$ shifted by $s+1$ has a collision involving message 0. By construction of $A'_1$, because of the choice of $s$, there is a message $j$ which is next to message 0 in the first or second period. It implies that either $A'_1(j)$ or $A'_1(j) + d_j \bmod P'$ is a multiple of $m$ and since $d_j$ is a multiple of $m$, then both $A'_1(j)$ and $A'_1(j) + d_j \bmod P'$ are multiples of $m$. The procedure is repeated, we obtain $A_{i+1}$ from $A_i$ by fixing $i$ messages of $A_i$ with an offset multiple of $m$ and shifting the other messages as previously.

By construction, $A'_n$ is a valid assignment of $I''$, and all positions of messages in the first and second period are multiples of $m$. Finally, we let $A$ be the assignment of $I$ defined as, for all $i \in [n]$, $A(i) = A'_n(i)/m$. $\quad$

Notice that, the transformation of Lemma 19 does not give a bijection between assignments of both instances but only an injection, which is enough for our purpose. We obtain an instance with a period $P' = m\tau'$, which is slightly smaller than the original period $P$. The load increases from $\lambda = n\tau/P$ to at most $\lambda(1 + 1/m)$: the difference is less than $1/m < 1/n$, thus very small for most instances. If we drop the hypothesis that $P = m\tau$, the theorems of Sec. 3 can be restated as proving the existence of a valid assignment for a load at most $\lambda - o(1)$, where $o(1)$ goes to 0 when $n$ grows.

## 5.2 From Large to Small Messages

In this section, we explain how we can trade load or buffering in the network to reduce the size of messages up to $\tau = 1$. This further justifies the interest of Sec. 4, where specific algorithms for $\tau = 1$ are given.

### Doubling the Load

We describe here a reduction from an instance of PMA to another one with the same period and the same number of messages but the size of a message is doubled. This instance is equivalent to an instance with $\tau = 1$, by dividing everything by the message size. Thus, we can always assume that $\tau = 1$, if we are willing to double the load.

**Theorem 20.** Let $I$ be an instance of PMA with $n$ messages and load $\lambda$. There is an instance $J$ with $n$ messages of size $1$ and load $2\lambda$ such that an assignment of $J$ can be transformed into an assignment of $I$ in polynomial time.

*Proof.* From $I = (P, \tau, (d_0, \dots, d_{n-1}))$, we build $I' = (P, 2\tau, (d'_0, \dots, d'_{n-1}))$, where $d'_i = d_i - (d_i \bmod 2\tau)$. The instance $I'$ has a load twice as large as $I$. On the other hand, all its delays are multiples of $2\tau$ hence solving PMA on $I'$ is equivalent to solving it on $I'' = (P/2\tau, 1, (d_0/2\tau, \dots, d_{n-1}/2\tau))$, as already explained in the proof of Lemma 19.

Let us prove that an assignment $A'$ of $I'$ can be transformed into an assignment $A$ of $I$. Consider the message $i$ with offset $A'(i)$, it uses all times between $A'(i)$ and $A'(i) + 2\tau - 1$ in the first period and all times between $A'(i) + d_i - (d_i \bmod 2\tau)$ to $A'(i) + 2\tau - 1 + d_i - (d_i$
XX:18 Scheduling Periodic Messages on a Shared Link without Buffering

<figure><img src="image_11.png" /><figcaption>Figure 7 Transformation of $A'$ assignment of $I'$ into $A$ assignment of $I$</figcaption></figure>

mod $2\tau$) in the second period. If $d_i \mod 2\tau < \tau$, we set $A(i) = A'(i)$, and the message $i$ of $I$ is scheduled “inside” the message $i$ of $I'$, see Fig. 8. If $\tau \le d_i \mod 2\tau < 2\tau$, then we set $A(i) = A'(i) - \tau$. There is no collision in the assignment $A$, since all messages in the second period use times which are used by the same message in $A'$. In the first period, the messages scheduled by $A$ use either the first half of the same message in $A'$ or the position $\tau$ before, which is either free in $A'$ or the second half of the times used by another message in $A'$ and thus not used in $A$.

<figure><img src="image_12.png" /><figcaption>Figure 8 Building assignment $A$ of $I$ from assignment $A'$ of $I'$ with messages twice larger</figcaption></figure>

Remark that combining Greedy Uniform and Th. 20 allows solving PMA on random instances, with probability one when the number of messages goes to infinity and the load is strictly less than 1/2. This is why we have not presented nor analyzed an algorithm designed for arbitrary $\tau$ on random instances, since any greedy algorithm, relying on minimizing $FO(A)$, cannot guarantee anything for load larger than 1/2. However, in Sec. 6.1, we present Compact Fit, a simple greedy algorithm that exhibits good performance on random instances.
Trade-off between Latency and Message Size

The problem PMA is a simplified version of the practical problem we address, allowing a single degree of freedom for each message: its offset. We may relax it slightly to be more similar to what is studied in [10]: we allow buffering a message *i* during a time *b* between the two contention points, which corresponds here to changing *d*<sub>*i*</sub> into *d*<sub>*i*</sub> + *b*. The quality of the solutions obtained for such a modified instance of PMA is worse since the buffering adds latency to the messages. We now describe how we can make a trade-off between the added latency and the size of the messages, knowing that smaller messages helps to schedule instances with higher load.

The idea is to buffer all messages so that their $d_i$ have the same remainder modulo $\tau$. It costs at most $\tau-1$ of buffering, which is not so good, since algorithms optimizing the latency do better on random instances, see [10]. However, it is much better than buffering for a time $P$, the only value for which we are guaranteed to find an assignment, whatever the instance. When all delays are changed so that $d_i$ is a multiple of $\tau$, we have an easy reduction to the case of $\tau=1$, by dividing all values by $\tau$, as explained in the proof of Lemma. 19.

We can do the same kind of transformation by buffering all messages, so that $d_i$ is a multiple of $\tau/k$. The cost in terms of latency is then at most $\tau/k - 1$ but the reduction yields messages of size $k$. For small size of messages, it is easy to get better algorithm for PMA, in particular for $\tau = 1$ as we have shown in Sec. 4. Here, we show how to adapt *Compact Pairs* to the case of $\tau = 2$, to get an algorithm working with higher load.

**Theorem 21.** *Compact Pairs on instances with $\tau = 2$ always solves PMA positively on instances of load at most 4/9.*

**Proof.** We assume w.l.o.g that there are less message with even $d_i$ than odd $d_i$. We schedule compact pairs of messages with even $d_i$, then we schedule single message with odd $d_i$. The worst case is when there is the same number of the two types of messages. In the first phase, if we schedule $n/2$ messages, the number of forbidden offsets is $(2 + 3/2)n/2 = 7n/4$. In the second phase, if we schedule $n/2$ additional messages, the number of forbidden offsets is bounded by $(1 + 3/2)n/2 + (1 + 1)n/2 = 9n/4$. Hence, both conditions are satisfied and we can always schedule messages when $n \le (4/9)m$. ◀

We may want to add less latency to the message using the longest route. A simple solution is the following: choose the message with the longest route as the reference remainder by subtracting its remainder from every delay. As a consequence, this message needs zero buffering. However, the message with the second-longest route may have a remainder of $\tau - 1$, thus the worst case increase of total latency is $\tau - 1$.

An alternative would be to minimize the average latency rather than the worst latency. We prove that we can do the transformation yielding $\tau = 1$ while optimizing the average latency. The only degree of freedom in the presented reduction is the choice of the reference remainder since all other delays are then modified to have the same remainder. Let us define the total latency for a choice $t$ of reference time, denoted by $L(t)$, as the sum of buffering times used for the messages when $t$ has been removed from their delay. If we sum $L(t)$, from $t=0$ to $\tau-1$, the contribution of each message is $\sum_{i=0}^{\tau-1} i$. Since there are $n$ messages, the sum of $L(t)$ for all $t$ is $n\tau(\tau-1)/2$. There is at least one term of the sum less than its average, hence there is a $t_0$ such that $L(t_0) \le n(\tau-1)/2$. Hence, the average delay for a message, with $t_0$ as reference is less than $(\tau-1)/2$.
<figure><img src="image_13.png" /><figcaption>Figure 9 Left, a C-RAN network with a routing not coherent, and right a C-RAN network with coherent routing. The edges with multiple colors represent a single physical link used by several messages.</figcaption></figure>

## 5.3 Coherent Routing

In this section, we explain how algorithms solving PMA may be used on more complex networks with more than two contention points. We consider networks with **coherent routing**, a common property of telecommunication networks (see e.g. [22]). Each message follows a fixed route from an antenna to the data center, and the coherent routing property implies that two routes share either nothing or a single path (i.e. a sequence of contiguous links) in the network. See Fig. 9 for a network with and without coherent routing.

The problem PMA can be defined over any network: the problem is to find an assignment (an offset for each message) such that there is no collision in the network. The problem PMA (under the name PAZL) is proven to be NP-hard in [11] and the instances used for the reduction have a coherent routing.

When the routing is coherent, for each pair of messages, there is either no common contention point or a single contention point which is the beginning of their common path. If there is no collision at this contention point, there is no collision between these two messages further in the network. In our model, the routing is coherent from the antennas to the data centers, and then it is coherent from the data centers to the antenna. Hence, the collision between two messages can be characterized by their two contentions points (on the way forward and on the way back) and the delay between these two points.

We now prove that we can transform a network with coherent routing into a network with a single shared link such that an assignment of the latter is also an assignment of the former. Therefore, the algorithms proposed in this article for the single shared link case can be transferred to the coherent routing case.

The transformation is the following: let us consider two contention points $c_1$ and $c_2$ in the network, such that there is no contention point before $c_1$ nor between $c_1$ and $c_2$. All messages going through $c_2$ but not $c_1$ are routed through $c_1$ and then $c_2$. The contention point $c_2$ is then removed from the network, see Fig. 10. Let $l$ be the length of the link between $c_1$ and $c_2$. Let $S$ be the set of messages which have been rerouted from $c_2$ to $c_1$, and let $A$ be a valid assignment for the transformed network. Let $A'$ be the assignment defined by, for $i \notin S$, $A'(i) = A(i)$ and for $i \in S$, $A'(i) = A(i) + l \mod P$, then $A'$ is a valid assignment of the original network.

The coherent routing property ensures that applying the previous transformation to some network $N$ while possible, yields a network $N'$ with a single shared link. Hence, we can apply the algorithms presented in this article to find an assignment for $N'$, which can then be turned back into an assignment of $N$. Let us define the load of a general network as $n\tau/P$, then the load of $N'$ is the same as the load of $N$. It proves that there is always an assignment when the load of a network with coherent routing is less than $2/5$ or less than $1/2 + (\sqrt{5}/2 - 1)$ and $\tau = 1$.

Remark that there is a more precise way to define the load for general networks since the
<figure><img src="image_14.png" /><figcaption>■ **Figure 10** Transformation of a network *N* with coherent routing into *N*′ with one less contention point.</figcaption></figure>

load is not a global notion. Let $n_c$ be the number of messages going through the contention point $c$, then the load at $c$ is $n_c\tau/P$. The **local load** of the network is then defined as the maximum of the load of the contention points. It is always less than the load defined as $n\tau/P$ and it can be significantly so. It is easy to see that in a network with coherent routing, any greedy algorithm finds a solution when the local load is less than 1/4 since we can associate exactly two contention points to each message. However, the algorithms of this article do not seem to work for a local load larger than 1/4, since the bounds on FO or FMO do not hold anymore.

# 6 Experimental Results

In this section, we evaluate all presented algorithms and some others on random instances. For most algorithms, it would be extremely difficult to theoretically analyze the fraction of positive instances for a given load as we did for Greedy Uniform in Sec. 4. By doing these experiments, we get an idea of the difference between the bounds on the load we have proved for worst-case instances and random instances.

## 6.1 Experimental Results for Large Messages

In this section, the performance on random instances of the algorithms presented in Sec. 3 is experimentally characterized. The implementation in C of these algorithms can be found on one author's website<fnref n="3" />. We experiment with several periods and message sizes. For each set of parameters, we compute the success rate of each algorithm for all possible load by changing the number of messages. The success rate is measured on 10000 instances of PMA generated by drawing uniformly and independently the delays of each message in $[P]$.

We consider the following algorithms:

- First Fit

- Meta Offset

- Compact Pairs

- Compact Fit

- Greedy Uniform, the algorithm introduced and analyzed in Sec. 4, used for arbitrary $\tau$

- Exact Resolution which always find a valid assignment if there is one, using an algorithm from [11]

The only algorithm we have yet to describe is **Compact Fit**. The idea is, as for **Compact Pairs**, to combine the absence of collision on the first period of **Meta Offset** and the compactness of assignments given by **First Fit**. The messages are sorted in increasing

<footnote n="3">³ https://yann-strozecki.github.io/textesmaths.html</footnote>
XX:22 Scheduling Periodic Messages on a Shared Link without Buffering

<table><tr><td>Route (i)</td><td>0</td><td>1</td><td>2</td><td>3</td></tr><tr><td>Delay (d<sub>i</sub>)</td><td>2</td><td>0</td><td>1</td><td>7</td></tr><tr><td>d<sub>i</sub> mod τ</td><td>0</td><td>0</td><td>1</td><td>1</td></tr></table>

Step 1: First Period
0
Second Period
0

Step 2: 
0 
1
0 1

Step 3: 
0 
1 
2
0 1 2

Step 4: 
0 
3 
1 
2
0 1 2 3

<caption>Figure 11 An run of Compact Fit with $\tau = 2$ and $P = 10$, which creates two compact pairs</caption>

order of their delay modulo $\tau$, and each message is scheduled so that it extends an already scheduled compact tuple. In other words, it is scheduled using meta-offsets such that using one less as a meta-offset creates a collision on the second period. If it is not possible to schedule the message in that way, the first possible meta-offset is chosen. See Fig. 11 for an example run of Compact Fit. This algorithm is designed to work well on random instances. Indeed, it is not hard to evaluate the average size of the created compact tuples, and from that, to prove that Compact Fit works with high probability when the load is strictly less than 1/2.

On a regular 2017 laptop, all algorithms terminate in less than a second when solving 10000 instances with 100 messages except the exact resolution, whose complexity is exponential in the number of messages (but polynomial in the other parameters). Hence, the exact value of the success rate given by the exact resolution is only available in the experiment with at most 10 messages (the algorithm cannot compute a solution in less than an hour for twenty messages and a high load).
778

<figure><img src="image_15.png" /><figcaption>Figure 12 Success rates of all algorithms for increasing loads, $\tau = 1000$, $P = 100,000$</figcaption></figure>

<caption>Figure 13 Success rates of all algorithms for increasing loads, $\tau = 10$, $P = 1,000$</caption>

779

<figure><img src="image_16.png" /><figcaption>Figure 14 Success rates of all algorithms for increasing loads, $\tau = 1000$, $P = 10,000$</figcaption></figure>

<caption>Figure 15 Same parameters as in Fig. 12, delays uniformly drawn in $[\tau]$</caption>

780

781

782

783

For all sets of parameters, the algorithms have the same relative performances. Meta Offset and Greedy Uniform perform the worst and have almost equal success rates. Remark that they have a 100% success rate for load less than 1/2, while it is easy to build an instance of PMA of load 1/3 + $\epsilon$ which makes them fail.

784

785

786

787

788

789

First Fit performs better than Meta Offset on random instances, while we have proved that they always find a valid assignment for load at most 1/3 but not above. Compact Pairs, for which we have proved a better bound on the load also performs well in the experiments, always finding assignments for a load of 0.6. Compact Fit is similar in spirit to Compact Pairs but is designed to have a good success rate on random instances is indeed better than Compact Pairs, when there are enough messages.

790

791

792

793

794

795

796

As demonstrated by Fig. 12 and Fig. 13, the size of the messages has little impact on the success rate of the algorithms, when the number of messages and the load are kept the same. Comparing Fig. 14 and Fig. 12 shows that for more messages, the transition between 100% success rate to 0% success rate happens faster. Finally, the results of Exact Resolution in Fig. 14 show that the greedy algorithms are far from always finding a solution when it exists. Moreover, we have found an instance with load 0.8 with no assignment found by Exact Resolution, which gives an upper bound on the highest load for which PMA can always
XX:24 Scheduling Periodic Messages on a Shared Link without Buffering

be solved positively.

We also investigate the behavior of the algorithms when the delay of messages is drawn in $[\tau]$ in Fig. 15. The difference from the case of large delay is that **Compact Pairs** and **Compact Fit** are extremely efficient: they always find a solution for 99 messages. It is expected since all $d'_i$ are equal in these settings, and they will both build a 99-compact tuple and thus can only fail for load 1.

## 6.2 Experimental Results for Small Messages

In this section, the performance on random instances of the algorithms presented in Sec. 4 is experimentally characterized. The settings are as in Sec. 6.1, with $\tau = 1$. The evaluated algorithms are:

807 First Fit

808 Greedy Uniform

809 Greedy Potential, a greedy algorithm which leverages the notion of potential introduced for Swap. It schedules messages in arbitrary order, choosing the available offset which maximizes the potential of the unscheduled messages

811 Swap and Move

813 Exact Resolution

As in Sec. 6.1, the success rate on random instances is much better than the bound given by the worst-case analysis of the article. In the experiment presented in Fig. 16, all algorithms succeed on all instances when the load is less than 0.64. Greedy Uniform behaves exactly as proved in Th. 17, with a very small variance. The performance of Swap and Move and its simpler variant Greedy Potential, which optimizes the potential in a greedy way, is much better than First Fit or Greedy Uniform. Amazingly, Swap and Move always finds an assignment when the load is less than 0.95. Swap and Move is extremely close to Exact Resolution, but for $P = 10$ and load 0.9 or 1, it fails to find some valid assignments, as shown in Fig. 17.

<figure><img src="image_17.png" /><figcaption>Figure 16 Success rates of all algorithms for increasing loads, $\tau = 1$ and $P = 100$</figcaption></figure>

<caption>Figure 17 Success rates of all algorithms for increasing loads, $\tau = 1$ and $P = 10$</caption>

Finally, we evaluate the computation times of the algorithms to understand whether they scale to large instances. We present the computation times in Fig. 18 and we choose to consider instances of load 1, since they require the most computation time for a given
<figure><img src="image_18.png" /><figcaption>Figure 18 Computation time (logarithmic scale) function of the number of messages of all algorithms on 10000 instances of load 1</figcaption></figure>

size. The empirical complexity of an algorithm is evaluated by linear regression on the function which associates to $log(n)$, the log of the computation time of the algorithm on $n$ messages. First Fit, Greedy Uniform, and Swap and Move scale almost in the same way, with an empirical complexity slightly below $O(n^2)$, while Greedy Potential has an empirical complexity of $O(n^3)$. The empirical complexity corresponds to the worst-case complexity we have proved, except for Swap and Move which is in $O(n^3)$. There are two explanations: most of the messages are scheduled by the fast First Fit subroutine and most Swap operations improve the potential by more than 1, as we assume in the worst-case analysis.

# 7 Conclusion

In this article, we have proved that there is always a solution to PMA and that it can be found by a polynomial time greedy algorithm for arbitrary message size and load at most 0.4. For message of size 1 and load at most $\phi - 1$, a solution is found by a polynomial time local search algorithm. Moreover, the presented algorithms find valid assignments for random instances for much higher loads as we have shown empirically but also theoretically for a randomized greedy algorithm. As a consequence, we obtain communication schemes for C-RAN with *no buffering nor logical latency*, even for quite loaded fronthaul networks.

The first limitations of our model is the topology of the network. We have shown that an arbitrary topology can be transformed into a topology with two contention points. This transformation, while preserving the load, may map positive instances into negative instances. Hence, it would be interesting to design algorithms working directly on complex topologies, as we have done for the periodic assignment problem with buffering in [23].

The second limitation is that all messages are of the same size. To model networks with different kinds of traffic, or a production line with different tasks, we should relax this hypothesis. An interesting direction of research, would be to adapt algorithm *Swap and Move* to this setting. As a first step, we could already adapt *Swap and Move* to a single arbitrary $\tau$ and try to improve on the bound on latency obtained using *Compact 8-tuples*.

Finally, it remains to prove that PMA is NP-complete. If it is indeed the case, it would be interesting to understand whether exponential time algorithms may solve PMA positively for
larger loads.

References

1 Y. Bouguen, E. Hardouin, A. Maloberti, and F.-X. Wolff, *LTE et les réseaux 4G*. Editions Eyrolles, 2012.

2 L. Gavrilovska, V. Rakovic, and D. Denkovski, “From cloud ran to open ran.,” *Wirel. Pers. Commun.*, vol. 113, no. 3, pp. 1523–1539, 2020.

3 C. Mobile, “C-RAN: the road towards green RAN,” *White Paper, ver*, vol. 2, 2011.

4 A. Checko, H. L. Christiansen, Y. Yan, L. Scolari, G. Kardaras, M. S. Berger, and L. Dittmann, “Cloud ran for mobile networks—a technology overview,” *IEEE Communications surveys & tutorials*, vol. 17, no. 1, pp. 405–426, 2014.

5 T.-S. N. T. G. of IEEE 802.1, “Time-sensitive networks for fronthaul,” July 2016. IEEE P802.1/D0.4.

6 A. Dogra, R. K. Jha, and S. Jain, “A survey on beyond 5g network with the advent of 6g: Architecture and emerging technologies,” *IEEE Access*, vol. 9, pp. 67512–67547, 2020.

7 3GPP, *3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; Service requirements for the 5G system*; Stage 1 (Release 16).

8 G. Romano, “Imt-2020 requirements and realization,” *Wiley 5G Ref: The Essential 5G Reference Online*, pp. 1–28, 2019.

9 W. Yu, H. Hoogeveen, and J. K. Lenstra, “Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard,” *Journal of Scheduling*, vol. 7, no. 5, pp. 333–348, 2004.

10 D. Barth, M. Guiraud, B. Leclerc, O. Marcé, and Y. Strozecki, “Deterministic scheduling of periodic messages for cloud ran,” in *2018 25th International Conference on Telecommunications (ICT)*, pp. 405–410, IEEE, 2018.

11 D. Barth, M. Guiraud, and Y. Strozecki, “Deterministic scheduling of periodic messages for low latency in cloud ran,” *arXiv preprint arXiv:1801.07029*, 2018.

12 D. Barth, M. Guiraud, and Y. Strozecki, “Deterministic contention management for low latency cloud RAN over an optical ring,” in *ONDM 2019 - 23rd International Conference on Optical Network Design and Modeling (ONDM 2019)*, 2019.

13 N. G. Nayak, F. Dürr, and K. Rothermel, “Incremental flow scheduling and routing in time-sensitive software-defined networks,” *IEEE Transactions on Industrial Informatics*, vol. 14, no. 5, pp. 2066–2075, 2017.

14 W. Steiner, S. S. Craciunas, and R. S. Oliver, “Traffic planning for time-sensitive communication,” *IEEE Communications Standards Magazine*, vol. 2, no. 2, pp. 42–47, 2018.

15 A. C. T. dos Santos, B. Schneider, and V. Nigam, “Tnsched: Automated schedule generation for time sensitive networking,” in *2019 Formal Methods in Computer Aided Design (FMCAD)*, pp. 69–77, IEEE, 2019.

16 J. Korst, E. Aarts, J. K. Lenstra, and J. Wessels, “Periodic multiprocessor scheduling,” in *PARLE’91 Parallel Architectures and Languages Europe*, pp. 166–178, Springer, 1991.

17 C. Hanen and A. Munier, *Cyclic scheduling on parallel processors: an overview*. Université de Paris-Sud, Centre d’Orsay, Laboratoire de Recherche en Informatique, 1993.

18 E. Levner, V. Kats, D. A. L. de Pablo, and T. E. Cheng, “Complexity of cyclic scheduling problems: A state-of-the-art survey,” *Computers & Industrial Engineering*, vol. 59, no. 2, pp. 352–361, 2010.

19 R. M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan, “Railway track allocation: models and methods,” *OR spectrum*, vol. 33, no. 4, pp. 843–883, 2011.

20 P. Serafini and W. Ukovich, “A mathematical model for periodic scheduling problems,” *SIAM Journal on Discrete Mathematics*, vol. 2, no. 4, pp. 550–581, 1989.

21 A. J. Orman and C. N. Potts, “On the complexity of coupled-task scheduling,” *Discrete Applied Mathematics*, vol. 72, no. 1-2, pp. 141–154, 1997.
22 L. Schwiebert and D. Jayasimha, "A necessary and sufficient condition for deadlock-free wormhole routing," *J. Parallel Distributed Comput.*, vol. 32, pp. 103-117, 1996.

23 M. Guiraud, *Deterministic scheduling of periodic datagrams for low latency in 5G and beyond*. Theses, Université Paris-Saclay, June 2021.