Capacity-achieving encoding for the broadcast erasure channel with multiple users

We consider the N-user memoryless broadcast erasure channel with N unicast sessions (one for each user) where receiver feedback is sent to the transmitter in the form of ACK/NACK messages. We first provide a generic outer bound to the capacity of this system; using concepts from network coding, we then propose a session-mixing coding algorithm applied on specially constructed and maintained virtual queues (at the transmitter side), determine its throughput region and show that it achieves capacity under certain conditions on channel statistics (assuming that instantaneous feedback is known to all users). The algorithm requires no knowledge of channel statistics or future events. © 2011 IEEE