Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems

In this paper, we investigate the use of instantly decodable network coding for improving two fundamental performance metrics, namely the completion time (as a measure of throughput) and mean decoding delay, in multicast cooperative data exchange systems, where a group of geographically close clients cooperate with each other to obtain their missing packets. Here, an instantly decodable network coding scheme is used for the transmissions across these clients. We utilize the stochastic shortest path technique to study the minimum mean completion time problem. However, since finding the optimum solution is intractable, we use the obtained formulation to draw some theoretical guidelines to heuristically find solutions that can efficiently reduce the completion time. Second, we formulate the minimum mean decoding delay problem as selecting the appropriate maximal clique over well structured graphs at the clients, and in order to reduce its complexity, propose a simple heuristic algorithm for it. The effectiveness of our proposed algorithms is verified through extensive simulations and comparisons with existing techniques