Age of Information in Multihop Multicast Networks
Baturalp Buyukates Alkan Soysal Sennur Ulukus


               

1]Baturalp Buyukates
2]Alkan Soysal
1]Sennur Ulukus
[1]Department of Electrical and Computer Engineering, University of Maryland, MD
[2]Department of Electrical and Electronics Engineering, Bahcesehir University, Istanbul, Turkey

 

Age of Information in Multihop Multicast NetworksThis work was supported by NSF Grants CNS 15-26608, CCF 17-13977 and ECCS 18-07348. This paper was presented in part at the Annual Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, October 2018.
    [
    December 30, 2023
============================================================================================================================================================================================================================================================================




 


	We consider the age of information in a multihop multicast network where there is a single source node sending time-sensitive updates to n^L end nodes, and L denotes the number of hops. In the first hop, the source node sends updates to n first-hop receiver nodes, and in the second hop each first-hop receiver node relays the update packets that it has received to n further users that are connected to it. This network architecture continues in further hops such that each receiver node in hop ℓ is connected to n further receiver nodes in hop ℓ+1. We study the age of information experienced by the end nodes, and in particular, its scaling as a function of n. We show that, using an earliest k transmission scheme in each hop, the age of information at the end nodes can be made a constant independent of n. In particular, the source node transmits each update packet to the earliest k_1 of the n first-hop nodes, and each first-hop node that receives the update relays it to the earliest k_2 out of n second-hop nodes that are connected to it and so on. We determine the optimum k_ℓ stopping value for each hop ℓ for arbitrary shifted exponential link delays.	




§ INTRODUCTION

Recently, with the increase in the number of communication network applications requiring real-time status information, timeliness of the received messages has become a critical and desirable feature for networks. Such applications include sensor networks measuring ambient temperature <cit.>, autonomous vehicular networks where instantaneous vehicle information including velocity, position and acceleration is needed <cit.> and news reports from Twitter. In all these applications, information loses its value as it becomes stale.

This motivates the study of age of information, which is a metric measuring the freshness of the received information. A typical model to study age of information includes a source which acquires time-stamped status updates from a physical phenomenon. These updates are transmitted over the network to the receiver(s) and the age of information in this network, or simply the age, is the time elapsed since the most recent update at the receiver was generated at the transmitter. In other words, at time t, age Δ(t) of a packet which was generated at time u(t) is Δ(t)=t-u(t).

Most of the existing work focuses on age analysis in a queuing-theoretic setting. References <cit.> study the age under various arrival and service profiles. References <cit.> and <cit.> investigate packet management strategies including blocking and preemption for M/G/1/1 and G/G/1/1 queues, respectively. Reference <cit.> studies multi-hop networks in which update packets are relayed from one node to another. Another line of research studies the age under the energy harvesting setting <cit.>.

Considering dense IoT deployments and the increase in the number of users in networks supplying time-sensitive information, the scalability of age as a function of the number of nodes has become a critical issue. To this end, we need to study how the age performance of the network changes with growing network size. Reference <cit.> studies a mobile social network with a single service provider and n communicating users, and shows that under Poisson contact processes among users and uniform rate allocation from the service provider, the average age of the content at the users grows logarithmically in n. In contrast, reference <cit.> observes that in a single-hop multicast network appropriate stopping threshold k can prevent information staleness as the network grows. 

Motivated by this observation, we study the scalability of the age in multihop multicast networks using similar threshold ideas. Extending the results of <cit.>, we first analyze the single-hop problem with exogenous arrivals where the source directly communicates with the end users but cannot generate the updates itself. We then characterize the age for the two-hop case (see Fig. <ref>) using our single-hop with exogenous arrivals result as a building block. We show that for this two-hop multicast network under i.i.d. shifted exponential link delays and stopping thresholds k_1 and k_2 at each hop, an upper bound on the average age can be obtained. Through this upper bound, we show that the average age is limited by a constant as n increases. Utilizing this upper bound, we then extend the result of two-hop network to L-hop multicast networks for general L. We determine the optimal stopping threshold for each hop ℓ, k_ℓ, that minimizes the average age for arbitrary shifted exponential link delays.





§ SYSTEM MODEL AND AGE METRIC
 
We consider a multihop system where in the first hop a single source node broadcasts time-stamped updates to n first-hop receiver nodes using n links with i.i.d. random delays, and in the second hop, each first-hop receiver node relays the update packets it has received to n further nodes that are connected to it. This network architecture continues in further hops such that each receiver node in hop ℓ-1 acts as a transmitter in hop ℓ and it is connected to n further receiver nodes in hop ℓ. Fig. <ref> shows the described model for two hops. We first consider the age of information in a two-hop (L=2) multicast network and then extend our results to general multihop multicast networks with L hops, where L is arbitrary. 

We start describing our system model within the simpler two-hop setting. In the two-hop multicast network, an update takes X time to reach from the source node to a particular mid-level node and X̃ time to reach from the mid-level nodes to a particular end node where X and X̃ are shifted exponential random variables with parameters (λ,c) and (λ̃,c̃), respectively, where c and c̃ are positive constants. When the shift parameters are zero random variables corresponding to service times become exponentially distributed. In each hop, the service times of individual links are i.i.d. realizations of random variables X and X̃, e.g., in the first hop service times of individual links are i.i.d. X_i and in the second hop service times of individual links are i.i.d. X̃_i.

In the two-hop scenario, age is measured for each of the n^2 end nodes and for node i at time t age is the random process Δ_i(t) = t - u_i(t) where u_i(t) is the time-stamp of the most recent update at that node. When the source node sends out update j, it waits for the acknowledgment from the earliest k_1 of n middle nodes. After it receives all k_1 acknowledgement signals, we say that update j has been completed and the source node generates update j+1. At this time, transmissions of the remaining n-k_1 packets are terminated. Thus, if a node in the first hop is not in the earliest k_1 nodes to receive update j then service of this update is preempted. In the second hop, these earliest k_1 nodes that have received update j start transmitting this update to their end nodes and they stop whenever k_2 of their end nodes have received the current update.  Middle nodes implement a blocking scheme when they are busy transmitting to the end nodes, i.e., they discard arriving packets when they are not idle.  When the middle nodes finish transmitting the current update to k_2 of their children nodes, they wait for the arrival of the next update from the source node.
	
	

For general L, principles that are explained above are repeated at every hop, e.g., the transmitters in hop ℓ wait for k_ℓ of their children nodes to receive the current update before they declare that the current update has been completed; they drop all other incoming updates from transmitters in hop ℓ-1 as they are transmitting the current update; and when their update is received by k_ℓ receivers they preempt the remaining n-k_ℓ updates. When this is over, transmitters in hop ℓ wait for the next update from their parent nodes in hop ℓ-1; see Fig. <ref>(b).

The metric we use, time averaged age, is given by

    Δ = lim_τ→∞1/τ∫_0^τΔ(t) dt

where Δ(t) is the instantaneous age of the last successfully received update as defined above. We will use a graphical argument similar to <cit.> to derive the average age at an individual end node. Since all link delays are i.i.d. for all nodes and packets, each end node i experiences statistically identical age processes and will have the same average age. Therefore, it suffices to focus on a single end user for the age analysis.



§ BUILDING BLOCK: SINGLE-HOP NETWORK WITH EXOGENOUS ARRIVALS
 

We first note that at the second hop what we essentially have is n parent nodes each tied to n children nodes. Therefore, each second hop transmitter and its children nodes correspond to the single-hop network analyzed in <cit.> with one important difference: second hop transmitters cannot generate update packets. They can only relay packets sent from the source node. Thus, in this section, we first analyze a single-hop network in which update packets arrive exogenously with a given expected interarrival time 1/μ. Then, using this network as a building block we analyze the L-hop network described in Section <ref>, first for L=2, i.e., a two-hop network, then for general L.  We have i.i.d. shifted exponential service times between the source and each of its n children nodes as in <cit.>. Similarly, transmission of the current update stops when k out of n nodes receive the update. Thus, in this section, we extend the results of <cit.> to the case of exogenous arrivals, and determine a k threshold which depends on λ, c and μ. Fig. <ref> shows the arrival and update structure of a building block. Fig. <ref>(a) shows this building block as part of a two-hop network; and Fig. <ref>(b) shows it as a part of an ℓth hop in an L-hop network. 



Under this model with i.i.d. link delay X, an update takes X_k:n units of time to reach k out of n nodes where we denote the kth order statistic of random variables X_1, … ,X_n as X_k:n. Here X_k:n is the kth smallest of X_1, … ,X_n, e.g., X_1:n = min{X_i} and X_n:n = max{X_i}. For shifted exponential random variable X, we have

    E[X_k:n] =    c + 1/λ(H_n - H_n-k) 
    
    Var[X_k:n] =   1/λ^2(G_n - G_n-k)

where H_n = ∑_j=1^n1/j and G_n = ∑_j=1^n1/j^2. Using these,

    E[X_k:n^2] =    c^2 + 2c/λ(H_n - H_n-k) + 1/λ^2((H_n - H_n-k)^2 +G_n - G_n-k)


We say that the system is busy when a transmitted update has not been received by k out of n nodes yet. Once k end nodes receive an update, transmitter stops the service to the remaining n-k nodes. Then, the system is idle until the next update arrives. Fig. <ref> shows a realization of the update process between the source node and a particular end node. Note that realizations of the update process for different end nodes might be different depending on when and for which updates these nodes have been one of the earliest k nodes. On the other hand, although realizations are different, each end node experiences the same random process. Updates arrive at the source node with an interarrival time, R, where E[R]=1/μ. In the most general setting, R is an arbitrary i.i.d. random variable. In Fig. <ref>, arrows that are above and below the source node line indicate the received and transmitted updates at the source node, respectively. 

An important aspect of our model is that updates at the source node are divided into three groups, namely successful updates, dropped updates, and preempted updates. In Fig. <ref>, filled circles correspond to successfully received updates. They indicate that the update received at the source node started transmission to n end nodes and this particular end node received the update. We denote the time between the transmission and the reception of successful updates (filled circles) as the service time, X̅. The order of this particular node might be smaller than k, thus X̅≤ X_k:n. The source continues the service of the first filled circled update until k nodes receive the update. During this time if new updates arrive at the source, they are dropped; the dropped updates (crosses in Fig. <ref>) never go into service, they are lost. Once k nodes receive this update, system becomes idle and the source waits for the arrival of the next update. 


We denote the waiting time until the next arrival with Z. The next arrival which is shown with an empty circle in Fig. <ref> starts the service. However, for this particular realization of the update process, this particular end node is not one of the earliest k end nodes during the transmission of empty circled update. Since the source stops service once k end nodes receive the update, this transmitted update never arrives at this particular end node. We denote those updates that start a service but do not arrive at this particular end node as preempted updates. Even though preemption usually means stopping a current service in order to start a new one immediately, here we use the word preemption to mean that the current service is stopped, and a new service will start after an idle period when a new update arrives at the source. However, similar to regular meaning of preemption, in our model as well, current preempted update leaves service and a fresh update takes over. 

We denote the time between two consecutive departures from the source as Y = X_k:n + Z. Note that there are a random number of dropped updates during each realization of Y. In Fig. <ref>, between the first successful (filled circle) update and the next update that starts the service (empty circle), there are three dropped updates (crossed). In other words, the fourth received update is able to start a new service. In addition, there are multiple realizations of Y before the next successful (filled circle) update, since this particular end node is not able to receive empty circled updates. We denote the time between two successful updates, i.e., two consecutive updates that depart from the source and successfully arrive at the end node, with S. Remember that Y is the time between two updates that depart from the source and start the service but are not guaranteed to arrive at this particular end node. We can relate the interarrival times of departing updates and arriving updates using S = ∑_i=1^M Y_i. In Fig. <ref>, this particular end node receives the first and the fourth updates that depart the source and enter the service. Therefore, in this example we have M=3. In addition, remember that R is the interarrival time between the updates that arrive at the source node. For a general R, there is no closed-form expression with known variables that relates interarrival times at the end node, S, to interarrival times at the source node, R. However, when R is exponential Z is exponential as well due to the memoryless property of the exponential distribution. Thus, for exponential R we have S = ∑_i=1^M (X_k:n+R)_i.

When the current update reaches k earliest nodes, the source node terminates the remaining n-k transmissions and begins to wait for the next arrival and then repeats the process when the next update packet arrives. Since the link delays are i.i.d., the end users receive the packet in service with probability p = k/n. If an end user receives update j and the next one it receives is update j+M, then M is geometrically distributed with p with moments

    E[M] = 1/p = n/k,      
    E[M^2] = 2-p/p^2 = 2n^2/k^2-n/k


Similar to <cit.>, the average age for the earliest k stopping scheme with exogenous packet arrivals with rate μ is


    Δ_(k,μ) =   E[A]/E[S]

where A denotes the shaded area in Fig. <ref> and S is its length. Remember from Fig. <ref> that the random variable S is the  interarrival time at the end nodes. Inspecting Fig. <ref> to calculate A, we find E[A] = 1/2E[S^2] + E[S]E[X̅]. Here, X̅ denotes the service time of a successful update such that E[X̅] = E[X_i | i ∈𝒦] where 𝒦 is the set of earliest k nodes that receive the update. Now, (<ref>) becomes[Since the building block studied in this section will eventually be used in the upcoming sections in the analysis of two-hop and L-hop networks, we should emphasize that the definitions of X̅ and S do not assume any network structure. As far as (<ref>) is considered, it is not important where an update that is received by an end node is generated. X̅ is the time that the update spends in the system from the time it is generated (possibly by a node other than the one that relays it to the end node) until the time it is received at the end node. S is the time between two consecutive successfully received updates, regardless of whether the updates are generated at the node that transmits them or not. This reasoning is important for our derivations in multihop multicast networks.]

    Δ_(k,μ) =    E[X̅] + E[S^2]/2E[S]

 We can write the first and second moments of S  in terms of Y as 

    E[S]    = E[M]E[Y] 
    
    E[S^2]    = E[M]E[Y^2]+E[Y]^2E[M^2-M]
 
Inserting these into (<ref>) we obtain

    Δ_(k, μ) = E[X̅]+ E[M^2]/2E[M]E[Y] + Var[Y]/2E[Y]


In the following theorem, we determine the age of an update at an end node for a single-hop building block model using (<ref>).

 
For  a single-hop building block model with exogenous arrivals that have expected interarrival time 1/μ, for the earliest k stopping scheme, the average age of an update at an individual end node is
	
    Δ_(k,μ) =   1/k∑_i=1^k E[X_i:n] + 2n-k/2k(E[X_k:n] + E[Z]) + Var[X_k:n+Z]/2(E[X_k:n] + E[Z])




	The first term comes from E[X̅] as
	
    E[X̅] =    E[X_j| j ∈𝒦] = ∑_i=1^k E[X_i:n] Pr[j=i| j ∈𝒦 ] = 1/k∑_i=1^k E[X_i:n]
	
	where we used the fact that, since we have k out of n nodes selected independently and identically in 𝒦, we have Pr[j=i| j ∈𝒦] = 1/k. The second and third terms are obtained upon substitution of Y = X_k:n + Z and E[M] and E[M^2] expressions given in (<ref>) into (<ref>).  


When we have general interarrival times as we have in this problem, X_k:n and Z may be dependent. However, with exponential interarrivals we can show their independence using the memoryless property, and simplify the age expression in (<ref>) as follows.

 
	When the arrival process is Poisson with rate μ, the age of an end node is
	
    Δ_(k,μ) =   1/k∑_i=1^k E[X_i:n] + 2n-k/2kμ(μ E[X_k:n] + 1) + μ Var[X_k:n]/2(μ E[X_k:n] + 1) + 1/2(μ^2 E[X_k:n] + μ)




	When the arrival process is Poisson with μ, in other words, R is exponential with expected interarrival time 1/μ, the random variable Z which corresponds to the residual interarrival time is exponentially distributed with the same parameter, i.e., Z=R. In addition, Z is independent of X due to the memoryless property of the exponential distribution. Then,
	
    Var[Y] = Var[X_k:n+Z] = Var[X_k:n]+Var[Z]

	and we plug in E[Z] = 1/μ and Var[Z] = 1/μ^2. 

When the service times X are i.i.d. shifted exponential random variables and when n is large, we can further simplify the age expression in (<ref>) as follows.
  
	For large n and n>k, set k = α n. For shifted exponential (λ,c) service times X, the average age for the earliest k scheme with exogenous Poisson arrivals with rate μ can be approximated as
	
    Δ_(k,μ)≈c/α + c/2  + 1/λ - 1/2λlog(1-α) +1/αμ-1/2μ + 1/2(μ^2c - μ^2 log(1-α)/λ+μ)^-1
	


	Using the order statistics above,
	
    δ_1 =    1/k∑_i=1^k E[X_i:n] =  c + H_n/λ - 1/kλ∑_i=1^k H_n-i
	 	
	As in <cit.>, we have ∑_i=1^k H_n-i  = ∑_i=1^n-1 H_i - ∑_i=1^n-k-1 H_i and the series identity ∑_i=1^k H_i  = (k+1)(H_k+1-1). Using these we get
	
    δ_1 =  c+ 1/λ- n-k/kλ(H_n - H_n-k) ≈ c+1/λ+1-α/αλlog(1-α)

	since for large n, we have H_i ≈log(i)+γ. Also,
	
    δ_2 =   2n-k/2μ k (μ E[X_k:n ] + 1) 
     =   2n-k/2μ k(μ(c+ H_n - H_n-k/λ)+1) 
    ≈   (2-α)c/2α + α-2/2αλlog(1-α) + 2-α/2αμ
	
	Next, we note that we have 	
	
    lim_n→∞μ Var[X_k:n]/2(μ E[X_k:n]+1) = 0
	 	
	We see this from the expected values of order statistics,
	
    μ Var[X_k:n]/2(μ E[X_k:n]+1) =   μ (G_n-G_n-k)/2(μλ^2c+μλ(H_n-H_n-k)+λ^2)

	We know that the sequence G_n converges to π^2/6. As n increases G_n-k = G_(1-α)n also goes to the same value making the numerator 0. Thus, as n tends to ∞ (<ref>) is achieved. Similarly,
	
    δ_3 =   1/2(μ^2E[X_k:n]+μ)≈1/2(μ^2c-μ^2 log(1-α)/λ+μ)^-1
	 	
	Summing δ_1, δ_2, and δ_3 yields the expression in (<ref>).


Note that the age expression in (<ref>) when n is large is a function of the ratio α=k/n only implying that the age converges to a constant even when the packets arrive exogenously, similar to <cit.> where the packets are generated at will at the source. 

Although there is no explicit closed form solution for the optimal α, denoted as α^*, which minimizes (<ref>), we can calculate it numerically. For instance, when (λ, c)=(1, 1) and Poisson arrival rate is μ=1, age minimizing α is α^* = 0.837. This optimal value is higher than that of the original case in which the source itself generates the packets at will, which is α^*=0.732 found in <cit.>. This is because with exogenous arrivals at the source node, update interarrival time at the end nodes is larger. In this regard, we see that when the Poisson arrival rate is increased α^* decreases. This is expected because when the arrival rate is high (i.e., update packets arrive frequently), the source node prefers to wait for the freshest one instead of sending the current update to more and more end users. Similarly, when the arrival rate is low (i.e., update packets arrive infrequently), α^* is higher because in this case source knows that interarrival time is higher so that before it waits for the next packet it wants to update as many end nodes as it can (see Fig. <ref>(a)). 
We also note that as we take μ→∞ in (<ref>), we get

    Δ_(k)≈c/α + c/2  + 1/λ - 1/2λlog(1-α)
	
which is the age expression in <cit.>. Thus, age expression under exogenous Poisson arrivals with rate μ converges to the case in which source generates the packets itself as μ tends to ∞.

Finally, we note an interesting aspect of the problem with exogenous arrivals: It is shown in <cit.> that when the service time random variable X is exponential (i.e., shift variable is zero), the average age is minimized when k=1. However, this is not the case when updates arrive exogenously. We observe in Fig. <ref>(b) that the age minimizing k value can be greater than 1, and it depends on the update arrival rate, μ. As μ increases, the optimal k decreases and approaches 1. The reason for this is that the random waiting time with exogenous arrivals introduces a random shift to the exponential distribution of the service time. 


 


§ TWO-HOP NETWORK
 
Using the building block problem solved in the previous section, we are now ready to solve the two-hop problem (L=2) described in Section <ref> as a preliminary step towards solving the most general case for arbitrary L. In the two-hop system, middle nodes cannot generate updates rather they receive them from the source node. Thus, each middle node and its n children nodes in the second hop can be modeled as in Section <ref>. Since the source node sends updates to the first k_1 of its nodes, a middle node receives a certain update packet with probability p_1 = k_1/n. If a middle node receives update j and the next one it receives is update j+M_1, as in the building block problem, M_1 is a geometrically distributed random variable with parameter p_1. 

Since the source generates a new update at will once the current update is delivered to k_1 middle nodes, the interarrival time between updates that start service in the first hop is Y_1 = X_k_1:n. Let random variable S_1 denote the interarrival time at the receiver nodes in the first hop. In other words, let S_1 denote the time between updates that leave service in the first hop. Since each update cycle takes X_k_1:n units of time, successful interarrival time at the middle nodes can be written as

    S_1 = ∑_i=1^M_1 (Y_1)_i = ∑_i=1^M_1 (X_k_1:n)_i

where the mean interarrival time is E[S_1]=E[M_1]E[X_k_1:n]. Note that we have Z_1 = 0 for the source node since it generates the updates as soon as the previous one is completed (transmitted to k_1 nodes). The receiver nodes in the first hop immediately relay the update that they have received. Therefore, the interarrival time between the successfully received updates at the receiver nodes in the first hop, S_1, is equal to update interarrival time at the transmitter nodes in the second hop, R_2.

After receiving the updates with interarrival time R_2=S_1, middle nodes transmit each update until it is delivered to k_2 of their children nodes. Similar to the first hop, when a middle node transmits an update, an end node receives the update with probability p_2 = k_2/n. Geometrically distributed M_2 with parameter p_2 denotes the number of cycles between successive updates to an end node. The interarrival time between updates that depart from a middle node and start service in the second hop is Y_2 = X̃_k_2:n + Z_2. Let random variable S_2 denote the interarrival time between updates that successfully arrive at the receiver nodes in the second hop. Then,

    S_2 = ∑_i=1^M_2 (Y_2)_i = ∑_i=1^M_2 (X̃_k_2:n + Z_2)_i


Note that in this model a successful update reaches an end node without being preempted in each of the hops. Thus, the service time of a successful update denoted by X̅ is the sum of link delays in each hop and corresponds to the total time spent in the system by that update. Then, the total service time of a successful update delivered to some node i through middle node j is E[X̅] = E[X_j | j ∈𝒦] + E[X̃_̃ĩ| i ∈𝒦_j]. Here the set 𝒦 is the set of first k_1 middle nodes that receive the update and the set 𝒦_j defined for each j in 𝒦 is the set of first k_2 end nodes that receive the update. Thus, for an update to reach an end node that end node has to be among the earliest k_2 children nodes of its middle node and the corresponding middle node has to be one of the earliest k_1 middle nodes. Now, by using (<ref>), the average age of an end node for a two-hop system is given in the following theorem.
 
	For a two-hop system with the earliest k_1, k_2 stopping scheme, the average age at an individual end node is
	
    Δ_(k_1, k_2) = 1/k_1∑_i=1^k_1 E[X_i:n] + 1/k_2∑_i=1^k_2 E[X̃_i:n] + 2n-k_2/2k_2(E[X̃_k_2:n] + E[Z_2]) + Var[X̃_k_2:n+Z_2]/2(E[X̃_k_2:n] + E[Z_2])
 



	This theorem follows from Theorem <ref> upon observing that the second hop is the same as the building block problem. However, successful updates in the two-hop setting spend time in both hops to reach the end nodes. Noting also that successful updates do not wait in the system till they reach the end nodes, we find 
	
    E[X̅] = 1/k_1∑_i=1^k_1 E[X_i:n] + 1/k_2∑_i=1^k_2 E[X̃_i:n]

	Using (<ref>) in (<ref>) yields the theorem.


This theorem is valid for any distribution for X and X̃. Random variable Z_2 denotes the residual interarrival time before the next update arrives to the middle node. When we no longer have exponential interarrival times, it is not easy to determine the first and second order statistics of Z_2. However, we can upper bound the average age of our model Δ_(k_1, k_2) with the average age under exponential interarrivals to the middle nodes Δ'_(k_1, k_2) using the following lemma.

 
	For a two-hop system, let Δ'_(k_1, k_2) denote the average age of an end node under exponential interarrivals to middle nodes with mean E[R_2]. Then, we have Δ_(k_1, k_2)≤Δ'_(k_1, k_2).

The proof of Lemma <ref> follows from the DMRL (decreasing mean residual life) <cit.> property of interarrival times and NBUE (new better than used in expectation) <cit.> property of service times and is provided in Section <ref>. Note that as long as the aforementioned conditions on the interarrival and service time distributions are met, this lemma also applies to the case with L>2 hops. This generalization is made in Section <ref>.  Since Δ_(k_1, k_2)≤Δ'_(k_1, k_2), in order to prove that the average age in the two-hop system is bounded by a constant, all we need to show is that Δ'_(k_1, k_2) is upper bounded by a constant as the network grows. 

 
For a two-hop system, assuming exponential interarrivals to the middle nodes with E[R_2], the average age at an end node under the earliest k_1,  k_2 stopping scheme is
	
    Δ'_(k_1, k_2) =   1/k_1∑_i=1^k_1 E[X_i:n] + 1/k_2∑_i=1^k_2 E[X̃_i:n] + 2n-k_2/2k_2E[X̃_k_2:n] + 2n^2-nk_2/2k_1k_2E[X_k_1:n]  
       + k_1Var[X̃_k_2:n]/2(k_1E[X̃_k_2:n] + nE[X_k_1:n]) + n^2E[X_k_1:n]^2/2k_1(k_1E[X̃_k_2:n] + nE[X_k_1:n])




When the interarrival times to the middle nodes, R_2 are exponential, then Z_2 = R_2 due to the memoryless property of the exponential distribution. In addition, we know that R_2 = S_1. Therefore, Z_2 is  exponential with mean E[Z_2] = E[S_1] = E[M_1]E[X_k_1:n]. Then, Var[Z_2] =E[S_1]^2 = E[M_1]^2E[X_k_1:n]^2 where M_1 is geometrically distributed with p_1 = k_1/n. Combining these and noting that Z_2 and X̃_k_2:n are independent yields the result.


 
For a two-hop system, assuming n is large and n>k_1 and n>k_2 and letting k_1 = α_1n and k_2 = α_2n, under exponential interarrival assumption to the middle nodes with mean E[R_2], and shifted exponential service times X with (λ,c) and X̃ with (λ̃, c̃), the average age for the earliest k_1, k_2 scheme can be approximated as
	
    Δ'_(k_1,k_2)≈   1/λ + 1/λ̃ + c̃/α_2 + c̃/2 -1/2λ̃log(1-α_2) + 2-α_2+2α_1α_2/2α_1α_2c  
        + λ̃K_1^2/2α_1λ[λα_1K_2+λ̃K_1] +  3α_2-2α_1α_2-2/2α_1α_2λlog(1-α_1)
	
	where K_1 = (λ c-log(1-α_1)) and K_2 = (λ̃c̃-log(1-α_2)).


With Corollary <ref> we have showed that Δ'_(k_1, k_2) derived in Corollary <ref> is independent of n for large n. Since it upper bounds our age expression Δ_(k_1, k_2), we conclude that age under the earliest k_1, k_2 stopping scheme for a two-hop multicast network is also independent of n for large n and is bounded by a constant as the number of end nodes increases.



§ EXTENSION TO L HOPS

In this section, we extend our two-hop age results in (<ref>), (<ref>), and (<ref>) to L hops. Considering an L-hop network, we have a single source node, n first hop receiver nodes, n^2 second hop receiver nodes and extending in this manner, n^L end (L hop) nodes. The network model for L=2 is shown in Fig. <ref> and it is generalized such that each of n nodes of the first hop is tied to n further nodes making n^2 second hop nodes and similarly, each of these n^2 second hop nodes is further connected to n nodes forming n^3 end nodes, and so on, for L hops. 

Remember that in the two-hop model, we denote the first hop link delays as X, and the second hop link delays as X̃. In this section, in order to accommodate general L hops, we change our notation so that the first hop link delay is now denoted as X^(1), the second hop link delay is now denoted as X^(2), the ℓth hop is denoted as X^(ℓ), and the last hop link delay is denoted as X^(L). For each hop ℓ, we utilize the earliest k_ℓ transmission policy such that once hop ℓ-1 receiver nodes receive an update they begin to act as hop ℓ transmitter nodes and relay the update they have received to k_ℓ of their n children nodes (see Fig. <ref>). After the packet transmission to k_ℓ children nodes are completed, hop ℓ transmitter nodes start waiting for the next update. Here, random variable Z_ℓ denotes this waiting time upon the completion of an update until the next one arrives. Thus, the interarrival time between two consecutive updates that depart from the transmitter and start service in hop ℓ is Y_ℓ = X_k_ℓ:n^(ℓ) + Z_ℓ.

Overall this L-hop network implements the earliest {k_ℓ}_ℓ=1^L transmission scheme. At each hop, we have random variable M_ℓ which is geometrically distributed with parameter p_ℓ = k_ℓ/n that represents the number of update cycles between two successive updates that arrive at a receiver in hop ℓ. The interarrival time between two consecutive updates that leave service in hop ℓ without being preempted can be written as 

    S_ℓ = ∑_i=1^M_ℓ (Y_ℓ)_i = ∑_i=1^M_ℓ (X_k_ℓ:n^(ℓ) + Z_ℓ)

A receiver node in hop ℓ immediately transmits an update it receives to its children nodes in hop ℓ+1. Therefore, the interarrival time between two consecutive successful updates that leave service in hop ℓ, S_ℓ, is equal to the interarrival time between two consecutive updates that arrive in hop ℓ+1, R_ℓ+1. We have R_ℓ+1 = S_ℓ. 

The last hop in this L-hop network can be seen as an application of our building block problem. In the building block problem, there is a source node and an end node. When this is applied to the last hop of the L-hop network, the source node is an arbitrary receiver node in hop L-1, and the end node is an arbitrary receiver node in hop L. Interarrival time of updates that arrive exogenously at the source node in the building block problem, R, is now R = S_L-1, and the interarrival time between successful updates that arrive at the end node in the building block problem, S, is now S = S_L. In addition, we know that S_L = ∑_i=1^M_L (Y_L)_i. Finally, the service time in the building block problem, X̅, is now X̅= ∑_ℓ=1^L X̅_ℓ, where X̅_ℓ is the service time at each hop. We know that for an update packet to reach the end nodes, it has to be among the earliest k_1, …, k_L nodes in all hops. Thus, ∑_ℓ=1^L X̅_ℓ term captures the expected time spent in the system for a successful update without being preemopted until it reaches one of the end nodes. The average age of an end node for an L-hop system is given in the following theorem.

 
For the general L-hop network with the earliest {k_ℓ}_ℓ=1^L stopping scheme, the average age at an individual end node at hop L is

    Δ_{k_ℓ}_ℓ=1^L =   ∑_ℓ=1^L 1/k_ℓ∑_i=1^k_ℓ E[X_i:n^(ℓ)] + 2n-k_L/2k_L(E[X_k_L:n^(L)] + E[Z_L]) + Var[X_k_L:n^(L)+Z_L]/2(E[X_k_L:n^(L)] + E[Z_L])



Since the last hop of the general L-hop network can be seen as a building block, we can apply (<ref>) to the setting here by inserting Y = Y_L and X̅= ∑_ℓ=1^L X̅_ℓ. Then, (<ref>) follows after similar calculations as in Theorems <ref> and <ref>.


Similar to Corollary <ref>, the age of the last hop can be upper bounded by assuming that the interarrival times at each hop are exponentially distributed. 
 
For the general L-hop network, assuming exponential interarrivals to each hop with mean E[R_ℓ], average age at an end node under {k_ℓ}_ℓ=1^L stopping scheme is given by
	
    Δ'_{k_ℓ}_ℓ=1^L =   ∑_ℓ=1^L 1/k_ℓ∑_i=1^k_ℓ E[X_i:n^(ℓ)] +
    	2n-k_L/2k_L∑_ℓ=1^L E[X_k_ℓ:n^(ℓ)]∏_i=ℓ^L-1E[M_i]  
       + Var[X_k_L:n^(L)] + (∑_ℓ=1^L-1 E[X_k_ℓ:n^(ℓ)]∏_i=ℓ^L-1E[M_i])^2/2(∑_ℓ=1^L E[X_k_ℓ:n^(ℓ)]∏_i=ℓ^L-1E[M_i])



Using Lemma <ref>, (<ref>) can be upper bounded with exponential interarrivals to the nodes at hop L-1, where mean interarrival time is E[R_L] = E[S_L-1]. When the interarrivals are exponentially distributed, we have Z_L = S_L-1 and therefore, E[Z_L] = E[S_L-1]. In addition, with exponential interarrivals, Z_L is independent of X_k_L:n. Then, we have Var[X_k_L:n^(L)+Z_L] = Var[X_k_L:n^(L)]+Var[Z_L], where Var[Z_L] = E[S_L-1]^2. Now, the upper bound for (<ref>) can be written as

    Δ'_{k_ℓ}_ℓ=1^L =   ∑_ℓ=1^L 1/k_ℓ∑_i=1^k_ℓ E[X_i:n^(ℓ)] + 2n-k_L/2k_L(E[X_k_L:n^(L)] + E[S_L-1]) + Var[X_k_L:n^(L)]+E[S_L-1]^2/2(E[X_k_L:n^(L)] + E[S_L-1]).


Now, let us calculate E[S_L-1]. We can write S_L-1 as

    S_L-1 =  ∑_i=1^M_L-1 (Y_L-1)_i = ∑_i=1^M_L-1 (X_k_L-1:n^(L-1)+ Z_L-1)_i

where Y_L-1 is the interarrival time between updates that start service in hop L-1. Then,

    E[Z_L] = E[S_L-1] = E[M_L-1]E[X_k_L-1:n^(L-1)]+E[M_L-1]E[Z_L-1].

Similarly, E[Z_L-1] can be written in terms of the variables in hop L-2. We continue with this recursive calculation until the second hop, where we have E[Z_2] = E[M_1]E[X_k_1:n^(1)]. As a result, we have

    E[S_L-1] =    E[M_L-1]E[X_k_L-1:n^(L-1)] + ⋯ + E[M_L-1]E[M_L-2]⋯ E[M_2]E[M_1]E[X_k_1:n^(1)] 
    
    =    ∑_ℓ=1^L-1 E[X_k_ℓ:n^(ℓ)]∏_i=ℓ^L-1E[M_i]
 
Adding E[X_k_L-1:n^L-1] to (<ref>), we have

    E[X_k_L-1:n^L-1] + E[S_L-1] = ∑_ℓ=1^L E[X_k_ℓ:n^(ℓ)]∏_i=ℓ^L-1E[M_i].
 
Finally, by inserting (<ref>) and (<ref>) into (<ref>), we obtain (<ref>).


Corollary <ref> introduces an upper bound for average age of an update that is generated at the source node and delivered to any one of the end nodes in hop L. Note that the total number of nodes in the L-hop network is ∑_ℓ=0^L n^l. The result of Corollary <ref> holds for any n. Next, we characterize the effect of increasing n on the scaling of average age.


	Assume n is large and n>k_ℓ and let k_ℓ = α_ℓ n for ℓ=1,…, L. Under exponential interarrival assumption to each hop with mean E[R_ℓ], and shifted exponential service times X^(ℓ) with (λ_ℓ, c_ℓ), the average age for the earliest {k_ℓ}_ℓ=1^L scheme can be approximated as
	
    Δ'_{k_ℓ}_ℓ=1^L≈   ∑_ℓ=1^L ( c_ℓ + 1/λ_ℓ + 1-α_ℓ/α_ℓλ_ℓlog (1-α_ℓ) ) + 2-α_L/2α_L∑_ℓ=1^L [   ( c_ℓ - 1/λ_ℓlog (1-α_ℓ) )  ∏_i=ℓ^L-11/α_i] 
       + (  ∑_ℓ=1^L-1[   ( c_ℓ - 1/λ_ℓlog (1-α_ℓ) )  ∏_i=ℓ^L-11/α_i]  )^2/2∑_ℓ=1^L [   ( c_ℓ - 1/λ_ℓlog (1-α_ℓ) )  ∏_i=ℓ^L-11/α_i]
	

The proof of this corrollary is similar to that of Corrollaries <ref> and <ref>. We use the first and second moments of order statistics of shifted exponential random variables and make necessary approximations for large n.

In conclusion, under the assumption that middle nodes receive update packets with exponential interarrivals with means equal to E[R_ℓ], the average age attained at the end nodes depends on n only through ratios α_ℓ. Thus, this result together with Lemma <ref> imply that the average age of an end node in an L-hop multicast network implementing the earliest {k_ℓ} transmission scheme is bounded by a constant as n increases.




§ NUMERICAL RESULTS
 



In this section, we provide simple numerical results. In order to optimize the age, we need to select appropriate k_i values, i.e., optimum ratios α_i^*, at each hop. From <cit.>, we know that in the single-hop multicast network α^* is 0.732 when link delays are shifted exponential with parameters (λ,c) = (1,1). For the two-hop network with (λ,c) = (λ̃, c̃) = (1,1), we obtain α_1^* = 0.615 and α_2^* = 0.921. This shows that when all link delays are statistically identical, to achieve a good age performance, we need to be more aggressive in the second hop than the first hop (see <cit.>). 

 When we add a third hop, we see that the optimal threshold results follow similar trends. Let us denote the link delay parameters of the third hop as (λ̃̃̃, c̃̃̃) for tractability. When all link delays are statistically identical, i.e., shifted exponentials with parameters (1,1), we have α_1^* = 0.626, α_2^* = 0.832 and α_3^* = 0.965. In a similar fashion, when we add a fourth hop, we have  α_1^* = 0.635, α_2^* = 0.837, α_3^* = 0.901 and α_4^* = 0.935. Thus, the observation we have made for two-hop multicast networks, i.e., that we need to be more agressive in the further hops to achieve a lower average age holds true for four-hop multicast networks as well. These results are summarized in Table <ref>.






Returning to the two-hop network, we observe that α_2 is responsive to the changes in the parameters of the first hop. This is intuitive because as k_1 varies, the mean interarrival time for the second hop changes. In Figs. <ref>(a) and <ref>(b), we plot the age as a function of k_2 (equivalently α_2) for a fixed set of second hop parameters and for a fixed set of first hop parameters, respectively. As shown in Fig. <ref>(a), for the same (λ̃, c̃) pair, when the mean interarrival time gets lower by increasing λ, α_2^* gets lower as well. Knowing that the next update arrival is not far away, middle nodes tend to wait for the next one instead of sending the current packet to more and more end users when the arrivals are frequent. This is exactly what we have observed in the building block problem with exogenous update arrivals. 





In Fig. <ref>(b) we observe that as the service rate of the second hop, λ̃, increases for a given λ, α_2^* also increases. This is intuitive because when λ is fixed the interarrival time to the middle nodes stays constant as opposed to their increasing service rate. Thus, they relay their current packet to more and more end nodes. 

In Figs. <ref>(a) and <ref>(b), we plot the age as a function of k_1 (equivalently α_1) when the second hop parameters are fixed and when the first hop parameters are fixed, respectively. In Fig. <ref>(a), α_1^* shows a similar trend as in α_2^* in Fig. <ref>(b) but α_1^* experiences bigger changes as λ increases. Fig. <ref>(b) shows the response of α_1^* to changes in λ̃ when λ is fixed. Here, we observe rather minor reaction from α_1^* when the service performance of the second stage varies. 

In Fig. <ref> we repeat the numerical analysis in Fig. <ref> when the link delays are exponential, i.e., shift parameters c = 0 and c̃ = 0. We observe similar trends for k_2^* as in Fig. <ref>. The only difference is now that the link delays are all exponential, we get k_1^* = 1 for all cases. This is also observed in <cit.> and in the building block problem when μ tends to ∞ and is because of the memoryless property of the exponential distribution.  





In Fig. <ref> we analyze the effects of the link delay parameters λ and λ̃ on Δ'_(k_1,k_2). In both cases we see that larger service rates (large λ and λ̃), i.e., lower link delays, lead to smaller average age at the end nodes. 

In Fig. <ref> we plot the three-hop version of Fig. <ref>. As shown in Fig. <ref>, when the mean interarrival time decreases at the third hop through a service rate increase in either one of the first two hops α_3^* gets smaller. One other observation from Fig. <ref> is the fact that although we change λ values in Fig. <ref>(a) and λ̃ values in Fig. <ref>(b), their effects on the third hop are quite similar. In either case we observe a similar trend, i.e., k_3 value decreases as λ or λ̃ increases.



§ APPENDIX: PROOF OF LEMMA <REF>
 
In this section, we prove Lemma <ref>, first, for the two-hop scenario, then we extend the proof to the L-hop case. We use <cit.> which, for a G/G/1/1 system, requires interarrival times to have DMRL property and service times to have NBUE property. Remember that the updates that depart the service at the first hop, S_1 are considered to be the arrivals at the second hop, R_2. Then, between a transmitter and a receiver at the second hop, we have interarrivals R_2 = ∑_i=1^M_1 (X_k_1:n)_i and service times X̃_k_2:n. In order to employ <cit.>, we need to show that R_2 has DMRL property and X̃_k_2:n has NBUE property. It is sufficient to show that both R_2 and X̃_k_2:n have log-concave density, since log-concavity implies both DMRL and NBUE properties <cit.>.

It is given in <cit.> that the order statistics of i.i.d. log-concave random variables is log-concave as well. Since shifted exponential has a log-concave density, we conclude that the second hop service time X̃_k_2:n has a log-concave density.

In order to show the log-concavity of R_2, we use the fact that a function is log-concave if and only if it is a Polya Frequency function of order 2 <cit.>, which is denoted by PF_2. We know that the geometric random variable M_1 and shifted exponential random variables X_k_1:n are log-concave, and hence they have  PF_2 densities. In addition, we know that M_1 is independent of X_k_1:n. Now, we can apply <cit.> that states that if  X_k_1:n and  M_1 have PF_k densities, and M_1 is independent of X_k_1:n, then R_2 = ∑_i=1^M_1 (X_k_1:n)_i has a PF_k density as well. Since <cit.> is stated for any k, it holds for k=2, and we conclude that R_2 has a PF_2 density, which, in turm, means that R_2 is log-concave.

We have proved that interarrivals to the second hop are DMRL and service time of the second hop is NBUE. Hence, using <cit.> average age of the second hop is upper bounded by a system where interarrivals are exponential with E[R_2]. In the third hop, service times are i.i.d. with the service times at the second hop. Therefore, service time of the third hop is NBUE as well. The interarrivals at the third hop are now R_3 = ∑_i=1^M_2 (X_k_2:n + Z_2)_i. In order to calculate the upper bound in the second hop, we have already assumed that the interarrivals, R_2, are exponential which resulted in Z_2 = R_2 to be exponential as well. Then, R_3 can be shown to be log-concave using similar ideas above and for exponential Z_2. This reasoning holds for each hop in an L-hop system, which proves the applicability of Lemma <ref> to an L-hop system as well. 



§ CONCLUSIONS
 
We studied the age of information in a multihop multicast network with a single source updating n^L end nodes where L denotes the number of hops. We showed that when the earliest k_ℓ transmission policy is implemented at each hop ℓ, the age of information at the end nodes can be upper bounded by a constant that is independent of n. We explicitly characterized an upper bound for an L-hop multicast network, and then determined the optimal stopping thresholds k_ℓ for arbitrary shifted exponential link delays. We note that even when the link delays are exponential we find k^*_1 =1 and k^*_ℓ > 1 in hops ℓ>1. This is because even when there is no shift in service, the random waiting time under exogenous arrivals introduces a random shift to the exponential service distribution in hops ℓ>1. 


unsrt


 

