The Age of Information in Multihop Networks
Ahmed M. Bedewy Yin Sun Ness B. Shroff
cs.IT cs.NI math.IT







The Age of Information in Multihop Networks
    Ahmed M. Bedewy, Yin Sun, Member, IEEE, and Ness B. Shroff, Fellow, IEEE
This paper was presented in part at IEEE ISIT 2017 <cit.>.
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, CNS-1518829, and CCF-1813050, and a grant from the Defense Thrust Reduction Agency HDTRA1-14-1-0058.
A. M. Bedewy is with the  Department  of  ECE,  The  Ohio  State  University, Columbus, OH 43210 USA (e-mail:  bedewy.2@osu.edu).
Y.  Sun  is  with  the  Department  of  ECE,  Auburn  University,  Auburn,  AL 36849 USA (e-mail:  yzs0078@auburn.edu).
N. B.  Shroff  is  with  the  Department  of  ECE and  the  Department  of  CSE, The Ohio State University,  Columbus, OH 43210 USA  (e-mail:  shroff.11@osu.edu).

    December 30, 2023
==========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



arabic



Information updates in multihop networks such as Internet of Things (IoT) and intelligent transportation systems have received significant recent attention. In this paper, we minimize the  age of a single information flow in interference-free multihop networks. When preemption is allowed and the packet transmission times are exponentially distributed, we prove that a preemptive Last-Generated, First-Served (LGFS) policy results in smaller age processes across all nodes in the network  than any other causal policy (in a stochastic ordering sense). In addition, for the class of New-Better-than-Used (NBU) distributions, we show that the non-preemptive LGFS policy is within a constant age gap from the optimum average age. In contrast, our numerical result shows that the preemptive LGFS policy can be very far from the optimum for some NBU transmission time distributions. Finally,  when preemption is prohibited and the packet transmission times are arbitrarily distributed, the non-preemptive LGFS policy is shown to minimize the age processes across all nodes in the network among all work-conserving policies (again in a stochastic ordering sense). Interestingly, these results hold under quite general conditions, including (i) arbitrary packet generation and arrival times, and (ii) for minimizing both the age processes in stochastic ordering and any non-decreasing functional of the age processes.

















 
 


 
 
 





 Age of information; Data freshness; Multihop network; New-Better-than-Used; Stochastic ordering; Scheduling 



§ INTRODUCTION

 

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 information is also crucial in other systems, e.g., monitoring systems that obtain information from environmental sensors and wireless communication systems that need rapid updates of channel state information. 

As a metric of data freshness, the age of information, or simply age, was defined in <cit.>. 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.

The demand for real-time information updates in multihop networks, such as the IoT, intelligent transportation systems, and sensor networks, has gained increasing attention recently. In intelligent transportation systems <cit.>, for example, a vehicle shares its information related to traffic congestion and road conditions to avoid collisions and reduce congestion. Thus, in such applications, maintaining the age at a low level at all network nodes is a crucial requirement. In some other information update applications, such as emergency alerts and sensor networks, critical information is needed to report in a timely manner, and the energy consumption of the sensor nodes must be sufficiently low to support a long battery life up to 10-15 years <cit.>. Because of the low traffic load in these systems, wireless interference is not the limiting factor, but rather battery life through energy consumption is. Furthermore, information updates over the Internet, cloud systems, and social networks are of significant importance. These systems are built on wireline networks or implemented based on transport layer APIs. Motivated by these applications, we investigate information updates over multihop networks that can be modeled as multihop queueing systems.






















It has been observed in early studies on age of information analysis <cit.> that Last-Come, First-Serve (LCFS)-type of scheduling policies can achieve a lower age than other policies. The optimality of the LCFS policy, or more generally the Last-Generated, First-Served (LGFS) policy, for minimizing the age of information in single-hop networks was first established in <cit.>. However, age-optimal scheduling in multihop networks remains an important open question.





























In this paper, we consider a multihop network represented by a directed graph, as shown in Fig. <ref>, where the update packets are generated at an external source and are then dispersed throughout the network via one or multiple gateway nodes. The case of multiple gateway nodes is motivated by news spreading in social media where news is usually posted by multiple social accounts or webpages. Moreover, we suppose that the packet generation times at the external source and the packet arrival times at the gateway node (gateway nodes) are arbitrary. This is because, in some applications, such as sensor and environment monitoring networks, the arrival process is not necessarily Poisson. For example, if a sensor observes an environmental phenomenon and sends an update packet whenever a change occurs, the arrival process of these update packets does not follow a Poisson process. The packet transmission times are independent but not necessarily identically distributed across the links, and
i.i.d. across time. Interestingly, we
find that some low-complexity scheduling policies can achieve (near) age-optimal performance in this setting. The main results in this paper are summarized in Table <ref>.



















 §.§ Our Contributions

We develop scheduling policies that can achieve age-optimality or near age-optimality in a multihop network with a single information flow. 

The following summarizes our main contributions in this paper: 


  * If preemption is allowed and the packet transmission times over the network links are exponentially distributed, we prove that the preemptive LGFS policy minimizes the age processes at all nodes in the network among all causal policies in a stochastic ordering sense (Theorem <ref>). 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 the non-decreasing functional of the age processes at all nodes represents a very general class of age metrics in that it includes many age penalty metrics studied in the literature, such as the time-average age <cit.>, average peak age <cit.>,  non-linear age functions <cit.>, and age penalty functional at single-hop network <cit.>.




  * Although the preemptive LGFS policy can achieve age-optimality for exponential transmission times, it does not always minimize the age processes for non-exponential transmission times. When preemption is allowed, we investigate an important class of packet transmission time distributions called New-Better-than-Used (NBU) distributions, which are more general than exponential. The network topology we consider here is 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, and buffer sizes (Theorem <ref>).  Our numerical result (Fig. <ref>) shows that the preemptive LGFS policy can be very far from the optimum for non-exponential transmission times, while the non-preemptive LGFS policy is near age-optimal.


  * If preemption is not allowed, then for arbitrary distributions of packet transmission times, we prove that the non-preemptive LGFS policy minimizes the age processes at all nodes among all work-conserving policies in the sense of stochastic ordering (Theorem <ref>).  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.




To the best of our knowledge, these are the first optimal results on minimizing the age of information in multihop queueing networks with arbitrary packet generation and arrival processes.



§ RELATED WORK

There exist a number of studies focusing on the analysis of the age and figuring out ways to reduce it in single-hop networks <cit.>. In <cit.>, the update frequency was optimized to minimize the age in First-Come, First-Served (FCFS) queueing systems with exponential service times. It was found that this frequency differs from those that minimize the delay or maximize the throughput. Extending the analysis to multi-class FCFS M/G/1 queue was considered in <cit.>.  In <cit.>, the stationary distributions of the age and peak age in FCFS GI/GI/1 queue was obtained. In <cit.>, it was shown that the age can be reduced by discarding old packets waiting in the queue when a new sample arrives. The age of information under energy replenishment constraints was analyzed in <cit.>. The time-average age was characterized for multiple sources LCFS information-update systems with and without preemption in  
<cit.>. In this study, the authors found that sharing service facility among Poisson sources improves the total age. The work in <cit.> analyzed the age in the presence of errors when the service times are exponentially
distributed. Gamma-distributed service times was considered in <cit.>. The studies
in <cit.>, <cit.> were carried out for LCFS queueing systems with and without preemption. 






It should be noted that in our study, the  packet generation and arrival times are exogenous, i.e., they are not controllable by the scheduler. On the other hand,  the generation times of update packets was optimized for single-hop networks in <cit.>. A general class of non-negative, non-decreasing age penalty functions was minimized for single source systems in <cit.>. Extending the study to multi-source systems was considered in <cit.>, where sampling and scheduling strategies are jointly optimized to minimize the age. A real-time sampling problem of the Wiener process was solved in <cit.>: If the sampling times are independent of the observed Wiener process, the optimal sampling problem in <cit.> reduces to an 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. 


There have also been a few recent studies on the age of information in multihop networks <cit.>.  The age is analyzed for specific network topologies, e.g., line
or star networks, in <cit.>. In <cit.>, an offline optimal sampling policy was developed to minimize the age in two-hop networks with an energy-harvesting source. A congestion control mechanism that enables timely delivery of the update packets over IP networks was considered in <cit.>. In <cit.>, the author analyzed the average age in a multihop line network with Poisson arrival process and exponential service times. This analysis was later extended in <cit.> to include age moments and distributions. This paper and <cit.> complement each other in the following sense: Our results (i.e., Theorem <ref>) show that the LCFS policy with preemption in service is age-optimal. However, we do not characterize the achieved optimal age, which was evaluated in <cit.>. The authors of <cit.> addressed the problem of scheduling in wireless multihop networks with general interference model and multiple flows, assuming that all network queues are adopting an FCFS policy. A similar network model was considered in <cit.>, where the optimal update policy was obtained for the “active sources scenario”.  In this scenario, each source can generate a packet at any time, and hence, each source always has a fresh packet to send. The active sources scenario in multihop networks was also considered in <cit.>, where nodes take turns broadcasting their updates, and hence each node can act either as a source or a relay. In contrast to our study, the works in <cit.> considered a time-slotted system, where a packet is transmitted from one node to another in one time slot.





















§ MODEL AND FORMULATION



 §.§ 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 𝔼[Z| A] denote the conditional expectation of Z for given A.

Let 𝐱=(x_1,x_2,…,x_n) and 𝐲=(y_1,y_2,…,y_n) be two vectors in ℝ^n, then we denote 𝐱≤𝐲 if x_i≤ y_i for i=1,2,…,n. A set U⊆ℝ^n is called upper if 𝐲∈ U whenever 𝐲≥𝐱 and 𝐱∈ U. We will need the following definitions: 
  Univariate Stochastic Ordering: <cit.> Let X and Y be two random variables. Then, X is said to be stochastically smaller than Y (denoted as X≤_stY), if

    ℙ{X>x}≤ℙ{Y>x},   ∀  x∈ℝ.


 Multivariate Stochastic Ordering: <cit.> 
Let 𝐗 and 𝐘 be two random vectors. Then, 𝐗 is said to be stochastically smaller than 𝐘 (denoted as 𝐗≤_st𝐘), if

    ℙ{𝐗∈ U}≤ℙ{𝐘∈ U},   for all upper sets   U⊆ℝ^n.


  Stochastic Ordering of Stochastic Processes: <cit.> Let {X(t), t∈ [0,∞)} and {Y(t), t∈[0,∞)} be two stochastic processes. Then, {X(t), t∈ [0,∞)} is said to be stochastically 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 t_1<t_2<…<t_n in [0,∞), it holds that

    (X(t_1),X(t_2),…,X(t_n))≤_st(Y(t_1),Y(t_2),…,Y(t_n)),

where the multivariate stochastic ordering in (<ref>) was defined in Definition <ref>.




 §.§ Network Model

We consider a multihop network represented by a directed graph 𝒢(𝒱,ℒ),  where 𝒱 is the set of nodes and ℒ is the set of links, as shown in Fig. <ref> [For the simplicity of presentation, we focus on the network model with a single gateway node in the rest of the paper. However, it is not hard to see that our results also hold for networks with multiple gateway nodes.]. The number of nodes in the network is |𝒱|=N. The nodes are indexed from 0 to N-1, where node 0 acts as a gateway node. Define (i, j)∈ℒ as a link from node i to node j, where i is the origin node and j is the destination node. We assume that the links in the network can be active simultaneously, which holds in the applications mentioned in Section <ref>. The packet transmission times are independent 
but not necessarily identically distributed across the links, and i.i.d. across time. As will be clear later on, we consider the following transmission time distributions: Exponential distribution, NBU distributions, and arbitrary distribution. In addition, we consider two types of network topology: general network topology and special network topology in which each node has one incoming link. We note that this special network topology is an extension of tandem queues. These different network settings are summarized in Table <ref>.















The system starts to operate at time t=0. The update packets are generated at an external source, and are firstly forwarded to node 0, from which they are dispersed throughout the network. Thus, the update packets may arrive at node 0 some time after they
are generated. The l-th update packet, called packet l, is generated at time s_l, arrives at node 0 at time a_l0, and is delivered to any other node j at time a_lj such that  0≤ s_1≤ s_2≤… and  s_l ≤ a_l0≤ a_lj for all j = 1, …, N-1. Note that in this paper, the sequences {s_1,s_2,…} and {a_10, a_20,…} are arbitrary. Hence, the update packets may not arrive at node 0 in the order of their generation times. For example, packet l+1 may arrive at node 0 earlier than packet l such that s_l ≤ s_l+1 but a_l0≥ a_(l+1)0. We suppose that once a packet arrives at node i, it is immediately available to all the outgoing links from node i. Moreover, the update packets are time-stamped with their generation times such that each node knows the generation times of its received packets. Each link (i,j) has a queue of buffer size B_ij to store the incoming packets, which can be infinite, finite, or even zero. If a link has a finite queue buffer size, then the packet that arrives to a full buffer either is dropped or replaces another packet in the queue. 











 §.§ Scheduling Policy
 
 We let π denote a scheduling policy that determines the following (at each link): i) Packet assignments to the server, ii) packet preemption if preemption is allowed, iii) packet droppings and replacements when the queue buffer is full. The sequences of packet generation times {s_1, s_2, …} and packet arrival times {a_10, a_20, …} at node 0 do not change according to the scheduling policy, while the packet arrival times at other nodes (i.e., a_lj for all l and j=1,…,N-1) are functions of the scheduling policy π. 

 We suppose that the packet transmission times over the links are invariant of the scheduling policy and the realization of a packet transmission time at any link is unknown until its
transmission over this link is completed (unless the transmission time is deterministic). 
 
 
 
 
 
 Let Π  denote the set of all causal policies, in which

scheduling decisions are made based on the history and current information of the system (system information includes the location, arrival times, and generation times of all the packets in the system, and the idle/busy state of all the servers).

  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 can be stored back into the queue if there is enough buffer space and 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 link's queue.


 §.§ Age Performance Metric


Let U_j(t)=max{s_l : a_lj≤ 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 <cit.>

    Δ_j(t)=t-U_j(t).
 
The process of Δ_j(t) is given by Δ_j={Δ_j(t), t∈ [0,∞)}. The initial state of U_j(t) at time t=0^- is invariant of the scheduling policy π∈Π, where we assume that U_j(0^-)=0=s_0 for all j∈𝒱. As shown in Fig. <ref>, 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)).

The age process of all the network nodes is given by 

    Δ={Δ(t), t∈ [0,∞)}.


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.

  Age Penalty Functional:
Let 𝐕 be the set of n-dimensional functions, i.e.,

    𝐕 = {f : [0,∞)^n ↦ℝ}.

A functional g:𝐕↦ℝ 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,∞).


The age penalty functionals used in prior studies include:


  * Time-average age <cit.>: The time-average age of node j is defined as


    g_1(Δ)=1/T∫_0^TΔ_j(t) dt,


  * Average peak age <cit.>: The average peak age of node j is defined as 

    g_2(Δ)=1/K∑_k=1^K A_kj,

where A_kj denotes the k-th peak value of Δ_j(t) since time t=0. 

  * Non-linear age functions <cit.>: The non-linear age function of node j is in the following form

    g_3(Δ)= 1/T∫_0^T h(Δ_j(t)) dt,

where h : [0,∞)→ [0,∞) can be any non-negative and non-decreasing function. As pointed out in  <cit.>, a stair-shape function h(x)=⌊ x⌋ can be used to characterize the dissatisfaction of data staleness when the information of interest is checked periodically, and an exponential function h(x)=e^x is appropriate for online learning and control applications where the desire for data refreshing grows quickly with respect to the age. Also, an indicator function h(x)=1(x>d) can be used to characterize the dissatisfaction when a given age limit d is violated. 

  * Age penalty functional in single-hop networks <cit.>: The age penalty functional in <cit.> is a non-decreasing functional of the age process at one node, which is a special case of that defined in Definition <ref> with n = 1.






§ MAIN RESULTS

In this section, we present our (near) age-optimality results for multihop networks. We prove our results using stochastic ordering.


 §.§ Exponential Transmission Times, Preemption is Allowed

 

We study age-optimal packet scheduling for networks that allow for preemption and the packet transmission times are exponentially distributed, independent across the links and i.i.d. across time[Although we consider exponential transmission times, packet transmission
time distributions are not necessarily identical over the network links, i.e.,
different links may have different mean transmission times.].  We consider a LGFS scheduling principle which is defined as follows.

A scheduling policy is said to follow the Last-Generated, First-Served discipline, if the last generated packet is sent first among all packets in the queue.  

We consider a preemptive LGFS (prmp-LGFS) policy at each link (i,j)∈ℒ. 


The implementation details of this policy are depicted in Algorithm <ref>[The decision related to packet droppings and replacements in full buffer case (at any link) doesn’t affect the age performance of prmp-LGFS policy. Hence, we don’t specify this decision under the prmp-LGFS policy.]. 




Define a set of parameters ℐ={𝒢(𝒱, ℒ), (B_ij, (i,j)∈ℒ),  s_l, a_l0,l=1,2,…}, where 𝒢(𝒱, ℒ) is the network graph, B_ij is the queue buffer size of link (i,j), s_l is the generation time of packet l, and a_l0 is the arrival time of packet l to node 0. 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.

If the packet transmission times are exponentially distributed, independent across links and i.i.d. across time, then for all ℐ and π∈Π 

    [Δ_𝐩𝐫𝐦𝐩-𝐋𝐆𝐅𝐒|ℐ]≤_st [Δ_π|ℐ],

or equivalently, for all ℐ and non-decreasing functional g
 
    𝔼[g(Δ_prmp-LGFS)|ℐ]= min_π∈Π𝔼[g(Δ_π)|ℐ],

provided the expectations in (<ref>) exist.


 We use a coupling and forward induction to prove it. We first consider the comparison between the preemptive LGFS policy and any arbitrary policy π. We couple the packet departure processes at each link of the network such that they are identical under both policies. Then, we use the forward induction over the packet delivery events at each link (using Lemma <ref>) and the packet arrival events at node 0 (using Lemma <ref>) to show that the generation times of the freshest packets at each node of the network are maximized under the preemptive LGFS policy. By this, the preemptive LGFS policy is age-optimal among all causal policies. For more details, see Appendix <ref>.
 








 

Theorem <ref> tells us that for arbitrary sequence of packet generation times {s_1, s_2, …}, sequence of arrival times {a_10, a_20, …} at node 0, network topology 𝒢(𝒱, ℒ), and buffer sizes (B_ij,(i,j)∈ℒ), the prmp-LGFS policy achieves optimality of the joint distribution of the age processes at the network nodes within the policy space Π. In addition, (<ref>) tells us that the prmp-LGFS policy minimizes any non-decreasing age penalty functional g, including the time-average age (<ref>), average peak age (<ref>), and non-linear age functions (<ref>). 



As we mentioned before, the result of Theorem <ref> still holds for the multiple-gateway model shown in Fig. <ref>. In particular, Lemma <ref> can be applied to each packet arrival event at each gateway, and hence the result follows. It is also worth pointing out that the arrival processes at the gateway nodes may be heterogeneous, and they do not change according to the scheduling policy.  A weaker version of Theorem <ref> can be obtained as follows.


If the conditions of Theorem <ref> hold, then for any arbitrary packet generation and arrival processes at the external source and node 0, respectively, and for all π∈Π

    Δ_𝐩𝐫𝐦𝐩-𝐋𝐆𝐅𝐒≤_stΔ_π.



We consider a mixture over the realizations of packet generation and arrival processes (arrival process at node 0) to prove the result. In particular, by using the result of Theorem <ref> and Theorem 6.B.16.(e) in <cit.>, the corollary follows.

































































































 §.§ New-Better-than-Used Transmission Times, Preemption is Allowed

Although the preemptive LGFS policy can achieve age-optimality when the transmission times are exponentially distributed, it does not always, as we will observe later, minimize the age for non-exponential transmission times. We aim to answer the question
of whether for an important class of distributions that are more general than exponential, optimality or near-optimality can be achieved while preemption is allowed. We here consider the classes of New-Better-than-Used (NBU) packet transmission time distributions, which are defined as follows.
  New-Better-than-Used distributions <cit.>: Consider a non-negative random variable X with complementary cumulative distribution function (CCDF) F̅(x)=ℙ[X>x]. Then, X is New-Better-than-Used (NBU) if for all t,τ≥0

    F̅(τ +t)≤F̅(τ)F̅(t).
 


Examples of NBU [The word better in the terminology New-Better-than-Used refers to that a random variable with a long lifetime is better than that with a shorter lifetime <cit.>. In our case, the random variable is the transmission time, and longer transmission time is worse in terms of the age. Thus, the word better here does not imply an improvement in the age performance.] distributions include constant transmission time, (shifted) exponential distribution, geometric distribution, Erlang distribution, negative binomial distribution, etc. Recently,  age was analyzed in single hop networks for exponential transmission times with transmission error in <cit.>, and for Gamma-distributed transmission times in <cit.>. These studies did not answer the question of which policy can be (near) age-optimal for non-exponential transmission times in single hop networks. We provided a unified answer to identify the policy that is near age-optimal in single hop networks in <cit.>. Since the question has remained open for multihop networks, we here extend our investigation to answer this question in multihop networks and  identify the near age-optimal policy for a more general class of transmission time distributions.



We propose a non-preemptive LGFS (non-prmp-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 is already at its maximum buffer level (i.e., the queue is already full). 

The implementation details of non-prmp-LGFS policy are depicted in Algorithm <ref>.




While we are able to consider a more general class of transmission time distributions, we are able to prove this result for a somewhat more restrictive network than the general topology 𝒢(𝒱,ℒ). The network here is represented by a directed graph 𝒢'(𝒱,ℒ), in which each node j∈𝒱\{0} has one incoming link. An example of this network topology is shown in Fig. <ref>. We show that the non-prmp-LGFS policy can come close to age-optimal into two steps: i) we construct an infeasible policy which provides the age lower bound, ii) we then show the near age-optimality result by identifying the gap between the constructed lower bound and our proposed policy non-prmp-LGFS. The construction of the the infeasible policy and the lemma that explains the age lower bound are presented in Appendix <ref>.




 



We can now proceed to characterize the age performance of policy non-prmp-LGFS among the policies in Π. Define a set of the parameters ℐ'={𝒢'(𝒱, ℒ), (B_ij, (i,j)∈ℒ),  s_l, a_l0,l=1,2,…}, where  𝒢'(𝒱, ℒ) is the network graph with the new restriction, B_ij is the queue buffer size of the link (i,j), s_l is the generation time of packet l, and a_l0 is the arrival time of packet l to node 0. Define ℋ_k as the set of nodes in the k-th hop, i.e., ℋ_k is the set of nodes that are separated by k links from node 0 [Node 0 is in ℋ_0.]. Let  i_j,k represent the index of the node in ℋ_k that is in the path to the node j (for example, in Fig. <ref>, i_11,1=7 and i_10,2=8). Define X_j as the packet transmission time over the incoming link to node j. We use Lemma <ref> in Appendix <ref> to prove the following theorem.





Suppose that the packet transmission times are NBU, independent across links, and i.i.d. across time, then for all ℐ' satisfying B_ij≥ 1 for each (i,j)∈ℒ

    min_π∈Π[Δ̅_j,π|ℐ']≤ [Δ̅_j, non-prmp-LGFS|ℐ']≤
       min_π∈Π[Δ̅_j,π|ℐ'] +𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m],∀ j∈ℋ_k, ∀ k≥ 1,

where Δ̅_j,π=lim sup_T→∞𝔼[∫_0^TΔ_j,π(t)dt]/T is the average age at node j under policy π.


We use the infeasible policy and the lower bound process that are constructed in Appendix <ref> to prove Theorem <ref> into three steps:

Step 1: We derive an upper bound on the time differences between the arrival times (at each node) of the fresh packets under the infeasible policy and those under policy non-prmp-LGFS.

Step 2: We use the upper bound derived in Step 1 to derive an upper bound on the average gap between the constructed infeasible policy in Appendix <ref> and the non-prmp-LGFS policy.

 Step 3: Finally, we use the upper bound on the average gap together with Lemma <ref>  in Appendix <ref> to prove (<ref>). For the full proof, see Appendix <ref>.

Theorem <ref> tells us that for arbitrary sequence of packet generation times {s_1, s_2, …}, sequence of arrival times {a_10, a_20, …} at node 0, and buffer sizes (B_ij≥ 1,(i,j)∈ℒ), the non-prmp-LGFS policy is within a constant age gap from the optimum average age among all policies in Π. Similar to Theorem <ref>, we can show that the result of Theorem <ref> still holds for the multiple-gateway model shown in Fig. <ref>.



The reason behind considering the restrictive network topology 𝒢'(𝒱, ℒ) is as follows: In the general network topology 𝒢(𝒱,ℒ), a node can receive update packets from multiple paths. As a result, the arrival time of a fresh packet at this node depends on the fastest path that delivers this packet to this node. This fastest path may differ from one packet to another on sample-path. Thus, it becomes challenging to establish an upper bound that is very close to the age lower bound (Steps 1 and 2 in the proof of Theorem <ref>) using sample-path and coupling techniques, in this case.









 


 §.§ General Transmission Times, Preemption is Not Allowed

Finally, we study age-optimal packet scheduling for networks that do not allow for preemption and for which the packet transmission times are arbitrarily distributed, independent across the links and i.i.d. across time.  Since preemption is not allowed, we are restricted to non-preemptive policies within Π. Moreover, we consider work-conserving policies. We use Π_npwc⊂Π to denote the set of non-preemptive work-conserving policies.








We consider the non-prmp-LGFS policy, where we show that it is age-optimal among the policies in Π_npwc in the following theorem.
 

If the packet transmission times are independent across the links and i.i.d. across time, then for all ℐ and π∈Π_npwc 

    [Δ_𝐧𝐨𝐧-𝐩𝐫𝐦𝐩-𝐋𝐆𝐅𝐒|ℐ]
     ≤_st [Δ_π|ℐ],

or equivalently, for all ℐ and non-decreasing functional g
 
    𝔼[g(Δ_non-prmp-LGFS)|ℐ]= min_π∈Π_npwc𝔼[g(Δ_π)|ℐ],

provided the expectations in (<ref>) exist.


The proof of Theorem <ref> is similar to that of Theorem <ref>. The difference is that preemption is not allowed here. See Appendix <ref> for more details.



It is interesting to note from Theorem <ref> that, age-optimality can be achieved for arbitrary transmission time distributions, even if the transmission time distribution differs from a link to another. General service time distributions have been considered in some recent age analysis on single-hop networks <cit.>. Theorem <ref> explains the age-optimal policies in these scenarios. Moreover, similar to Theorem <ref>, the result of Theorem <ref> still holds
for the multiple-gateway model shown in Fig. <ref>.













It is worth observing that the results in Theorem <ref>, Theorem <ref>, and Theorem <ref> hold for any link buffer sizes B_ij's. Hence, the buffer sizes can be chosen according to the application. In particular, in some applications, such as  news and social updates, users are interested in not just the latest updates, but also past news. Thus, in such application, we may need to have queues with buffer sizes greater than one to store old packets and send them later whenever links become idle. On the other hand, there are some other applications, in which old packets become useless when the fresher packets exist. Thus, in these applications, buffer sizes can be chosen to be zero (one) when we follow the prmp-LGFS (non-prmp-LGFS) scheduling policy. 



























































































 




§ NUMERICAL RESULTS



We now present numerical results that validate our theoretical findings. The inter-generation times at all setups are i.i.d. Erlang-2 distribution with mean 1/λ.






We use Figure <ref> to validate the result in Section <ref>. We consider the network in Fig. <ref>. The time difference between packet generation and arrival to node 0, i.e., a_i0-s_i, 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 <ref>
 illustrates the average peak age at node 2 versus the packet generation rate λ for the multihop network in Fig. <ref>. 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).
Note that the age performance of the preemptive LGFS policy is not affected by the buffer sizes. This is because, in the case of the preemptive LGFS policy, queues are only used to store the old packets, while a fresh packet can start service as soon as it arrives at a queue. Hence, the preemptive LGFS policy has the same performance for different buffer sizes.
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 <ref>.





























We use Figure <ref> to validate the results in Section <ref>. We consider the network in Fig. <ref>.
Figure <ref> 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 is normalized to 0.2. The time difference (a_i0-s_i) 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 case and hence is not plotted in this figure. The “Age lower bound” curve is generated by using ∫_0^TΔ_5,IP^LB/T when the buffer sizes are 1 which, according to Lemma <ref>, 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 <ref>. 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 <ref>. However, as can be seen in the figure, the average age at node 5 of the prmp-LGFS 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 increases the age. This phenomenon occurs heavily at the first link (link (0,1)) which, in turn, affects the age at the subsequent nodes. 










We use Figure <ref> to validate the result in Section <ref>.
We consider the network in Fig. <ref>. The time difference between packet generation and arrival to node 0, i.e., a_i0-s_i, is modeled to be either  1 or 100, with equal probability. Figure <ref> plots  the time-average age at node 3 versus the packets generation rate λ for the multihop network in Fig. <ref>. 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 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. This observation agrees with Theorem <ref>. We also observe that the average age of FCFS policy with B_ij=∞ 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 B_ij=1, the average age is finite at high traffic intensity, since the fresh packet has a better opportunity to be delivered in a relatively short period compared with FCFS policy with B_ij=∞. 



§ CONCLUSION

In this paper, we studied the age minimization problem in interference-free multihop networks. We considered general system settings including arbitrary network topology, packet generation and arrival times at node 0, and queue buffer sizes. A number of scheduling policies were developed and proven to be (near) age-optimal in  a  stochastic  ordering  sense for minimizing any non-decreasing functional of the age processes. In particular, we showed that age-optimality can be achieved when: i) preemption is allowed and the packet transmission times are exponentially distributed, ii) preemption is not allowed and the packet transmission times are arbitrarily distributed (among work-conserving policies). Moreover, for networks that allow for preemption and the packet transmission times are NBU, we showed that the non-preemptive LGFS policy is near age-optimal in a somewhat more restrictive network topology.




















§ PROOF OF THEOREM <REF>

Let us define the system state of a policy π:

 At any time t, the system state of policy π is specified by  𝐔_π(t)=( U_0,π(t), U_2,π(t), …,U_N-1,π(t)), where U_j,π(t) is the generation time of the freshest packet that arrived at node j by time t.
Let {𝐔_π(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 <ref> is the following lemma, where we compare policy P with any work-conserving policy π.

 
 Suppose that 𝐔_P(0^-)=𝐔_π(0^-) for all work conserving policies π, then for all ℐ,

    [{𝐔_P(t),  t∈[0,∞)}|ℐ]≥_st[{𝐔_π(t), t∈[0,∞)}|ℐ].




 
 We use coupling and forward induction to prove Lemma <ref>.
For any work-conserving policy π, suppose that stochastic processes 𝐔_P(t) and 𝐔_π(t) have the same distributions with 𝐔_P(t) and 𝐔_π(t), respectively. 

The state processes 𝐔_P(t) and 𝐔_π(t) are coupled in the following manner: If a packet is delivered from node i to node j at time t as 𝐔_P(t) evolves in policy P,  then there exists a packet delivery from node i to node j at time t as 𝐔_π(t) evolves in policy π. 
Such a coupling is valid since the transmission time is exponentially distributed and thus memoryless. Moreover, policy P and policy π have identical packet generation times (s_1, s_2, …, s_n) at the external source and packet arrival times (a_10, a_20, …, a_n0) to node 0. According to Theorem 6.B.30 in <cit.>, if we can show 

    ℙ[𝐔_P(t)≥𝐔_π(t), t∈[0,∞)|ℐ]=1,

then (<ref>) is proven. 

To ease the notational burden, we will omit the tildes in this proof on the coupled versions and just use 𝐔_P(t) and 𝐔_π(t). Next, we use the following lemmas to prove (<ref>):


Suppose that under policy P, 𝐔'_P is obtained by a packet delivery over the link (i,j) in the system whose state is 𝐔_P. Further, suppose that under policy π, 𝐔'_π is obtained by a packet delivery over the link (i,j) in the system whose state is 𝐔_π. If

    𝐔_P≥𝐔_π,

then,

    𝐔'_P≥𝐔'_π.



Let s_P 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

    U_j,P'   =max{U_j,P,s_P},
    
    U_j,π'   =max{U_j,π,s_π}.

Hence, we have two cases:


Case 1: If s_P≥ s_π. From (<ref>), we have

    U_j,P≥ U_j,π.

Also, s_P≥ s_π, together with  (<ref>) and (<ref>) imply

    U'_j,P≥ U'_j,π.

Since there is no packet delivery under other links, we get

    U'_k,P=U_k,P≥ U_k,π=U'_k,π,   ∀ k≠ j.

Hence, we have 

    𝐔'_P≥𝐔'_π.


Case 2: If s_P<s_π. By the definition of the system state, s_P≤ U_i,P and s_π≤ U_i,π. Then, using U_i, P≥ U_i,π, we obtain

    s_P < s_π≤ U_i,π≤ U_i, P.

Because s_P<U_i, P, policy P is sending a stale packet on link (i,j). By the definition of policy P, this happens only when all packets that are generated after s_P in the queue of the link (i,j) have been delivered to node j. Since s_π≤ U_i, P, node i has already received a packet (say packet w) generated no earlier than s_π in policy P. Because s_P<s_π, packet w is generated after s_P. Hence, packet w must have been delivered to node j in policy P such that

    s_π≤ U_j, P.

Also, from (<ref>), we have

    U_j,π≤ U_j, P.

Combining (<ref>) and (<ref>) with (<ref>), we obtain

    U'_j,P≥ U'_j,π.

Since there is no packet delivery under other links, we get

    U'_k,P=U_k,P≥ U_k,π=U'_k,π,   ∀ k≠ j.

Hence, we have 

    𝐔'_P≥𝐔'_π,

which complete the proof. 
See our technical report <cit.>.


Suppose that under policy P, 𝐔'_P is obtained by the arrival of a new packet to node 0 in the system whose state is 𝐔_P. Further, suppose that under policy π, 𝐔'_π is obtained by the arrival of a new packet to node 0 in the system whose state is 𝐔_π. If

    𝐔_P≥𝐔_π,

then,

    𝐔'_P≥𝐔'_π.



Let s denote the generation time of the new arrived packet. From the definition of the system state, we can deduce that

    U_0,P'   =max{U_0,P,s},
    
    U_0,π'   =max{U_0,π,s}.

Combining this with (<ref>), we obtain

    U'_0,P≥ U'_0,π.

Since there is no packet delivery under other links, we get

    U'_k,P=U_k,P≥ U_k,π=U'_k,π,   ∀ k≠ 0.

Hence, we have 

    𝐔'_P≥𝐔'_π,

which complete the proof.
See our technical report <cit.>.


For any sample path, we have that 𝐔_P(0^-) = 𝐔_π(0^-). This, together with Lemma <ref> and Lemma <ref>,  implies that  

    [𝐔_P(t)|ℐ] ≥ [𝐔_π(t)|ℐ],

holds for all t∈[0,∞). Hence, (<ref>) holds which implies (<ref>) by Theorem 6.B.30 in <cit.>.
This completes the proof.







According to Lemma <ref>, we have

    [{𝐔_P(t),  t∈[0,∞)}|ℐ]≥_st [{𝐔_π(t), t∈[0,∞)}|ℐ],

holds for all work-conserving policies π, which implies

    [{Δ_P(t), t∈[0,∞)}|ℐ]≤_st[{Δ_π(t), t∈[0,∞)}|ℐ],

holds for all work-conserving policies π.

Finally, transmission idling only postpones the delivery of fresh packets. Therefore, the age under non-work-conserving policies will be greater. As a result,

    [{Δ_P(t), t∈[0,∞)}|ℐ]≤_st[{Δ_π(t), t∈[0,∞)}|ℐ],

holds for all π∈Π. This completes the proof.







§ LOWER BOUND CONSTRUCTION

Let v_lj(π) denote the transmission starting time of packet l over the incoming link to node j under policy π. We construct an infeasible policy which provides the age lower bound as follows:



  1- The infeasible policy (IP) 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 v_lj(IP) to denote the transmission starting time of packet l over the incoming link to node j under the infeasible policy (IP) constructed above.

 
One example of the infeasible policy IP is illustrated in Fig. <ref>, where we consider two hops of tandem queues. We use t^l_j 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 a_10 (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 a_20 and finds the link (0,1) busy. Therefore, packet 2 cannot start its transmission until link (0,1) becomes idle again at time t^1_1 (v_21(IP)=t^1_1). Once packet 2 starts its transmission at time t^1_1 over the link (0,1), it is deemed delivered to node 1 (a_21(IP)=v_21(IP)=t^1_1) and link (0,1) is kept busy until time t^2_1. At time t^1_1, link (1,2) is busy. Thus, packet 2 cannot start its transmission over the link (1,2) until it becomes idle again at time t^1_2. Once packet 2 starts its transmission over the link (1,2) at time t^1_2, it is deemed delivered to node 2 (a_22(IP)=v_22(IP)=t^1_2).



  2- The age lower bound is constructed as follows. For each node j∈𝒱, define a function Δ_j,IP^LB(t) as

    Δ_j,IP^LB(t)=t-max{s_l : v_lj(IP)≤ t}.

The definition of the Δ_j,IP^LB(t) is similar to that of the age in (<ref>) 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, Δ_j,IP^LB(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. <ref>. The process of Δ_j,IP^LB(t) is given by Δ_j,IP^LB={Δ_j,IP^LB(t), t∈ [0,∞)} for each j∈𝒱. The age lower bound vector of all the network nodes is 

    Δ^LB_IP(t)=(Δ_0,IP^LB(t), Δ_1,IP^LB(t), …, Δ_N-1,IP^LB(t)).

The age lower bound process of all the network nodes is given by

    Δ_IP^LB={Δ^LB_IP(t), t∈ [0,∞)}.




The next Lemma tells us that the process Δ_IP^LB is an age lower bound of all policies in Π in the following sense. 

Suppose that the packet transmission times are NBU, independent across links, and i.i.d. across time, then for all ℐ' satisfying B_ij≥ 1 for each (i,j)∈ℒ, and π∈Π

    [Δ^LB_IP|ℐ']≤_st [Δ_π|ℐ'].



Condition (<ref>) is very crucial in proving Lemma <ref>.  In particular,  (<ref>) implies that for NBU service time distributions, the remaining service time of a packet that has already spent τ seconds in service is probably shorter than the service time of a new packet (i.e., ℙ[X>t+τ| X>τ]≤ℙ[X>t], where X represents the service time). This is used to show that the transmission starting times of the fresh packets under policy IP are stochastically smaller than their corresponding delivery times under policy π, and hence (<ref>) follows. For more details, see Appendix <ref>.









§ PROOF OF LEMMA <REF>



For notation simplicity, let policy IP represent the infeasible policy. We need to define the following parameters: Recall that v_lj denotes the transmission starting time of packet l over the incoming link to node j and a_lj denotes the arrival time of packet l to node j. We define Γ_lj and D_lj as

    Γ_lj   =min_q≥ l{v_qj},


    D_lj=min_q≥ l{a_qj},


where Γ_lj  and D_lj 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. <ref>. Suppose that there are n update packets, where n is an arbitrary positive integer, no matter finite or infinite. Define the vectors Γ_j=(Γ_1j, …, Γ_nj), and 𝐃_j=(D_1j, …, D_nj). Also, a packet l is said to be an informative packet at node i, if all packets that arrive to node i before packet l are staler than packet l, i.e., s_l'≤ s_l for all packets l' satisfying a_l'i≤ a_li. All these quantities are functions of the scheduling policy π (except the packet arrival times (a_10, a_20, …, a_n0) to node 0 which are invariant of the scheduling policy). 

We can deduce from (<ref>) that the age process Δ_π under any policy π is  increasing in [𝐃_1(π), …, 𝐃_N-1(π)]. Moreover, we can deduce from (<ref>) that the process Δ_IP^LB is increasing in [Γ_1(IP), …, Γ_N-1(IP)]. According to Theorem 6.B.16.(a) of <cit.>, if we can show 

    [Γ_1(IP), …, Γ_N-1(IP)|ℐ']≤_st [𝐃_1(π), …, 𝐃_N-1(π)|ℐ'],

holds for all π∈Π, then (<ref>) is proven. Hence, (<ref>) is what we need to show. We pick an arbitrary policy π∈Π and prove (<ref>) into two steps:

Step 1: We first show that, at any link (i,j), if the arrival times of the informative packets at node i under policy IP are earlier than those of the informative packets at node i under policy π, then the arrival times of the informative packets at node j under policy IP are earlier than those of the informative packets at node j under policy π. Observe that the vector Γ_i(IP) represents the arrival times of the informative packets at node i under policy IP (recall the construction of the infeasible policy IP and its age evolution in  (<ref>)), while the vector 𝐃_i(π) represents the arrival times of the informative packets at node i under policy π. Then, the previous statement is manifested in the following lemma. 

For any link (i,j)∈ℒ, if (i) the packet transmission times are NBU, and (ii) Γ_i(IP)≤𝐃_i(π), then

    [Γ_j(IP)|ℐ'] ≤_st [𝐃_j(π)|ℐ'],

holds for all ℐ' satisfying B_ij≥ 1.


See Appendix <ref>


Step 2: We use Lemma <ref> to prove (<ref>). Consider a node j∈ℋ_k. We prove (<ref>) using Theorem 6.B.3  and Theorem 6.B.16.(c) of <cit.> into two steps:

Step A: Consider node i_j,1. Observe that node i_j,1 receives update packets from node 0. Since the packet arrival times (a_10, …, a_n0) to node 0 are invariant of the scheduling policy, both conditions of  Lemma <ref> are satisfied and we can apply it on the link (0,i_j,1) to obtain

    [Γ_i_j,1(IP)|ℐ']≤_st [𝐃_i_j,1(π)|ℐ'].



Step B: Consider node i_j,m, where 2≤ m≤ k. We need to prove that 

    [Γ_i_j,m(IP)|ℐ', Γ_i_j,1(IP)=γ_i_j,1,…,Γ_i_j,m-1(IP)=γ_i_j,m-1 ]
       ≤_st [𝐃_i_j,m(π)|ℐ',𝐃_i_j,1(π)=𝐝_i_j,1,…,𝐃_i_j,m-1(π)=𝐝_i_j,m-1],
       whenever  γ_i_j,t≤𝐝_i_j,t,t=1, …,m-1.

Since node i_j,m receives update packets from node i_j,m-1 and Γ_i_j,m-1(IP)≤𝐃_i_j,m-1(π) in (<ref>), both conditions of Lemma <ref> are satisfied in this case as well (in particular, for the link (i_j,m-1,i_j,m)), and we can use it to prove (<ref>). By using (<ref>) and (<ref>) with Theorem 6.B.3 of <cit.>, we can show

    [Γ_i_j,1(IP), …, Γ_i_j,k(IP)|ℐ']≤_st [𝐃_i_j,1(π), …, 𝐃_i_j,k(π)|ℐ'].

 Following the previous argument, we can show that (<ref>) holds for all j∈𝒱. Note that the transmission times are independent
across links. Using this with Theorem 6.B.3 and Theorem
6.B.16.(c) of <cit.>, we prove (<ref>). This completes the proof.
















§ PROOF OF LEMMA <REF>

The proof of Lemma <ref> is motivated by the proof idea of  <cit.> and <cit.>. 
 

We prove (<ref>) using Theorem 6.B.3 of  <cit.> into two steps.

Step 1: Consider packet 1. Note that packet 1 may not be the first packet to arrive at node i under policy IP. Thus, we use l^* to denote the index of the first arrived packet at node i under policy IP, where s_l^*≥ s_1. From the construction of the policy IP and (<ref>), Γ_1i(IP) is the arrival time of the first arrived packet at node i under policy IP. Since the link (i,j) is idle before the arrival of the first arrived packet at node i, 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 (at time Γ_1i(IP)). Thus, from (<ref>), we obtain

    [Γ_1j(IP)|ℐ']=[v_l^*j(IP)|ℐ']=[Γ_1i(IP)|ℐ'].

Observe that we have 

    [Γ_1i(IP)|ℐ']≤[D_1i(π)|ℐ'].

 Also, we must have 
 
    [D_1i(π)|ℐ']≤[D_1j(π)|ℐ'],

 because a packet must spend a time over the link (i,j) (its transmission time over the link (i,j)) before it is delivered from node i to node j under policy π. Combining (<ref>), (<ref>), and (<ref>), we get 	 

    [Γ_1j(IP)|ℐ']=[Γ_1i(IP)|ℐ']≤[D_1i(π)|ℐ']≤[D_1j(π)|ℐ'].


Step 2: Consider a packet p, where 2≤ p ≤ n.  We suppose that no packet with generation time greater than s_p has arrived to node j before packet p under policy π. We need to prove that

    [Γ_pj(IP)|ℐ',Γ_1j(IP)=γ_1, …, Γ_(p-1)j(IP)=γ_p-1]
    ≤_st[D_pj(π)|ℐ', D_1j(π)=d_1, …, D_(p-1)j(π)=d_p-1],
    whenever  γ_l≤ d_l, l=1, 2, …, p-1.

For notation simplicity, define Γ^p-1≜{Γ_1j(IP)=γ_1, …, Γ_(p-1)j(IP)=γ_p-1} and D^p-1≜{ D_1j(π)=d_1, …, D_(p-1)j(π)=d_p-1}. We will show that the link (i,j) under policy IP can send a new packet at a time that is stochastically smaller than the arrival time of packet p at node j under policy π.  At this time, there are two possible cases under policy IP. One of them is that the link (i,j) sends a packet with generation time greater than s_p. The other one is that the link (i,j) sends a packet with generation time less than s_p or there is no packet to be sent. We will show that (<ref>) holds in either case.

As illustrated in Fig. <ref>, suppose that under policy π, link (i,j) starts to send packet p at time v_pj(π) and will complete its transmission at time a_pj(π). Under policy IP, define h^*=_h{v_hj(IP) : v_hj(IP)≤ v_pj(π)} as the index of the last packet whose transmission starts over the link (i,j) before time v_pj(π). Note that the link (i,j) under policy IP is kept busy after time v_h^*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 v_pj(π). Let R_IP denote the remaining busy period of the link (i,j) under policy IP after time v_pj(π) (this remaining busy period is due to the remaining transmission time of packet h^* after time v_pj(π)). Hence, link (i,j) becomes available to send a new packet at time v_pj(π)+R_IP. Let X_π=a_pj(π)-v_pj(π) denote the transmission time of packet p under policy π and X_IP=χ+R_LB denote the actual transmission time of packet h^*. Then, the CCDF of R_IP is given by
 
    ℙ[R_IP> s]=ℙ[X_IP-χ>s| X_IP>χ].

Because the packet transmission times are NBU, we can obtain that for all s,χ≥ 0
 
    ℙ[X_IP-χ>s| X_IP>χ]   =
    ℙ[X_π-χ>s| X_π>χ]
       ≤ℙ[X_π>s].

By combining (<ref>) and (<ref>), we obtain
 
    R_IP≤_stX_π,

which implies

    v_pj(π)+R_IP≤_stv_pj(π)+X_π=a_pj(π).

From (<ref>), 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 a_pj(π). Let θ(IP) denote the time that link (i,j) becomes available to send a new packet under policy IP. According to (<ref>), we have
 
    [θ(IP)|ℐ', Γ^p-1]≤_st[a_pj(π)|ℐ', D^p-1],
    whenever  γ_l≤ d_l, l=1, 2, …, p-1.

It is important to note that, since we have  [Γ_pi(IP)|ℐ']≤[D_pi(π)|ℐ'], there is a packet with generation time greater than s_p is available to the link (i,j) before time v_pj(π) 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. <ref>. Hence we obtain 
 
    [v_kj(IP)|ℐ', Γ^p-1]=[θ(IP)|ℐ', Γ^p-1]≤_st[a_pj(π)|ℐ', D^p-1]
    whenever  γ_l≤ d_l, l=1, 2, …, p-1.

Since s_k≥ s_p, (<ref>) implies

    [Γ_pj(IP)|ℐ', Γ^p-1]≤ [v_kj(IP)|ℐ', Γ^p-1].

Since there is no packet with generation time greater than s_p that has been arrived to node j before packet p under policy π, (<ref>) implies 

    [D_pj(π)|ℐ', D^p-1]=[a_pj(π)|ℐ', D^p-1].

By combining (<ref>), (<ref>), and (<ref>), (<ref>) follows.

Case 2: Link (i,j) starts to send a stale packet (with generation time smaller than s_p) 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 s_p is available to the link (i,j) before time v_pj(π) under policy IP, the link (i,j) must have sent a fresh packet k with k≥ p before time θ(IP), as shown in Fig. <ref>. Hence, we have
 
    [v_kj(IP)|ℐ', Γ^p-1]≤[θ(IP)|ℐ', Γ^p-1]≤_st[a_pj(π)|ℐ', D^p-1]
    whenever  γ_l≤ d_l, l=1, 2, …, p-1.

Similar to Case 1, we can use (<ref>), (<ref>), and (<ref>) to show that (<ref>) holds in this case. 

Notice that if there is a fresher packet y with s_y>s_p and a_yj(π)<a_pj(π) (this may occur if packet y preempts the transmission of packet p under policy π or packet y arrives to node i before packet p under policy π), then we replace packet p by packet y in the arguments and equations from (<ref>) to (<ref>) to obtain
 
    [Γ_yj(IP)|ℐ', Γ^p-1]≤[D_yj(π)|ℐ', D^p-1]
    whenever  γ_l≤ d_l, l=1, 2, …, p-1.

Observing that s_y>s_p, (<ref>) implies

    [Γ_pj(IP)|ℐ', Γ^p-1]≤[Γ_yj(IP)|ℐ', Γ^p-1].

Since a_yj(π)<a_pj(π) and s_y>s_p, (<ref>) implies

    [D_pj(π)|ℐ', D^p-1]=[D_yj(π)|ℐ', D^p-1].

By combining (<ref>), (<ref>), and (<ref>), we can prove (<ref>) in this case too. Finally, substitute (<ref>) and (<ref>) into Theorem 6.B.3 of  <cit.>, (<ref>) is proven. 












§ PROOF OF THEOREM <REF>



For notation simplicity, let policy P represent the non-prmp-LGFS policy and policy IP represent the infeasible policy (the construction of the infeasible policy and the age lower bound are provided in Appendix <ref>). We will need the definitions that are provided at the beginning of Appendix <ref> throughout this proof. Consider a node j∈ℋ_k with k≥ 1. We prove Theorem <ref> into three steps:

Step 1: We provide an upper bound on the time differences between the arrival times of the informative packets at node j under policy IP and those under policy P. To achieve that, we need the following definitions. For each link in the path to node j (i.e., (i_j,m-1,i_j,m) for all 1≤ m≤ k), define R_li_j,m=Γ_li_j,m-D_li_j,m-1 as the time spent in the queue of the link (i_j,m-1,i_j,m) by the packet that arrives at node i_j,m-1 at time D_li_j,m-1, until the first transmission starting time over the link (i_j,m-1,i_j,m) of the packets with generation time greater than s_l. If there is a packet that is being transmitted over the link (i_j,m-1,i_j,m) at time D_li_j,m-1, let χ_li_j,m (χ_li_j,m≥ 0) denote the amount of time that the link (i_j,m-1,i_j,m) has spent on sending this packet by the time D_li_j,m-1. These parameters (R_li_j,m and χ_li_j,m) are functions of the scheduling policy π. An illustration of these parameters is provided in Fig. <ref>. Note that policy P is a LGFS work-conserving policy. Also, the packets under policy IP are served by following a work-conserving LGFS principle. Thus, we can express R_li_j,m under these policies as R_li_j,m=[X_i_j,m-χ_li_j,m| X_i_j,m>χ_li_j,m]. Because the packet transmission times are NBU and i.i.d. across time, for all realization of χ_li_j,m

    [R_li_j,m|χ_li_j,m]≤_stX_i_j,m, for  m=1,…,k, ∀ l,

which implies that 

    𝔼[R_li_j,m|χ_li_j,m]≤𝔼[X_i_j,m],  for m=1,…,k, ∀ l,

holds for policy P and policy IP. Define z_l=D_lj(P)-Γ_lj(IP). Note that, Γ_lj(IP) represents the arrival time at node j of a packet p with s_p≥ s_l under policy IP, and D_lj(P) represents the arrival time at node j of a packet h with s_h≥ s_l under policy P. Therefor, z_l's represent the time differences between the arrival times of the informative packets at node j  under policy IP and those under policy P, as shown in Fig. <ref>. By invoking the construction of policy IP, we have D_lj(IP)=Γ_lj(IP) for all l. Using this with the definition of R_li_j,m, we can express Γ_lj(IP) as

    Γ_lj(IP)=a_l0+∑_m=1^k[R_li_j,m(IP)|χ_li_j,m(IP)],

 where Γ_lj(IP) is considered as the arrival time at node j of the first packet with generation time greater than s_l  under policy IP. Also, we can express D_lj(P) as 

    D_lj(P)=a_l0+∑_m=1^k[R_li_j,m(P)|χ_li_j,m(P)]+∑_m=1^kX_i_j,m.

Observing that packet arrival times (a_10, a_20, …) at node 0 and the packet transmission times are invariant of the scheduling policy π. Then, from the construction of policy IP, we have [R_li_j,1(IP)|χ_li_j,1(IP)]=[R_li_j,1(P)|χ_li_j,1(P)] for all l (because all nodes in ℋ_1 receive the update packets from node 0). Using this with (<ref>) and (<ref>), we can obtain

    z_l   =D_lj(P)-Γ_lj(IP)
       =∑_m=2^k[R_li_j,m(P)|χ_li_j,m(P)]+∑_m=1^kX_i_j,m
       -∑_m=2^k[R_li_j,m(IP)|χ_li_j,m(IP)]
       ≤∑_m=2^k[R_li_j,m(P)|χ_li_j,m(P)]+∑_m=1^kX_i_j,m=z_l^'.

Since the packet transmission times are independent of the packet generation process, we also have z_l^''s are independent of the packet generation process. In addition, from (<ref>), we have

    𝔼[z_l^']≤𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m].



Step 2: We use Step 1 to provide an upper bound on the average gap between Δ_j,IP^LB and Δ_j,P. This gap process is denoted by {G_j(t), t∈[0,∞)}. The average gap is given by 

    [G̅_j|ℐ']=lim sup_T→∞∫_0^T G_j(t)dt/T.

Let τ_l denote the inter-generation time between packet l and packet l-1 (i.e., τ_l=s_l-s_l-1), where τ={τ_l, l≥ 1}. Define N(T)=max{l : s_l≤ T} as the number of generated packets by time T. Note that [0,s_N(T)]⊆ [0,T], where the length of the interval 	[0,s_N(T)] is ∑_l=1^N(T)τ_l. Thus, we have 

    ∑_l=1^N(T)τ_l≤ T.

The area defined by the integral in (<ref>) can be decomposed into a sum of disjoint geometric parts. Observing Fig. <ref>, the area can be approximated by the concatenation of the parallelograms G_1, G_2,… (G_l's are highlighted in Fig. <ref>). Note that the parallelogram G_l 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≥ s_l, the total area of the parallelogram G_l is accounted in the summation ∑_l=1^N(T)G_l, while it may not be accounted in the integral ∫_0^T G_f(t)dt. This implies that

    ∑_l=1^N(T)G_l≥∫_0^T G_j(t)dt.

Combining (<ref>) and (<ref>), we get 

    ∫_0^T G_j(t)dt/T≤∑_l=1^N(T)G_l/∑_l=1^N(T)τ_l.

Then, take conditional expectation given τ and N(T) on both sides of (<ref>), we obtain

    𝔼[∫_0^T G_j(t)dt|τ, N(T)]/T   ≤𝔼[∑_l=1^N(T)G_l|τ, N(T)]/∑_l=1^N(T)τ_l
       =∑_l=1^N(T)𝔼[G_l|τ, N(T)]/∑_l=1^N(T)τ_l,

where the second equality follows from the linearity of the expectation. From Fig. <ref>, G_l can be calculated as 

    G_l=τ_lz_l.

substituting by (<ref>) into (<ref>), yields

    𝔼[∫_0^T G_j(t)dt|τ, N(T)]/T   ≤∑_l=1^N(T)𝔼[τ_lz_l|τ, N(T)]/∑_l=1^N(T)τ_l
       =∑_l=1^N(T)τ_l𝔼[z_l|τ, N(T)]/∑_l=1^N(T)τ_l.

Using (<ref>), we obtain
 
    𝔼[∫_0^T G_j(t)dt|τ, N(T)]/T   ≤∑_l=1^N(T)τ_l𝔼[z_l|τ, N(T)]/∑_l=1^N(T)τ_l
       ≤∑_l=1^N(T)τ_l𝔼[z_l^'|τ, N(T)]/∑_l=1^N(T)τ_l.

Note that z_l^''s are independent of the packet generation process. Thus, we have 𝔼[z_l^'|τ, N(T)]=𝔼[z_l^']≤𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m] for all l. Using this in (<ref>), we get

    𝔼[∫_0^T G_j(t)dt|τ, N(T)]/T   ≤∑_l=1^N(T)τ_l(𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m])/∑_l=1^N(T)τ_l
       ≤𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m],

by the law of iterated expectations, we have

    𝔼[∫_0^T G_j(t)dt]/T≤𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m].

Taking lim sup of both sides of (<ref>) when T→∞, yields

    lim sup_T→∞𝔼[∫_0^T G_j(t)dt]/T≤𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m].

Equation (<ref>) tells us that the average gap between Δ_f,IP^LB and Δ_f,P is no larger than 𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m].



Step 3: We use the provided upper bound on the gap in Step
2 to prove (<ref>). Since Δ_j,IP^LB is a lower bound of Δ_j,P, we obtain

    [Δ̅_j,IP^LB|ℐ']≤ [Δ̅_j,P|ℐ']≤
        [Δ̅_j,IP^LB|ℐ']+𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m],

where Δ̅_j,IP^LB=lim sup_T→∞𝔼[∫_0^TΔ_j,IP^LB(t)dt]/T. From Lemma <ref> in Appendix <ref>, we have for all ℐ' satisfying B_ij≥ 1, and π∈Π

    [Δ_j,IP^LB|ℐ']≤_st[Δ_j,π|ℐ'],

which implies that

    [Δ̅_j,IP^LB|ℐ']≤[Δ̅_j,π|ℐ'],

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

    [Δ̅_j,IP^LB|ℐ']≤min_π∈Π[Δ̅_j,π|ℐ'].

Since policy P is a feasible policy, we get

    min_π∈Π[Δ̅_j,π|ℐ']≤ [Δ̅_j,P|ℐ'].

Combining (<ref>), (<ref>), and (<ref>), we get

    min_π∈Π[Δ̅_j,π|ℐ']≤ [Δ̅_j,P|ℐ']≤
       min_π∈Π[Δ̅_j,π|ℐ']+𝔼[X_i_j,1]+2∑_m=2^k𝔼[X_i_j,m].

Following the previous argument, we can show that (<ref>) holds for all j∈𝒱\{0}. This proves (<ref>), which completes the proof.































































































































































































§ PROOF OF THEOREM <REF>

This proof is similar to that of Theorem <ref>. The difference between this proof and the proof of Theorem <ref> is that policy π cannot be a preemptive policy here. We will use the same definition of the system state of policy π used in Theorem <ref>. For notational simplicity, let policy P represent the non-preemptive LGFS policy.

The key step in the proof of Theorem <ref> is the following lemma, where we compare policy P with an arbitrary policy π∈Π_npwc.








 
 Suppose that 𝐔_P(0^-)=𝐔_π(0^-) for all π∈Π_npwc, then for all ℐ,

    [{𝐔_P(t),  t∈[0,∞)}|ℐ]≥_st [{𝐔_π(t), t∈[0,∞)}|ℐ].








 We use coupling and forward induction to prove Lemma <ref>.
For any work-conserving policy π, suppose that stochastic processes 𝐔_P(t) and 𝐔_π(t) have the same distributions with 𝐔_P(t) and 𝐔_π(t), respectively. 

The state processes 𝐔_P(t) and 𝐔_π(t) are coupled in the following manner: If a packet is delivered from node i to node j at time t as 𝐔_P(t) evolves in policy prmp-LGFS,  then there exists a packet delivery from node i to node j at time t as 𝐔_π(t) evolves in policy π.
Such a coupling is valid 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 (s_1, s_2, …, s_n) at the exterenal source and packet arrival times (a_10, a_20, …, a_n0) to node 0. According to Theorem 6.B.30 in <cit.>, if we can show 

    ℙ[𝐔_P(t)≥𝐔_π(t), t∈[0,∞)|ℐ]=1,

then (<ref>) is proven.  

To ease the notational burden, we will omit the tildes henceforth on the coupled versions and just use 𝐔_P(t) and 𝐔_π(t).

Next, we use the following lemmas to prove (<ref>):


Suppose that under policy P, 𝐔_P(ν) is obtained by a packet delivery over the link (i,j) at time ν in the system whose state is 𝐔_P(ν^-). Further, suppose that under policy π, 𝐔_π(ν) is obtained by a packet delivery over the link (i,j) at time ν in the system whose state is 𝐔_π(ν^-). If

    𝐔_P(t)   ≥𝐔_π(t),

holds for all t∈ [0, ν^-], then

    𝐔_P(ν) ≥𝐔_π(ν).




Let s_P 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

    U_j,P(ν)   =max{U_j,P(ν^-),s_P},
    
    U_j,π(ν)   =max{U_j,π(ν^-),s_π}.

Hence, we have two cases:

Case 1: If s_P≥ s_π. From (<ref>), we have

    U_j,P(ν^-)≥ U_j,π(ν^-).

By s_P≥ s_π, (<ref>), and (<ref>), we have

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

Since there is no packet delivery under other links, we get

    U_k,P(ν)=U_k,P(ν^-)≥ U_k,π(ν^-)=U_k,π(ν),   ∀ k≠ j.

Hence, we have 

    𝐔_P(ν) ≥𝐔_π(ν).











Case 2: If s_P<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_π≤ U_i,π(a_π).

From (<ref>), we obtain 

    U_i,π(a_π)≤ U_i,P(a_π).

Combining (<ref>) and (<ref>), yields

    s_π≤ U_i,P(a_π).

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

    U_i,P(a_π)≤ U_i,P(τ).

Then, (<ref>) and (<ref>) imply

    s_π≤ U_i,P(τ).

Since s_P < s_π, (<ref>) tells us

    s_P < U_i,P(τ),

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 that are generated after s_P in the queue of the link (i,j) have been delivered to node j by time τ. In addition, (<ref>) tells us that by time τ, node i has already received a packet (say packet h) generated no earlier than s_π in policy P. By s_P < s_π, packet h is generated after s_P. Hence, packet h must have been delivered to node j by time τ in policy P such that 


    s_π≤ U_j,P(τ).

Because the U_j,P(t) is a non-decreasing function of t, and τ≤ν^-, (<ref>) implies





    s_π≤ U_j,P(ν^-).

Also, from (<ref>), we have

    U_j,π(ν^-)≤ U_j,P(ν^-).

Combining (<ref>) and (<ref>) with (<ref>), we obtain

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

Since there is no packet delivery under other links, we get

    U_k,P(ν)=U_k,P(ν^-)≥ U_k,π(ν^-)=U_k,π(ν),   ∀ k≠ j.

Hence, we have 

    𝐔_P(ν) ≥𝐔_π(ν),

which complete the proof.



Suppose that under policy P, 𝐔'_P is obtained by the arrival of a new packet to node 0 in the system whose state is 𝐔_P. Further, suppose that under policy π, 𝐔'_π is obtained by the arrival of a new packet to node 0 in the system whose state is 𝐔_π. If

    𝐔_P≥𝐔_π,

then,

    𝐔'_P≥𝐔'_π.




The proof of Lemma <ref> is similar to that of Lemma <ref>, and hence is not provided.























For any sample path, we have that 𝐔_P(0^-) = 𝐔_π(0^-). This, together with Lemma <ref> and Lemma <ref>,  implies that  

    [𝐔_P(t)|ℐ] ≥ [𝐔_π(t)|ℐ],

holds for all t∈[0,∞). Hence, (<ref>) holds which implies (<ref>) by Theorem 6.B.30 in <cit.>.
This completes the proof.




According to Lemma <ref>, we have

    [{𝐔_P(t),  t∈[0,∞)}|ℐ]≥_st [{𝐔_π(t), t∈[0,∞)}|ℐ],

holds for all π∈Π_npwc, which implies

    [{Δ_P(t), t∈[0,∞)}|ℐ]≤_st[{Δ_π(t), t∈[0,∞)}|ℐ],

holds for all π∈Π_npwc. This completes the proof. 

IEEEbib



    [
    < g r a p h i c s >
]Ahmed M. Bedewy
received  the B.S.  and  M.S.  degrees  in  electrical  and  electronics engineering from Alexandria University, Alexandria,  Egypt, in 2011 and 2015,   respectively.   He   is   currently   pursuing   the Ph.D.   degree   with   the   Electrical   and   Computer Engineering Department, at the Ohio State University, OH, USA.  His  research interests  include wireless communication, cognitive radios, resource allocation, communication networks, information freshness, optimization, and scheduling algorithms.   He awarded the Certificate of Merit, First Class Honors, for being one of the top ten undergraduate students during 2006-2008 and for being 1-st during 2008-2011 in electrical and electronics engineering.




    [
    < g r a p h i c s >
]Yin Sun (S'08-M'11) received his B.Eng. and Ph.D. degrees in Electronic Engineering from Tsinghua University, in 2006 and 2011, respectively. At Tsinghua, he received the Excellent Doctoral Thesis Award of Tsinghua University, among many awards and scholarships. He was a postdoctoral scholar and research associate at the Ohio State University during 2011-2017. Since Fall 2017, Dr. Sun joined Auburn University as an assistant professor in the Department of Electrical and Computer Engineering.

His research interests include wireless communications, communication networks, information freshness, information theory, and machine learning. He is the founding co-chair of the first and second Age of Information Workshops, in conjunction with the IEEE INFOCOM 2018 and 2019. The paper he co-authored received the best student paper award at IEEE WiOpt 2013.




    [
    < g r a p h i c s >
]Ness B. Shroff (S’91–M’93–SM’01–F’07)
received the Ph.D. degree in electrical engineering from Columbia University in 1994. He joined Purdue University immediately thereafter as an Assistant Professor with the School of Electrical and Computer Engineering. At Purdue, he became a Full Professor of ECE and the director of  a university-wide center on wireless systems and applications in 2004. In 2007, he joined The Ohio State University, where he holds the Ohio Eminent Scholar Endowed Chair in networking and communications, in the departments of ECE and CSE. He holds or has held visiting (chaired) professor positions at Tsinghua University, Beijing, China, Shanghai Jiaotong University, Shanghai, China, and IIT Bombay, Mumbai, India. He has received numerous best paper awards for his research and is listed in Thomson Reuters’ on The World’s Most Influential Scientific Minds, and is noted as a Highly Cited Researcher by Thomson Reuters. He also received the IEEE INFOCOM Achievement Award for seminal contributions to scheduling and resource allocation in wireless networks. He currently serves as the steering committee chair for ACM Mobihoc and Editor at Large of the IEEE/ACM Transactions on Networking. 



