Age of Information in a Network of Preemptive Servers

I. INTRODUCTION

• Earlier studies of lossy preemptive queues considered single-hop systems, while multihop LGFS results did not facilitate explicit age calculation.The cited multihop results showed that preemptive LGFS yields smaller age processes than other causal policies when link transmission times are exponential.Source: §I · p. 1
• The paper derives a simple expression for average age at each node in a Poisson-fed multihop line of preemptive LCFS servers using a stochastic hybrid systems model.Preemptive LCFS is treated as a special case of LGFS.Source: §I · p. 1
• For two servers, the paper tests whether monitor age changes when the service rates—and thus where dropping occurs—are reversed.The introduction poses the comparison between µ1 < µ2 and µ1 > µ2.Source: §I · p. 1

II. SYSTEM MODEL

• Updates arrive as a rate-λ Poisson process and pass through exponential-service ·/M/1/1 preemptive servers, where new arrivals discard updates in service.The model has no queueing; it is useful when head-of-line time is dominated by waiting for transmission.Source: §II · p. 1
• The status age is elapsed time since generation of the most recently delivered update; discarded updates have infinite delivery time.Average age is the long-run expected instantaneous age.Source: §II · p. 2
• Multihop analysis is difficult because preemption makes the network lossy, complicates the effective monitor arrival rate, and leaves node departures nonmemoryless.Updates reaching the monitor may also have survivor bias because they avoided preemption.Source: §II · p. 2
• Downstream arrivals are aged by prior nodes, and their ages may be correlated with both earlier service times and interarrival times.Source: §II · p. 2

III. STOCHASTIC HYBRID SYSTEMS FOR AOI

• The SHS pairs a discrete Markov state q(t) with a continuous vector x(t) that tracks age-related processes.For AoI, the paper uses a simplified SHS in which x(t) evolves piecewise linearly.Source: §III · p. 2
• Each transition has a rate and a reset map for x, while x evolves at a state-dependent rate between transitions.Binary reset maps and growth-rate vectors specify which age components are tracked and updated.Source: §III · p. 2
• For an ergodic discrete-state chain, the method computes stationary state probabilities and age-state correlations to obtain average age when the associated differential equation is stable.The stationary average age is the sum of the monitor-age components of the limiting correlation vector.Source: §III · p. 3

IV. AGE IN THE TANDEM QUEUE WITH PREEMPTION

• The four discrete states encode which of the two nodes is serving an update, and the continuous state tracks monitor age and the ages of in-service updates.An idle node’s age component is irrelevant and set to zero.Source: §IV · p. 3
• Transitions represent fresh arrivals, preemptions, and service completions; their reset maps update the age components as updates move through the two nodes.Table I lists the transition pairs, rates, and reset mappings.Source: §IV · p. 3, Table I · p. 3
• For two preemptive servers, monitor age is insensitive to server ordering, with each node contributing 1/µi to the total.Tracking every node’s state requires solving (n + 1)2^n equations; the following section reduces this to n + 1 equations for n nodes.Source: §IV · p. 4

• A departing update leaves a same-timestamp fake update that can be preempted without delaying real arrivals, yielding a singleton-state Markov chain.If a fake update departs, it has the same age as the update it would preempt at the next node.Source: §V · pp. 4–5
• The paper extends the fake-updates approach used for a single LCFS-S queue in to analyze the n-node line network.Source: §V · p. 4
• Theorem 2 derives the monitor’s average age for Poisson arrivals at rate λ through n LCFS-S servers with service rates µ1, . . . , µn.Source: §V · p. 5

VI. NUMERICAL EXPERIMENTS

• The experiments examine instantaneous ages for three nodes using 50-arrival sample paths and running averages from 10 paths of 200 Poisson arrivals.The running-average paths use λ = 1 and service rates µ1 = 1, µ2 = 0.5, and µ3 = 0.25.Source: §VI · pp. 5–6, Figure 4 · p. 6
• For service rates [1, 0.5, 0.25], occasional updates pass quickly through the network and reset monitor age to a relatively low value.The authors describe this as evidence of survivor bias in the representative sample paths.Source: §VI · p. 5, Figure 4 · p. 6
• Thinning updates through successive preemptive servers is associated with larger age fluctuations at downstream nodes.The experiments also report increasing variation and apparently slower convergence of running-average age at successive servers.Source: §VI · pp. 5–6
• With service rates [0.25, 0.5, 1], most updates are dropped at node 1, and downstream age paths mostly mimic node 1 with a small lag.This sample path shows no evidence of survivor bias.Source: §VI · p. 5, Figure 5 · p. 6
• Running-average age paths cluster around ages 2, 4, and 8 for nodes 1, 2, and 3, respectively.The plotted bundles are reported as consistent with the expected conclusion.Source: §VI · p. 6

VII. CONCLUSIONS

• The stochastic hybrid systems approach analyzes age in an n-node line network of exponential servers and can extend to other finite-CTMC queues and simple networks.The broader applicability is illustrated by the paper’s two-node example.Source: §VII · p. 6
• Figure 6’s running-average sample paths cluster around ages 2, 4, and 8, supporting Theorem 2.The plotted configuration has λ = 1 and service rates µ1 = 1, µ2 = 0.5, and µ3 = 0.25.Source: Figure 6 · p. 6
• For memoryless preemptive servers, fake updates can greatly simplify age computation, but the method appears useful only with preemption in service.With preemption in waiting, the state must distinguish busy servers and real from fake updates, and can grow exponentially with network size.Source: §VII · p. 6