A new capacity-approaching protocol for general 1-to-K broadcast packet erasure channels with ACK/NACK
Chih-Hua Chang, Chih-Chun Wang · 2017
The capacity region of 1-to-K broadcast packet erasure channels with ACK/NACK is known for some scenarios, e.g., K ≤ 3, etc. However, existing achievability schemes either require knowing the target rate R in advance, and/or have a complicated description of the achievable rate region that is difficult prove whether it matches the capacity or not. This work proposes a new network coding protocol with the following unique set of features: (i) Its achievable rate region is identical to the capacity region for all the scenarios in which the capacity is known; (ii) Its achievable rate region is much more tractable that existing works and has been used to derive new capacity rate vectors; (iii) It employs sequential encoding that naturally handles dynamic packet arrivals; (iv) It automatically adapts to unknown packet arrival rates R⃗; (v) It is based on GF(q) with q > K. Numerically, for K = 4, it admits an average control overhead 2-4% (assuming each packet has 1000 bytes), average encoding memory usage 48.5 packets, and average per-packet delay 94.8 time slots, when operating at 95% of the capacity.