We consider the average age of information in G/G/1/1 systems under two service discipline models. In the first model, if a new update arrives when the service is busy, it is blocked; in the second model, a new update preempts the current update in service. For the blocking model, we first derive an exact age expression for G/G/1/1 systems. Then, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. We observe that deterministic interarrivals minimize the average age of G/M/1/1 systems for a given mean interarrival time. Next, for the preemption in service model, we first derive an exact average age expression for G/G/1/1 systems. Then, similar to blocking discipline, using the age expression for G/G/1/1 systems, we calculate average age expressions for special cases, i.e., M/G/1/1 and G/M/1/1 systems. Average age for G/M/1/1 can be written as a summation of two terms, the first of which depends only on the first and second moments of interarrival times and the second of which depends only on the service rate. In other words, interarrival and service times are decoupled. We prove that deterministic interarrivals are optimum for G/M/1/1 systems for a given mean interarrival time. On the other hand, we observe for non-exponential service times that the optimal distribution of interarrival times depends on the relative values of the mean interarrival time and the mean service time. Finally, we propose a simple to calculate upper bound to the average age for the preemption in service discipline.

J-8

Scaling Laws for Age of Information in Wireless Networks

We study age of information in a multiple source-multiple destination setting with a focus on its scaling in large wireless networks. There are \(n\) nodes uniformly and independently distributed on a fixed area that are randomly paired with each other to form \(n\) source-destination (S-D) pairs. Each source node wants to keep its destination node as up-to-date as possible. To accommodate successful communication between all \(n\) S-D pairs, we first propose a three-phase transmission scheme which utilizes local cooperation between the nodes along with what we call mega update packets to serve multiple S-D pairs at once. We show that under the proposed scheme average age of an S-D pair scales as \( O(n^{\frac{1}{4}} \log n) \) as the number of users, \(n\), in the network grows. Next, we observe that communications that take place in Phases I and III of the proposed scheme are scaled-down versions of network-level communications. With this along with scale-invariance of the system, we introduce hierarchy to improve this scaling result and show that when hierarchical cooperation between users is utilized, an average age scaling of \( O(n^{\alpha(h)} \log n) \) per-user is achievable, where \(h\) denotes the number of hierarchy levels and \( \alpha(h) = \frac{1}{3·2^h + 1} \). We note that \( \alpha (h) \) tends to \(0\) as \(h\) increases, and asymptotically, the average age scaling of the proposed hierarchical scheme is \( O(\log n) \). To the best of our knowledge, this is the best average age scaling result in a status update system with multiple S-D pairs.

C-20

Age of Information Scaling in Large Networks with Hierarchical Cooperation

Baturalp Buyukates, Alkan Soysal, and Sennur. Ulukus

In IEEE Global Communications Conference (Globecom), Dec 2019

We consider the age of information in a multihop multicast network where there is a single source node sending timesensitive 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 \(\ell\) is connected to \(n\) further receiver nodes in hop \(\ell + 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_1\) stopping value for each hop \(\ell\) for arbitrary shifted exponential link delays.