Source-linked AI summary
Age-of-Information in the Presence of Error
Kun Chen, Longbo Huang
TL;DR
The paper addresses PAoI in an M/M/1 queue where update packets may be lost during delivery. It derives exact expressions across FCFS, LCFS, and retransmission variants, and uses analysis and simulation to show that LCFS and retransmissions address queueing delay and packet loss.
Problem
The paper examines PAoI when packet delivery is unreliable, extending prior work that largely assumes perfect delivery.
Method
The paper derives exact PAoI expressions for FCFS, LCFS with preemptive or non-preemptive priority, and retransmission with or without preemption.
Results
Analytical and simulation results show that LCFS and retransmissions can avoid PAoI increases caused by large queueing delay and packet loss.
Takeaways & Limitations
LCFS maintains low PAoI under high packet loss, while retransmissions provide significant PAoI reductions when packet loss is high.
Abstract
from arXiv · showhide
We consider the peak age-of-information (PAoI) in an M/M/1 queueing system with packet delivery error, i.e., update packets can get lost during transmissions to their destination. We focus on two types of policies, one is to adopt Last-Come-First-Served (LCFS) scheduling, and the other is to utilize retransmissions, i.e., keep transmitting the most recent packet. Both policies can effectively avoid the queueing delay of a busy channel and ensure a small PAoI. Exact PAoI expressions under both policies with different error probabilities are derived, including First-Come-First-Served (FCFS), LCFS with preemptive priority, LCFS with non-preemptive priority, Retransmission with preemptive priority, and Retransmission with non-preemptive priority. Numerical results obtained from analysis and simulation are presented to validate our results.
I. INTRODUCTION
The paper studies freshness of status updates in an M/M/1 queue when packet deliveries can fail. It derives PAoI expressions for FCFS, LCFS, and retransmission policies, emphasizing policies that address queueing delay and packet loss.
- Status updates support monitoring, transportation, and wireless-network control, but stale information can produce incorrect system estimates and severe performance loss.
- AoI measures information freshness and jointly captures update-transmission latency and delivery rate, unlike delay or throughput alone.
- Most prior work assumes perfect delivery and often uses FCFS, leaving delivery errors and losses in LCFS systems insufficiently studied.
- The paper derives exact PAoI expressions for LCFS with preemptive or non-preemptive priority and for retransmission policies with or without preemption.
- Retransmission repeatedly sends the most recent packet without feedback, trading potentially fresher updates for additional packet-state management.
- The model uses Poisson packet arrivals and exponential service times in an M/M/1 queue, with each completed packet reaching the destination independently with probability p.
III. PAOI UNDER FCFS
The FCFS analysis defines informative packets and decomposes PAoI using inter-arrival and service-related intervals. The paper then motivates LCFS and retransmission policies as alternatives to congestion and packet-loss problems.
- For FCFS, α(n) denotes the first informative packet arriving no earlier than packet n.
- The quantities X̂_n and Ŝ_n represent, respectively, the interval from n to α(n)'s arrival and the duration from n's service start to α(n)'s departure.
- Under FCFS, successfully transmitted packets are informative, so PAoI combines the expected inter-arrival time between successful packets with packet time in the system.
- FCFS can suffer large PAoI under congestion because packets spend substantial time traversing the queue.
- LCFS prioritizes later packets through preemptive or non-preemptive service, while retransmission always serves the latest information at the cost of additional state management.
IV. PAOI UNDER LCFS WITH PREEMPTIVE PRIORITY
The LCFS preemptive analysis models informative packets and derives exact probabilities and conditional service-time quantities needed for PAoI.
- IV. PAOI UNDER LCFS WITH PREEMPTIVE PRIORITY: Under LCFS with preemptive priority, packets begin service immediately upon arrival, and informative packets determine PAoI inter-departure intervals.A packet is informative when it contributes to the sequence of successfully delivered updates.
- IV. PAOI UNDER LCFS WITH PREEMPTIVE PRIORITY: The analysis introduces ˜p as the probability that some packet successfully reaches the destination during a packet’s service process.This includes the packet itself and packets arriving before its departure.
- IV. PAOI UNDER LCFS WITH PREEMPTIVE PRIORITY: The derivation uses memorylessness of exponential arrivals and services to obtain recursive expressions for ˜p and related conditional durations.The recursion distinguishes whether later packets complete service successfully before the current service process ends.
- IV. PAOI UNDER LCFS WITH PREEMPTIVE PRIORITY: The probability that a packet is informative and its conditional expected service time are computed explicitly.The supplied expressions give P(n ∈Ψ) and E{Sn|n ∈Ψ} in terms of λ, µ, p, and ˜p.
B. Computing PAoI
PAoI is computed by decomposing each informative update interval into the informative packet’s service time and the subsequent inter-departure duration.
- B. Computing PAoI: PAoI is expressed as E{Sni|ni ∈Ψ} + E{Ŷni}, combining informative-packet service and the next informative departure interval.This decomposition separates the packet’s own service contribution from the time until the next informative packet departs.
- B. Computing PAoI: The expected delay until the next informative packet begins with the mean interarrival time 1/λ.Subsequent duration depends on whether the next packet’s service process completes successfully or requires further progression.
- B. Computing PAoI: The resulting LCFS preemptive PAoI expression combines the conditional service-time term with the derived inter-departure contribution.The expression is parameterized by λ, µ, p, and ˜p.
- B. Computing PAoI: When p = 1, the packet-loss model reduces to the perfect-delivery special case stated in the derivation.The corresponding expression is given immediately after the general result.
V. PAOI UNDER LCFS WITH NON-PREEMPTIVE PRIORITY
The LCFS non-preemptive analysis accounts for packets that arrive during service but cannot interrupt the packet currently being served.
- V. PAOI UNDER LCFS WITH NON-PREEMPTIVE PRIORITY: Under non-preemptive LCFS, a newly arriving packet waits when the server is busy and cannot interrupt the current service.This differs from the preemptive case, where packets begin service immediately upon arrival.
- V. PAOI UNDER LCFS WITH NON-PREEMPTIVE PRIORITY: The analysis defines γ(n) as the first informative packet arriving after n starts service and Ẑn as its departure time relative to u(n).These variables describe the interval used to compute PAoI in the non-preemptive case.
- V. PAOI UNDER LCFS WITH NON-PREEMPTIVE PRIORITY: Packets arriving after ni arrives but before ni starts service are served before ni and are lost upon departure when ni is informative.Thus, waiting packets affect which update becomes informative.
A. Analyzing a Service Process
The non-preemptive service-process analysis characterizes arrivals during service and derives recursive equations for the probability of successful informative delivery.
- A. Analyzing a Service Process: The process ¯Sn runs from u(n) until the server becomes free or serves a packet that arrived no later than u(n).Its distribution is determined by arrivals and services after u(n), independently of the earlier system state.
- A. Analyzing a Service Process: The number of arrivals during service is geometrically distributed with parameter λ/(λ+µ), and the conditional service duration is (k+1)/(λ+µ).These quantities support the subsequent recursive service-process calculation.
- A. Analyzing a Service Process: The recursion propagates through packets served after n, distinguishing successful packets from packets requiring further service-process analysis.This determines whether the next informative packet completes within the relevant interval.
- A. Analyzing a Service Process: The probability ˜p satisfies λ(1−p)˜p^2 + (µ−λ+2λp)˜p −λp = 0.Solving this quadratic yields the probability used in the non-preemptive service-process analysis.
- A. Analyzing a Service Process: The derived relation (1−˜p)˜s = [1−˜p]/[λ+µ−2λ(1−p)(1−˜p)] determines the auxiliary duration parameter ˜s.This relation follows after solving the preceding service-process equations.
B. Computing PAoI
The section computes PAoI by characterizing waiting and service-related processes in the LCFS queue, then combining them into exact expressions. The resulting formula remains non-trivial even with perfect delivery.
- B. Computing PAoI: The queue state at arrival and service completion determines waiting and post-service components in the PAoI calculation.The analysis tracks π(a(n)), π(u(n)), and conditional residual-time processes to characterize these components.
- B. Computing PAoI: The analysis defines conditional residual-time quantities z_k for packets observing k packets at service completion.These quantities are obtained recursively from the service process and its arrival-dependent transitions.
- B. Computing PAoI: The resulting expressions combine queueing, transmission-error, and service-process terms to compute PAoI.The expressions use τ and ˜p together with the derived conditional expectations.
- B. Computing PAoI: Even when p = 1, the LCFS solution remains non-trivial.The paper explicitly notes that perfect delivery does not reduce the expression to a trivial form.
VI. PAOI UNDER RETRANSMISSION WITH PREEMPTIVE PRIORITY
This section analyzes retransmission with preemptive priority, where packets are repeatedly transmitted until successful delivery or preemption. Because newer arrivals preempt older packets, the policy effectively stores only the latest packet.
- VI. PAOI UNDER RETRANSMISSION WITH PREEMPTIVE PRIORITY: A packet is retransmitted until it reaches the destination successfully or is preempted.The analysis treats successful transmission and preemption as the relevant departure events.
- VI. PAOI UNDER RETRANSMISSION WITH PREEMPTIVE PRIORITY: The policy can be viewed as storing only the latest packet and replacing it whenever a new packet arrives.A successfully transmitted packet may still be served before the next arrival, without affecting the system under preemptive priority.
A. Analyzing a Service Process
The service-process analysis models repeated transmissions under preemption by separating first transmission outcomes from subsequent retransmissions. It then derives the needed expected service quantities.
- A. Analyzing a Service Process: The analysis divides PAoI as in the preceding section and introduces symbols for repeated-service quantities.It defines ˜s, ˜p, ˆS_n, and S_n,k to describe total and per-transmission service behavior.
- A. Analyzing a Service Process: If a newer packet arrives during the first transmission, it preempts the current packet and the remaining process becomes the newer packet’s process.If the packet is lost instead, retransmission begins, with the first transmission not affecting subsequent retransmission time.
- A. Analyzing a Service Process: The expected residual service time after a lost first transmission is represented by ˜s, leading to an equation for the service process.The derivation combines first-transmission duration, loss probability, and preemption probability.
- A. Analyzing a Service Process: The analysis separately considers packets successfully transmitted before preemption and uses the number of transmissions together with Lemma 1.The resulting equations are solved to obtain the corresponding service-process quantities.
B. Computing PAoI
The section computes PAoI for retransmission with non-preemptive priority by tracking packets that succeed before replacement and packets retained through repeated transmissions. The derived result corresponds to an LCFS preemptive system with effective service rate pµ.
- B. Computing PAoI: The result corresponds to LCFS with preemptive priority at service rate pµ and success probability 1.The correspondence follows because each packet is either successfully transmitted or preempted, with mean service time 1/(pµ).
- B. Computing PAoI: Under non-preemptive retransmission, the server repeatedly transmits the most recent packet and remains busy.A new arrival cannot interrupt current service, but it can replace a packet waiting in the queue or at service completion.
- B. Computing PAoI: The analysis defines ˜s and ˜p for packets that are successfully transmitted before replacement or remain in service through the relevant process.Packets in Ω are those with no arrivals during their waiting time, and the service process is analyzed for these packets.
- B. Computing PAoI: If the first transmission fails, the server either transmits a newer packet that arrived during service or retransmits the current packet.Both cases produce the same expected remaining-time quantity ˜s for the analyzed process.
- B. Computing PAoI: The derived expected service quantity is ˜t = 1/µ + (1 − p)/[µ(λ + µ)(λ + pµ)].This expression is obtained after solving the preceding service-process equations.
B. Computing PAoI
The paper computes PAoI by analyzing waiting and service intervals in the M/M/1 system, then evaluates the resulting expressions across scheduling policies and packet-loss regimes.
- B. Computing PAoI: The PAoI calculation begins by conditioning on no arrivals during a packet’s waiting time and using the server’s continuously busy behavior.The derivation introduces conditional waiting and service expectations before forming the peak-age expression.
- B. Computing PAoI: The expected peak-age interval combines the conditional waiting term with the expected service and inter-delivery contributions.The displayed expressions define E{W_ni|n_i ∈ Ψ}, E{Ẑ_ni|n_i ∈ Ψ}, and PAoI from these components.
- VIII. Numerical Results: The numerical evaluation compares FCFS, packet-managed FCFS, LCFS, and retransmission policies under preemptive and non-preemptive priority.The study evaluates formulas alongside simulations for multiple delivery-error regimes, including p = 0.1, p = 0.5, and p = 1.
- VIII. Numerical Results: Theoretical and simulation results match closely, while LCFS and retransmission avoid the large PAoI caused by queueing delay or packet loss under relevant conditions.FCFS becomes very large at high channel utilization; retransmission performs especially well at high packet-loss rates, whereas non-preemptive retransmission can block later packets when loss is low.