Effective Capacity for Renewal Service Processes With Applications to HARQ Systems

Zheng Shi, Theodoros A. Tsiftsis, Weiqiang Tan, Guanghua Yang, Shaodan Ma, Mohamed-Slim Alouini

TL;DR

This paper provides a breakthrough in cross-layer network design by deriving the first exact analytical expressions for the "Effective Capacity" of renewal service processes. By applying these mathematical tools to various Hybrid Automatic Repeat Request (HARQ) schemes, the authors demonstrate how to accurately evaluate and optimize system throughput while strictly adhering to 5G-grade quality of service (QoS) constraints like latency and buffer limits.

What Problem Does This Paper Address?

In the push toward 5G and beyond, we need more than just high "raw" data rates; we need "ultra-reliability" and "low latency." Traditional physical-layer metrics often ignore the behavior of the data queue. If a system has a high average throughput but high jitter or long bursts of errors, the data buffer will overflow, causing delays that are unacceptable for applications like autonomous driving or remote surgery.

Effective Capacity (EC) is a cross-layer metric that solves this by defining the maximum arrival rate a link can support while meeting a specific statistical delay constraint (represented by the QoS exponent $\theta$). However, calculating EC is notoriously difficult for systems using HARQ (where packets are retransmitted until successful). HARQ creates a "renewal process"—a sequence of random service events—that makes the underlying math messy. Previous research relied on loose approximations that failed when QoS requirements were strict. This paper aims to replace those guesses with exact formulas.

Methods

The authors move away from the standard "small-exponent" approximations used in prior literature. Instead, they employ a rigorous approach based on Z-transforms and Laplace transforms.

  1. Renewal Reward Theory: They model the communication process as a renewal reward process, where each successful transmission cycle is a "renewal" and the bits delivered are the "reward."
  2. Z-Transform Analysis: For discrete service processes (like HARQ), they use Z-transforms to derive a closed-form expression for the moment-generating function of the accumulated service.
  3. Matrix Representation: They introduce a novel theorem using Vandermonde matrices to simplify the inverse Z-transform process, resulting in a compact matrix-form expression for Effective Capacity.
  4. Generalization: They extend the math from simple constant-reward processes to complex scenarios with variable rewards and variable transmission rates (VR-HARQ and XP-HARQ).

Datasets

As a theoretical communication theory paper, it does not use external real-world datasets. Instead, the authors evaluate their models using:

  • Numerical Analysis: Direct computation of their derived analytical formulas.
  • Monte Carlo Simulations: Extensive simulations of Rayleigh fading channels (independent and identically distributed) to validate that their "exact" formulas actually match simulated reality.

Key Insights and Ideas

  • The "Exact" Advantage: The paper proves that previous approximations significantly overestimate capacity when QoS constraints are tight (high $\theta$). Their new formulas remain accurate across the entire range of QoS requirements.
  • Monotonicity and Bounds: The authors prove that Effective Capacity is a monotonically decreasing function of the QoS exponent. They also establish clear upper and lower bounds, providing engineers with a "performance envelope" for system design.
  • The Power of Variable Rates: A major "aha" moment is the comparison between different HARQ types. While Fixed-Rate HARQ (FR-HARQ) is simpler, Variable-Rate (VR-HARQ) and Cross-Packet (XP-HARQ) schemes perform significantly better under delay constraints because they can adapt more fluidly to channel fluctuations.
  • Convergence of Advanced Schemes: Interestingly, the results show that VR-HARQ and XP-HARQ achieve almost identical optimal performance, suggesting that the complexity of cross-packet coding might not always be necessary if variable-length coding is well-optimized.

Key Results

  • Accuracy: Numerical results perfectly corroborate the analytical derivations, showing a significant gap between the new exact results and old approximations at higher QoS exponents.
  • Throughput Gains: Under a delay constraint of $\theta = 10^{-3}$, the paper shows that optimized HARQ-IR (Incremental Redundancy) significantly outperforms Type I HARQ and Chase Combining (CC).
  • SNR Impact: The effective capacity increases with the transmit Signal-to-Noise Ratio (SNR) but eventually hits a plateau defined by the transmission rate and the maximum number of retransmissions ($K$).
  • Rate Selection: The authors demonstrate that selecting the right initial transmission rate is critical; a poorly chosen rate can cause the effective capacity to drop to nearly zero, even if the average SNR is high.

Limitations and Future Work

  • Idealized Feedback: The current model assumes that HARQ feedback (ACK/NACK) is instantaneous and error-free. In real-world satellite or long-distance links, feedback delay and errors could significantly impact the renewal process.
  • Computational Complexity of Optimization: While the paper provides the formulas to evaluate capacity, maximizing it requires an exhaustive search over transmission rates due to the non-convex nature of the objective function. Developing more efficient optimization algorithms is a suggested next step.
  • Channel Correlation: The study assumes independent fading between rounds. Future work could extend these exact expressions to time-correlated channels, which are common in slow-moving mobile scenarios.

Summary updated

Abstract

Considering the widespread use of effective capacity in cross-layer design and the extensive existence of renewal service processes in communication networks, this paper thoroughly investigates the effective capacity for renewal processes. Exact expressions of the effective capacity at a given quality of service (QoS) exponent are derived for the renewal processes with either constant or variable reward. The simple expressions reveal meaningful insights, such as the monotonicity and bounds of the effective capacity. The analytical results are then applied to evaluate the cross-layer throughput for diverse hybrid automatic repeat request (HARQ) systems, including fixed-rate HARQ (FR-HARQ, e.g., Type I HARQ, HARQ with chase combining (HARQ-CC) and HARQ with incremental redundancy (HARQ-IR)), variable-rate HARQ (VR-HARQ), and cross-packet HARQ (XP-HARQ). Furthermore, aiming at maximizing the effective capacity via the optimal rate selection, it is disclosed that the VR-HARQ and XP-HARQ attain almost the same performance, and both of them perform better than FR-HARQ. In contrast, most of the prior outcomes approximate the effective capacity with the lack of insightful discussions that hampers the optimal design of HARQ systems. Finally, the numerical results corroborate the analytical ones.
BibTeX
@article{shi2019effective,
  author = {Zheng Shi and Theodoros A. Tsiftsis and Weiqiang Tan and Guanghua Yang and Shaodan Ma and Mohamed-Slim Alouini},
  title = {{Effective Capacity for Renewal Service Processes With Applications to HARQ Systems}},
  journal = {IEEE Trans. Communications},
  year = {2019},
  url = {https://openreview.net/forum?id=ZM98asYGHuh},
}
Figure