On Coding for Reliable Communication over Packet Networks
arXiv:cs/0510070 · doi:10.1016/j.phycom.2008.01.006
Abstract
We present a capacity-achieving coding scheme for unicast or multicast over lossy packet networks. In the scheme, intermediate nodes perform additional coding yet do not decode nor even wait for a block of packets before sending out coded packets. Rather, whenever they have a transmission opportunity, they send out coded packets formed from random linear combinations of previously received packets. All coding and decoding operations have polynomial complexity. We show that the scheme is capacity-achieving as long as packets received on a link arrive according to a process that has an average rate. Thus, packet losses on a link may exhibit correlation in time or with losses on other links. In the special case of Poisson traffic with i.i.d. losses, we give error exponents that quantify the rate of decay of the probability of error with coding delay. Our analysis of the scheme shows that it is not only capacity-achieving, but that the propagation of packets carrying "innovative" information follows the propagation of jobs through a queueing network, and therefore fluid flow models yield good approximations. We consider networks with both lossy point-to-point and broadcast links, allowing us to model both wireline and wireless packet networks.
33 pages, 6 figures; revised appendix
References in corpus (4)
Cited by in corpus (59)
- On Coding for Reliable Communication over Packet Networks
- Minimum-Cost Multicast over Coded Packet Networks
- ARQ for Network Coding
- Batched Sparse Codes
- Network Coding Meets Multimedia: a Review
- Further Results on Coding for Reliable Communication over Packet Networks
- Coding Schemes for Line Networks
- Decoding Delay Performance of Random Linear Network Coding for Broadcast
- Feedback-based online network coding
- On Counteracting Byzantine Attacks in Network Coded Peer-to-Peer Networks
- Cross-Layer Designs in Coded Wireless Fading Networks with Multicast
- Network Coded TCP (CTCP)
- An Algebraic Watchdog for Wireless Network Coding
- Wireless Network Coding via Modified 802.11 MAC/PHY: Design and Implementation on SDR
- Efficient Operation of Coded Packet Networks
- Throughput and Latency in Finite-Buffer Line Networks
- Joint Optimization of Throughput and Packet Drop Rate for Delay Sensitive Applications in TDD Satellite Network Coded Systems
- Algebraic Watchdog: Mitigating Misbehavior in Wireless Network Coding
- Network Coding Security: Attacks and Countermeasures
- Finite-Length Analysis of BATS Codes
- Near Optimal Broadcast with Network Coding in Large Sensor Networks
- Network Codes with Overlapping Chunks over Line Networks: A Case for Linear-Time Codes
- Algebraic Network Coding Approach to Deterministic Wireless Relay Networks
- Online network coding for optimal throughput and delay -- the three-receiver case
- Throughput-Delay Analysis of Random Linear Network Coding for Wireless Broadcasting
- Overlapped Chunked Network Coding
- BAR: Blockwise Adaptive Recoding for Batched Network Coding
- Deterministic Network Model Revisited: An Algebraic Network Coding Approach
- On the Delay of Network Coding over Line Networks
- 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
- Counteracting Byzantine Adversaries with Network Coding: An Overhead Analysis
- Iterative Approximate Consensus in the presence of Byzantine Link Failures
- Random Linear Network Coding For Time Division Duplexing: Energy Analysis
- One Packet Suffices - Highly Efficient Packetized Network Coding With Finite Memory
- Expander Chunked Codes
- Joint Design of Channel and Network Coding for Star Networks
- Repair for Distributed Storage Systems in Packet Erasure Networks
- Decoding Error Probability of the Random Matrix Ensemble over the Erasure Channel
- Repair for Distributed Storage Systems with Erasure Channels
- Wireless Broadcast with Network Coding in Mobile Ad-Hoc Networks: DRAGONCAST
- Whether and Where to Code in the Wireless Relay Channel
- Beyond the Min-Cut Bound: Deterministic Network Coding for Asynchronous Multirate Broadcast
- Reduced Complexity Sum-Product Algorithm for Decoding Network Codes and In-Network Function Computation
- Utility Maximization for Multihop Wireless Networks Employing BATS Codes
- Wireless Erasure Networks with Feedback
- A Novel Network Coded Parallel Transmission Framework for High-Speed Ethernet
- A Unified Adaptive Recoding Framework for Batched Network Coding
- Network coding for multicasting over Rayleigh fading multi access channels
- Pipelined Encoding for Deterministic and Noisy Relay Networks
- On the Delay Advantage of Coding in Packet Erasure Networks
- On cone partitions for the min-cut and max-cut problems with non-negative edges
- Dynamic Radio Resource Management for Random Network Coding: Power Control and CSMA Backoff Control
- Distributed Intrusion Detection of Byzantine Attacks in Wireless Networks with Random Linear Network Coding
- Dynamic control of Coding in Delay Tolerant Networks
- Beyond Capacity: The Joint Time-Rate Region
- Analyzing Random Network Coding with Differential Equations and Differential Inclusions