Delay Reduction in Persistent Erasure Channels for Generalized Instantly Decodable Network Coding

In this paper, we consider the problem of minimizing the decoding delay of generalized instantly decodable network coding (G-IDNC) in persistent erasure channels (PECs). By persistent erasure channels, we mean erasure channels with memory, which are modeled as a Gilbert-Elliott two-state Markov model with good and bad channel states. In this scenario, the channel erasure dependence, represented by the transition probabilities of this channel model, is an important factor that could be exploited to reduce the decoding delay. We first formulate the G-IDNC minimum decoding delay problem in PECs as a maximum weight clique problem over the G-IDNC graph. Since finding the optimal solution of this formulation is NP-hard, we propose two heuristic algorithms to solve it and compare them using extensive simulations. Simulation results show that each of these heuristics outperforms the other in certain ranges of channel memory levels. They also show that the proposed heuristics significantly outperform both the optimal strict IDNC in the literature and the channel-unaware G-IDNC algorithms.