Age-Optimal Multi-Flow Status Updating with Errors: A Sample-Path Approach

I. INTRODUCTION

In many information-update and networked control systems, such as news updates, stock trading, autonomous driving, remote surgery, robotics control, and real-time surveillance, information usually has the greatest value when it is fresh. A metric for information freshness, called age of information or simply age, was introduced in [2], [3]. Consider a flow of status update packets that are sent from a source to a destination through a channel. Let U(t) be the time stamp (i.e., generation time) of the newest update that the destination has received by time t. Age of information, as a function of time t, is defined as [TeX:] $$\Delta(t)=t-U(t),$$ which is the time elapsed since the newest update was generated.

In recent years, there have been a lot of research efforts on (i) analyzing the distributional quantities of Age [TeX:] $$\Delta(t)$$ for various network models and (ii) controlling [TeX:] $$\Delta(t)$$ to keep the destination’s information as fresh as possible, e.g., [1]–[44]. If there is a single flow of status update packets, the Last Generated, First Served (LGFS) update transmission policy, in which the last generated packet is served the first, has been shown to be (nearly) optimal for minimizing the age process [TeX:] $$\{\Delta(t), t \geq 0\}$$ in a stochastic ordering sense for queueing networks with multiple servers or multiple hops [14]–[18]. These results hold for arbitrary packet generation times at the information source (e.g., a sensor) and arbitrary packet arrival times at the transmitter’s queueing buffer; they also hold for minimizing any non-decreasing functional [TeX:] $$\phi(\{\Delta(t), t \geq 0\})$$ of the age process [TeX:] $$\{\Delta(t), t \geq 0\}$$. If packets arrive at the queue in the order of their generation times, then the LGFS policy reduces to the Last Come, First Served (LCFS) policy, thus demonstrating the (near) age-optimality of the LCFS policy. These studies motivated us to delve deeper into the design of scheduling policies to minimize age of information in more complex networks involving multiple flows of status update packets and transmission errors, where each flow is from one source node to a destination node. In this scenario, the transmission scheduler must compare not only packets from the same flow, but also packets from different flows. Additionally, the presence of transmission errors adds an additional layer of complexity to the scheduling problem. As a result, addressing these challenges becomes crucial in achieving efficient age minimization in such systems.

In this paper, we investigate age-optimal scheduling in continuous-time and discrete-time status updating systems that involve multiple flows, multiple servers, and transmission errors, as illustrated in Figure 1. Each server can transmit packets to their respective destinations, one packet at a time. Different servers are not allowed to simultaneously transmit packets from the same flow. We assume that the packet generation and arrival times are synchronized across the flows. In other words, when a packet from flow n arrives at the queue at time [TeX:] $$A_i$$, with its generation time denoted as [TeX:] $$S_i$$ (where [TeX:] $$S_i \leq A_i$$), one corresponding packet from each flow simultaneously received at time [TeX:] $$A_i$$, and all of these packets were generated at the same time [TeX:] $$S_i$$. In practice, synchronized packet generations and arrivals occur when there is a single source and multiple destinations (e.g., [ 22]), or in periodic sampling where multiple sources are synchronized by the same clock, which is common in monitoring and control systems (e.g., [ 45], [ 46]). We develop a unifying sample-path approach and use it to show that the proposed scheduling policies can achieve optimal or near-optimal age performance in a quite strong sense (i.e., in terms of stochastic ordering of agepenalty stochastic processes). The contributions of this paper are summarized as follows:

· Let [TeX:] $$\Delta(t)$$ denote the age vector of multiple flows. We introduce an age penalty function [TeX:] $$p_t(\boldsymbol{\Delta}(t))$$ to represent the level of dissatisfaction for having aged information at the destinations at time t, where [TeX:] $$p_t$$ can be any time-dependent, symmetric, and non-decreasing function of the age vector [TeX:] $$\Delta(t)$$.

· For continuous-time status updating systems with one or multiple flows, one or multiple servers, and i.i.d. exponential transmission times, we propose a Preemptive, Maximum Age First, Last Generated First Served (PMAF- LGFS) scheduling policy.¹ If the packet generation and arrival times are synchronized across the flows, then for any age penalty function [TeX:] $$p_t$$ defined above, any number of flows, any number of servers, any synchronized packet generation and arrival times, and regardless the presence of transmission errors or not, the P-MAF-LGFS policy is proven to minimize the continuous-time age penalty process [TeX:] $$\left\{p_t(\boldsymbol{\Delta}(t)), t \geq 0\right\}$$ among all causal policies in a stochastic ordering sense (see Theorem 1 and Corollary 1). Theorem 1 is more general than [1, Theorem 1], as the latter was established for the special case of single-server status updating systems without transmission errors. In addition, if packet replication is allowed, we show that a Preemptive, Maximum Age First, Last Generated First Served scheduling policy with packet Replications (P-MAF-LGFS-R) is age-optimal for minimizing the age penalty process [TeX:] $$\left\{p_t(\boldsymbol{\Delta}(t)), t \geq 0\right\}$$ in terms of stochastic ordering (see Corollary 2).

¹ This new P-MAF-LGFS policy is suitable for both single-server and multiserver systems, whereas the original P-MAF-LGFS policy, as presented in [1], was specifically tailored for single-server scenarios.

· For continuous-time status updating systems with one or multiple flows, one or multiple servers, and i.i.d. New- Better-than-Used (NBU) transmission times (which include exponential transmission times as a special case), age-optimal multi-flow scheduling is quite difficult to achieve. In this case, we consider an age lower bound called the Age of Served Information and propose a Non- Preemptive, Maximum Age of Served Information First, Last Generated First Served (NP-MASIF-LGFS) scheduling policy. The NP-MASIF-LGFS policy is shown to be near age-optimal. Specifically, it is within an additive gap from the optimum for minimizing the expected timeaverage of the average age of the flows, where the gap is equal to the mean transmission time of one packet (see Theorem 2 and Corollary 3). This additive sub-optimality gap is quite small.

· For discrete-time status updating systems with one or multiple flows and one or multiple servers, we propose a Discrete Time, Maximum Age First, Last Generated First Served (DT-MASIF-LGFS) scheduling policy. If the packet generation and arrival times are synchronized across the flows, then for any age penalty function pt, any number of flows, any number of servers, any synchronized packet generation and arrival times, and regardless the presence of transmission errors or not, the DT-MAFLGFS policy is proven to minimize the discrete-time age penalty process [TeX:] $$\left\{p_t(\Delta(t)), t=0, T_s, 2 T_s, \ldots\right\}$$ among all causal policies in a stochastic ordering sense, where [TeX:] $$T_s$$ is the fundamental time unit of the discrete-time systems (see Theorem 3).

Our results can be potentially applied to: (i) cloud-hosted Web services where the servers in Figure 1 represent a pool of threads (each for a TCP connection) connecting a front-end proxy node to clients [47], (ii) industrial robotics and factory automation systems where multiple sensor-output flows are sent to a wireless AP and then forwarded to a system monitor and/or controller [48], and (iii) Multi-access Edge Computing (MEC) that can process fresh data (e.g., data for video analytics, location services, and IoT) locally at the very edge of the mobile network.

II. RELATED WORK

The age of information concept has attracted a significant surge of research interest; see, e.g., [1]–[43] and a recent survey [44]. Initially, research efforts were centered on analyzing and comparing the age performance of different queueing disciplines, such as First-Come, First-Served (FCFS) [3], [5], [9], [11], preemptive and non-preemptive Last-Come, First- Served (LCFS) [4], [20], and packet management [8], [10]. In [14]–[18], a sample-path approach was developed to prove that Last-Generated, First-Served (LGFS)-type policies are optimal or near-optimal for minimizing a broad class of age metrics in multi-server and multi-hop queueing networks with a single packet flow. When packets arrive in the order of their generation times, the LGFS policy becomes the well-known Last Come, First Served (LCFS) policy. Hence, the LCFS policy is (near) age-optimal in these queueing networks.

In recent years, researchers have expanded the aforementioned studies to consider age minimization in multi-flow discrete-time status updating systems [22]–[25]. In [22], the authors utilized a sample-path method to establish the optimality of the Maximum Age First (MAF) policy in minimizing the time-averaged sum age of multiple flows. This investigation focused on discrete-time systems with periodic arrivals and a single broadcast channel, which is susceptible to i.i.d. transmission errors. Moreover, in [23], a Markov decision process (MDP) approach was adopted to prove that the MAF policy minimizes the time-averaged sum age of multiple flows in discrete-time systems with Bernoulli arrivals, a single broadcast channel, and no buffer. In this bufferless setup, arriving packets are discarded if they cannot be transmitted immediately in the arriving time slot. In [24], the authors studied discrete-time systems with multiple flows and multiple ON/OFF channels, where the state of each channel (ON/OFF) is known for making scheduling decisions. It was demonstrated that a Max-Age Matching policy is asymptotically optimal for minimizing non-decreasing symmetric functions of the age of the flows as the numbers of flows and channels increase. In [25], it was shown that the MAF policy minimizes the Maximum Age of multiple flows in discretetime systems with periodic arrivals and a single broadcast channel susceptible to i.i.d. transmission errors, where the transmission error probability may vary across the flows. In [49], a sample-path method was employed to demonstrate that the round-robin policy minimizes a service regularity metric called time-since-last-service in discrete-time systems with multiple flows and transmission errors. In the definition of time-since-last-service, a user can receive service even if its queue is empty. Consequently, time-since-last-service bears similarities to the age of information concept, albeit these two metrics are different. The present paper, alongside its conference version [1], complements the aforementioned studies in several essential ways: (i) It considers general time-dependent, symmetric, and non-decreasing age penalty functions [TeX:] $$p_t$$. (ii) Both continuous-time and discrete-time systems with multiple flows, multiple channels (a.k.a. servers), and transmission errors are investigated. (iii) The paper establishes near ageoptimal scheduling results in scenarios where achieving ageoptimality is inherently challenging.

III. SYSTEM MODEL

A. Notations and Definitions

We use lower case letters such as [TeX:] $$x \text { and } \boldsymbol{x} \text {, }$$ respectively, to represent deterministic scalars and vectors. In the vector case, a subscript will index the components of a vector, such as [TeX:] $$x_i.$$ We use [TeX:] $$x_{[i]}$$ to denote the i-th largest component of vector [TeX:] $$\boldsymbol{x}.$$ Let 0 denote a vector with all 0 components. A function [TeX:] $$f: \mathbb{R}^n \rightarrow \mathbb{R}$$ is termed symmetric if [TeX:] $$f(x)=f\left(x_{[1]}, \ldots, x_{[n]}\right)$$ for all [TeX:] $$x \in \mathbb{R}^n.$$ A function [TeX:] $$f: \mathbb{R}^n \rightarrow \mathbb{R}$$ is termed separable if there exists functions [TeX:] $$f_1, \ldots, f_n$$ of one variable such that [TeX:] $$f(x)=\sum_{i=1}^n f_i\left(x_i\right)$$ for all [TeX:] $$\boldsymbol{x} \in \mathbb{R}^n.$$ The composition of functions f and g is denoted by [TeX:] $$f \circ g(x)=f(g(x)).$$ For any n-dimensional vectors [TeX:] $$\boldsymbol{x} \text{ and } \boldsymbol{y}$$, the elementwise vector ordering [TeX:] $$x_i \leq y_i, i=1, \ldots, n,$$ is denoted by [TeX:] $$\boldsymbol{x} \leq \boldsymbol{y}.$$ Let [TeX:] $$\mathcal{A} \text { and } \mathcal{U}$$ denote sets and events. For all random variable X and event [TeX:] $$\mathcal{A},$$ let [TeX:] $$[X \mid \mathcal{A}]$$ denote a random variable with the conditional distribution of X for given [TeX:] $$\mathcal{A}.$$ We will need the following definitions:

Definition 1. Stochastic Ordering of Random Variables [50]: A random variable X is said to be stochastically smaller than another random variable Y , denoted by [TeX:] $$X \leq_{\mathrm{st}} Y,$$ if

Definition 2. Stochastic Ordering of Random Vectors [50]: A set [TeX:] $$\mathcal{U} \subseteq \mathbb{R}^n$$ is called upper, if [TeX:] $$\boldsymbol{y} \in \mathcal{U}$$ whenever [TeX:] $$\boldsymbol{y} \geq \boldsymbol{x}$$ and [TeX:] $$x \in \mathcal{U}.$$ Let [TeX:] $$\boldsymbol{X} \text{ and } \boldsymbol{Y}$$ be two n-dimensional random vectors, [TeX:] $$\boldsymbol{X}$$ is said to be stochastically smaller than [TeX:] $$\boldsymbol{Y}$$, denoted by [TeX:] $$\boldsymbol{X} \leq_{\mathrm{st}} \boldsymbol{Y},$$ if

Definition 3. Stochastic Ordering of Stochastic Processes [50]: Let [TeX:] $$\{X(t), t \in[0, \infty)\} \text { and }\{Y(t), t \in[0, \infty)\}$$ be two stochastic processes, [TeX:] $$\{X(t), t \in[0, \infty)\}$$ is said to be stochastically smaller than [TeX:] $$\{Y(t), t \in[0, \infty)\}$$, denoted by [TeX:] $$\{X(t), t \in[0, \infty)\} \leq_{\text {st }}\{Y(t), t \in[0, \infty)\},$$ if for all integer n and [TeX:] $$0 \leq t_1\lt t_2\lt \ldots\lt t_n,$$ it holds that

A functional is a mapping from functions to real numbers. A functional ϕ is termed non-decreasing if [TeX:] $$\phi(\{X(t), t \in [0, \infty)\}) \leq \phi(\{Y(t), t \in[0, \infty)\})$$ whenever [TeX:] $$X(t) \leq Y(t)$$ for [TeX:] $$t \in[0, \infty).$$ We remark that [TeX:] $$\{X(t), t \in[0, \infty)\} \leq_{\mathrm{st}}\{Y(t), t \in [0, \infty)\}$$ if, and only if, [50]

holds for all non-decreasing functional ϕ, provided that the expectations in (4) exist.

B. Queueing System Model

Consider the status updating system illustrated in Fig. 1, where N flows of status update packets are sent through a queue with an infinite buffer and M servers. Let [TeX:] $$s_n$$ and [TeX:] $$d_n$$ denote the source and destination nodes of flow n, respectively. It is possible for multiple flows to share either the same source node or the same destination node.

A scheduler assigns packets from the transmitter’s queue to servers over time. The queue contains packets from different flows, and each packet can be assigned to any available server. Each server is capable of transmitting only one packet at a time. Different servers are not allowed to simultaneously transmit packets from the same flow. The packet transmission times are independent and identically distributed (i.i.d.) across both servers and packets, with a finite mean [TeX:] $$1 / \mu.$$ The packet transmissions are susceptible to i.i.d. errors with an error probability [TeX:] $$q \in[0,1),$$ occurring at the end of the packet transmission time intervals. The scheduler is made aware of transmission errors once they occur. In the event of such a error, the packet is promptly returned to the queue, where it awaits the next transmission opportunity. if q = 0, then there is no transmission errors.

The system starts to operate at time t = 0. The i-th packet of flow n is generated at the source node [TeX:] $$s_n$$ at time [TeX:] $$S_{n,i},$$ arrives at the queue at time [TeX:] $$A_{n,i},$$ and is delivered to the destination [TeX:] $$d_n$$ at time [TeX:] $$D_{n,i},$$ such that [TeX:] $$0 \leq S_{n, 1} \leq S_{n, 2} \leq \ldots \text { and } S_{n, i} \leq A_{n, i} \leq D_{n, i}.$$² We consider the following class of synchronized packet generation and arrival processes:

² This paper allows [TeX:] $$S_{n, i} \leq A_{n, i},$$ which is more general than the conventional assumption [TeX:] $$S_{n, i} = A_{n, i}$$ adopted in related literature.

Definition 4. Synchronized Packet Generations and Arrivals: The packet generation and arrival processes are said to be synchronized across the N flows, if there exist two sequences [TeX:] $$\left\{S_1, S_2, \ldots\right\}$$ and [TeX:] $$\left\{A_1, A_2, \ldots\right\}$$ such that for all [TeX:] $$i=1,2, \ldots,$$ and [TeX:] $$n=1, \ldots,N$$

We note that the sequences [TeX:] $$\left\{S_1, S_2, \ldots\right\}$$ and [TeX:] $$\left\{A_1, A_2, \ldots\right\}$$ in (5) are arbitrary. Hence, out-of-order arrivals, e.g., [TeX:] $$S_i\lt S_{i+1}$$ but [TeX:] $$A_i\gt A_{i+1}$$, are allowed. In the special case that the system has a single flow (N = 1), the packet generation times [TeX:] $$S_{n,1}$$, and arrival times [TeX:] $$A_{n,1}$$ of this flow are arbitrarily given without any constraint. Age-optimal scheduling in this special case has been previously studied in [14]–[17].

Let π represent a scheduling policy that determines how to assign packets from the queue to servers over time. Let Π denote the set of all causal scheduling policies in which the scheduling decisions are made based on the history and current states of the system. A scheduling policy is said to be preemptive if a busy server can stop the transmission of the current packet and start sending another packet at any time; the preempted packet is stored back to the queue, waiting to be sent at a later time. A scheduling policy is said to be non-preemptive if each server must complete the transmission of the current packet before initiating the service of another packet. A scheduling policy is said to be work-conserving if all servers remain busy whenever the queue contains packets waiting to be processed. We use [TeX:] $$\Pi_{n p}$$ to denote the set of nonpreemptive and causal scheduling policies, where [TeX:] $$\Pi_{n p} \subset \Pi .$$ Let

denote the synchronized packet generation and arrival times of the flows. We assume that the packet generation/arrival times [TeX:] $$\mathcal{I},$$ the packet transmission times, and the transmission errors are governed by three mutually independent stochastic processes, none of which are influenced by the scheduling policy.

C. Age Metrics

Among the packets that have been delivered to the destination [TeX:] $$d_n$$ of flow n by time t, the freshest packet was generated at time

Age of information, or simply age, for flow n is defined as [2], [3]

which is the time difference between the current time t and the generation time [TeX:] $$U_n(t)$$ of the freshest packet currently available at destination [TeX:] $$d_n$$. Because [TeX:] $$S_{n, i} \leq D_{n, i},$$ one can get [TeX:] $$\Delta_n(t) \geq 0$$ for all flow n and time t. Let [TeX:] $$\Delta(t)=\left(\Delta_1(t), \ldots, \Delta_N(t)\right) \in [0, \infty)^N$$ be the age vector of the N flows at time t.

We introduce an age penalty function [TeX:] $$p(\Delta)=p \circ \Delta$$ to represent the level of dissatisfaction for having aged information at the N destinations, where [TeX:] $$p:[0, \infty)^N \rightarrow \mathbb{R}$$ can be any non-decreasing function of the N-dimensional age vector Δ. Some examples of the age penalty function are:

1. The average age of the N flows is

2. The maximum age of the N flows is

3. The mean square age of the N flows is

4. The l-norm of the age vector of the N flows is

5. The sum of per-flow age penalty functions is

where [TeX:] $$g:[0, \infty) \rightarrow \mathbb{R}$$ is a non-decreasing function. Practical applications of non-decreasing age functions can be found in [32]–[34], [36], [44].

In this paper, we consider a class of symmetric and nondecreasing age penalty functions, i.e.,

[TeX:] $$\mathcal{P}_{\text {sym }}=\left\{p:[0, \infty)^N \rightarrow \mathbb{R} \text { is symmetric and non-decreasing }\right\} .$$

This is a fairly large class of age penalty functions, where the function p can be discontinuous, non-convex, or non-separable. It is easy to see

In this paper, we consider both continuous-time and discrete-time status updating systems. In the continuous-time setting, time [TeX:] $$t \in[0, \infty)$$ can take any positive value and the packet transmission times are i.i.d. continuous random variables. On the other hand, in the discrete-time setting, time is quantized into multiples of a fundamental time unit [TeX:] $$T_s,$$ i.e., [TeX:] $$t \in\left\{0, T_s, 2 T_s, \ldots\right\},$$ and each packet’s transmission time is fixed and equal to [TeX:] $$T_s.$$ Consequently, the variables [TeX:] $$S_{n, i}, A_{n, i}, D_{n, i}, t, U_n(t), \Delta_n(t)$$ are all multiples of [TeX:] $$T_s.$$ In realistic discrete-time systems, service preemption is not allowed.

Let [TeX:] $$\Delta_{n, \pi}(t)$$ denote the age of flow n achieved by scheduling policy π and [TeX:] $$\Delta_\pi(t)=\left(\Delta_{1, \pi}(t), \ldots, \Delta_{N, \pi}(t)\right).$$ In the continuous-time case, we assume that the initial age [TeX:] $$\boldsymbol{\Delta}_\pi\left(0^{-}\right)$$ at time [TeX:] $$t=0^{-}$$ remains the same for all scheduling policies [TeX:] $$\pi \in \Pi,$$ where [TeX:] $$t=0^{-}$$ is the moment right before t = 0. In the discrete-time case, we assume that the initial age [TeX:] $$\boldsymbol{\Delta}_\pi\left(0\right)$$ at time t = 0 remains the same for all scheduling policies [TeX:] $$\pi \in \Pi.$$

The results in this paper remain true even if the age penalty function [TeX:] $$p_t$$ varies over time t. For example, it is allowed that [TeX:] $$p_t=p_{\mathrm{avg}}$$ for [TeX:] $$0 \leq t \leq 100$$ and [TeX:] $$p_t=p_{\max }$$ for [TeX:] $$0 \lt t \leq 200$$. In the continuous-time case, we use [TeX:] $$\left\{p_t \circ \Delta_\pi(t), t \in\right.[0, \infty)\}$$ to represent the age-penalty stochastic process formed by the time-dependent penalty function [TeX:] $$p_t$$ of the age vector [TeX:] $$\boldsymbol{\Delta}_\pi(t)$$ under scheduling policy π. In the discrete-time case, the age-penalty stochastic process is denoted by [TeX:] $$\left\{p_t \circ \Delta_\pi(t), t=\right.\left.0, T_s, 2 T_s, \ldots\right\}.$$

IV. MULTI-FLOW STATUS UPDATE SCHEDULING: THE CONTINUOUS-TIME CASE

In this section, we investigate multi-flow scheduling in continuous-time status updating systems. We first consider a system setting with multiple servers and exponential transmission times, where an age-optimal scheduling result is established. Next, we study a more general system setting with multiple servers and NBU transmission times. In the second setting, age optimality is inherently difficult to achieve and we present a near age-optimal scheduling result.

A. Multiple Flows, Multiple Servers, Exponential Service Times

To address the multi-flow scheduling problem, we consider a flow selection discipline called Maximum Age First (MAF) [6], [22], [23], in which the flow with the maximum age is served first, with ties broken arbitrarily.

For multi-flow single-server systems, a scheduling policy is defined by combining the Preemptive, MAF, and LGFS service disciplines as follows:

Definition 5. Preemptive, Maximum Age First, Last Generated First Served (P-MAF-LGFS) policy: This is a work-conserving scheduling policy for multiple-server, continuous-time systems with synchronized packet generations and arrivals. It operates as follows:

1. If the queue is not empty, a server is assigned to process the most recently generated packet from the flow with the maximum age, with ties broken arbitrarily.

2. The next server is assigned to process the most recently generated packet from the flow with the second maximum age, with ties broken arbitrarily.

3. This process continues until either (i) the most recently generated packet of every flow is under service or has been delivered, or (ii) all servers are busy.

4. If the most recently generated packet of every flow is under service or has been delivered, the remaining servers can be arbitrarily assigned to send the remaining packets in the queue, until the queue becomes empty.

5. When fresher packets arrive, the scheduler can preempt the packets that are currently under service and assign the new packets to servers following Steps 1-4 above. The preempted packets are then returned to the queue, where they await their turn to be transmitted at a later time.

The following observation provides useful insights into the operations of the P-MAF-LGFS policy: Due to synchronized packet generations and arrivals, when the most recently generated packet of flow n is successfully delivered in the P-MAFLGFS policy, flow n must have the minimum age among the N flows. Conversely, if flow n does not have the minimum age among all the flows, its most recently generated packet must be undelivered. Hence, in the P-MAF-LGFS policy, the most recently generated packet from a flow that does not have the minimum age is always available to be scheduled.

The above P-MAF-LGFS policy is suitable for use in both single-server and multiple-server systems. It extends the original single-server P-MAF-LGFS policy introduced in [1] to encompass the more general multi-server scenario.

The age optimality of the P-MAF-LGFS policy is established in Theorem 1 and Corollary 1 below.

Theorem 1. (Continuous-time, multiple flows, multiple servers, exponential transmission times with transmission errors) In continuous-time status updating systems, if (i) the transmission errors are i.i.d. with an error probability [TeX:] $$q \in [0,1),$$ (ii) the packet generation and arrival times are synchronized across the N flows, and (iii) the packet transmission times are exponentially distributed and i.i.d. across packets, then it holds that for all [TeX:] $$\mathcal{I},$$ all [TeX:] $$p_t \in \mathcal{P}_{\text {sym }},$$ and all [TeX:] $$\pi \in \Pi$$

or equivalently, for all [TeX:] $$\mathcal{I},$$ all [TeX:] $$p_t \in \mathcal{P}_{\text {sym }},$$ and all non-decreasing functional ϕ

provided that the expectations in (16) exist.

Proof. See Appendix A.

According to Theorem 1, for any age penalty function in [TeX:] $$\mathcal{P}_{\text {sym }},$$ any number of flows N, any number of servers M, any synchronized packet generation and arrival times in [TeX:] $$\mathcal{I},$$ and regardless the presence of i.i.d. transmission errors or not, the P-MAF-LGFS policy minimizes the stochastic process [TeX:] $$\left[\left\{p_t \circ \boldsymbol{\Delta}_\pi(t), t \in[0, \infty)\right\} \mid \mathcal{I}\right]$$ among all causal policies in terms of stochastic ordering. Theorem 1 is more general than [1, Theorem 1], as the latter was established for the special case of single-server systems without transmission errors.

By considering a mixture over the different realizations of [TeX:] $$\mathcal{I},$$ it can be readily deduced from Theorem 1 that

Corollary 1. Under the conditions of Theorem 1, it holds that for all [TeX:] $$p_t \in \mathcal{P}_{\mathrm{sym}}$$ and all [TeX:] $$\pi \in \Pi$$

or equivalently, for all [TeX:] $$p_t \in \mathcal{P}_{\mathrm{sym}}$$ and all non-decreasing functional ϕ

provided that the expectations in (18) exist.

Corollary 1 states that the P-MAF-LGFS policy minimizes the stochastic process [TeX:] $$\left\{p_t \circ \boldsymbol{\Delta}_\pi(t), t \in[0, \infty)\right\}$$ in a stochastic ordering sense, outperforming all other causal policies.

1) Status Update Scheduling with Packet Replications: As discussed in Section III-B, our study has been centered on a scenario where different servers are not allowed to simultaneously transmit packets from the same flow. In this context, we have demonstrated the age-optimality of the PMAF- LGFS policy in Theorem 1. However, in situations where multiple servers can transmit packets from the same flow, and packet replication is permitted, it becomes possible to create multiple copies of the same packet and transmit these copies concurrently across multiple servers. The packet is considered delivered once any one of these copies is successfully delivered; at that point, the other copies are canceled to release the servers. If the packet service times follow an i.i.d. exponential distribution with a service rate of μ, the N servers can be equivalently viewed as a single, faster server with exponential service times and a higher service rate of [TeX:] $$N\mu$$. Additionally, this fast server exhibits i.i.d. transmission errors with an error probability q. Our study also addresses this scenario.

Definition 6. Preemptive, Maximum Age First, Last Generated First Served policy with packet Replications (P-MAF-LGFSR): In this policy, the last generated packet from the flow with the maximum age is served the first among all packets of all flows, with ties broken arbitrarily. This packet is replicated into N copies, which are transmitted concurrently over the N servers. The packet is considered delivered once any one of these N copies is successfully delivered; at that point, the other copies are canceled to release the servers.

By applying Theorem 1 to this particular scenario with a single, faster server, we derive the following corollary.

Corollary 2. Under the conditions of Theorem 1, if packet replication is allowed, then it holds that for all [TeX:] $$\mathcal{I},$$ all [TeX:] $$p_t \in \mathcal{P}_{\mathrm{sym}}$$, and all [TeX:] $$\pi \in \Pi$$

or equivalently, for all [TeX:] $$\mathcal{I},$$ all [TeX:] $$p_t \in \mathcal{P}_{\mathrm{sym}}$$, and all non-decreasing functional ϕ

provided that the expectations in (20) exist.

B. Multiple Flows, Multiple Servers, NBU Service Times

Next, we consider a more general system setting with multiple servers and a class of New-Better-than-Used (NBU) transmission time distributions that include exponential distribution as a special case.

Definition 7. New-Better-than-Used Distributions: Consider a non-negative random variable X with complementary cumulative distribution function (CCDF) [TeX:] $$\bar{F}(x)=\operatorname{Pr}[X\gt x].$$ Then, X is said to be New-Better-than-Used (NBU) if for all t, [TeX:] $$\tau \geq 0$$

Examples of NBU distributions include deterministic distribution, exponential distribution, shifted exponential distribution, geometric distribution, gamma distribution, and negative binomial distribution.

In the scheduling literature, optimal scheduling results were successfully established for delay minimization in singleserver queueing systems, e.g., [51], [52], but it can become inherently difficult in the multi-server cases. In particular, minimizing the average delay in deterministic scheduling problems with more than one servers is NP-hard [53]. Similarly, delay-optimal stochastic scheduling in multi-class, multiserver queueing systems is deemed to be quite difficult [54]– [56]. The key challenge in multi-class, multi-server scheduling is that one cannot combine the capacities of all the servers to jointly process the most important packet. Due to the same reason, age-optimal scheduling in multi-flow, multiserver systems is quite challenging. In the sequel, we consider a relaxed goal to seek for near age-optimal scheduling of multiple information flows, where our proposed scheduling policy is shown to be within a small additive gap from the optimum age performance.

To establish near age optimality, we introduce another age metric named age of served information, denoted as [TeX:] $$\Xi_n(t),$$ which is a lower bound for age of information [TeX:] $$\Delta_n(t):$$

Let [TeX:] $$V_{n,i}$$ be the time that the i-th packet of flow n starts its service by a server, i.e., the service starting time of the i-th packet of flow n. It holds that [TeX:] $$S_{n, i} \leq A_{n, i} \leq V_{n, i} \leq D_{n, i},$$ as illustrated in Fig. 2. Age of served information for flow n is defined as

which is the time difference between the current time t and the generation time of the freshest packet that has started service by time t. Let [TeX:] $$\Xi(t)=\left(\Xi_1(t), \ldots, \Xi_N(t)\right)$$ be the age of served information vector at time t. Age of served information [TeX:] $$\Xi_n(t)$$ reflects the staleness of the packets that has begun service, whereas [TeX:] $$\Delta_n(t)$$ represents the staleness of the packets that has been successfully delivered to their destination. As depicted in Fig. 3, it is evident that [TeX:] $$\Xi_n(t) \leq \Delta_n(t).$$ In non-preemptive policies, the discrepancy between [TeX:] $$\Xi_n(t) \text { and } \Delta_n(t)$$ solely arises from the i.i.d. packet transmission times. Consequently, the age of served information [TeX:] $$\Xi_n(t)$$ closely approximates the age [TeX:] $$\Delta_n(t).$$

We propose a new flow selection discipline called Maximum Age of Served Information First (MASIF), in which the flow with the maximum Age of Served Information is served first, with ties broken arbitrarily. Using this discipline, we define another scheduling policy:

Definition 8. Non-Preemptive, Maximum Age of Served Information first, Last Generated First Served (NP-MASIF-LGFS) policy: This is a non-preemptive, work-conserving scheduling policy for multi-server systems. It operates as follows:

1. When the queue is not empty and there are idle servers, an idle server is assigned to process the most recently generated packet from the flow with the maximum age of served information, with ties broken arbitrarily.

2. After a packet from flow n is assigned to an idle server, the server transitions into a busy state and will complete the transmission of the current packet from flow n before serving any other packet. The age of served information [TeX:] $$\Xi_n(t)$$ of flow n decreases. As a result, flow n may no longer retain the maximum age of served information, allowing the remaining idle servers to be allocated to process other flows. The next idle server is assigned to process the most recently generated packet from the flow with the maximum age of served information, with ties broken arbitrarily.

3. This procedure continues until either all servers are busy or the queue becomes empty.

Next, we will establish the near-age optimality of the NPMASIF- LGFS policy. The following theorem shows that the age of served information obtained by the NP-MASIF-LGFS policy serves as a lower bound (in terms of stochastic ordering) for the age of all other non-preemptive and causal policies.

Theorem 2. (Continuous-time, multiple flows, multiple servers, NBU transmission times with no errors) In continuous-time status updating systems, if (i) there is no transmission errors (i.e., q = 0), (ii) the packet generation and arrival times are synchronized across the N flows, and (iii) the packet transmission times are NBU and i.i.d. across both servers and packets, then it holds that for all [TeX:] $$\mathcal{I},$$ all [TeX:] $$p_t \in \mathcal{P}_{\text {sym }}$$, and all [TeX:] $$\pi \in \Pi_{n p}$$³

³ Recall that [TeX:] $$\Pi_{n p}$$ is the set of non-preemptive and causal scheduling policies.

or equivalently, for all [TeX:] $$\mathcal{I},$$ all [TeX:] $$p_t \in \mathcal{P}_{\text {sym }}$$, and all non-decreasing functional ϕ

provided that the expectations in (24) exist.

Proof idea. In the NP-MASIF-LGFS policy, if a packet from flow n* begins service, it implies that flow n* possesses the maximum age of served information before the service starts. If the packet generation and arrival times are synchronized across the flows, flow n* also exhibits the minimum age of served information after the service starts. The proof of Theorem 2 relies on this property and a sample-path argument that is developed for NBU service time distributions. See Appendix B for the details.

Considering the close approximation between the age of served information [TeX:] $$\Xi_{\text {NP-MASIF-LGFS}}(t)$$ and the age of information [TeX:] $$\Delta_{\text {NP-MASIF-LGFS}}(t)$$ in (24), we can conclude that the NPMASIF-LGFS policy is near age-optimal. Furthermore, in the case of the average age metric as defined in (9) (i.e., [TeX:] $$p_t=p_{\text {avg }}$$ for all t), we can derive the following corollary:

Corollary 3. Under the conditions of Theorem 2, it holds that for all [TeX:] $$\mathcal{I}$$

where

is the expected time-average of the average age of the N flows, and [TeX:] $$1/\mu$$ is the mean packet transmission time.

Proof. The proof of Corollary 3 is the same as that of Theorem 12 in [15] and hence is omitted here.

By Corollary 3, the average age of the NP-MASIF-LGFS policy is within an additive gap from the optimum, where the gap [TeX:] $$1/\mu$$ is invariant of the packet arrival and generation times [TeX:] $$\mathcal{I}$$, the number of flows N, and the number of servers M.

Similar to Corollary 1, by taking a mixture over the different realizations of [TeX:] $$\mathcal{I}$$, one can remove the condition [TeX:] $$\mathcal{I}$$ from (23), (24), (25), and (26).

The sampling-path argument utilized in the proof of Theorem 2 can effectively handle multiple flows, multiple servers, and i.i.d. NBU transmission time distributions. This is achieved by establishing a coupling between the start time of packet transmissions in the NP-MASIF-LGFS policy and the completion time of packet transmissions in any other work-conserving policy from [TeX:] $$\Pi_{np}.$$ However, extending this sampling-path argument to encompass the scenario of i.i.d. transmission errors poses additional challenges that are currently difficult to overcome.

V. MULTI-FLOW STATUS UPDATE SCHEDULING: THE DISCRETE-TIME CASE

In this section, we investigate age-optimal scheduling in discrete-time status updating systems, where the variables [TeX:] $$S_{n, i}, A_{n, i}, D_{n, i}, t, U_n(t), \Delta_n(t)$$ are all multiples of the period [TeX:] $$T_s,$$ the transmission time of each packet is fixed as [TeX:] $$T_s,$$ and the packet submissions are subject to i.i.d. errors with an error probability [TeX:] $$q \in[0,1) .$$ Service preemption is not allowed in discrete-time systems.

For multiple-server, discrete-time systems, a scheduling policy is defined by combining the MAF and LGFS service disciplines as follows:

Definition 9. Discrete Time, Maximum Age First, Last Generated First Served (DT-MAF-LGFS) policy: This is a workconserving scheduling policy for multiple-server, discrete-time systems with synchronized packet generations and arrivals. It operates as follows:

1. When time t is a multiple of period [TeX:] $$T_s,$$ if the queue is not empty, an idle server is assigned to process the most recently generated packet from the flow with the maximum age, with ties broken arbitrarily.

2. The next idle server is assigned to process the most recently generated packet from the flow with the second maximum age, with ties broken arbitrarily.

3. This process continues until either (i) the most recently generated packet of each flow is under service or has been delivered, or (ii) all servers are busy.

4. If the most recently generated packet of each flow is under service or has been delivered, and there are additional idle servers, then these servers can be arbitrarily assigned to send the remaining packets in the queue, until the queue becomes empty.

One can observe that the DT-MAF-LGFS policy for discrete-time systems is similar to the P-MAF-LGFS policy designed for continuous-time systems.

The age optimality of the DT-MAF-LGFS policy is obtained in the following theorem.

Theorem 3. (Discrete-time, multiple flows, multiple servers, constant transmission times with transmission errors) In discrete-time status updating systems, if (i) the transmission errors are i.i.d. with an error probability [TeX:] $$q \in[0,1),$$ (ii) the packet generation and arrival times are synchronized across the N flows, and (iii) the packet transmission times are fixed as [TeX:] $$T_s,$$ then it holds that for all [TeX:] $$\mathcal{I}$$, all [TeX:] $$p_t \in \mathcal{P}_{\text {sym}},$$ and all [TeX:] $$\pi \in \Pi_{np}$$

or equivalently, for all [TeX:] $$\mathcal{I}$$, all [TeX:] $$p_t \in \mathcal{P}_{\text {sym}},$$ and all non-decreasing functional ϕ

provided that the expectations in (28) exist.

Proof. See Appendix C.

According to Theorem 3, the DT-MAF-LGFS policy minimizes the stochastic process [TeX:] $$\left[\left\{p_t \circ \Delta_\pi(t), t=\right.\right.\left.\left.\left.0, T_s, 2 T_s, \ldots\right)\right\} \mid \mathcal{I}\right]$$ in terms of stochastic ordering within discrete-time status updating systems. This optimality result holds for any age penalty function in [TeX:] $$\mathcal{P}_{\text {sym}},$$ any number of flows N, any number of servers M, any synchronized packet generation and arrival times in [TeX:] $$\mathcal{I},$$ and regardless the existence of i.i.d. transmission errors.

Theorem 3 generalizes [22, Theorem 1], by allowing for multiple servers and a broader range of age penalty functions. Similar to Corollary 1, one can remove the condition [TeX:] $$\mathcal{I}$$ from (27) and (28).

VI. NUMERICAL RESULTS

In this section, we evaluate the age performance of several multi-flow scheduling policies. These scheduling policies are defined by combining the flow selection disciplines {MAF, MASIF, RAND} and the packet selection disciplines {FCFS, LGFS}, where RAND represents randomly choosing a flow among the flows with un-served packets. The packet generation times [TeX:] $$S_i$$ follow a Poisson process with rate λ, and the time difference [TeX:] $$\left(A_i-S_i\right)$$ between packet generation and arrival is equal to either [TeX:] $$0 \text { or } 4 / \lambda$$ with equal probability. The mean transmission time of each server is set as [TeX:] $$\mathbb{E}[X]=1 / \mu=1.$$ Hence, the traffic intensity is [TeX:] $$\rho=\lambda N / M \text {, }$$ where N is the number of flows and M is the number of servers.

Figure 4 illustrates the expected time-average of the maximum age [TeX:] $$p_{\max }(\Delta(t))$$ of 3 flows in a system with a single server and i.i.d. exponential transmission times. One can see that the P-MAF-LGFS policy has the best age performance and its age is quite small even for [TeX:] $$\rho \gt 1,$$ in which case the queue is actually unstable. On the other hand, both the RAND and FCFS disciplines have much higher age. Note that there is no need for preemptions under the FCFS discipline. Figure 5 plots the expected time-average of the average age [TeX:] $$p_{\text {avg }}(\boldsymbol{\Delta}(t))$$ of 50 flows in a system with 3 servers and i.i.d. NBU transmission times. In particular, the transmission time X follows the following shifted exponential distribution:

One can observe that the NP-MASIF-LGFS policy is better than the other policies, and is quite close to the age lower bound where the gap from the lower bound is no more than the mean transmission time [TeX:] $$\mathbb{E}[X]=1.$$ One interesting observation is that the NP-MASIF-LGFS policy is better than the NPMAF- LGFS policy for NBU transmission times. The reason behind this is as follows: When multiple servers are idle, the NP-MAF-LGFS policy will assign these servers to process multiple packets from the flow with the maximum age (say flow n). This reduces the age of flow n, but at a cost of postponing the service of the flows with the second and third maximum ages. On the other hand, in the NP-MASIF-LGFS policy, once a packet from the flow with the maximum age of served information (say flow m) is assigned to a server, the age of served information of flow m drops greatly, and the next server will be assigned to process the flow with the second maximum age of served information. As shown in [57], [58], using multiple parallel servers to process different flows is beneficial for NBU service times.

VII. CONCLUSION

We have proposed causal scheduling policies and developed a unifying sample-path approach to prove that these scheduling policies are (near) optimal for minimizing age of information in continuous-time and discrete-time status updating systems with multiple flows, multiple servers, and transmission errors.