Completion Delay Minimization for Instantly Decodable Network Coding with Limited Feedback

In this paper, we consider the problem of minimizing the broadcast completion delay for instantly decodable network coding with limited feedback. We first extend the stochastic shortest path formulation of the full feedback scenario in [1] to the limited feedback scenario. We then show that the resulting formulation is more complicated to solve than the original one but has its same properties and structure. Based on this result, we design four variants of the algorithms employed in [1] with four different approaches to deal with un-acknowledged transmissions. We finally compare these four algorithms through extensive simulations and show that the algorithm that temporarily avoids all un-acknowledged transmissions in subsequent coding decisions and transmissions can result in a tolerable degradation compared to the full feedback performance while using a much lower feedback frequency.