Source-linked AI summary
Age-Optimal Information Updates in Multihop Networks
Ahmed M. Bedewy, Yin Sun, Ness B. Shroff
TL;DR
The paper asks how to minimize information age in general multihop networks, extending prior single-hop work. It analyzes LGFS scheduling under exponential and arbitrary transmission-time distributions, proving stochastic age-optimality across all nodes under the corresponding policy classes. The results cover arbitrary topologies, packet generation and arrival times, buffer sizes, and non-decreasing age functionals.
Problem
The paper addresses age-of-information minimization in general multihop networks, where scheduling decisions across hops interact and prior work largely focused on single-hop settings.
Method
The paper models a directed multihop network and compares preemptive or non-preemptive LGFS policies within causal or non-preemptive work-conserving policy classes.
Results
Preemptive LGFS is stochastically age-optimal for exponential link transmission times, while non-preemptive LGFS is optimal among non-preemptive work-conserving policies for arbitrary distributions.
Takeaways & Limitations
Age-optimality holds jointly at all network nodes and extends to any non-decreasing functional of the age processes under broad network and arrival settings.
Abstract
from arXiv · showhide
The problem of reducing the age-of-information has been extensively studied in the single-hop networks. In this paper, we minimize the age-of-information in general multihop networks. If the packet transmission times over the network links are exponentially distributed, we prove that a preemptive Last Generated First Served (LGFS) policy results in smaller age processes at all nodes of the network (in a stochastic ordering sense) than any other causal policy. In addition, for arbitrary general distributions of packet transmission times, the non-preemptive LGFS policy is shown to minimize the age processes at all nodes of the network among all non-preemptive work-conserving policies (again in a stochastic ordering sense). It is surprising that such simple policies can achieve optimality of the joint distribution of the age processes at all nodes even under arbitrary network topologies, as well as arbitrary packet generation and arrival times. These optimality results not only hold for the age processes, but also for any non-decreasing functional of the age processes.
I. INTRODUCTION
The paper extends age-of-information optimization from single-hop to general multihop networks. It establishes stochastic age-optimality for LGFS policies under exponential transmission times and, with non-preemptive work conservation, under arbitrary transmission-time distributions.
- Motivation: Age-of-information measures the time elapsed since the freshest update at a destination was generated.At time t, age is defined as ∆(t) = t − U(t), where U(t) is the generation time of the freshest update.
- Problem setting: The paper studies update packets dispersed through a general multihop network from an external source via a gateway node.This setting includes arbitrary network topology, packet arrivals, and queue buffer sizes.
- Main results: For exponentially distributed link transmission times, preemptive LGFS produces stochastically smaller age processes at every node than any causal policy.The result applies to arbitrary arrival processes, network topologies, and buffer sizes.
- Implications: These stochastic-ordering results extend to every non-decreasing functional of the age processes, including time-average, peak-age, and age-penalty measures.Thus, the policy guarantees apply jointly across the network rather than only to an individual node or metric.
- Main results: For arbitrary transmission-time distributions, non-preemptive LGFS minimizes all-node age processes among non-preemptive work-conserving policies.The result also permits heterogeneous transmission-time distributions across links.
B. Network Model
The paper models updates traversing a directed multihop network under causal scheduling policies and evaluates node-wise age through general non-decreasing functionals.
- Network Model: The network is a directed graph G(V, L) with N nodes, gateway node 0, link queues of buffer size B_ij, and random transmission times.
- Network Model: Packets are generated externally, forwarded first to gateway node 0, and then dispersed through the network according to a scheduling policy π.
- Network Model: Generation times and gateway arrival times are arbitrary and policy-independent, so packets may reach the gateway out of generation order.
- Scheduling Policies: Causal policies choose link transmissions using the system’s history and current state.
- Scheduling Policies: Preemptive policies may interrupt transmissions, whereas non-preemptive policies complete the current packet before sending another.
- Performance Metrics: Age at node j is based on the freshest arrived packet, and the age vector covers all network nodes over time.The paper also considers non-decreasing functionals representing dissatisfaction with stale information, including time-average age, average peak age, and average age penalty.
III. AGE-OPTIMALITY RESULTS
With exponential transmission times, preemptive LGFS is age-optimal across the multihop network, minimizing the joint age processes and every non-decreasing age functional.
- Exponential transmission times: Under exponential link transmission times, preemptive LGFS achieves age optimality among all policies in Π.The result assumes transmission times are independent across links and i.i.d. across time, with expectations existing.
- Exponential transmission times: Preemptive LGFS serves the freshest queued packet and can preempt the packet currently being transmitted when a fresher packet arrives.The preempted packet is returned to the queue, and the freshest queued packet is selected after delivery.
- Exponential transmission times: The policy minimizes the joint distribution of age processes at all network nodes within Π.The guarantee applies for arbitrary packet counts, generation and arrival times, network topology, and link buffer sizes.
- Exponential transmission times: Preemptive LGFS also minimizes every non-decreasing age penalty functional, including time-average age, average peak age, and average age penalty.The theorem states the equivalent functional inequality for all non-decreasing g, provided expectations exist.
B. General Transmission Time Distributions
For arbitrary transmission-time distributions, non-preemptive LGFS is age-optimal among non-preemptive work-conserving policies, including heterogeneous link distributions.
- General transmission time distributions: Non-preemptive LGFS minimizes age processes at all nodes among policies in Πnpwc.Πnpwc is the class of non-preemptive work-conserving policies.
- General transmission time distributions: The result holds for arbitrary general transmission-time distributions that are independent across links and i.i.d. across time.The theorem applies provided the relevant expectations exist.
- General transmission time distributions: Age-optimality remains achievable when transmission-time distributions differ from one link to another.Thus, the theorem covers heterogeneous transmission-time distributions across network links.
IV. NUMERICAL RESULTS
The numerical results compare age performance across multihop policies under exponential and heterogeneous general transmission times, including out-of-order packet arrivals. Preemptive or non-preemptive LGFS achieves the best reported age performance in the corresponding settings.
- Experimental setup: The experiments use an Erlang-2 inter-generation process with mean 1/λ and out-of-order arrivals to node 0 caused by delays of 1 or 100 with equal probability.The network is the topology shown in Fig. 3.
- Exponential transmission times: Preemptive LGFS achieves smaller average peak age at node 2 than non-preemptive LGFS, non-preemptive LCFS, and FCFS under exponential transmission times.The comparison includes buffer sizes of 1 and infinity, with mean transmission times 1 on links (0, 1) and (1, 2), and 0.5 on link (0, 2).
- Exponential transmission times: The node-2 peak-age result supports Theorem 1 for out-of-order receptions and general network topology.
- General transmission times: Non-preemptive LGFS improves age performance over non-preemptive LCFS when packets arrive to node 0 out of generation order, even with heterogeneous link distributions.FCFS with infinite buffers has average age that blows up at high traffic intensity, whereas FCFS with buffer size 1 remains finite.
V. CONCLUSION
The paper presents an initial age-of-information minimization result for general multihop networks. Its optimality claims cover broad system settings and extend from age processes to non-decreasing age functionals.
- The paper makes a first attempt to minimize age-of-information in general multihop networks.
- Age-optimality holds for arbitrary network topology, packet generation and arrival times to node 0, and queue buffer sizes.
- The optimality results apply both to age processes and to any non-decreasing functional of those processes.
APPENDIX A PROOF OF THEOREM 1
The proof of Theorem 1 compares preemptive LGFS with arbitrary causal policies through coupled state processes and forward induction. It then extends the comparison from work-conserving to all policies using the effect of transmission idling.
- System state: The system state records, at every node, the generation time of the freshest packet that has arrived there.For policy π, the state is Uπ(t) = (U0,π(t), U2,π(t), . . . , UN−1,π(t)).
- Coupling argument: The proof compares preemptive LGFS with any work-conserving policy using coupling and forward induction on their system state processes.The coupled processes preserve the respective policy distributions while matching packet deliveries across links.
- Event analysis: The induction handles packet-delivery and new-arrival events through lemmas comparing the post-event states under preemptive LGFS and a competing policy.The argument includes separate cases based on the generation times of packets delivered over a link.
- Conclusion of proof: The state-process ordering holds for all t ∈ [0, ∞), yielding the theorem's stochastic ordering for work-conserving policies.The proof derives the result from the state ordering and Theorem 6.B.30 in.
- Extension to all policies: Transmission idling postpones delivery of fresh packets, so non-work-conserving policies have greater age and are also covered by the theorem.
APPENDIX B PROOF OF THEOREM 2
Theorem 2 is proved by adapting the coupling and forward-induction argument to non-preemptive LGFS and arbitrary non-preemptive work-conserving policies. The proof compares packet deliveries and arrivals through the corresponding system states.
- Coupling argument: The proof compares non-preemptive LGFS with an arbitrary policy in Πnpwc using coupling and forward induction.The non-preemptive LGFS policy is denoted by NP in the proof.
- Proof setting: The proof uses the same system-state definition as Theorem 1 while excluding preemptive competing policies.
- Event analysis: The induction analyzes packet-delivery events by comparing the generation times and arrival times of packets sent over the same link.The argument includes cases based on the delivered packets' generation times and tracks the transmission start time.
- Conclusion of proof: The state-process comparison holds for all t ∈ [0, ∞), which implies the theorem's stochastic ordering for the non-preemptive work-conserving class.The proof invokes Theorem 6.B.30 in after establishing the state ordering.