# On the Age of Information of Processor Sharing Systems

Beñat Gandarias, Josu Doncel, Mohamad Assaad B. Gandarias and J. Doncel are
with University of the Basque Country, UPV/EHU.M. Assaad is with Laboratoire
des Signaux et Systèmes (L2S), CentraleSupelec, University of Paris-
Saclay.This work has been partially supported by the Department of Education
of the Basque Government, Spain through the Consolidated Research Group
MATHMODE (IT1294-19) and by the Marie Sklodowska-Curie grant agreement N.
777778.

###### Abstract

In this paper, we examine the Age of Information (AoI) of a source sending
status updates to a monitor through a queue operating under the Processor
Sharing (PS) discipline. While AoI has been well studied for various queuing
models and policies, less attention has been given so far to the PS
discipline. We first consider the M/M/1/2 queue with and without preemption
and provide closed-form expressions for the average AoI in this case. We
overcome the challenges of deriving the AoI expression by employing the
Stochastic Hybrid Systems (SHS) tool. We then extend the analysis to the M/M/1
queue with one and two sources and provide numerical results for these cases.
Our results show that PS can outperform the M/M/1/1* queue in some cases.

###### Index Terms:

Age of Information; Processor Sharing Queues; Stochastic Hybrid Systems;

##  I Introduction

With the development of Internet of Things (IoT), there is an increasing
interest nowadays in real-time monitoring, where a remote monitor is tracking
the status of a source/sensor. Age of Information (AoI) has been introduced in
[1] to capture the freshness of information in such contexts, networked
control systems. This metric is defined as the time elapsed since the
generation of the last correctly received packet at the monitor. Since its
introduction, this metric has received particular interest from researchers
and has been studied in various network models and scenarios. Since the
evolution of the AoI over time exhibits a sawtooth pattern, researchers have
focused on AoI-dependent metrics computation, such as Average AoI, Peak AoI,
etc. In particular, the average AoI has received a lot of attention and has
been evaluated in various continuous and discrete time network models. In [1,
2, 3, 4], it was shown that the computation of the average AoI is a hard task
in general settings since it needs the evaluation of the expected value of the
product of inter-arrival and response times, which are correlated random
variables. The average AoI has been computed by considering specific source
and response time models (although these models cover a wide range of
scenarios), and the medium between the source and monitor has been modeled by
a queuing system. For instance, the authors in [1] derived the average AoI of
the M/M/1 queue, M/D/1 queue, and D/M/1 queue models and obtained the best
arrival rate of the packet update. The single source single destination M/M/1
queue under First Come First Served (FCFS) and Last Come First Served (LCFS)
disciplines has been studied in [2, 3]. The peak AoI has also been studied in
various scenarios. For instance, average AoI and peak AoI have been analyzed
for M/M/1/1 and M/M/1/2 queues [5, 6]. To improve the AoI, a queue discipline
called M/M/1/2*, in which a new arriving packet preempts a waiting one in the
queue, has been introduced in [5, 6].

In addition to the aforementioned works that have focused on Poisson arrivals
and exponential service time, more general single queue models have been
explored. In [7], a G/G/1/1 is analyzed. The average aoI in a multi-source
M/G/1/1 queue with packet management has been studied in [8, 9], where it was
shown that preempting packets does not reduce AoI for small service time
variance coefficients.

The analysis of AoI was also studied in the case of multi-source single-server
(e.g. M/M/1/2*) in [10, 11] and multi-source multi-server systems in [12, 13,
14]. While the aforementioned works have focused on predefined arrival and
queuing disciplines, several studies have explored the optimal status update
(information sampling and scheduling) policy in various scenarios, e.g. in
single hop networks [15, 16, 17], multihop networks [18, 19], etc.
Interestingly, it has been shown in [20, 21], for a single source and single
destination scenario, that zero-wait policy, where the source transmits a
fresh update right when the previous one has been delivered, does not always
minimize the AoI. For discrete-time multi-user networks, several Age-based
scheduling solutions have also been developed, e.g. [15, 22, 23]. A whittle
index based scheduling policy has been developed in [15, 22]. Such a Whittle
index based policy has been proved to be asymptotically optimal in some cases
[24, 23]. Furthermore, there have been studies on energy-constrained updating,
e.g. in energy harvesting context [25, 26, 27, 28, 29]. It is worth mentioning
that in addition to the above AoI metrics, there is an increasing interest
recently in developing beyond-age metrics [30, 31, 32, 33, 34, 35, 36], for
example to capture the semantic of information [37] such as value of
information [38], Age of Incorrect of Information (AoII)[32, 39, 40, 41],
Query Age of Incorrect Information (QAoII) [42], etc. For more recent surveys
of existing work the reader can refer to [43, 44, 45].

In this paper, we focus on the average AoI metric. We consider a single source
single destination queuing model under Processor Sharing (PS) discipline.
Under the Processor Sharing discipline, all the packets in the queue are
served at the same speed, i.e., when there are $n$ packets in the queue, each
packet gets a proportion of $1/n$ of the service capacity. Despite its
extensive use and analysis since its introduction in [46], e.g. [47, 48], to
the best of our knowledge, the PS queue has not been studied from the AoI
perspective. In this paper, we provide analysis of the average AoI in a single
queue system under the PS discipline. We make use of Stochastic Hybrid System
(SHS) tool to overcome the challenges of analyzing the AoI under the PS
discipline. Specifically, the main contributions in this paper are as follows:

  * •

We first consider the M/M/1/2 queue without preemption and we provide an
explicit expression of the AAoI for the PS discipline.

  * •

We then consider the M/M/1/2 queue with preemption, which we denote the
M/M/1/2∗ queue. We also provide an analytical expression of the AAoI when the
queueing discipline is PS.

  * •

We show that, for the M/M/1/2 with and without preemption, the PS discipline
outperforms the FGFS discipline in terms of AAoI. Moreover, for the M/M/1/2
queue, the AAoI for the FGFS discipline is, at most, 1.2 times worse than the
AAoI for the PS discipline and, for the M/M/1/2∗ queue, it is at most 4/3
worse.

  * •

We prove that the AAoI of the M/M/1/2∗ queue is always smaller than the AAoI
of the M/M/1/2 queue under PS, and, in fact, the AAoI of the M/M/1/2 queue is,
at most, 5/3 worse than the AAoI of the M/M/1/2∗ queue.

  * •

We analyze the AAoI of the M/M/1 queue for PS and FGFS (First Generated First
Served) disciplines, and provide numerical results by solving the system of
equations obtained by the SHS technique.

  * •

We analyze the case of two sources and provide numerical results, by solving
the equations resulting from the SHS analysis. Interestingly, the results show
that the PS discipline can outperform the M/M/1/1* in some cases.

The remainder of the article is organized as follows. We present the system
model in Section II. In Section III, we study the M/M/1/2 model without and
with preemption, while the M/M/1 analysis is provided in Section IV. The
multiple source scenario is given in Section V, and the conclusion is
presented in Section VI. The proofs are given in the appendix.

##  II Model Description

We consider a monitoring system in which there is a process of interest (i.e.
the source) whose status needs to be observed timely by a remote monitor (i.e.
the sink). To this end, packets containing information about the status of the
system are generated at the source and are sent to the sink through a
transmission channel.

Figure 1: A monitoring system example.

We assume that packet generation times at the source follow a Poisson process
of rate $\lambda$ and that the transmission channel is a single server queue
with exponential service times of rate $\mu$. The load of the system is
$\rho=\lambda/\mu$. Moreover, it is assumed that the transmission times from
the source to the queue and from the queue to the monitor are both zero.

We consider that the queue serves the packet containing status updates of the
system according to the Processor Sharing (PS) discipline. This means that all
the packets in the queue are served at the same speed, i.e., when there are
$n$ packets in the queue, each packet is served at rate $\mu/n$.

We consider the Age of Information as the metric of performance of the system.
The Age of Information is defined as the time elapsed since the generation
time of the last packet that has been delivered to the monitor successfully.
More precisely, if $t_{i}$ is the generation time of the $i$-th packet and
$L(t)$ is the index of the last successfully delivered packet before time $t$,
the Age of Information at time $t$ is defined as $\Delta(t)=t-t_{L(t)}$.

Our focus will be on the AAoI of divers queueing models, which we denote by
$\Delta$ with a subindex that indicates the queueing model we refer to. For
instance, when we study the AAoI of the M/M/1/2-PS queue, we denote it by
$\Delta_{M/M/1/2-PS}$.

##  III The M/M/1/2 Queue With And Without Preemption

###  III-A The M/M/1/2 Queue

We consider the M/M/1/2 queue without preemption. In this system, the maximum
number of packets that can be stored in the queue is two. Besides, when a new
packet arrives and there are two packets in the system, the incoming packet is
discarded. Under the PS discipline, when there is a single packet in the
queue, it is served at rate $\mu$, but when there are two packets in the
queue, both are served at rate $\mu/2$.

The following result characterizes the AAoI of the M/M/1/2 queue without
preemption and under the PS discipline. The proof is available in Appendix A.

######  Proposition 1.

The AAoI of the M/M/1/2-PS queue is

$\Delta_{M/M/1/2-PS}=\frac{5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4}}{2\lambda\mu(\lambda+\mu)(\lambda^{2}+\lambda\mu+\mu^{2})}.$
(1)

In [6], it is shown that the AAoI of the M/M/1/2 queue with the FGFS
discipline and without preemption in waiting is

$\Delta_{M/M/1/2-FGFS}=\frac{3\lambda^{4}+5\lambda^{3}\mu+4\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{\lambda\mu(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)}.$
(2)

We now aim to analyze the benefits on the AAoI of the PS discipline with
respect to the FGFS discipline by comparing (1) with (2). The following result
provides an analytical comparison of both expressions. The proof is available
in Appendix B.

######  Proposition 2.

We have that

$1\leq\frac{\Delta_{M/M/1/2-FGFS}}{\Delta_{M/M/1/2-PS}}\leq 1.2.$ (3)

From this result, we conclude that the PS discipline outperforms the FGFS
discipline and also that the AAoI when we consider the FGFS discipline is, at
most, 1.2 times the AAoI of the PS discipline.

###  III-B The M/M/1/2∗ Queue

We now consider the M/M/1/2 queue with preemption. In this system, when a new
packet arrives to the system and there are two packets in the queue, the last
update in the queue is replaced by the incoming one. Note that this is a big
difference with respect to the M/M/1/2 queue without preemption that has been
studied in the previous section. In fact, it is known that when we consider
the Age of Information metric, preemption leads to a performance improvement
with respect to a system without preemption [12]. In this section, we follow
the notation of [6] and we denote by M/M/1/2∗ the system under study in this
section.

Our goal is to extend the results of the previous section to the M/M/1/2∗ to
analyze the impact of the preemption on the ratio of the AAoI of the FGFS
discipline over the AAoI of the PS discipline.

We now present the expression of the AAoI of the M/M/1/2∗. The proof of this
result is postponed to Appendix C.

######  Proposition 3.

The AAoI of the M/M/1/2∗-PS queue is

$\Delta_{M/M/1/2^{*}-PS}=\\\
\frac{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{2\lambda\mu(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}.$
(4)

We now aim to compare the AAoI of the M/M/1/2∗ queue under the PS discipline
with the AAoI under the FGFS discipline. The expression of the former system
has been shown in [6], and it is

$\Delta_{M/M/1/2^{*}-FGFS}=\\\
\frac{2\lambda^{5}+7\lambda^{4}\mu+8\lambda^{3}\mu^{2}+7\lambda^{2}\mu^{3}+4\lambda\mu^{4}+\mu^{5}}{\lambda\mu(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}.$
(5)

We focus on the ratio
$\frac{\Delta_{M/M/1/2^{*}-FGFS}}{\Delta_{M/M/1/2^{*}-PS}}$. In the following
result, we provide a lower-bound and an upper-bound of this ratio. The proof
of this result is provided in Appendix D.

######  Proposition 4.

We have that

$1\leq\frac{\Delta_{M/M/1/2^{*}-FGFS}}{\Delta_{M/M/1/2^{*}-PS}}\leq\frac{4}{3}.$
(6)

From this result, we conclude that the AAoI of the M/M/1/2 queue with
preemption and under PS discipline is always smaller than the AAoI of the
M/M/1/2 queue with preemption and under FGFS discipline. Besides, we also
conclude that $\Delta_{M/M/1/2^{*}-FGFS}$ is, at most, $4/3$ times worse than
$\Delta_{M/M/1/2^{*}-PS}$.

The authors in [6] showed that the AAoI of the M/M/1/2 queue with preemption
and under FGFS is smaller than the AAoI without preemption and under FGFS.
This implies that, for the FGFS, when the maximum number of packets in the
queue is two, preemption of packets leads to a performance improvement. In the
following result, we study if such a performance improvement is also achieved
when we consider the PS queue instead of the FGFS queue. Its proof is
presented in Appendix E.

######  Proposition 5.

We have that

$1\leq\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/2^{*}-PS}}\leq\frac{5}{3}.$ (7)

From this result, we derive that the aforementioned property shown in [6]
about the preemption of the FGFS when the maximum number of packets is two
also holds when we consider the PS discipline.

###  III-C The M/M/1/2∗∗ Queue

We now consider the M/M/1/2 queue with preemption to the oldest packet. In
this system, when a new packet arrives to the system and there are two packets
in the queue, unlike in the previous section, the oldest packet in the queue
is replaced by the incoming one. We denote this queueing model as the
M/M/1/2∗∗ queue.

We now present the expression of the AAoI of the M/M/1/2∗∗. The proof is
presented in Appendix F.

######  Proposition 6.

The AAoI of the M/M/1/2∗∗-PS queue is

$\Delta_{M/M/1/2^{**}-PS}=\\\
\frac{2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}{2\lambda\mu(\lambda+\mu)^{3}(\lambda^{2}+\mu^{2}+\lambda\mu)}.$
(8)

We aim to compare the AAoI of the M/M/1/2∗∗-PS queue with the AAoI of the
M/M/1/2∗∗-FGFS queue. We present the expression of the latter in the following
proposition. The proof is available in Appendix G.

######  Proposition 7.

The AAoI of the M/M/1/2∗∗-FGFS queue is

$\Delta_{M/M/1/2^{**}-FGFS}=\\\
\frac{\lambda^{6}+6\lambda^{5}\mu+14\lambda^{4}\mu^{2}+15\lambda^{3}\mu^{3}+11\lambda^{2}\mu^{4}+5\lambda\mu^{5}+\mu^{6}}{\lambda\mu(\lambda+\mu)^{3}(\lambda^{2}+\mu^{2}+\lambda\mu)}.$
(9)

We focus on the ratio
$\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}$. In the
following result, as in the previous section, we provide a lower-bound and an
upper-bound of this ratio. The proof is given in Appendix H.

######  Proposition 8.

We have that

$1\leq\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}\leq 1.0731.$
(10)

From this result, we conclude that the AAoI of the M/M/1/2∗∗-PS queue is
slightly smaller than the AAoI of the M/M/1/2∗∗-FGFS queue. Furthermore, we
also show that $\Delta_{M/M/1/2^{**}-FGFS}$ is, at most, $1.0731$ worse than
$\Delta_{M/M/1/2^{**}-PS}$.

We now want to compare the two different systems with preemption and under the
PS discipline. As a matter of fact, we aim to compare the AAoI of the M/M/1/2∗
queue and the AAoI of the M/M/1/2∗∗ queue under the PS discipline. In the
following result, we study if discarding the oldest packet agaisnt the newest
one leads to a performance improvement. We present the proof in Appendix I.

######  Proposition 9.

We have that

$1\leq\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/2^{**}-PS}}\leq\frac{3}{2}.$
(11)

From this result, we see that, indeed, preemption replacing the oldest packet
in the queue leads to a performance improvement against preemption replacing
the newest packet. And that $\Delta_{M/M/1/2^{*}-PS}$ is, at most,
$\frac{3}{2}$ worse than $\Delta_{M/M/1/2^{**}-PS}$. Moreover, from
Proposition 7 and Proposition 11 we derive the following result.

######  Corollary 1.

We have that

$1\leq\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/2^{**}-PS}}\leq\frac{5}{2}.$
(12)

We conclude that the AAoI of the M/M/1/2 queue under the PS discipline and
with optimal preemption can be, at most, 2.5 better than the one without
preemption.

###  III-D Comparison with the M/M/1/1 Queue

In this section our goal will be comparing the M/M/1/1 queue with the
M/M/1/2∗∗ queue under the PS discipline. In the M/M/1/1 queue system, the
maximum number of packets that can be stored in the queue is one. Besides, in
the M/M/1/1 queue, when a new packet arrives and there is already a packet in
the system, the incoming packet is discarded.

It is shown in [6] the following result that characterizes the AAoI of the
M/M/1/1 queue:

$\Delta_{M/M/1/1}=\frac{2\lambda^{2}+2\lambda\mu+\mu^{2}}{\lambda\mu(\lambda+\mu)}.$
(13)

We now focus on the ratio $\frac{\Delta_{M/M/1/1}}{\Delta_{M/M/1/2^{*}-PS}}$.
We give a lower and an upper bound for the ratio in the following result. The
proof is available in Appendix J.

######  Proposition 10.

We have that

$1\leq\frac{\Delta_{M/M/1/1}}{\Delta_{M/M/1/2^{*}-PS}}\leq\frac{4}{3}.$ (14)

From this result, we see that the AAoI of the M/M/1/2∗ queue under the PS
discipline is smaller than the AAoI of the M/M/1/1 queue (and, as a
consequence, AAoI of the M/M/1/2∗∗ queue under the PS discipline is smaller
than the AAoI of the M/M/1/1 queue). Moreover, we conclude that
$\Delta_{M/M/1/1}$ will be, at most, 2 times worse than
$\Delta_{M/M/1/2^{**}-PS}$, i.e.,

$1\leq\frac{\Delta_{M/M/1/1}}{\Delta_{M/M/1/2^{**}-PS}}\leq 2.$

We now compare the AAoI of the M/M/1/1 queue with the AAoI of the M/M/1/2
queue. We present the proof in Appendix K.

######  Proposition 11.

We have that

$0.9641\leq\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/1}}\leq\frac{5}{4}.$ (15)

From this result, we conclude that, when $\lambda\in[0,\mu]$, then we have
that $\Delta_{M/M/1/1}\geq\Delta_{M/M/1/2-PS}$, whereas when
$\lambda\in[\mu,\infty)$, we have that
$\Delta_{M/M/1/2-PS}\geq\Delta_{M/M/1/1}$. Besides, the AAoI of the M/M/1/1
queue can be, at most, 5/4 times better than the AAoI of the M/M/1/2-PS queue
and the AAoI of the M/M/1/2-PS queue can be, at most, $1/0.9641\approx 1.0372$
times better than the AAoI of the M/M/1/1 queue.

###  III-E Comparison with the M/M/1/1∗ Queue

We now want to extend the results of the previous section to the M/M/1/1∗
queue. In the M/M/1/1∗ system we have preemption, when a new packet arrives
while there is a packet in the queue, the packet will be replaced by the
incoming one.

In [11] it is shown that the expression of $\Delta_{M/M/1/1^{*}}$ is

$\Delta_{M/M/1/1^{*}}=\frac{\lambda+\mu}{\lambda\mu}.$ (16)

Now, we compare the AAoI of the M/M/1/1∗ queue with the AAoI of the
M/M/1/2∗∗-PS queue. In order to that we give the following result. The proof
is available in Appendix L.

######  Proposition 12.

We have that

$1\leq\frac{\Delta_{M/M/1/2^{**}-PS}}{\Delta_{M/M/1/1^{*}}}\leq 1.0788.$ (17)

##  IV The M/M/1 Queue

We now analyze the AAoI of the M/M/1 queue with the PS discipline. For this
case, we assume that $\rho<1$ to ensure stability. Our first result of this
section consists of establishing a lower-bound of $\Delta_{M/M/1-PS}$. Its
proof is available in Appendix M.

######  Lemma 1.

$\Delta_{M/M/1-PS}>\frac{\mu-\lambda}{\lambda\mu}.$

It is shown in [1] that

$\Delta_{M/M/1-FGFS}=\frac{1}{\mu}\left(1+\frac{1}{\rho}+\frac{\rho^{2}}{1-\rho}\right),$
(18)

which is clearly unbounded from above when $\lambda\to 0$. This result implies
that, when we consider the M/M/1-FGFS model, the arrival rate that minimizes
the mean number of customers does not minimize the AAoI. Using Lemma 1, we now
show that this property also holds when we consider the M/M/1-PS model.

######  Proposition 13.

When $\lambda\to 0$, $\Delta_{M/M/1-PS}$ is unbounded from above.

###### Proof.

From Lemma 1, the desired result follows noting that, when $\lambda\to 0$,
$\frac{\mu-\lambda}{\lambda\mu}$ tends to infinity. ∎

We have tried to provide an explicit expression of $\Delta_{M/M/1-PS}$ using
the Stochastic Hybrid System (SHS) technique. Unfortunately, the derived
expression are extremely difficult and, therefore, we did not succeed in
characterizing $\Delta_{M/M/1-PS}$. After extensive numerical experiments, we
conjecture that the AAoI of the M/M/1-PS queue has a similar form as
$\Delta_{M/M/1-FGFS}$. To be more precise, we now present our conjecture.

######  Conjecture 1.

$\Delta_{M/M/1-PS}=\frac{1}{\mu}\left(\frac{1}{\rho}+1+C(\rho)\right),$ (19)

where $\lim_{\rho\to 0}C(\rho)=0$, $\lim_{\rho\to 1}C(\rho)=+\infty$ and
$0\leq C(\rho)\leq\frac{\rho^{2}}{1-\rho}$ for all $\rho\in(0,1)$. Moreover,
when $\rho$ is large enough,

$\frac{(\rho-0.5)^{3}}{1-\rho}\leq
C(\rho)\leq\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}.$ (20)

We remark that, if Conjecture 20 holds, then it follows that, when $\lambda$
is large enough,

$\Delta_{M/M/1-PS}\geq\frac{1}{\mu}\left(\frac{1}{\rho}+1+\frac{(\rho-0.5)^{3}}{1-\rho}\right).$

Let us note that the rhs of the above expression tends to infinity when
$\rho\to 1$. Therefore, we conclude that, if Conjecture 20 holds, when
$\rho\to 1$, $\Delta_{M/M/1-PS}$ tends to infinity.

We know from (18) that, when $\rho\to 1$, the AAoI of the M/M/1-FGFS queue
tends to infinity, therefore the load that maximizes the throughput does not
optimize the AAoI for this model. Now, we conclude that, if Conjecture 20
holds, then the aforementioned property is verified also for the M/M/1-PS
queue.

In the following result, we study the value of the ratio
$\frac{\Delta_{M/M/1-FGFS}}{\Delta_{M/M/1-PS}}$. The proof is available in
Appendix N.

######  Proposition 14.

If Conjecture 20 holds, then

$1\leq\frac{\Delta_{M/M/1-FGFS}}{\Delta_{M/M/1-PS}}\leq+\infty.$

##  V Multiple Sources

In this section we will expand our analysis from single-source systems to
multiple source systems. In fact, we consider that there are two sources
sending update packets through the transmission channel to the monitor
following Poisson processes. The rate at which updates of source 1 are sent is
$\lambda_{1}$ and of source 2 is $\lambda_{2}$. The service rate is
exponentially distributed with rate $\mu$ for the updates from any source.

We aim to analyze the impact of $\lambda_{2}$ on the AAoI of the updates of
source one under the different queueing disciplines. In our numerical analysis
we consider that $\mu=1$ and we represent with a solid line the AAoI of the
M/M/1-PS queue, with a dashed line the AAoI of the M/M/1-FGFS and with a
dotted line the AAoI of the M/M/1/1∗ queue. In Figure 2, we consider that
$\lambda_{1}=0.1$ and $\lambda_{2}$ varying from $0.001$ to $0.05$. We observe
that the influence of $\lambda_{2}$ is very similar for PS and FGFS (and that
PS outperforms FGFS for all $\lambda_{2}$), but the AAoI of the M/M/1/1∗ queue
increases dramatically with $\lambda_{2}$. Indeed, when $\lambda_{2}$ is close
to zero, the AAoI of the M/M/1/1∗ queue is the smallest one, but further
numerical experiments show that it tends to infinity when $\lambda_{2}$ grows
large much faster than FGFS and PS. Therefore, we conclude that, when
$\lambda_{1}$ is small, the presence of other sources has a very negative
impact in the AAoI of the M/M/1/1∗ compared to the AAoI of PS and FGFS.

Figure 2: Comparison of the AAoI of source 1 in a M/M/1 queue with divers
queueing disciplines when $\lambda_{2}$ changes from 0.001 to 0.05 and
$\lambda_{1}=0.1$.

We now aim to study whether the conclusions obtained for $\lambda_{1}$ small
extend to instances where $\lambda_{1}$ is large. To this end, we consider
$\lambda_{1}=5$ and $\lambda_{2}$ varying from 0.001 to $10^{3}$. In Figure 3,
we represent the values of the AAoI we have obtained in our numerical
analysis. We observe that the influence of $\lambda_{2}$ is again very similar
for PS and FGFS and when $\lambda_{2}$ is close to zero the AAoI of the
M/M/1/1∗ queue is the smallest one. However, when $\lambda_{2}$ is large, the
AAoI of the M/M/1/1∗ queue is not worse than that of PS and FGFS; they equal,
in fact, the same value. As a result, we conclude that, when $\lambda_{1}$ is
large, the presence of a different source does not have a very negative impact
on the performance of the M/M/1/1∗ queue compared to the PS and FGFS.

Figure 3: Comparison of the AAoI of the source 1 in a M/M/1 queue with divers
queueing disciplines when $\lambda_{2}$ changes from 0.001 to $10^{3}$ and
$\lambda_{1}=5$.

We now focus on the AAoI of both sources. To this aim, we analyze the
evolution of the sum of the AAoI of both sources as a function of the arrival
rate of one of them. We consider $\mu=1$ in these experiments and same
queueing disciplines as in Figure 2 and Figure 3. In Figure 5, we set
$\lambda_{1}=0.1$ and we plot the AAoI of both sources when $\lambda_{2}$
changes from 0.001 to 30. We observe that, in this case, the AAoI of the
M/M/1/1∗ queue is larger than the AAoI of PS and FGFS. Therefore, we conclude
that, when the arrival rate of one of the source is low, PS and FGFS
outperform M/M/1/1∗. However, in Figure 4, we consider $\lambda_{1}=5$ to
analyze whether the aforementioned conclusions extend to the instance where
$\lambda_{1}$ is large. We observe that, when $\lambda_{2}$ is small, the AAoI
of the M/M/1/1∗ queue is again larger than the AAoI of PS and FGFS, whereas
when $\lambda_{2}$ is large, the AAoI of the M/M/1/1∗ queue is smaller. We
conclude that, when the arrival rate of both sources is large, it is
preferable from the perspective of the AAoI the M/M/1/∗ queue and, in the rest
of the cases, PS or FGFS are preferable.

Figure 4: Comparison of the AAoI of source 1 plus the AAoI of source 2 in a
M/M/1 queue with divers queueing disciplines when $\lambda_{2}$ changes from
0.001 to 30 and $\lambda_{1}=0.1$.  Figure 5: Comparison of the AAoI of source
1 plus the AAoI of source 2 in a M/M/1 queue with divers queueing disciplines
when $\lambda_{2}$ changes from 0.001 to $10^{3}$ and $\lambda_{1}=5$.

##  VI Conclusions

In this paper, we investigated the average AoI in a system composed of sources
sending status updates to a monitor through a Processor Sharing (PS) queue. We
considered the single source M/M//2 queue with and without preemption, and
derived a closed-form expression of the average AoI by making use of SHS tool.
We compared analytically our results to the FGFS discipline. The results of
this work is consistent with [12] since we provide analytical results that
show that disciplines without queueing have good AoI performance.

We then extended the analysis to the M/M/1 queue with one and two sources. We
solved numerically the equations resulting from the SHS framework and compared
the obtained results with the FGFS and M/M/1/1*, which is known to have good
AoI performance. Our results show that the PS discipline can outperform the
M/M/1/1* queue in some cases.

##  Appendix A Proof of Proposition 1

We use the SHS methodology [11] to characterize the AAoI of the M/M/1/2-PS
queue. The SHS technique is formed by a couple $(x,q)$ where $x$ is a
continuous state and $q$ a discrete state. For this model, the discrete state
belongs to the continuous time Markov chain illustrated in Figure 6, where
each state represents the number of packets in the queue; the continuous state
is a vector $\mathbf{x}(t)=[x_{0}(t)\ x_{1}(t)\ x_{2}(t)]$ where $x_{0}(t)$ is
the Age of Information at time $t$ and $x_{i}(t)$ is the age of the i-th
packet in the queue. We also define $b_{0}=[1,0,0],$ $b_{1}=[1,1,0]$ and
$b_{2}=[1,1,1]$ that represent which are the packets whose age increases at
rate one for each of the states of the Markov chain of Figure 6.

The second column of Table I represents the rate at which transitions of the
Markov chain occur. The steady-state distribution of this Markov chain is
clearly

$\pi_{i}=\frac{\rho^{i}}{1+\rho+\rho^{2}},i=0,1,2.$

We now describe each of the transitions of Table I.

  * $l=0$

A new packet arrives when the queue is empty. This occurs with rate $\lambda$.
For this case, the age of the monitor does not change and the age of the first
packet in the queue is equal to zero, i.e., $x_{1}^{\prime}=0$.

  * $l=1$

There is one packet in the queue and it is served, which occurs with rate
$\mu$. For this case, the age of the monitor is replace by the age of the
packet in service, i.e., $x_{0}^{\prime}=x_{1}$.

  * $l=2$

A new packet arrives when there is another packet in the queue. This occurs
with rate $\lambda$. For this case, the age of the monitor and of the packet
that was being served in the queue do not change. However, the age of the
second packet is equal to zero.

  * $l=3$

There are two packets in the system and the packet that arrived first is
served. This occurs with rate $\mu/2$. For this case, the age of the monitor
changes to the age of the packet that has been served, i.e.,
$x_{0}^{\prime}=x_{1}$. Besides, the packet that stays in the queue has become
the freshest of the packets in the queue and, therefore,
$x_{1}^{\prime}=x_{2}$.

  * $l=4$

There are two packets in the system and the packet that last arrived is
served. This occurs with rate $\mu/2$. For this case, the age of the monitor
is replaced by the age of the last arrived packet, i.e.,
$x_{0}^{\prime}=x_{2}$. Besides, the packet that stays in the queue is
obsolete and, therefore, we replace it by a fake update with the same age of
the served packet, i.e., $x_{1}^{\prime}=x_{2}$.

  * $l=5$

There are two packets in the system and a new packet arrives. This occurs with
rate $\lambda$. For this case, the new incoming packet is discarded, therefore
the age of the monitor and of the packets in the queue does not change.

$0$$1$$2$$l=5$$l=0$$l=1$$l=2$$l=3$$l=4$ Figure 6: The Markov chain under consideration in the proof of Proposition 1. $l$ | $\lambda^{(l)}$ | $q\longrightarrow q^{\prime}$ | $x\longrightarrow x^{\prime}=A_{l}x$ | $v_{ql}A_{l}$
---|---|---|---|---
0 | $\lambda$ | $0\longrightarrow 1$ | $[x_{0},0,0]\longrightarrow[x_{0},0,0]$ | $[v_{00},0,0]$
1 | $\mu$ | $1\longrightarrow 0$ | $[x_{0},x_{1},0]\longrightarrow[x_{1},0,0]$ | $[v_{11},0,0]$
2 | $\lambda$ | $1\longrightarrow 2$ | $[x_{0},x_{1},0]\longrightarrow[x_{0},x_{1},0]$ | $[v_{10},v_{11},0]$
3 | $\frac{\mu}{2}$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{1},x_{2},0]$ | $[v_{21},v_{22},0]$
4 | $\frac{\mu}{2}$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{2},x_{2},0]$ | $[v_{22},v_{22},0]$
5 | $\lambda$ | $2\longrightarrow 2$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{0},x_{1},x_{2}]$ | $[v_{20},v_{21},v_{22}]$
TABLE I: The SHS table under consideration in the proof of Proposition 1.

We apply (35a) of [11] for our case and we obtain:

$\displaystyle[v_{00},v_{01},v_{02}]\lambda=$ $\displaystyle
b_{0}\pi_{0}+\mu[v_{11},0,0]$
$\displaystyle[v_{10},v_{11},v_{12}](\lambda+\mu)=$ $\displaystyle
b_{1}\pi_{1}+\lambda[v_{00},0,0]+\frac{\mu}{2}[v_{21},v_{22},0]$
$\displaystyle+\frac{\mu}{2}[v_{22},v_{22},0]$
$\displaystyle[v_{20},v_{21},v_{22}](\lambda+\mu)=$ $\displaystyle
b_{2}\pi_{2}+\lambda[v_{10},v_{11},0]+\lambda[v_{20},v_{21},v_{22}].$

From Theorem 4 of [11], we know that, if there exists a non negative solution
of the above system of equations, then the AAoI of this model is given by
$v_{00}+v_{10}+v_{20}$.

We solve the above system of equations and we get

$\displaystyle v_{00}$
$\displaystyle=\frac{\mu(\lambda+\mu)}{\lambda(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{10}$
$\displaystyle=\frac{3\lambda^{2}+2\mu^{2}+4\lambda\mu}{2(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{11}$
$\displaystyle=\frac{\lambda}{\lambda^{2}+\lambda\mu+\mu^{2}}$ $\displaystyle
v_{20}$
$\displaystyle=\frac{5\lambda^{3}+6\lambda^{2}\mu+2\lambda\mu^{2}}{2\mu(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{21}$
$\displaystyle=\frac{2\lambda^{2}}{\mu(\lambda^{2}+\lambda\mu+\mu^{2})}$
$\displaystyle v_{22}$
$\displaystyle=\frac{\lambda^{2}}{\mu(\lambda^{2}+\lambda\mu+\mu^{2})}$

Therefore,

$\displaystyle\Delta_{M/M/1/2-PS}$ $\displaystyle=v_{00}+v_{10}+v_{20}$
$\displaystyle=\frac{5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4}}{2\lambda\mu(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)},$

where the last equality has been obtained simplifying the derived expression.
And the desired result follows.

##  Appendix B Proof of Proposition 3

We first note that (2) can be written as follows

$\frac{3\lambda^{4}+5\lambda^{3}\mu+4\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{\lambda\mu(\lambda+\mu)(\lambda^{2}+\lambda\mu+\mu^{2})}.$

As a result,

$\frac{\Delta_{M/M/1/2-FGFS}}{\Delta_{M/M/1/2-PS}}=2\frac{3\lambda^{4}+5\lambda^{3}\mu+4\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4}}.$
(21)

Thus, taking into account that the rhs of (21) tends to 1 when $\lambda\to 0$
and to 1.2 when $\lambda\to\infty$, the desired result follows if we show that
the rhs of (21) is increasing with $\lambda$, which we proof in the following
result.

######  Lemma 2.

The rhs of (21) is an increasing function of $\lambda$ for all $\mu>0$.

###### Proof.

We compute the derivative of
$\frac{3\lambda^{4}+5\lambda^{3}\mu+4\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4}}$
with respect to $\lambda$ and it results

$\frac{12\lambda^{3}+15\lambda^{2}\mu+8\lambda\mu^{2}+3\mu^{3}}{5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4}}\\\
-(20\lambda^{3}+27\lambda^{2}\mu+16\lambda\mu^{2}+6\mu^{3})\\\
\frac{(3\lambda^{4}+5\lambda^{3}\mu+4\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4})}{(5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4})^{2}}.$

The above expression is positive if and only if

$(12\lambda^{3}+15\lambda^{2}\mu+8\lambda\mu^{2}+3\mu^{3})\\\
(5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda\mu^{3}+2\mu^{4})\\\
>(20\lambda^{3}+27\lambda^{2}\mu+16\lambda\mu^{2}+6\mu^{3})\\\
(3\lambda^{4}+5\lambda^{3}\mu+4\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}),$

which simplifying we obtain that

$2\lambda^{6}\mu+8\lambda^{5}\mu^{2}+12\lambda^{4}\mu^{3}+10\lambda^{3}\mu^{4}+3\lambda^{2}\mu^{5}>0,$

which is true for all $\mu>0$. And the desired result follows. ∎

##  Appendix C Proof of Proposition 4

The proof is similar to that of Proposition 1. In fact, we formulate the same
SHS approach with the exception of transition $l=5$, which is described in
Table II.

We again apply (35a) of [11] and we get the following system of equations:

$\displaystyle[v_{00},v_{01},v_{02}]\lambda=$ $\displaystyle
b_{0}\pi_{0}+\mu[v_{11},0,0]$
$\displaystyle[v_{10},v_{11},v_{12}](\lambda+\mu)=$ $\displaystyle
b_{1}\pi_{1}+\lambda[v_{00},0,0]+\frac{\mu}{2}[v_{21},v_{22},0]$
$\displaystyle+\frac{\mu}{2}[v_{22},v_{22},0]$
$\displaystyle[v_{20},v_{21},v_{22}](\lambda+\mu)=$ $\displaystyle
b_{2}\pi_{2}+\lambda[v_{10},v_{11},0]+\lambda[v_{20},v_{21},0].$

The solution of this system of linear equations is

$\displaystyle v_{00}$
$\displaystyle=\frac{3\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{\lambda(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{10}$
$\displaystyle=\frac{\lambda^{4}+7\lambda^{3}\mu+13\lambda^{2}\mu^{2}+8\lambda\mu^{3}+2\mu^{4}}{2(\lambda+\mu)^{3}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{11}$
$\displaystyle=\frac{2\lambda^{2}\mu+\lambda\mu^{2}}{(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{20}$
$\displaystyle=\frac{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{2\lambda\mu(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{21}$
$\displaystyle=\frac{\lambda^{4}+4\lambda^{3}\mu+2\lambda^{2}\mu^{2}}{\mu(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{22}$
$\displaystyle=\frac{\lambda^{2}}{(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)}.$

According to Theorem 4 of [11], the desired value is obtained by summing
$v_{00}$, $v_{10}$ and $v_{20}$. And the desired result follows.

$l$ | $\lambda^{(l)}$ | $q\longrightarrow q^{\prime}$ | $x\longrightarrow x^{\prime}=A_{l}x$ | $v_{ql}A_{l}$
---|---|---|---|---
0 | $\lambda$ | $0\longrightarrow 1$ | $[x_{0},0,0]\longrightarrow[x_{0},0,0]$ | $[v_{00},0,0]$
1 | $\mu$ | $1\longrightarrow 0$ | $[x_{0},x_{1},0]\longrightarrow[x_{1},0,0]$ | $[v_{11},0,0]$
2 | $\lambda$ | $1\longrightarrow 2$ | $[x_{0},x_{1},0]\longrightarrow[x_{0},x_{1},0]$ | $[v_{10},v_{11},0]$
3 | $\frac{\mu}{2}$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{1},x_{2},0]$ | $[v_{21},v_{22},0]$
4 | $\frac{\mu}{2}$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{2},x_{2},0]$ | $[v_{22},v_{22},0]$
5 | $\lambda$ | $2\longrightarrow 2$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{0},x_{1},0]$ | $[v_{20},v_{21},0]$
TABLE II: The SHS table under consideration in the proof of Proposition 4

##  Appendix D Proof of Proposition 6

As in the proof of Proposition 3, we first show that the ratio under study is
monotonically increasing with $\lambda$. First, we note that the ratio
$\frac{\Delta_{M/M/1/2^{*}-FGFS}}{\Delta_{M/M/1/2^{*}-PS}}$ can be written as
follows

$\frac{4\lambda^{5}+14\lambda^{4}\mu+16\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}.$
(22)

######  Lemma 3.

The ratio

$\frac{\Delta_{M/M/1/2^{*}-FGFS}}{\Delta_{M/M/1/2^{*}-PS}}$

is an increasing function of $\lambda$.

###### Proof.

The derivative of (22) with respect to $\lambda$ is

$\frac{20\lambda^{4}+56\lambda^{3}\mu+48\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4}}{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}-\\\
(15\lambda^{4}+44\lambda^{3}\mu+45\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
\frac{4\lambda^{5}+14\lambda^{4}\mu+16\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{(3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})^{2}}.$

We assume that the above expression is negative and we will see that it is an
absurd. Thus, the derivative of (22) with respect to $\lambda$ is negative if
and only if

$(20\lambda^{4}+56\lambda^{3}\mu+48\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
(3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})<\\\
(15\lambda^{4}+44\lambda^{3}\mu+45\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
(4\lambda^{5}+14\lambda^{4}\mu+16\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}),$

which expanding the polynomials it results

$\displaystyle
60\lambda^{9}+388\lambda^{8}\mu+1060\lambda^{7}\mu^{2}+1732\lambda^{6}\mu^{3}+1996\lambda^{5}\mu^{4}$
$\displaystyle+1668\lambda^{4}\mu^{5}+1008\lambda^{3}\mu^{6}+432\lambda^{2}\mu^{7}+120\lambda\mu^{8}+16\mu^{9}$
$\displaystyle<60\lambda^{9}+386\lambda^{8}\mu+1036\lambda^{7}\mu^{2}+1656\lambda^{6}\mu^{3}+1880\lambda^{5}\mu^{4}$
$\displaystyle+1572\lambda^{4}\mu^{5}+968\lambda^{3}\mu^{6}+426\lambda^{2}\mu^{7}+120\lambda\mu^{8}+16\mu^{9}.$

We now simplify this expression and we obtain

$2\lambda^{8}\mu+24\lambda^{7}\mu^{2}+76\lambda^{6}\mu^{3}+116\lambda^{5}\mu^{4}+96\lambda^{4}\mu^{5}+40\lambda^{3}\mu^{6}\\\
+6\lambda^{2}\mu^{7}<0,$

which is clearly false since $\lambda$ and $\mu$ are positive. Therefore, the
desired result follows.

∎

We now prove Proposition 6 by studying the limit of the ratio
$\frac{\Delta_{M/M/1/2^{*}-FGFS}}{\Delta_{M/M/1/2^{*}-PS}}$ when $\lambda$
tends to zero and to infinity. For the later limit, we get one, whereas for
the former, we get 4/3. And the desired result follows.

##  Appendix E Proof of Proposition 7

We show that the ratio $\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/2^{*}-PS}}$
is increasing with $\lambda$. We first provide the expression of the ratio
under analysis:

$\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/2^{*}-PS}}=\\\
\frac{5\lambda^{5}+14\lambda^{4}\mu+17\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}.$

We observe that the limit when $\lambda\to 0$ (resp. when $\lambda\to\infty$)
of the above expression is one (resp. is 5/3). Therefore, the proof ends by
showing that the ratio
$\frac{\Delta_{M/M/1/2^{*}-FGFS}}{\Delta_{M/M/1/2^{*}-PS}}$ is increasing with
$\lambda$.

######  Lemma 4.

$\frac{\Delta_{M/M/1/2^{-}PS}}{\Delta_{M/M/1/2^{*}-PS}}$ is an increasing
function of $\lambda$.

###### Proof.

The derivative of $\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/2^{*}-PS}}$ with
respect to $\lambda$ is

$\frac{25\lambda^{4}+56\lambda^{3}\mu+51\lambda^{2}\mu^{2}+28\lambda^{2}\mu^{3}+8\mu^{4}}{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}\\\
-(15\lambda^{4}+44\lambda^{3}\mu+45\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
\frac{5\lambda^{5}+14\lambda^{4}\mu+17\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{(3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})^{2}}.$

This expression is positive if and only if

$(25\lambda^{4}+56\lambda^{3}\mu+51\lambda^{2}\mu^{2}+28\lambda^{2}\mu^{3}+8\mu^{4})\\\
(3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})\\\
>(15\lambda^{4}+44\lambda^{3}\mu+45\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
(5\lambda^{5}+14\lambda^{4}\mu+17\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}).$

Expanding the polynomials and simplifying, we get the following expression:

$13\lambda^{8}\mu+48\lambda^{7}\mu^{2}+107\lambda^{6}\mu^{3}+148\lambda^{5}\mu^{4}+120\lambda^{4}\mu^{5}+56\lambda^{3}\mu^{6}\\\
+12\lambda^{2}\mu^{7}>0,$

which is clearly positive since $\lambda$ and $\mu$ are positive. Thus, the
desired result follows. ∎

##  Appendix F Proof of Proposition 8

The proof is very similar to that of Proposition 4. We formulate the same SHS
approach with the exception of transition $l=5$, whis is described in Table
III.

We again apply (35a) of [11] and we get the following system of equations:

$\displaystyle[v_{00},v_{01},v_{02}]\lambda=$ $\displaystyle
b_{0}\pi_{0}+\mu[v_{11},0,0]$
$\displaystyle[v_{10},v_{11},v_{12}](\lambda+\mu)=$ $\displaystyle
b_{1}\pi_{1}+\lambda[v_{00},0,0]+\frac{\mu}{2}[v_{21},v_{22},0]$
$\displaystyle+\frac{\mu}{2}[v_{22},v_{22},0]$
$\displaystyle[v_{20},v_{21},v_{22}](\lambda+\mu)=$ $\displaystyle
b_{2}\pi_{2}+\lambda[v_{10},v_{11},0]+\lambda[v_{20},v_{22},0].$

$l$ | $\lambda^{(l)}$ | $q\longrightarrow q^{\prime}$ | $x\longrightarrow x^{\prime}=A_{l}x$ | $v_{ql}A_{l}$
---|---|---|---|---
0 | $\lambda$ | $0\longrightarrow 1$ | $[x_{0},0,0]\longrightarrow[x_{0},0,0]$ | $[v_{00},0,0]$
1 | $\mu$ | $1\longrightarrow 0$ | $[x_{0},x_{1},0]\longrightarrow[x_{1},0,0]$ | $[v_{11},0,0]$
2 | $\lambda$ | $1\longrightarrow 2$ | $[x_{0},x_{1},0]\longrightarrow[x_{0},x_{1},0]$ | $[v_{10},v_{11},0]$
3 | $\frac{\mu}{2}$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{1},x_{2},0]$ | $[v_{21},v_{22},0]$
4 | $\frac{\mu}{2}$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{2},x_{2},0]$ | $[v_{22},v_{22},0]$
5 | $\lambda$ | $2\longrightarrow 2$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{0},x_{2},0]$ | $[v_{20},v_{22},0]$
TABLE III: The SHS table under consideration in the proof of Proposition 8

The solution of this system of linear equations is

$\displaystyle v_{00}$
$\displaystyle=\frac{3\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{\lambda(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{10}$
$\displaystyle=\frac{5\lambda^{4}\mu+19\lambda^{3}\mu^{2}+21\lambda^{2}\mu^{3}+10\lambda\mu^{4}+2\mu^{5}}{2(\lambda+\mu)^{4}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{11}$
$\displaystyle=\frac{2\lambda^{2}\mu+\lambda\mu^{2}}{(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{20}$
$\displaystyle=\frac{2\lambda^{6}+13\lambda^{5}\mu+31\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+12\lambda^{2}\mu^{4}+2\lambda\mu^{5}}{2\mu(\lambda+\mu)^{4}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{21}$
$\displaystyle=\frac{2\lambda^{4}+5\lambda^{3}\mu+2\lambda^{2}\mu^{2}}{(\lambda+\mu)^{3}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{22}$
$\displaystyle=\frac{\lambda^{2}}{(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)}.$

According to Theorem 4 of [11], the desired value is obtained by summing
$v_{00}$, $v_{10}$ and $v_{20}$. And the desired result follows.

##  Appendix G Proof of Proposition 9

The proof is very similar to that of Proposition 4 and Proposition 8. We
formulate the same SHS approach, but now as we are operating unde FGFS
discipline some transitions will be different, whis are described in Table IV.

We apply (35a) of [11] and we get the following system of equations:

$\displaystyle[v_{00},v_{01},v_{02}]\lambda=$ $\displaystyle
b_{0}\pi_{0}+\mu[v_{11},0,0]$
$\displaystyle[v_{10},v_{11},v_{12}](\lambda+\mu)=$ $\displaystyle
b_{1}\pi_{1}+\lambda[v_{00},0,0]+\mu[v_{21},v_{22},0]$
$\displaystyle[v_{20},v_{21},v_{22}](\lambda+\mu)=$ $\displaystyle
b_{2}\pi_{2}+\lambda[v_{10},v_{11},0]+\lambda[v_{20},v_{22},0].$

$l$ | $\lambda^{(l)}$ | $q\longrightarrow q^{\prime}$ | $x\longrightarrow x^{\prime}=A_{l}x$ | $v_{ql}A_{l}$
---|---|---|---|---
0 | $\lambda$ | $0\longrightarrow 1$ | $[x_{0},0,0]\longrightarrow[x_{0},0,0]$ | $[v_{00},0,0]$
1 | $\mu$ | $1\longrightarrow 0$ | $[x_{0},x_{1},0]\longrightarrow[x_{1},0,0]$ | $[v_{11},0,0]$
2 | $\lambda$ | $1\longrightarrow 2$ | $[x_{0},x_{1},0]\longrightarrow[x_{0},x_{1},0]$ | $[v_{10},v_{11},0]$
3 | $\mu$ | $2\longrightarrow 1$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{1},x_{2},0]$ | $[v_{21},v_{22},0]$
4 | $\lambda$ | $2\longrightarrow 2$ | $[x_{0},x_{1},x_{2}]\longrightarrow[x_{0},x_{2},0]$ | $[v_{20},v_{22},0]$
TABLE IV: The SHS table under consideration in the proof of Proposition 9

The solution of this system of linear equations is

$\displaystyle v_{00}$
$\displaystyle=\frac{3\lambda^{2}\mu^{2}+3\lambda\mu^{3}+\mu^{4}}{\lambda(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{10}$
$\displaystyle=\frac{3\lambda^{4}\mu+11\lambda^{3}\mu^{2}+11\lambda^{2}\mu^{3}+5\lambda\mu^{4}+\mu^{5}}{(\lambda+\mu)^{4}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{11}$
$\displaystyle=\frac{2\lambda^{2}\mu+\lambda\mu^{2}}{(\lambda+\mu)^{2}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{20}$
$\displaystyle=\frac{\lambda^{6}+7\lambda^{5}\mu+17\lambda^{4}\mu^{2}+15\lambda^{3}\mu^{3}+6\lambda^{2}\mu^{4}+\lambda\mu^{5}}{\mu(\lambda+\mu)^{4}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{21}$
$\displaystyle=\frac{2\lambda^{4}+5\lambda^{3}\mu+2\lambda^{2}\mu^{2}}{(\lambda+\mu)^{3}(\lambda^{2}+\mu^{2}+\lambda\mu)}$
$\displaystyle v_{22}$
$\displaystyle=\frac{\lambda^{2}}{(\lambda+\mu)(\lambda^{2}+\mu^{2}+\lambda\mu)}.$

According to Theorem 4 of [11], the desired value is obtained by summing
$v_{00}$, $v_{10}$ and $v_{20}$. And the desired result follows.

##  Appendix H Proof of Proposition 10

We are first going to write the expression of the ratio.

$\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}=\\\
\frac{2\lambda^{6}+12\lambda^{5}\mu+28\lambda^{4}\mu^{2}+30\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}{2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}.$

Since $\lambda>0$ and $\mu>0$ it is easily seen that

$\Delta_{M/M/1/2^{**}-PS}\leq\Delta_{M/M/1/2^{**}-FGFS}.$

Therefore, we know that

$1\leq\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}.$ (23)

Since this ratio is not an increasing function of $\lambda$, we now want to
find the maximum value of it, that way we will have proven Proposition 10. In
order to that, we present the following result.

######  Lemma 5.

The ratio $\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}$ takes
its maximum value at $\rho=2.3943$ and it is

$\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}=1.0731$ (24)

###### Proof.

First we rewrite the ratio by dividing $\mu^{6}$ in the numerator and the
denominator and we get the following

$\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}=\\\
\frac{2\rho^{6}+12\rho^{5}+28\rho^{4}+30\rho^{3}+22\rho^{2}+10\rho+2}{2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2}.$

The derivative of
$\frac{\Delta_{M/M/1/2^{**}-FGFS}}{\Delta_{M/M/1/2^{**}-PS}}$ with respect to
$\rho$ is

$\frac{12\rho^{5}+60\rho^{4}+112\rho^{3}+90\rho^{2}+44\rho+10}{2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2}\\\
-(12\rho^{5}+55\rho^{4}+100\rho^{3}+87\rho^{2}+44\rho+10)\\\
\frac{2\rho^{6}+12\rho^{5}+28\rho^{4}+30\rho^{3}+22\rho^{2}+10\rho+2}{(2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2)^{2}}.$

We set the derivative equal to zero and we get the following result

$(12\rho^{5}+60\rho^{4}+112\rho^{3}+90\rho^{2}+44\rho+10)\\\
(2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2)\\\
-(12\rho^{5}+55\rho^{4}+100\rho^{3}+87\rho^{2}+44\rho+10)\\\
(2\rho^{6}+12\rho^{5}+28\rho^{4}+30\rho^{3}+22\rho^{2}+10\rho+2)=0$

Expanding that expression we get

$-2\rho^{10}-12\rho^{9}-14\rho^{8}+36\rho^{7}+128\rho^{6}\\\
+172\rho^{5}+122\rho^{4}+44\rho^{3}+6\rho^{2}=0$ (25)

Since $\lambda>0$ and $\mu>0$ then $\rho$ must be positive, and the only
postive root of that expression is $\rho=2.3943$. Therefore, this ratio is
larger than one from (23) and it is equal to one when $\rho\to 0$ and
$\rho\to\infty$. Therefore, it has a unique maximum when $\rho$ is positive,
which is achieved for $\rho=2.3943$.We evaluate $\rho=2.3943$ on our ratio and
the desired result follows. ∎

##  Appendix I Proof of Proposition 11

We have

$\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/2^{**}-PS}}=\\\
\frac{3\lambda^{6}+14\lambda^{5}\mu+26\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}{2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}$
(26)

Thus, taking into account that the rhs of (26) tends to 1 when $\lambda\to 0$
and to $\frac{3}{2}$ when $\lambda\to\infty$, the desired result follows if we
show that the rhs of (26) is increasing with $\lambda$, which we proof in the
following result.

######  Lemma 6.

The rhs of (26) is an increasing function of $\lambda$ for all $\mu>0$.

###### Proof.

We compute the derivative of the ratio with respect to $\lambda$ and it
results

$\frac{18\lambda^{5}+70\lambda^{4}\mu+104\lambda^{3}\mu^{2}+87\lambda^{2}\mu^{3}+44\lambda\mu^{4}+10\mu^{5}}{2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}\\\
-(12\lambda^{5}+55\lambda^{4}\mu+100\lambda^{3}\mu^{2}+87\lambda^{2}\mu^{3}+44\lambda\mu^{4}+10\mu^{5})\\\
\frac{(3\lambda^{6}+14\lambda^{5}\mu+26\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6})}{(2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6})^{2}}.$

The above expression is positive if and only if

$(18\lambda^{5}+70\lambda^{4}\mu+104\lambda^{3}\mu^{2}+87\lambda^{2}\mu^{3}+44\lambda\mu^{4}+10\mu^{5})\\\
(2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6})\\\
>(12\lambda^{5}+55\lambda^{4}\mu+100\lambda^{3}\mu^{2}+87\lambda^{2}\mu^{3}+44\lambda\mu^{4}+10\mu^{5})\\\
(3\lambda^{6}+14\lambda^{5}\mu+26\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}),$

which simplifying we obtain that

$5\lambda^{10}\mu+46\lambda^{9}\mu^{2}+151\lambda^{8}\mu^{3}+262\lambda^{7}\mu^{4}+277\lambda^{6}\mu^{5}\\\
+176\lambda^{5}\mu^{6}+60\lambda^{4}\mu^{7}+8\lambda^{3}\mu^{8}>0,$

which is true for all $\mu>0$. And the desired result follows. ∎

##  Appendix J Proof of Proposition 14

We have

$\frac{\Delta_{M/M/1/1}}{\Delta_{M/M/1/2^{*}-PS}}=\\\
\frac{4\lambda^{5}+12\lambda^{4}\mu+18\lambda^{3}\mu^{2}+16\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}$
(27)

Thus, taking into account that the rhs of (27) tends to 1 when $\lambda\to 0$
and to $\frac{4}{3}$ when $\lambda\to\infty$, the desired result follows if we
show that the rhs of (27) is increasing with $\lambda$, which we proof in the
following result.

######  Lemma 7.

The rhs of (27) is an increasing function of $\lambda$ for all $\mu>0$.

###### Proof.

We compute the derivative of the ratio with respect to $\lambda$ and it
results

$\frac{20\lambda^{4}+48\lambda^{3}\mu+54\lambda^{2}\mu^{2}+32\lambda\mu^{3}+8\mu^{4}}{3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}}\\\
-(15\lambda^{4}+44\lambda^{3}\mu+45\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
\frac{(4\lambda^{5}+12\lambda^{4}\mu+18\lambda^{3}\mu^{2}+16\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})}{(3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})^{2}}.$

The above expression is positive if and only if

$(20\lambda^{4}+48\lambda^{3}\mu+54\lambda^{2}\mu^{2}+32\lambda\mu^{3}+8\mu^{4})\\\
(3\lambda^{5}+11\lambda^{4}\mu+15\lambda^{3}\mu^{2}+14\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5})\\\
>(15\lambda^{4}+44\lambda^{3}\mu+45\lambda^{2}\mu^{2}+28\lambda\mu^{3}+8\mu^{4})\\\
(4\lambda^{5}+12\lambda^{4}\mu+18\lambda^{3}\mu^{2}+16\lambda^{2}\mu^{3}+8\lambda\mu^{4}+2\mu^{5}),$

which simplifying we obtain that

$8\lambda^{8}\mu+12\lambda^{7}\mu^{2}+6\lambda^{6}\mu^{3}+16\lambda^{5}\mu^{4}+46\lambda^{4}\mu^{5}\\\
+56\lambda^{3}\mu^{6}+34\lambda^{2}\mu^{7}+8\lambda\mu^{8}>0,$

which is true for all $\mu>0$. And the desired result follows. ∎

##  Appendix K Proof of Proposition 15

We have the following ratio,

$\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/1}}=\\\
\frac{5\lambda^{4}+9\lambda^{3}\mu+8\lambda^{2}\mu^{2}+6\lambda^{2}\mu^{3}+2\mu^{4}}{4\lambda^{4}+8\lambda^{3}\mu+10\lambda^{2}\mu^{2}+6\lambda^{2}\mu^{3}+2\mu^{4}}$
(28)

When $\lambda\in(0,\mu]$, then we have that
$\Delta_{M/M/1/1}\geq\Delta_{M/M/1/2-PS}$ and when $\lambda\in[\mu,\infty)$,
we have $\Delta_{M/M/1/1}\leq\Delta_{M/M/1/2-PS}$. So we will study each case
separately.

In the case of $\lambda\in(0,\mu]$, we want to find the minimum value of the
ratio.

######  Lemma 8.

If $\lambda\in(0,\mu]$, then we have the following

$0.9641\leq\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/1}}\leq 1$ (29)

###### Proof.

First we rewrite the ratio by dividing $\mu^{4}$ in the numerator and the
denominator. So we get the following

$\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/1}}=\frac{5\rho^{4}+9\rho^{3}+8\rho^{2}+6\rho^{2}+2}{4\rho^{4}+8\rho^{3}+10\rho^{2}+6\rho^{2}+2}.$
(30)

The derivative of the ratio with respect to $\rho$ is

$\frac{20\rho^{3}+27\rho^{2}+16\rho+6}{4\rho^{4}+8\rho^{3}+10\rho^{2}+6\rho^{2}+2}\\\
-(16\rho^{3}+24\rho^{2}+20\rho+6)\frac{5\rho^{4}+9\rho^{3}+8\rho^{2}+6\rho^{2}+2}{(4\rho^{4}+8\rho^{3}+10\rho^{2}+6\rho^{2}+2)^{2}}.$

We set the derivative equal to zero and we get the following result

$(20\rho^{3}+27\rho^{2}+16\rho+6)(4\rho^{4}+8\rho^{3}+10\rho^{2}+6\rho^{2}+2)\\\
-(16\rho^{3}+24\rho^{2}+20\rho+6)(5\rho^{4}+9\rho^{3}+8\rho^{2}+6\rho^{2}+2)=0$

Expanding that expression we get

$4\rho^{6}+36\rho^{5}+44\rho^{4}+20\rho^{3}-6\rho^{2}-8\rho=0$ (31)

Since $\lambda>0$ and $\mu>0$ then $\rho$ must be positive, and the only
postive root of that expression is $\rho=0.4697$. Besides,

$\frac{5\rho^{4}+9\rho^{3}+8\rho^{2}+6\rho^{2}+2}{4\rho^{4}+8\rho^{3}+10\rho^{2}+6\rho^{2}+2}$

is clearly smaller or equal than one and equal to one when $\rho\to 0$ and
$\rho\to\infty$. Therefore, since we have shown that it has a single local
critical point, it is a minimum. We evaluate $\rho=0.4697$ on our ratio and
the desired result follows. ∎

We now focus in the case of $\lambda\in[\mu,\infty)$. In this case, we have
$\rho=\frac{\lambda}{\mu}$ where $\lambda>\mu$. Knowing that, it is clearly
visible that the expression (31) is always positive. So (31) is an increasing
function on $\lambda$. Then as the ratio tends to $\frac{5}{4}$ when
$\lambda\to\infty$, we have the following result.

$1\leq\frac{\Delta_{M/M/1/2-PS}}{\Delta_{M/M/1/1}}\leq\frac{5}{4}.$ (32)

Taking into account (29) and (32) the desired result is achieved.

##  Appendix L Proof of Proposition 17

We first going to write the expression of the ratio.

$\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/1^{*}}}=\\\
\frac{2\lambda^{6}+11\lambda^{5}\mu+25\lambda^{4}\mu^{2}+29\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}{2\lambda^{6}+10\lambda^{5}\mu+22\lambda^{4}\mu^{2}+28\lambda^{3}\mu^{3}+22\lambda^{2}\mu^{4}+10\lambda\mu^{5}+2\mu^{6}}.$

Since $\lambda>$0 and $\mu>$0 it is easily seen that
$\Delta_{M/M/1/1^{*}}\leq\Delta_{M/M/1/2^{*}-PS}$. So we know that

$1\leq\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/1^{*}}}.$ (33)

Since this ratio is not an increasing function of $\lambda$, we now want to
find the maximum value of it, that way we will have proven Proposition 17. In
order to that, we present the following result.

######  Lemma 9.

The ratio $\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/1^{*}}}$ takes its
maximum value at $\rho=2.3943$ and it is

$\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/1^{*}}}=1.0788$ (34)

###### Proof.

First we rewrite the ratio by dividing $\mu^{6}$ in the numerator and the
denominator. So we get the following

$\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/1^{*}}}=\\\
\frac{2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2}{2\rho^{6}+10\rho^{5}+22\rho^{4}+28\rho^{3}+22\rho^{2}+10\rho+2}.$

The derivative of $\frac{\Delta_{M/M/1/2^{*}-PS}}{\Delta_{M/M/1/1^{*}}}$ with
respect to $\rho$ is

$\frac{12\rho^{5}+55\rho^{4}+100\rho^{3}+87\rho^{2}+44\rho+10}{2\rho^{6}+10\rho^{5}+22\rho^{4}+28\rho^{3}+22\rho^{2}+10\rho+2}\\\
-(12\rho^{5}+50\rho^{4}+88\rho^{3}+84\rho^{2}+44\rho+10)\\\
\frac{2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2}{(2\rho^{6}+10\rho^{5}+22\rho^{4}+28\rho^{3}+22\rho^{2}+10\rho+2)^{2}}.$

We set the derivative equal to zero and we get the following result

$(12\rho^{5}+55\rho^{4}+100\rho^{3}+87\rho^{2}+44\rho+10)\\\
(2\rho^{6}+10\rho^{5}+22\rho^{4}+28\rho^{3}+22\rho^{2}+10\rho+2)\\\
-(12\rho^{5}+50\rho^{4}+88\rho^{3}+84\rho^{2}+44\rho+10)\\\
(2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2)=0$

Expanding that expression we get

$-2\rho^{10}-12\rho^{9}-14\rho^{8}+36\rho^{7}+128\rho^{6}\\\
+172\rho^{5}+122\rho^{4}+44\rho^{3}+6\rho^{2}=0$ (35)

Since $\lambda>0$ and $\mu>0$ then $\rho$ must be positive, and the only
positive root of that expression is $\rho=2.3943$. Besides, we have that

$\frac{2\rho^{6}+11\rho^{5}+25\rho^{4}+29\rho^{3}+22\rho^{2}+10\rho+2}{2\rho^{6}+10\rho^{5}+22\rho^{4}+28\rho^{3}+22\rho^{2}+10\rho+2},$

is clearly larger than one when $\rho\in(0,\infty)$ and tends to one when
$\rho\to 0$ and $\rho\to\infty$. Therefore, this ratio has a unique maximum
when $\rho\in(0,\infty)$. We evaluate $\rho=2.3943$ on our ratio and the
desired result follows. ∎

##  Appendix M Proof of Lemma 1.

.

We also model the system using the SHS methodology. In this case, the Markov
chain we consider is $\mathcal{Q}=\\{0,1,2,\dots\\}$, which is a birth-death
process with birth rate $\lambda$ and death rate $\mu$. For this Markov chain,
the stationary distribution is clearly $\pi_{i}=(1-\rho)\rho^{i}.$ For the
continuous state, we will only focus on the transitions of state zero. Indeed,
the idea of the proof is to apply Theorem 4 of [11] as follows

$\Delta_{M/M/1-PS}=\sum_{q\in\mathcal{Q}}v_{q0}>v_{00}.$

Thus, in the SHS table under consideration, we only show the transitions
related to state zero as well as the values of the continuous state of state
zero. This is represented in Table V.

$l$ | $\lambda^{(l)}$ | $q\longrightarrow q^{\prime}$ | $x\longrightarrow x^{\prime}=A_{l}x$ | $v_{ql}A_{l}$
---|---|---|---|---
0 | $\lambda$ | $0\longrightarrow 1$ | $[x_{0},...]\longrightarrow[x_{0},...]$ | $[v_{00},...]$
1 | $\mu$ | $1\longrightarrow 0$ | $[x_{0},...]\longrightarrow[x_{1},...]$ | $[v_{11},...]$
TABLE V: The SHS table under consideration in the proof of Lemma 1

We omit the explanation of the transitions represented in Table V because they
coincide with the transitions 0 and 1 of the SHS table of Proposition 1. Now,
we apply (35a) of [11] to the SHS of Table V and we get

$\lambda v_{00}=\pi_{0}+v_{11}\mu>\pi_{0}\iff
v_{00}=\frac{\mu-\lambda}{\lambda\mu}.$

And the desired result follows.

##  Appendix N Proof of Proposition 14.

.

Under Conjecture 20, we know that $C(\rho)\leq\frac{\rho^{2}}{1-\rho}$ and
$C(\rho)\geq\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}$, therefore

$\Delta_{M/M/1-FGFS}\leq\Delta_{M/M/1-PS}\leq\frac{1}{\mu}\left(1+\frac{1}{\rho}+\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}\right).$

Therefore, the proof ends if we show that
$\frac{\Delta_{M/M/1-FGFS}}{\Delta_{M/M/1-PS}}$ is unbounded from above. That
is,

$\displaystyle\frac{1+\frac{1}{\rho}+\frac{\rho^{2}}{1-\rho}}{1+\frac{1}{\rho}+C(\rho)}\geq\frac{1+\frac{1}{\rho}+\frac{\rho^{2}}{1-\rho}}{1+\frac{1}{\rho}+\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}}=1+\frac{\frac{\rho^{2}}{1-\rho}-\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}}{1+\frac{1}{\rho}+\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}}$

and the last expression tends to infinity when $\rho\to 1$ since

$\frac{\frac{\rho^{2}}{1-\rho}-\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}}{1+\frac{1}{\rho}+\frac{0.75\rho}{(1-\rho)^{\frac{1}{2}}}}=\frac{\frac{\rho^{2}}{(1-\rho)^{\frac{1}{2}}}-0.75\rho}{\left(1+\frac{1}{\rho}\right)(1-\rho)^{\frac{1}{2}}+0.75\rho},$

and the numerator tends to infinity and the denominator to 0.75 when $\rho\to
1$.

## References

  * [1] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _2012 Proceedings IEEE INFOCOM_. IEEE, 2012, pp. 2731–2735.
  * [2] ——, “Status updates through queues,” in _in Conf. on Information Sciences and Systems (CISS)_. IEEE, 2012\.
  * [3] R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in _2012 IEEE International Symposium on Information Theory Proceedings_. IEEE, 2012, pp. 2666–2670.
  * [4] C. Kam, S. Kompella, G. D. Nguyen, and A. Ephremides, “Effect of message transmission path diversity on status age,” _IEEE Trans. Info. Theory_ , vol. 62, no. 3, pp. 1360–1374, 2016.
  * [5] M. Costa, M. Codreanu, and A. Ephremides, “Age of information with packet management,” in _in Proc. IEEE Int’l. Symp. Info. Theory (ISIT)_. IEEE, 2014, pp. 1583–1587.
  * [6] ——, “On the age of information in status update systems with packet management,” _IEEE Transactions on Information Theory_ , vol. 62, no. 4, pp. 1897–1910, 2016.
  * [7] A. Soysal and S. Ulukus, “Age of information in g/g/1/1 systems: Age expressions, bounds, special cases, and optimization,” _IEEE Trans. Info. Theory_ , vol. 67, no. 11, pp. 7477–7489, 2021.
  * [8] Z. Chen, D. Deng, C. She, Y. Jia, L. Liang, S. Fang, M. Wang, and Y. Li, “Age of information: The multi-stream m/g/1/1 non-preemptive system,” _IEEE Trans. Commun._ , vol. 70, no. 4, pp. 2328–2341, 2022.
  * [9] E. Najm and E. Telatar, “Status updates in a multi-stream m/g/1/1 preemptive queue,” in _in IEEE Conference on Computer Communications (INFOCOM) Workshops_. IEEE, 2018, pp. 124–129.
  * [10] R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in _2012 IEEE International Symposium on Information Theory Proceedings_. IEEE, 2012, pp. 2666–2670.
  * [11] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” _IEEE Transactions on Information Theory_ , vol. 65, no. 3, pp. 1807–1827, 2018.
  * [12] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Optimizing data freshness, throughput, and delay in multi-server information-update systems,” in _2016 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2016, pp. 2569–2573.
  * [13] R. D. Yates, “Status updates through networks of parallel servers,” in _In IEEE International Symposium on Information Theory Proceedings_. IEEE, 2018.
  * [14] J. Doncel and M. Assaad, “Age of information in a decentralized network of parallel queues with routing and packets losses,” _IEEE/KICS Journal of Communications and Networks_ , vol. 24, no. 1, pp. 17–36, 2022.
  * [15] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” _IEEE/ACM Transactions on Networking_ , vol. 26, no. 6, pp. 2637–2650, 2018\.
  * [16] A. Maatouk, Y. Sun, A. Ephremides, and M. Assaad, “Status updates with priorities: Lexicographic optimality,” in _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. IEEE, 2020, pp. 1–8.
  * [17] Y. Sun, E. Uysal-Biyikoglu, and S. Kompella, “Age-optimal updates of multiple information flows,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2018, pp. 136–141.
  * [18] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Age-optimal information updates in multihop networks,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 576–580.
  * [19] ——, “The age of information in multihop networks,” _IEEE/ACM Transactions on Networking_ , vol. 27, no. 3, pp. 1248–1257, 2019.
  * [20] Y.Sun, E.Uysal-Biyikoglu, R.D.Yates, C.E.Koksal, and N.B.Shroff, “Update or wait: How to keep your data fresh.” IEEE, 2016.
  * [21] ——, “Update or wait: How to keep your data fresh,” _IEEE Transactions on Information Theory_ , vol. 63, no. 11, pp. 7492–7508, 2017.
  * [22] Y.-P. Hsu, E. Modiano, and L. Duan, “Age of information: Design and analysis of optimal scheduling algorithms,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 561–565.
  * [23] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “On the optimality of the whittle’s index policy for minimizing the age of information,” _IEEE Transactions on Wireless Communications_ , 2020.
  * [24] S. Kriouile, M. Assaad, and A. Maatouk, “On the global optimality of whittle’s index policy for minimizing the age of information,” _IEEE Transactions on Information Theory_ , vol. 68, no. 1, pp. 572–600, 2022.
  * [25] A. Arafa, J. Yang, and S. Ulukus, “Age-minimal online policies for energy harvesting sensors with random battery recharges,” in _in Proc. of IEEE International Conference on Communications (ICC)_. IEEE, 2018.
  * [26] A.Arafa, J.Yang, S.Ulukus, and H.V.Poor, “Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies,” _IEEE Trans. Info. Theory_ , vol. 66, no. 1, pp. 534–556, 2019.
  * [27] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in _In IEEE International Symposium on Information Theory Proceedings_. IEEE, 2015, pp. 3008–3012.
  * [28] B. T. Bacinoglu, Y. Sun, E. Uysal-Bivikoglu, and V. Mutlu, “Achieving the age-energy tradeoff with a finite-battery energy harvesting source,” in _In IEEE International Symposium on Information Theory Proceedings_. IEEE, 2018, pp. 876–880.
  * [29] B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, “Age of information under energy replenishment constraints,” in _in Proc. Info. Theory and Appl. (ITA) Workshop_. IEEE, 2015.
  * [30] F. C. et al, “Query age of information: Freshness in pull-based communication,” _IEEE Transactions on Communications_ , vol. 70, no. 3, pp. 1606–1622, 2022.
  * [31] J. Zhong, R. D. Yates, and E. Soljanin, “Two freshness metrics for local cache refresh,” in _IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1924–1928.
  * [32] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 5, pp. 2215–2228, 2020.
  * [33] G. Stamatakis and A. T. N. Pappas, “Control of status updates for energy harvesting devices that monitor processes with alarms,” in _In Proc. of IEEE Globecom Workshops (GC Wkshps)_ , 2019.
  * [34] C. Kam, S. Kompella, G. D. Nguyen, J. E. Wieselthier, and A. Ephremides, “Towards an effective age of information: Remote estimation of a markov source,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2018, pp. 367–372.
  * [35] R. D. Yates, “The age of gossip in networks,” in _In IEEE International Symposium on Information Theory Proceedings_. IEEE, 2021, pp. 2984–2989.
  * [36] Y. Sun and B. Cyr, “Sampling for data freshness optimization: Non-linear age functions,” _IEEE/KICS Journal of Communications and Networks_ , vol. 21, no. 3, pp. 204–219, 2019.
  * [37] E. Uysal and et al, “Semantic communications in networked systems: A data significance perspective,” _IEEE Network_ , vol. 36, no. 4, pp. 233–240, 2022.
  * [38] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “Age and value of information: Non-linear age case,” in _IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2019, pp. 326–330.
  * [39] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: an enabler of semantics-empowered communication,” _arXiv preprint arXiv:2012.13214_ , 2020.
  * [40] S. Kriouile and M. Assaad, “Minimizing the age of incorrect information for real-time tracking of markov remote sources,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 2978–2983.
  * [41] Y. Chen and A. Ephremides, “Scheduling to minimize age of incorrect information with imperfect channel state information,” _Entropy_ , vol. 23, no. 12, 2021.
  * [42] M. Ayik, E. T. Ceran, and E. Uysal, “Optimization of aoii and qaoii in multi-user links,” in _available on arviv, arXiv:2305.00191_ , 2023.
  * [43] N. Pappas, M. Abd-Elmagid, B. Zhou, W. Saad, and H. Dhillon, _Age of Information: Foundations and Applications_. Cambridge University Press, 2023.
  * [44] Y. Sun, I. Kadota, R. Talak, and E. Modiano, _Age of Information: A New Metric for Information Freshness_. Synthesis Lectures on Communication Networks, Morgan and Claypool Publishers, 2019\.
  * [45] R. Yates, Y. Sun, D. Brown, S. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1183–1210, 2021.
  * [46] L. Kleinrock, “Theory, volume 1, queueing systems,” 1975.
  * [47] S. F. Yashkov, “Processor-sharing queues: Some progress in analysis,” _Queueing systems_ , vol. 2, pp. 1–17, 1987.
  * [48] F. Kelly, “Stochastic networks and reversibility, wiley, new york,” 1979.

Beñat Gandarias obtained the Degree in Mathematics from the University of the
Basque Country, UPV/EHU, in 2023. He is currently a research staff in the
Mathematics department of the UPV/EHU. His research interests cover the
analysis of queueing disciplines from the Age of Information perspective.
---
Josu Doncel obtained from the University of the Basque Country (UPV/EHU) the
Industrial Engineering degree in 2007, the Mathematics degree in 2010 and, in
2011, the Master degree in Applied Mathematics and Statistics. I received in
2015 the PhD degree from Université de Toulouse (France). He is currently
associate professor in the Mathematics department of the UPV/EHU. He has
previously held research positions at LAAS-CNRS (France), INRIA Grenoble
(France) and BCAM-Basque Center for Applied Mathematics (Spain), teaching
positions at ENSIMAG (France), INSA-Toulouse (France) and IUT-Blagnac (France)
and invited researcher positions at Laboratory of Signals and Systems of
CentraleSupelec (France), at Inria Paris (France) and at Laboratory David
(France). His research interests are the modeling, optimization and
performance evaluation of distributed stochastic systems such as
telecommunications and energy networks.
---
Mohamad Assaad received the M.Sc and PhD degrees, both in telecommunications,
from Telecom ParisTech, Paris, France, in 2002 and 2006, respectively. Since
2006, he has been with the Telecommunications Department at CentraleSupelec,
where he is currently a professor. He is also a researcher at the Laboratoire
des Signaux et Systemes (L2S, CNRS) and holds the 5G Chair. He has co-authored
1 book and more than 120 publications in journals and conference proceedings
and has served as TPC member or TPC co-chair for toptier international
conferences, including TPC co-chair for IEEE WCNC 21, IEEE Globecom 20 Mobile
and Wireless networks Symposium Cochair, etc. He is an Editor for the IEEE
Wireless Communications Letters and the Journal of Communications and
Information Networks. He served also as a guest co-editor for a special issue
of the IEEE transactions on Network Science and Engineering. He has given in
the past successful tutorials on several topics related to 5G systems, and Age
of Information at various conferences including IEEE ISWCS 15, IEEE WCNC 16,
and IEEE ICC 21 conferences. His research interests include 5G and beyond
systems, fundamental networking aspects of wireless systems, Age of
Information, resource optimization and Machine Learning in wireless networks.
---