A class of feedback-based coding algorithms for broadcast erasure channels with degraded message sets

We consider single-hop broadcast erasure channels (BEC) with degraded message sets and instantaneous feedback regularly available from all receivers, and demonstrate that the main principles of the virtual queue-based algorithms in [1], which were proposed for multiple unicast sessions, can still be applied to this setting and lead to capacity achieving algorithms. Specifically, we propose a generic class of algorithms and intuitively describe its rationale and properties that result in its efficiency. We then apply this class of algorithms to three examples of BEC channels (with different numbers of users and 2 or 3 degraded message sets) and show that the achievable throughput region matches a known capacity outer bound. These algorithms do not require any prior knowledge of channel statistics for their operation.

Related material