Performance Analysis of Feedback-Based Network-Coded Systems for Broadcast

In a broadcast transmission over an erasure network, feedback with network coding is both capacity-achieving and loss-immune. In this article, we carry out performance analyses of the feedback-based online network coding technique, drop when seen (DWS), and its recently proposed randomized variant (rDWS). An absorbing discrete time Markov chain (DTMC) model is constructed to find the probability of dropping a packet from the sender queue (even before decoding) in a generation-based DWS broadcast. The dropping probability is computed efficiently in homogeneous as well as in heterogeneous erasure scenario by a tensor-algebraic formulation on top of the DTMC model. Further, the notion of first time drop leads to obtain a dropping distribution. A similar inspection for rDWS is not straight-forward because of receivers' Markov-state dependency. So, the analysis is carried out with respect to Independent Markov-state Model (IMM), and the model is shown to be accurate in most of the cases except the situations where erasure probabilities, number of receivers, field size, target time slot all are very low. Another characterization of the dropping phenomenon helps in establishing the fact, average dropping time strictly decreases with generation size for DWS, and we conjecture, the same holds for rDWS. Using the fundamental matrix concept, we calculate the mean decoding time of a generation for a receiver. Extending the idea of first time dropping to decoding, statistics of different decoding options are analyzed. Finally, some analytical and simulation plots yield, the light-weight rDWS exhibits a very close performance to DWS for a sufficiently large finite field.