1

The Age of Information in Multihop Networks
Ahmed M. Bedewy† , Yin Sun⋆ , and Ness B. Shroff†‡

arXiv:1712.10061v1 [] 25 Dec 2017

†

Dept. of ECE, ‡ Dept. of CSE, The Ohio State University, Columbus, OH.
⋆
Dept. of ECE, Auburn University, Auburn, Alabama.
emails: bedewy.2@osu.edu, yzs0078@auburn.edu, shroff.11@osu.edu

Abstract
The problem of minimizing the age-of-information has been extensively studied in single-hop networks. In this paper, we minimize the age of a single information flow in multihop networks. If the packet
transmission times over the network links are exponentially distributed, we prove that a preemptive LastGenerated, First-Serve (LGFS) policy results in smaller age processes at all nodes of the network (in a
stochastic ordering sense) than any other causal policy. In addition, for arbitrary distributions of packet
transmission times, the non-preemptive LGFS policy is shown to minimize the age processes at all nodes
among all non-preemptive work-conserving policies (again in a stochastic ordering sense). Interestingly,
these simple policies can achieve optimality of the joint distribution of the age processes at all nodes
even under arbitrary network topologies, as well as arbitrary packet generation and arrival times. These
optimality results not only hold for the age processes, but also for any non-decreasing functional of
the age processes. Finally, we investigate the class of New-Better-than-Used (NBU) packet transmission
time distributions and show that the non-preemptive LGFS policy is within a constant age gap from the
optimum average age, and that the gap is independent of system parameters.

This paper was presented in part at IEEE ISIT 2017 [1].
This work has been supported in part by ONR grants N00014-17-1-2417 and N00014-15-1-2166, Army Research Office
grants W911NF-14-1-0368 and MURI W911NF-12-1-0385, National Science Foundation grants CNS-1446582, CNS-1421576,
and CNS-1518829, and a grant from the Defense Thrust Reduction Agency HDTRA1-14-1-0058.

January 1, 2018

DRAFT

2

/

.
!"#$%&'()*+,%-$

0

5'#$6'7

1

2

3

4

Figure 1: Information updates in a multihop network.

I. I NTRODUCTION
There has been a growing interest in applications that require real-time information updates, such as
news, weather reports, email notifications, stock quotes, social updates, mobile ads, etc. The freshness
of the information is also crucial in other systems, e.g., monitoring systems that obtain information from
environmental sensors, wireless systems that need rapid updates of channel state information, etc.
As a metric of data freshness, the age-of-information, or simply age, was defined in [2]–[5]. At
time t, if the freshest update at the destination was generated at time U (t), the age ∆(t) is defined as
∆(t) = t − U (t). Hence, age is the time elapsed since the freshest packet was generated.
In our recent work [6], [7], we have shown that the LGFS scheduling policy minimizes the age-ofinformation in single-hop networks in a quite strong sense. In this paper, we further investigate ageoptimal scheduling in multihop networks. We consider an interference free network represented by a
directed graph, as shown in Fig. 1, where the update packets are generated at an external source and
are then dispersed throughout the network via a gateway node. It is well known that delay-optimality
is notoriously difficult in multihop networks, except for some special network settings (e.g., tandem
networks) [8], [9]. This difficulty stems from the fact that the packet scheduling decisions at each hop
are influenced by the decisions on other hops and vice versa. Somewhat surprisingly, age minimization
has some significant differences from delay minimization. In particular, we find that some simple policies
can achieve optimality of the joint distribution of the age processes at all nodes, even under arbitrary
network topologies. The following summarizes our main contributions in this paper:
•

•

If the packet transmission times over the network links are exponentially distributed, then for any
arbitrary arrival process, network topology, and buffer sizes, the preemptive LGFS policy minimizes
the age processes at all nodes in the network among all causal policies in a stochastic ordering sense
(Theorem 1). In other words, the preemptive LGFS policy minimizes any non-decreasing functional
of the age processes at all nodes in a stochastic ordering sense. Note that this age penalty model is
very general. Many age penalty metrics studied in the literature, such as the time-average age [5],
[10]–[18], average peak age [11], [14], [18]–[20], time-average age penalty function [21], [22], and
age penalty functional at single-hop network [6], [7], are special cases of the general age functional
model that we consider in this paper.
We then prove that, for arbitrary distributions of packet transmission times, the non-preemptive
LGFS policy minimizes the age processes at all nodes among all non-preemptive work-conserving

January 1, 2018

DRAFT

3

•

policies in the sense of stochastic ordering (Theorem 2). It is interesting to note that age-optimality
here can be achieved even if the transmission time distribution differs from one link to another, i.e.,
the transmission time distributions are heterogeneous.
Finally, we investigate an important class of packet transmission time distributions called NewBetter-than-Used (NBU) distributions, which are more general than exponential. We generalize the
policy space (compared to that of the general transmission time case) such that it includes all causal
policies. The network topology we consider here is somewhat more restrictive in the sense that each
node has one incoming link only. We show that the non-preemptive LGFS policy is within a constant
age gap from the optimum average age, and that the gap is independent of the packet generation
and arrival times, network topology, and buffer sizes (Theorem 4).

To the best of our knowledge, these are the first optimal results on minimizing the age-of-information
in multihop networks for given generation and arrival times of the update packets.
The remainder of this paper is organized as follows. After a brief overview of related work in Section
II, we describe the model and problem formulation in Section III. The age-optimality results are presented
in Section IV, and near age-optimality results are developed in Section V. Finally, the conclusion is drawn
in Section VI.
II. R ELATED W ORK
There are a number of studies that have focused on the analysis of the age and figuring out ways to
reduce it in single-hop networks [5], [10], [11], [13]–[20], [23]. In [5], [10], the update frequency was
optimized to minimize the age in First-Come, First-Serve (FCFS) queueing systems when the service time
is exponentially distributed. It was found that this frequency differs from those that minimize the delay or
maximize the throughput. Extending the analysis to multi-class M/G/1 queue was considered in [19]. In
[11]–[13], it was shown that age can be improved by discarding old packets waiting in the queue when
a new sample arrives. Analyzing the age-of-information in the existence of the energy replenishment
constraints was considered in [14], [15]. In [16], the time-average age was characterized for Last-Come,
First-Serve (LCFS) information-update systems with and without preemption. Expanding the analysis
to multiple sources was considered in [17], where sharing service facility among Poisson sources was
found to improve the total age. The work in [20] analyzed the age in the presence of errors when the
service times are exponentially distributed. Gamma-distributed service times was considered in [18]. The
studies in [20], [18] were carried out for LCFS queueing systems with and without preemption. Wireless
scheduling for minimizing the age in single-hop networks was investigated in [23], where the minimum
age scheduling problem is shown to be NP-hard in general. Applications of the age-of-information in
channel state information (CSI) were considered in [24]–[26], where the age of CSI in wireless systems
was reduced for a single channel in [24], [25], and multiple channels in [26].
Age-optimal generation of update packets was studied for single-hop networks in [14], [15], [21],
[22]. A general class of non-negative, non-decreasing age penalty functions was minimized in [21], [22].
Later, a real-time sampling problem of the Wiener process was solved in [27]: If the sampling times
are independent of the observed Wiener process, the optimal sampling problem in [27] reduces to an

January 1, 2018

DRAFT

4

age-of-information optimization problem; otherwise, the optimal sampling policy can use knowledge of
the Wiener process to achieve better performance than age-of-information optimization.
Quite recently, it was shown in [6], [7] that for arbitrary packet generation times, arrival times, and
queue buffer size, a preemptive LGFS policy simultaneously optimizes the age, throughput, and delay
in multi-server single-hop networks with exponential service times. The study was extended to the class
of NBU packet service time distributions in [7], where it was shown that near age-optimality can be
achieved. In this study [7], packet replication technique was considered and an interesting result was
revealed: While it is known that replication worsens the delay and decreases the throughput for most
NBU service time distributions, surprisingly, it was found that replication can in fact reduce the age for
a variety of NBU service time distributions.
There exist a few studies on the age-of-information in multihop networks [28]–[30]. In [28], the authors
analyzed the age-of-information in multihop networks for specific topologies, but did not consider the
optimal age performance. In [29], an offline optimal scheduling policy was developed to minimize the age
in two-hop networks with an energy-harvesting source. In comparison to [28], [29], this paper optimizes
the age in multihop network with general age metric, arrival process, and network topologies. In addition,
in contrast to [29], this paper considers an online scheduling problem. The authors of [30] addressed the
problem of scheduling in wireless multihop networks with multiple flows, where all network queues are
served in FCFS manner. An age-based scheduling algorithm was developed to maintains the freshness
of the information at the receiver, and the performance of the proposed scheduler was characterized by
heavy-traffic analysis. Our simulations show that the LGFS scheduling policy considered in this paper
can achieve much better age performance than the FCFS scheduling policies analyzed in [30].
III. M ODEL

AND

F ORMULATION

A. Notations and Definitions
For any random variable Z and an event A, let [Z|A] denote a random variable with the conditional
distribution of Z for given A, and E[Z|A] denote the conditional expectation of Z for given A.
Let x = (x1 , x2 , . . . , xn ) and y = (y1 , y2 , . . . , yn ) be two vectors in Rn , then we denote x ≤ y if
xi ≤ yi for i = 1, 2, . . . , n. A set U ⊆ Rn is called upper if y ∈ U whenever y ≥ x and x ∈ U . We
will need the following definitions:
Definition III.1. Univariate Stochastic Ordering: [31] Let X and Y be two random variables. Then,
X is said to be stochastically smaller than Y (denoted as X ≤st Y ), if
P{X > x} ≤ P{Y > x},

∀x ∈ R.

Definition III.2. Multivariate Stochastic Ordering: [31] Let X and Y be two random vectors. Then,
X is said to be stochastically smaller than Y (denoted as X ≤st Y ), if
P{X ∈ U } ≤ P{Y ∈ U },

for all upper sets U ⊆ Rn .

Definition III.3. Stochastic Ordering of Stochastic Processes: [31] Let {X(t), t ∈ [0, ∞)} and
{Y (t), t ∈ [0, ∞)} be two stochastic processes. Then, {X(t), t ∈ [0, ∞)} is said to be stochastically

January 1, 2018

DRAFT

5

smaller than {Y (t), t ∈ [0, ∞)} (denoted by {X(t), t ∈ [0, ∞)} ≤st {Y (t), t ∈ [0, ∞)}), if, for all
choices of an integer n and t1 < t2 < . . . < tn in [0, ∞), it holds that
(X(t1 ), X(t2 ), . . . , X(tn )) ≤st (Y (t1 ), Y (t2 ), . . . , Y (tn )),

(1)

where the multivariate stochastic ordering in (1) was defined in Definition III.2.
B. Network Model
We consider a multihop network represented by a directed graph G(V, L) where V is the set of nodes
and L is the set of links, as shown in Fig. 1. The network topology is arbitrary and the number of nodes
in the network is |V| = N . The system starts to operate at time t = 0. A sequence of n update packets
are generated at an external source, where n can be an arbitrary finite or infinite integer. The generation
time of the l-th packet is sl , such that 0 ≤ s1 ≤ s2 ≤ . . . ≤ sn . The external source is connected to
the network through a gateway node 0. The update packets are firstly forwarded to node 0, from which
they are dispersed throughout the network. Let alj denote the arrival time of packet l to node j . Then,
sl ≤ al0 ≤ alj for all j = 1, . . . , N − 1. Note that the update packets may arrive at node 0 out of the
order of their generation times. For example, packet l + 1 may arrive at node 0 earlier than packet l such
that sl ≤ sl+1 but al0 ≥ a(l+1)0 . Define (i, j) ∈ L as a link from node i to node j , where i is the origin
node and j is the destination node. Once a packet arrives at node i, it is immediately available to all the
outgoing links from node i. Each link (i, j) has a queue of buffer size Bij to store the incoming packets.
If Bij is finite, the queue buffer may overflow and some packets are dropped. The packet transmission
time on each link (i, j) is random and the network is interference free.
C. Scheduling Policy
We let π denote a scheduling policy that determines when to send the packets on each link and in
which order. The packet generation times (s1 , s2 , . . . , sn ) and packet arrival times (a10 , a20 , . . . , an0 ) at
node 0 are arbitrary and do not change according to the scheduling policy, while the packet arrival times
at the other nodes are functions of the scheduling policy π . We assume that the packet transmission times
are invariant of the scheduling policy.
Let Π denote the set of all causal policies, in which scheduling decisions are made based on the history
and current state of the system. We define several types of policies in Π:
A policy is said to be preemptive, if a link can switch to send another packet at any time; the preempted
packets will be stored back into the queue if there is enough buffer space and then sent out at a later time
when the link is available again. In contrast, in a non-preemptive policy, a link must complete sending
the current packet before starting to send another packet. A policy is said to be work-conserving, if each
link is busy whenever there are packets waiting in the queue feeding this link.
D. Age Performance Metric
Let Uj (t) = max{sl : alj ≤ t} be the generation time of the freshest packet arrived at node j before
time t. The age-of-information, or simply the age, at node j is defined as
∆j (t) = t − Uj (t).

January 1, 2018

(2)

DRAFT

6

∆j (t)

s1

a1j

s2

a2j

t

Figure 2: A sample path of the age process ∆j (t) at node j .
The process of ∆j (t) is given by ∆j = {∆j (t), t ∈ [0, ∞)}. The initial state Uj (0− ) at time t = 0− is
invariant of the scheduling policy π ∈ Π, where we assume that Uj (0− ) = 0 = s0 for all j ∈ V . As
shown in Fig. 2, the age increases linearly with t but is reset to a smaller value with the arrival of a
fresher packet. The age vector of all the network nodes at time t is
∆(t) =(∆0 (t), ∆1 (t), . . . , ∆N −1 (t)).

(3)

The age process of all the network nodes is given by
∆ = {∆(t), t ∈ [0, ∞)}.

(4)

In this paper, we introduce a general age penalty functional g(∆) to represent the level of dissatisfaction
for data staleness at all the network nodes.
Definition III.4. Age Penalty Functional: Let V be the set of N -dimensional Lebesgue measurable
functions, i.e.,
V = {f : [0, ∞)N 7→ R such that f is Lebesgue measurable}.

A functional g : V 7→ R is said to be an age penalty functional if g is non-decreasing in the following
sense:
g(∆1 ) ≤ g(∆2 ), whenever ∆1 (t) ≤ ∆2 (t), ∀t ∈ [0, ∞).
(5)
The age penalty functionals used in prior studies include:
•

•

Time-average age [5], [10]–[18]: The time-average age of node j is defined as
Z
1 T
g1 (∆) =
∆j (t)dt,
T 0

(6)

Average peak age [11], [14], [18]–[20]: The average peak age of node j is defined as
g2 (∆) =

K
1 X
Akj ,
K

(7)

k=1

January 1, 2018

DRAFT

7

Algorithm 1: The preemptive Last-Generated, First-Serve (LGFS) policy.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

αij := 0;
// αij is the generation time of the packet being transmitted on the link (i, j)
while the system is ON do
if a new packet with generation time s arrives to node i then
if the link (i, j) is busy then
if s ≤ αij then
Store the packet in the queue;
else
// The packet carries fresher information than the packet being transmitted.
Send the packet over the link by preempting the packet being transmitted;
The preempted packet is stored back to the queue;
αij = s;
end
else
// The link is idle.
The new packet is sent over the link;
end
end
if a packet is delivered to node j then
if the queue is not empty then
The freshest packet in the queue is sent over the link;
end
end
end

•

•

where Akj denotes the k-th peak value of ∆j (t) since time t = 0.
Time-average age penalty function [21], [22]: The average age penalty function of node j is
Z
1 T
g3 (∆) =
h(∆j (t))dt,
T 0

(8)

where h : [0, ∞) → [0, ∞) can be any non-negative and non-decreasing function. As pointed out
in [22], a stair-shape function h(x) = ⌊x⌋ can be used to characterize the dissatisfaction of data
staleness when the information of interests is checked periodically, and an exponential function
h(x) = ex is appropriate for online learning and control applications where the desire for data
refreshing grows quickly with respect to the age.
Age penalty functional in single-hop networks [6], [7]: This is a special case of the age penalty
functional defined in Definition III.4 with N = 1.
IV. AGE - OPTIMALITY R ESULTS

In this section, we present our age-optimality results for multihop networks. We prove our results in
a stochastic ordering sense.
A. Exponential Transmission Time Distributions
We study the age-optimal packet scheduling when the packet transmission times are exponentially
distributed, independent across the links and i.i.d. across time. We consider a LGFS scheduling principle

January 1, 2018

DRAFT

8

in which the packet being transmitted at each link is generated the latest (i.e., the freshest) one among
all packets in the queue; after transmission, the link starts to send the next freshest packet in its queue.
We consider a preemptive LGFS (prmp-LGFS) policy at each link (i, j) ∈ L. The implementation details
of this policy are depicted in Algorithm 1.
Define a set of parameters I = {n, (sl , al0 )nl=1 , G(V, L), (Bij , (i, j) ∈ L)}, where n is the total number
of packets, sl is the generation time of packet l, al0 is the arrival time of packet l to node 0, G(V, L)
is the network graph, and Bij is the queue buffer size of link (i, j). Let ∆π be the age processes of
all nodes in the network under policy π . The age optimality of prmp-LGFS policy is provided in the
following theorem.
Theorem 1. If the packet transmission times are exponentially distributed, independent across links and
i.i.d. across time, then for all I and π ∈ Π
[∆prmp-LGFS |I] ≤st[∆π |I],

(9)

or equivalently, for all I and non-decreasing functional g
E[g(∆prmp-LGFS )|I] = min E[g(∆π )|I],
π∈Π

(10)

provided the expectations in (10) exist.
Proof. See Appendix A.
Theorem 1 tells us that for arbitrary number n, packet generation times (s1 , s2 , . . . , sn ) and arrival
times (a10 , a20 , . . . , an0 ) at node 0, network topology G(V, L), and buffer sizes (Bij , (i, j) ∈ L), the
prmp-LGFS policy achieves optimality of the joint distribution of the age processes at the network
nodes within the policy space Π. In addition, (10) tells us that the prmp-LGFS policy minimizes any
non-decreasing age penalty functional g, including the time-average age (6), average peak age (7), and
average age penalty (8).
B. General Transmission Time Distributions
Now, we study the age-optimal packet scheduling for arbitrary general packet transmission time
distributions which are independent across the links and i.i.d. across time. We consider the set of nonpreemptive work-conserving policies, denoted by Πnpwc ⊂ Π. We propose a non-preemptive LGFS (nonprmp-LGFS) policy. It is important to note that under non-prmp-LGFS policy, the fresh packet replaces
the oldest packet in a link’s queue when the queue has a finite buffer size and full. The description of
non-preemptive LGFS policy can be obtained from Algorithm 1 by replacing Steps 5-11 by Step 6. We
next show that the non-preemptive LGFS policy is age-optimal among the policies in Πnpwc.
Theorem 2. If the packet transmission times are independent across the links and i.i.d. across time, then
for all I and π ∈ Πnpwc
[∆non-prmp-LGFS |I]≤st[∆π |I],

January 1, 2018

(11)

DRAFT

9

/

.
!"#$%&'()*+,%-$

1

2'#$3'4

0

Figure 3: A multihop network.

or equivalently, for all I and non-decreasing functional g
E[g(∆non-prmp-LGFS )|I] =

min E[g(∆π )|I],

π∈Πnpwc

(12)

provided the expectations in (12) exist.
Proof. The proof of Theorem 2 is similar to that of Theorem 1. The difference is that preemption is not
allowed here. See Appendix B for more details.
It is interesting to note from Theorem 2 that, age-optimality can be achieved for arbitrary transmission
time distributions, even if the transmission time distribution differs from a link to another.
C. Simulation Results
We present some numerical results to illustrate the age performance of different policies and validate
the theoretical results. We consider the network in Fig. 3. The inter-generation times are i.i.d. Erlang-2
distribution with mean 1/λ. The time difference between packet generation and arrival to node 0, i.e.,
ai0 − si , is modeled to be either 1 or 100, with equal probability. This means that the update packets
may arrive to node 0 out of order of their generation time.
Figure 4 illustrates the average peak age at node 2 versus the packet generation rate λ for the multihop
network in Fig. 3. The packet transmission times are exponentially distributed with mean 1 at links (0, 1)
and (1, 2), and mean 0.5 at link (0, 2). One can observe that the preemptive LGFS policy achieves a
better (smaller) peak age at node 2 than the non-preemptive LGFS policy, non-preemptive LCFS policy,
and FCFS policy, where the buffer sizes are either 1 or infinity. It is important to emphasize that the peak
age is minimized by preemptive LGFS policy for out of order packet receptions at node 0, and general
network topology. This numerical result shows agreement with Theorem 1.
Figure 5 plots the time-average age at node 3 versus the packets generation rate λ for the multihop
network in Fig. 3. The plotted policies are FCFS policy, non-preemptive LCFS, and non-preemptive
LGFS policy, where the buffer sizes are either 1 or infinity. The packet transmission times at links
(0, 1) and (1, 3) follow a gamma distribution with mean 1. The packet transmission times at links (0, 2),
(1, 2), and (2, 3) are distributed as the sum of a constant with value 0.5 and a value drawn from an
exponential distribution with mean 0.5. We find that the non-preemptive LGFS policy achieves the best
age performance among all plotted policies. By comparing the age performance of the non-preemptive
LGFS and non-preemptive LCFS policies, we observe that the LGFS scheduling principle improves the

January 1, 2018

DRAFT

10

14
FCFS, Bij =∞
Non-prmp-LCFS, B ij =1

12
Average Peak Age

Non-prmp-LGFS, B ij =1
Prmp-LGFS, any B ij ≥ 0

10

8

6

4
0.2

0.4

0.6
0.8
1
1.2
Packet Generation Rate λ

1.4

1.6

Figure 4: Average peak age at node 2 versus packets generation rate λ for exponential packet
transmission times.
9
FCFS, Bij =∞
FCFS, Bij =1

Average Age

8

Non-prmp-LCFS, B ij =1
Non-prmp-LGFS, B ij =1

7

6

5

4

0.4

0.6

0.8
1
1.2
Packet Generation Rate λ

1.4

1.6

Figure 5: Average age at node 3 versus packets generation rate λ for general packet transmission time
distributions.

age performance when the update packets arrive to node 0 out of the order of their generation times. It
is important to note that the non-preemptive LGFS policy minimizes the age among the non-preemptive
work-conserving policies even if the packet transmission time distributions are heterogeneous across the
links. We also observe that the average age of FCFS policy with Bij = ∞ blows up when the traffic
intensity is high. This is due to the increased congestion in the network which leads to a delivery of
stale packets. Moreover, in case of the FCFS policy with Bij = 1, the average age is finite at high

January 1, 2018

DRAFT

11

/

0

1

3

2

.
!"#$%&'()*+,%-$

5'#$6'7

4

8

//

/.

9

:

Figure 6: Information updates over a multihop network, where each node in the network (except the
gateway) is restricted to receive data from only one node.

traffic intensity, since the fresh packet has a better opportunity to be delivered in a relatively short period
compared with FCFS policy with Bij = ∞. This numerical result agrees with Theorem 2.
V. N EAR AGE - OPTIMALITY R ESULTS
While the policy space being considered in Theorem 1 (for exponential transmission distributions)
is very general, the policy space considered in Theorem 2 (for general transmission distributions) is
restricted to only non-preemptive work-conserving policies. The next question we answer is whether for
an important class of distributions that are more general than exponential, optimality or near-optimality
can be achieved without restricting to the class of non-preemptive work-conserving policies. We propose a
non-preemptive LGFS policy and show that it is within a small age gap of the optimum average age among
all policies in Π. However, we are able to prove this result for a somewhat more restrictive network than
the general topology G(V, L). The network here is represented by a directed graph G ′ (V, L), in which
each node j ∈ V\{0} is allowed to receive data from only one node (the total number of incoming
links to each node j ∈ V\{0} is at most one), as shown in Fig. 6. The packet transmission times are
assumed to be i.i.d. across time and links. We consider the classes of New-Better-than-Used (NBU)
packet transmission time distributions, which are defined as follows.
Definition V.1. New-Better-than-Used distributions: Consider a non-negative random variable X with
complementary cumulative distribution function (CCDF) F̄ (x) = P[X > x]. Then, X is New-Betterthan-Used (NBU) if for all t, τ ≥ 0
F̄ (τ + t) ≤ F̄ (τ )F̄ (t).

(13)

Examples of NBU distributions include constant transmission time, (shifted) exponential distribution,
geometrical distribution, Erlang distribution, negative binomial distribution, etc.
Define a set of the parameters I ′ = {n, (sl , al0 )nl=1 , G ′ (V, L), (Bij , (i, j) ∈ L)}, where n is the total
number of packets, sl is the generation time of packet l, al0 is the arrival time of packet l to node 0,
G ′ (V, L) is the network graph with the new restriction, and Bij is the queue buffer size of the link (i, j).
Define Hk as the set of nodes in the k-th hop, i.e., Hk is the set of nodes that are separated by k links

January 1, 2018

DRAFT

12

#

"

!

(a) Two-hop tandem network.

1

Link (0, 1) a
10

2
1
2
2
a20 t1 = v
21 t1
1
2

1
Link (1, 2)

Node 2

1
a11

2
a21 t12 = v22 t22

1

2

a12

a22

(b) A sample path of the packet arrival processes.

Figure 7: An illustration of the infeasible policy in a Two-hop network.

from node 0 1 . Let vlj (π) denote the transmission starting time of packet l over the incoming link to
node j under policy π . To show that policy non-prmp-LGFS can come close to age-optimal, we need
to construct an age lower bound. We will construct an infeasible policy which provides the age lower
bound as follows:
•

1

The infeasible policy (IP ): The infeasible policy is constructed as follows. At each link (i, j), the
packets are served by following a work-conserving LGFS principle. A packet l is deemed delivered
from node i to node j once the transmission of packet l starts over the link (i, j) (this step is
infeasible). After the transmission of packet l starts over the link (i, j), the link (i, j) will be busy
for a time duration equal to the actual transmission time of packet l over the link (i, j). Hence, the
next packet cannot start its transmission over the link (i, j) until the end of this time duration. We
use vlj (IP ) to denote the transmission starting time of packet l over the incoming link to node j
under the infeasible policy (IP ) constructed above.

Node 0 is always considered to be in H0 .

January 1, 2018

DRAFT

13

•

One example of the infeasible policy IP is illustrated in Fig. 7. We use tlj to denote the time by
which the incoming link to node j becomes idle again after the transmission of packet l starts. Since
all links are idle at the beginning, packet 1 arrives to all nodes once it arrives to node 0 at time
a10 (this is because each packet is deemed delivered to the next node once its transmission starts).
However, each link is kept busy for a time duration equal to the actual transmission time of packet 1
over each link. Then, packet 2 arrives to node 0 at time a20 and finds the link (0, 1) busy. Therefore,
packet 2 cannot start its transmission until link (0, 1) becomes idle again at time t11 (v21 (IP ) = t11 ).
Once packet 2 starts its transmission at time t11 over the link (0, 1), it is deemed delivered to node
1 (a21 (IP ) = v21 (IP ) = t11 ) and link (0, 1) is kept busy until time t21 . At time t11 , link (1, 2) is
busy. Thus, packet 2 cannot start its transmission over the link (1, 2) until it becomes idle again at
time t12 . Once packet 2 starts its transmission over the link (1, 2) at time t12 , it is deemed delivered
to node 2 (a22 (IP ) = v22 (IP ) = t12 ).
The age lower bound: The age lower bound is constructed as follows. For each node j ∈ V , define
a function ∆LB
j,IP (t) as
∆LB
(14)
j,IP (t) = t − max{sl : vlj (IP ) ≤ t}.
The definition of the ∆LB
j,IP (t) is similar to that of the age in (2) except that the packets arrival times
to node j are replaced by their transmission starting times over the incoming link to node j in the
infeasible policy. In this case, ∆LB
j,IP (t) increases linearly with t but is reset to a smaller value with
the transmission start of a fresher packet over the incoming link to node j , as shown in Fig. 8. The
LB
LB
process of ∆LB
j,IP (t) is given by ∆j,IP = {∆j,IP (t), t ∈ [0, ∞)} for each j ∈ V . The age lower
bound vector of all the network nodes is
LB
LB
LB
∆LB
IP (t) =(∆0,IP (t), ∆1,IP (t), . . . , ∆N −1,IP (t)).

(15)

The age lower bound process of all the network nodes is given by
LB
∆LB
IP = {∆IP (t), t ∈ [0, ∞)}.

(16)

The next Lemma tells us that the process ∆LB
IP is an age lower bound of all policies in Π in the
following sense.
Lemma 3. Suppose that the packet transmission times are NBU and i.i.d. across time and links, then for
all I ′ satisfying Bij ≥ 1 for each (i, j) ∈ L, and π ∈ Π
′
′
[∆LB
IP |I ] ≤st [∆π |I ].

(17)

Proof. See Appendix C.
We can now proceed to characterize the age performance of policy non-prmp-LGFS among policies
in Π. Let Xij denote the packet transmission time over the link (i, j), with mean E[Xij ] = E[X] < ∞
for all (i, j) ∈ L. We use Lemma 3 to prove the following theorem.

January 1, 2018

DRAFT

14

∆(t)

∆LB
j,IP (t) ∆j,π (t)

t

s1 v1 s2 c1 v2 c2
Figure 8: The evolution of ∆LB
j,IP (t) and ∆j,π (t) at node j ∈ H1 .
Theorem 4. Suppose that the packet transmission times are NBU and i.i.d. across time and links, then
for all I ′ satisfying Bij ≥ 1 for each (i, j) ∈ L
¯ j,π |I ′ ] ≤ [∆
¯ j,non-prmp-LGFS |I ′ ] ≤ min[∆
¯ j,π |I ′ ] + (2k − 1)E[X], ∀j ∈ Hk , ∀k ≥ 1,
min[∆
π∈Π

¯ j,π = lim supT →∞
where ∆

π∈Π

E[

RT
0

∆j,π (t)dt]
T

(18)

is the average age at node j under policy π .

Proof. See Appendix E.
Theorem 4 tells us that for arbitrary number n, packet generation times (s1 , s2 , . . . , sn ) and arrival
times (a10 , a20 , . . . , an0 ) at node 0, and buffer sizes (Bij ≥ 1, (i, j) ∈ L), the non-prmp-LGFS policy is
within a constant age gap from the optimum average age among all policies in Π.
A. Simulation Results
We now provide a simulation result to illustrate the age performance of different policies when the
transmission times are NBU. We consider the network in Fig. 6. Figure 9 illustrates the average age
at node 5 under gamma transmission time distributions at each link with different shape parameter β ,
where the buffer sizes are either 1, 10, or 100. The mean of the gamma transmission time distributions
at each link are normalized to 0.2. The inter-generation times are i.i.d. Erlang-2 distribution with mean
1/λ = 1/30. The time difference (ai0 − si ) between packet generation and arrival to node 0 is Zero.
Note that the average age of the FCFS policy with infinite buffer sizes is extremely high in this
R T case
∆LB
and hence is not plotted in this figure. The “Age lower bound” curve is generated by using 0 T 5,IP
when the buffer sizes are 1 which, according to Lemma 3, is a lower bound of the optimum average
age at node 5. We can observe that the gap between the “Age lower bound” curve and the average age
of the non-prmp-LGFS policy at node 5 is no larger than 9E[X] = 1.8, which agrees with Theorem
4. In addition, we can observe that prmp-LGFS policy achieves the best age performance among all
plotted policies when β = 1. This is because a gamma distribution with shape parameter β = 1 is
an exponential distribution. Thus, age-optimality can be achieved in this case by policy prmp-LGFS as
stated in Theorem 1. However, as can be seen in the figure, the average age at node 5 of the prmp-LGFS

January 1, 2018

DRAFT

15

45
40

Average Age

35
30

FCFS, Bij =100

25

prmp-LGFS, any B ij

20
15
10

0

1.5
1
0.5
16

FCFS, Bij =10
FCFS, Bij =1
Non-prmp-LGFS, B ij =1
Age lower bound, B ij =1

18

20

5
0
5

10

15

20

Figure 9: Average age at node 5 under gamma transmission time distributions at each link with
different shape parameter β .

policy blows up as the shape parameter β increases and the non-prmp-LGFS policy achieves the best age
performance among all plotted policies when β > 2. The reason for this phenomenon is as follows: As β
increases, the variance (variability) of normalized gamma distribution decreases. Hence, when a packet
is preempted, the service time of a new packet is probably longer than the remaining service time of
the preempted packet. Because the generation rate is high, packet preemption happens frequently, which
leads to infrequent packet delivery and increase the age. This phenomenon occurs heavily at the first link
(link (0, 1)) which, in turn, affects the age at the subsequent nodes.
VI. C ONCLUSION
In this paper, we made the first attempt to minimize the age-of-information in multihop interference free
networks. We considered general system settings including arbitrary network topology, packet generation
and arrival times to node 0, and queue buffer sizes. A number of scheduling policies are developed
and are proven to be age-optimal in stochastic ordering sense for (i) exponential transmission times
and general policy space, (ii) general transmission times and restrictive policy space (non-preemptive
work-conserving policies). These optimality results not only hold for the age processes, but also for
any non-decreasing functional of the age processes. Finally, we investigated the class of NBU packet
transmission time distributions in a somewhat more restrictive network topology and showed that the
non-preemptive LGFS policy is near age-optimal.
R EFERENCES
[1] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Age-optimal information updates in multihop networks,” in Proc. IEEE ISIT,
June 2017, pp. 576–580.
[2] B. Adelberg, H. Garcia-Molina, and B. Kao, “Applying update streams in a soft real-time database system,” in ACM
SIGMOD Record, 1995, vol. 24, pp. 245–256.

January 1, 2018

DRAFT

16

[3] J. Cho and H. Garcia-Molina, “Synchronizing a database to improve freshness,” in ACM SIGMOD Record, 2000, vol. 29,
pp. 117–128.
[4] L. Golab, T. Johnson, and V. Shkapenyuk, “Scheduling updates in a real-time stream warehouse,” in Proc. IEEE 25th
Int’l Conf. Data Eng. (ICDE), March 2009, pp. 1207–1210.
[5] S. Kaul, R. D. Yates, and M. Gruteser, “Real-time status: How often should one update?,” in Proc. IEEE INFOCOM,
2012, pp. 2731–2735.
[6] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Optimizing data freshness, throughput, and delay in multi-server informationupdate systems,” in Proc. IEEE ISIT, July 2016, pp. 2569–2573.
[7] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Minimizing the age of the information through queues,” submitted to IEEE
Trans. Inf. Theory, 2017, https://arxiv.org/abs/1709.04956.
[8] G. R. Gupta and N. B. Shroff, “Delay analysis and optimality of scheduling policies for multihop wireless networks,”
IEEE/ACM Trans. Netw., vol. 19, no. 1, pp. 129–141, 2011.
[9] L. Tassiulas and A. Ephremides, “Dynamic scheduling for minimum delay in tandem and parallel constrained queueing
models,” Ann. Oper. Res., vol. 48, no. 4, pp. 333–355, 1994.
[10] R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in Proc. IEEE ISIT, July 2012, pp. 2666–2670.
[11] M. Costa, M. Codreanu, and A. Ephremides, “Age of information with packet management,” in Proc. IEEE ISIT, June
2014, pp. 1583–1587.
[12] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,”
IEEE Trans. Inf. Theory, vol. 62, no. 4, pp. 1897–1910, April 2016.
[13] N. Pappas, J. Gunnarsson, L. Kratz, M. Kountouris, and V. Angelakis, “Age of information of multiple sources with queue
management,” in Proc. IEEE ICC, June 2015, pp. 5935–5940.
[14] B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, “Age of information under energy replenishment constraints,” in
Proc. ITA, Feb. 2015.
[15] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in Proc. IEEE ISIT, 2015.
[16] S. K. Kaul, R. D. Yates, and M. Gruteser, “Status updates through queues,” in 2012 46th Annu. Conf. Inf. Sci. Syst.,
March 2012, pp. 1–6.
[17] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” submitted to IEEE
Trans. Inf. Theory, 2016, https://arxiv.org/abs/1608.08622.
[18] E. Najm and R. Nasser, “Age of information: The gamma awakening,” in Proc. IEEE ISIT, July 2016, pp. 2574–2578.
[19] L. Huang and E. Modiano, “Optimizing age-of-information in a multi-class queueing system,” in Proc. IEEE ISIT, June
2015, pp. 1681–1685.
[20] K. Chen and L. Huang, “Age-of-information in the presence of error,” in Proc. IEEE ISIT, July 2016, pp. 2579–2583.
[21] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,”
in Proc. IEEE INFOCOM, April 2016.
[22] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,”
IEEE Trans. Inf. Theory, vol. 63, no. 11, pp. 7492–7508, Nov 2017.
[23] Q. He, D. Yuan, and A. Ephremides, “Optimal link scheduling for age minimization in wireless systems,” IEEE Trans. Inf.
Theory, vol. PP, no. 99, pp. 1–1, 2017.
[24] M. Costa, S. Valentin, and A. Ephremides, “On the age of channel information for a finite-state markov model,” in Proc.
IEEE ICC, June 2015, pp. 4101–4106.
[25] M. Costa, S. Valentin, and A. Ephremides, “On the age of channel state information for non-reciprocal wireless links,” in
Proc. IEEE ISIT, June 2015, pp. 2356–2360.
[26] A. G. Klein, S. Farazi, W. He, and D. R. Brown, “Staleness bounds and efficient protocols for dissemination of global
channel state information,” IEEE Transactions on Wireless Communications, vol. 16, no. 9, pp. 5732–5746, Sept 2017.
[27] Y. Sun, Y. Polyanskiy, and E. Uysal-Biyikoglu, “Remote estimation of the Wiener process over a channel with random
delay,” in Proc. IEEE ISIT, 2017.
[28] J. Selen, Y. Nazarathy, L. LH Andrew, and H. L. Vu, “The age of information in gossip networks,” in International
Conference on Analytical and Stochastic Modeling Techniques and Applications. Springer, 2013, pp. 364–379.
[29] A. Araf and S. Ulukus, “Age-minimal transmission in energy harvesting two-hop networks,” CoRR, abs/1704.08679, Apr
2017.

January 1, 2018

DRAFT

17

[30] C. Joo and A. Eryilmaz, “Wireless scheduling for information freshness and synchrony: Drift-based design and heavytraffic analysis,” in 2017 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless
Networks (WiOpt), May 2017, pp. 1–8.
[31] M. Shaked and J. G. Shanthikumar, Stochastic orders, Springer Science & Business Media, 2007.
[32] Y. Sun, C. E. Koksal, and N. B. Shroff, “On delay-optimal scheduling in queueing systems with replications,”
CoRR, abs/1603.07322, Jan. 2016.

A PPENDIX A
P ROOF OF T HEOREM 1
Let us define the system state of a policy π :
Definition A.1. At any time t, the system state of policy π is specified by Uπ (t) = (U0,π (t), U2,π (t),
. . . , UN −1,π (t)), where Uj,π (t) is the generation time of the freshest packet that arrived at node j by time
t. Let {Uπ (t), t ∈ [0, ∞)} be the state process of policy π , which is assumed to be right-continuous. For
notational simplicity, let policy P represent the preemptive LGFS policy.
The key step in the proof of Theorem 1 is the following lemma, where we compare policy P with
any work-conserving policy π .
Lemma 5. Suppose that UP (0− ) = Uπ (0− ) for all work conserving policies π , then for all I ,
[{UP (t), t ∈ [0, ∞)}|I] ≥st [{Uπ (t), t ∈ [0, ∞)}|I].

(19)

We use coupling and forward induction to prove Lemma 5. For any work-conserving policy π ,
e P (t) and U
e π (t) have the same distributions with UP (t) and Uπ (t),
suppose that stochastic processes U
e P (t) and U
e π (t) are coupled in the following manner: If a packet
respectively. The state processes U
e P (t) evolves in policy P , then there exists a packet
is delivered from node i to node j at time t as U
e π (t) evolves in policy π . Such a coupling is valid since
delivery from node i to node j at time t as U
the transmission time is exponentially distributed and thus memoryless. Moreover, policy P and policy
π have identical packet generation times (s1 , s2 , . . . , sn ) at the external source and packet arrival times
(a10 , a20 , . . . , an0 ) to node 0. According to Theorem 6.B.30 in [31], if we can show
e P (t) ≥ U
e π (t), t ∈ [0, ∞)|I] = 1,
P[U

(20)

then (19) is proven.
To ease the notational burden, we will omit the tildes in this proof on the coupled versions and just
use UP (t) and Uπ (t). Next, we use the following lemmas to prove (20):
Lemma 6. Suppose that under policy P , U′ P is obtained by a packet delivery over the link (i, j) in the
system whose state is UP . Further, suppose that under policy π , U′ π is obtained by a packet delivery
over the link (i, j) in the system whose state is Uπ . If
UP ≥ Uπ ,

(21)

U′ P ≥ U′ π .

(22)

then,

January 1, 2018

DRAFT

18

Proof. Let sP and sπ denote the generation times of the packets that are delivered over the link (i, j)
under policy P and policy π , respectively. From the definition of the system state, we can deduce that
′
Uj,P
= max{Uj,P , sP },

(23)

′
Uj,π
= max{Uj,π , sπ }.

Hence, we have two cases:
Case 1: If sP ≥ sπ . From (21), we have
Uj,P ≥ Uj,π .

(24)

Also, sP ≥ sπ , together with (23) and (24) imply
′
′
Uj,P
≥ Uj,π
.

(25)

Since there is no packet delivery under other links, we get
′
′
,
= Uk,P ≥ Uk,π = Uk,π
Uk,P

∀k 6= j.

(26)

Hence, we have
U′ P ≥ U′ π .

(27)

Case 2: If sP < sπ . By the definition of the system state, sP ≤ Ui,P and sπ ≤ Ui,π . Then, using
Ui,P ≥ Ui,π , we obtain
sP < sπ ≤ Ui,π ≤ Ui,P .
(28)
Because sP < Ui,P , policy P is sending a stale packet on link (i, j). By the definition of policy P , this
happens only when all packets generated after sP in the queue of the link (i, j) have been delivered to
node j . Since sπ ≤ Ui,P , node i has already received a packet (say packet w) generated no earlier than
sπ in policy P . Because sP < sπ , packet w is generated after sP . Hence, packet w must have been
delivered to node j in policy P such that
sπ ≤ Uj,P .
(29)
Also, from (21), we have
Uj,π ≤ Uj,P .

(30)

Combining (29) and (30) with (23), we obtain
′
′
Uj,P
≥ Uj,π
.

(31)

Since there is no packet delivery under other links, we get
′
′
,
= Uk,P ≥ Uk,π = Uk,π
Uk,P

∀k 6= j.

(32)

Hence, we have
U′ P ≥ U′ π ,

(33)

which complete the proof.

January 1, 2018

DRAFT

19

Lemma 7. Suppose that under policy P , U′ P is obtained by the arrival of a new packet to node 0 in
the system whose state is UP . Further, suppose that under policy π , U′ π is obtained by the arrival of a
new packet to node 0 in the system whose state is Uπ . If
UP ≥ Uπ ,

(34)

U′ P ≥ U′ π .

(35)

then,

Proof. Let s denote the generation time of the new arrived packet. From the definition of the system
state, we can deduce that
′
U0,P
= max{U0,P , s},

(36)

′
U0,π
= max{U0,π , s}.

Combining this with (34), we obtain
′
′
U0,P
≥ U0,π
.

(37)

Since there is no packet delivery under other links, we get
′
′
,
= Uk,P ≥ Uk,π = Uk,π
Uk,P

∀k 6= 0.

(38)

Hence, we have
U′ P ≥ U′ π ,

(39)

which complete the proof.
Proof of Lemma 5. For any sample path, we have that UP (0− ) = Uπ (0− ). This, together with Lemma
6 and Lemma 7, implies that
[UP (t)|I] ≥ [Uπ (t)|I],

holds for all t ∈ [0, ∞). Hence, (20) holds which implies (19) by Theorem 6.B.30 in [31]. This completes
the proof.
Proof of Theorem 1. According to Lemma 5, we have
[{UP (t), t ∈ [0, ∞)}|I] ≥st [{Uπ (t), t ∈ [0, ∞)}|I],

holds for all work-conserving policies π , which implies
[{∆P (t), t ∈ [0, ∞)}|I]≤st[{∆π (t), t ∈ [0, ∞)}|I],

holds for all work-conserving policies π .
Finally, transmission idling only postpones the delivery of fresh packets. Therefore, the age under

January 1, 2018

DRAFT

20

non-work-conserving policies will be greater. As a result,
[{∆P (t), t ∈ [0, ∞)}|I]≤st[{∆π (t), t ∈ [0, ∞)}|I],

holds for all π ∈ Π. This completes the proof.
A PPENDIX B
P ROOF OF T HEOREM 2
This proof is similar to that of Theorem 1. The difference between this proof and the proof of Theorem
1 is that policy π cannot be a preemptive policy here. We will use the same definition of the system
state of policy π used in Theorem 1. For notational simplicity, let policy P represent the non-preemptive
LGFS policy.
The key step in the proof of Theorem 2 is the following lemma, where we compare policy P with an
arbitrary policy π ∈ Πnpwc .
Lemma 8. Suppose that UP (0− ) = Uπ (0− ) for all π ∈ Πnpwc , then for all I ,
[{UP (t), t ∈ [0, ∞)}|I] ≥st [{Uπ (t), t ∈ [0, ∞)}|I].

(40)

We use coupling and forward induction to prove Lemma 8. For any work-conserving policy π ,
e P (t) and U
e π (t) have the same distributions with UP (t) and Uπ (t),
suppose that stochastic processes U
e P (t) and U
e π (t) are coupled in the following manner: If a packet is
respectively. The state processes U
e P (t) evolves in policy prmp-LGFS, then there exists a
delivered from node i to node j at time t as U
e π (t) evolves in policy π . Such a coupling is valid
packet delivery from node i to node j at time t as U
since the transmission time distribution at each link is identical under all policies. Moreover, policy π
can not be either preemptive or non-work-conserving policy, and both policies have the same packets
generation times (s1 , s2 , . . . , sn ) at the exterenal source and packet arrival times (a10 , a20 , . . . , an0 ) to
node 0. According to Theorem 6.B.30 in [31], if we can show
e P (t) ≥ U
e π (t), t ∈ [0, ∞)|I] = 1,
P[U

(41)

then (40) is proven.
To ease the notational burden, we will omit the tildes henceforth on the coupled versions and just use
UP (t) and Uπ (t).
Next, we use the following lemmas to prove (41):
Lemma 9. Suppose that under policy P , UP (ν) is obtained by a packet delivery over the link (i, j) at
time ν in the system whose state is UP (ν − ). Further, suppose that under policy π , Uπ (ν) is obtained
by a packet delivery over the link (i, j) at time ν in the system whose state is Uπ (ν − ). If
UP (t) ≥ Uπ (t),

(42)

UP (ν) ≥ Uπ (ν).

(43)

holds for all t ∈ [0, ν − ], then

January 1, 2018

DRAFT

21

Proof. Let sP and sπ denote the packet indexes and the generation times of the delivered packets over
the link (i, j) at time ν under policy P and policy π , respectively. From the definition of the system
state, we can deduce that
Uj,P (ν) = max{Uj,P (ν − ), sP },

(44)

Uj,π (ν) = max{Uj,π (ν − ), sπ }.

Hence, we have two cases:
Case 1: If sP ≥ sπ . From (42), we have
Uj,P (ν − ) ≥ Uj,π (ν − ).

(45)

Uj,P (ν) ≥ Uj,π (ν).

(46)

By sP ≥ sπ , (44), and (45), we have

Since there is no packet delivery under other links, we get
Uk,P (ν) = Uk,P (ν − ) ≥ Uk,π (ν − ) = Uk,π (ν),

∀k 6= j.

(47)

Hence, we have
UP (ν) ≥ Uπ (ν).

(48)

Case 2: If sP < sπ . Let aπ represent the arrival time of packet sπ to node i under policy π . The
transmission starting time of the delivered packets over the link (i, j) is denoted by τ under both policies.
Apparently, aπ ≤ τ ≤ ν − . Since packet sπ arrived to node i at time aπ in policy π , we get
sπ ≤ Ui,π (aπ ).

(49)

Ui,π (aπ ) ≤ Ui,P (aπ ).

(50)

sπ ≤ Ui,P (aπ ).

(51)

From (42), we obtain

Combining (49) and (50), yields

Hence, in policy P , node i has a packet with generation time no smaller than sπ by the time aπ . Because
the Ui,P (t) is a non-decreasing function of t and aπ ≤ τ , we have
Ui,P (aπ ) ≤ Ui,P (τ ).

(52)

sπ ≤ Ui,P (τ ).

(53)

sP < Ui,P (τ ),

(54)

Then, (51) and (52) imply

Since sP < sπ , (53) tells us

and hence policy P is sending a stale packet on link (i, j). By the definition of policy P , this happens
only when all packets generated after sP in the queue of the link (i, j) have been delivered to node j

January 1, 2018

DRAFT

22

by time τ . In addition, (53) tells us that by time τ , node i has already received a packet (say packet h)
generated no earlier than sπ in policy P . By sP < sπ , packet h is generated after sP . Hence, packet h
must have been delivered to node j by time τ in policy P such that
sπ ≤ Uj,P (τ ).

(55)

Because the Uj,P (t) is a non-decreasing function of t, and τ ≤ ν − , (55) implies
sπ ≤ Uj,P (ν − ).

(56)

Uj,π (ν − ) ≤ Uj,P (ν − ).

(57)

Also, from (42), we have

Combining (56) and (57) with (44), we obtain
Uj,P (ν) ≥ Uj,π (ν).

(58)

Since there is no packet delivery under other links, we get
Uk,P (ν) = Uk,P (ν − ) ≥ Uk,π (ν − ) = Uk,π (ν),

∀k 6= j.

(59)

Hence, we have
UP (ν) ≥ Uπ (ν),

(60)

which complete the proof.
Lemma 10. Suppose that under policy P , U′ P is obtained by the arrival of a new packet to node 0 in
the system whose state is UP . Further, suppose that under policy π , U′ π is obtained by the arrival of a
new packet to node 0 in the system whose state is Uπ . If
UP ≥ Uπ ,

(61)

U′ P ≥ U′ π .

(62)

then,

Proof. The proof of Lemma 10 is similar to that of Lemma 7, and hence is not provided.
Proof of Lemma 8. For any sample path, we have that UP (0− ) = Uπ (0− ). This, together with Lemma
9 and Lemma 10, implies that
[UP (t)|I] ≥ [Uπ (t)|I],

holds for all t ∈ [0, ∞). Hence, (41) holds which implies (40) by Theorem 6.B.30 in [31]. This completes
the proof.
Proof of Theorem 2. According to Lemma 8, we have
[{UP (t), t ∈ [0, ∞)}|I] ≥st [{Uπ (t), t ∈ [0, ∞)}|I],

January 1, 2018

DRAFT

23

The incoming
link to node j

time

l

q
Γlj = vqj

Dlj = aqj vlj

alj

Figure 10: An illustration of vlj , alj , Γlj and Dlj . We consider the incoming link to node j, and sq > sl . The
transmission starting time over this link and the arrival time to node j of packet q are earlier than those of packet
l. Thus, we have Γlj = vqj and Dlj = aqj .

holds for all π ∈ Πnpwc, which implies
[{∆P (t), t ∈ [0, ∞)}|I]≤st[{∆π (t), t ∈ [0, ∞)}|I],

holds for all π ∈ Πnpwc. This completes the proof.
A PPENDIX C
P ROOF OF L EMMA 3
For notation simplicity, let policy P represent the non-prmp-LGFS policy and IP represent the
infeasible policy. We need to define the following parameters: Recall that vlj denotes the transmission
starting time of packet l over the incoming link to node j and alj denotes the arrival time of packet l to
node j . We define Γlj and Dlj as
Γlj = min{vqj },

(63)

Dlj = min{aqj },

(64)

q≥l

q≥l

where Γlj and Dlj are the smallest transmission starting time over the incoming link to node j and
arrival time to node j , respectively, of all packets that are fresher than the packet l. An illustration of these
parameters is provided in Fig. 10. Define the vectors Γj = (Γ1j , . . . , Γnj ), and Dj = (D1j , . . . , Dnj ). All
these quantities are functions of the scheduling policy π (except the packet arrival times (a10 , a20 , . . . , an0 )
to node 0 which are invariant of the scheduling policy).
To prove (17), we need to show that
[Γ1 (IP ), . . . , ΓN −1 (IP )|I ′ ] ≤st [D1 (π), . . . , DN −1 (π)|I ′ ],

(65)

holds for all π ∈ Π. To prove (65), we need the following lemma.
Lemma 11. For any link (i, j) ∈ L and policy π ∈ Π, if (i) the packet transmission times are NBU, and
(ii) Γi (IP ) ≤ Di (π), then
[Γj (IP )|I ′ ] ≤st [Dj (π)|I ′ ],
(66)
holds for all I ′ satisfying Bij ≥ 1.

January 1, 2018

DRAFT

24

Proof. See Appendix D
Proof of (65). Pick any policy π ∈ Π. We use mkj to represent the index of the j -th node in Hk 2 . We
prove (17) using Theorem 6.B.3 of [31] into two steps
Step 1: Consider node m11 . Since the packet arrival times (a10 , . . . , an0 ) to node 0 are invariant of the
scheduling policy, both conditions of Lemma 11 are satisfied and we can apply it on the link (0, m11 ) to
obtain
[Γm11 (IP )|I ′ ] ≤st [Dm11 (π)|I ′ ].
(67)
Step 2: Consider a node mK
J , where J ≥ 2 if K = 1 and J ≥ 1 if K ≥ 2. We need to prove that
[ΓmK
(IP )|I ′ , Γm11 (IP ) = γm11 , Γm12 (IP ) = γm12 , . . . , ΓmK
(IP ) = γmK
]
J
J−1
J−1
≤st [DmK
(π)|I ′ , Dm11 (π) = dm11 , Dm12 (π) = dm12 , . . . , DmK
(π) = dmK
],
J
J−1
J−1

(68)

whenever γmkj ≤ dmkj , mkj = m11 , m12 , . . . , mK
J−1 .
Note that node mK
J receives data from some node in HK−1 . Since both conditions of Lemma 11 are
satisfied in this case too, we can use it to prove (68).
Finally, using (67) and (68) with Theorem 6.B.3 and Theorem 6.B.16.(c) of [31], we prove (65). This
completes the proof.
Proof of Lemma 3. We can deduce from (2) that the age process ∆π under any policy π is an increasing
function of [D1 (π), . . . , DN −1 (π)]. Moreover, we can deduce from (14) that the process ∆LB
IP is an
increasing function of [Γ1 (IP ), . . . , ΓN −1 (IP )]. By using Theorem 6.B.16.(a) of [31], (17) follows
directly from (65). This completes the proof.
A PPENDIX D
P ROOF OF L EMMA 11
The proof of Lemma 11 is motivated by [32]. We prove (66) using Theorem 6.B.3 of [31] into two
steps.
Step 1: Consider packet 1. Define l∗ = max{l : ali (IP ) = Γ1i (IP )}, where sl∗ ≥ s1 . From the
construction of the policy IP and (63), Γ1i (IP ) is the arrival time of the first arrived packet to node i
under policy IP . Since the link (i, j) is idle by time Γ1i (IP ) and policy IP is a work-conserving policy,
packet l∗ will start its transmission under policy IP over the link (i, j) once it arrives to node i. Thus,
from (63), we obtain
[Γ1 j(IP )|I ′ ] = [vl∗ j (IP )|I ′ ] = [Γ1i (IP )|I ′ ].
(69)
Since we have [Γ1i (IP )|I ′ ] ≤ [D1i (π)|I ′ ] and [D1i (π)|I ′ ] ≤ [D1j (π)|I ′ ], it follows that
[Γ1j (IP )|I ′ ] = [Γ1i (IP )|I ′ ] ≤ [D1i (π)|I ′ ] ≤ [D1j (π)|I ′ ].

(70)

Step 2: Consider a packet p, where 2 ≤ p ≤ n. We suppose that, both in math description and in
words, there is no packet with generation time greater than sp has arrived to node j before packet p
2

The nodes in Hk are ordered rondamly.

January 1, 2018

DRAFT

25

Link (i, j)
under policy π
Link (i, j)
under policy IP

p
vpj (π)

Xπ
h∗

χ

apj (π)
k

RIP θ(IP )

(a) Case 1: Link (i, j) sends packet k after the time θ(IP ).

Link (i, j)
under policy π
Link (i, j)
under policy IP

p
vpj (π)
k
χ

Xπ

apj (π)

h∗
RIP θ(IP )

(b) Case 2: Link (i, j) sends packet k before the time IP .

Figure 11: Illustration of packet transmissions under policy π and policy IP . In policy π , link (i, j)
starts to send packet p at time vpj (π) and will complete its transmission at time apj (π). Hence, the
transmission duration of packet p is [vpj (π), apj (π)] in policy π . Under policy IP , link (i, j) is kept
busy before time vpj (π) for a time duration equal to the actual transmission time of packet h∗ and
becomes available to send a new packet at the time θ(IP ) < apj (π).

under policy π ; otherwise, if there is a fresher packet y with sy > sp and ayj (π) < apj (π), then we
replace packet p by packet y in the following argument. We need to prove that
[Γpj (IP )|I ′ , Γ1j (IP ) = γ1 , . . . , Γ(p−1)j (IP ) = γp−1 ]
≤st [Dpj (π)|I ′ , D1j (π) = d1 , . . . , D(p−1)j (π) = dp−1 ],

(71)

whenever γl ≤ dl , l = 1, 2, . . . , p − 1.
For notation simplicity, define Γp−1 , {Γ1j (IP ) = γ1 , . . . , Γ(p−1)j (IP ) = γp−1 } and D p−1 , {D1j (π) =
d1 , . . . , D(p−1)j (π) = dp−1 }.
As illustrated in Fig. 11, suppose that under policy π , link (i, j) starts to send packet p at time vpj (π)
and will complete its transmission at time apj (π). Under policy IP , define h∗ = argmaxh {vhj (IP ) :
vhj (IP ) ≤ vpj (π)} as the index of the last packet that its transmission starts over the link (i, j) before
time vpj (π). Note that the link (i, j) under policy IP is kept busy after time vh∗ j (IP ) for a time duration
equal to the actual transmission time of packet h∗ over the link (i, j). Suppose that under policy IP ,
link (i, j) is kept busy for χ (χ ≥ 0) seconds of the actual transmission time of packet h∗ before time
vpj (π). After time vpj (π), let RIP denote the remaining transmission time of packet h∗ that the link
(i, j) will be busy during it under policy IP . Hence, link (i, j) becomes available to send a new packet
at time vpj (π) + RIP . Let Xπ = apj (π) − vpj (π) denote the transmission time of packet p under policy
π and XIP = χ + RLB denote the actual transmission time of packet h∗ . Then, the CCDF of RIP is
given by
P[RIP > s] = P[XIP − χ > s|XIP > χ].

(72)

Because the packet transmission times are NBU, we can obtain that for all s, χ ≥ 0
P[XIP − χ > s|XIP > χ] = P[Xπ − χ > s|Xπ > χ] ≤ P[Xπ > s].

January 1, 2018

(73)

DRAFT

26

By combining (72) and (73), we obtain
RIP ≤st Xπ ,

(74)

vpj (π) + RIP ≤st vpj (π) + Xπ = apj (π).

(75)

which implies

From (75), we can deduce that link (i, j) becomes available to send a new packet under policy IP at
a time that is stochastically smaller than the time apj (π). Let θ(IP ) denote the time that link (i, j)
becomes available to send a new packet under policy IP . According to (75), we have
[θ(IP )|I ′ , Γp−1 ] ≤st [apj (π)|I ′ , D p−1 ],

(76)

whenever γl ≤ dl , l = 1, 2, . . . , p − 1.
It is important to note that, since we have [Γpi (IP )|I ′ ] ≤ [Dpi (π)|I ′ ], there is a packet with generation
time greater than sp is available to the link (i, j) before time vpj (π) under policy IP . At the time θ(IP ),
we have two possible cases under policy IP :
Case 1: link (i, j) starts to send a fresh packet k with k ≥ p at the time θ(IP ) under policy IP , as
shown in Fig. 11(a). Hence we obtain
[vkj (IP )|I ′ , Γp−1 ] = [θ(IP )|I ′ , Γp−1 ] ≤st [apj (π)|I ′ , D p−1 ]

(77)

whenever γl ≤ dl , l = 1, 2, . . . , p − 1.
Since sk ≥ sp , (63) implies
[Γpj (IP )|I ′ , Γp−1 ] ≤ [vkj (IP )|I ′ , Γp−1 ].

(78)

Since there is no packet with generation time greater than sp has been arrived to node j before packet
p under policy π , (64) implies
[Dpj (π)|I ′ , D p−1 ] = [apj (π)|I ′ , D p−1 ].

(79)

By combining (77), (78), and (79), (71) follows.
Case 2: Link (i, j) starts to send a stale packet (with generation time smaller than sp ) or there is no
packet transmission over the link (i, j) at the time θ(LB) under policy IP . Since the packets are served
by following a work-conserving LGFS principle under policy IP , and a packet with generation time
greater than sp is available to the link (i, j) before time vpj (π) under policy IP , the link (i, j) must
have sent a fresh packet k with k ≥ p before time θ(IP ), as shown in Fig. 11(b). Hence, we have
[vkj (IP )|I ′ , Γp−1 ] ≤ [θ(IP )|I ′ , Γp−1 ] ≤st [apj (π)|I ′ , D p−1 ]

(80)

whenever γl ≤ dl , l = 1, 2, . . . , p − 1.
Similar to Case 1, we can use (63), (64), and (80) to show that (71) holds in this case.
As we mentioned before, if there is a fresher packet y with sy > sp and ayj (π) < apj (π), then we

January 1, 2018

DRAFT

27

l
h

Link (i, j)

χlj

k
ali ahj
Rlj

akj

Figure 12: An illustration of Rlj and χlj . Packet l arrives to node i at time ali , while packet h with h < l is
being transmitted over the link (i, j). After the delivery of packet h to node j at time ahj , packet k with k ≥ l is
transmitted over the link (i, j). The duration Rlj is the waiting time of packet l in the queue of the link (i, j) until
the packet k starts its transmission. The duration χlj is the time spent by the link (i, j) on sending the packet h
before the time ali .

replace packet p by packet y in the previous argument to obtain
[Γyj (IP )|I ′ , Γp−1 ] ≤ [Dyj (π)|I ′ , D p−1 ]

(81)

whenever γl ≤ dl , l = 1, 2, . . . , p − 1.
Observing that sy > sp , (63) implies
[Γpj (IP )|I ′ , Γp−1 ] ≤ [Γyj (IP )|I ′ , Γp−1 ].

(82)

Since ayj (π) < apj (π) and sy > sp , (64) implies
[Dpj (π)|I ′ , D p−1 ] = [Dyj (π)|I ′ , D p−1 ].

(83)

By combining (81), (82), and (83), we can prove (71) in this case too. Finally, substitute (70) and (71)
into Theorem 6.B.3 of [31], (66) is proven.
A PPENDIX E
P ROOF OF T HEOREM 4
For notation simplicity, let policy P represent the non-prmp-LGFS policy and policy IP represent the
infeasible policy. Consider a node f ∈ Hk with k ≥ 1. We first identify the average gap between ∆LB
f,IP
and ∆f,P . For each link (i, j), define Rlj = Γlj − Dli as the time spent in the queue of the link (i, j) by
the packet that has a generation time greater than sl and arrives to node i at time Dli , until this packet
(or a fresher one) starts its transmission at the link (i, j). If there is a packet that is being transmitted
on the link (i, j) at time Dli , let χlj (χlj ≥ 0) denote the amount of time that the link (i, j) has spent
on sending this packet by the time Dli . These parameters (Rlj and χlj ) are functions of the scheduling
policy π . An illustration of these parameters is provided in Fig. 12. Note that policy P is a LGFS workconserving policy. Also, the packets under policy IP are served by following a work-conserving LGFS
principle. Thus, we can express Rlj under these policies as Rlj = [Xij − χlj |Xij > χlj ]. Because the
packet transmission times are NBU and i.i.d. across time and links, for all realization of χlj
[Rlj |χlj ] ≤st Xij , ∀j ∈ V, ∀l = 1, . . . , n,

January 1, 2018

(84)

DRAFT

28

which implies that
E[Rlj |χlj ] ≤ E[X], ∀j ∈ V, ∀l = 1, . . . , n,

(85)

Holds for policy P and policy IP . Let Lf denote the set of links that connect node 0 to node f (i.e.,
the set of links in the path from node 0 to node f ), where |Lf | = k. Define zl = Dlf (P ) − Γlf (IP ).
note that, if a packet k with k ≥ l arrives to node f at time Γlf (IP ) under policy IP , then a packet h
with h ≥ l must be delivered to node f at time Dlf (P ) under policy P . Therefor, zl represents the time
difference between the deliveries of these packets under policy IP and policy π , as shown in Fig. 13.
By invoking the construction of policy IP , we have Dj (IP ) = Γj (IP ) for all j ∈ V . Using this with
the definition of Rlj , we can express Γlf (IP ) as
X
[Rlj (IP )|χlj (IP )],
(86)
Γlf (IP ) = al0 +
j:(i,j)∈Lf

where Γlf (IP ) is considered as the arrival time of the first packet with generation time greater than sl
to node f under policy IP . Also, we can express Dlf (P ) as
X
X
Xij .
(87)
[Rlj (P )|χlj (P )] +
Dlf (P ) = al0 +
(i,j)∈Lf

j:(i,j)∈Lf

Observing that packet arrival times (a10 , a20 , . . . , an0 ) at node 0 and the packet transmission times are invariant of the scheduling policy π . Then, from the construction of policy IP , we have [Rlj (IP )|χlj (IP )] =
[Rlj (P )|χlj (P )] for all l = 1, . . . , n and all j ∈ H1 . Using this with (86) and (87), we can obtain
X
X
X
[Rlj (IP )|χlj (IP )]
Xij −
[Rlj (P )|χlj (P )] +
zl = Dlf (P ) − Γlf (IP ) =
(i,j)∈Lf

j:(i,j)∈Lf ,j6∈H1

≤

X

[Rlj (P )|χlj (P )] +

X

j:(i,j)∈Lf ,j6∈H1
′

Xij = zl .

(i,j)∈Lf

j:(i,j)∈Lf ,j6∈H1

(88)
′

Since the packet transmission times are independent of the packet generation process, we also have zl ’s
are independent of the packet generation process. In addition, from (85) and the fact that |Lf | = k, we
have
′
E[zl ] ≤ (2k − 1)E[X].
(89)
Now, we proceed to identify the average gap between ∆LB
f,IP and ∆f,P , where the gap process is denoted
by {Gf (t), t ∈ [0, ∞)}. The average gap is given by
RT
Gf (t)dt
′
[Ḡf |I ] = lim sup 0
.
(90)
T
T →∞
Let τl denote the inter-generation time between packet l and packet l − 1 (i.e., τm = sl − sl−1 ), where
τ = {τl , l ≥ 1}. Define N (T ) = max{l : sl ≤ T } as the number of generated packets by time T . Note
PN (T )
that [0, sN (T ) ] ⊆ [0, T ], where the length of the interval [0, sN (T ) ] is l=1 τl . Thus, we have
N (T )

X

τl ≤ T.

(91)

l=1

January 1, 2018

DRAFT

29

∆f,P

∆(t)

z4
z2
z1

∆LB
f,IP

z3

G1

G4

G3
τ3

G5

G2
s1 s2
s3
τ3

t

s4 s5

Figure 13: The evolution ∆LB
f,IP and ∆f,P .

The area defined by the integral in (90) can be decomposed into a sum of disjoint geometric parts.
Observing Fig. 13, the area can be approximated by the concatenation of the parallelograms G1 , G2 , . . .
(Gl ’s are highlighted in Fig. 13). Note that the parallelogram Gl results after the generation of packet l
(i.e., the gap that is corresponding to the packet l, occurs after its generation). Since the observing time
T is chosen arbitrary, when T ≥ sl , the total area of the parallelogram Gl is accounted in the summation
RT
PN (T )
l=1 Gl , while it may not be accounted in the integral 0 Gf (t)dt. This implies that
N (T )

X
l=1

Combining (91) and (92), we get

RT
0

Gl ≥

Z

T

Gf (t)dt.

(92)

0

PN (T )
Gf (t)dt
Gl
≤ Pl=1
.
N (T )
T
τl

(93)

l=1

Then, take conditional expectation given τ and N (T ) on both sides of (93), we obtain
RT
PN (T )
PN (T )
E[ 0 Gf (t)dt|τ, N (T )]
E[Gl |τ, N (T )]
E[ l=1 Gl |τ, N (T )]
= l=1 PN (T )
,
≤
P
N
(T
)
T
τl
τl
l=1

(94)

l=1

where the second equality follows from the linearity of the expectation. From Fig. 13, Gl can be calculated
as
Gl = τl zl .
(95)

January 1, 2018

DRAFT

30

substituting by (95) into (94), yields
RT
PN (T )
PN (T )
E[ 0 Gl (t)dt|τ, N (T )]
τl E[zl |τ, N (T )]
l=1 E[τl zl |τ, N (T )]
≤
= l=1 PN (T )
.
P
N
(T
)
T
τl
τl
l=1

(96)

l=1

Using (88), we obtain
RT
PN (T )
PN (T )
′
E[ 0 Gf (t)dt|τ, N (T )]
l=1 τl E[zl |τ, N (T )]
l=1 τl E[zl |τ, N (T )]
≤
≤
.
PN (T )
PN (T )
T
τl
τl
l=1

(97)

l=1

′

′

′

Note that zl ’s are independent of the packet generation process. Thus, we have E[zl |τ, N (T )] = E[zl ] ≤
(2k − 1)E[X] for all l. Using this in (97), we get
RT
PN (T )
E[ 0 Gf (t)dt|τ, N (T )]
τl (2k − 1)E[X]
≤ l=1 PN (T )
≤ (2k − 1)E[X],
(98)
T
τl
l=1

by the law of iterated expectations, we have
RT
E[ 0 Gf (t)dt]
≤ (2k − 1)E[X].
T

Taking lim sup of both sides of (99) when T → ∞, yields
RT
E[ 0 Gf (t)dt]
≤ (2k − 1)E[X].
lim sup
T
T →∞

(99)

(100)

Equation (100) tells us that the average gap between ∆LB
f,IP and ∆f,P is no larger than (2k − 1)E[X].
LB
Since ∆f,IP is a lower bound of ∆f,P , we obtain
¯ LB |I ′ ] ≤ [∆
¯ f,P |I ′ ] ≤ [∆
¯ LB |I ′ ] + (2k − 1)E[X],
[∆
f,IP
f,IP
¯ LB = lim supT →∞
where ∆
f,IP
π∈Π

E[

RT
0

∆LB
f,IP (t)dt]
.
T

(101)

From Lemma 3, we have for all I ′ satisfying Bij ≥ 1, and

′
′
[∆LB
f,IP |I ] ≤st [∆f,π |I ],

(102)

¯ LB |I ′ ] ≤ [∆
¯ f,π |I ′ ],
[∆
f,IP

(103)

¯ f,π |I ′ ].
¯ LB |I ′ ] ≤ min[∆
[∆
f,IP

(104)

which implies that

holds for all π ∈ Π. As a result, we get
π∈Π

Since policy P is a feasible policy, we get
¯ f,π |I ′ ] ≤ [∆
¯ f,P |I ′ ].
min[∆
π∈Π

(105)

Combining (101), (104), and (105), we get
¯ f,π |I ′ ] ≤ [∆
¯ f,P |I ′ ] ≤ min[∆
¯ f,π |I ′ ] + (2k − 1)E[X].
min[∆
π∈Π

January 1, 2018

π∈Π

(106)

DRAFT

31

Following the previous argument, we can show that (106) holds for all f ∈ Hk , with any k ≥ 1. This
proves (18), which complete the proof.

January 1, 2018

DRAFT

