Your browser does not support the NLM PubReader view.
Go to this page to see a list of supporting browsers.

On the Age of Information of Processor Sharing Systems

Be˜ nat Gandarias , Josu Doncel and Mohamad Assaad

Article Information

Be˜ nat Gandarias, University of the Basque Country, UPV/EHU, benat.gandarias@ehu.eus

Josu Doncel, University of the Basque Country, UPV/EHU, josu.doncel@ehu.eus

Mohamad Assaad, Laboratoire des Signaux et Syste`mes (L2S), CentraleSu- pelec, University of Paris-Saclay., mohamad.assaad@centralesupelec.fr

Received: June 27 2023

Accepted: September 25 2023

Published (Electronic): October 31 2023

Abstract

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. In the PS queueing discipline, all the updates are served simultaneously and, therefore, none of of the jobs wait in the queue to get service. 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.

Keywords: 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 (AAoI), peak AoI, etc. In particular, the AAoI has received a lot of attention and has been evaluated in various continuous and discrete time network models. In [1]–[4], it was shown that the computation of the AAoI 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 AAoI 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 AAoI 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, AAoI 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 AAoI 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]–[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]–[17], multihop networks [18], [19], etc. Interestingly, it has been shown in [20], 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 multiuser networks, several Age-based scheduling solutions have also been developed, e.g., [15], [21], [22]. A Whittle index based scheduling policy has been developed in [15], [21]. Such a Whittle index based policy has been proved to be asymptotically optimal in some cases [22], [23]. Furthermore, there have been studies on energy-constrained updating, e.g., in energy harvesting context [24]–[28]. It is worth mentioning that in addition to the above AoI metrics, there is an increasing interest recently in developing beyond-age metrics [29]–[35], for example to capture the semantic of information [36] such as value of information [37], age of incorrect of information (AoII) [31], [38]–[40], query age of incorrect information (QAoII) [41], etc. For more recent surveys of existing work the reader can refer to [42]–[44].

In this paper, we focus on the AAoI metric. We consider a single source single destination queuing model under processor sharing (PS) discipline. Under the PS 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 [45], e.g., [46], [47], 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 AAoI 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 first generated first served (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 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.

Fig. 1.
A monitoring system example.

We assume that packet generation times at the source follow a Poisson process of rate λ and that the transmission channel is a single server queue with exponential service times of rate μ. The load of the system is [TeX:] $$\rho=\lambda / \mu \text {. }$$ 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 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 [TeX:] $$\mu / n.$$

We consider the AoI as the metric of performance of the system. The AoI 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 [TeX:] $$t_i$$ is the generation time of the ith packet and L(t) is the index of the last successfully delivered packet before time t, the AoI at time t is defined as [TeX:] $$\Delta(t)=t-t_{L(t)}.$$

Our focus will be on the AAoI of divers queueing models, which we denote by Δ 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 [TeX:] $$\Delta_{M / M / 1 / 2-P S}.$$

III. THE M/M/1/2 QUEUE WITH AND WITHOUT PREEMPTION

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 μ, but when there are two packets in the queue, both are served at rate [TeX:] $$\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

(1)
[TeX:] $$\Delta_{M / M / 1 / 2-P S}=\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)\left(\lambda^2+\lambda \mu+\mu^2\right)} .$$

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

(2)
[TeX:] $$\Delta_{M / M / 1 / 2-F G F S}=\frac{3 \lambda^4+5 \lambda^3 \mu+4 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4}{\lambda \mu(\lambda+\mu)\left(\lambda^2+\mu^2+\lambda \mu\right)}.$$

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

(3)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2-F G F S}}{\Delta_{M / M / 1 / 2-P S}} \leq 1.2 .$$

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.

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 AoI 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.

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

(4)
[TeX:] $$\begin{aligned} & \Delta_{M / M / 1 / 2^*-P S}= \\ & \quad \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\left(\lambda^2+\mu^2+\lambda \mu\right)} . \end{aligned}$$

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

(5)
[TeX:] $$\begin{aligned} & \Delta_{M / M / 1 / 2^*-F G F S}= \\ & \quad \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\left(\lambda^2+\mu^2+\lambda \mu\right)} . \end{aligned}$$

We focus on the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2^*-F G F S}}{\Delta_{M / M / 1 / 2^*-P S}} .$$ 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

(6)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2^*-F G F S}}{\Delta_{M / M / 1 / 2^*-P S}} \leq \frac{4}{3}.$$

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 [TeX:] $$\Delta_{M / M / 1 / 2 *-F G F S}$$ is, at most, 4/3 times worse than [TeX:] $$\Delta_{M / M / 1 / 2^*-P S}.$$

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

(7)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 2^*-P S}} \leq \frac{5}{3}.$$

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.

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

(8)
[TeX:] $$\begin{aligned} & \Delta_{M / M / 1 / 2^{* *}-P S}= \\ & \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\left(\lambda^2+\mu^2+\lambda \mu\right)} . \\ & \end{aligned}$$

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

(9)
[TeX:] $$\begin{aligned} & \Delta_{M / M / 1 / 2^{* *}-F G F S}= \\ & \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\left(\lambda^2+\mu^2+\lambda \mu\right)} . \end{aligned}$$

We focus on the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}} .$$ 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

(10)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}} \leq 1.0731.$$

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 [TeX:] $$\Delta_{M / M / 1 / 2^{* *}-F G F S}$$ is, at most, 1.0731 worse than [TeX:] $$\Delta_{M / M / 1 / 2^{* *}-P S}.$$

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

(11)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 2^{* *}-P S}} \leq \frac{3}{2}.$$

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 [TeX:] $$\Delta_{M / M / 1 / 2^*-P S}$$ is, at most, 3/2 worse than [TeX:] $$\Delta_{M / M / 1 / 2^{* *}-P S}.$$ Moreover, from Proposition 5 and Proposition 9 we derive the following result.

Corollary 1. We have that

(12)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 2^{* *}-P S}} \leq \frac{5}{2}.$$

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.

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:

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

We now focus on the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 1}}{\Delta_{M / M / 1 / 2^*-P S}}.$$ 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

(14)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 1}}{\Delta_{M / M / 1 / 2^*-P S}} \leq \frac{4}{3}.$$

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 [TeX:] $$\Delta_{M / M / 1 / 1}$$ will be, at most, 2 times worse than [TeX:] $$\Delta_{M / M / 1 / 2^{* *}-P S} \text {, }$$

[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 1}}{\Delta_{M / M / 1 / 2^{* *}-P S}} \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

(15)
[TeX:] $$0.9641 \leq \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 1}} \leq \frac{5}{4}.$$

From this result, we conclude that, when [TeX:] $$\lambda \in[0, \mu],$$ then we have that [TeX:] $$\Delta_{M / M / 1 / 1} \geq \Delta_{M / M / 1 / 2-P S},$$ whereas when [TeX:] $$\lambda \in[\mu, \infty),$$ we have that [TeX:] $$\Delta_{M / M / 1 / 2-P S} \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, [TeX:] $$1 / 0.9641 \approx 1.0372$$ times better than the AAoI of the M/M/1/1 queue.

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 [TeX:] $$\Delta_{M / M / 1 / 1^*}$$ is

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

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

(17)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2^{* *}-P S}}{\Delta_{M / M / 1 / 1^*}} \leq 1.0788.$$

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 [TeX:] $$\rho\lt 1$$ to ensure stability. Our first result of this section consists of establishing a lower-bound of [TeX:] $$\Delta_{M / M / 1-P S}.$$ Its proof is available in Appendix M.

Lemma 1.

[TeX:] $$\Delta_{M / M / 1-P S}\gt \frac{\mu-\lambda}{\lambda \mu} .$$

It is shown in [1] that

(18)
[TeX:] $$\Delta_{M / M / 1-F G F S}=\frac{1}{\mu}\left(1+\frac{1}{\rho}+\frac{\rho^2}{1-\rho}\right),$$

which is clearly unbounded from above when [TeX:] $$\lambda \rightarrow 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 [TeX:] $$\lambda \rightarrow 0,$$ [TeX:] $$\Delta_{M / M / 1-P S}$$ is unbounded from above.

Proof. From Lemma 1, the desired result follows noting that, when [TeX:] $$\lambda \rightarrow 0,(\mu-\lambda) / \lambda \mu$$ tends to infinity.

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

Conjecture 1.

(19)
[TeX:] $$\Delta_{M / M / 1-P S}=\frac{1}{\mu}\left(\frac{1}{\rho}+1+C(\rho)\right),$$

where [TeX:] $$\lim _{\rho \rightarrow 0} C(\rho)=0, \lim _{\rho \rightarrow 1} C(\rho)=+\infty$$ and [TeX:] $$0 \leq C(\rho) \leq \frac{\rho^2}{1-\rho} \text { for all } \rho \in(0,1).$$ Moreover, when ρ is large enough,

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

We remark that, if Conjecture 1 holds, then it follows that, when λ is large enough,

[TeX:] $$\Delta_{M / M / 1-P S} \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 [TeX:] $$\rho \rightarrow 1,$$ Therefore, we conclude that, if Conjecture 1 holds, when [TeX:] $$\rho \rightarrow 1,$$ [TeX:] $$\Delta_{M / M / 1-P S}$$ tends to infinity.

We know from (18) that, when [TeX:] $$\rho \rightarrow 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 1 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 [TeX:] $$\frac{\Delta_{M / M / 1-F G F S}}{\Delta_{M / M / 1-P S}} .$$ The proof is available in Appendix N.

Proposition 14. If Conjecture 1 holds, then

[TeX:] $$1 \leq \frac{\Delta_{M / M / 1-F G F S}}{\Delta_{M / M / 1-P S}} \leq+\infty.$$

Fig. 2.
Comparison of the AAoI of source 1 in a M/M/1 queue with divers queueing disciplines when [TeX:] $$\lambda_2$$ changes from 0.001 to 0.05 and [TeX:] $$\lambda_1=0.1.$$

V. MULTIPLE SOURCES

In this section we will expand our analysis from singlesource 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 [TeX:] $$\lambda_1$$ and of source 2 is [TeX:] $$\lambda_2$$. The service rate is exponentially distributed with rate μ for the updates from any source.

We aim to analyze the impact of [TeX:] $$\lambda_2$$ on the AAoI of the updates of source one under the different queueing disciplines. In our numerical analysis we consider that μ = 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 Fig. 2, we consider that [TeX:] $$\lambda_1=0.1$$ and [TeX:] $$\lambda_2$$ varying from 0.001 to 0.05. We observe that the influence of [TeX:] $$\lambda_2$$ is very similar for PS and FGFS (and that PS outperforms FGFS for all [TeX:] $$\lambda_2$$), but the AAoI of the M/M/1/1* queue increases dramatically with [TeX:] $$\lambda_2$$. Indeed, when [TeX:] $$\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 [TeX:] $$\lambda_2$$ grows large much faster than FGFS and PS. Therefore, we conclude that, when [TeX:] $$\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.

We now aim to study whether the conclusions obtained for [TeX:] $$\lambda_1$$ small extend to instances where [TeX:] $$\lambda_1$$ is large. To this end, we consider [TeX:] $$\lambda_1=5$$ and [TeX:] $$\lambda_2$$ varying from [TeX:] $$0.001 \text { to } 10^3 \text {. }$$ In Fig. 3, we represent the values of the AAoI we have obtained in our numerical analysis. We observe that the influence of [TeX:] $$\lambda_2$$ is again very similar for PS and FGFS and when [TeX:] $$\lambda_2$$ is close to zero the AAoI of the M/M/1/1* queue is the smallest one. However, when [TeX:] $$\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 [TeX:] $$\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.

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 μ = 1 in these experiments and same queueing disciplines as in Figs. 2 and 3. In Fig. 5, we set [TeX:] $$\lambda_1=0.1$$ and we plot the AAoI of both sources when [TeX:] $$\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 Fig. 4, we consider [TeX:] $$\lambda_1=5$$ to analyze whether the aforementioned conclusions extend to the instance where [TeX:] $$\lambda_1$$ is large. We observe that, when [TeX:] $$\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 [TeX:] $$\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.

Fig. 3.
Comparison of the AAoI of the source 1 in a M/M/1 queue with divers queueing disciplines when [TeX:] $$\lambda_2$$ changes from [TeX:] $$0.001 \text { to } 10^3 \text { and } \lambda_1=5 \text {. }$$
Fig. 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 [TeX:] $$\lambda_2$$ changes from 0.001 to 30 and [TeX:] $$0\lambda_1=0.1 \text {. }$$
Fig. 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 [TeX:] $$\lambda_2$$ changes from [TeX:] $$0.001 \text { to } 10^3 \text { and } \lambda_1=5 \text {. }$$

VI. CONCLUSIONS

In this paper, we investigated the average AoI in a system composed of sources sending status updates to a monitor through a 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 Fig. 6, where each state represents the number of packets in the queue; the continuous state is a vector [TeX:] $$\mathbf{x}(t)=\left[x_0(t) x_1(t) x_2(t)\right]$$ where [TeX:] $$x_0(t)$$ is the AoI at time t and [TeX:] $$x_i(t)$$ is the age of the ith packet in the queue. We also define [TeX:] $$b_0=[1,0,0], b_1=[1,1,0] \text { 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 Fig. 6.

Fig. 6.
The Markov chain under consideration in the proof of Proposition 1.

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

[TeX:] $$\pi_i=\frac{\rho^i}{1+\rho+\rho^2}, i=0,1,2.$$

We now describe each of the transitions of Table I.

TABLE I
THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 1.

l = 0. A new packet arrives when the queue is empty. This occurs with rate λ. 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., [TeX:] $$x_1^{\prime}=0.$$

l = 1. There is one packet in the queue and it is served, which occurs with rate μ. For this case, the age of the monitor is replace by the age of the packet in service, i.e., [TeX:] $$x_0^{\prime}=x_1$$

l = 2. A new packet arrives when there is another packet in the queue. This occurs with rate λ. 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 [TeX:] $$\mu/2.$$ For this case, the age of the monitor changes to the age of the packet that has been served, i.e., [TeX:] $$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, [TeX:] $$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 [TeX:] $$\mu/2.$$ For this case, the age of the monitor is replaced by the age of the last arrived packet, i.e., [TeX:] $$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., [TeX:] $$x_1^{\prime}=x_2.$$

l = 5. There are two packets in the system and a new packet arrives. This occurs with rate λ. 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.

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

[TeX:] $$\begin{aligned} {\left[v_{00}, v_{01}, v_{02}\right] \lambda=} & b_0 \pi_0+\mu\left[v_{11}, 0,0\right], \\ {\left[v_{10}, v_{11}, v_{12}\right](\lambda+\mu)=} & b_1 \pi_1+\lambda\left[v_{00}, 0,0\right]+\frac{\mu}{2}\left[v_{21}, v_{22}, 0\right] \\ & +\frac{\mu}{2}\left[v_{22}, v_{22}, 0\right], \\ {\left[v_{20}, v_{21}, v_{22}\right](\lambda+\mu)=} & b_2 \pi_2+\lambda\left[v_{10}, v_{11}, 0\right]+\lambda\left[v_{20}, v_{21}, v_{22}\right] . \end{aligned}$$

From [11, Th. 4], 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 [TeX:] $$v_{00}+v_{10}+v_{20}.$$

We solve the above system of equations and we get

[TeX:] $$\begin{aligned} & v_{00}=\frac{\mu(\lambda+\mu)}{\lambda\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{10}=\frac{3 \lambda^2+2 \mu^2+4 \lambda \mu}{2(\lambda+\mu)\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{11}=\frac{\lambda}{\lambda^2+\lambda \mu+\mu^2}, \\ & v_{20}=\frac{5 \lambda^3+6 \lambda^2 \mu+2 \lambda \mu^2}{2 \mu(\lambda+\mu)\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{21}=\frac{2 \lambda^2}{\mu\left(\lambda^2+\lambda \mu+\mu^2\right)}, \\ & v_{22}=\frac{\lambda^2}{\mu\left(\lambda^2+\lambda \mu+\mu^2\right)} . \end{aligned}$$

Therefore,

[TeX:] $$\begin{aligned} \Delta_{M / M / 1 / 2-P S} & =v_{00}+v_{10}+v_{20} \\ & =\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)\left(\lambda^2+\mu^2+\lambda \mu\right)}, \end{aligned}$$

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

APPENDIX B

PROOF OF PROPOSITION 2

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

[TeX:] $$\frac{3 \lambda^4+5 \lambda^3 \mu+4 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4}{\lambda \mu(\lambda+\mu)\left(\lambda^2+\lambda \mu+\mu^2\right)}.$$

As a result,

(21)
[TeX:] $$\frac{\Delta_{M / M / 1 / 2-F G F S}}{\Delta_{M / M / 1 / 2-P S}}=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} .$$

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

Lemma 2. The rhs of (21) is an increasing function of λ for all μ > 0.

Proof. We compute the derivative of [TeX:] $$\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 λ and it results

[TeX:] $$\begin{aligned} & \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} \\ & -\left(20 \lambda^3+27 \lambda^2 \mu+16 \lambda \mu^2+6 \mu^3\right) \\ & \times \frac{\left(3 \lambda^4+5 \lambda^3 \mu+4 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4\right)}{\left(5 \lambda^4+9 \lambda^3 \mu+8 \lambda^2 \mu^2+6 \lambda \mu^3+2 \mu^4\right)^2} . \\ & \end{aligned}$$

The above expression is positive if and only if

[TeX:] $$\begin{gathered} \left(12 \lambda^3+15 \lambda^2 \mu+8 \lambda \mu^2+3 \mu^3\right)\left(5 \lambda^4+9 \lambda^3 \mu+8 \lambda^2 \mu^2+6 \lambda \mu^3+2 \mu^4\right) \\ \gt \left(20 \lambda^3+27 \lambda^2 \mu+16 \lambda \mu^2+6 \mu^3\right)\left(3 \lambda^4+5 \lambda^3 \mu+4 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4\right), \end{gathered}$$

which simplifying we obtain that

[TeX:] $$2 \lambda^6 \mu+8 \lambda^5 \mu^2+12 \lambda^4 \mu^3+10 \lambda^3 \mu^4+3 \lambda^2 \mu^5\gt 0,$$

which is true for all μ > 0. And the desired result follows.

APPENDIX C

PROOF OF PROPOSITION 3

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 [11, eq. (35a)] and we get the following system of equations:

[TeX:] $$\begin{aligned} {\left[v_{00}, v_{01}, v_{02}\right] \lambda=} & b_0 \pi_0+\mu\left[v_{11}, 0,0\right], \\ {\left[v_{10}, v_{11}, v_{12}\right](\lambda+\mu)=} & b_1 \pi_1+\lambda\left[v_{00}, 0,0\right]+\frac{\mu}{2}\left[v_{21}, v_{22}, 0\right] \\ & +\frac{\mu}{2}\left[v_{22}, v_{22}, 0\right], \\ {\left[v_{20}, v_{21}, v_{22}\right](\lambda+\mu)=} & b_2 \pi_2+\lambda\left[v_{10}, v_{11}, 0\right]+\lambda\left[v_{20}, v_{21}, 0\right] . \end{aligned}$$

The solution of this system of linear equations is

[TeX:] $$\begin{aligned} & v_{00}=\frac{3 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4}{\lambda(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{10}=\frac{\lambda^4+7 \lambda^3 \mu+13 \lambda^2 \mu^2+8 \lambda \mu^3+2 \mu^4}{2(\lambda+\mu)^3\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{11}=\frac{2 \lambda^2 \mu+\lambda \mu^2}{(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{20}=\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\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{21}=\frac{\lambda^4+4 \lambda^3 \mu+2 \lambda^2 \mu^2}{\mu(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{22}=\frac{\lambda^2}{(\lambda+\mu)\left(\lambda^2+\mu^2+\lambda \mu\right)} . \end{aligned}$$

According [11, Th. 4], the desired value is obtained by summing [TeX:] $$v_{00}, v_{10} \text{ and } v_{20}.$$ And the desired result follows.

TABLE II
THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 3.

APPENDIX D

PROOF OF PROPOSITION 4

As in the proof of Proposition 2, we first show that the ratio under study is monotonically increasing with λ. First, we note that the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2 *-F G F S}}{\Delta_{M / M / 1 / 2^*-P S}}$$ can be written as follows

(22)
[TeX:] $$\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} .$$

Lemma 3. The ratio

[TeX:] $$\frac{\Delta_{M / M / 1 / 2{ }^*-F G F S}}{\Delta_{M / M / 1 / 2 *-P S}}$$

is an increasing function of λ.

Proof. The derivative of (22) with respect to λ is

[TeX:] $$\begin{aligned} & \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} \\ & \quad-\left(15 \lambda^4+44 \lambda^3 \mu+45 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times \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}{\left(3 \lambda^5+11 \lambda^4 \mu+15 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right)^2} . \end{aligned}$$

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 λ is negative if and only if

[TeX:] $$\begin{aligned} & \left(20 \lambda^4+56 \lambda^3 \mu+48 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times\left(3 \lambda^5+11 \lambda^4 \mu+15 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right) \\ & \lt \left(15 \lambda^4+44 \lambda^3 \mu+45 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times\left(4 \lambda^5+14 \lambda^4 \mu+16 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right), \end{aligned}$$

which expanding the polynomials it results

[TeX:] $$\begin{aligned} & 60 \lambda^9+388 \lambda^8 \mu+1060 \lambda^7 \mu^2+1732 \lambda^6 \mu^3+1996 \lambda^5 \mu^4 \\ & \quad+1668 \lambda^4 \mu^5+1008 \lambda^3 \mu^6+432 \lambda^2 \mu^7+120 \lambda \mu^8+16 \mu^9 \\ & \lt 60 \lambda^9+386 \lambda^8 \mu+1036 \lambda^7 \mu^2+1656 \lambda^6 \mu^3+1880 \lambda^5 \mu^4 \\ & \quad+1572 \lambda^4 \mu^5+968 \lambda^3 \mu^6+426 \lambda^2 \mu^7+120 \lambda \mu^8+16 \mu^9 . \end{aligned}$$

We now simplify this expression and we obtain

[TeX:] $$\begin{array}{r} 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\lt 0, \end{array}$$

which is clearly false since λ and μ are positive. Therefore, the desired result follows.

We now prove Proposition 4 by studying the limit of the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2-F G F S}}{\Delta_{M / M / 1 / 2^*-P S}}$$ when λ 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 5

We show that the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 2^*-P S}}$$ is increasing with λ. We first provide the expression of the ratio under analysis:

[TeX:] $$\begin{aligned} & \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 2^*-P S}}= \\ & \quad \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} . \end{aligned}$$

We observe that the limit when [TeX:] $$\lambda \rightarrow 0$$ (resp. when [TeX:] $$\lambda \rightarrow \infty$$) of the above expression is one (resp. is 5/3). Therefore, the proof ends by showing that the ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2^*-F G F S}}{\Delta_{M / M / 1 / 2^*-P S}}$$ is increasing with λ.

Lemma 4. [TeX:] $$\frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 2^*-P S}}$$ is an increasing function of λ.

Proof. The derivative of [TeX:] $$\frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 2^*-P S}}$$ with respect to λ is

[TeX:] $$\begin{aligned} & \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} \\ & \quad-\left(15 \lambda^4+44 \lambda^3 \mu+45 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times \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}{\left(3 \lambda^5+11 \lambda^4 \mu+15 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right)^2} . \end{aligned}$$

This expression is positive if and only if

[TeX:] $$\begin{aligned} & \left(25 \lambda^4+56 \lambda^3 \mu+51 \lambda^2 \mu^2+28 \lambda^2 \mu^3+8 \mu^4\right) \\ & \quad \times\left(3 \lambda^5+11 \lambda^4 \mu+15 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right) \\ & \gt \left(15 \lambda^4+44 \lambda^3 \mu+45 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times\left(5 \lambda^5+14 \lambda^4 \mu+17 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right) . \end{aligned}$$

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

[TeX:] $$\begin{array}{r} 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\gt 0, \end{array}$$

which is clearly positive since λ and μ are positive. Thus, the desired result follows.

APPENDIX F

PROOF OF PROPOSITION 6

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

TABLE III
THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 6.

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

[TeX:] $$\begin{aligned} {\left[v_{00}, v_{01}, v_{02}\right] \lambda=} & b_0 \pi_0+\mu\left[v_{11}, 0,0\right], \\ {\left[v_{10}, v_{11}, v_{12}\right](\lambda+\mu)=} & b_1 \pi_1+\lambda\left[v_{00}, 0,0\right]+\frac{\mu}{2}\left[v_{21}, v_{22}, 0\right] \\ & +\frac{\mu}{2}\left[v_{22}, v_{22}, 0\right], \\ {\left[v_{20}, v_{21}, v_{22}\right](\lambda+\mu)=} & b_2 \pi_2+\lambda\left[v_{10}, v_{11}, 0\right]+\lambda\left[v_{20}, v_{22}, 0\right] . \end{aligned}$$

The solution of this system of linear equations is

[TeX:] $$\begin{aligned} v_{00} & =\frac{3 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4}{\lambda(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ v_{10} & =\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\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ v_{11} & =\frac{2 \lambda^2 \mu+\lambda \mu^2}{(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ v_{20} & =\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\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ v_{21} & =\frac{2 \lambda^4+5 \lambda^3 \mu+2 \lambda^2 \mu^2}{(\lambda+\mu)^3\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ v_{22} & =\frac{\lambda^2}{(\lambda+\mu)\left(\lambda^2+\mu^2+\lambda \mu\right)} . \end{aligned}$$

According to [11, Th. 4], the desired value is obtained by summing [TeX:] $$v_{00}, v_{10} \text { and } v_{20}.$$ And the desired result follows.

APPENDIX G

PROOF OF PROPOSITION 7

The proof is very similar to that of Proposition 3 and Proposition 6. 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.

TABLE IV
THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 6.

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

[TeX:] $$\begin{aligned} {\left[v_{00}, v_{01}, v_{02}\right] \lambda } & =b_0 \pi_0+\mu\left[v_{11}, 0,0\right], \\ {\left[v_{10}, v_{11}, v_{12}\right](\lambda+\mu) } & =b_1 \pi_1+\lambda\left[v_{00}, 0,0\right]+\mu\left[v_{21}, v_{22}, 0\right] \\ {\left[v_{20}, v_{21}, v_{22}\right](\lambda+\mu) } & =b_2 \pi_2+\lambda\left[v_{10}, v_{11}, 0\right]+\lambda\left[v_{20}, v_{22}, 0\right] . \end{aligned}$$

The solution of this system of linear equations is

[TeX:] $$\begin{aligned} & v_{00}=\frac{3 \lambda^2 \mu^2+3 \lambda \mu^3+\mu^4}{\lambda(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{10}=\frac{3 \lambda^4 \mu+11 \lambda^3 \mu^2+11 \lambda^2 \mu^3+5 \lambda \mu^4+\mu^5}{(\lambda+\mu)^4\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{11}=\frac{2 \lambda^2 \mu+\lambda \mu^2}{(\lambda+\mu)^2\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{20}=\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\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{21}=\frac{2 \lambda^4+5 \lambda^3 \mu+2 \lambda^2 \mu^2}{(\lambda+\mu)^3\left(\lambda^2+\mu^2+\lambda \mu\right)}, \\ & v_{22}=\frac{\lambda^2}{(\lambda+\mu)\left(\lambda^2+\mu^2+\lambda \mu\right)} . \end{aligned}$$

According to [11, Th. 4], the desired value is obtained by summing [TeX:] $$v_{00}, v_{10} \text { and } v_{20}.$$ And the desired result follows.

APPENDIX H

PROOF OF PROPOSITION 8

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

[TeX:] $$\begin{aligned} & \quad \frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}= \\ & \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}. \end{aligned}$$

Since λ > 0 and μ > 0 it is easily seen that

[TeX:] $$\Delta_{M / M / 1 / 2^{* *}-P S} \leq \Delta_{M / M / 1 / 2^{* *}-F G F S}.$$

Therefore, we know that

(23)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}.$$

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

Lemma 5. The ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}$$ takes its maximum value at [TeX:] $$\rho=2.3943$$ and it is

(24)
[TeX:] $$\frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}=1.0731$$

Proof. First we rewrite the ratio by dividing [TeX:] $$\mu^6$$ in the numerator and the denominator and we get the following

[TeX:] $$\begin{aligned} & \frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}= \\ & \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} . \end{aligned}$$

The derivative of [TeX:] $$\frac{\Delta_{M / M / 1 / 2^{* *}-F G F S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}$$ with respect to ρ is

[TeX:] $$\begin{aligned} & \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} \\ & \quad-\left(12 \rho^5+55 \rho^4+100 \rho^3+87 \rho^2+44 \rho+10\right) \\ & \quad \times \frac{2 \rho^6+12 \rho^5+28 \rho^4+30 \rho^3+22 \rho^2+10 \rho+2}{\left(2 \rho^6+11 \rho^5+25 \rho^4+29 \rho^3+22 \rho^2+10 \rho+2\right)^2} . \end{aligned}$$

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

[TeX:] $$\begin{aligned} & \left(12 \rho^5+60 \rho^4+112 \rho^3+90 \rho^2+44 \rho+10\right) \\ & \quad \times\left(2 \rho^6+11 \rho^5+25 \rho^4+29 \rho^3+22 \rho^2+10 \rho+2\right) \\ & \quad-\left(12 \rho^5+55 \rho^4+100 \rho^3+87 \rho^2+44 \rho+10\right) \\ & \quad \times\left(2 \rho^6+12 \rho^5+28 \rho^4+30 \rho^3+22 \rho^2+10 \rho+2\right)=0 . \end{aligned}$$

Expanding that expression we get

(25)
[TeX:] $$\begin{aligned} -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 \end{aligned}$$

Since λ > 0 and μ > 0 then ρ must be positive, and the only postive root of that expression is ρ = 2.3943. Therefore, this ratio is larger than one from (23) and it is equal to one when [TeX:] $$\rho \rightarrow 0 \text { and } \rho \rightarrow \infty \text {. }$$ Therefore, it has a unique maximum when ρ is positive, which is achieved for ρ = 2.3943. We evaluate ρ = 2.3943 on our ratio and the desired result follows.

APPENDIX I

PROOF OF PROPOSITION 9

We have

(26)
[TeX:] $$\begin{aligned} & \quad \frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 2^{* *}-P S}}= \\ & \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} . \end{aligned}$$

Thus, taking into account that the rhs of (26) tends to 1 when [TeX:] $$\rho \rightarrow 0 \text { and } to 3/2$$ when [TeX:] $$\rho \rightarrow \infty \text {, }$$ the desired result follows if we show that the rhs of (26) is increasing with λ, which we proof in the following result.

Lemma 6. The rhs of (26) is an increasing function of λ for all μ > 0.

Proof. We compute the derivative of the ratio with respect to λ and it results

[TeX:] $$\begin{aligned} & \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} \\ & -\left(12 \lambda^5+55 \lambda^4 \mu+100 \lambda^3 \mu^2+87 \lambda^2 \mu^3+44 \lambda \mu^4+10 \mu^5\right) \\ & \times \frac{\left(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\right)}{\left(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\right)^2} . \end{aligned}$$

The above expression is positive if and only if

[TeX:] $$\begin{aligned} & \left(18 \lambda^5+70 \lambda^4 \mu+104 \lambda^3 \mu^2+87 \lambda^2 \mu^3+44 \lambda \mu^4+10 \mu^5\right) \\ & \times\left(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\right) \\ & \gt \left(12 \lambda^5+55 \lambda^4 \mu+100 \lambda^3 \mu^2+87 \lambda^2 \mu^3+44 \lambda \mu^4+10 \mu^5\right) \\ & \times\left(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\right) \end{aligned}$$

which simplifying we obtain that

[TeX:] $$\begin{aligned} & 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\gt 0, \end{aligned}$$

which is true for all μ > 0. And the desired result follows.

APPENDIX J

PROOF OF PROPOSITION 10

We have

(27)
[TeX:] $$\begin{aligned} & \frac{\Delta_{M / M / 1 / 1}}{\Delta_{M / M / 1 / 2^*-P S}}= \\ & \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}. \end{aligned}$$

Thus, taking into account that the rhs of (27) tends to 1 when [TeX:] $$\lambda \rightarrow 0$$ and to 4/3 when [TeX:] $$\lambda \rightarrow \infty,$$ the desired result follows if we show that the rhs of (27) is increasing with λ, which we proof in the following result.

Lemma 7. The rhs of (27) is an increasing function of λ for all μ > 0.

Proof. We compute the derivative of the ratio with respect to λ and it results

[TeX:] $$\begin{aligned} & \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} \\ & \quad-\left(15 \lambda^4+44 \lambda^3 \mu+45 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times \frac{\left(4 \lambda^5+12 \lambda^4 \mu+18 \lambda^3 \mu^2+16 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right)}{\left(3 \lambda^5+11 \lambda^4 \mu+15 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right)^2} . \end{aligned}$$

The above expression is positive if and only if

[TeX:] $$\begin{aligned} & \left(20 \lambda^4+48 \lambda^3 \mu+54 \lambda^2 \mu^2+32 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times\left(3 \lambda^5+11 \lambda^4 \mu+15 \lambda^3 \mu^2+14 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right) \\ & \gt \left(15 \lambda^4+44 \lambda^3 \mu+45 \lambda^2 \mu^2+28 \lambda \mu^3+8 \mu^4\right) \\ & \quad \times\left(4 \lambda^5+12 \lambda^4 \mu+18 \lambda^3 \mu^2+16 \lambda^2 \mu^3+8 \lambda \mu^4+2 \mu^5\right), \end{aligned}$$

which simplifying we obtain that

[TeX:] $$\begin{aligned} 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\gt 0, \end{aligned}$$

which is true for all μ > 0. And the desired result follows.

APPENDIX K

PROOF OF PROPOSITION 11

(28)
[TeX:] $$\begin{aligned} & \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 1}}= \\ & \quad \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} . \end{aligned}$$

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

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

Lemma 8. If [TeX:] $$\lambda \in(0, \mu],$$ then we have the following

(29)
[TeX:] $$0.9641 \leq \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 1}} \leq 1.$$

Proof. First we rewrite the ratio by dividing [TeX:] $$\mu^4$$ in the numerator and the denominator. So we get the following

(30)
[TeX:] $$\frac{\Delta_{M / M / 1 / 2-P S}}{\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} .$$

The derivative of the ratio with respect to ρ is

[TeX:] $$\begin{aligned} & \quad \frac{20 \rho^3+27 \rho^2+16 \rho+6}{4 \rho^4+8 \rho^3+10 \rho^2+6 \rho^2+2} \\ & -\left(16 \rho^3+24 \rho^2+20 \rho+6\right) \frac{5 \rho^4+9 \rho^3+8 \rho^2+6 \rho^2+2}{\left(4 \rho^4+8 \rho^3+10 \rho^2+6 \rho^2+2\right)^2}. \end{aligned}$$

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

[TeX:] $$\begin{array}{r} \left(20 \rho^3+27 \rho^2+16 \rho+6\right)\left(4 \rho^4+8 \rho^3+10 \rho^2+6 \rho^2+2\right) \\ -\left(16 \rho^3+24 \rho^2+20 \rho+6\right)\left(5 \rho^4+9 \rho^3+8 \rho^2+6 \rho^2+2\right)=0. \end{array}$$

Expanding that expression we get

(31)
[TeX:] $$4 \rho^6+36 \rho^5+44 \rho^4+20 \rho^3-6 \rho^2-8 \rho=0 .$$

Since λ > 0 and μ > 0 then ρ must be positive, and the only postive root of that expression is ρ = 0.4697. Besides,

[TeX:] $$\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 [TeX:] $$\rho \rightarrow 0 \text { and } \rho \rightarrow \infty.$$ Therefore, since we have shown that it has a single local critical point, it is a minimum. We evaluate ρ = 0.4697 on our ratio and the desired result follows.

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

(32)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2-P S}}{\Delta_{M / M / 1 / 1}} \leq \frac{5}{4}.$$

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

APPENDIX L

PROOF OF PROPOSITION 12

We first going to write the expression of the ratio.

[TeX:] $$\begin{aligned} & \quad \frac{\Delta_{M / M / 1 / 2^*-P S}}{\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} . \end{aligned}$$

Since λ > 0 and μ > 0 it is easily seen that [TeX:] $$\Delta_{M / M / 1 / 1^*} \leq \Delta_{M / M / 1 / 2^*-P S}.$$ So we know that

(33)
[TeX:] $$1 \leq \frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 1^*}}.$$

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

Lemma 9. The ratio [TeX:] $$\frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 1^*}}$$ takes its maximum value at ρ = 2.3943 and it is

(34)
[TeX:] $$\frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 1^*}}=1.0788.$$

Proof. First we rewrite the ratio by dividing [TeX:] $$\mu^6$$ in the numerator and the denominator. So we get the following

[TeX:] $$\begin{aligned} & \frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 1^*}}= \\ & \quad \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} . \end{aligned}$$

The derivative of [TeX:] $$\frac{\Delta_{M / M / 1 / 2^*-P S}}{\Delta_{M / M / 1 / 1^*}}$$ with respect to ρ is

[TeX:] $$\begin{aligned} & \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} \\ & \quad-\left(12 \rho^5+50 \rho^4+88 \rho^3+84 \rho^2+44 \rho+10\right) \\ & \quad \times \frac{2 \rho^6+11 \rho^5+25 \rho^4+29 \rho^3+22 \rho^2+10 \rho+2}{\left(2 \rho^6+10 \rho^5+22 \rho^4+28 \rho^3+22 \rho^2+10 \rho+2\right)^2} . \end{aligned}$$

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

[TeX:] $$\begin{aligned} & \left(12 \rho^5+55 \rho^4+100 \rho^3+87 \rho^2+44 \rho+10\right) \\ & \quad \times\left(2 \rho^6+10 \rho^5+22 \rho^4+28 \rho^3+22 \rho^2+10 \rho+2\right) \\ & \quad-\left(12 \rho^5+50 \rho^4+88 \rho^3+84 \rho^2+44 \rho+10\right) \\ & \quad \times\left(2 \rho^6+11 \rho^5+25 \rho^4+29 \rho^3+22 \rho^2+10 \rho+2\right)=0 . \end{aligned}$$

Expanding that expression we get

(35)
[TeX:] $$\begin{aligned} -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 . \end{aligned}$$

Since λ > 0 and μ > 0 then ρ must be positive, and the only positive root of that expression is ρ = 2.3943. Besides, we have that

[TeX:] $$\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 [TeX:] $$\rho \in(0, \infty)$$ and tends to one when [TeX:] $$\rho \rightarrow 0 \text { and } \rho \rightarrow \infty \text {. }$$ Therefore, this ratio has a unique maximum when [TeX:] $$\rho \in(0, \infty)$$. We evaluate ρ = 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 [TeX:] $$\mathcal{Q}=\{0,1,2, \cdots\},$$ which is a birth-death process with birth rate λ and death rate μ. For this Markov chain, the stationary distribution is clearly [TeX:] $$\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 [11, Th. 4] as follows

[TeX:] $$\Delta_{M / M / 1-P S}=\sum_{q \in \mathcal{Q}} v_{q 0}>v_{00}$$

TABLE V
THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF LEMMA 1.

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.

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 [11, eq. (35a)] to the SHS of Table V and we get

[TeX:] $$\lambda v_{00}=\pi_0+v_{11} \mu>\pi_0 \Longleftrightarrow v_{00}=\frac{\mu-\lambda}{\lambda \mu}.$$

And the desired result follows.

APPENDIX N

PROOF OF PROPOSITION 14.

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

[TeX:] $$\Delta_{M / M / 1-F G F S} \leq \Delta_{M / M / 1-P S} \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 [TeX:] $$\frac{\Delta_{M / M / 1-F G F S}}{\Delta_{M / M / 1-P S}}$$ is unbounded from above. That is,

[TeX:] $$\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 [TeX:] $$\rho \rightarrow 1$$ since

[TeX:] $$\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 [TeX:] $$\rho \rightarrow 1$$.

Biography

Be˜ nat Gandarias

bio1.png

Be˜ nat 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.

Biography

Josu Doncel

bio2.png

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. He received in 2015 the PhD degree from Universit´ e 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), INSAToulouse (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.

Biography

Mohamad Assaad

bio3.png

Mohamad Assaad received the M.Sc and PhD degrees, both in Telecommunications, from Telecom ParisTech, Paris, France, in 2002 and 2006, respec- tively. Since 2006, he has been with the Telecom- munications 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 Co-Chair, 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.

References

  • 1 S. Kaul, R. Yates, and M. Gruteser, "Real-time status: How often should one update?" in Proc. IEEE INFOCOM, 2012.custom:[[[https://ieeexplore.ieee.org/document/6195689]]]
  • 2 S. K. Kaul, R. D. Yates, and M. Gruteser, "Status updates through queues," in Proc. IEEE CISS, 2012.custom:[[[https://ieeexplore.ieee.org/document/6310931]]]
  • 3 R. D. Yates and S. Kaul, "Real-time status updating: Multiple sources," IEEE Int. Symp. Inf. Theory Proc., pp. 2666-2670, 2012.custom:[[[https://ieeexplore.ieee.org/document/6284003]]]
  • 4 C. Kam, S. Kompella, G. D. Nguyen, and A. Ephremides, "Effect of message transmission path diversity on status age," IEEE Trans. Inf. Theory, vol. 62, no. 3, pp. 1360-1374, 2016.custom:[[[https://ieeexplore.ieee.org/document/7364263]]]
  • 5 M. Costa, M. Codreanu, and A. Ephremides, "Age of information with packet management," in Proc. IEEE ISIT, 2014.custom:[[[https://ieeexplore.ieee.org/document/6875100]]]
  • 6 M. Costa, M. Codreanu, and A. Ephremides, "On the age of information in status update systems with packet management," IEEE Trans. Inf. Theory, vol. 62, no. 4, pp. 1897-1910, 2016.custom:[[[https://ieeexplore.ieee.org/abstract/document/7415972]]]
  • 7 A. Soysal and S. Ulukus, "Age of information in G/G/1/1 systems: Age expressions, bounds, special cases, and optimization," IEEE Trans. Inf. Theory, vol. 67, no. 11, pp. 7477-7489, 2021.custom:[[[https://www.semanticscholar.org/paper/Age-of-Information-in-G-G-1-1-Systems%3A-Age-Bounds%2C-Soysal-Ulukus/de72bd546c35ee5f5b07cf3dddd48e629163afaa]]]
  • 8 Z. Chen et al., "Age of information: The multi-stream M/G/1/1 non-preemptive system," IEEE Trans. Commun., vol. 70, no. 4, pp. 2328-2341, 2022.custom:[[[https://ieeexplore.ieee.org/document/9718306]]]
  • 9 E. Najm and E. Telatar, "Status updates in a multi-stream M/G/1/1 preemptive queue," in Proc. IEEE INFOCOM, 2018.doi:[[[10.48550/arXiv.1801.04068]]]
  • 10 R. D. Yates and S. Kaul, "Real-time status updating: Multiple sources," IEEE Int. Symp. Inf. Theory Proc., pp. 2666-2670, 2012.custom:[[[https://ieeexplore.ieee.org/document/6284003]]]
  • 11 R. D. Yates and S. K. Kaul, "The age of information: Real-time status updating by multiple sources," IEEE Trans. Inf. Theory, vol. 65, no. 3, pp. 1807-1827, 2018.custom:[[[https://ieeexplore.ieee.org/document/8469047]]]
  • 12 A. M. Bedewy, Y . Sun, and N. B. Shroff, "Optimizing data freshness, throughput, and delay in multi-server information-update systems," in Proc. IEEE ISIT, 2016.doi:[[[10.48550/arXiv.1603.06185]]]
  • 13 R. D. Yates, "Status updates through networks of parallel servers," IEEE Int. Symp. Inf. Theory Proc., pp 2281-2285, 2018.custom:[[[https://ieeexplore.ieee.org/document/8437907]]]
  • 14 J. Doncel and M. Assaad, "Age of information in a decentralized network of parallel queues with routing and packets losses," IEEE/KICS J. Commun. Netw., vol. 24, no. 1, pp. 17-36, 2022.doi:[[[10.48550/arXiv.2002.01696]]]
  • 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 Trans. Netw., vol. 26, no. 6, pp. 2637-2650, 2018.custom:[[[https://ieeexplore.ieee.org/document/8514816]]]
  • 16 A. Maatouk, Y . Sun, A. Ephremides, and M. Assaad, "Status updates with priorities: Lexicographic optimality," in Proc. IEEE WiOPT, 2020.doi:[[[10.48550/arXiv.2002.01916]]]
  • 17 Y . Sun, E. Uysal-Biyikoglu, and S. Kompella, "Age-optimal updates of multiple information flows," in Proc. IEEE INFOCOM WKSHPS, 2018.doi:[[[10.48550/arXiv.1801.02394]]]
  • 18 A. M. Bedewy, Y . Sun, and N. B. Shroff, "Age-optimal information updates in multihop networks," in Proc. IEEE ISIT, 2017.custom:[[[https://ieeexplore.ieee.org/document/8006593]]]
  • 19 A. M. Bedewy, Y . Sun, and N. B. Shroff, "The age of information in multihop networks,"IEEE/ACMTrans.Netw., vol. 27, no. 3, pp. 1248-1257, 2019.doi:[[[10.48550/arXiv.1712.10061]]]
  • 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 Trans. Inf. Theory, vol. 63, no. 11, pp. 7492-7508, 2017.doi:[[[10.48550/arXiv.1601.02284]]]
  • 21 Y .-P. Hsu, E. Modiano, and L. Duan, "Age of information: Design and analysis of optimal scheduling algorithms," in Proc. ISIT, 2017.custom:[[[https://ieeexplore.ieee.org/abstract/document/8006590]]]
  • 22 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 Trans. Wireless Commun., vol. 20, no. 2, pp. 1263-1277, 2020.custom:[[[https://ieeexplore.ieee.org/document/9241401/]]]
  • 23 S. Kriouile, M. Assaad, and A. Maatouk, "On the global optimality of whittle’s index policy for minimizing the age of information," IEEE Trans. Inf. Theory, vol. 68, no. 1, pp. 572-600, 2022.doi:[[[10.48550/arXiv.2102.02528]]]
  • 24 A. Arafa, J. Yang, and S. Ulukus, "Age-minimal online policies for energy harvesting sensors with random battery recharges," inProc.IEEE ICC, 2018.custom:[[[https://ieeexplore.ieee.org/document/8422086]]]
  • 25 A. Arafa, J. Yang, S. Ulukus, and H. V . Poor, "Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies," IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 534-556, 2019.custom:[[[https://ieeexplore.ieee.org/document/8822722]]]
  • 26 R. D. Yates, "Lazy is timely: Status updates by an energy harvesting source," IEEE Int. Symp. Inf. Theory Proc., pp. 3008-3012, 2015.custom:[[[https://ieeexplore.ieee.org/document/7283009]]]
  • 27 B. T. Bacinoglu, Y . Sun, E. Uysal-Bivikoglu, and V . Mutlu, "Achieving the age-energy tradeoff with a finite-battery energy harvesting source," IEEE Int. Symp. Inf. Theory Proc., pp. 876-880, 2018.custom:[[[https://ieeexplore.ieee.org/document/8437573]]]
  • 28 B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, "Age of information under energy replenishment constraints," in Proc. ITA WKSHPS, 2015.custom:[[[https://www.researchgate.net/publication/308729887_Age_of_information_under_energy_replenishment_constraints]]]
  • 29 F. Chiariotti et al., "Query age of information: Freshness in pull-based communication," IEEE Trans. Commun., vol. 70, no. 3, pp. 1606-1622, 2022.custom:[[[https://ieeexplore.ieee.org/document/9676636]]]
  • 30 J. Zhong, R. D. Yates, and E. Soljanin, "Two freshness metrics for local cache refresh," in Proc. IEEE ISIT, 2018.custom:[[[https://ieeexplore.ieee.org/document/8437927]]]
  • 31 A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, "The age of incorrect information: A new performance metric for status updates," IEEE/ACM Trans. Netw., vol. 28, no. 5, pp. 2215-2228, 2020.doi:[[[10.1109/TNET.2020.3005549]]]
  • 32 G. Stamatakis and A. T. N. Pappas, "Control of status updates for energy harvesting devices that monitor processes with alarms," in Proc. GLOBECOM WKSHPS, 2019.custom:[[[https://ieeexplore.ieee.org/document/9024463]]]
  • 33 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 Proc. IEEE INFOCOM WKSHPS, 2018.custom:[[[https://ieeexplore.ieee.org/document/8406891]]]
  • 34 R. D. Yates, "The age of gossip in networks," IEEE Int. Symp. Inf. Theory Proc., pp. 2984-2989, 2021.doi:[[[10.48550/arXiv.2102.02893]]]
  • 35 Y . Sun and B. Cyr, "Sampling for data freshness optimization: Nonlinear age functions," IEEE/KICS J. Commun. Netw., vol. 21, no. 3, pp. 204-219, 2019.doi:[[[10.48550/arXiv.1812.07241]]]
  • 36 E. Uysal et al., "Semantic communications in networked systems: A data significance perspective," IEEE Netw., vol. 36, no. 4, pp. 233-240, 2022.doi:[[[10.48550/arXiv.2103.05391]]]
  • 37 A. Kosta, N. Pappas, A. Ephremides, and V . Angelakis, "Age and value of information: Non-linear age case," in Proc. IEEE ISIT, 2019.doi:[[[10.48550/arXiv.1701.06927]]]
  • 38 A. Maatouk, M. Assaad, and A. Ephremides, "The age of incorrect information: An enabler of semantics-empowered communication," 2020, arXiv:2012.13214.custom:[[[https://ieeexplore.ieee.org/document/9838737]]]
  • 39 S. Kriouile and M. Assaad, "Minimizing the age of incorrect information for real-time tracking of Markov remote sources," in Proc. IEEE ISIT, 2021.doi:[[[10.48550/arXiv.2102.03245]]]
  • 40 Y . Chen and A. Ephremides, "Scheduling to minimize age of incorrect information with imperfect channel state information," Entropy, vol. 23, no. 12, p. 1572, 2021.doi:[[[10.48550/arXiv.2301.06150]]]
  • 41 M. Ayik, E. T. Ceran, and E. Uysal, "Optimization of AoII and QAoII in multi-user links," 2023, arXiv:2305.00191.doi:[[[10.48550/arXiv.2305.00191]]]
  • 42 N. Pappas, M. Abd-Elmagid, B. Zhou, W. Saad, and H. Dhillon, Age of Information: Foundations and Applications. Cambridge University Press, 2023.custom:[[[https://www.cambridge.org/core/books/age-of-information/DC6772A6B62FC2F5527CA569A6C6EE98]]]
  • 43 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.custom:[[[https://www.amazon.com/Age-Information-Freshness-Synthesis-Communication/dp/1681736802]]]
  • 44 R. Yates et al., "Age of information: An introduction and survey," IEEE J. Sel. Areas Commun., vol. 39, no. 5, pp. 1183-1210, 2021.doi:[[[10.48550/arXiv.2007.08564]]]
  • 45 L. Kleinrock, "Theory, volume 1, queueing systems," 1975.custom:[[[-]]]
  • 46 S. F. Yashkov, "Processor-sharing queues: Some progress in analysis," Queueing Syst., vol. 2, pp. 1-17, 1987.custom:[[[https://link.springer.com/article/10.1007/BF01182931]]]
  • 47 F. Kelly, "Stochastic networks and reversibility, New York, Wiley," 1979.custom:[[[https://link.springer.com/chapter/10.1007/978-3-662-13052-0_4]]]

TABLE I

THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 1.
l [TeX:] $$\lambda^{(l)}$$ [TeX:] $$q \longrightarrow q^{\prime}$$ [TeX:] $$x \longrightarrow x^{\prime}=A_l x$$ [TeX:] $$v_{q l} A_l$$
0 λ [TeX:] $$0 \longrightarrow 1$$ [TeX:] $$\left[x_0, 0,0\right] \longrightarrow\left[x_0, 0,0\right]$$ [TeX:] $$\left[v_{00}, 0, 0\right]$$
1 μ [TeX:] $$1 \longrightarrow 0$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_1, 0,0\right]$$ [TeX:] $$\left[v_{11}, 0, 0\right]$$
2 λ [TeX:] $$1 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_0, x_1 ,0\right]$$ [TeX:] $$\left[v_{10}, v_{11}, 0\right]$$
3 [TeX:] $$\frac{\mu}{2}$$ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_1, x_2 ,0\right]$$ [TeX:] $$\left[v_{21}, v_{22}, 0\right]$$
4 [TeX:] $$\frac{\mu}{2}$$ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_2, x_2 ,0\right]$$ [TeX:] $$\left[v_{22}, v_{22}, 0\right]$$
5 λ [TeX:] $$2 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_0, x_1 ,x_2\right]$$ [TeX:] $$\left[v_{20}, v_{21}, v_{22}\right]$$

TABLE II

THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 3.
l [TeX:] $$\lambda^{(l)}$$ [TeX:] $$q \longrightarrow q^{\prime}$$ [TeX:] $$x \longrightarrow x^{\prime}=A_l x$$ [TeX:] $$v_{q l} A_l$$
0 λ [TeX:] $$0 \longrightarrow 1$$ [TeX:] $$\left[x_0, 0,0\right] \longrightarrow\left[x_0, 0,0\right]$$ [TeX:] $$\left[v_{00}, 0, 0\right]$$
1 μ [TeX:] $$1 \longrightarrow 0$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_1, 0,0\right]$$ [TeX:] $$\left[v_{11}, 0, 0\right]$$
2 λ [TeX:] $$1 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_0, x_1 ,0\right]$$ [TeX:] $$\left[v_{10}, v_{11}, 0\right]$$
3 [TeX:] $$\frac{\mu}{2}$$ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_1, x_2 ,0\right]$$ [TeX:] $$\left[v_{21}, v_{22}, 0\right]$$
4 [TeX:] $$\frac{\mu}{2}$$ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_2, x_2 ,0\right]$$ [TeX:] $$\left[v_{22}, v_{22}, 0\right]$$
5 λ [TeX:] $$2 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_0, x_1 ,0\right]$$ [TeX:] $$\left[v_{20}, v_{21}, 0\right]$$

TABLE III

THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 6.
l [TeX:] $$\lambda^{(l)}$$ [TeX:] $$q \longrightarrow q^{\prime}$$ [TeX:] $$x \longrightarrow x^{\prime}=A_l x$$ [TeX:] $$v_{q l} A_l$$
0 λ [TeX:] $$0 \longrightarrow 1$$ [TeX:] $$\left[x_0, 0,0\right] \longrightarrow\left[x_0, 0,0\right]$$ [TeX:] $$\left[v_{00}, 0, 0\right]$$
1 μ [TeX:] $$1 \longrightarrow 0$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_1, 0,0\right]$$ [TeX:] $$\left[v_{11}, 0, 0\right]$$
2 λ [TeX:] $$1 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_0, x_1 ,0\right]$$ [TeX:] $$\left[v_{10}, v_{11}, 0\right]$$
3 [TeX:] $$\frac{\mu}{2}$$ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_1, x_2 ,0\right]$$ [TeX:] $$\left[v_{21}, v_{22}, 0\right]$$
4 [TeX:] $$\frac{\mu}{2}$$ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_2, x_2 ,0\right]$$ [TeX:] $$\left[v_{22}, v_{22}, 0\right]$$
5 λ [TeX:] $$2 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_0, x_2 ,0\right]$$ [TeX:] $$\left[v_{20}, v_{22}, 0\right]$$

TABLE IV

THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF PROPOSITION 6.
l [TeX:] $$\lambda^{(l)}$$ [TeX:] $$q \longrightarrow q^{\prime}$$ [TeX:] $$x \longrightarrow x^{\prime}=A_l x$$ [TeX:] $$v_{q l} A_l$$
0 λ [TeX:] $$0 \longrightarrow 1$$ [TeX:] $$\left[x_0, 0,0\right] \longrightarrow\left[x_0, 0,0\right]$$ [TeX:] $$\left[v_{00}, 0, 0\right]$$
1 μ [TeX:] $$1 \longrightarrow 0$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_1, 0,0\right]$$ [TeX:] $$\left[v_{11}, 0, 0\right]$$
2 λ [TeX:] $$1 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, 0\right] \longrightarrow\left[x_0, x_1 ,0\right]$$ [TeX:] $$\left[v_{10}, v_{11}, 0\right]$$
3 μ [TeX:] $$2 \longrightarrow 1$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_1, x_2 ,0\right]$$ [TeX:] $$\left[v_{21}, v_{22}, 0\right]$$
4 λ [TeX:] $$2 \longrightarrow 2$$ [TeX:] $$\left[x_0, x_1, x_2\right] \longrightarrow\left[x_0, x_2 ,0\right]$$ [TeX:] $$\left[v_{20}, v_{22}, 0\right]$$

TABLE V

THE SHS TABLE UNDER CONSIDERATION IN THE PROOF OF LEMMA 1.
l [TeX:] $$\lambda^{(l)}$$ [TeX:] $$q \longrightarrow q^{\prime}$$ [TeX:] $$x \longrightarrow x^{\prime}=A_l x$$ [TeX:] $$v_{q l} A_l$$
0 λ [TeX:] $$0 \longrightarrow 1$$ [TeX:] $$\left[x_0, \ldots\right] \longrightarrow\left[x_0, \ldots\right]$$ [TeX:] $$\left[v_{00}, \ldots\right]$$
1 μ [TeX:] $$1 \longrightarrow 0$$ [TeX:] $$\left[x_0, \ldots\right] \longrightarrow\left[x_1, \ldots\right]$$ [TeX:] $$\left[v_{11}, \ldots\right]$$
A monitoring system example.
Comparison of the AAoI of source 1 in a M/M/1 queue with divers queueing disciplines when [TeX:] $$\lambda_2$$ changes from 0.001 to 0.05 and [TeX:] $$\lambda_1=0.1.$$
Comparison of the AAoI of the source 1 in a M/M/1 queue with divers queueing disciplines when [TeX:] $$\lambda_2$$ changes from [TeX:] $$0.001 \text { to } 10^3 \text { and } \lambda_1=5 \text {. }$$
Comparison of the AAoI of source 1 plus the AAoI of source 2 in a M/M/1 queue with divers queueing disciplines when [TeX:] $$\lambda_2$$ changes from 0.001 to 30 and [TeX:] $$0\lambda_1=0.1 \text {. }$$
Comparison of the AAoI of source 1 plus the AAoI of source 2 in a M/M/1 queue with divers queueing disciplines when [TeX:] $$\lambda_2$$ changes from [TeX:] $$0.001 \text { to } 10^3 \text { and } \lambda_1=5 \text {. }$$
The Markov chain under consideration in the proof of Proposition 1.