






















































\section{Introduction}
\label{sec:introduction}

The always-increasing capacity of wireless systems is promoting the design of applications and services with increasingly challenging demands, such as video streaming, teleconference, telepresence, \acrfull{xr}, among others~\cite{tgayUsageModel}.
In order to meet the demand in terms of data rate of such applications, the latest versions of the \gls{wifi} standard, i.e., IEEE~802.11ad and 802.11ay, also known as \gls{wigig}, offer the possibility to communicate over the mmWave band at 60~GHz, where multiple 2.16~GHz channels are available.
By taking advantage of techniques such as channel bonding and \gls{mimo}, and by introducing novel features to the protocol stack, these standards can provide data rates over 100~Gbps~\cite{11ayMagazine}.

However, many applications also have very stringent \gls{qos} requirements, in particular in terms of delay and jitter, which may be incompatible with the stochastic nature of contention-based channel access mechanisms generally supported by legacy \glspl{wlan}.
To address this problem, the \gls{wigig} standards introduced a contention-free access mechanism that allows a \gls{sta} to reserve radio resources at regular time intervals.
These resources are organized in blocks, called \glspl{sp}, and the standards only specify the basic procedures to ensure inter-vendor compatibility, leaving the design and the implementation of the scheduler to the manufacturers.

Regarding the practical design, handling multiple periodic traffic streams can be problematic, especially when traffic flows with different periodicities coexist.
In this case, it is necessary to anticipate collisions among different periodic allocations and either adjust them or, in the worst case, reject new incompatible requests.
Furthermore, even if a collection of requests with identical traffic requirements is considered, upon receiving a new request, the scheduler needs to decide whether to rearrange the previously allocated resources to improve fairness and efficiency, or to maintain the original schedule and then best accommodate the new request, in order not to perturb the pre-existing streams but potentially reaching suboptimal resource allocation.
Moreover, \glspl{sp} are subject to a number of constraints, described in \cref{sec:framework_description}, which need to be accounted for when designing and optimizing scheduling algorithms.

With these challenges in mind, in this work we address both admission control and resource allocation for multiple periodic traffic sources, following the constraints given by the \gls{wigig} standards.
Specifically, we cast the periodic scheduling problem within the \gls{wigig} allocation framework and design a simple and efficient algorithm to check for the feasibility of a new request.
We then propose a simple admission control algorithm with limited scheduling capabilities, as well as a more elaborate and optimized strategy to increase the admission rate and, possibly, the fairness among independent flows.
Finally, we compare these two policies and shed some light on basic trade-offs.

The rest of the paper is organized as follows.
The resource allocation framework is described in \cref{sec:framework_description}, while \cref{sec:state_of_the_art} provides an overview of the State of the Art on related problems, and motivates our need to fill the gap of the current literature in this topic.
Then, we present the proposed algorithms in \cref{sec:scheduling_algorithms}. Performance analysis is presented in \cref{sec:results}.
Finally, in \cref{sec:conclusions} we draw our conclusions and propose possible extensions of this work.


\section{Framework Description}
\label{sec:framework_description}
Based on~\cite{standard802.11_2016}, \glspl{sta} can request the \gls{ap} to reserve periodic transmission intervals by sending a control frame containing the required periodicity ($\p{}$) and the minimum and maximum duration of each allocation ($[\Tmin{}, \Tmax{}]$).
The \gls{ap} advertises the allocated \glspl{sp} to the \glspl{sta} at each \gls{bi}, specifying the starting time, duration, and periodicity of each block.
The allocation needs to comply with a number of constraints:
\begin{enumerate}
 \item Periodicity ($\p{}$) can only be an integer multiple ($\p{} \in \mathbb{N}$) or an integer fraction ($\p{}^{-1} \in \mathbb{N}$) of a \gls{bi} (\ensuremath{T_{\rm BI}}), thus the block periodicity interval will be $\Tp{} = \p{} \, \ensuremath{T_{\rm BI}} $;
 \item Allocation blocks cannot be scheduled across the \gls{bi} boundaries;
 \item The allocated block duration $\Tblk{}$ should fall in the range $[\Tmin{}, \Tmax{}]$ specified in the resource request.
\end{enumerate}
A more detailed description of the constraints imposed by the standard can be found in~\cite{standard802.11_2016} and~\cite{mohebi2020challenges}.

Since this work is focused on  allocation algorithms for periodic traffic sources, we neglect the \glspl{cbap}, which is present in each \gls{bi} for asynchronous traffic.
In addition, to compare the scheduling algorithms in challenging conditions, we assume that the allocated resources will be maintained indefinitely, so that the channel load increases progressively as new resource reservations are accepted.
For the sake of simplicity and clarity, we also assume that the allocation blocks of a given accepted request are not fractioned into multiple disjoint intervals (i.e., each \gls{sp} will consist of a single time interval of duration $\Tblk{}$).
Furthermore, we consider a \textit{strict periodicity} constraint, which prevents the scheduler from changing the starting time of already allocated blocks, while the block duration $\Tblk{}$ can be freely changed within the interval $\qty[\Tmin{}, \Tmax{}]$.



\begin{figure}[tp]
 \centering

 \newcommand\fscale{1}
 \input{img/notation_joint_alloc.tex}
 \caption{Example of allocations $A_1$ (orange) and $A_2$ (blue), with $\p{2}=2\p{1}$.}
 \label{fig:joint_alloc}
\end{figure}

\section{State of the Art}
\label{sec:state_of_the_art}

Many works analyzing the \gls{mac} layer of the \gls{wigig} standards focus mostly on \glspl{cbap}, which extend the traditional WiFi access to cope with directional communications, either neglecting \gls{sp} allocations or considering extremely simple allocation schemes.
In \cite{babich2009throughput}, the authors proposed a mathematical framework for the analysis of \gls{e2e} metrics in 802.11-based systems, comparing throughput and average packet delay in scenarios where the nodes are equipped with advanced antenna systems.
The characteristics of the \gls{dcf} were taken into account, for which a theoretical performance analysis was carried out in \cite{bianchi2000performance}.
Instead, the authors in~\cite{pielli2019analytical} present a model to assess the performance of \glspl{cbap} for the IEEE 802.11ad standard, taking into account a directional channel model and the presence of scheduled \glspl{sp}, but they do not focus on how to assign such \glspl{sp}.

To the best of our knowledge, little work has been done on contention-free scheduling for \gls{wigig} networks.
In~\cite{hemanth2013performance,rajan2016saturation}, the authors analyze the case where all contention-free allocations occupy the beginning of each \gls{bi}, while the rest of the interval is left for a single \gls{cbap}.
This allocation strategy, however, cannot support requests for periodic resource allocations with time period shorter than $\ensuremath{T_{\rm BI}}{}$.
The authors of~\cite{khorov2016mathematical}, instead, propose an accurate mathematical analysis of the performance of a realistic \gls{vbr} traffic source in the presence of channel errors, when using a periodic resource allocation scheme, but do not tackle the problem of scheduling multiple periodic allocations at once.


On the other hand, the problem of periodic scheduling has been widely studied in other areas, such as real-time computation and task scheduling, where the objective is to complete tasks within a given time, while minimizing the resource utilization.
For example, the authors of~\cite{liu73scheduling} develop and compare heuristic algorithms for scheduling tasks with hard periodic deadlines and constant resource utilization, showing that a deadline-first approach ensures maximum resource utilization.
In~\cite{ramamritham95allocation}, the authors try to schedule safety-critical periodic tasks with precedence constraints, distributed over multi-processor systems using an adapted deadline-first approach, while the authors of~\cite{cheng95allocation} use simulated annealing to optimize a similar problem.
Finally, \cite{zhu03multiple} finds a low-overhead optimal solution (from a resource utilization point of view) assuming that tasks have a fixed resource requirement.

All these approaches, however, cannot be directly used in \gls{wigig} systems, either because they are not compliant with the constraints imposed by the resource allocation procedures (i.e., granularity of the allocation periods, \gls{bi} boundaries), or because they cannot exploit the \gls{wigig} standards' flexibility (e.g., the dynamic allocation of $\Tblk{}$). This work contributes to fill the gap by proposing admission control and scheduling algorithms that account for the specific features of \gls{mmw} \glspl{wlan}.



\section{Scheduling Algorithms}
\label{sec:scheduling_algorithms}
\begin{figure}[t!]
 \newcommand\fscale{1}
 \centering
 \begin{subfigure}[b]{\columnwidth}
  \centering
 
  \input{img/scheduling_alg_fail_0.tex}
  \caption{Scheduling step 0.}
  \label{fig:feasibility_check_fail_0}
 \end{subfigure}
 \\
 \begin{subfigure}[b]{\columnwidth}
  \centering
 
  \input{img/scheduling_alg_fail_1.tex}
  \caption{Scheduling step 1.}
  \label{fig:feasibility_check_fail_1}
 \end{subfigure}
 \\
 \begin{subfigure}[b]{\columnwidth}
  \centering
 
  \input{img/scheduling_alg_fail_2.tex}
  \caption{Scheduling step 2.}
  \label{fig:feasibility_check_fail_2}
 \end{subfigure}
 \caption{Feasibility check for an \textit{infeasible} pair of allocations, where $A_1$ (blue) was a pre-existing allocation with $\p{1}=\frac{1}{2}$, and the algorithm is checking whether a new allocation $A_2$ (orange) with $\p{2}=\frac{1}{3}$ is compatible.}
 \label{fig:feasibility_check_fail}
\end{figure}

\begin{algorithm}[t!]
 \footnotesize
 \caption{Feasibility check under strong periodicity conditions (see \cref{fig:feasibility_check_fail,fig:feasibility_check_succ}).}
 \label{alg:strict_periodicity_feasibility}
 \begin{algorithmic}[1]
  \REQUIRE $\qty{A_1,\ldots, A_{N-1}}$ (fixed), $A_N$ (new allocation), $\qty[\ensuremath{t_{\rm min}}, \ensuremath{t_{\rm max}}]$

  \STATE Compute $\Tp{1,\ldots,N}$
  \STATE $\tstart{N} = t_{0, \rm start}^N \leftarrow \ensuremath{t_{\rm min}}$ \COMMENT{\cref{fig:feasibility_check_fail_0}}

  \WHILE{$t_{0, \rm end}^{N} < \ensuremath{t_{\rm max}}$}
  \STATE Check for collisions in $\left[\ensuremath{t_{\rm min}}, \ensuremath{t_{\rm min}} + \Tp{1,\ldots,N} \right)$
  \IF{no collisions}
  \STATE $\ensuremath{t_{\rm feas}} \leftarrow \tstart{N}$
  \RETURN $A_N$ is feasible with starting time $\ensuremath{t_{\rm feas}}$ \COMMENT{\cref{fig:feasibility_check_succ}}
  \ELSE
  \STATE Allocation block $h \in A_N$ collides with allocation block $k \in A_i$, for some $i \in {1,\ldots,N-1}$
  \STATE $\Delta t \leftarrow t_{k, \rm end}^i - t_{h, \rm start}^N$
  \STATE $\tstart{N} \leftarrow \tstart{N} + \Delta t$
  \ENDIF
  \ENDWHILE

  \RETURN $A_N$ is not a feasible allocation \COMMENT{\cref{fig:feasibility_check_fail}}
 \end{algorithmic}
\end{algorithm}

We denote by $A_n= (\tstart{n}, \Tp{n}, \Tblk{n})$ the allocation for the $n$-th traffic stream, where $\tstart{n}$ is the starting epoch, $\Tp{n}$ is the period, and $ \Tblk{n}$ is the allocated duration of each individual block.
Therefore, the allocation consists of a sequence of blocks, where the $k$-th block of the $n$-th traffic stream takes the interval $b_k^n = \qty(t_{k, \rm start}^n, t_{k, \rm end}^{n})$, where
\begin{equation}
 \begin{aligned}\label{eq:alloc_blk_start_end}
  t_{k, \rm start}^n & = \tstart{n} + k \Tp{n}           \;;  \\
  t_{k, \rm end}^{n} & = \tstart{n} + k \Tp{n} + \Tblk{n} \;;
 \end{aligned}
\end{equation}
for $k=0,1,2,\ldots\;$.
A graphical example is shown in \cref{fig:joint_alloc}.

Following this definition we can say that, given $N$ distinct allocations $A_1,\ldots,A_N$, they are jointly periodic over a period
\begin{equation}
  T_p^{1,\ldots,N} = \mathrm{lcm}\left(T_p^i, \ldots, T_p^N \right),
\end{equation}
where $\mathrm{lcm}$ indicates the \textit{least common multiple} of the periods.
Note that, since all block periods are integer multiples or fractions of \ensuremath{T_{\rm BI}}, the \gls{lcm} can always be properly defined~\cite{zazkis2015lcm} as
\begin{equation}
  \mathrm{lcm}\left( \frac{a}{b}, \frac{c}{d} \right) = \frac{\mathrm{lcm}(a,c)}{\mathrm{gcf}(b,d)},
\end{equation}
where $\mathrm{gfc}$ is the \textit{greatest common factor}.


Given the periodicity of the allocation patterns, a new allocation $A_N$ should start within a time interval $\Tp{N}$ since the beginning of the \gls{bi}.
Moreover, a necessary requirement for admission is that in an interval of duration $T_P^{1,\ldots,N}$, no block $b_h^N$ overlaps with any block $b_k^n$, $n \in \{1,,\ldots,N-1\}$, $\forall h,k\geq 0$.

The remainder of this section is structured as follows: in \cref{sub:feasibility_check_algorithm} we will illustrate an algorithm to efficiently check whether a new allocation is compatible with a pre-existing schedule, in \cref{sub:simple_scheduler} we will present a simple scheduling algorithm, and finally in \cref{sub:max_min_fair_scheduler} we will describe in detail a more complex algorithm that aims at minimizing the rejection of new allocations under the \textit{strict periodicity} assumption.

\subsection{Feasibility Check Algorithm}
\label{sub:feasibility_check_algorithm}

\begin{figure}[t!]
 \newcommand\fscale{1}
 \centering
 \begin{subfigure}[b]{\columnwidth}
  \centering
 
  \input{img/scheduling_alg_succ_0.tex}
  \caption{Scheduling step 0.}
  \label{fig:feasibility_check_succ_0}
 \end{subfigure}
 \\
 \begin{subfigure}[b]{\columnwidth}
  \centering
 
  \input{img/scheduling_alg_succ_1.tex}
  \caption{Scheduling step 1.}
  \label{fig:feasibility_check_succ_1}
 \end{subfigure}
 \vspace{0.1pt}
 \\
 \begin{subfigure}[b]{\columnwidth}
  \centering
 
  \input{img/scheduling_alg_succ_2.tex}
  \caption{Feasible intervals.}
  \label{fig:feasibility_check_succ_2}
 \end{subfigure}
 \caption{Feasibility check for a \textit{feasible} pair of allocations, where $A_1$ (blue) was a pre-existing allocation with $\p{1}=\frac{1}{4}$, and the algorithm is checking whether a new allocation $A_2$ (orange) with $\p{2}=\frac{1}{2}$ is compatible.}
 \label{fig:feasibility_check_succ}
\end{figure}

This feasibility check can be performed as described in \cref{alg:strict_periodicity_feasibility}, whose arguments consist of the existing allocations $A_1,\ldots,A_{N-1}$, the new request $A_N$ and a search interval $\qty[\ensuremath{t_{\rm min}}, \ensuremath{t_{\rm max}}]$.
For reasons that will be clear later, we assume that the existing allocations cannot be changed, while for $A_N$ only $\tstart{N}$ can be modified, keeping the period $T_p^N$ and the block duration $\Tblk{N}$ fixed.
Based on these input values, the aim of the procedure is to find the earliest feasible starting time $\ensuremath{t_{\rm feas}}^N$ such that a block of duration $\Tblk{N}$ fits in the search interval.

To do so, starting from $\ensuremath{t_{\rm min}}$, the algorithm progressively shifts the starting time by an interval $\Delta t$ (described in \cref{alg:strict_periodicity_feasibility}) until either all feasibility conditions are met, or $t_{0, \rm end}^{N} > \ensuremath{t_{\rm max}}$, in which case the allocation $A_N$ with block duration $\Tblk{N}$ is rejected.

A trivial example involves $A_1$, i.e., the first received allocation request from a \gls{sta}.
In this case, $\ensuremath{t_{\rm min}}$ will be set to the start time of the first \gls{bi} following the reception of the request, while $\ensuremath{t_{\rm max}} = \Tp{N}$ to guarantee the periodicity.
Since no previous allocated \glspl{sp} exist, $A_1$ is immediately accepted with $\ensuremath{t_{\rm feas}} = \ensuremath{t_{\rm min}}$.
It is important to highlight that, however, by choosing specific combinations of input parameters, \cref{alg:strict_periodicity_feasibility} can be used also by more advanced scheduling schemes, as explained later.

Given any feasible starting time $\ensuremath{t_{\rm feas}}$, it is useful to compute the rightmost \textit{boundary} of the allocation, i.e., the largest interval $[\ensuremath{t_{\rm feas}},\ensuremath{t_{\rm lim}}]$ that would still make $b_0^N \in [\ensuremath{t_{\rm feas}},\ensuremath{t_{\rm lim}}]$ and, in turn, $A_N$ feasible, even for larger values $\tstart{N}$ and $\Tblk{N}$.
This boundary can be computed by finding the minimum distance between each $b_h \in A_N$ and each $b_k \in A_n$, $n \neq N$.
The final results will be the minimum measured distance.
A graphical illustration of how the algorithm behaves when the new request is infeasible is shown in \cref{fig:feasibility_check_fail}, while a new feasible request is shown in \cref{fig:feasibility_check_succ}.

Following this definition and the above numerical example, the first allocation request to be generated, i.e., $A_1$, will find itself in the optimal condition where $\ensuremath{t_{\rm feas}}=\ensuremath{t_{\rm min}}$ and $\ensuremath{t_{\rm lim}}=\ensuremath{t_{\rm max}}$.

In general, multiple feasible intervals exist.
To find an exhaustive list, we can iterate \cref{alg:strict_periodicity_feasibility} with $\tstart{N}$ initialized to the start time of the \gls{bi}, and progressively updated at each iteration with the value of $\ensuremath{t_{\rm lim}}$ found in the previous execution.
This procedure continues until the shift of $\tstart{N}$ leads to an infeasible allocation.
We define the list of feasible intervals (which depend on $\Tblk{N}$) as $\mathcal{I}_N = \qty{I_1^N,\ldots,I_M^N}$, where $I_m^N = \qty[\tfeasmn{m}{N}, \tlimmn{m}{N}]$, $m=1,\ldots,M$ (see \cref{fig:feasibility_check_succ_2}).
Hence, each of these intervals delimits the finite number of intervals in which the new allocation $A_N$ can be fitted, considering all previous allocations.
A good scheduling algorithm should then assess which interval yields the best overall performance, possibly trying to optimize a target \gls{kpi}.



\subsection{Simple Scheduler}
\label{sub:simple_scheduler}
The first scheduler that we propose assumes that the block duration and periodicity of already accepted traffic streams cannot be varied.
Then, a new request $A_N$ with a block duration of $\Tblk{N} \in [\Tmin{N}, \Tmax{N}]$ can be accepted only if there exists a feasible interval in $\mathcal{I}_N $ with a duration of at least $\Tmin{N}$.
Therefore, the maximum amount of available resources that can be allocated to $A_N$ is determined by the longest feasible interval, or by $\Tmax{N}$, whichever is smaller; $\tstart{N}$ and $\Tblk{N}$ need to be set accordingly.
We can already notice that, using this simple first-come-first-served approach, the latest requests are highly disadvantaged if the first ones require big slices of time resources.
In the long term, as we will see in \cref{sec:results}, this could lead not only to poor performance in terms of fairness, but also to a very low admission rate.


\subsection{Max-Min Fair Scheduler}
\label{sub:max_min_fair_scheduler}
A more flexible approach consists in dynamically adapting the duration of the allocated intervals within the admissible range, $\Tblk{n} \in [\Tmin{n}, \Tmax{n}]$, $\forall n=1,\ldots,N$, in order to distribute time resources among all traffic streams in a fairer manner.

Consider the following parameterized block duration:
\begin{equation}\label{eq:parameterized_tblk}
 \Tblk{n}(r) = \Tmin{n} + r_n(\Tmax{n} - \Tmin{n}), \quad r_n \in [0,1] \;.
\end{equation}
We consider a scheduler to be fair if $r_{\rm min} = \min_{n} \{r_n\}$ cannot be increased without breaking the limits imposed by some allocation under the \textit{strict periodicity} constraint (see \cref{sec:framework_description}).
The scheduling algorithm, then, should assign the largest possible \gls{sp} to each allocation, while respecting all the constraints.\footnote{Note that if $\Tmin{n}=\Tmax{n}$, $r_n$ has no meaning. For simplicity, this case has not been included in this study.}

To fit a new traffic stream, the pre-existing allocations will thus have to either maintain or reduce their block duration, depending on whether and how the new allocation collides with them.
This will lead to a lower rejection rate with respect to the \textit{\nameref{sub:simple_scheduler}} (\cref{sub:simple_scheduler}), and more fairness among requests distributed in time.

The proposed algorithm is here presented in two parts: the first part describes how the allocation scheme works (\cref{ssub:allocation_algorithm}), while the second part describes the fairness paradigm (\cref{ssub:optimally_fair_allocation}).

\subsubsection{Allocation Algorithm}
\label{ssub:allocation_algorithm}

Differently from the simple scheduler, this scheduler can change the block duration within the range imposed by the requesting \gls{sta}, i.e., $\Tblk{n} \in [\Tmin{n}, \Tmax{n}]$.
To reduce the rejection rate, we check the feasibility of a new allocation $A_N$ (\cref{sub:feasibility_check_algorithm}) by assuming all existing allocations are shrunk to their minimum, i.e., $\Tblk{n} = \Tmin{n}$ for $n=1,\ldots,N$.
If $A_N$ is infeasible even under these conditions, then the allocation cannot be granted without disattending the requests of some previously accepted flow.
Therefore, $A_N$ is rejected.
Conversely, if $A_N$ is feasible, it gets accepted, and in a later step the algorithm will try to increase the resource utilization of all allocations fairly.

From now on, we use the symbol $^*$ to represent the parameter values at the end of the execution of the algorithm.
We recall that, based on the strict periodicity assumption, the starting times of the already allocated blocks cannot change


Note that, given a set of feasible allocations, reducing any $r_n$ (and, in turn, the $\Tblk{n}$) still yields a valid configuration.
Similarly, a valid configuration for $A_N$ with $\tstart{N}$ and $r_N \geq 0$ will remain valid if $\tstart{N*} \geq \tstart{N}$ and $\tend{N*} = \tstart{N*} + \Tblk{N}(r_N^*) \leq \tend{N}$.
We thus consider the following constraints:
\begin{subequations}\label{eq:optimally_fair_alloc_constraints}
 \begin{align}
  \label{eq:rn_bound}
  r_n^*       & \leq r_n, \, \forall n \leq N;        \\
  \label{eq:tstart_bound}
  \tstart{N*} & \geq \tstart{N}; \\
  \label{eq:tend_bound}
  \tend{N*}   & \leq \ensuremath{t_{\rm lim}}^N.
 \end{align}
\end{subequations}

\floatstyle{spaceruled
\restylefloat{algorithm
\begin{algorithm}[t!]
 \footnotesize
 \caption{Max-min fair scheduling.}
 \label{alg:complex_allocation}
 \begin{algorithmic}[1]
  \REQUIRE $A_1,\ldots, A_N$, $\Tp{1,\ldots,N}$

  \STATE Compute $\mathcal{I}_N$ considering $\Tblk{n}=\Tmin{n} \forall n=1,\ldots,N$
  \FORALL{$I_m^N = \qty[\ensuremath{t_{\rm feas}}, \ensuremath{t_{\rm lim}}]^N_m \in \mathcal{I}_N$}
  \STATE $\tstart{N} \leftarrow \ensuremath{t_{\rm feas}}$
  \STATE Set $r_N$ such that $\Tblk{N} = \min\qty{\Tmax{N}, \ensuremath{t_{\rm lim}} - \ensuremath{t_{\rm feas}}}$ \COMMENT{\cref{eq:parameterized_tblk}}

  \FORALL{$A_n, \; n=1,\ldots,N-1$}

  \FORALL{(block $k \in A_n$) $\in \Tp{1,\ldots,N}$}
  \IF{block $k$ collides with $A_N$}
  \STATE Update $r_n^*$, $r_N^*$, $\tstart{N*}$ \COMMENT{\cref{ssub:optimally_fair_allocation}}

  \IF{$r_n^* < r_n$}
  \STATE Add/update $A_n$ to a list $\mathcal{C}$ of colliding allocations
  \STATE Memorize $r_{n,\rm prev} \leftarrow r_n$
  \ENDIF

  \STATE Update $r_n$, $r_N$, $\tstart{N}$
  \ENDIF

  \ENDFOR
  \ENDFOR

  \FORALL{$A_n \in \mathcal{C}$}
  \STATE Compute $\Delta t= \ensuremath{t_{\rm lim}} - \tstart{n}$ for $A_n$ given $A_N$ \COMMENT{see \cref{sec:scheduling_algorithms}}
  \STATE $\Tblk{n} \leftarrow \min\qty{\Tblk{n}(r_{n,\rm prev}), \Delta t}$ \COMMENT{Try to improve the allocation duration if $A_N$ has been further reduced}
  \ENDFOR

  \STATE Compute allocation score $s_m \leftarrow \min_{n=1,\ldots,N} r_n$
  \ENDFOR

  \RETURN The configuration which maximizes the allocation score $\qty{s_m}$
 \end{algorithmic}
\end{algorithm}

The algorithm starts by considering the first feasible interval $I_1^N$, which ensures a valid configuration when $r_n=0$, $\forall n \leq N$.
The new request is temporarily accepted with $\tstart{N}=\tfeasmn{1}{N}$ and maximum possible $r_N$, such that $\Tblk{N} = \min\qty{\Tmax{N}, \ensuremath{t_{\rm lim}} - \ensuremath{t_{\rm feas}}}$.

Then, the algorithms try to re-balance the resource allocation by increasing all $\{ r_n, \, \forall n \leq N \}$ to their previous values.
Given that feasible intervals $\mathcal{I}_N$ were computed considering all allocations with minimum duration, though, setting $\tstart{N}=\tfeasmn{1}{N}$ may (or may not) create a collision with a generic $A_i$ when setting $r_i\geq 0$ back to its previous value.

On the other hand, thanks to the information given by $\ensuremath{t_{\rm lim}}$, we can always choose $r_N$ such that the new allocation does not collide with a previous one, on the right.

Collisions can be found iteratively over each block of each previous allocation in a joint period.

If for a certain block $b_k^n \in A_n$ and a block $b_h^N \in A_N$ we have
\begin{equation}
 t_{k, \rm start}^{n} + \Tblk{n}(r_n) \geq t_{h, \rm start}^{N}.
\end{equation}
then the two allocations are in conflict, as shown in \cref{fig:collision_baseline}.
In this case, $\tstart{N*}$, $r_N^*$, and $r_n^*$ have to be updated following the constraints in \eqref{eq:optimally_fair_alloc_constraints}, as described in \cref{ssub:optimally_fair_allocation}.

The constraints from \eqref{eq:optimally_fair_alloc_constraints}, the existence of a non-empty set of feasible intervals, and the iterative nature of the problem ensure that the algorithm will stop in a finite time with a valid configuration.
Since each feasible interval $I_m^N \in \mathcal{I}_N$ has one locally fairest configuration, the exhaustive search described in \cref{alg:complex_allocation} is able to find the globally fairest configuration by exhaustive search.


\begin{figure}[tbp]
  \centering
 
  \newcommand\fscale{1}
  \input{img/collision_baseline.tex}
  \caption{Representation of a collision between $A_n$ and $A_N$.}
  \label{fig:collision_baseline}
 \end{figure}

\subsubsection{Optimally fair allocation}
\label{ssub:optimally_fair_allocation}

In this section, we will discuss how fairness can be achieved given a pair of colliding allocations $A_n$, $n\in \{1,\ldots,N-1\}$, and $A_N$.
In \cref{ssub:allocation_algorithm} we explained how such a collision can be found, e.g, between blocks $b_k^n$ and $b_h^N$.
For the sake of clarity, in this section we will drop the notation for the specific colliding blocks.

In order to fully exploit the available resources, looking at \cref{fig:collision_baseline}, we force $\tstart{N} = \tend{n}$ and $\tend{N} \leq \ensuremath{t_{\rm lim}}$.
In this way we make $A_N$ start right after $A_n$, still respecting the limits imposed by $\ensuremath{t_{\rm lim}}$.

While possibly not being optimal, this is still a sensible choice for a greedy approach that tries to maximize the fairness of the current configuration.
By doing so and imposing $r_n = r_N = r^*$, what we call the \textit{fairness equation}, and by noting that $r^*\leq 1$ should hold, we have that
\begin{equation}\label{eq:bounded_rstar}
 r^* = \min \qty{1, \frac{\ensuremath{t_{\rm lim}} - \tstart{n} - \Tmin{n} - \Tmin{N}}{\qty(\Tmax{n} - \Tmin{n}) + \qty(\Tmax{N} - \Tmin{N})}}.
\end{equation}
We call $r^*$ the \textit{fair allocation ratio}, and note that if $r^*<1$, it must be that $\tend{N}=\ensuremath{t_{\rm lim}}$, whereas if $r^*=1$ in general $\tend{N} \leq \ensuremath{t_{\rm lim}}$ by construction.

Depending on the initial conditions of the problem, there is a number of different cases which have to be properly managed in order to obtain a fair distribution of resources.

First of all, if $r_n \leq r^*$, following \cref{eq:rn_bound}, it means that previous adjustments do not make it possible for $A_n$ to obtain more resources while still ensuring a valid configuration, and thus $r_n^* = r_n$.
Furthermore, since we assume that a collision happens between $A_n$ and $A_N$ with this configuration, $A_N$ has to be delayed setting $\tstart{N*} = \tstart{n} + \Tblk{n}(r_n^*) > \tstart{N}$.

In case also $r_N \leq r^*$, allocation $A_N$ cannot be extended either.
Since both allocations have $r_n, r_N \leq r^*$, they will both surely fit in the feasible interval.
If, instead, $r_N > r^*$, $A_N$ can obtain $r_N^* \geq r_n^*$, i.e., $\Tblk{N*} = \min\qty{\Tblk{N}(r_N), \ensuremath{t_{\rm lim}} - \tstart{N*}}$.

On the other hand, if $1 \geq r_n > r^*$, the block duration must be reduced so that $r_n^* = r^*$.
Then, if also $r_N > r^*$, both allocations must be trimmed and are fairly allocated, i.e., $r_n^*=r_N^*=r^* < 1$.
It follows from the properties of \cref{eq:bounded_rstar} that $\tend{N*} = \ensuremath{t_{\rm lim}}$ and $\tstart{N*} > \tstart{N}$.

Finally, if $r_N \leq r^* < r_n \leq 1$, and therefore $r_N < 1$, the properties of \cref{eq:bounded_rstar} imply that $\tend{N}=\ensuremath{t_{\rm lim}}$.
Since $A_N$ cannot be extended without possibly reducing the allocation ratio of other allocations, $\tstart{N*}=\tstart{N}$ and $r_N^* = r_N$.
Since, by assumption, $\tend{n} > \tstart{N}$, the duration of $A_n$ needs to be reduced so that $\Tblk{n*} = \tstart{N*} - \tstart{n} < \Tblk{n}$.





\section{Results}
\label{sec:results}


\begin{figure*}[t!]
\newcommand\fheight{0.5\columnwidth}
\newcommand\fwidth{0.9\columnwidth}

 \begin{subfigure}[b]{\textwidth}
  \centering
  \input{img/scenario1_legend.tex}
 \end{subfigure}
 \\
 \vspace{-2ex}
 \\
 \hspace*{\fill}%
 \begin{subfigure}[t]{0.45\textwidth}
  \centering
  \input{img/accrate_eta_bound_0.1.tex}
  \vspace*{-2ex}
  \caption{Acceptance Rate vs. $\rho$.}
  \label{fig:accrate_rho_bound}
 \end{subfigure}
 \hspace*{\fill}%
 \begin{subfigure}[t]{0.45\textwidth}
  \centering
  \input{img/jain_eta_0.1.tex}
  \caption{Jain's Index vs. $\rho$.}
  \label{fig:jain_rho}
 \end{subfigure}
 \hspace*{\fill}%
 \\
 \vspace*{2ex}
 \\
 \hspace*{-2pt}
 \begin{subfigure}[t]{0.45\textwidth}
  \centering
  \input{img/tblk_eta_0.1.tex}
  \caption{Normalized average $\Tblk{}$ vs. $\rho$.}
  \label{fig:tblk_rho}
 \end{subfigure}
 \hspace*{6ex}%
 \begin{subfigure}[t]{0.45\textwidth}
  \centering
  \input{img/tblk_accrate_0.1.tex}
  \caption{Normalized average $\Tblk{}$ vs. Acceptance Rate.}
  \label{fig:tblk_accrate}
 \end{subfigure}
 \hspace*{\fill}%

 \caption{Results for Scenario~1.}
 \label{fig:results_scenario_1}
\end{figure*}

In this section, we evaluate the algorithms described in \cref{sec:scheduling_algorithms}.
The proposed schedulers have been implemented in Python, only focusing on their capabilities of allocating communication resources to the different traffic streams.
The simulations proposed here do not include full stack behaviors, which will be investigated in future works, and their aim is thus to highlight the fundamental characteristics of each algorithm.

Based on their design criteria, we expected the two algorithms to differ mainly with respect to three \glspl{kpi}, namely the acceptance rate of new requests, the fairness among accepted allocations, and the average scheduled block duration.
To highlight these characteristics we shape the offered traffic based on three parameters, namely: the \textit{average allocation request}
\begin{equation}\label{eq:avg_allocation_request}
T_{\rm avg} = \frac{\Tmin{} + \Tmax{}}{2};
\end{equation}
the \textit{interval ratio}
\begin{equation}\label{eq:interval_ratio}
\rho = \frac{\Tmin{}}{\Tmax{}}  \in [0, 1];
\end{equation}
and the \textit{load factor}
\begin{equation}\label{eq:load_factor}
\lambda = \frac{T_{\rm avg}}{\Tp{}}.
\end{equation}
Note that, for a given average allocation request $T_{\rm avg}$, a low interval ratio $\rho$ corresponds to very flexible allocations, while $\rho=1$ corresponds to rigid allocations where $\Tmin{}=\Tmax{}$.

The proposed algorithms are compared in two different simulation scenarios:
\begin{itemize}
 \item \textit{Scenario~1}: all traffic streams are homogeneous, i.e., all requests have the same parameters.
       Specifically, we consider the case with periodicity $\Tp{}=\frac{\ensuremath{T_{\rm BI}}}{3}$, load factor $\lambda=0.1$, and $\rho \in (0,1)$.
       The impact of different periodicities and load factors is also discussed.
 \item \textit{Scenario~2}: multiple non-homogeneous applications coexist on the same network, thus generating traffic streams with different characteristics.
      We analyze a scenario where traffic streams can be of class $C_1$ or $C_2$, with periodicity $\Tp{C_1}=\frac{\ensuremath{T_{\rm BI}}}{3}$ and $\Tp{C_2}=\frac{\ensuremath{T_{\rm BI}}}{5}$, respectively.
       Both classes have load factor $\lambda=0.1$ and interval ratio $\rho=0.1$.
\end{itemize}

To evaluate the performance of the algorithms, we propose three \glspl{kpi} for \textit{Scenario~1}, shown in \cref{fig:results_scenario_1}.
Note that, given the discrete behavior of the problem and the lack of randomness in the proposed algorithms, the plots cannot be smoothed by running multiple repetitions.


\begin{figure*}[t!]
 \newcommand\fheight{0.5\columnwidth}
 \newcommand\fwidth{0.9\columnwidth}
 %
 \begin{subfigure}[b]{\textwidth}
  \centering
  \input{img/scenario_2_2_legend.tex}
 \end{subfigure}
 \\
 \hspace*{\fill}%
 \begin{subfigure}[b]{0.45\textwidth}
  \centering
 
 
 
  \input{img/conditional_acceptance_c1_3000run_21pt.tex}
  \caption{First allocation is of class $C_1$.}
  \label{fig:conditional_c1}
 \end{subfigure}
 \hspace*{\fill}%
 \begin{subfigure}[b]{0.45\textwidth}
  \centering
 
 
 
  \input{img/conditional_acceptance_c2_3000run_21pt.tex}
  \caption{First allocation is of class $C_2$.}
  \label{fig:conditional_c2}
 \end{subfigure}
 \hspace*{\fill}%
 \\
 \vspace{1ex}%
 \begin{subfigure}[b]{\textwidth}
  \centering
  \input{img/scenario2_legend.tex}
 \end{subfigure}
 \\
 \hspace*{\fill}%
 \begin{subfigure}[b]{0.45\textwidth}
  \centering
 
 
 
  \input{img/variability_3000run_21pt.tex}
  \caption{Variability of scheduled allocations.}
  \label{fig:variability}
 \end{subfigure}
 \hspace*{\fill}%
 \begin{subfigure}[b]{0.45\textwidth}
  \centering
 
 
 
  \input{img/occupancy_3000run_21pt.tex}
  \caption{BI occupancy ratio.}
  \label{fig:occupancy}
 \end{subfigure}
 \hspace*{\fill}%

 \caption{Results for Scenario 2.
 
  }
 \label{fig:results_scenario_2}
\end{figure*}

The first metric is the acceptance rate (\cref{fig:accrate_rho_bound}), defined as the ratio between the number of accepted allocation requests and the maximum number of acceptable requests.
To compute this achievable upper bound, since all allocations share the same parameters we ignore the strict periodicity assumption and calculate how many allocations with minimum duration $\Tblk{}=\Tmin{}$ can fit in a period $\Tp{}$, which is equal to $N_{\rm max}(\rho) = \left\lfloor \frac{\Tp{}}{\Tmin{}(\rho)} \right\rfloor$ and shown as a red, dashed line.
The acceptance rates can thus be normalized in the interval $[0,1]$, where $1$ means that the scheduler reaches the peak acceptance rate.
Since as $\rho \rightarrow 0$, $\Tmin{} \rightarrow 0$ and thus $N_{\rm max} (\rho) \rightarrow \infty$, we consider at most 100 allocations.

As expected, the \textit{simple scheduler} suffers from a lower acceptance rate than the \textit{max-min fair} one, even though, starting from $\rho=0.5$, the two algorithms tend to behave similarly.
In fact, more rigid allocations do not give enough flexibility to the \textit{max-min fair scheduler} to perform its optimization, thus yielding similar performance to the much \textit{simple scheduler}.

The second metric is \textit{Jain's Fairness Index} (\cref{fig:jain_rho}), defined as:
\begin{equation}
 \mathcal{J} = \frac{\left( \sum_n x_n \right)^2}{n \cdot \sum_n (x_n)^2},
\end{equation}
where only accepted allocations are counted and $x_n$ can either be the block duration $\Tblk{n}$ or the block duration ratio $r_n$.
If the $\{ x_n \}$ are all equal, then $\mathcal{J}(x)=1$.
On the other hand, the more unequal the values of $\{ x_n \}$, the closer the metric to its minimum $\mathcal{J}(x) = \frac{1}{N}$.

Based on the results plotted in \cref{fig:jain_rho}, both algorithms behave fairly with respect to the accepted allocations.

The third metric, shown in \cref{fig:tblk_rho}, offers a different perspective considering the average normalized block duration $\overline{\Tblk{}}/\Tmax{}(\rho)$.
As expected, the \textit{simple scheduler} shows an oscillating trend, due to the discrete behavior of the allocations.
In fact, the last scheduled allocation will only reduce \Tblk{} down to $\Tmin{}(\rho)$, thus, if the portion of DTI left by the previous allocations is less than $\Tmin{}(\rho)$, no additional allocations can be fitted.
On the other hand, the \textit{max-min fair scheduler} will try to reduce all allocations up to their minimum duration in order to avoid rejecting new ones, granting more accepted allocations at the cost of an overall lower block duration.

Finally, the two most discriminating metrics, namely the average normalized block duration and the acceptance rate, are plotted against each other in \cref{fig:tblk_accrate}.
In general, the \textit{simple scheduler} tends to favor higher average block duration for a lower acceptance rate, while the \textit{max-min fair scheduler} tends to favor acceptance rate at the cost of a lower average block duration, as expected.
Both algorithms are able to ensure high fairness to the accepted allocations, generally well above 0.85.

Similar behaviors were also observed for load factors $\lambda \in \{0.025, 0.4\}$, not shown here.
As expected, higher loads tend to have more pronounced variability in both the average block duration and the fairness granted to the accepted allocations.
Curiously, regardless of the load factor, for values of the interval ratio larger than $\rho\approx 0.5$, the two algorithms tend to have very similar performance due to the more rigid allocation requests that do not allow the \textit{max-min fair scheduler} to exploit its agility.

\ml{what about $\Tp{}>\ensuremath{T_{\rm BI}}$? does anything change?} \md{if I recall correctly, we obtained similar results and so we avoid further studies on this case}

\textit{Scenario~2} allows us to analyze the impact of allocations with different periodicities on the overall network performance, as a function of the probability $P(C_1)$ that a request $C_1$ is offered to the system.

Since allocations with different periods coexist, it is mandatory to decide how many allocations should be offered to the schedulers, as this will affect how the acceptance rate is normalized.
We define the \textit{minimum occupancy} as the minimum BI occupancy ratio of the allocation of category $C_i$, namely $O_{\rm min}^i = \Tmin{i}/\Tp{i}$.
Allocations are offered to the schedulers as long as the cumulative minimum offered occupancy does not exceed the value of 1.

In \cref{fig:conditional_c1,fig:conditional_c2} we show the biasing effect of the first accepted allocation on the proposed schedulers.
Clearly, the \textit{simple scheduler} suffers a strong and symmetric effect, meaning that once the first allocation is scheduled with maximum duration, it will be harder for subsequent allocations with a different period to fit the constrained BI, making the scheduler favor allocations with the same period.
On the other hand, it is significantly harder to interpret the behavior of the more complex \textit{max-min fair scheduler}.
From further results, not shown here for lack of space, it is possible to notice that allocations with a lower average BI occupancy are favored, with a slight preference towards those with lower values of \Tp{} and \Tmin{}.
As also shown here, in fact, allocations with lower values of \Tp{}, such as $C_2$ with respect to $C_1$, tend to fragment the BI more, making it harder to then fit allocations with different periodicity and higher \Tmin{}.

To further confirm this biasing behavior, we show the variability $\nu$ among the scheduled allocations, defined as
\begin{equation}
  \nu_{1,2}=\frac{\min\{| C_1 |, | C_2 |\}}{\max\{| C_1 |, | C_2 |\}},
\end{equation}
where $| C_i |$ represents the number of accepted allocations of category $C_i$.
This metric takes values in $[0,1]$, where a value of 0 means that only allocations of a single type have been accepted, while a value of 1 means that the same number of allocations of both categories have been accepted.
Results are shown in \cref{fig:variability}, which confirms that the \textit{simple scheduler} favors a more homogeneous BI allocation, while the \textit{max-min fair scheduler} shows once again more flexibility, being able to accommodate fairly requests from different classes, as shown by the higher variability of the accepted allocations.

Finally, we studied how efficiently the two algorithms are able to use the radio resources by measuring the BI occupancy ratio, i.e., the ratio between scheduled and unscheduled air time.
It can be noticed that, while the \textit{simple scheduler} accepts fewer requests, it is able to use almost all available resources.
This is due to the fact that the scheduler tends to accept homogeneous allocations, allowing them to be packed more efficiently in the BI.
On the other hand, the \textit{max-min fair scheduler} successfully fits multiple allocations of both types, but the constraints on the periodicity and the minimum block duration $\Tmin{}$ prevent it from fully utilizing the whole \gls{bi} when a mixture of the two types of sources is presented.
Nonetheless, it ensures very high occupancy ratios, always above 95\% for the shown example.


\section{Conclusions}
\label{sec:conclusions}

In this paper, we presented a framework for periodic scheduling in \gls{wigig}-compatible devices.
We proposed two heuristic algorithms, \textit{simple} and \textit{max-min fair schedulers}, and accurately described their inner workings.
Finally, we assessed their performance in two different scenarios, showing that the \textit{max-min fair scheduler} tends to trade resource availability for a much higher acceptance rate, contrary to the \textit{simple scheduler}'s behavior, while both schedulers obtained a high Jain's fairness index for the accepted allocations.

Even working in a simplified settings without considering further sources of complexity from other parts of the communication stack, it was possible to notice that both the design and the evaluation of \gls{wigig}-specific scheduling algorithms for periodic sources is highly non-trivial and can show surprising results.
In fact, while the formalization of the problem is straightforward, scheduling algorithms often have to deal with many hard-to-predict edge cases, which greatly increases the difficulty of designing a general algorithm.

Future works will focus on multiple objectives.
A first objective is to implement these algorithms in a full-stack simulator, allowing the study of APP-layer performance metrics for a range of possible applications.
A second objective is to extend the framework by relaxing some of the assumptions made in \cref{sec:framework_description} and test the impact of each one of them on the overall performance of a \gls{wigig} system.
A third objective is to extend the study for scheduling multiple allocations at once, a possibility given by \gls{mimo} techniques.
To further achieve a realistic evaluation, the impact of accurate wireless channel simulations, physical layer design, as well as user mobility will also be studied.



\bibliographystyle{IEEEtran}
