{'fraction_non_alphanumeric': 0.04385119688639498, 'fraction_numerical': 0.010353492414366415, 'mean_word_length': 4.203499803381832, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Age of Information for Single Buffer Systems with Vacation Server

In this research, we study the information freshness in M/G/1 queueing system with a single buffer and the server taking multiple vacations. This system has wide applications in communication systems. We aim to evaluate the information freshness in this system with both i.i.d. and non-i.i.d. vacations under three different scheduling policies, namely Conventional Buffer System (CBS), Buffer Relaxation System (BRS), and Conventional Buffer System with Preemption in Service (CBS-P). For the systems with i.i.d. vacations, we derive the closed-form expressions of information freshness metrics such as the expected Age of Information (AoI), the expected Peak Age of Information (PAoI), and the variance of peak age under each policy. For systems with non-i.i.d. vacations, we use the polling system as an example and provide the closed-form expression of its PAoI under each policy. We explore the conditions under which one of these policies has advantages over the others for each information freshness metric. We further perform numerical studies to validate our results and develop insights.


INTRODUCTION
Information freshness has recently drawn the wide attention of researchers due to its applications in many communication settings [1], [2]. In a communication system, the data receiver (user) usually needs fresh information sampled at the physical process for on-the-fly decisionmaking. Unlike long-established queueing metrics such as throughput or waiting time, information freshness measures how timely the user is informed about the physical process, and a large information freshness would enable the user to react timely to different changes in the physical process [3], [4], [5]. Therefore, guaranteeing the information freshness for users in communication systems is of great importance. This paper studies the information freshness in a queueing system where a data source generates data packets and sends them to a server over time. The server needs to process the packets to extract useful information for the user. The server would take vacations after processing a packet, and the server would resume working if it finds a packet in the queue after returning from a vacation period. Such a vacation server system where information freshness is of interest is an abstraction of real-life communication systems, and it can be found in many application scenarios.
One scenario is in a smart manufacturing system where fresh data sampled at machines would be helpful for the decision-maker (user) in estimating the Remaining Useful Life (RUL) [6], detecting defects of manufactured products [7], or making process controls [8]. In such a system, the energy-saving sleeping period that the server (computer or processor) takes when it has no information to process can be regarded as a vacation period [9].
Another scenario of such a system is in underwater sensor networks of the petroleum industry or aquatic environment monitoring, where people need to obtain timely updates about underwater environment status. A rechargeable autonomous underwater vehicle can be sent from the surface to upload or collect data from the underwater node in a periodic manner (see [10], [11]). This way of collecting data can avoid frequent battery replacement resulted from acoustic transmissions (see [12], [13]), and the period that the vehicle travels between the surface and underwater node can be regarded as the server vacation.
The third scenario is in remote health monitoring, where the health data is acquired by a wearable device from a patient and transmitted to the healthcare provider over time (see [14], [15]). The most recent health status of the patient will be useful for tracking the patient's health status, but the doctor at the health center cannot wait for the update from a single patient all the time without performing other duties.
Besides the examples mentioned above, the vacation server systems also exist in sensor networks and computercommunication systems where the server has additional tasks aside from processing the primary data source of interest, such as priority queue systems [16], [17], [18] and polling systems [19]. Systems with server maintenance (see [20]) and systems with on/off servers (see [21]) can be regarded as vacation server systems as well.
Although the vacation server system widely exists in various applications, its performance on information freshness has not been fully understood. In this work, we aim to answer the following key research questions: • There are several widely discussed metrics to measure information freshness, such as Age of Information (AoI) [1], Peak Age of Information arXiv:2004.11847v2 [cs.PF] 23 Dec 2021 (PAoI) [4], and variance of peak age [22]. How do we evaluate these metrics in the systems with server vacations?
• How are these information freshness metrics determined by packet arrival rate, service time, vacation time, and scheduling policies?
• For different scheduling policies applied in this system, which policy performs the best in terms of each information freshness metric?
Answering those research questions would provide us with theoretical performance guarantees and guidelines for designing scheduling policies in various communication systems and real-life applications, thereby improving information freshness for users. Several challenges exist in answering these questions, which are: 1) the information freshness metrics in vacation server systems have not been fully studied, and results for systems with no vacations cannot be applied in our system; 2) when the packet processing time and vacation time are non-exponential, the technics that rely on exponential assumptions (such as Continuous Time Markov Chain analysis [23] and Stochastic Hybrid System analysis [24]) cannot be applied; 3) when the vacation time is non-i.i.d., the age metrics could be difficult to solve.
To address the research questions and overcome the challenges above, we focus our discussion on scheduling policies applied to the single buffer system due to the benefit of having a single buffer in improving information freshness [17], [25]. In particular, we study three different scheduling policies in the single buffer system, denoted as Conventional Buffer System (CBS), Buffer Relaxation System (BRS), and Conventional Buffer System with Preemption in Service (CBS-P), with detailed descriptions provided in Section 3. We show that the information freshness metrics under these policies can be decomposed into several computable components. Using this decomposition approach, we further evaluate the AoI, PAoI, and variance of peak age for systems with i.i.d. vacations, and PAoI for systems with non-i.i.d. vacations, under each scheduling policy. The main contributions of this paper are summarized as follows: • We propose a novel analytical approach to derive the closed-form expressions of AoI, PAoI, and variance of peak age for CBS, BRS, and CBS-P in systems with i.i.d. vacations. For systems with non-i.i.d. vacations, we derive the PAoI for polling systems with Markovian polling schemes. We show that this analytical approach can be potentially applied to evaluate the age metrics for systems with other types of server vacations. • We provide the conditions under which one scheduling policy has the advantage over the others. Specifically, we prove that when vacation times are i.i.d., the PAoI in BRS is always no greater than that in CBS, regardless of the vacation or service time distributions. We also show that when the arrival rate is low, BRS can have a significant advantage over CBS in minimizing AoI, PAoI, and variance of peak age, which shows the advantage of allowing the buffer to be available all the time in light-traffic systems.
• We provide sufficient conditions under which CBS-P has a smaller PAoI than CBS. Our analysis reveals the advantage of having packet preemption in vacation server systems when the packet processing time is Gamma distributed with small scale parameters.

•
Our results show that under some specific processing time distributions, reducing vacation time does not always decrease the AoI, due to the particular definition of AoI.
• Our work reveals that for polling systems with multiple queues, reducing the vacation time for a specific queue could reduce the PAoI for this queue but significantly increase the PAoI for other queues. So the cyclic routing scheme is recommended in polling systems for minimizing the average PAoI across queues.
The rest of this paper is organized as follows: Section 2 provides a summary of the literature. The system model is then introduced in Section 3. In Section 4, we consider the cases where the server takes i.i.d. vacations. In Section 5, we consider the case with non-i.i.d. vacations and discuss the polling system as an example of the non-i.i.d. vacation model. We perform numerical studies, develop insights in Section 6, and provide concluding remarks and insights for future work in Section 7.

RELATED WORK
The queueing systems with server vacations have been widely investigated due to their wide applications. Most of the early studies focused on classic queueing metrics such as average waiting time, queue length, throughput, and blocking probability in vacation server systems, without considering information freshness. Fuhrmann [26] studied the sojourn time in M/G/1 system with the server following the multiple vacation scheme. Lee studied the queue length distribution for M/G/1/N queue with vacations in [27], [28]. Kella and Yechiali [18] studied the moments for waiting time in M/G/1 system with server vacations and customer priorities. Other models about server vacations can be found in [29], [30], [31], [32]. As a concept developed recently, information freshness was not considered in these early works.
There are very few papers discussing information freshness in systems with server vacations. Maatouk et al. [23] considered a system where the server sleeps and wakes randomly following exponential distributions. We will show later in our work that allowing the service time to be non-exponential will lead to some counterintuitive results. Moreover, the Continuous Time Markov Chain analysis used in [23] cannot be applied to systems where vacation and service times are generally distributed. Najm et al. [49] considered a system of two data streams with different priorities, and discussed several service disciplines for the low priority stream. Xu and Gautam [17] discussed the PAoI in M/G/1/2* and M/G/1 priority queueing systems. However, the priority queue system is a special type of vacation model. The analysis in [17], [49] cannot be applied in our vacation server system under different scheduling policies. Tripathi et al. [50], [51] provided analysis for discrete-time FCFS Ber/G/1 vacation server queue. However, Talak et al. [47] found that the AoI and PAoI in discrete-time queues could be significantly different from their counterparts in continuoustime systems. Therefore, there is a need to investigate a continuous-time vacation server model. Moreover, as pointed out in [17], the single buffer systems are usually more efficient than FCFS in guaranteeing information freshness. It thus motivates us to consider the systems with a single buffer. The technics to derive age-related metrics for FCFS discipline systems cannot be applied to single buffer systems.
In summary, the information freshness metrics in systems with server vacations have not been fully investigated. It is still unclear which scheduling policy in the single buffer system achieves the smallest AoI or PAoI. The methodologies used in previous studies cannot be applied in our models to derive the information freshness metrics. This paper aims to provide a general mathematical framework to compute the information freshness in systems with server vacations. We also hope to understand how to manage the single buffer to guarantee information freshness for both independent and dependent vacation cases.

SYSTEM MODEL
To better describe the models we analyze in this paper, we first describe the single-queue system with server vacations. In Section 5 we will show that a polling system with multiple queues can be regarded as a single-queue system with non-i.i.d. vacations. To avoid introducing more notations at this stage, we leave the detailed description of the polling system in Section 5.
We consider a single-server system, where a data source generates data packets following a Poisson process with rate λ. The data packets are sent to the server as soon as they are generated. The processing time (service time) H for each packet is i.i.d. and generally distributed. Once a packet has been processed, the server takes a vacation. If the server finds no packet waiting in the buffer upon returning from a vacation, it takes another vacation. Otherwise, it starts processing the packet. This type of vacation scheme is called multiple vacation scheme, and it has wide applications (see [52], [53]). In Section 4, we discuss the case where each vacation period is i.i.d., and we discuss the case of non-i.i.d. vacations in Section 5.We suppose that the buffer at the server only holds the freshest data packet, i.e, the new packet will replace the old one in the buffer, if the buffer is available. The buffer availability is determined by scheduling policies defined as follows: • Conventional Buffer System (CBS) (see [54], [55], [56], [57]): In this system, the buffer becomes available only when the server is on vacation. Packets that arrive when the server is processing will be rejected. The vacation starts once a packet has been processed.
• Buffer Relaxation System (BRS) (see [55], [56]): The buffer becomes available as soon as the server starts serving. After completing a packet, the server will start a vacation, regardless of whether the buffer is empty or not.
• Conventional Buffer System with Preemption in Service (CBS-P): In this system, new arrival during processing will preempt the packet in service. The preempted packet will be discarded. The vacation starts once the system becomes empty.
When the vacation time becomes zero, CBS becomes M/G/1/1 system, BRS collapses into M/G/1/2* system, and CBS-P reduces to M/G/1/1/preemptive system. We will discuss these special cases in Subsection 4.5.
We consider age-related metrics in these systems. The age at time t, for a single queue system, is defined as ∆(t) = t − max{r {l} : C {l} ≤ t}, where C {l} is the completion time of the l th packet that completes processing at the server, and r {l} is the generation time of this packet. Note that the preempted or discarded packets are not indexed, and we refer to those packets that complete the service (incur age drops) as informative packets. The time-average age is then defined as∆ = lim T →∞ 1 T T 0 ∆(t)dt. By assuming the system is ergodic, we have E[∆] = lim t→∞ E[∆(t)] =∆, and we use the term "AoI" to refer E[∆]. While AoI is a useful metric to measure data freshness, many researchers also analyzed a metric called Peak Age of Information (PAoI) due to its tractability [2], [4], [39]. We let the l th peak of ∆(t) be A {l} , and the time-average peak value is then given byĀ = lim k→∞ 1 k k l=1 A {l} . Again, by assuming the ergodicity, we have the expected peak age value, i.e., , to be equal toĀ. In this paper, we use the term "PAoI" to refer E[A]. Throughout this paper, we let X * (s) denote the Laplace-Stieltjes Transform (LST) of random variable X, X * (n) (s) be the n th derivative of X * (s), and F X (x) be the cumulative distribution function (CDF) for X.

AGE OF INFORMATION FOR SYSTEMS WITH I.I.D. VACATIONS
We now consider three variations of the system, i.e., CBS, BRS, and CBS-P, which we defined earlier in Section 3, in the scenarios where each vacation V that the server takes is i.i.d. with LST V * (s). The AoI, PAoI, and variance of peak age of these three systems can be calculated by decomposing the peak age into different computable components. In this section, we only discuss the decomposition method that applies to non-preemptive service systems, i.e., CBS and BRS. The decomposition approach for CBS-P shares a similar idea but requires a different set of notations. So we leave the derivations for CBS-P in Appendix D of the supplementary material.
We now let S {l} be the time when the server starts processing the l th informative packet, and this informative packet is completed at time C {l} . From Fig. 1, we find that the l th age peak A {l} in CBS or BRS is the time span from the completion time C {l} of the l th informative packet, to the generation time (arrival time) of its previous informative packet, i.e., r {l−1} . This time span can then be divided into three components: waiting time G {l−1} (in queue) of the (l − 1) th informative packet, time span I {l} from the service starting time S {l−1} of the (l−1) th informative packet till the time when the l th informative packet starts service (which we call regenerative cycle), and service time H {l} of the l th packet. These three components are mutually independent for the following reasons.
and the system AoI can be given as Note that Equation (1) and (2) are for non-preemptive service systems, i.e., CBS and BRS. In Appendix A of the supplementary material we show that the PAoI and AoI for CBS-P can be calculated in a similar manner. Let the LST of G, I and H be G * (s), I * (s) and H * (s), and then the LST of A can be given as PAoI can be easily obtained by calculating the first moment of A * (s) at s = 0. The variance of peak age can be used as a metric to measure the age violations, and the variance of peak age can be given as In this work, H is a system parameter. We only need to obtain G * (s) and I * (s) to derive E[A], E[∆] and V ar(A). We now define a random variable that is useful in deriving G * (s). Let W be the period that starts from when the buffer becomes non-empty within a regenerative cycle I, to the end of the regenerative cycle. Note that W in CBS and CBS-P only starts when the server is on vacation (i.e., the system is empty). But W in BRS could start when the server is processing because the buffer becomes available as soon as processing starts. Another way to understand W is as follows. We consider a dummy system for each of the three systems. In each dummy system, packet replacement in the buffer is not allowed. Each dummy system has the same vacation distribution as its original counterpart, so that W is equivalent to the packet waiting time in the dummy system. A demonstrative graph about buffer status and period W is provided in Fig. 2. The following lemma reveals the relation between G * (s) and W * (s), which will be useful for our derivations later. Lemma 1. For CBS, BRS, and CBS-P, it holds that G * (s) = λ λ+s + s λ+s W * (λ + s).
Proof: Since G is the waiting time of the last packet that arrived during W , from Campbell Theorem (P173, Theorem 5.14 in [58] By unconditioning on W = t, the lemma can be proven. From Lemma 1 we can get Lemma 1 implies that one can derive G * (s) by obtaining the LST of waiting time in the dummy system. This result will be useful in our derivation later. It was shown in [17] that for systems with Poisson arrivals. However, this fact cannot be used to calculate AoI or variance of peak age, as the time period during which the buffer is empty (with expectation 1 λ ) and the time period W are not independent. As we will show later in this section, the relation between W * (s) and I * (s) could be involved. Therefore, to obtain the AoI, PAoI, and variance of peak age for CBS, BRS, and CBS-P with i.i.d. vacations, we will need to derive I * (s) first, and then characterize the relation between W * (s) and I * (s).

Conventional Buffer System
In this subsection, we will derive the information freshness metrics for CBS. Recall that in CBS, the buffer will not be available until the processing is completed, and the server will start a vacation once the buffer becomes empty. We provide the results for CBS in the following theorem.

Theorem 2. The AoI of CBS is
and the variance of peak age of CBS is for CBS. Notice that the period I starts once the server starts processing, and ends when the server returns from a vacation and observes a packet waiting in the buffer. Therefore I * (s) = E[e −s(H+B) ], where B is the time period during which the server is continuously on vacation within I. Note that B may consist multiple vacations. Let B * (s) be the LST of B. We let V 1 be the first vacation taken during B, and V ∞ be the last vacation. Let m(V 1 ) be the number of arrivals during vacation by further unconditioning on λ.
Since W only occurs in the last vacation, and the last vacation always has m( . By taking the second derivative of G * (s), we obtain Using Equation (4) we can obtain V ar(A).
In the proof of Theorem 2, we used the fact that W only occurs in the last V during period B that comprises a sequence of vacations. This fact also holds for BRS and CBS-P since we assume the multiple vacation scheme for all three systems. We So that the results can be obtained from Equations (1) and (2)

Buffer Relaxation System
In BRS, the server will take a vacation after processing a packet, and the packet arriving during processing will be processed only when the vacation is over. This service discipline is also called "gated" in some literature about vacation server systems (see [30], [59], [60]). This gated policy prevents the server from serving the buffer continuously without taking vacations when the arrival rate is large, which is helpful for systems where vacations have to be taken, such as the priority queue systems [17] where vacations correspond to "serving the prioritized queues". Also, as we will see in Section 4.4, BRS has the advantage over CBS in terms of minimizing PAoI. We now provide the AoI and PAoI for BRS in the following theorem.
. The PAoI of BRS is Proof: The proof relies on the renewal argument, which is similar to the proof of Theorem 2. The detail of the proof is shown in Appendix B of the supplementary material.
We can also obtain the variance of peak age for BRS, albeit its closed-form expression is involved. To obtain the variance of peak age, we need the LST of G, I, and H, as shown in Equation (4). The LST of I has been given in Theorem 4, which is The expression of W * (s) is given in the proof of Theorem 4, from which we can obtain One can see from Theorem 4 that both E[∆ BRS ] and E[A BRS ] are uniquely determined by the distributions of vacation time V and processing time H. We will show the numerical results for the variance of peak age for BRS in Section 6. In the next corollary, we provide the results for BRS with exponential service and exponential vacation times.
Corollary 5. For exponential vacation time with parameter v and exponential service time with parameter µ, we have Proof: The results follow from Theorem 4 with V * (s) = v v+s and H * (s) = µ µ+s . One can easily verify that E[A BRS ] decreases on λ, µ, and v by taking the derivative. It implies that increasing the generation, service, and vacation rates can reduce PAoI in this special case. In Section 6, we will show E[∆ BRS ] does not always decrease as the vacation rate v increases when the service time is not exponential.

Conventional Buffer System with Preemption in Service
Note that when allowing preemption in service, both CBS and BRS will reduce to CBS-P. Unlike the nonpreemptive service case, in CBS-P, the age peak cannot be decomposed as shown in Equation (1), simply because a packet that results in age peak may not have the waiting time G (as it may be a preemptive packet). A detailed decomposition approach for CBS-P is given in Appendix A of the supplementary material. The AoI and PAoI are CBS-P is given in the following theorem.

Theorem 6. The AoI for CBS-P is
and the PAoI for CBS-P is Proof: See Appendix A of the supplementary material.
We also find from Theorem 6 that E[∆ CBS−P ] and E[A CBS−P ] are uniquely determined by the distributions of vacation time V and processing time H. In the next corollary, we provide the expressions for E[∆ CBS−P ] and E[A CBS−P ] when both vacation and processing time distributions are exponential.

Corollary 7.
For exponential vacation time with parameter v and exponential service time with parameter µ, we have It can be observed from Corollary 7 that when service and vacation times are both exponential, E[∆ CBS−P ] is always upper bounded by E[A CBS−P ]. One can also verify that in this case, E[A CBS−P ] and E[∆ CBS−P ] are decreasing on parameters λ, µ, and v by taking the derivatives. The variance of peak age for CBS-P can also be obtained by the decomposition approach given in Appendix A, but its expression is involved. We will show it numerically in Section 6.

System Comparison
We mainly compare the AoI and PAoI under different policies in this subsection. The expressions for variance of peak age for BRS and CBS-P are involved, so that we will compare the variance of peak age numerically in Section 6. We first compare the PAoI for CBS and BRS in the following theorem. Theorem 8 shows that allowing the buffer to be available all the time, i.e., adopting BRS, can achieve a smaller PAoI than CBS. However, as shown in Fig. 3, BRS does not always have a smaller AoI than CBS, which implies that a policy that reduces PAoI does not necessarily reduce AoI. One can also find from Fig. 3 that CBS has a smaller AoI than BRS when both v and λ are large, but the advantage that CBS has over BRS is not significant. When both v and λ are small, E[∆ BRS ] could be much smaller than E[∆ CBS ]. This observation shows the advantage of adopting BRS when the vacation time is large and the data generation rate is low. We then compare CBS-P with CBS, and we have the following theorems. Note that Theorem 9 holds for systems with vacation time being general and service time being exponential. It does not always hold when the service time is nonexponential, as shown numerically in Section 6. In the following theorem, we provide a sufficient condition under which CBS-P will always have a PAoI no greater than CBS. for all s > 0, then CBS-P always has a PAoI no greater than that in CBS, when vacation times are i.i.d.
Proof: See Appendix E of the supplementary material.
Theorem 10 provides a simple condition for checking whether CBS-P has a smaller PAoI than CBS, and this sufficient condition does not rely on the vacation time distribution. We now provide some examples of how Theorem 10 can be applied. When the service time is exponential, we have . Then by Theorem 10 we can conclude that CBS-P has a PAoI than no greater than that in CBS, which is the same as our conclusion in Theorem 9. We next give an example where the processing time is Gamma distributed with parameters α and β. Since the LST of Gamma distribution is given by H * (s) = (1 + βs) −α , we have . By Bernoulli's inequality we have that (1 + βs) α ≥ 1 + αβs when α ≥ 1, and (1 + βs) α < 1+αβs when α < 1. From the fact that E[H] = αβ, we have when α ≤ 1. By Theorem 10, CBS-P will have an advantage over CBS when the service time is Gamma distributed with scale parameter α ≤ 1. For Gamma distributions with α ≤ 1, the probability density functions are more skewed than the exponential distribution. Therefore, Theorem 10 implies that when service time distribution is more skewed than the exponential distribution, allowing preemption in processing would reduce PAoI. A numerical study of this example is given in Fig. 4, from which we find that when α = 2, CBS-P does not always have a smaller PAoI than CBS. When α = 1 2 , CBS-P has a smaller PAoI than CBS for all the positive values of λ and v. Using the results of Theorems 2, 4, and 6, one can also derive other sufficient and necessary conditions under which one policy performs better than the others, by simply comparing the closed-form expressions. However, those conditions may be complicated due to the closedform expressions for information freshness metrics being involved.

Discussions for Systems without Server Vacation
When the server takes no vacations (or takes vacation infinitely fast), then CBS reduces to the M/G/1/1 nonpreemptive system, BRS becomes the M/G/1/2* system (the asterisk means that only the most recent packet is kept in the buffer as defined in [2], [34]), and CBS-P becomes M/G/1/1/preemptive system. Different variations of these systems have been discussed in [2], [4], [33], [34], [38], [39]. However, the variance of peak age in these single buffer systems has not been studied. We here provide the variance of peak age for the systems without server vacations as an extension of our discussion about vacation server systems. With the decomposition approach that we introduced earlier, we can provide the variance of peak age for M/G/1/1, M/G/1/2*, and M/G/1/1/preemptive systems, as shown in Table 1. The detailed derivations for Table 1 are provided in Appendix F of the supplementary material. When the service time is exponentially distributed, we have Table 2.
The AoI and PAoI results for M/M/1/1 and M/M/1/2* systems in Table 2 are the same as the ones obtained in [2]. The AoI and PAoI results for M/G/1/1/preemptive system in Table 1 are the same as the ones obtained in [33]. The AoI and PAoI results in Table 2 can also be obtained from Corollaries 3, 5 and 7, by letting v → ∞. These closed-form expressions enable us to evaluate the information freshness in M/M/1/1, M/M/1/2*, and M/M/1/1/Preemptive systems. Interestingly, no system always performs better or worse than the other two systems in terms of all the three metrics: AoI, PAoI, and variance of peak age. As shown in Table 3, although M/M/1/1/Preemptive has the smallest AoI among the three systems, it does not have a smaller PAoI or variance of peak age than the other two systems. M/M/1/1 turns out to perform worse than the other two systems in terms of PAoI and variance of peak age, but its AoI is not always greater than that in M/M/1/2* system. Note that Table 3 only compares the systems with exponential service times. When service times are generally distributed, one can easily verify that Theorems 8 and 10 still hold for systems with no vacations. More numerical comparisons are provided in Section 6.

PEAK AGE OF INFORMATION FOR SYSTEMS WITH DEPENDENT VACATIONS
We now extend our discussion to a more general case by allowing the vacations to be non-i.i.d. Equations (2) and (3) may no longer hold in this case as G and I may not be independent. However, we can still rely on Equation (1) to compute the PAoI for each system. This section will discuss the approach for deriving the exact solution for PAoI, and use PAoI to evaluate the information freshness under each scheduling policy. In Section 4.4, we showed that when vacation times are i.i.d., the PAoI in BRS is always no greater than that in CBS, and the PAoI in CBS-P is always no greater for BRS, and for CBS-P.
(6) As we mentioned in Section 4, W can be regarded as the waiting time of a packet in the dummy system where packet replacement in the buffer is not allowed. Once W * (s) is available, the closed-form expression of PAoI can be obtained. Equation (6) does not require the vacation to be i.i.d., so it can be applied to derive PAoI for general systems with server vacations. One only needs to obtain the LST of packet waiting time in the dummy system to calculate PAoI. In the remaining part of this section, we will focus our discussion on the polling system, as it is a system where the server takes non-i.i.d. vacations (see [61]). We will show how to obtain W * (s) for polling systems, and then derive the PAoI for polling systems based on Equation (6).
A polling system is a queueing system that contains a single server and k classes of packets. Each packet class would have its own queue, so there are k queues in the system. The server serves packets by switching between queues, and a switchover time is incurred when the server switches from one queue to another. A demonstrative graph of polling systems is provided in Fig. 5. Polling systems have a wide application in communication networks and other networks (see [19], [62], [63]), but the PAoI in polling systems has not been fully studied. Specifically, suppose there are multiple data nodes in the underwater sensor network example which we discussed in Section 1 (also see [10], [11]). In this case, we can model the underwater system as a polling system, where each data node can be modeled as a queue/buffer, and the autonomous vehicle can be regarded as the server that collects/processes data from each node in a periodic manner. In this paper, we are interested in single buffer systems, so we assume that each queue has a single buffer that can hold only one packet at a time. Similar to our discussion in Section 4, we assume that only the most recently arrived packet is kept in the buffer, and we consider three variations of the polling system by making different assumptions about the buffer availability and service preemption. We still denote the polling systems under the three scheduling policies as CBS, BRS, and CBS-P. In CBS, the buffer is not available until the current packet completes its service. When the server is busy processing, newly arrived packets in this queue will be rejected. In BRS, the buffer becomes available once the service has started, and the new arrival during the service time will be served in the next polling instant. In CBS-P, the new arrival will preempt the packet in service, and the preempted packet will be discarded. The server will switch to the next queue when the service of a packet is complete. In all these three systems, the server will start another switching process immediately if it observes an empty queue. We assume that the arrival process of packets in each queue i follows a Poisson process with rate λ i , and the service time H i for packets at each queue is i.i.d. with mean h i and LST H * i (s). The switchover time U ij from queue i to queue j has mean u ij and LST U * ij (s). In the remaining part of this section, we use the subscript i to denote the parameter for queue i in the polling system.
There are multiple widely used routing schemes that determine which queue to switch to next for the server. Routing schemes include cyclic [55], [57], [64], [65], random polling [54], and Markovian polling [56], [66]. In this work, we focus on the Markovian polling scheme since the random polling and cyclic polling schemes are both special cases of the Markovian polling scheme, as we will show later. In the Markovian polling scheme, after serving queue i, the probability of serving queue j next is given by p ij . Considering all the possible queue indices before and after switching, we can characterize the switching process by a discrete Markov chain with transition matrix P = [p ij ]. We assume that P is irreducible positive recurrent.
For the cyclic polling scheme, the transition matrix is given by Two other polling schemes were discussed in [56]. One is called load-oriented-policy (LOP), which is defined by the transition matrix with p ij = λj k l=1 λ l for all i and j. The other polling scheme is called symmetric random polling, in which p ij = 1 k for all i and j. We will show the performance of these schemes numerically in Section 6.
The service process for each queue in polling systems can be modeled as a single server with multiple vacations: when the server polls the queue, it serves the packet if the queue is not empty, and takes a vacation (switches out and serves other queues) once the service completes; if the queue is empty when polled, the server takes another vacation. It is important to note that as pointed out by Kofman in [61], even when the cyclic polling scheme is applied, the vacations that the server takes in a polling system are noni.i.d. Suppose W i is the packet waiting time in queue i of the dummy system, with LST W * i (s). Our methods for deriving W * (s) for systems with i.i.d. vacations in Section 4 cannot be applied here for deriving W * i (s) in polling systems. Chung et al. [56] provided the LST for waiting time W i in the dummy systems of CBS and BRS i.e., without packet replacement in the buffer. We can borrow the expressions of W * i (s) for our system as whether there is preemption or not in the buffer for CBS and BRS does not influence the vacation process. We now summarize how W * i (s) is obtained by Chung et al. [56] and use it to derive the PAoI for queue i (i.e., E[A i ]). The main idea in [56] of deriving W * i (s) is to solve Equation (7), where F i (z 1 , ..., z k ) is a probability generating function with F i (1, ..., 1) = 1, (π 1 , ..., π k ) is the stationary distribution of the transition matrix P , for BRS, and for CBS-P.
Chung et al. [56] only showed that Equation (7) holds for CBS and BRS. However, we show that Equation (7) also holds for CBS-P, withH * j given in Equation (8). The analysis is as follows. In CBS-P, the server switches out from queue j only when one packet has been completely served. If we regard the period during which the server is continuously serving packets as the service time for "one packet", then we can also regard CBS-P as CBS. The only difference is in the distribution of completing one packet. In CBS, completing one packet in queue j takes H j amount of time. While in CBS-P, completing one packet in queue j takes time L j with LST A detailed derivation of Equation (9) can be found in Appendix A of the supplementary material. Then, the formula ofH * j for CBS-P in Equation (8) is obtained by simply combining Equation (9) with the formulaH * j for CBS in Equation (8). Equation (7) thus holds for CBS-P as well, with onlyH * j being different from CBS. Solving the system (7) is quite involved, as shown in [56]. However, the expected value of W i can be obtained by solving the system (7) with z j = 0 or 1 for j = 1, ..., k, where only k(2 k −1) linear equations need to be solved. The expected time W i is then given as E[W i ] = γi λiαi − 1 λi , where α i = 1 − F i (1, ..., i 0, ..., 1) (the notation F i (1, ..., i 0, ..., 1) means that z i = 0 and z l =i = 1 in F i (z 1 , ..., z k )) and γ i is given in Equation (10).
Note here we only need to solve system (11) for z j = 0 or 1 for j = 1, ..., k to obtain W * i (λ i ), so that k 2 2 k number of equations need to be solved. After solving system (7) and (11), the closed-form expression of PAoI can be obtained from the Equation (12), and we can also have the following theorem.

(12)
Theorem 11. If the service time for each queue is exponentially distributed in a polling system, then CBS-P will always have a PAoI than that in CBS.
Proof: See Appendix H of the supplementary material.
However, when the service time is not exponential, CBS-P does not always have a smaller PAoI than CBS. We will show more computational results in Section 6.

NUMERICAL STUDY: VERIFICATION, FINDINGS, AND EXPLANATIONS
In this section, we first perform a set of numerical experiments for systems with i.i.d. vacations, and then provide the numerical results to verify the exact solution of PAoI for polling systems. We then provide the results for the polling system under different Markovian polling schemes and develop insights.

CBS, BRS and CBS-P with i.i.d. Vacations
We begin our discussion by comparing the AoI, PAoI, and variance of peak age for CBS, BRS, and CBS-P, as shown in Fig. 6. In each subfigure of Fig. 6, the simulation results match the exact results, which verifies our analysis. Fig. 6(a) and Fig. 6(d) compare the AoI for these three systems under different service and vacation times. It is shown in Fig. 6(a) that CBS-P has the advantage over the other two systems in minimizing AoI, when service time is exponentially distributed. When the arrival rate is large, this advantage becomes more significant. However, in Fig.  6(d) where service time is deterministic, AoI in CBS-P is greater than that in the other two systems when the arrival rate is large. In CBS-P, the server would process the new packet when an arrival preempts the service. The server will continuously serve only until an inter-arrival time is smaller than the constant service time. If the arrival rate is large (which means the expected inter-arrival time is small), then the probability of the inter-arrival time being smaller than the constant service time is small. Thus the AoI of CBS-P becomes large when the arrival rate is large for deterministic service time cases. In Section 6.2 we will observe a similar phenomenon when the server does not take vacations.
In Fig. 6(b) and Fig. 6(e) we compare the PAoI of these three systems. We find that CBS always has a larger PAoI than BRS for both exponential and deterministic service times, which matches Theorem 8. It can be observed from Fig. 6(a) and Fig. 6(b) that CBS-P has smaller AoI and PAoI than CBS for the exponential service cases, which matches the results in Theorem 9. In Fig. 6(c) and Fig. 6(f), we compare the variance of peak age for these three systems. When service time is exponential, CBS has a larger variance of peak age than the other two systems when λ is large. From all the subfigures in Fig. 6, we find that for both CBS and BRS, increasing the arrival rate would reduce AoI, PAoI, and variance of peak age for the given service time and vacation time distributions.
In Fig. 7 we plot the age metrics as functions of the vacation rate v. We compare the metrics with H ∼ Gamma(0.1, 100) and H ∼ exp(0.1). Interestingly, we find that reducing the vacation time decreases the PAoI and V ar(A) for CBS, BRS, and CBS-P, but it does not always reduce the AoI, as shown in Fig. 7(a). When H ∼ Gamma(0.1, 100) Fig. 7 that the AoI, PAoI, and variance of peak age under CBS-P is significantly smaller than those under CBS and BRS when H ∼ Gamma(0.1, 100), which shows the advantage of having preemption in processing when H is Gamma distributed with a small scale parameter.

Systems with No Vacations
We next compare the AoI, PAoI, and variance of peak age for M/G/1/1, M/G/1/2*, and M/G/1/1/preemptive systems under exponential and deterministic service cases. The simulation results match the exact results in Section 4.5 for each system, as shown in Fig. 8. We find that although the AoI in M/G/1/2* system is not always smaller than that in M/G/1/1 system, the PAoI and variance of peak age in M/G/1/2* system are smaller than those in M/G/1/1 system. Especially when the arrival rate is low, the advantage that M/G/1/2* system has over M/G/1/1 system in minimizing PAoI and variance of peak age becomes significant. For M/G/1/1/preemptive system, the AoI, PAoI, and variance of peak age will increase dramatically when the arrival rate becomes large when the service time is deterministic. We also find that when the service time is exponential, M/M/1/1 system has the largest variance of peak age among all the three systems, which verifies our discussion in Section 4.5. When the service time is deterministic, M/D/1/2* system has a lower variance of peak age than the other two systems.

Polling Systems
We now perform numerical studies for different polling systems. In Fig. 9 we compare the exact solutions of PAoI that we provided in Section 5 with the simulation results for the polling system with k = 3 and cyclic polling scheme. We find that the exact results match the simulation results from Fig. 9. Interestingly, we find that increasing the traffic load will not always reduce the PAoI for CBS, BRS, and CBS-P. This observation is different from that for i.i.d. vacation systems, where increasing the traffic rate can reduce the PAoI when service time is exponential. As we observed from Fig. 9(c), the PAoI of queue 3 in all three systems will increase when the traffic load increases. This phenomenon is because the numerical test of Fig. 9 is based on the cyclic polling scheme. For queue 3, the vacation time increases since the other queues are more likely to be served during the server's vacation. Although increasing the traffic load will reduce the waiting time of an informative packet (i.e., the server is more likely to find a fresh packet when a vacation is over), the increase in vacation time for queue 3 would overshadow the reduction in G, so that the PAoI is increasing for queue 3 as the total traffic load increases. The numerical study for a polling system with k = 8 and cyclic scheme is provided in Table 4. We choose the same system parameters as the numerical study in [55] by heavily loading two queues (each queue takes 45% of the total load). We proved in Theorem 8 that BRS always has a no greater PAoI than CBS when the server's vacations are i.i.d. However, Table 4 shows that the PAoI of BRS is not always smaller than PAoI of CBS in the polling system. [61]. The non-i.i.d. vacations in the polling system thus prevent Theorem 8 from holding true. However, we can see that when the arrival rate is low, BRS still has a smaller PAoI than CBS. Table 4 also shows that PAoI in CBS is larger than that in CBS-P when the service time is exponential, as we proved in Theorem 11. Now we consider the PAoI of the polling system under different polling schemes described in Section 5. We keep  the same set of parameters for service and switching time for Table 5 and 6, and provide the computational results for cyclic, LOP, and symmetric random polling schemes with different total traffic loads. From both Tables 5 and 6, we find that cyclic and symmetric random schemes perform similarly when the total traffic load is low. When the traffic load is high, the symmetric scheme provides a lower PAoI for those queues with high arrival rates than the cyclic scheme, but provides higher PAoI for other queues than the cyclic scheme. LOP has a lower PAoI than the other  two schemes for queues with high arrival rates, especially when the total traffic load is high. However, LOP causes very large PAoI for queues with low arrival rates. This is because the server under LOP would serve queues with high arrival rates more frequently. Note that Theorem 11 does not specify the polling scheme for CBS or CBS-P. So when service time is exponential, CBS-P will always have a PAoI no greater than that in CBS regardless of the polling scheme, as shown in Tables 5 and 6.
Next, we consider the average PAoI across queues (i.e., 1 under those three different Markovian polling schemes, as shown in Fig. 10. The average PAoI across queues was also considered in [17], [67]. In Fig. 10 we find that the cyclic scheme achieves the lowest average PAoI under different traffic loads for CBS, BRS, and CBS-P. LOP has the highest average PAoI among these three polling schemes. This is because, under LOP, the server would likely serve the queues with high arrival rates, and queues with low arrival rates would be polled infrequently. Since PAoI is more sensitive to the arrival rate change when the arrival rate is low (which we can observe from Fig. 6 and 8), the PAoI reduction in queues with high arrival rates would be overshadowed by the PAoI increase in queues with low arrival rates, when LOP is applied. This observation implies that if one wants to reduce the average PAoI for the entire system, a potential strategy is to avoid polling specific queues too frequently. Therefore, policies with even polling frequency for queues, such as the cyclic scheme, are recommended for achieving a small average PAoI.

CONCLUDING REMARKS
In this paper, we investigated the information freshness on queueing systems with server vacations. We evaluated the performance of three scheduling policies, i.e., CBS, BRS, and CBS-P, in systems with both i.i.d. vacations and noni.i.d. vacations. For i.i.d. vacation systems, we provided a general decomposition approach that decomposes the system age into independent components. We further used the decomposition approach to derive information freshness metrics such as AoI, PAoI, and the variance of peak age for these three policies. We showed that BRS always achieves a PAoI no greater than CBS regardless of the service time and vacation time distributions, and BRS has the advantage over CBS in minimizing information freshness metrics when the arrival rate is low. We also proved that the AoI and PAoI in CBS-P are always no greater than those in CBS when the service time is exponential, and we showed that CBS-P has the advantage over CBS in minimizing information freshness metrics when the service time is Gamma distributed with a small scale parameter. However, no system always performs better than the other two in terms of AoI, PAoI, and variance of peak age altogether. We also found that reducing vacation time does not always reduce AoI, due to the special definition of AoI.
For systems with non-i.i.d. vacations, we investigated the polling system as an example. We provided an approach to calculate the PAoI for the three policies in the polling system and proved that when service times are exponential, CBS-P has a PAoI no greater than that in CBS, under any Markovian polling schemes. Our numerical studies showed that BRS no longer has a smaller PAoI than CBS in the polling system. However, when the arrival rate is low, the PAoI in BRS can still be much smaller than that in CBS. We also found that the cyclic polling scheme performs better than the symmetric scheme and LOP in reducing the average PAoI across queues in polling systems. In our future work, we will consider the closed-form expressions of AoI for systems with non-i.i.d. vacations, such as polling systems. We will also consider the optimal switching scheme and scheduling scheme for polling systems in the future.    Proof: Different from the case of non-preemptive service, in the case where service is preempted by new arrivals, we decompose the age peak into three pieces (13) where D {l−1} is the delay (time in the system) of an informative packet, B {l} is the time period when the server is on vacation during the l th regenerative cycle (the same as we defined in Theorem 2), and L {l+1} is the time when the server is processing during the l th regenerative cycle. We let r j , S j , and C j be the arrival time, time to start service, and completion time of the j th packet that arrives in the system from time 0. Note that not all the packets have S j and C j , as some packets are preempted and discarded. A demonstrative graph is given in Fig. 11, and the three decomposed components are mutually independent. This is because B {l} is the time when the server is on vacation, which is independent of delay D {l−1} and processing time L {l+1} . L {l+1} is independent of D {l−1} . Therefore the AoI of this system can be given as We now derive the LST of D, denoted as D * (s). We first notice that if the service time of a packet H is smaller than the inter-arrival time T , then the packet is served without being preempted. Therefore, all the packets that are eventually processed must have the service time smaller than the inter-arrival time. If the packet that we serve arrives during the last vacation, then its delay D is its waiting time G plus its service time. If it arrives during service (it preempts the previous packet in service), then the delay is its service time only. Systems. The l th age peak is decomposed into three components: is the delay of the (l − 1) th informative packet, B {l} is period when the server is on vacation, and L {l+1} is the time period when the server is serving.
In CBS-P, packet indices may differ from the indices for age peaks. In this example, packet j is preempted by packet j + 1 at time r {j+1} , and packet j + 1 is not preempted by any packet.
= H * (λ + s) G * (s) + 1 H * (λ) − 1 . . Now we derive the LST for L, i.e., L * (s). Notice that if the inter-arrival time T is greater than service time H, then the packet is processed without being preempted. If the inter-arrival time T is smaller than H, then a new period L is started after T . We can then get L * (s) = H * (s + λ) s s+λ + λ s+λ H * (s + λ) , and The PAoI for the system can now be given as

APPENDIX B PROOF FOR THEOREM 4.
Proof: We first derive I * (s) in BRS. Since each I starts with processing a packet with processing time H, if there is more than one arrival during the processing time H, then the server only takes one vacation after processing the current packet. If there is no arrival during this processing time, the server takes vacations until a packet is observed in buffer when a vacation is over. Therefore E[G] = 1 λ + V * (1) (λ)H * (λ) + V * (λ)H * (1) (λ) + V * (1) (λ) 1−V * (λ) V * (λ)H * (λ). Using Equation (1) and (2) we can then obtain the PAoI and AoI of BRS.