4 days ago - vector is then found for the age on a line network of preemptive .... Monitor. Fig. 2. Source updating through a network described by a s...

0 downloads 0 Views 561KB Size

The Age of Information in Networks: Moments, Distributions, and Sampling

arXiv:1806.03487v1 [cs.IT] 9 Jun 2018

Roy D. Yates

Abstract We examine a source providing status updates to monitors through networks with state given by a continuous-time finite Markov chain. Using an age of information metric, we characterize timeliness by the vector of ages tracked by the monitors. Using a stochastic hybrid systems (SHS) approach, we derive first order linear differential equations for the temporal evolution of both the age moments and a moment generating function (MGF) of the age vector components. We show that the existence of a non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher order moments as well as a region of convergence for the MGF vector of the age. The stationary MGF vector is then found for the age on a line network of preemptive memoryless servers. From this MGF, it is found that the age at a node is identical in distribution to the sum of independent exponential service times. This observation is then generalized to linear status sampling networks in which each node receives samples of the update process at each preceding node according to a renewal process. For the each node in the line, the age is shown to be identical in distribution to a sum of independent renewal process age random variables.

Index Terms Age of information, queueing systems, communication networks, stochastic hybrid systems, status updating, status sampling network

Note This is a near-final draft; the next revision will be be submitted for publication. Corrections, comments, and suggestions are welcomed. Roy Yates is with WINLAB and the ECE Department, Rutgers University, NJ, USA, e-mail: [email protected] This work was presented in part at the 2018 IEEE Infocom Age of Information Workshop. This work was supported by NSF award CCF-1717041.

2

I. I NTRODUCTION Maintaining the timeliness of data and state information in a network is a problem that has appeared in many forms, including, for example, data freshness in warehouses [1] and web caches [2], updating of real time databases [3], stale information in ad hoc networking protocols [4], [5], vehicular safety messaging [6]–[8], and safety-related intelligent transport system applications, [9], [10]. The need for timely state knowledge has led to the development and analysis of status update systems. This paper focuses on an age of information (AoI) timeliness metric as a basis for the evaluation and design of status update systems that deliver timestamped updates to a monitor. When the monitor’s most recently received update at time t is timestamped u(t), the age of information (AoI) is the random process x(t) = t − u(t). The AoI metric metric enables end-toend evaluation of the network performance, separate from application-specific criteria that may be too complex to employ in the design of a network. Traditionally, network performance has been characterized by tradeoffs in rate, delay, throughput and loss. The data rate can be increased, but this induces additional delay in lossless systems or increased packet dropping in lossy systems. Delay comparisons among lossy systems can difficult to interpret. Similarly, delay and throughput comparisons between lossless and lossy networks also tend to be problematic. By contrast, it has been shown that AoI is fundamentally different; the age metric enables direct comparison of lossless and lossy systems [11]. Moreover, the goal of timely updating is neither the same as maximizing the throughput or utilization of the communication system, nor of ensuring that generated status updates are received with minimum delay. Utilization is maximized when updates are sent as fast as possible. However, this can lead to the monitor receiving delayed updates because the status messages become backlogged in the communication system. Over the past several years, AoI has emerged as a performance metric for latency-sensitive cyberphysical systems. However, when queues have been used to model update delivery processes, analysis of the time-average AoI has proven challenging. The primary objective of this work is to introduce new tools for AoI analysis in networks. Building on prior work [12] that introduced stochastic hybrid systems (SHS) for AoI analysis, this paper employs SHS to analyze the temporal convergence of higher order AoI moments E[xm (t)] and the moment generating function (MGF) E esx(t) . The MGF enables characterization of the stationary distribution of the

3

X(t)

X(t)

t01

t02

t03

(a)

t

t1

t2

t01

t3 t4 t02

t03

t04

t

(b)

Fig. 1. Examples of the AoI process: (a) Fresh updates are delivered to the monitor as a point process at times t0i . Because the updates are fresh, the AoI is reset to zero at time t0i . (b) Update i from the source is created and timestamped at time ti and is delivered with some delay to the monitor at time t0i . The AoI at time t0i is t0i − ti .

AoI in a class of status sampling networks, a networking paradigm in which samples of a node’s status update process are delivered as a point process to neighbor nodes. This type of model may be useful in a high speed network in which updates represent small amounts of protocol information (requiring negligible time for transmission) that are given priority over data traffic. While the transmission of a single update may be negligible, the update rates are limited so that protocol information in the aggregate does not consume an excessive fraction of network resources. A. AoI: Background and Prior Work We say an update at time t is fresh when its timestamp is t and its age is zero. Figure 1(a) shows an example of an AoI process in which fresh updates are delivered to the monitor as a renewal point process. In this example, a renewal resets the AoI to zero and the AoI is simply the age (also known as the backwards excess) [13], [14] of the renewal process. Figure 1(b) shows an AoI sample path of x(t) with successive status updates timestamped t1 , t2 , . . . , tn . The AoI of the source at the monitor increases linearly in time in the absence of any updates and is reset to a smaller value when an update is received. Update j, generated at time tj , is delivered to the monitor at time t0j . At t0j , the AoI x(t0j ) is reset to the age t0j − tj of the received status update. Thus the AoI function x(t) exhibits the characteristic sawtooth pattern shown in Figure 1(b). Initial work on age has focused on applying graphical methods to the sawtooth age waveform

4

to evaluate the limiting time-average AoI 1 X = lim T →∞ T

Z

T

x(t) dt.

(1)

0

While the time average X is often referred as the AoI, we will use AoI and age as synonyms that refer to the process x(t) and call X the average AoI or average age.1 When randomly arriving updates are queued in a service facility, early work [11], [15] showed that it is generally in the self-interest of a source to limit its offered load. In particular, the updating must balance between too infrequent updates and overly frequent updates that induce queueing delays. This observation has prompted the study of age in lossy systems that discard updates to avoid building queues. These include the last-come-first served (LCFS) queue with preemption either in waiting or service [11], [16], [17] and packet management mechanisms that restrict the number of queued packets [18] or discard waiting packets as they become stale [19]. Other contributions to AoI analysis have also appeared recently. For single server queues, distributions of the AoI have been derived [20], [21]. The higher order moments and MGF that will be evaluated in this work can be interpreted as a nonlinear cost of updating [37] or as an age penalty function [31]. To evaluate AoI for a single source sending updates through a network cloud [22] or through an M/M/2 server [15], [23], out-of-order packet delivery was the key analytical challenge. A related (and often more tractable) metric, peak age of information (PAoI), was introduced in [18]. Properties of PAoI have also been studied in [24] for an FCFS M/G/1 multiclass queue. In [18], [25], the authors analyzed average AoI and PAoI for M/M/1/1 and M/M/1/2 queues that discard arriving updates if the system is full and also for a third queue, dubbed M/M/1/2*, in which an arriving update would preempt a waiting update. In [12], the M/M/1/2* queue is called the M/M/1 LCFS-W (with “W” denoting preemption in Waiting) queue and average AoI results are extended to an LCFS-W system with multiple sources. Most recently, packet deadlines are found to improve average AoI in [19], average AoI in the presence of errors is evaluated in [26], and LCFS with non-memoryless gamma-distributed service times is considered in [27]. There have also been studies of energy-constrained updating [28]–[31] in which updates are submitted to the server with knowledge of the server state. Additional references can be found in the survey [32]. 1

In Section V, we will need to distinguish between the AoI and the age of a renewal process that we use for random sampling.

5

Source

Network [q(t), x(t)]

Monitor

Fig. 2. Source updating through a network described by a stochastic hybrid system [q(t), x(t)].

The SHS model in this work can be applied to a single server as well as to networks of servers. There have already been efforts to examine age in multihop network settings [33]–[36]. When update transmission times over network links are exponentially distributed, sample path arguments were used [33]–[35] to show that a preemptive Last-Generated, First-Served (LGFS) policy results in smaller age processes at all nodes of the network than any other causal policy. However, these structural optimality results do not facilitate the explicit evaluation of age. The first evaluation of the average AoI over multihop network routes [36] employs a discrete-time version of the status sampling network described here in Section V. B. Paper Overview This work is based on the system depicted in Figure 2 in which a source sends update packets through a network to a monitor. The updates may follow multihop routes to the monitor and the network may carry other network traffic that interferes with the updating process of interest. We assume the network is described by a stochastic hybrid system (SHS) [38] with state [q(t), x(t)] such that q(t) is a continuous-time finite-state Markov chain and x(t) is a real-valued vector that describes the continuous-time evolution of a collection of age-related processes. We will refer to x(t) as the age vector or AoI process. For AoI analysis, the SHS approach was introduced in [12] for the average age analysis of LCFS queues. In that work, the discrete state q(t) described the number and source type of each update in the system while components of x(t) tracked the age at the monitor as well as the ages of updates in the system. It was shown [12] that age tracking can be implemented as a simplified SHS with non-negative linear reset maps in which the continuous state is a piecewise linear process [39], [40], a special case of piecewise deterministic processes [41], [42]. In this case, the SHS approach led to a system of ordinary first order differential equations describing the temporal evolution of the expected value of the age process. For finite-state queues

6

with memoryless service, this led to a set of age balance equations and simple conditions [12, Theorem 4] under which E[x(t)] converges to a fixed point. In this work, we expand on the prior effort [12]. In Section II, the SHS method is extended to derive a set of first order differential equations for calculating the temporal evolution of the higher order moments and a moment generating function (MGF) of the age vector. Section III derives stationary higher order moments of the age in Theorem 1 and the MGF of the age in Theorem 2. In particular, it is shown that a non-negative fixed point for the first moment guarantees the existence of all moments of the age and a region of convergence for the MGF. While the higher order moments can be derived from the MGF, there are cases in which direct calculation of the moments is more straightforward. On the other hand, the MGF can also be used for Chernoff bounds on the tail probabilities of age. This may be useful in designing a communication network to meet application-specific statistical requirements for age. Section IV goes on to use Theorems 1 and 2 to derive the moments, MGF, and stationary distribution of the age in a line network with memoryless preemptive servers. From the MGF, we find that the age at a node has distribution identical to a sum of independent exponential random variables. This generalizes a preliminary result in [43] for the average age that was based on the method of fake updates. In Section V, we show that the structural simplicity of the AoI in the line network derives from the observation that a network preemptive memoryless servers employing fake updates is an instance of a status sampling network in which samples of the update process at a node are delivered as a point process to a neighbor. For these status sampling networks, we show that when a node j is simply an observer that samples the status update process of a neighbor node i via a renewal process, the AoI at node j has a stationary distribution given by the independent sum of the AoI at node i and the stationary age of the renewal process. C. Notation For integers m ≤ n, m : n = {m, m + 1, . . . , n}; otherwise m : n is an empty set. The Kronecker delta function is denoted δij . The vectors 0n and 1n denote the row vectors [0 0 · · ·

0]

and [1 1 · · · 1] in Rn . The n × n identity matrix is In . With n unspecified, 0, 1, and I have dimensions that can be inferred from context. A vector x ∈ Rn is a 1 × n row vector. For vector x = [x1 , · · ·

xn ], [x]j = xj denotes the jth element. We use ei to denote the ith Cartesian

unit vector satisfying [ei ]j = δij . A matrix B has i, jth element [B]i,j and jth column [B]j .

7

In some instances, it will be convenient for vector/matrix indexing to start at j = 0 such that x = [ x0 . . .

xn ] and B has upper left element [B]00 and leftmost column [B]0 . For a vector

˙ process x(t), we use x˙ and x(t) to denote the derivative dx(t)/dt. A random variable X has CDF FX (x) and complementary CDF F X (x). If random variables X and Y have the same distribution, we write X ∼ Y . In addition, X ⊕ Y denotes the sum X + Y under the product distribution FX,Y (x, y) = FX (x)FY (y). For a scalar function g(·), g(x) = [g(x1 ) · · · In particular, we will often write xm = [xm ... xm 2 1

] and esx = [esx1 · · · xm n

g(xn )].

esxn ]. When

x is a random vector, we refer to the vector E[esx ] as the MGF vector.2 When x(t) is a random process such that the random variable x(t) converges to a stationary distribution, we use X(t) to denote the random process initialized with this stationary distribution. II. S TOCHASTIC H YBRID S YSTEMS FOR AO I A NALYSIS We start in Section II-A with an introduction to the general SHS method. Section II-B applies SHS to age tracking with Definition 1 identifying a special case of SHS in which the continuous state x(t) is a piecewise linear process that is subject to linear transition reset maps. Section II-C introduces test functions whose expected values yield, as functions of time, the discrete state probabilities, moments of the age, and the MGF of the age vector. We derive in Lemma 1 a set of first order differential equations for these expected value functions that will enable the computation of stationary moments and the stationary MGF vector in Section III. A. An Introduction to SHS There are many SHS variations [44], but this work follows the model and notation in [38]. In an SHS, the state is partitioned into a discrete component q(t) ∈ Q = {0, 1, . . . , qmax } that evolves as a point process and a continuous component x(t) = [x1 (t) · · ·

xn (t)] ∈ Rn . Given

the discrete set Q and the k-vector z(t) of independent Brownian motion processes, an SHS is defined by a stochastic differential equation x˙ = f (q, x, t) + g(q, x, t)z˙

(2)

2 This is a restricted form of MGF that is insufficient for describing dependency among the vector components, but will enable us to derive the marginal distribution of each xi through E[esxi ].

8

for mappings f : Q × Rn × [0, ∞) → Rn and g : Q × Rn × [0, ∞) → Rn×k , and a set of transitions L such that each l ∈ L defines a discrete transition/reset map (q 0 , x0 ) = φl (q, x, t),

φl : Q × Rn × [0, ∞) → Q × Rn ,

(3a)

with transition intensity λ(l) (q, x, t),

λ(l) : Q × Rn × [0, ∞) → [0, ∞).

(3b)

When the system is in discrete state q, x(t) evolves according to (2); but in a discrete transition from q to q 0 , the continuous state can make a discontinuous jump from x to x0 , as specified by (3a). The resulting x(t) process has piecewise continuous sample paths. Associated with each transition l is a counting process Nl (t) that counts the number of occurrences of transition l in the interval [0, t]. The probability that Nl jumps in the interval (t, t + dt] is λ(l) (q(t), x(t), t) dt. Because of the generality and power of the SHS model, characterization of the q(t) and x(t) processes can be complicated and often intractable. The approach in [38] is to define test functions ψ(q, x, t) whose expected values E[ψ(q(t), x(t), t)] are performance measures of interest that can be evaluated as functions of time; see [38] and the survey [44] for additional background. B. An SHS for Age Moments In the setting of status updates aging deterministically at unit rate while passing through a network, we restrict our attention to systems in which q(t) is a continuous-time finite-state Markov chain and the components of the age vector x(t) ∈ Rn are deterministic unit-slope ramp processes that can have discontinuous jumps during discrete state transitions. We will see that this is sufficient to capture sawtooth age processes. In terms of the general SHS model given by (2) and (3), we have f (q, x, t) = bq ,

(4a)

g(q, x, t) = 0,

(4b)

λ(l) (q, x, t) = λ(l) δql ,q , φl (q, x, t) = (ql0 , xAl ).

(4c) (4d)

In the graphical representation of the Markov chain q(t), each state q ∈ Q is a node and each transition l is a directed edge (ql , ql0 ) with transition rate λ(l) while q(t) = ql . In (4c), the

9

Kronecker delta function δql ,q ensures that transition l occurs only in state ql . For each transition l, the transition reset map will be a linear mapping of the continuous state x of the form x0 = xAl . That is, transition l causes the system to jump to discrete state ql0 and resets the continuous state from x to x0 = xAl . In addition, we note that (4a) and (4b) imply that the continuous state evolution (2) in each discrete state q(t) = q is ˙ x(t) = bq .

(5)

Hence the evolution of x(t) in each state is specified by B = {bq : q ∈ Q}. Since the transition links l are described by the tuples al = (ql , ql0 , λ(l) , Al ) and the set of transitions is A = {al : l ∈ L}, we use the tuple (Q, B, A) to refer to an AoI process defined by a piecewise linear SHS with linear reset maps. The transition rates λ(l) correspond to the transition rates of the continuous-time Markov chain for the discrete state q(t); but there are some differences. Unlike an ordinary continuoustime Markov chain, the SHS may include self-transitions in which the discrete state is unchanged because a reset occurs in the continuous state. Furthermore, for a given pair of states i, j ∈ Q, there may be multiple transitions l and l0 in which the discrete state jumps from i to j but the transition maps Al and Al0 are different.3 The SHS method specifies the continuous state x(t) for all discrete states q ∈ Q. In [12], these components were explicitly associated with update packets in the systems; for example, in the age analysis of the LCFS queue with preemption, x(t) = [x0 (t) x1 (t) x2 (t)] such that x0 (t) denoted the age at a monitor, x1 (t) denoted the age of an update in service, and x2 (t) denoted the age of an update in waiting, if any. In general, when x(t) ∈ Rn , one component of x(t) tracked the age at the monitor and the other components tracked the ages of up to n − 1 update packets in the system. However, if a state q had nq < n − 1 updates in the system, then there were components of x(t) that were not well defined since they were not tracking the age of any particular update. To avoid this issue, this work takes a somewhat different approach. Rather than xj (t) being the age of an update packet j, we instead define xj (t) as the age process of a monitor that observes the update packets that pass through a position j in the system. For example, the jth 3 For example, consider a queueing system in which an update in service can either complete service or be discarded in the middle of service. Under either transition, the next discrete state reflects the departure or discard of the update in service. However, a service completion yields a reduction in age while discarding an update in service results in no reduction in age.

10

position may refer to position j in a queue, server j in a multiple server system, or node j in a network. While this distinction may seem almost trivial, the key difference is that xj (t) is no longer ill-defined when a transition leaves position j empty. Instead, the age process of the associated monitor remains well defined and continues to grow at unit rate in the absence of a fresher arriving update. Under this model, all components of x(t) grow at unit rate in every state qˆ ∈ Q. That is, bq = 1 for all states q ∈ Q. With respect to prior work [12], this approach increases the algebraic complexity of SHS derivations of age formulas in terms of system parameters for simple queues. However, there will be benefit in giving physical meaning to all components of x(t) in all system states. Moreover, it will simplify the analysis of moments and generating functions in this work. For tracking of the AoI process, each Al is a binary matrix that has no more than a single 1 in a column. We refer to such an Al as an age assignment matrix. The set of mappings {Al } will depend on the specific queue discipline at each node, the network routing function, and the indexing scheme for updates in the system. Column j of Al determines how x0j is set when transition l takes place. In particular if [Al ]i,j = 1, then transition l resets the age xj at the position j monitor to x0j = xi . This corresponds to transition l delivering the update from position i to position j. This occurs, for example, in an FCFS queue when an update changes its queue position from i to i − 1 with the service completion of the head-of-line update. Another important case occurs when a transition l inserts a fresh update in queue position j at time t. Immediately following the transition, x0j = 0 because the update is fresh. In this case, [Al ]j is an all-zero column. In all cases, the age assignment Al encodes the age reductions offered by the delivery of updates to monitors in specific positions. Based on these considerations, we adopt the following definition.4 Definition 1: An age-of-information SHS (Q, 1, A) is an SHS in which the discrete state q(t) ∈ Q is a continuous-time Markov chain with transitions l ∈ L from state ql to ql0 at rate ˙ λ(l) and the continuous state evolves according to x(t) = 1 in each discrete state q ∈ Q and is subject to the age assignment map x0 = xAl in transition l. ˙ In prior work [12], a less restrictive definition of an AoI SHS allowed x(t) to evolve as x(t) = bq ∈ {0, 1}n in state q. In this case, the SHS is specified by the tuple (Q, B, A) with B = {bq : q ∈ Q}. In addition, the prior definition did not explicitly require Al to be an age assignment matrix. We will see that the more restrictive definition is needed here to enable derivation of the age MGF vector. 4

11

C. SHS test functions For AoI moment analysis, we will employ two classes of test functions; for j ∈ 1 : n, (m)

ψ(q, x) = ψqˆj (q, x) = xm j δqˆ,q ,

m = 0, 1, 2, . . . ,

(6a)

and (s)

ψ(q, x) = ψqˆj (q, x) = esxj δqˆ,q .

(6b)

Based on these test functions, we define for all qˆ ∈ Q and j ∈ 1 : n, h i (m) (m) vqˆj (t) = E ψqˆj (q(t), x(t)) = E xm j (t)δqˆ,q(t) , h i (s) (s) vqˆj (t) = E ψqˆj (q(t), x(t)) = E esxj (t) δqˆ,q(t) .

(7a) (7b)

We also define the vector functions (m) (m) (m) vqˆ (t) = [vqˆ1 (t), . . . , vqˆn (t)] = E xm (t)δqˆ,q(t) , (s) (s) (m) vqˆ (t) = [vqˆ1 (t), . . . , vqˆn (t)] = E esx(t) δqˆ,q(t) . (m)

(s)

(8a) (8b) (m)

(s)

We observe that the notation ψqˆj (q, x) and ψqˆj (q, x), or equivalently vqˆ (t) and vqˆ (t), uses the dummy parameter names m and s to distinguish between classes of test functions. While this is generally undesirable, it will highlight the parallelism in formulations. We do note that this (2)

(m)

(s)

abuse of notation can create ambiguity; ψqˆj (q, x) may refer to ψqˆj (q, x)|m=2 or to ψqˆj (q, x)|s=2 . (i)

To avoid this ambiguity, we adopt the convention that for any integer i ≥ 1 that ψqˆj (q, x) and (i)

(m)

(m)

vqˆ (t) refer to ψqˆj (q, x) and vqˆ (t) at m = i. Conveniently, at m = 0 or s = 0, our abuse of notation is consistent in yielding the state indicator (m) ψqˆj (q(t), x(t))

m=0

(s) = ψqˆj (q, x)

s=0

= δqˆ,q(t) .

(9)

We observe that the index j on the left side of (9) has become redundant. Since E δqˆ,q(t) = P[q(t) = qˆ], it follows from (8) that

(m) vqˆ (t)

= m=0

(s) vqˆ (t)

(0)

s=0

= vqˆ (t) = [1 1 · · ·

1] P[q(t) = qˆ]

(10)

is a vector of identical copies of P[q(t) = qˆ]. This vectorized redundancy will be convenient in simplifying some subsequent matrix algebra.

12

Since δqˆ,q(t) = 0 for q(t) 6= qˆ, it follows from (8) and the law of total expectation that (m)

vqˆ (t) = E[xm (t)|q(t) = qˆ] P[q(t) = qˆ], (s) vqˆ (t) = E esx(t) |q(t) = qˆ P[q(t) = qˆ],

qˆ ∈ Q,

(11a)

qˆ ∈ Q.

(11b)

(m)

(s)

Modulo the normalization by P[q(t) = qˆ], we see from (11) that vqˆ (t) and vqˆ (t) can be interpreted as conditional expectations of xm (t) and esx(t) given q(t) = qˆ. Furthermore, since xm (t) =

X

xm (t)δq¯,q(t) ,

(12)

q¯∈Q (m)

summing the conditional moments vqˆ (t) yields the vector of mth moments E[xm (t)] =

X X (m) E xm (t)δq¯,q(t) = vq¯ (t). q¯∈Q

(13a)

q¯∈Q

(s)

Similarly, from vq¯ (t), we obtain the MGF vector X sx(t) X (s) E esx(t) = E e δq¯,q(t) = vq¯ (t). q¯∈Q

(13b)

q¯∈Q

To derive these moments, we employ the mapping ψ → Lψ known as the extended generator. From [38, Theorem 1], it follows from the conditions (4) and the time invariance of either version of ψ(q, x) in (6) that the extended generator of a piecewise linear SHS is given by (Lψ)(q, x) =

∂ψ(q, x) > X (ψ(φl (q, x)) − ψ(q, x))λ(l) (q), 1 + ∂x l∈L

(14)

(m)

where the row vector ∂ψ(q, x)/∂x denotes the gradient. When ψ(q, x) = ψqˆj (q, x), (m)

∂ψqˆj (q, x) (m−1) = mxm−1 δqˆ,q ej = mψqˆ (q, x)ej j ∂x (s) and when ψ(q, x) = ψqˆj (q, x),

(15a)

(s)

∂ψqˆj (q, x) (s) = sesxj δqˆ,q ej = sψqˆj (q, x)ej . ∂x

(15b)

Each test function ψ(q(t), x(t)) must satisfy Dynkin’s formula d E[ψ(q(t), x(t))] = E[(Lψ)(q(t), x(t))]. dt

(16) (0)

We will see that (16) reduces to a system of first order ordinary differential equations for vq¯ (t),

13

(m)

(s)

vq¯ (t), and vq¯ (t) . To write these equations, we need some additional definitions. Let L0q¯ = {l ∈ L : ql0 = q¯},

(17a)

Lq¯ = {l ∈ L : ql = q¯}

(17b)

denote the respective sets of incoming and outgoing transitions for each state q¯. In addition, for ˆ l such that each transition mapping Al , we define a diagonal companion matrix A 1 i = j, [Al ] = 0> , j ˆ l] = (18) [A ij 0 otherwise. ˆ l mark the zero columns of Al . With these definitions, we have the The nonzero entries of A following lemma. Lemma 1: For an AoI SHS (Q, 1, A), we have for each state q¯ ∈ Q, (0) v˙ q¯ (t) =

X

(0)

λ(l) vq(0) (t) − vq¯ (t) l

l∈L0q¯

X

λ(l) ,

(19a)

l∈Lq¯

(m) (m−1) v˙ q¯ (t) = mvq¯ (t) +

X

(m)

λ(l) vq(m) (t)Al − vq¯ (t) l

l∈L0q¯ (s) (s) v˙ q¯ (t) = svq¯ (t) +

X

X

λ(l) ,

(19b)

l∈Lq¯

h

i

ˆ l − vq(s) λ(l) vq(s) (t)Al + vq(0) (t)A ¯ (t) l l

l∈L0q¯

X

λ(l) .

(19c)

l∈Lq¯

Proof of Lemma 1 appears in the Appendix. From a given initial condition at time t = 0, we can (0)

(0)

use (19a) to compute the temporal evolution of the state probabilities vq¯ (t). Given vq¯ (t), (19b) (1)

permits us to compute the conditional first moments vq¯ (t). Moreover, repeating this process (m−1)

(m)

for m = 2, 3, . . ., we can successively compute the conditional moments vq¯ (t) from vq¯

(t)

to whatever order we wish. At each step of this process we need to solve a system of first order linear differential equations with n|Q| variables. In the transform domain, the situation in (19c) (0)

(s)

is even simpler; given vq¯ (t), a single set of n|Q| differential equations defines vq¯ (t). III. S TATIONARY M OMENTS AND THE S TATIONARY MGF While using Lemma 1 to calculate these age moment trajectories may be of interest, the primary value of the lemma is in deriving stationary moments of the AoI. A foundational assumption for age analysis is that the Markov chain q(t) is ergodic; otherwise, time-average

14

(0)

age analysis makes little sense. Under this assumption, the state probabilities vq¯ (t) in (19a) ¯ q(0) satisfying always converge to unique stationary probabilities v ¯ q(0) v ¯

X

λ(l) =

¯ q(0) , λ(l) v l

(20a)

l∈L0q¯

l∈Lq¯

X

X

¯ q(0) v ¯ = 1.

(20b)

q¯∈Q

Moreover, we see in Lemma 1 that this convergence of state probabilities is disconnected from the evolution of the age process. This is as expected since the age process x(t) is a measurements process that does not influence the evolution of the queue state. Going forward, we assume that the discrete-state Markov chain q(t) is ergodic and that the (0) ¯ q(0) state probabilities vq¯ (t) are given by the stationary probabilities v ¯ . Under these ergodicity

and stationarity assumptions, we see from Lemma 1 that (19b) for m = 1 is reduced to a system of first order differential equations (1) ¯ q(0) v˙ q¯ (t) = v ¯ +

X

(1)

λ(l) vq(1) (t)Al − vq¯ (t) l

l∈L0q¯

in the vector v(1) (t) = [v0(1) (t) · · ·

X

λ(l) ,

q¯ ∈ Q,

(21)

l∈Lq¯ (1) vqmax (t)]. While Lemma 1 holds for any set of reset maps

{Al }, the differential equation (21) may or may not be stable. Stability depends on the specific (1) collection of reset maps5 . When (21) is stable, each vq¯ (t) = E x(t)δq¯,q(t) converges to a limit ¯ q(1) v ¯ as t → ∞. In this case, it then follows from (12) that the average age is E[x] = lim E[x(t)] = lim t→∞

t→∞

X X (1) ¯ q¯ . E x(t)δq¯,q(t) = v q¯∈Q

(22)

q¯∈Q

(0) (1) We can calculate these limiting values by setting the derivatives v˙ q¯ (t) and v˙ q¯ (t) in Lemma 1

¯ q(0) ¯ q(1) to zero and solve for the limiting values v ¯ and v ¯ . We note that Lemma 1 is in a form that shows how the “probability flow” in (19a) is similar to the “age flow” in (19b) and (19c). However, these forms are not concise in that multiple instances (·)

(·)

of vql on the right side of (19) may refer to the same vq . To characterize the convergence of the differential equations in Lemma 1, we now rewrite these equations in matrix form in terms 5

For example, if [bq ]1 = 1 for all q and each Al maps x01 = x1 , then x1 (t) = t simply tracks the passage of time and grows without bound for all states q.

(m) vq1 (t)

15

of the long row vectors v(m) (t) = [v0(m) (t) · · ·

vqmax (t)],

(m)

v(s) (t) = [v0(s) (t) · · ·

vqmax (t)].

(23a)

(s)

(23b)

Starting with the differential equations (19), we define the departure rate from state q¯ as dq¯ =

X

λ(l)

(24)

l∈Lq¯

and the n|Q| × n|Q| diagonal matrix D = diag[d0 In , . . . , dqmax In ].

(25)

We also define Lij = {l ∈ L : ql = i, ql0 = j},

i, j ∈ Q,

(26)

as the set of SHS transitions from state i to state j. This permits us to define the block matrices ˆ such that for i, j ∈ Q, blocks i, j of R and R ˆ are given by R and R X

Rij =

λ(l) Al ,

(27a)

ˆ l. λ(l) A

(27b)

l∈Lij

X

ˆ ij = R

l∈Lij

A. Matrix Evaluation of the Moment Vector With the observation that L0q¯ = ∪i Li¯q , we now can rewrite (19b) as (m) (m−1) v˙ q¯ (t) = mvq¯ (t) +

XX i

(m)

λ(l) vq(m) (t)Al − dq¯vq¯ (t), l

q¯ ∈ Q.

(28)

l∈Li¯ q

With the substitution q¯ = j and the observation that ql = i for all l ∈ Lij , we obtain (m) (m−1) v˙ j (t) = mvj (t) +

X

(m)

vi (t)

i (m−1)

= mvj

(t) +

X i

X

(m)

λ(l) Al − dj vj (t)

l∈Lij (m)

(m)

vi (t)Rij − dj vj (t),

j ∈ Q.

(29)

16

It follows from (23a) that (29) can be written in vector form as v˙ (m) (t) = mv(m−1) (t) + v(m) (t)(R − D).

(30)

¯ (0) and thus for m = 1 we obtain By stationarity of q(t), v(0) (t) = v ¯ (0) + v(1) (t)(R − D). v˙ (1) (t) = v

(31)

¯ (1) yields We note that setting v˙ (1) (t) = 0 and solving for v(1) (t) = v ¯ (1) D = v ¯ (0) + v ¯ (1) R. v

(32)

¯ (0) > 0 and there exists a non-negative solution v ¯ (1) for (32), then all eigenvalues Lemma 2: If v of R − D have strictly negative real parts. Proof of Lemma 2 follows from non-negativity of D and R and appears in the Appendix. ¯ (1) for (32) implies that the Lemma 2 says that the existence of a non-negative solution v ¯ (1) such that differential equation (31) for v(1) (t) is stable and that limt→∞ v(1) (t) = v ¯ (1) = v ¯ (0) (D − R)−1 . v

(33)

¯ (1) as the stationary first moment of the age process. Similarly, In the following, we refer to v ¯ (m) will denote the stationary mth moment. Note that Lemma 2 requires that the finite state v Markov chain q(t) have no transient states; all components of the stationary probability vector ¯ (0) must be strictly positive. This condition is carried forward in the next theorem. v Theorem 1: If the discrete-state Markov chain q(t) is ergodic with stationary distribution ¯ (0) > 0 and we can find a non-negative solution v ¯ (1) = [v v ¯ 0(1) · · · (a) v(m) (t) = [v0(m) (t) · · ·

] for (32), then ¯ q(1) v max

(m) vqmax (t)] converges to the stationary mth moment

¯ (m) = [v v ¯ 0(m) · · ·

m ¯ (0) (D − R)−1 , ] = m! v ¯ q(m) v max

(34a)

(b) and E[xm (t)] converges to the stationary mth moment age vector qmax m

E[x ] =

X

¯ q(m) . v

(34b)

q=0

Proof by induction appears in the Appendix. We note for m = 1 that Theorem 1 is a restatement

17

of [12, Theorem 4] using matrix notation. The proof follows almost directly from Lemma 2. B. Evaluation of the MGF Vector We now follow similar steps for the MGF. Recalling L0q¯ = ∪i Li¯q , we rewrite (19c) as (s) (s) v˙ q¯ (t) = svq¯ (t) +

h i (0) ˆ l − dq¯vq(s) λ(l) vq(s) (t)A + v (t) A l ¯ (t). ql l

XX i

(35)

l∈Li¯ q

With the substitution q¯ = j and the observation that ql = i for all l ∈ Lij , we obtain (s) v˙ j (t)

=

(s) svj (t)

+

X

(s) vi (t)Rij

+

(0) ˆ ij vi (t)R

(s)

− dj vj (t).

(36)

i

It follows from (23b) and (27) that (36) can be written in vector form as ˆ v˙ (s) (t) = v(s) (t)(R − D + sI) + v(0) (t)R.

(37)

¯ (0) . Moreover, if Under our stationarity assumption, the state probability vector is v(0) (t) = v ¯ (1) for (32), then the eigenvalues of R − D have strictly there exists a non-negative solution v negative real parts. This implies there exists s0 > 0 such that for all s < s0 the eigenvalues of R − D + sI have strictly negative real parts and v(s) (t) will converge to the fixed point given by v˙ (s) (t) = 0. We state this observation in the following claim. Theorem 2: If the discrete-state Markov chain q(t) is ergodic with stationary distribution ¯ (0) > 0 and there exists a stationary first moment v ¯ (1) ≥ 0 satisfying (32), then v (a) there exists s0 > 0 such that for all s < s0 , v(s) (t) converges to the stationary MGF vector ¯ (s) = [v v ¯ 0(s) · · ·

ˆ ¯ (0) R(D ]=v − R − sI)−1 ; ¯ q(s) v max

(38a)

(b) the MGF E esx(t) converges to the stationary vector qmax

E[esx ] =

X

¯ q(s) . v

(38b)

q=0

As one would expect, the stationary MGF is sufficient to rederive the stationary moments ˆ ¯ (s) (D − R − sI) = v ¯ (0) R. found in Theorem 1. For example, by rewriting (38a) we obtain v Taking the derivative of both sides yields ¯ (s) dv ¯ (s) = 0. (D − R − sI) − v ds

(39)

18

Source 0

µ0

x1

µ1

x2

µ2

µn−1

xn

Fig. 3. The n-node line network model. Node i forwards its current state update as a rate µi Poisson process to node i + 1.

Evaluating at s = 0 and rearranging yields the Theorem 1 claim ¯ (s) dv ¯ (0) (D − R)−1 = v ¯ (m) m=1 . =v ds s=0

(40)

¯ (m) . In the same way, successive derivatives of (39) will yield the higher order moments v While the age moments of Theorem 1 are indeed a simple consequence of the MGF, it is ¯ (1) of the age. The existence of the worth re-emphasizing the central role of the first moment v first moment, i.e. the average age, guarantees the existence of, and convergence to, the stationary MGF vector of the age process. IV. P REEMPTIVE LINE NETWORKS Convergence to a stationary MGF vector in Theorem 2 indicates that each component xi (t) of the age vector x(t) has converged to a stationary distribution FXi (·). In the following, we examine age in networks using the stationary MGF vector. For these networks, we assume the following definition holds. Definition 2: The AoI SHS (Q, 1, A) is a stationary age process if the Markov chain q(t) ¯ (0) > 0, there exists non-negative first moment v ¯ (1) satisfying (32), has stationary probabilities v ¯ (s) . and v(s) (t) = v ¯ (s) . Practically, this is a These conditions hold by initializing the system with v(s) (0) = v ¯ (1) implies weak assumption since Theorem 2 tells us that the existence of the first moment v ¯ (s) . exponential convergence of v(s) (t) to the fixed point v We now apply Theorem 2 to the preemptive LCFS line network depicted in Figure 3. In this system, source node 0 generates fresh updates as a rate λ = µ0 Poisson process. These updates pass through nodes 1, 2, . . . , n − 1 to sink node n such that each node i is a rate µi memoryless server supporting preemption in service. An update that arrives from node i − 1 immediately goes into service at node i and any preempted update is discarded.

19

1 0

2 .. 0

. n−1

Fig. 4. The SHS Markov chain for the line network with n nodes. The transition rates and transition/reset maps for links l = 0, . . . , n are shown in Table I.

l 0 1 2 .. .

λ(l) µ0 µ1 µ2 .. .

n − 1 µn−1

xAl [ 0 x2 [x1 x1 [x1 x2 .. . [x1 x2

x3 · · · xn−1 xn ] x3 · · · xn−1 xn ] x2 · · · xn−1 xn ] x3 · · · xn−1 xn−1 ]

TABLE I TABLE OF TRANSITIONS FOR THE SHS M ARKOV CHAIN IN F IGURE 4.

We expand here on an initial SHS analysis [43] that showed that the average age is additive from hop to hop. Specifically, with fresh updates arriving at node 1 as a rate λ Poisson process, the expected age E[xn (t)] at the monitor converges to the stationary expected value6 E[Xn ] =

1 1 1 + + ··· + . µ0 µ1 µn−1

(41)

In [43], it was observed that the memory in the network associated with the idle/busy state of each queue made it difficult to use graphical methods of AoI calculation. Moreover, to avoid a combinatorial explosion in the SHS analysis associated with tracking the idle/busy state of each server, the method of “fake updates” [12] was used to collapse the state space into a single state in which all nodes are perpetually busy. Fake updates were needed for the analysis because the continuous state x(t) tracked the ages of updates in the system. Here we take the alternate view that xi (t) monitors the age based on updates that reach node i. This allows for an alternate interpretation of the system depicted in Figure 3. In this model, a node i represents a monitor that forwards its current state to node i + 1 as a Poisson point process. The transmission/delivery of an update occurs instantaneously and µi is the rate of a Poisson point process for these instantaneous updates. 6

A discrete-time version of this result was first recognized in [36, Theorem 1].

20

We now evaluate age along the line network. With xi (t) as the age at node i, the network state is x(t) = [x1 (t) · · ·

xn (t)]. The SHS has the trivial discrete state space Q = {0}

¯ (0) = 1. From (13a), the mth moment of the age at time t is and stationary probabilities v (m)

v(m) (t) = v0 (t) = E[xm (t)]. The state transitions are shown in Table I. Note that •

Transition l = 0 marks the arrival of a fresh update at node 1. In the continuous state x, we set x01 = 0 but all other components of x are unchanged.

•

In a transition l ∈ {1, . . . , n − 1}, an update is sent from node l to node l + 1. At node l + 1, x0l+1 = xl . At all other nodes, the age is unchanged.

All transitions are trivially 0 → 0 self transitions and the total rate of transitions out of state 0 P is d0 = n−1 i=0 µi . Thus D = d0 I. From Table I, we can infer the n × n transition matrices Al and construct R given in (27a). By following these steps and applying Theorem 1, the following claim is verified in the Appendix. Theorem 3: The n-node line network has stationary mth moment age vector h m ¯ (m) = lim E[xm v 1 (t)] E[x2 (t)] · · · t→∞ m 1 1 1 · · · µ0 µ0 µ0 1 1 . . . µ1 µ1 = m! 1 . .. . .. .

i (t)] E[xm n

(42)

1 µn−1

We now examine the MGF vector. In the Appendix, we employ D and R from the proof of ˆ as specified by (27b). Since Q = {0}, it follows from (13b) Theorem 3 and then construct R (s) that the MGF vector is E esx(t) = v(s) (t) = v0 (t). By applying Theorem 2, the following claim is verified in the Appendix. Theorem 4: The n-node line network has stationary MGF ¯ v

(s)

h sx (t) sx (t) i sx (t) 1 2 = lim E e E e ··· E e n t→∞ # " 1 n−1 Y Y µi µi µ0 . = ··· µ0 − s i=0 µi − s µ − s i i=0

(43)

The interpretation of Theorem 4 is that Xk , the stationary age at node k, has distribution Xk ∼ Z0 ⊕ · · · ⊕ Zk−1 ,

(44)

21

where the Zi are independent exponential (µi ) random variables. We also note that Theorem 4 generalizes the sum result (41) for the average age originally derived in [43]. V. S AMPLING S TATIONARY AGE P ROCESSES For the stationary age process x(t) of the line network, we observe in (44) that the distribution of the age Xi+1 at node i is described by Xi+1 ∼ Xi ⊕ Zi ,

(45)

where Zi is an exponential (µi ) random variable independent of Xi . From the earlier perspective [43] of update packets and preemptive memoryless queues, this is a counterintuitive observation as the preemption and discarding along the line network is a complex process with memory. However, this result will prove less surprising when we view Xi+1 as the age of a monitor positioned at node i + 1. In particular, there is a rate µi Poisson point process of updates being conveyed instantaneously from the monitor at node i to the monitor at node i + 1. An arrival of this process at time t resets xi+1 (t) to xi (t). Between arrivals of these updates, the age process at node i + 1 grows at unit rate. In fact, this is an example of the more general situation in this definition: Definition 3: Node j is sampling the update process at node i if (a) xi (t) is an age process for a monitor at node i that maintains a current update, i.e. a copy of its freshest update. (b) There is a point process that marks the time instances that the current update at node i is delivered to node j. (c) When node i delivers an update to j at time t0 , the age xj (t0 ) is reset to x0j (t0 ) = xi (t0 ), the age of the just received update. (d) In the absence of an update from node i, the age at node j grows at unit rate. We say that node j is sampling the status update process at node i because node j receives a subsequence of those state samples delivered to node i. While this sampling is defined in terms of the state updates sent from i to j, it is also convenient from the perspective of age analysis to say node j is sampling the age process at node i. In the case of the Figure 3 line network, each node j = i + 1 is sampling the node i status update process as a rate µi Poisson process. The inter-update times of this sampling process are iid exponential (µi ) random variables. The Poisson sampling on the line network can be

22

Source 0

Y0

x1

Y1

x2

Y2

Yn−1

xn

Fig. 5. The linear status sampling network with n nodes. Node i + 1 samples the update process at node i at time instances that form a renewal process with renewal times identical to Yi .

generalized to sampling through an renewal process in which the renewal points mark the time instances that updates from i are delivered to j. A. Status Sampling Renewal Processes We now analyze the AoI induced by a status-sampling renewal process. Suppose that the most recent update delivery from node i occurred at time t − Z(t). We recall from Section I that Z(t) is the age of the renewal process. In particular, Z(t) will have a sample path like that shown in Figure 1(a). When this renewal process is in equilibrium and has inter-update times that are iid continuous random variables identical to Y , Z(t) is stationary and has PDF [14, Theorem 5.7.4] fZ (z) =

F Y (z) . E[Y ]

(46)

Moreover, it follows from conditions (c) and (d) in Definition 3 that the age at node j is Xj (t) = Xi (t − Z(t)) + Z(t).

(47)

We now show that (47) yields the following claim. Theorem 5: If node j is sampling a stationary age process Xi (t) at node i according to an equilibrium renewal process with inter-update times identical to Y and stationary renewal process age Z distributed according to (46), then the age Xj (t) at node j is a stationary process identical in distribution to Xj ∼ Xi ⊕ Z.

(48)

Proof: (Theorem 5) From (47) we can use the MGF to write E esXj (t) |Z(t) = z = E es(Xi (t−z)+z) |Z(t) = z = esz E esXi (t−z) |Z(t) = z = esz E esXi (t−z)

(49a) (49b) (49c)

23

= esz E esXi (t) ,

(49d)

where (49c) follows from independence of the Xi (t) and Z(t) processes, and (49d) holds because Xi (t) is stationary. Thus E esXj (t) |Z(t) = esZ(t) E esXi (t) and averaging over Z(t) we obtain E esXj (t) = EZ(t) esXj (t) |Z(t) = EZ(t) esZ(t) esXi (t) = E esZ(t) E esXi (t) .

(50)

Since Xi (t) and Z(t) are stationary processes, they are identical to Xi and Z in distribution and thus (45) holds. For the line network, the derivation of (45) relied on the age process x(t) being generated by an AoI SHS. However, this assumption is not required in the steps of (49) and (50). All that is needed is that Xi (t) is a stationary age process that is independent of the equilibrium renewal process that controls the sampling. With this notion of sampling an update process, we can generalize the Figure 3 line network. Instead of memoryless updating, we now assume that node i + 1 samples the update process at node i according to a renewal process with inter-renewal times identical to random variable Yi . This network is depicted in Figure 5. When each Yi has an exponential (µi ) distribution, the age at each network node is identical to the age in the line network of preemptive LCFS servers in Figure 3. In general however, the network in Figure 5 should not be mistaken for a queueing network as there are no easily defined customer service times. Instead, it is an example of an status sampling network in which each node samples the updating process of each preceding node in the line. In this network, status sampling at node i is an equilibrium renewal process with stationary age Zi with PDF in the form of (46) and moments E[Zi ] =

E[Yi2 ] , 2 E[Yi ]

E[Yi3 ] E Zi2 = . 3 E[Yi ]

(51)

The age at source node 0 is always zero and is trivially stationary. By Theorem 5, Xi+1 ∼ Xi ⊕Zi and stationarity of Xi (t) implies stationarity of Xi+1 (t). It follows that the age at node k is given by Xk ∼ Z0 ⊕ · · · ⊕ Zk−1 .

(52)

24

age

14 12

x 3 (t)

10

x 2 (t) x 1 (t)

8 6 4 2 0 0

5

10

15

20

25

30

35

time Fig. 6. Sample paths of age processes x1 (t), x2 (t) and x3 (t) when node i + 1 is sampling the update process at node i. For each node, status sampling times are chosen according to an independent renewal process. Node 1 receives fresh updates, the age process x1 (t) is reset to zero when an update is received. At nodes 2 and 3, the squares and crosses mark the respective sampling times.

We demonstrate this behavior with a simulation of the status sampling network shown in Figure 5 in which each sampling renewal time Yi is a continuous uniform (0, b) random variable Y and each Zi has PDF given by (46). Starting at time 0 with the age vector x(0) = 0, age samples forwarded by each node i are used to generate the age process Xi+1 (t) at node each node i + 1. Specifically, at node i, the iid sequence Yi,1 , Yi,2 , . . . , Yi,m of uniform (0, b) update P interarrival times is generated. At each time Ti,j = jk=1 Yi,k , age sample Xi (Ti,j ) is forwarded to node i + 1. This sequence of samples yields the Z(t) function in (47) with j = i + 1, and this enables construction of the age process Xi+1 (t). This sampling and age sample path construction process is successively repeated at each node. This construction method is depicted graphically in Figure 6.7 At each node i, samples of the age process Xi (t) are used to form the normalized histograms shown in Figure 7. From (52), the PDF of each Xk has is the k-fold convolution of the PDF of Z. In particular, when the inter-update time Y has a uniform (0, b) PDF, (46) implies 2 1 − x 0 ≤ x ≤ b, b b fX1 (x) = 0 otherwise, 7

In discrete time, this same sample path construction has previously appeared in [36].

(53)

25

0.35

0.2 n=1 n=2

Sample Frequency

Sample Frequency

0.3 0.25 0.2 0.15 0.1

n=3 n=4 n=5

0.15

0.1

0.05

0.05 0

0 0

2

4

6

8

10

12

2

4

6

Age

8

10

12

14

16

18

20

Age

(a) n = 1, 2

(b) n=3,4,5

Fig. 7. Sample frequency histograms from sample paths of Xn (t) for n ∈ {1, . . . , 5}. Each Xn (t) is a stationary process with 2 E[Xn ] = 2n and σX = 2n. (a) For n = 1, 2, normalized histgrams are shown to match the corresponding PDFs fX1 (x) and n fX2 (x). (b) For n = 3, 4, 5, each histogram is compared with the approximating Gaussian PDF of the same mean and variance.

4x 1 − xb + 2 b fX2 (x) = 2 2 − x 3 3b b 0

x2 6b2

0 ≤ x ≤ b, b ≤ x ≤ 2b,

(54)

otherwise.

In Figure 7(a), histograms from sample paths of X1 (t) and X2 (t) are shown to be in correspondence with the PDFs fX1 (x) and fX2 (x). In addition, it follows from (51) that each Zi has moments E[Z] = b/3 and E[Z 2 ] = b2 /6. Under stationarity, each Xk (t) has expected value E[Xk ] = kb/3 and variance Var[Xk ] = k Var[Z] = kb2 /18. As n becomes large, the central limit theorem will take effect. To examine this convergence, Figure 7(b) compares the sample histograms against the Gaussian PDFs of the same mean and variance as Xn for n = 3, 4, 5. We see for small n that the Gaussian approximation is a reasonable fit. The distribution of Xn is skewed leftward relative tot eh corresponding Gaussian; but this is not surprising inasmuch as the uniform PDF of Y implies the PDF of each Z is skewed to the left. VI. C ONCLUSION We have employed an age of information metric to examine the problem of a source delivering timely status through a network to a monitor. We have employed stochastic hybrid systems to enable evaluation of all moments of the age as well as the MGF of the age in any network described by a finite-state continuous-time Markov chain. To the best of our knowledge, the MGF vector results are the first explicit age distribution results for updates traversing multihop

26

routes in networks. In addition, for the iid sum (52), the MGF would facilitate finding useful bounds on the tail of Xn , if that were needed. We have shown that SHS enables straightforward computation of both the moments and the moment generating functions of the age vector components. These MGFs provide distributional characterization of the age process. In the example of the line network with preemptive memoryless servers, we generalized the prior SHS analysis [43] that showed the average age is additive across the links of the network by showing that the age at a node is distributed according to a sum of independent renewal process age random variables. In the case of preemptive memoryless servers, these renewal process age random variables were also exponentially distributed. However, this observation was generalized in Section V by showing it holds for all equilibrium renewal processes with continuous inter-update distributions and stationary age processes. The key to this generalization is the concept of sampling an update process. The insights from these simple observations lead us to believe that there is still considerable progress to be made in characterizing age of information in systems and networks. A PPENDIX Proof: (Lemma 1) In the following, m is a positive integer. From (14) and (15), we calculate (0) Lψq¯j ,

(m)

(s)

Lψq¯j and Lψq¯j for each j ∈ 1 : n and q¯ ∈ Q: (0)

(0)

Lψq¯j (q, x) = Λq¯j (q, x), (m−1)

(m)

Lψq¯j (q, x) = mψq¯j (s)

(55a) (m)

(q, x) + Λq¯j (q, x),

(s)

(s)

Lψq¯j (q, x) = sψq¯j (q, x) + Λq¯j (q, x),

(55b) (55c)

where (0)

Λq¯j (q, x) =

i Xh (0) (0) ψq¯ (φl (q, x)) − ψq¯ (q, x) λ(l) (q),

(56a)

l∈L

i Xh (m) (m) (m) Λq¯j (q, x) = ψq¯j (φl (q, x)) − ψq¯j (q, x) λ(l) (q),

(56b)

l∈L

i Xh (s) (s) (s) Λq¯j (q, x) = ψq¯j (φl (q, x)) − ψq¯j (q, x) λ(l) (q).

(56c)

l∈L

When φl (q, x) = (ql0 , xAl ), (0)

(0)

ψq¯j (φl (q, x)) = ψq¯j (ql0 , xAl ) = δq¯,ql0 ,

(57a)

27

(m)

(m)

(57b)

(s)

(s)

(57c)

m 0 0 ψq¯j (φl (q, x)) = ψq¯j (ql0 , xAl ) = [xAl ]m j δq¯,ql = [x Al ]j δq¯,ql ,

ψq¯j (φl (q, x)) = ψq¯j (ql0 , xAl ) = es[xAl ]j δq¯,ql0 .

m In (57b), we note that that [xAl ]m j = [x Al ]j because Al is a binary matrix such that each

column has no more than one nonzero entry. Since λ(l) (q) = λ(l) δql ,q , it follows from (56) and (57) that (0)

Λq¯j (q, x) =

X

λ(l) δq¯,ql0 − δq¯,q δql ,q ,

(58a)

λ(l) [xm Al ]j δq¯,ql0 − xm j δq¯,q δql ,q ,

(58b)

λ(l) es[xAl ]j δq¯,ql0 − esxj δq¯,q δql ,q .

(58c)

l∈L (m) Λq¯j (q, x)

=

X

=

X

l∈L (s) Λq¯j (q, x)

l∈L

We observe that δq¯,ql0 δql ,q =

δq¯,q δql ,q =

δq ,q l

l ∈ L0q¯,

0 δq¯,q

l ∈ Lq¯,

0

otherwise.

(59a)

otherwise,

(59b)

It follows from (17), (58) and (59) that (0)

Λq¯j (q, x) =

X l∈L0q¯

(m)

Λq¯j (q, x) = (s)

Λq¯j (q, x) =

X

λ(l) δql ,q − δq¯,q

X

λ(l) ,

(60a)

l∈Lq¯

λ(l) [xm Al ]j δql ,q − xm j δq¯,q

X

l∈L0q¯

l∈Lq¯

X

λ(l) es[xAl ]j δql ,q − esxj δq¯,q

X

l∈L0q¯

λ(l) ,

(60b)

λ(l) .

(60c)

l∈Lq¯

(0)

With ψ(q, x) = ψq¯j (q, x), (7a) at m = 0, (16), (55a) and (60a) imply h i (0) (0) v˙ q¯j (t) = E Lψq¯j (q(t), x(t)) h i (0) = E Λq¯j (q(t), x(t)) X X = E λ(l) δql ,q(t) − δq¯,q(t) λ(l) l∈L0q¯

l∈Lq¯

28

=

X

(0)

λ(l) vq(0) (t) − vq¯ (t) l

l∈L0q¯

X

λ(l) ,

q¯ ∈ Q.

(61)

l∈Lq¯

Gathering the equations in (61) and rewriting in terms of the vector of duplicated state proba(0)

bilities vq¯ (t), we obtain (19a) in Lemma 1. (m)

For j ∈ 1 : n with ψ(q, x) = ψq¯j (q, x), (7), (16) and (55b) imply h i (m) (m) v˙ q¯j (t) = E Lψq¯j (q(t), x(t)) h i h i (m−1) (m) = E mψq¯j (q(t), x(t)) + E Λq¯j (q(t), x(t)) h i (m−1) (m) = mvq¯j (t) + E Λq¯j (q(t), x(t)) .

(62)

From (60b), we observe that i X h X (l) (m) λ(l) E xm (t)δql ,q(t) Al j − E xm E Λq¯j (q(t), x(t)) = λ j (t)δq¯,q(t) l∈L0q¯

X

=

l∈Lq¯

(m) λ(l) vq(m) (t)Al j − vq¯j (t) l

l∈L0q¯

X

λ(l) .

(63)

l∈Lq¯

It then follows from (62) and (63) that (m−1)

(m)

v˙ q¯j (t) = mvq¯j

(t) +

X

X (m) λ(l) . (t) λ(l) vq(m) (t)A − v l j q¯j l

l∈L0q¯

(64)

l∈Lq¯

Gathering the equations in (64) for j ∈ 1 : n and rewriting as row vectors, we obtain (19b) in Lemma 1. (s)

For j ∈ 1 : n with ψ(q, x) = ψq¯j (q, x), (7), (16) and (55c) imply (s) v˙ q¯j (t)

h i (s) = E Lψq¯j (q(t), x(t)) h i h i (s) (s) = E sψq¯j (q(t), x(t)) + E Λq¯j (q(t), x(t)) h i (s) (s) = svq¯j (t) + E Λq¯j (q(t), x(t)) .

(65)

From (60c), we observe that h i X X (l) (s) E Λq¯j (q(t), x(t)) = λ(l) E es[x(t)Al ]j δql ,q(t) − E esxj (t) δq¯,q(t) λ l∈L0q¯

=

X l∈L0q¯

l∈Lq¯

X (s) λ(l) E es[x(t)Al ]j δql ,q(t) − vq¯j (t) λ(l) . l∈Lq¯

(66)

29

Similarly, if [Al ]j = e> k , then [xAl ]j = xk and (s) E es[x(t)Al ]j δql ,q(t) = E esxk (t) δql ,q(t) = vql k (t) = [vq(s) (t)Al ]j . l

(67a)

However, if [Al ]j = 0> , then (t). E es[x(t)Al ]j δql ,q(t) = E δql ,q(t) = vq(0) l

(67b)

ˆ l in (18), the two cases in (67) can be written in the combination form With the definition of A ˆ l] (t)Al + vq(0) (t)A E es[x(t)Al ]j δql ,q(t) = [vq(s) j l l

(68)

ˆ l ]j = 0> . It then follows from (65), (66) and (68) that because either [Al ]j = 0> or [A (s)

(s)

v˙ q¯j (t) = svq¯j (t) +

X

ˆ l ] − v (s) (t) λ(l) [vq(s) (t)Al + vq(0) (t)A q¯j j l l

l∈L0q¯

X

λ(l) .

(69)

l∈Lq¯

Gathering the equations (69) for j ∈ 1 : n and rewriting as row vectors, we obtain (19c) in Lemma 1 to complete the proof. Proof: (Lemma 2) Let σ = 1 + maxi di , then σI − D is a strictly positive diagonal matrix. ¯ (1) (σI − D) to both sides of (32) yields Adding v ¯ (0) + v ¯ (1) (σI + R − D). σ¯ v(1) = v

(70)

Because the reset maps Al are binary, R is non-negative and thus σI + R − D is also nonnegative. It follows that σI + R − D has a dominant real eigenvalue r(σ) ≥ 0 with an associated non-negative non-zero right eigenvector u> such that || ≤ r(σ) for any other eigenvalue [45, Exercise 1.12]8 . Right multiplying (70) by u> , we obtain ¯ (0) u> + r(σ)¯ σ¯ v(1) u> = v v(1) u> ,

(71)

¯ (0) u> [σ − r(σ)]¯ v(1) u> = v

(72)

which simplifies to

¯ (0) is strictly positive and u> is non-negative and non-zero, v ¯ (0) u> > 0. Non-negativity Since v 8

This is a weak form of the Perron-Frobenius theorem that does not require irreducibility of the non-negative matrix.

30

¯ (1) implies v ¯ (1) u> ≥ 0 and it follows that σ − r(σ) > 0. If is an eigenvalue of σI + R − D of v then − σ is an eigenvalue of R − D and has real part Re( − s) = Re() − σ ≤ || − σ ≤ r(σ) − σ < 0.

(73)

Proof: (Theorem 1) We prove Theorem 1(a) by induction. For m = 1, we observe that from Lemma 2 that the existence of the fixed point v(1) implies that R − D has stable eigenvalues ¯ (1) . We now assume and that the differential equation (31) converges to limt→∞ v(1) (t) = v ¯ (m−1) = (m − 1)!¯ lim v(m−1) (t) = v v(0) [(D − R)−1 ]m−1 .

t→∞

(74)

Since R − D has stable eigenvalues, it follows from (30) that v˙ (m) (t) → 0 and that ¯ (m) (R − D). 0 = m¯ v(m−1) + v

(75)

¯ (m) = m¯ v v(m−1) (D − R)−1 = m!¯ v(0) [(D − R)−1 ]m .

(76)

Thus,

For part (b), we observe that E[xm ] = lim E[xm (t)] = lim t→∞

t→∞

X X (m) ¯ q¯ . E xm (t)δq¯,q(t) = v q¯∈Q

(77)

q¯∈Q

Proof: (Theorem 3) From Table I, we construct the n dimensional transition matrices Al ; for example, A0 = diag[0, 1, . . . , 1], 1 1 0 0 A1 = 1 .. .

(78a)

, 1

(78b)

31

and

An−1

1 1 . . .. = 1 1 0 0

(78c)

With the shorthand notation βj = d0 − µj , we use (27a) to construct

R = R00

β0 µ1 β µ 1 2 n−1 X . = µl A l = β2 . . l=0 . . . µn−1 βn−1

(79)

and this permits us to write

µ0 −µ1

D−R=

µ1

... .. . −µn−1 µn−1

−µ2 µ2

(80)

and (D − R)−1

1 µ0

=

1 µ0

···

1 µ0

1 µ1

... .. .

1 µ1

. .. .

(81)

1 µn−1

The claim follows from Theorem 1. Proof: (Theorem 4) From Table I, the transition matrices Al are given in (78). Similarly, R and D − R are given in (79) and (80). We note that Ai has no all-zero columns for i ≥ 1. Thus it follows from (27b) and (78a) that ˆ =R ˆ 00 = µ0 A ˆ 0 = diag[µ0 , 0, · · · , 0]. R

(82)

32

Defining µ ¯i = µi − s,

i ∈ 0 : n − 1,

(83)

it follows from (80) that µ ¯0 −µ1 µ ¯1 −µ2 . . .. D − R − sI = µ ¯ 2 ... −µ n−1 µ ¯n−1

(84)

This implies

1 µ ¯0

=

(D − R − sI)−1

µ1 µ ¯0 µ ¯1 1 µ ¯1

µ1 µ2 µ ¯0 µ ¯1 µ ¯2 µ2 µ ¯1 µ ¯2

···

1 µ ¯0

...

1 µ ¯1

1 µ ¯2

··· .. .

1 µ ¯2

Qn

.. .

µi i=1 µ ¯i Qn µi i=2 µ ¯i Qn µi . i=3 µ ¯i

1 µ ¯n−1

(85)

¯ (0) = 1, we employ (82) and Theorem 2 to write Recalling that v ˆ ¯ (s) = v ¯ (0) R(D − R − sI)−1 v h = µµ¯0 µµ¯0 µµ¯1 µµ¯0 µµ¯1 µµ¯2 · · · 0

0 1

0 1 2

Qn−1

µi i=0 µ ¯i

i

.

(86)

The claim follows from the definition (83). R EFERENCES [1] A. Karakasidis, P. Vassiliadis, and E. Pitoura, “ETL queues for active data warehousing,” in Proceedings of the 2nd international workshop on Information quality in information systems, ser. IQIS ’05. Baltimore, Maryland: ACM, 2005, pp. 28–39, ACM ID: 1077509. [2] H. Yu, L. Breslau, and S. Shenker, “A scalable web cache consistency architecture,” SIGCOMM Comput. Commun. Rev., vol. 29, no. 4, pp. 163–174, Aug. 1999, ACM ID: 316219. [3] M. Xiong and K. Ramamritham, “Deriving deadlines and periods for real-time update transactions,” in The 20th IEEE Real-Time Systems Symposium, 1999. Proceedings. IEEE, 1999, pp. 32–43. [4] Y. C. Hu and D. B. Johnson, “Ensuring cache freshness in on-demand ad hoc network routing protocols,” in Proceedings of the second ACM international workshop on Principles of mobile computing, 2002, pp. 25–30. [5] V. C. Giruka and M. Singhal, “Hello protocols for ad-hoc networks: overhead and accuracy tradeoffs,” in World of Wireless Mobile and Multimedia Networks, WoWMoM, Sixth IEEE International Symposium on. IEEE, Jun. 2005, pp. 354–361. [6] P. Papadimitratos, A. La Fortelle, K. Evenssen, R. Brignolo, and S. Cosenza, “Vehicular communication systems: Enabling technologies, applications, and future outlook on intelligent transportation,” IEEE Communications Magazine, vol. 47, no. 11, pp. 84–95, Nov. 2009. [7] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of information in vehicular networks,” in IEEE Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), Salt Lake City, Utah, USA, 2011.

33

[8] S. K. Kaul, R. D. Yates, and M. Gruteser, “On piggybacking in vehicular networks,” in IEEE Global Telecommunications Conference, GLOBECOM 2011, Dec. 2011. [9] B. Kloiber, C. Garcia, J. H¨arri, and T. Strang, “Update delay: A new information-centric metric for a combined communication and application level reliability evaluation of cam based safety applications,” in ITS World Congress, 2012. [10] M. van Eenennaam, L. Hendriks, G. Karagiannis, and G. Heijenk, “Oldest packet drop (opd): A buffering mechanism for beaconing in ieee 802.11p vanets (poster),” in Vehicular Networking Conference (VNC), 2011 IEEE, nov. 2011, pp. 252 –259. [11] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in Proc. IEEE INFOCOM Mini Conference, 2012. [12] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” CoRR, vol. abs/1608.08622, 2016, submitted to the IEEE Transactions on Information Theory. [Online]. Available: http://arxiv.org/abs/1608.08622 [13] S. M. Ross, Stochastic Processes, 2nd ed. John Wiley & Sons, 1996. [14] R. G. Gallager, Stochastic processes: theory for applications. Cambridge University Press, 2013. [15] C. Kam, S. Kompella, and A. Ephremides, “Effect of message transmission diversity on status age,” in Proc. IEEE Int’l. Symp. Info. Theory, June 2014, pp. 2411–2415. [16] S. Kaul, R. Yates, and M. Gruteser, “Status updates through queues,” in Conf. on Information Sciences and Systems (CISS), Mar. 2012. [17] R. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in Proc. IEEE Int’l. Symp. Info. Theory, Jul. 2012. [18] M. Costa, M. Codreanu, and A. Ephremides, “Age of information with packet management,” in Proc. IEEE Int’l. Symp. Info. Theory, June 2014, pp. 1583–1587. [19] C. Kam, S. Kompella, G. D. Nguyen, J. Wieselthier, and A. Ephremides, “Age of information with a packet deadline,” in Proc. IEEE Int’l. Symp. Info. Theory, 2016, pp. 2564–2568. [20] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “The stationary distribution of the age of information in FCFS singleserver queues,” in 2017 IEEE International Symposium on Information Theory (ISIT), June 2017, pp. 571–575. [21] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “A General Formula for the Stationary Distribution of the Age of Information and Its Application to Single-Server Queues,” ArXiv e-prints, Apr. 2018. [22] C. Kam, S. Kompella, and A. Ephremides, “Age of information under random updates,” in Proc. IEEE Int’l. Symp. Info. Theory, 2013, pp. 66–70. [23] C. Kam, S. Kompella, G. D. Nguyen, and A. Ephremides, “Effect of message transmission path diversity on status age,” IEEE Trans. Info Theory, vol. 62, no. 3, pp. 1360–1374, March 2016. [24] L. Huang and E. Modiano, “Optimizing age-of-information in a multi-class queueing system,” in Proc. IEEE Int’l. Symp. Info. Theory, Jun. 2015. [25] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” IEEE Trans. Info Theory, vol. 62, no. 4, pp. 1897–1910, April 2016. [26] K. Chen and L. Huang, “Age-of-information in the presence of error,” in Proc. IEEE Int’l. Symp. Info. Theory, 2016, pp. 2579–2584. [27] E. Najm and R. Nasser, “The age of information: The gamma awakening,” in Proc. IEEE Int’l. Symp. Info. Theory, 2016, pp. 2574–2578. [28] B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, “Age of information under energy replenishment constraints,” in Proc. Info. Theory and Appl. (ITA) Workshop, Feb. 2015, la Jolla, CA. [29] R. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in Proc. IEEE Int’l. Symp. Info. Theory, 2015. [30] Y. Sun, E. Uysal-Biyikoglu, R. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” in IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, April 2016, pp. 1–9. [31] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” IEEE Transactions on Information Theory, vol. 63, no. 11, pp. 7492–7508, 2017. [32] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” Foundations and Trends in Networking, vol. 12, no. 3, pp. 162–259, 2017. [Online]. Available: http://dx.doi.org/10.1561/1300000060 [33] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Optimizing data freshness, throughput, and delay in multi-server informationupdate systems,” in Proc. IEEE Int’l. Symp. Info. Theory, 2016, pp. 2569–2574. [34] ——, “Age-optimal information updates in multihop networks,” in Proc. IEEE Int’l. Symp. Info. Theory, June 2017, pp. 576–580. [35] ——, “The age of information in multihop networks,” CoRR, vol. abs/1712.10061, 2017. [Online]. Available: http://arxiv.org/abs/1712.10061 [36] R. Talak, S. Karaman, and E. Modiano, “Minimizing age-of-information in multi-hop wireless networks,” in 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Oct 2017, pp. 486–493. [37] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “Age and value of information: Non-linear age case,” in Information Theory (ISIT), 2017 IEEE International Symposium on. IEEE, 2017, pp. 326–330. [38] J. Hespanha, “Modelling and analysis of stochastic hybrid systems,” IEE Proceedings-Control Theory and Applications, vol. 153, no. 5, pp. 520–535, 2006.

34

[39] D. Vermes, “Optimal dynamic control of a useful class of randomly jumping processes,” International Institute for Applied Systems Analysis, Tech. Rep. PP-80-015, 1980. [40] B. Gnedenko and I. Kovalenko, “Introduction to the theory of mass service,” Nau (trad, ingles: 1968, Jerusalem), 1966. [41] M. H. A. Davis, “Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models,” J. Roy. Statist. Soc., vol. 46, pp. 353–388, 1984. [42] L. DeVille, S. Dhople, A. D. Dom´ınguez-Garc´ıa, and J. Zhang, “Moment closure and finite-time blowup for piecewise deterministic markov processes,” SIAM Journal on Applied Dynamical Systems, vol. 15, no. 1, pp. 526–556, 2016. [43] R. D. Yates, “Age of information in a network of preemptive servers,” in Proc. INFOCOM Workshop on Age of Information, 2018. [44] A. R. Teel, A. Subbaraman, and A. Sferlazza, “Stability analysis for stochastic hybrid systems: A survey,” Automatica, vol. 50, no. 10, pp. 2435–2456, 2014. [45] E. Seneta, Non-negative Matrices and Markov Chains, 2nd ed. Springer Verlag, 1981.