Exact Analysis of the Age of Information in the Multi-Source M/GI/1 Queueing System

We consider a situation that multiple time-varying information sources are monitored remotely. Specifically, each information source is attached with a sensor node, which reports observed data to a remote monitor that displays the latest state information received. Each observed data needs to be “served” by an intermediate service resource (such as a communication link and a processor) before it is received by the monitor, so that it experiences queueing and processing delay there. The service resource is shared by the source-monitor pairs in the system and the degree of congestion is highly affected by the sampling rate of the sensors.

Because the state of the information source changes over time, the value of displayed information degenerates with time. It is thus important for such a system that the information displayed on each monitor is kept sufficiently fresh. The age of information (AoI) [1, 2] is a widely used metric of the freshness of information, which is defined as the elapsed time from the generation time of currently displayed information. Specifically, letting $K$ denote the number of sensor-monitor pairs, the AoI $A_{t}^{\langle k\rangle}$ of the $k$th ($k=0,1,\ldots,K-1$) sensor-monitor pair at time $t$ is defined as

$$A_{t}^{\langle k\rangle}=t-\eta_{t}^{\langle k\rangle},\quad t\in\mathbb{R},$$

(1)

where $\eta_{t}^{\langle k\rangle}$ denotes the generation time of the displayed information at time $t$.

The mean AoI $\mathrm{E}[A^{\langle k\rangle}]$ is the primary performance measure of interest, which is defined as

$$\mathrm{E}[A^{\langle k\rangle}]=\lim_{T\to\infty}\frac{1}{T}\int_{-T/2}^{T/2}A_{t}^{\langle k\rangle}\mathrm{d}t.$$

Under a fairly general setting, the mean AoI $\mathrm{E}[A^{\langle k\rangle}]$ is given in terms of the mean inter-sampling time, the mean delay, and a cross-term of the inter-sampling time and the delay [1]. A more detailed characterization of the AoI process is provided by the probability distribution $F_{A^{\langle k\rangle}}(x)$ ($x\geq 0$) of the AoI, which is defined as a long-run fraction of time that the AoI process does not exceed $x$:

$$F_{A^{\langle k\rangle}}(x)=\lim_{T\to\infty}\frac{1}{T}\int_{-T/2}^{T/2}\mathbbm{1}\{A_{t}^{\langle k\rangle}\leq x\}\mathrm{d}t,$$

which is known to be given in terms of the probability distributions of the system delay and the peak AoI value just before updates [3].

To characterize the AoI process formally, the system is usually modeled as a queueing system, where generation of information packets by sensors corresponds to “arrivals”, and their reception by monitors corresponds to “departures”. Analytical results for the AoI in various queueing systems have been reported in the literature, e.g., first-come first-served (FCFS) queues [1, 3], last-come first-served (LCFS) queues [4, 5, 6], and multi-server queues [7, 8]. The FCFS queueing model represents the situation where the application layer does not have any control over the data transmission performed by lower layer protocols, so that the AoI performance in this framework is interpreted as that of monitoring applications implemented on top of the conventional communication mechanisms. The LCFS queueing model, on the other hand, gives a priority to newer information in transmission, which in general leads to better performance at the expense of implementation/operation costs, especially due to the necessity of the cross-layer design and intelligent functionalities of network components.

The models mentioned above [1, 3, 4, 5, 6, 7] assume that there is only a single sensor node in the system (i.e., $K=1$), so that the “congestion” of the system refers to the accumulation of buffered packets generated by the sensor itself. In order to incorporate the existence of competing sensors that share the communication resources, it is necessary to consider multi-source queueing models, where each source corresponds to a sensor node. In fact, significant research efforts have recently been put into generalizing the AoI analysis to multi-source queueing models. Such generalization has been particularly successful for the multi-source buffer-less M/G/1/1 queues [11, 12, 13, 14, 15, 16], whose analysis is less complicated due to the small state space.

For the standard (infinite-buffer) multi-source FCFS systems, however, the exact analysis of the AoI has been reported for the simplest M/M/1 queueing model only [9, 10]. The difficulty in the analysis of the multi-source FCFS M/GI/1 queue is explained in [10], where approximate formulas for the mean AoI are proposed. Roughly speaking, in multi-class FCFS queues, an unbounded number of information packets from other sources can arrive between two successive packets of a single source, which makes it necessary to keep track of the whole dynamics of the system driven by other sources. Because of such difficulty, exact analysis of the AoI in the multi-source FCFS M/GI/1 queue has been an open problem for years.

The purpose of this paper is to provide a solution to this problem, by showing that the Laplace-Stieltjes transform (LST) of the stationary distribution of the AoI in the multi-source FCFS M/GI/1 queue, as well as the mean AoI, is given by a simple explicit formula. The key observation is that the system dynamics between two successive packets from a single source is characterized in terms of the double transform [17, P. 83] of the transient workload process in the M/GI/1 queue. As will be shown later, the complexity of the exact mean AoI formula is more or less the same as that of the single-source M/GI/1 queue.

The rest of this paper is organized as follows. We first provide a formal description of the model in Section II. We then present the exact analysis of the AoI in Section III, where explicit formulas of the LST and the mean of the AoI are derived. Finally, we conclude this paper in Section IV.

Throughout this paper, we comply with the following rules of notation: for any non-negative random variable $Y$, its cumulative distribution function (CDF) is denoted by $F_{Y}(x)$ ($x\geq 0$) and its LST is denoted by $f_{Y}^{*}(s)$ ($s>0$):

$$F_{Y}(x):=\Pr(Y\leq x),\qquad f_{Y}^{*}(s):=\mathrm{E}[e^{-sY}]=\int_{0}^{\infty}e^{-sx}\mathrm{d}F_{Y}(x).$$

We also apply this rule in the opposite direction: given a CDF denoted by $F_{Y}(x)$ ($x\geq 0$), the corresponding random variable $Y$ is defined accordingly.

We consider an FCFS single-server queue with $K$ different source-monitor pairs. The $k$th ($k=0,1,\ldots,K-1$) source generates information packets according to a Poisson process with rate $\lambda^{\langle k\rangle}$ ($\lambda^{\langle k\rangle}>0$), which arrive at the server immediately after their generations. Packets are served by the server in order of arrival and they update the corresponding monitor on completion of the service. Hereafter we shall refer to the $k$th source and monitor as source $k$ and monitor $k$ for short. We assume that service times of packets from source $k$ are i.i.d. according to a general non-negative probability distribution with CDF $F_{H^{\langle k\rangle}}(x)$ ($x\geq 0$), i.e., the service time distribution is allowed to differ depending on the source-monitor pair. Let $\rho^{\langle k\rangle}$ denote the traffic intensity of source $k$:

$$\rho^{\langle k\rangle}=\lambda^{\langle k\rangle}\mathrm{E}[H^{\langle k\rangle}],\quad k=0,1,\ldots,K-1.$$

We assume $\sum_{k=1}^{K}\rho^{\langle k\rangle}<1$, so that the system is stable. Also, we assume that the system is stationary unless otherwise mentioned.

To define the AoI process for each monitor, let $\alpha_{n}^{\langle k\rangle}$ ($n\in\mathbb{Z}$) denote the generation time of the $n$th packet of source $k$. Without loss of generality, we set packet indices so that $\alpha_{-1}^{\langle k\rangle}<0\leq\alpha_{0}^{\langle k\rangle}$ holds for each $k$. Let $\beta_{n}^{\langle k\rangle}$ ($n\in\mathbb{Z}$) denote the reception time of the $n$th packet by monitor $k$. Its system delay $D_{n}^{\langle k\rangle}$ ($n\in\mathbb{Z}$) is then given by $D_{n}^{\langle k\rangle}=\beta_{n}^{\langle k\rangle}-\alpha_{n}^{\langle k\rangle}$.

The AoI $A_{t}^{\langle k\rangle}$ ($t\geq 0$, $k=1,2,\ldots,K$) of monitor $k$ at time $t$ is then defined as

$$A_{t}^{\langle k\rangle}=t-\alpha_{n}^{\langle k\rangle},\quad\beta_{n}^{\langle k\rangle}\leq t<\beta_{n+1}^{\langle k\rangle}.$$

Let $A_{\mathrm{peak},n}^{\langle k\rangle}$ denote the $n$th peak AoI of monitor $k$, i.e., the value of AoI just before $n$th update of the monitor:

	$\displaystyle A_{\mathrm{peak},n}^{\langle k\rangle}=\lim_{t\to\beta_{n}^{\langle k\rangle}-}A_{t}^{\langle k\rangle}$	$\displaystyle=\beta_{n}^{\langle k\rangle}-\alpha_{n-1}^{\langle k\rangle}$
		$\displaystyle=\beta_{n}^{\langle k\rangle}-\alpha_{n}^{\langle k\rangle}+\alpha_{n}^{\langle k\rangle}-\alpha_{n-1}^{\langle k\rangle}$
		$\displaystyle=D_{n}^{\langle k\rangle}+G_{n}^{\langle k\rangle},$		(2)

where $G_{n}^{\langle k\rangle}:=\alpha_{n}^{\langle k\rangle}-\alpha_{n-1}^{\langle k\rangle}$ denotes the inter-generation time between $n$th and $(n-1)$st packets of source $k$.

Because of the stationarity of the system, the probability distribution of $A_{t}^{\langle k\rangle}$ does not depend on $t$. Let $A^{\langle k\rangle}$ denote a generic random variable following the stationary distribution of $A_{t}^{\langle k\rangle}$. Similarly, let $G^{\langle k\rangle}$, $D^{\langle k\rangle}$, and $A_{\mathrm{peak}}^{\langle k\rangle}$ denote generic random variables following the stationary distributions of $G_{n}^{\langle k\rangle}$, $D_{n}^{\langle k\rangle}$ and $A_{\mathrm{peak},n}^{\langle k\rangle}$.

For better readability, we mainly focus on the AoI $A^{\langle 0\rangle}$ of source $0$ in the analysis below, which can be readily done without loss of generality.

Because the sequences of amounts of work brought by sources $1,2,\ldots,K-1$ (excluding source $0$) are all represented as compound Poisson processes, their superposition also forms a compound Poisson process with rate $\lambda^{+}$ and the random jump size $H^{+}$, where

$\displaystyle\lambda^{+}=\sum_{k=1}^{K-1}\lambda^{\langle k\rangle},\quad f_{H^{+}}^{*}(s)=\sum_{k=1}^{K-1}\frac{\lambda^{\langle k\rangle}}{\lambda^{+}}\cdot f_{H^{\langle k\rangle}}^{*}(s).$

Similarly, we define $\lambda^{\mathrm{all}}$ and $H^{\mathrm{all}}$ as the rate and random jump size of the compound Poisson process composed of all sources including source $0$:

$\displaystyle\lambda^{\mathrm{all}}=\lambda^{\langle 0\rangle}+\lambda^{+},\quad f_{H^{\mathrm{all}}}^{*}(s)=\frac{\lambda^{\langle 0\rangle}f_{H^{\langle 0\rangle}}^{*}(s)+\lambda^{+}f_{H^{+}}^{*}(s)}{\lambda^{\mathrm{all}}}.$

(3)

We further define $\rho^{\mathrm{all}}$ as the total traffic intensity:

$$\rho^{\mathrm{all}}=\rho^{\langle 0\rangle}+\rho^{+},$$

(4)

where

$$\rho^{+}=\rho_{1}+\rho_{2}+\cdots+\rho_{K-1}.$$

To make the notation even simpler, we hereafter drop the superscript $\langle 0\rangle$ for quantities of source $0$. For example, the inter-generation time $G_{n}^{\langle 0\rangle}$ and system delay $D_{n}^{\langle 0\rangle}$ of source $0$ are written simply as

$\displaystyle G_{n}:=G_{n}^{\langle 0\rangle},\quad D_{n}:=D_{n}^{\langle 0\rangle}.$

Similarly, the AoI and peak AoI of source $0$ are written as

$$A_{t}:=A_{t}^{\langle 0\rangle},\quad A_{\mathrm{peak},n}=A_{\mathrm{peak},n}^{\langle 0\rangle}.$$

The same rules apply to their stationary versions:

$$G:=G^{\langle 0\rangle},\quad D:=D^{\langle 0\rangle},\quad A:=A^{\langle 0\rangle}.$$

Notice that (3) and (4) are rewritten as

$$\lambda^{\mathrm{all}}=\lambda+\lambda^{+},\qquad f_{H^{\mathrm{all}}}^{*}(s)=\frac{\lambda f_{H}^{*}(s)+\lambda^{+}f_{H^{+}}^{*}(s)}{\lambda^{\mathrm{all}}},\qquad\rho^{\mathrm{all}}=\rho+\rho^{+}.$$

The starting point of our analysis is the following relation known in the literature [3]:

Because the stationary waiting time of packets of source $0$ is identical to that in the single-input M/GI/1 queue with the arrival rate $\lambda^{\mathrm{all}}$ and service time LST $f_{H^{\mathrm{all}}}^{*}(s)$, we have

$$f_{W}^{*}(s)=\frac{(1-\rho^{\mathrm{all}})s}{s-\lambda^{\mathrm{all}}+\lambda^{\mathrm{all}}f_{H^{\mathrm{all}}}^{*}(s)}=\frac{(1-\rho-\rho^{+})s}{s-\lambda-\lambda^{+}+\lambda f_{H}^{*}(s)+\lambda^{+}f_{H^{+}}^{*}(s)}.$$

(5)

It then follows from $f_{D}^{*}(s)=f_{W}^{*}(s)f_{H}^{*}(s)$ that

$\displaystyle f_{D}^{*}(s)$

$\displaystyle=\frac{(1-\rho-\rho^{+})s}{s-\lambda-\lambda^{+}+\lambda f_{H}^{*}(s)+\lambda^{+}f_{H^{+}}^{*}(s)}\cdot f_{H}^{*}(s).$

(6)

We thus consider $f_{A_{\mathrm{peak}}}^{*}(s)$ below.

We then obtain the following expression for the LST of the AoI distribution:

Taking the derivative of (6) and letting $s\to 0+$, we have the mean system delay $\mathrm{E}[D]$:

$$\mathrm{E}[D]=\frac{\lambda\mathrm{E}[H^{2}]+\lambda^{+}\mathrm{E}[(H^{+})^{2}]}{2(1-\rho-\rho^{+})}+\mathrm{E}[H].$$

(13)

An explicit formula for the mean AoI is then obtained as follows:

The proof of Corollary 1 is straightforward; we provide the proof in the appendix.

The expression (14) for the mean AoI $\mathrm{E}[A]$ largely resembles the known result for the single-source M/GI/1 queue. In fact, it is readily verified that as $\lambda^{+}\to 0+$, we have $\gamma\to\lambda$ and

$$\mathrm{E}[A]\to\frac{\lambda\mathrm{E}[H^{2}]}{2(1-\rho)}+\mathrm{E}[H]+\frac{1-\rho}{\lambda f_{H}^{*}(\lambda)},$$

which agrees with the mean AoI in the single-source M/GI/1 queue [3, Eq. (36)].

In this paper, we presented the exact analysis of the AoI in the multi-source FCFS M/GI/1 queueing model. We derived the explicit formula for the LST of the stationary distribution of the AoI in Theorem 1, based on the observation that the LST of the stationary peak AoI distribution is tractable using the explicit double-transform of the transient workload in the M/GI/1 queue. We also showed in Corollary 1 that the mean AoI $\mathrm{E}[A]$ in this model is given by a simple explicit formula. The result shows that the complexity of the mean AoI formula in the multi-source M/GI/1 queue is more or less the same as that of the single-source case, suggesting its usefulness as a simple framework in understanding the AoI performance in multi-source communication systems.

Note first that the existence and uniqueness of the solution of (15) is verified in the same way as Remark 1: the left-hand side of this equation is increasing and continuous for $\lambda\leq x\leq\lambda+\lambda^{+}$ and it takes a negative value at $x=\lambda$ and a positive value at $x=\lambda+\lambda^{+}$.

We decompose the LST of the AoI into the following product form (11):

$$f_{A}^{*}(s)=f_{A,1}^{*}(s)\cdot f_{A,2}^{*}(s),$$

where

	$\displaystyle f_{A,1}^{*}(s)$	$\displaystyle:=\frac{\lambda f_{H}^{*}(s)}{s+\lambda-\phi(s)},$		(16)
	$\displaystyle f_{A,2}^{*}(s)$	$\displaystyle:=f_{W}^{*}(s)-(1-\rho-\rho^{+})+\frac{\lambda f_{D}^{*}\left(\psi(s+\lambda)\right)}{\psi(s+\lambda)}.$		(17)

Noting that the definition of $\gamma$ and (15) imply $\phi(\gamma)=\lambda$, we have from (12),

$$f_{D}^{*}(\gamma)=\frac{(1-\rho-\rho^{+})\gamma}{\lambda}.$$

(18)

It then follows from $\lim_{s\to 0}\phi(s)=0$ that

$$\lim_{s\to 0+}f_{A,1}^{*}(s)=1,\quad\lim_{s\to 0+}f_{A,2}^{*}(s)=1.$$

Therefore, letting

$$f_{A,i}^{(1)}(s):=(-1)\cdot\frac{\mathrm{d}f_{A,i}^{*}(s)}{\mathrm{d}s},\quad i=1,2,$$

we have

	$\displaystyle\mathrm{E}[A]$	$\displaystyle=(-1)\cdot\lim_{s\to 0+}\frac{\mathrm{d}f_{A}^{*}(s)}{\mathrm{d}s}$
		$\displaystyle=\lim_{s\to 0+}f_{A,1}^{(1)}(s)+\lim_{s\to 0+}f_{A,2}^{(1)}(s).$		(19)

We thus consider $f_{A,1}^{(1)}(s)$ and $f_{A,2}^{(1)}(s)$ below.

By definition (cf. (8) and (9)), we have

$$\frac{\mathrm{d}\phi(s)}{\mathrm{d}s}=1-\lambda^{+}f_{H^{+}}^{(1)}(s),\quad\frac{\mathrm{d}\psi(\omega)}{\mathrm{d}\omega}=\frac{1}{1-\lambda^{+}f_{H^{+}}^{(1)}(\psi(\omega))},$$

where

$$f_{H^{+}}^{(1)}(s):=(-1)\cdot\frac{\mathrm{d}f_{H^{+}}^{*}(s)}{\mathrm{d}s}.$$

It then follows immediately from (16), (17), and (18) that

	$\displaystyle\lim_{s\to 0+}f_{A,1}^{(1)}(s)$	$\displaystyle=\mathrm{E}[H]+\frac{\rho^{+}}{\lambda},$		(20)
	$\displaystyle\lim_{s\to 0+}f_{A,2}^{(1)}(s)$	$\displaystyle=\mathrm{E}[W]+\frac{\lambda f_{D}^{(1)}(\psi(\lambda))}{\psi(\lambda)}\cdot\lim_{\omega\to\lambda}\frac{\mathrm{d}\psi(\omega)}{\mathrm{d}\omega}+\frac{\lambda f_{D}^{*}(\psi(\lambda))}{(\psi(\lambda))^{2}}\cdot\lim_{\omega\to\lambda}\frac{\mathrm{d}\psi(\omega)}{\mathrm{d}\omega}$
		$\displaystyle=\mathrm{E}[W]+\frac{1}{1-\lambda^{+}f_{H^{+}}^{(1)}(\gamma)}\left(\frac{\lambda}{\gamma}\cdot f_{D}^{(1)}(\gamma)+\frac{\lambda f_{D}^{*}(\gamma)}{\gamma^{2}}\right)$
		$\displaystyle=\mathrm{E}[W]+\frac{1}{\{1-\lambda^{+}f_{H^{+}}^{(1)}(\gamma)\}\gamma}\left(\lambda f_{D}^{(1)}(\gamma)+1-\rho-\rho^{+}\right),$		(21)

where

$$f_{D}^{(1)}(s):=(-1)\cdot\frac{\mathrm{d}f_{D}^{*}(s)}{\mathrm{d}s}.$$

The rest is to determine $f_{D}^{(1)}(\gamma)$, which is straightforward with $\phi(\gamma)=\lambda$:

	$\displaystyle f_{D}^{(1)}(\gamma)$	$\displaystyle=-\frac{1-\rho-\rho^{+}}{\phi(\gamma)-\lambda+\lambda f_{H}^{*}(\gamma)}\cdot f_{H}^{*}(\gamma)$
		$\displaystyle\quad{}+\frac{(1-\rho-\rho^{+})\gamma}{(\phi(\gamma)-\lambda+\lambda f_{H}^{*}(\gamma))^{2}}\cdot\{1-\lambda^{+}f_{H^{+}}^{(1)}(\gamma)-\lambda f_{H}^{(1)}(\gamma)\}\cdot f_{H}^{*}(\gamma)$
		$\displaystyle\quad{}+\frac{(1-\rho-\rho^{+})\gamma}{\phi(\gamma)-\lambda+\lambda f_{H}^{*}(\gamma)}\cdot f_{H}^{(1)}(\gamma)$
		$\displaystyle=-\frac{1-\rho-\rho^{+}}{\lambda f_{H}^{*}(\gamma)}\cdot f_{H}^{*}(\gamma)$
		$\displaystyle\quad{}+\frac{(1-\rho-\rho^{+})\gamma}{(\lambda f_{H}^{*}(\gamma))^{2}}\cdot\{1-\lambda^{+}f_{H^{+}}^{(1)}(\gamma)-\lambda f_{H}^{(1)}(\gamma)\}\cdot f_{H}^{*}(\gamma)$
		$\displaystyle\quad{}+\frac{(1-\rho-\rho^{+})\gamma}{\lambda f_{H}^{*}(\gamma)}\cdot f_{H}^{(1)}(\gamma)$
		$\displaystyle=\frac{1-\rho-\rho^{+}}{\lambda^{2}f_{H}^{*}(\gamma)}\cdot\{-\lambda f_{H}^{*}(\gamma)+\gamma-\gamma\lambda^{+}f_{H^{+}}^{(1)}(\gamma)\}.$

Therefore, we have from (19), (20), and (21),

	$\displaystyle\mathrm{E}[A]$	$\displaystyle=\mathrm{E}[D]+\frac{\rho^{+}}{\lambda}$
		$\displaystyle\qquad{}+\frac{1}{\{1-\lambda^{+}f_{H^{+}}^{(1)}(\gamma)\}\gamma}\left(\frac{1-\rho-\rho^{+}}{\lambda f_{H}^{*}(\gamma)}\cdot\{-\lambda f_{H}^{*}(\gamma)+\gamma-\gamma\lambda^{+}f_{H^{+}}^{(1)}(\gamma)\}+1-\rho-\rho^{+}\right).$

We thus obtain (14) from this equation and (13). ∎