Effective Delay Control in Online Network Coding

Abstract

Motivated by streaming applications with stringent delay constraints, we consider the design of online network coding algorithms with timely delivery guarantees. Assuming that the sender is providing the same data to multiple receivers over independent packet erasure channels, we focus on the case of perfect feedback and heterogeneous erasure probabilities. Based on a general analytical framework for evaluating the decoding delay, we show that existing ARQ schemes fail to ensure that receivers with weak channels are able to recover from packet losses within reasonable time. To overcome this problem, we re-define the encoding rules in order to break the chains of linear combinations that cannot be decoded after one of the packets is lost. Our results show that sending uncoded packets at key times ensures that all the receivers are able to meet specific delay requirements with very high probability.

9 pages, IEEE Infocom 2009

References in corpus (3)

• ARQ for Network Coding
• Informed Network Coding for Minimum Decoding Delay
• Hitting times for independent random walks on ${\mathbb{Z}}^d$

Cited by in corpus (13)

• Analysis and Optimization of Sparse Random Linear Network Coding for Reliable Multicast Services
• Modeling Network Coded TCP Throughput: A Simple Model and its Validation
• Binary Systematic Network Coding for Progressive Packet Decoding
• Systematic Network Coding with the Aid of a Full-Duplex Relay
• Performance Characterization and Transmission Schemes for Instantly Decodable Network Coding in Wireless Broadcast
• Instantly Decodable versus Random Linear Network Coding: A Comparative Framework for Throughput and Decoding Delay Performance
• Adaptive Network Coding for Scheduling Real-time Traffic with Hard Deadlines
• On Minimizing the Average Packet Decoding Delay in Wireless Network Coded Broadcast
• Reliable Multicasting for Device-to-Device Radio Underlaying Cellular Networks
• Dynamic Rate Adaptation for Improved Throughput and Delay in Wireless Network Coded Broadcast
• On Improving the Balance between the Completion Time and Decoding Delay in Instantly Decodable Network Coded Systems
• Beyond the Min-Cut Bound: Deterministic Network Coding for Asynchronous Multirate Broadcast
• Constant Delay and Constant Feedback Moving Window Network Coding for Wireless Multicast: Design and Asymptotic Analysis