PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Data Freshness, Throughput, and Delay in Multi-Server Information-Update Systems

Ahmed M. Bedewy, Yin Sun, Ness B. Shroff

arXiv:1603.06185v5cs.IT

TL;DR

The paper addresses how to reduce information age without losing throughput when all externally generated updates may need delivery and arrivals can be out of generation order. It models multi-server queueing with arbitrary arrivals and proves that preemptive LGFS optimizes age, while also optimizing throughput and delay with an infinite buffer. The results establish a broad optimality result for age-of-information under the stated exponential-service model.

  • Problem

    Existing age improvements may reduce throughput by lowering update generation or dropping stale packets, motivating age optimization when all externally generated updates must be delivered.

  • Method

    The paper analyzes a multi-server queue with exogenous packets, arbitrary generation and arrival times, and i.i.d. exponential service, comparing causal scheduling policies.

  • Results

    Preemptive LGFS stochastically minimizes age for any queue size and arbitrary arrivals, and with an infinite buffer it is also throughput-optimal and delay-optimal.

  • Takeaways & Limitations

    The paper provides simultaneous age, throughput, and delay optimality for preemptive LGFS within the stated multi-server model.

Abstract

from arXiv · show

In this work, we investigate the design of information-update systems, where incoming update packets are forwarded to a remote destination through multiple servers (each server can be viewed as a wireless channel). One important performance metric of these systems is the age-of-information or simply age, which is defined as the time elapsed since the freshest packet at the destination was generated. Recent studies on information-update systems have shown that the age-of-information can be reduced by intelligently dropping stale packets. However, packet dropping may not be appropriate in many applications, such as news and social updates, where users are interested in not just the latest updates, but also past news. Therefore, all packets may need to be successfully delivered. In this paper, we study how to optimize age-of-information without throughput loss. We consider a general scenario where incoming update packets do not necessarily arrive in the order of their generation times. We prove that a preemptive Last Generated First Served (LGFS) policy simultaneous optimizes the age, throughput, and delay performance in infinite buffer queueing systems. We also show age-optimality for the LGFS policy for any finite queue size. These results hold for arbitrary, including non-stationary, arrival processes. To the best of our knowledge, this paper presents the first optimal result on minimizing the age-of-information in communication networks with an external arrival process of information update packets.

I. INTRODUCTION

Information-update systems seek timely delivery of fresh information, but reducing age by dropping packets can sacrifice throughput or exclude users’ interest in past updates. This paper asks whether age, throughput, and delay can be optimized together with externally generated packets and arbitrary arrivals.

  • Motivation: Age of information is the time elapsed since the freshest packet at the destination was generated.At time t, age is defined as ∆(t) = t − U(t), where U(t) is the generation time of the freshest delivered update.
  • Motivation: Prior approaches reduced age by lowering update generation rates or discarding stale queued packets, which can sacrifice throughput or prevent delivery of past updates.Applications such as news and social updates may require all packets to be successfully delivered.
  • Research Questions: The paper studies exogenous update arrivals forwarded through multiple servers and asks whether age-optimality holds under arbitrary arrival processes.The system differs from settings where update generation and transmission are jointly controlled.
  • Contributions: Preemptive LGFS stochastically minimizes the age process for arbitrary arrivals and any queue size when service times are i.i.d. exponential.This implies optimality for non-decreasing age functionals, including time-average and average peak age.
  • Contributions: With an infinite buffer, preemptive LGFS is also throughput-optimal and delay-optimal among all causally feasible policies.The paper identifies this as a simultaneous optimization of freshness, throughput, and delay.

A. Notations and Definitions

The paper introduces univariate, multivariate, and process-level stochastic ordering to compare age and other random performance quantities.

  • Ordering Definitions: Vector ordering compares x and y componentwise, with x ≤ y when every x_i ≤ y_i.This ordering supports the definition of upper sets in R^n.
  • Ordering Definitions: A random variable X is stochastically smaller than Y when its distribution satisfies the paper’s univariate stochastic-order condition.The supplied passage introduces the notation but does not include the condition’s displayed formula.
  • Ordering Definitions: For random vectors, X is stochastically smaller than Y when P{X ∈ U} ≤ P{Y ∈ U} for every upper set U.An upper set contains every vector y ≥ x whenever it contains x.
  • Ordering Definitions: Process-level stochastic ordering requires the corresponding finite-dimensional vectors at every ordered collection of time points to satisfy multivariate stochastic ordering.The comparison applies to all integers n and times t_1 < t_2 < ... < t_n.

B. Queuing System Model

The model has exogenously generated packets stored in a buffer and assigned to m identical exponential-service servers, with finite buffers potentially causing packet loss.

  • System Model: Packets generated exogenously are stored in a queue and assigned to one of m identical servers, each with i.i.d. exponential service time of rate µ.Servers may represent wireless channels or TCP connections.
  • System Model: The buffer size B may be infinite, finite, or zero.A finite buffer can overflow, causing packet drops and throughput loss.

C. Scheduling Policy

Scheduling decisions determine completion times for packets whose arrival order may differ from generation order, using causal, preemptive, or work-conserving policy classes.

  • Scheduling Policy: Packet generation and arrival times are arbitrary and policy-independent, and packets may arrive out of generation order.For example, a_i > a_{i+1} can occur even when s_i < s_{i+1}.
  • Scheduling Policy: Causal policies make scheduling decisions from the system’s history and current state.The paper denotes the set of all such policies by Π.
  • Scheduling Policy: A preemptive policy allows a server to switch packets at any time, storing preempted packets when buffer space is available.A non-preemptive policy must complete the current packet before starting another.
  • Scheduling Policy: The age process increases linearly over time and resets to a smaller value when a fresher packet arrives.Figure 2 illustrates this sawtooth evolution.
  • Scheduling Policy: A work-conserving policy keeps every server busy whenever packets are waiting in the queue.This property is distinct from whether service can be preempted.

D. Performance Metric

The paper defines age as the elapsed time since the freshest delivered packet was generated and describes age-penalty functionals for evaluating staleness. It also presents the preemptive LGFS implementation that prioritizes fresh packets while managing server assignments and preemptions.

  • Age definition: Age is the time elapsed since the freshest packet at the destination was generated.The freshest generation time is U(t), and age is Δ(t) = t − U(t).
  • Age evolution: The age process increases linearly over time and resets to a smaller value when a fresher packet arrives.
  • Age penalties: An age-penalty functional is non-decreasing with respect to age and represents dissatisfaction with stale information.
  • Age penalties: The paper considers time-average age, average peak age, and time-average age penalty as examples of age-related performance measures.Average peak age uses peak values of the age process, while the penalty function may use any non-negative non-decreasing function h.
  • Preemptive LGFS: Preemptive LGFS assigns the freshest arriving packets to servers, stores preempted packets when possible, and assigns queued fresh packets when servers become idle.

III. OPTIMALITY ANALYSIS

The optimality analysis compares preemptive LGFS with causally feasible policies using coupled system states and stochastic ordering. Under i.i.d. exponential service times, LGFS is age-optimal for arbitrary arrivals and buffer sizes, while infinite buffers also yield throughput and mean-delay optimality.

  • Policy: Preemptive LGFS serves the freshest packets among those in service or waiting, assigning the next freshest packet after service completion.
  • Age optimality: With i.i.d. exponential service times, Theorem 1 establishes LGFS age-optimality for arbitrary generation and arrival sequences and any buffer size.
  • Proof strategy: The proof couples LGFS and competing work-conserving policies using exponential service times and forward induction on their system states.The exponential service assumption provides memorylessness for the coupling construction.
  • Age optimality: LGFS minimizes every non-decreasing age-penalty functional, including time-average age, average peak age, and average age penalty.
  • Buffer size: For any queue size B ≥ 0, the age performance of preemptive LGFS remains unchanged because stale preempted and outdated packets do not affect its age process.
  • Throughput and delay: When B = ∞, preemptive LGFS is throughput-optimal and mean-delay-optimal, and every work-conserving policy shares those two optimalities.

IV. NUMERICAL RESULTS

Numerical experiments compare age across traffic intensity, server count, queue size, and packet-ordering conditions. Preemptive LGFS consistently provides the strongest age performance in the reported settings.

  • Single-server results: With m = 1 server, preemptive LGFS achieves smaller time-average age than FCFS and non-preemptive LCFS with B = 1.For ordered arrivals, LGFS and LCFS have the same age performance when both correspond to the ordered-arrival setting.
  • Multi-server results: Five servers yield better age performance than the single-server case, attributed to the diversity provided by multiple servers.The reported comparison uses the multi-server experiment corresponding to Figure 4 and the single-server experiment corresponding to Figure 3.
  • Multi-server results: Preemptive LGFS achieves the best plotted age performance among the five-server policies, with age unchanged for every queue size B ≥ 0.Non-preemptive LGFS and FCFS vary with B in the multi-server setting.
  • Multi-server results: FCFS with B = ∞ has unbounded average age at high traffic intensity, whereas FCFS with B = 10 remains high but bounded.The paper attributes the divergence to congestion and stale-packet delivery, while finite buffering gives fresh packets a shorter delivery opportunity.

V. CONCLUSION

The paper studies multi-server information-update systems with exogenous arrivals and establishes optimality of preemptive LGFS under i.i.d. exponential service times. The policy simultaneously optimizes freshness, throughput, and delay for any given arrival process and queue size.

  • V. CONCLUSION: The system forwards exogenously generated update packets to a destination through multiple network servers.The servers can represent communication channels, and packets are stored in a queue before assignment.
  • V. CONCLUSION: Under i.i.d. exponential service times, preemptive LGFS simultaneously optimizes data freshness, throughput, and delay among all causally feasible policies.The result holds for any given arrival process and queue size.
  • V. CONCLUSION: The authors plan to extend these results to more general system settings with general service-time distributions.The stated conclusion identifies service-time generality as the next scope of extension.

APPENDIX A PROOF OF LEMMA 2*

The proof compares the freshest packets available under the proposed policy with those available under an arbitrary policy. The resulting inequalities establish the target relation for every queue size B ≥ 0.

  • APPENDIX A PROOF OF LEMMA 2*: The arrived-packet set S is policy-invariant, and s[i] denotes the i-th largest generation time among packets in S.This common packet set supports the comparison between policies.
  • APPENDIX A PROOF OF LEMMA 2*: Under policy P, the relevant generation-time quantity is αi,P = max{s[i], UP} for i = 1, . . . , m.The expression combines the i-th freshest arrived generation time with the policy state variable UP.
  • APPENDIX A PROOF OF LEMMA 2*: For an arbitrary policy π, the i-th freshest processed packet is no fresher than the i-th freshest packet in S, yielding αi,π ≤ max{s[i], Uπ}.The comparison uses the fact that choosing an older packet cannot improve the generation time.
  • APPENDIX A PROOF OF LEMMA 2*: Because the arrived set is invariant and UP ≥ Uπ, the two inequalities imply the desired comparison between policies.The proof then handles packet-delivery and no-delivery cases separately.
  • APPENDIX A PROOF OF LEMMA 2*: The resulting relation holds for every queue size B ≥ 0.The proof explicitly concludes both delivery cases for arbitrary queue capacity.

APPENDIX D PROOF OF THEOREM 6

The proof of Theorem 6 couples the state processes of preemptive LGFS and arbitrary work-conserving policies under infinite buffering. It then shows equal throughput and mean delay among work-conserving policies, while idling worsens both metrics.

  • APPENDIX D PROOF OF THEOREM 6: The proof compares policy P, the preemptive LGFS policy, with an arbitrary work-conserving policy π.The comparison is conducted through the policies’ system states and coupled packet-delivery times.
  • APPENDIX D PROOF OF THEOREM 6: For policy π, the state is Hπ(t) = (Nπ(t), γπ(t)), where Nπ(t) counts packets in the system and γπ(t) counts delivered packets.The state process is assumed to be right-continuous.
  • APPENDIX D PROOF OF THEOREM 6: Lemma 7 states that, with B = ∞ and matching initial states, the state processes of P and any work-conserving π have the same conditional distribution.The proof obtains this through coupling and supporting delivery and arrival lemmas.
  • APPENDIX D PROOF OF THEOREM 6: All work-conserving policies therefore have the same throughput and mean-delay performance under infinite buffering.The equality follows from identical distributions for the cumulative delivered-packet and in-system-packet processes.
  • APPENDIX D PROOF OF THEOREM 6: Service idling only increases packet waiting time, so non-work-conserving policies have worse throughput and mean delay.Consequently, preemptive LGFS is throughput-optimal and mean-delay-optimal among all policies in Π.
Loading 1603.06185v5…