Broadcast erasure channel with feedback - Capacity and algorithms
Authors:
- 1 June 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23749660,p. 54-61
Abstract
We consider the two-user broadcast erasure channel where feedback in the form of ack messages is fed back to the transmitter. We provide an upper bound to the capacity region of this system. We then present two algorithms whose rate region (information bits per transmitted bit) becomes arbitrarily close to the upper bound for large packet sizes. The first algorithm relies on random coding techniques while the second relies only on XOR operations between pairs of packets. Complexity and feedback information tradeoffs for the two algorithms are discussed. For the case where, in addition to traffic destined exclusively to either one of the users there is additional multicast traffic, we present an algorithm that shows that the rate region of the system can be increased by allowing inter-session coding. Finally, for the case where there are random arrivals to the system we present an algorithm, based on the previous algorithms, whose stability region gets close to the capacity region for reasonably large packet sizes. The latter algorithm operates without knowledge of arrival process and channel statistics.Keywords
This publication has 10 references indexed in Scilit:
- Online network coding for optimal throughput and delay - the three-receiver case2008
- ARQ for network coding2008
- On coding for reliable communication over packet networksPhysical Communication, 2008
- Towards Reliable Broadcasting using ACKs2007
- On Feedback for Network Coding2007
- ER2007
- XORs in the airACM SIGCOMM Computer Communication Review, 2006
- Capacity of wireless erasure networksIEEE Transactions on Information Theory, 2006
- The capacity region of multiple input erasure broadcast channels2005
- The feedback capacity of degraded broadcast channels (Corresp.)IEEE Transactions on Information Theory, 1978