Delay on Broadcast Erasure Channels Under Random Linear Combinations
Nan Xie, Steven P. Weber · IEEE Transactions on Information Theory · 2016
We consider a transmitter broadcasting random linear combinations (over a field of size d) formed from a block of c packets to a collection of n receivers, where the channels between the transmitter and each receiver are independent erasure channels with reception probabilities q = (q1,..., qn). We establish several properties of the random delay until all n receivers have recovered all c packets, denoted Yn:n(c). First, we provide lower and upper bounds, exact expressions, and a recurrence for the moments of Yn:n(c). Second, we study the delay per packet Yn:n(c)/c as a function of c, including the asymptotic delay (as c → ∞) and monotonicity (in c) properties of the delay per packet. Third, we employ extreme value theory to investigate Yn:n(c)as a function of n (as n → ∞). Several results are new, some results are extensions of existing results, and some results are the proofs of known results using new (probabilistic) proof techniques.