Source-linked AI summary
The Age of Information in Multihop Networks
Ahmed M. Bedewy, Yin Sun, Ness B. Shroff
TL;DR
The paper studies age minimization in multihop queueing networks, an important open question for networks such as IoT and intelligent transportation systems. It develops scheduling policies proven to be (near) age-optimal in a stochastic ordering sense, including settings with arbitrarily distributed transmission times among work-conserving policies.
Problem
Age minimization in multihop queueing networks, including IoT and intelligent transportation systems, remains an important open question.
Method
The paper studies age minimization and develops scheduling policies for multihop networks, including policies evaluated among work-conserving policies.
Results
The developed policies are proven to be (near) age-optimal in a stochastic ordering sense, including arbitrary transmission-time distributions among work-conserving policies.
Takeaways & Limitations
The results identify scheduling policies that can minimize or nearly minimize age across multihop-network settings covered by the paper.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper studies information freshness in multihop networks motivated by real-time updates, and models packet dissemination through multihop queueing systems. It focuses on age minimization under broad arrival and transmission assumptions.
- Motivation and model: Age measures the time elapsed since the freshest packet at a destination was generated.It is defined as ∆(t) = t − U(t), where U(t) is the generation time of the freshest received update.
- Motivation and model: Real-time updates are important in IoT, intelligent transportation, sensor, Internet, cloud, and social-network applications.Examples include sharing traffic and road information, reporting emergencies, and maintaining channel-state information.
- Motivation and model: The paper investigates information updates over multihop networks modeled as multihop queueing systems.Packets originate at an external source and spread through one or multiple gateway nodes.
- Research gap: Age-optimal scheduling in multihop networks remains an important open question despite prior single-hop results for LCFS-type policies.The paper develops low-complexity policies aimed at achieving near age-optimal performance in this setting.
- Motivation and model: The model permits arbitrary packet generation and gateway-arrival times, with independent transmission times that may differ across links.These assumptions accommodate applications whose arrivals are not necessarily Poisson.
A. Our Contributions
The paper establishes stochastic age-optimality or near-optimality for LGFS policies under different preemption and transmission-time regimes. These results cover broad arrival conditions and general age-process functionals.
- Main results: With preemption and exponential transmission times, preemptive LGFS minimizes age processes at all nodes among causal policies.The guarantee is in the sense of stochastic ordering.
- Main results: Preemptive LGFS minimizes any non-decreasing functional of the age processes at all network nodes in stochastic ordering.This class includes metrics such as time-average age, average peak age, and nonlinear age functions.
- Scope and limitation: Preemptive LGFS can be very far from optimum for some non-exponential transmission-time distributions, whereas non-preemptive LGFS performs near optimally in the reported numerical result.Thus, exponential-time optimality does not extend universally to non-exponential settings when preemption is allowed.
- Main results: For NBU transmission-time distributions, non-preemptive LGFS is within a constant age gap of optimum average age.The gap is independent of packet generation times, arrival times, and buffer sizes.
- Main results: For arbitrary transmission-time distributions without preemption, non-preemptive LGFS minimizes age processes among work-conserving policies.This stochastic-ordering result also permits heterogeneous transmission-time distributions across links.
- Scope and limitation: The results are presented as among the first optimal multihop age results with arbitrary packet generation and arrival times.The paper also restricts the considered topology so that each node has one incoming link in the NBU analysis.
II. RELATED WORK
Prior work studied age in single-hop systems, selected multihop topologies, and specialized arrival or service models. This paper complements those analyses by proving policy optimality in multihop networks.
- Multihop studies: Prior multihop studies analyzed specific topologies, energy-harvesting sources, congestion control, or Poisson arrivals with exponential service.Examples include line and star networks and two-hop systems.
- Related objectives: Earlier research optimized or characterized age under energy constraints, sampling decisions, queueing disciplines, and service distributions.These studies include FCFS and LCFS systems and average-age or age-distribution analyses.
- Relationship to prior work: This paper complements prior analyses by proving age-optimality for preemptive LCFS in multihop networks while not characterizing the achieved optimal age.Earlier work evaluated optimal age quantities that this paper leaves uncharacterized.
- Multihop studies: Related work also considered time-slotted multihop systems, multiple flows, general interference, or active-source scenarios.Those models differ from the continuous-time single-flow setting considered here.
A. Notations and Definitions
This section defines stochastic ordering for random variables, random vectors, and stochastic processes. These definitions formalize the paper’s comparisons of age performance.
- Notation: Conditional notation [Z|A] denotes a random variable with the conditional distribution of Z given A, while E[Z|A] denotes conditional expectation.These notations support the probabilistic arguments that follow.
- Notation: Vector inequality x ≤ y means that each corresponding component satisfies x_i ≤ y_i.This componentwise relation is used to define upper subsets of R^n.
- Stochastic ordering: Univariate stochastic ordering compares two random variables through their ordering under increasing threshold events.The supplied passage introduces the definition but does not include its full inequality.
- Stochastic ordering: Multivariate stochastic ordering compares random vectors using probabilities of all upper sets.For an upper set U, the ordering is expressed through P{X ∈ U} ≤ P{Y ∈ U}.
- Stochastic ordering: A stochastic process is smaller when every finite vector of observations is smaller under multivariate stochastic ordering.The comparison applies to arbitrary finite choices of ordered time points.
B. Network Model
The network is a directed multihop graph with a gateway node that distributes timestamped update packets across simultaneously active links. Packet generation and gateway-arrival sequences may be arbitrary, and links may use varied transmission-time distributions and topologies.
- The network is modeled as a directed graph G(V, L) with N nodes, indexed from gateway node 0 through node N−1.
- The study considers arbitrary and structured network settings, including general topologies, one-incoming-link topologies, exponential, NBU, and arbitrary transmission-time distributions.The one-incoming-link topology extends tandem queues; a single-gateway presentation also applies to multiple gateways.
- Packets are generated externally, forwarded to gateway node 0, and then dispersed through the network to other nodes.Packet l has generation time s_l, gateway-arrival time a_l0, and delivery time a_lj.
- Generation and gateway-arrival times are arbitrary, so packets can reach node 0 out of generation order.A later-generated packet may arrive earlier than an earlier-generated packet.
- Each packet is timestamped with its generation time, becomes available on outgoing links upon arrival, and is stored in link queues that may have finite, infinite, or zero capacity.Packets arriving at full finite buffers may be dropped or replace another queued packet.
C. Scheduling Policy
Scheduling policies determine packet assignment, preemption, and work conservation using causal system information. The model distinguishes preemptive from non-preemptive service and allows packet dropping or replacement when buffers are full.
- When a finite queue is full, arriving packets may be dropped or replace packets already in the queue.
- Packet generation and gateway-arrival times do not depend on scheduling, whereas downstream arrival times do depend on the policy.Transmission-time distributions are assumed invariant across policies.
- Scheduling decisions use system history and current information, including packet locations, arrival and generation times, and server states.
- A preemptive policy may switch a link to another packet at any time, while a non-preemptive policy completes the current transmission first.Preempted packets can return to the queue when buffer space permits.
- A work-conserving policy keeps each link busy whenever packets are waiting.
D. Age Performance Metric
The paper measures information freshness through node age processes and a general non-decreasing age-penalty functional. Age grows between fresh-packet arrivals and decreases when newer information arrives.
- At node j, age is determined by the generation time of the freshest packet delivered by time t.The corresponding freshest-generation process is U_j(t)=max{s_l:a_lj≤t}.
- The age process Δ_j(t) increases linearly with time and resets to a smaller value when a fresher packet arrives.
- The paper introduces an age-penalty functional g(Δ) to represent dissatisfaction with data staleness across all network nodes.
- An age-penalty functional is non-decreasing in the age vector, so larger ages cannot reduce the penalty.
- The framework includes time-average age, average peak age, non-linear age functions, and single-node functionals as special cases.Non-linear functions may use any non-negative, non-decreasing function h.
IV. MAIN RESULTS
The paper develops near age-optimality results for multihop networks using stochastic-ordering arguments. Its main-results section introduces the preemptive LGFS policy and its freshest-packet service rule.
- The section presents the paper’s near age-optimality results for multihop networks.
- The results are established using stochastic-ordering methods.
- Preemptive LGFS assigns a newly arrived packet priority based on its fresher generation time and preempts the packet currently being transmitted.
- If preemption occurs, the interrupted packet is stored back in the queue for possible later transmission.
- When a packet is delivered and the queue is nonempty, the freshest queued packet is sent next.
A. Exponential Transmission Times, Preemption is Allowed
Under exponential transmission times with preemption allowed, preemptive LGFS is age-optimal among causal policies, minimizing age processes and non-decreasing age functionals.
- A. Exponential Transmission Times, Preemption is Allowed: Any non-decreasing age penalty functional is minimized, including time-average, average peak, and nonlinear age functions.
- A. Exponential Transmission Times, Preemption is Allowed: The proof couples policies so packet departure processes match, then uses forward induction over delivery and arrival events.
- A. Exponential Transmission Times, Preemption is Allowed: Preemptive LGFS is age-optimal among all causal policies under exponential transmission times.Transmission times are independent across links and i.i.d. across time.
Appendix A.
The exponential-case optimality extends to arbitrary packet generation and arrival processes, heterogeneous gateway arrivals, multiple gateways, and arbitrary buffer sizes.
- Appendix A.: Preemptive LGFS achieves optimality for arbitrary packet generation times, arrival times, network topology, and buffer sizes.
- Appendix A.: The optimality statement covers any non-decreasing age penalty functional, including time-average, average peak, and nonlinear functions.
- Appendix A.: The result extends to multiple gateways, whose arrival processes may be heterogeneous and policy-independent.
B. New-Better-than-Used Transmission Times, Preemption is Allowed
For NBU transmission times with preemption allowed, non-preemptive LGFS is within a constant gap of optimum average age on restricted multihop topologies; without preemption, it is age-optimal for arbitrary transmission distributions under work conservation.
- B. New-Better-than-Used Transmission Times, Preemption is Allowed: Non-preemptive LGFS sends the freshest queued packet and replaces the oldest packet when a full link buffer receives a fresher packet.
- B. New-Better-than-Used Transmission Times, Preemption is Allowed: The NBU near-optimality result is proved for networks where each node has one incoming link.The restriction avoids multiple-path arrivals whose fastest path can differ across packets.
- B. New-Better-than-Used Transmission Times, Preemption is Allowed: Non-preemptive LGFS is within a constant age gap of optimum average age for NBU transmission times.The result assumes independent links, i.i.d. transmission times across time, arbitrary packet generation and arrival sequences, and positive buffer sizes.
- C. General Transmission Times, Preemption is Not Allowed: The results also extend to multiple-gateway models and arbitrary buffer sizes.
- C. General Transmission Times, Preemption is Not Allowed: Without preemption, non-preemptive LGFS minimizes age processes among work-conserving policies for arbitrary link transmission distributions.The result allows independent links and i.i.d. transmission times across time, including distributions that differ between links.
V. NUMERICAL RESULTS
The numerical results validate the paper’s theoretical conclusions across exponential, gamma, and general transmission-time settings. Preemptive LGFS performs best in the exponential case, while non-preemptive LGFS is strongest for general distributions and preemptive LGFS can perform poorly for some gamma shapes.
- Exponential transmission times: Preemptive LGFS age performance is unaffected by buffer size because fresh packets can begin service immediately while queues store older packets.This yields the same performance for different buffer sizes.
- Gamma transmission times: When gamma transmission times have shape parameter β = 1, preemptive LGFS achieves the best age performance among the plotted policies.Here the gamma distribution is exponential, matching the setting of Theorem 1.
- General transmission times: For general transmission-time distributions, non-preemptive LGFS achieves the best age performance among the plotted policies.This agrees with Theorem 3, including heterogeneous transmission-time distributions across links and out-of-order arrivals.
- General transmission times: The numerical study supports the conclusion that non-preemptive LGFS minimizes age among non-preemptive work-conserving policies, while FCFS can suffer high age under congestion.With a unit buffer, FCFS remains finite at high traffic intensity because fresh packets have better delivery opportunities.