ARQ for Network Coding
arXiv:0802.1754 · doi:10.1109/ISIT.2008.4595268
Abstract
A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly online, as opposed to a block-by-block approach. The setup assumes a packet erasure broadcast channel with stochastic arrivals and full feedback, but the proposed scheme is potentially applicable to more general lossy networks with link-by-link feedback. The algorithm guarantees that the physical queue size at the sender tracks the backlog in degrees of freedom (also called the virtual queue size). The new notion of a node "seeing" a packet is introduced. In terms of this idea, our algorithm may be viewed as a natural extension of ARQ schemes to coded networks. Our approach, known as the drop-when-seen algorithm, is compared with a baseline queuing approach called drop-when-decoded. It is shown that the expected queue size for our approach is as opposed to for the baseline approach, where is the load factor.
Submitted to the 2008 IEEE International Symposium on Information Theory (ISIT 2008)
References in corpus (2)
Cited by in corpus (36)
- Network coding meets TCP
- Batched Sparse Codes
- Effective Delay Control in Online Network Coding
- On Coding for Cooperative Data Exchange
- On-the-fly erasure coding for real-time video applications
- Capacity of 1-to-K Broadcast Packet Erasure Channels with Channel Output Feedback
- Streaming-Codes for Multicast over Burst Erasure Channels
- Network Coding in a Multicast Switch
- Joint Optimization of Throughput and Packet Drop Rate for Delay Sensitive Applications in TDD Satellite Network Coded Systems
- Performance Characterization and Transmission Schemes for Instantly Decodable Network Coding in Wireless Broadcast
- Adaptive Network Coding for Scheduling Real-time Traffic with Hard Deadlines
- Network Coding in a Multicast Switch
- Online network coding for optimal throughput and delay -- the three-receiver case
- Centralized and Cooperative Transmission of Secure Multiple Unicasts using Network Coding
- Random Linear Network Coding For Time Division Duplexing: When To Stop Talking And Start Listening
- Optimality of Network Coding in Packet Networks
- Network Coding as a WiMAX Link Reliability Mechanism
- Collision Helps - Algebraic Collision Recovery for Wireless Erasure Networks
- Random Linear Network Coding For Time Division Duplexing: Energy Analysis
- One Packet Suffices - Highly Efficient Packetized Network Coding With Finite Memory
- Capacity of 1-to-K Broadcast Packet Erasure Channels with Channel Output Feedback (Full Version)
- Energy-Delay Considerations in Coded Packet Flows
- Reliable Multicasting for Device-to-Device Radio Underlaying Cellular Networks
- Beyond the Min-Cut Bound: Deterministic Network Coding for Asynchronous Multirate Broadcast
- High Throughput Low Delay Wireless Multicast via Multi-Channel Moving Window Codes
- Dynamic Rate Adaptation for Improved Throughput and Delay in Wireless Network Coded Broadcast
- On the Concatenation of Non-Binary Random Linear Fountain Codes with Maximum Distance Separable Codes
- Online multipath convolutional coding for real-time transmission
- ARQ with Cumulative Feedback to Compensate for Burst Errors
- Constant Delay and Constant Feedback Moving Window Network Coding for Wireless Multicast: Design and Asymptotic Analysis
- ARQ for Physical-layer Network Coding
- Random Linear Network Codes for Secrecy over Wireless Broadcast Channels
- Random Access with Physical-layer Network Coding
- Joint On-the-Fly Network Coding/Video Quality Adaptation for Real-Time Delivery
- Study of Throughput and Latency in Finite-buffer Coded Networks
- Cooperative Network Coded ARQ Strategies for Two Way Relay Channel