PaperlayerView exact revision on arXiv

Source-linked AI summary

Reliable Transmission of Short Packets through Queues and Noisy Channels under Latency and Peak-Age Violation Guarantees

Rahul Devassy, Giuseppe Durisi, Guido Carlo Ferrante, Osvaldo Simeone, Elif Uysal

arXiv:1806.09396v3cs.ITmath.IT

TL;DR

Short-packet URLLC needs delay and freshness guarantees that account for queueing and undetected decoding errors, rather than relying on average delay alone. The paper analyzes these violation probabilities for Bernoulli arrivals and VLSF transmission, including ARQ and HARQ. It reports that equal average delays can conceal large differences in delay-violation probability, while LCFS-S outperforms the other examined policies on peak-age violation probability.

  • Problem

    For short-packet URLLC and status-update applications, the paper studies how to characterize delay and peak-age violations under latency and reliability constraints when queueing and undetected errors matter.

    Source: §I · p. 1, B. Definition of the Delay Violation… · p. 4

  • Method

    The paper combines queueing analysis with finite-blocklength VLSF coding, accounting for undetected errors and examining ARQ, HARQ, and packet-management policies.

    Source: §I · pp. 2–3

  • Results

    For ARQ, two frame sizes with the same average delay can produce delay-violation probabilities differing by two orders of magnitude; LCFS-S outperforms the other three examined policies in peak-age violation probability.

    Source: §I · p. 3

  • Takeaways & Limitations

    Frame size, decoding threshold, and packet-management policy are relevant design choices when targeting delay or peak-age violation probability.

    Source: §I · p. 3

Abstract

from arXiv · show

This work investigates the probability that the delay and the peak-age of information exceed a desired threshold in a point-to-point communication system with short information packets. The packets are generated according to a stationary memoryless Bernoulli process, placed in a single-server queue and then transmitted over a wireless channel. A variable-length stop-feedback coding scheme---a general strategy that encompasses simple automatic repetition request (ARQ) and more sophisticated hybrid ARQ techniques as special cases---is used by the transmitter to convey the information packets to the receiver. By leveraging finite-blocklength results, the delay violation and the peak-age violation probabilities are characterized without resorting to approximations based on large-deviation theory as in previous literature. Numerical results illuminate the dependence of delay and peak-age violation probability on system parameters such as the frame size and the undetected error probability, and on the chosen packet-management policy. The guidelines provided by our analysis are particularly useful for the design of low-latency ultra-reliable communication systems.

I. INTRODUCTION

The paper develops joint coding-and-queuing analyses of delay and peak-age violation probabilities for short-packet URLLC, where average delay and long-blocklength channel abstractions do not capture the target tail behavior. It applies finite-blocklength tools to VLSF transmission, including ARQ and HARQ, and accounts for undetected errors.

I. INTRODUCTION

  • For URLLC, the paper analyzes the probability that overall steady-state delay—including queueing and transmission—exceeds a target, and also studies peak-age violations when data freshness matters.The latter is relevant when packets carry sensor updates: low delivery latency may not satisfy the application’s freshness requirement.Source: §I · p. 1
  • Bit-pipe and large-deviation approaches are limited for short packets: they can give inaccurate delay estimates, tight estimates only for large delay, or require large packets.Earlier approaches also commonly assume zero undetected-error probability.Source: §I · p. 2
  • The analysis covers Bernoulli packet arrivals served by general VLSF codes, with ARQ and incremental-redundancy HARQ as special cases.The paper studies both delay and peak-age violation probabilities.Source: §I · p. 2
  • The proposed delay-violation definition includes both delay exceeding the latency target and undetected errors; its computable upper bound adds the steady-state delay CCDF to the undetected-error probability.The analysis obtains the steady-state delay distribution through its PGF and computes the CCDF using an inverse transform, with saddlepoint methods as an approximation.Source: §I · pp. 2–3
  • For simple ARQ, two frame sizes with the same average delay can yield delay-violation probabilities differing by two orders of magnitude, and large-deviation estimates are loose, especially at low SNR.The analysis uses finite-blocklength random-coding bounds to numerically select the frame size that minimizes delay violation probability.Source: §I · p. 3
  • For HARQ, the analysis estimates the stopping-time PGF and undetected-error probability, then optimizes the decoding threshold to reduce overall delay violation probability.The threshold trades off the delay CCDF at the target latency against undetected errors.Source: §I · p. 3
  • Among the examined peak-age policies, LCFS with preemption in service outperforms FCFS-1, FCFS-2, and LCFS-Q in peak-age violation probability.The analysis also considers ARQ with perfect packet error detection.Source: §I · p. 3

II. SYSTEM MODEL

The system models independent Bernoulli packet arrivals to a single-server FCFS queue, with packets transmitted over a discrete-time memoryless channel using VLSF codes. Transmission proceeds frame by frame with ACK/NACK feedback, and the synchronous model assumes ideal synchronization.

II. SYSTEM MODEL

  • Packets carrying k information bits arrive independently in each channel use with probability λ and enter a single-server FCFS queue.The mean interarrival time is 1/λ.Source: §II · p. 3
  • A VLSF encoder sends n-symbol frames and retransmits after NACKs until decoding succeeds and an ACK removes the packet from the queue.The random number of frames is τ, service time is nτ channel uses, and an ACK can still correspond to an undetected error with probability ϵu.Source: §II · p. 3
  • In the frame-synchronous setup, transmission of a packet arriving to an empty buffer waits until the next frame; the alternative asynchronous setup starts in the next available channel use and assumes ideal synchronization.The synchronous queue is modeled as Geo/G/1 with bulk arrivals; its steady-state delay exists when λnE[τ] < 1.Source: §II · pp. 3–4

III. STEADY-STATE DELAY VIOLATION PROBABILITY

This section defines VLSF coding and a steady-state delay-violation measure that counts both latency exceedances and undetected decoding errors. It gives a computable upper bound using the steady-state delay distribution and undetected-error probability, and describes methods for computing the distribution’s tail.

A. Definition of a VLSF Code

  • VLSF decoding is attempted after each n-symbol frame, and the code is parameterized by the stopping-time distribution Pτ rather than its mean.A failed attempt prompts another frame; successful decoding stops transmission and removes the packet from the queue.Source: A. Definition of a VLSF Code · p. 4

B. Definition of the Delay Violation Probability

  • The delay-violation upper bound is the steady-state delay CCDF at the latency constraint plus the undetected-error probability.The bound is obtained using the union bound; the delay distribution is taken in steady state.Source: B. Definition of the Delay Violation… · p. 5
  • The steady-state delay PGF depends on the packet arrival rate and service-time PGF, under the stability condition λn E[τ] < 1.The delay CCDF can be computed from this PGF; the section also presents numerical inversion and a reduced-complexity saddlepoint approximation.Source: B. Definition of the Delay Violation… · p. 5
  • The saddlepoint approximation is reported to be very accurate over a large range of system parameters.The method distinguishes cases according to whether the latency threshold in frames is above or below the expected steady-state delay.Source: B. Definition of the Delay Violation… · p. 5

C. A Special Case: ARQ with Perfect Error Detection

For ARQ with perfect error detection, the section uses finite-blocklength random-coding bounds to characterize delay violation. It also presents a stochastic-network-calculus alternative, which can be looser than the characterization based on the delay distribution.

C. A Special Case: ARQ with Perfect Error Detection

  • In this ARQ setup, the transmitter repeats the same n channel inputs in each frame until receiving an ACK, which is assumed to follow only correct decoding.The analysis notes that hashing can provide perfect error detection, with its overhead neglected.Source: C. A Special Case: ARQ with Perfect… · p. 5
  • The RCUs bound [27, Thm. 1] supplies an achievable frame error probability, yielding geometric decoding time with parameter 1 − ϵ_rcus.With perfect error detection, ϵ_u = 0, so the delay-violation upper bound equals the delay-violation probability.Source: C. A Special Case: ARQ with Perfect… · pp. 5–6
  • Stochastic network calculus gives an alternative upper bound for ARQ with perfect error detection, but it can be much looser than the delay-distribution characterization.Its numerical evaluation has the same complexity as the saddlepoint approximation, and both are easier to evaluate than the inversion-based expression.Source: C. A Special Case: ARQ with Perfect… · p. 6

D. VLSF Codes with Positive Undetected Error Probability

For VLSF codes with positive undetected-error probability, the section adapts a threshold-decoding achievability bound to characterize stopping time and error probability. It also treats retransmission limits and notes why the stochastic-network-calculus bound used for ARQ does not extend to general VLSF.

D. VLSF Codes with Positive Undetected Error Probability

  • The adapted threshold-decoding bound characterizes the stopping-time CCDF and undetected-error probability for VLSF codes.The threshold crossing for the transmitted codeword defines τ*, which stochastically dominates the actual stopping time; an undetected error occurs when an incorrect codeword crosses first.Source: D. VLSF Codes with Positive Undetected… · p. 6
  • The achievability bound extends to truncated hybrid ARQ by limiting retransmissions to a maximum number of frames.The bound includes an additional term for a NACK after the last frame, which yields a detected error.Source: D. VLSF Codes with Positive Undetected… · p. 6
  • With at most nt frame transmissions, every VLSF code can be represented as a convex combination of at most nt + 1 deterministic VLSF codes.The stopping-time distribution is specified by an (nt − 1)-dimensional vector, and the common-randomness set need not exceed nt + 1 elements.Source: D. VLSF Codes with Positive Undetected… · p. 6
  • The stochastic-network-calculus bound used for ARQ is unavailable for general VLSF because its proof requires stationary, memoryless departures, an assumption that does not hold here.Source: D. VLSF Codes with Positive Undetected… · pp. 6–7

IV. THE FRAME-ASYNCHRONOUS SETUP

The section gives a delay PGF for frame-asynchronous operation and develops peak-age PGFs for frame-synchronous operation under different packet-management policies.

IV. THE FRAME-ASYNCHRONOUS SETUP

  • In the frame-asynchronous model, the steady-state delay PGF is given for VLSF codes satisfying λn E[τ] < 1.Packets arriving to an empty buffer begin transmission in the next available channel use, and the setup is modeled as a Geo/G/1 queue.Source: §IV · p. 7

V. STEADY-STATE PEAK-AGE VIOLATION PROBABILITY

  • Peak age is evaluated for frame-synchronous status updates using the frame index when each packet enters the queue as its timestamp.The peak age is the age of information just before a transmitted packet is received.Source: §V · p. 7
  • The analyzed policies range from FCFS-1, which discards arrivals during service, to FCFS-2 and LCFS-Q with one waiting packet, and LCFS-S, which preempts service.FCFS-1 and FCFS-2 avoid preemption; LCFS-Q has lower peak-age violation probability than FCFS-2, while LCFS-S is described as most complex and best-performing.Source: §V · pp. 7–8
  • For the frame-synchronous model, the paper characterizes peak-age PGFs for FCFS-1, FCFS-2, LCFS-Q, and LCFS-S.The FCFS-1 result applies to stable VLSF codes; the FCFS-2, LCFS-Q, and LCFS-S results are presented for ARQ with perfect error detection.Source: §V · p. 8
  • For peak-age analysis of FCFS-2, LCFS-Q, and LCFS-S, the paper restricts attention to ARQ with perfect error detection because general VLSF analysis appears unfeasible.The restriction permits use of the geometric service-time distribution's memorylessness.Source: §V · p. 8

VI. NUMERICAL RESULTS

The numerical results show that delay- and peak-age violation probabilities depend strongly on frame size, decoding threshold, and packet-management policy. They also illustrate trade-offs between delay and undetected errors, and among policies for peak age.

Simple ARQ with Perfect Error Detection

  • Higher SNR reduces both service time and overall packet delay in ARQ with perfect error detection.The comparison uses n = 100 channel uses and λ = 10^-3 packets per channel use; the saddlepoint approximation is reported as extremely accurate.Source: §VI · p. 9
  • At ρ = 0 dB, the stochastic-network-calculus throughput estimate is about 35% lower than the exact analysis, which exhibits a throughput-maximizing frame size.Small frames increase packet errors and retransmissions; large frames can produce long delays even with few retransmissions.Source: §VI · p. 9, Figure 5 · p. 9

General VLSF Codes

  • For general VLSF codes, lowering the decoding threshold γ reduces delay exceedance but raises undetected-error probability; increasing γ reverses this trade-off.The delay-violation upper bound is the sum of the steady-state delay CCDF at the latency constraint and the undetected-error probability.Source: Figure 6 · p. 9, §VI · p. 10
  • For ARQ, decreasing frame size improves VLSF delay violation, while too-small or too-large frames penalize ARQ.VLSF benefits because shorter frames let the decoder sample accumulated information density more frequently.Source: §VI · p. 10

Peak-Age Violation Probability

  • LCFS-S uniformly outperforms FCFS-1, FCFS-2, and LCFS-Q in peak-age violation probability; FCFS-1 is better at high arrival rates, while FCFS-2 is better at lower rates.For k = 25 bits, the high-arrival limits are 3.2 × 10^-7 for FCFS-1, 8 × 10^-7 for FCFS-2, 1.2 × 10^-7 for LCFS-Q, and 9.7 × 10^-9 for LCFS-S.Source: §VI · p. 10, Figure 8 · p. 10

A. Fading and Interference

The analysis can be extended beyond the standard bi-AWGN channel to models including fading, multiple antennas, pilot-assisted transmission, and mismatch decoding.

A. Fading and Interference

  • Block fading with frames spanning frequency-separated resource blocks can model frequency diversity as a block-memoryless channel.The framework can use block-memoryless finite-blocklength bounds in place of those for the memoryless channel.Source: A. Fading and Interference · p. 10
  • Pilot-assisted transmission and mismatch nearest-neighbor decoding can be incorporated into the analysis.Treating unknown interference as additive noise in the decoder allows its performance impact to be characterized.Source: A. Fading and Interference · pp. 10–11
  • The proposed analysis also encompasses fading and multiple-antenna system models for URLLC transmission.These extensions are described as generalizations of the framework presented in the paper.Source: A. Fading and Interference · p. 10

B. Beyond the Point-to-Point Setup

The framework is presented for a single-flow point-to-point link, with several broader network settings identified as generalizations. The conclusion describes nonasymptotic evaluation of delay and peak-age violation probabilities and reports sensitivity to system parameters, while cautioning against average-latency and stochastic-network-calculus design approaches.

B. Beyond the Point-to-Point Setup

  • The analysis covers a single-flow point-to-point link; multiple flows, broadcast, multiple access, and multihop are identified as natural generalizations.The first three scenarios are discussed as possible extensions of the framework.Source: B. Beyond the Point-to-Point Setup · p. 11

VIII. CONCLUSION

  • The paper evaluates delay and peak-age violation probabilities for Bernoulli arrivals, a single-server queue, and point-to-point communication over a bi-AWGN channel using VLSF codes.The approach also accounts for undetected errors, which the authors identify as potentially harmful in mission-critical systems.Source: §VIII · p. 11
  • The delay violation probability is extremely sensitive to system parameters, including frame size and undetected-error probability.The cited figures show dependence on frame size for maximum throughput and delay violation under simple ARQ with perfect error detection, and on undetected-error probability for delay violation.Source: §VIII · p. 11
  • Average-latency and stochastic-network-calculus analyses do not yield an optimal design; the latter also lacks generality.Source: §VIII · p. 11

APPENDIX A PROOF OF THEOREM 1

The proof models the buffer size after successive bulk departures as a Markov chain and uses its probability generating function to obtain the steady-state buffer-size distribution. The appendix also describes an exact recursive z-transform inversion for computing a CCDF from a rational probability generating function.

APPENDIX A PROOF OF THEOREM 1

  • The remaining buffer size after each bulk departure follows a Markov chain with next state equal to the prior state minus one, floored at zero, plus arrivals during service.The number of arrivals during service depends on the service time and is independent of the current buffer state.Source: Appendix A · p. 11
  • A probability generating function for the steady-state buffer size is obtained from the arrivals-during-service distribution, under the stability condition E[U] < 1.The derivation relates the steady-state buffer size to the sum of arrival indicators during the service time.Source: Appendix A · p. 11

APPENDIX B COMPUTATION OF THE CCDF FROM THE PGF OF A

  • For rational probability generating functions, recursive z-transform inversion computes the CCDF exactly by successively obtaining lower-index tail probabilities.The method applies only when GX(s) is rational.Source: Appendix B · p. 11

APPENDIX C PROOF OF THEOREM 4

The proof of Theorem 4 uses decoder information densities and an ACK threshold to bound the transmission-frame tail. The proof of Theorem 8 expresses peak age using interarrival and service times together with packets interrupted by preemption.

APPENDIX C PROOF OF THEOREM 4

  • At each frame, the decoder evaluates information densities and sends an ACK when one exceeds γ; the resulting transmission-frame CCDF is upper-bounded.The decoder outputs the message associated with the first threshold crossing, with a tie resolved by the largest message index.Source: Appendix C · p. 12

APPENDIX D PROOF OF THEOREM 8

  • Given the number of preempted packets between successful deliveries, peak age is distributed as a sum of interarrival and service-time variables.The count of preemptions plus one is geometrically distributed with parameter pd.Source: Appendix D · p. 12
Loading 1806.09396v3…