Completion Delay Minimization for Instantly Decodable Network Codes

Details Completion Delay Minimization for Instantly Decodable Network Codes Completion Delay Minimization for Instantly Decodable Network Codes

2012-01-23

arxiv.org/abs/1201.4768v1

Computer Science

Networking and Internet Architecture

Scientific paper

In this paper, we consider the problem of minimizing the completion delay for instantly decodable network coding (IDNC), in wireless multicast and broadcast scenarios. We are interested in this class of network coding due to its numerous benefits, such as low decoding delay, low coding and decoding complexities and simple receiver requirements. We first extend the IDNC graph, which represents all feasible IDNC coding opportunities, to efficiently operate in both multicast and broadcast scenarios. We then formulate the minimum completion delay problem for IDNC as a stochastic shortest path (SSP) problem. Although finding the optimal policy using SSP is intractable, we use this formulation to draw the theoretical guidelines for the policies that can efficiently reduce the completion delay in IDNC. Based on these guidelines, we design a maximum weight clique selection algorithm, which can efficiently reduce the IDNC completion delay in polynomial time. We also design a quadratic time heuristic clique selection algorithm, which can operate in real-time applications. Simulation results show that our proposed algorithms efficiently reduce the IDNC completion delay compared to the random and maximum-rate algorithms, and almost achieve the global optimal completion delay performance over all network codes in broadcast scenarios.

Affiliated with

Also associated with

No associations

Rating

Completion Delay Minimization for Instantly Decodable Network Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Completion Delay Minimization for Instantly Decodable Network Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Completion Delay Minimization for Instantly Decodable Network Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498170