Abstract
For several years, the completion time and the decoding delay problems in Instantly Decodable Network Coding (IDNC) were considered separately and were thought to completely act against each other. Recently, some works aimed to balance the effects of these two important IDNC metrics but none of them studied a further optimization of one by controlling the other. In this paper, we study the effect of controlling the decoding delay to reduce the completion time below its currently best known solution in persistent erasure channels. We first derive the decoding-delay-dependent expressions of the users' and overall completion times. Although using such expressions to find the optimal overall completion time is NP-hard, we design two novel heuristics that minimizes the probability of increasing the maximum of these decoding-delay-dependent completion time expressions after each transmission through a layered control of their decoding delays. We, then, extend our study to the limited feedback scenario. Simulation results show that our new algorithms achieves both a lower mean completion time and mean decoding delay compared to the best known heuristic for completion time reduction. The gap in performance becomes significant for harsh erasure scenarios.
Introduction
Instantly Decodable Network Coding (IDNC) is a popular technique for low-latency wireless broadcasting applications, such as IPTV or vehicle-to-roadside safety messages. Its primary appeal is "instant decodability": a receiver can decode a new packet immediately upon reception using a simple XOR operation, without needing to buffer a large block of data.
Historically, researchers have focused on two primary performance metrics: Completion Time (CT), the total number of transmissions required until every user has received all required packets, and Decoding Delay (DD), the delay experienced by a user when they receive a coded packet that cannot be immediately decoded. These metrics were traditionally treated as a zero-sum game—optimizing for one was thought to degrade the other. This paper challenges that belief, demonstrating that intelligently controlling decoding delay can actually accelerate the total completion time, particularly in challenging wireless environments.
Modeling Persistent Erasure Channels
Most existing IDNC models assume "memoryless" channels where packet loss is purely random. In reality, wireless channels often suffer from persistent erasures, where if one packet is lost, subsequent packets are also likely to be lost due to fading or interference. To model this behavior, the authors utilize a two-state Gilbert-Elliott channel model.
By incorporating the memory of the channel (the probability of staying in a "Bad" state), the proposed algorithms make more informed decisions about which users to target compared to traditional memoryless models.
Methodology
The authors derive a new analytical approximation for individual completion time that explicitly incorporates decoding delay. They then formulate the problem of minimizing the maximum completion time across all users as a stochastic optimization task. To solve this NP-hard problem, they propose two novel heuristics:
- Multi-layer Greedy Algorithm: This approach partitions the IDNC graph into "layers" based on user criticality. It uses a Maximum Weight Clique search to find the best combination of packets to XOR together, prioritizing users in the most critical layers while ensuring instant decodability.
- Binary Particle Swarm Optimization (BPSO): A population-based search algorithm that explores the space of possible packet combinations to maximize a multi-layer objective function, offering high computational efficiency.
The study also extends these methods to limited feedback scenarios, where the sender may not know exactly which packets receivers have decoded. They introduce "blind" update policies (Pessimist, Optimist, and Realistic) to estimate receiver states.
Key Results and Insights
Through extensive Monte Carlo simulations, the paper establishes several key findings:
- Breaking the Trade-off: Contrary to previous assumptions, the new algorithms achieve a lower mean completion time and a lower mean decoding delay simultaneously. Decoding delay acts as a predictor of future completion time; controlling it prevents bottlenecks before they form.
- Superior Performance in Harsh Conditions: The proposed "P-CT" algorithm consistently outperforms the best-known existing heuristic ("Min-CT"), with the performance gap widening in high-erasure scenarios.
- BPSO Efficiency: The BPSO-based approach achieves near-optimal performance with very few iterations, making it suitable for real-time hardware implementation.
- Robustness: Even with unreliable feedback channels, the "Realistic" blind update policy allows the system to maintain high efficiency.
Conclusion
This research demonstrates that minimizing completion time and decoding delay are not inherently conflicting goals. By implementing layered control of decoding delays and accounting for persistent channel erasures, IDNC systems can achieve significantly faster data delivery. Future work may explore these mechanisms in more complex network topologies or with varied data traffic types.
Summary updated