Source-linked AI summary
Completion Delay Minimization for Instantly Decodable Network Codes
Sameh Sorour, Shahrokh Valaee
TL;DR
The paper asks how to reduce expected IDNC completion delay over erasure channels in multicast and broadcast. It extends the IDNC graph, uses an intractable stochastic-shortest-path formulation to derive policy guidance, and designs maximum-weight clique algorithms. The proposed heuristics track optimal clique selection closely, and broadcast performance nearly reaches the global optimum over network codes.
Problem
The paper asks how to reduce expected IDNC completion delay over erasure channels in multicast and broadcast, beyond prior attention to decoding-receiver counts and erasure-less index coding.
Source: §I · p. 2Method
The paper extends the IDNC graph to multicast and broadcast, formulates completion-delay minimization as an SSP problem, and designs polynomial-time and quadratic-time clique-selection algorithms from its policy properties.
Source: §I · p. 2Results
The heuristic tracks optimal clique selection with less than 5% degradation except for large receiver counts, while broadcast algorithms nearly achieve globally optimal random-network-coding performance and outperform random and maximum-clique algorithms.
Source: §X · p. 10, §XI · p. 11Takeaways & Limitations
Reducing completion delay calls for prioritizing receivers with higher demands and worse channels rather than maximizing the number of decoders in each transmission.
Source: §I · p. 2
Abstract
from arXiv · showhide
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.
I. INTRODUCTION AND MOTIVATION
The paper studies reducing IDNC completion delay over erasure channels, where receiver service order and evolving coding opportunities matter beyond maximizing decoders per transmission. It positions this problem across prior work on index coding and rate maximization, then defines a feedback-driven multicast/broadcast delivery model.
II. RELATED WORK
- Prior IDNC and ONC work emphasized decoding receivers or achievable rates, while completion-delay work addressed erasure-less index coding rather than dynamic erasure channels.With erasures, receiver feedback changes probabilistically after each transmission, requiring packet schedules to be updated dynamically.Source: §I · p. 2, §II · p. 2
I. INTRODUCTION AND MOTIVATION
- Completion-delay policy should prioritize receivers with higher demands and worse channels, because maximizing the number of decoders per transmission alone is not sufficient.The paper identifies receiver service order and the evolution of coding opportunities as key factors; its contribution is framed as the first rigorous study of IDNC completion-delay reduction over erasure channels.Source: §I · p. 2
III. SYSTEM MODEL AND PARAMETERS
- The sender delivers a packet frame to multicast receivers requesting subsets or broadcast receivers requesting all packets, using feedback to update receiver state until all requested packets arrive.Completion delay is the number of recovery transmissions needed after the initial uncoded phase; receiver erasure and success probabilities are assumed constant during frame transmission.Source: §III · p. 3
IV. IDNC GRAPH
The IDNC graph represents feasible instantly decodable packet combinations, and maximal cliques identify combinations the sender can transmit. The paper also introduces an SSP model in which states, actions, transitions, and costs describe completion delay.
IV. IDNC GRAPH
- Each vertex represents a requested packet, while edges encode packet pairs satisfying either of the stated compatibility conditions.A clique therefore groups packets that can be combined while preserving instant decodability.Source: §IV · p. 3
- Maximal cliques represent all feasible packet combinations, which the sender forms by XORing their packets.A maximal clique is one not contained in a larger clique.Source: §IV · p. 3
- The two-layer IDNC graph adds secondary-packet vertices to the primary graph, connects vertices under the same compatibility conditions, and has construction complexity O(M^2N).The primary layer represents requested packets; the secondary layer represents packets outside each receiver’s Wants set.Source: §IV · p. 3
A. The SSP Problem
- A stochastic shortest path models terminating stochastic decisions, with the optimal policy minimizing cumulative mean cost until absorption.Its value function is expected cumulative cost until absorption, and the optimal action is defined over successor states.Source: A. The SSP Problem · p. 4
B. Problem Formulation
The completion-delay problem is formulated as an SSP over feedback-matrix states, with maximal cliques as actions and packet receptions governing transitions. Each transmission incurs one time-slot of cost, while computing an optimal policy is difficult in real time for typical system sizes.
B. Problem Formulation
- The paper formulates expected completion-delay minimization in IDNC as a stochastic shortest path problem.This formulation uses the recovery-phase system states, feasible actions, transition probabilities, and costs.Source: B. Problem Formulation · p. 4
- States represent possible feedback matrices, characterized by Has, Lacks, and Wants vectors; absorbing states have Wants vector ψ0.The state space has size O(2^MN) as printed in the passage.Source: 1) State Space S · p. 4
- Each state’s action space consists of the maximal cliques in its IDNC graph.Source: 2) Action Spaces A(s) · p. 4
3) State-Action Transition Probabilities
- Transitions depend on which targeted receivers successfully receive the coded packet and which lose it.The transition-probability expression is defined using sets for these two receiver outcomes.Source: 3) State-Action Transition Probabilities · p. 4
- Figure 2 illustrates the example’s states and actions, along with possible transitions when action a7 is taken.Source: 3) State-Action Transition Probabilities · p. 4
4) State-Action Costs
- Every action costs one time-slot because each process transition corresponds to one packet transmission.Accordingly, the cost of every action in every state is set to 1.Source: 4) State-Action Costs · pp. 4–5
C. SSP Solution Complexity
- Computing the optimal SSP policy is very difficult in real time for typical values of M and N.Even the cited simulation-based technique remains impractical in real time because its complexity scales with |S|.Source: C. SSP Solution Complexity · p. 5
VI. SSP PROPERTIES
The SSP structure suggests prioritizing actions that move toward completion and leave useful coding opportunities in successor states. The geometric analysis refines this guidance by weighting receiver Wants and channel erasures when choosing whom to serve.
VI. SSP PROPERTIES
- With uniform action costs and no cycles longer than singleton self-loops, successor states have expected costs no greater than their predecessor.The optimal action favors transitions with high probability of reaching states with minimum expected residual completion delay.Source: §VI · p. 5
- The value of a successor state depends on its distance from the absorbing Wants vector and the number and sizes of maximal cliques in its primary graph.The policy should move Wants vectors closer to absorption while maximizing coding opportunities in successor primary graphs.Source: §VI · p. 5
- The optimal value functions have no closed-form expression in IDNC, so accurately determining the optimal policy requires solving the SSP.Source: §VI · p. 5
VII. GEOMETRIC STRUCTURE
- In the erasure-free example, from Wants vector [2, 1, 1], a3 leads to, closer to absorption than a5’s [2, 0, 0]; minimizing the maximum Wants entry brings the system closest to absorption.Source: §VII · p. 6
- When actions tie on the maximum successor Wants entry, serving an additional receiver with a smaller Wants set can still bring the system closer to absorption.Norm-based weighting gives greater priority to receivers with larger coordinate entries; larger norms bias that weighting more strongly.Source: §VII · p. 6
- For equal Wants-set sizes, a receiver with higher packet-erasure probability requires more targeting attempts on average than one with lower probability.The passage says targeting the lower-erasure receiver while ignoring the higher-erasure one is expected to result in higher overall completion delay.Source: §VII · p. 6
- Channel-weighted Wants values give higher service priority to receivers with larger values of eψi.The geometric representation uses these channel-weighted values as its coordinates, with side lengths q_i^-1.Source: §VII · p. 6
- The policy seeks successor states closest to the absorbing point under the geometric distance, while also checking whether receiver prioritization preserves coding opportunities.The analysis proposes investigating whether norm-based receiver selection also maximizes successor-state coding opportunities.Source: §VII · pp. 6–7
VIII. EVOLUTION OF CODING OPPORTUNITIES
The section treats primary-graph edge count as a measure of coding opportunities relevant to completion-delay reduction. It extends an earlier broadcast analysis to multicast and states a theorem for expected next-step edge count.
VIII. EVOLUTION OF CODING OPPORTUNITIES
- The number of edges in the primary IDNC graph represents its coding opportunities, which are identified as a factor in reducing completion delay.Source: §VIII · p. 7
- The section extends an earlier broadcast study of expected edge count to wireless multicast, where its analysis first introduces a theorem.The earlier study ignored packet content and computed expected edge-set size from set cardinalities.Source: §VIII · p. 7
- For a chosen maximal clique in multicast, Theorem 1 expresses the expected cardinality of the next time step’s primary-graph edge set.The proof is located in Appendix A.Source: §VIII · p. 7
A. Causal Evolution
The expected edge-set size evolves causally across transmissions, while receiver disappearance creates an unavoidable loss. The analysis identifies targeting choices that increase or preserve future coding opportunities.
A. Causal Evolution
- The expected edge-set size at time t depends on its prior size, so maximizing it in a successor state benefits later states when the same policy is reused.The edge-set-size evolution is causal across transmission steps.Source: A. Causal Evolution · p. 7
B. Vertex Disappearance
- Serving receivers with larger Wants sets and erasure probabilities, and smaller Has sets, reduces edge-set loss when targeted vertices disappear.The disappearance loss cannot be reduced by shrinking the primary targeted set without tending to increase expected completion delay.Source: B. Vertex Disappearance · p. 7
C. Degrees of Remaining Vertices
- Targeting receivers with larger Wants sets increases the degrees of remaining vertices, while secondary targeting favors larger Wants sets and lower erasure probabilities.For every receiver, the degree increase is at least as large when targeted as when not targeted; under equal demand ratios, prioritizing receivers with smaller reception probabilities on average increases both degree-change terms.Source: C. Degrees of Remaining Vertices · pp. 7–8
D. Overall Maximization Strategy
The WoRLT strategy prioritizes receivers to maximize expected future graph size, and the paper implements it with clique-selection methods. A greedy vertex-search heuristic offers a lower-complexity alternative.
D. Overall Maximization Strategy
- WoRLT targets receivers with the largest Wants sets and erasure probabilities using primary packets, then targets remaining receivers with large Wants sets and lower erasure probabilities using secondary packets.This strategy is presented as an efficient way to reduce IDNC completion delay.Source: D. Overall Maximization Strategy · p. 8
A. Maximum Weight Clique Selection Algorithm
- The two-step maximum weight clique algorithm selects primary and then connected secondary cliques to maximize channel-weighted Wants-set size and expected successor graph edges.The selected cliques determine the source packets XORed into the transmitted IDNC packet.Source: A. Maximum Weight Clique Selection… · p. 8
B. Maximum Weight Vertex Search Algorithm
- The greedy maximum weight vertex search builds primary and secondary cliques iteratively and has complexity O(M^2N).It recomputes weights within the subgraph adjacent to the vertices already selected.Source: B. Maximum Weight Vertex Search… · p. 9
X. SIMULATION RESULTS
Across the comparison parameters, the proposed maximum weight clique algorithms outperform random and maximum-clique IDNC selection. Their heuristic versions closely track optimal clique selection, while broadcast performance approaches the global optimum of random network coding.
X. SIMULATION RESULTS
- The proposed maximum weight clique algorithms considerably outperform RND and MC in average completion delay across µ, M, N, and p; the heuristics stay within 5% of optimal except for large receiver counts.The heuristic also considerably improves on both optimal and heuristic MC algorithms.Source: Figure 4 · p. 9, Figure 5 · p. 9, §X · pp. 9–10
- For norms above L1, performance tends toward the smallest completion delays achieved by L3 and L5, while L10 slightly degrades across comparison parameters.The L1 algorithm performs worse than the other norms because it represents a very loose upper bound of Vπ∗(s).Source: §X · p. 10
- For broadcast, the proposed algorithm's maximum degradation from optimal random network coding is less than 5%, occurring only at very high receiver counts.The paper states this near-optimality preserves IDNC's benefits compared with perfect RNC.Source: §X · p. 10
XI. CONCLUSION
The paper formulates IDNC completion-delay minimization as an intractable stochastic shortest path problem, then derives policies and algorithms from its properties. Simulations show strong performance against IDNC baselines and near-global-optimal broadcast performance.
XI. CONCLUSION
- The minimum completion-delay problem for IDNC is formulated as a stochastic shortest path problem, whose optimal solution is intractable.The paper uses properties of the formulation and IDNC graph evolution to derive efficient delay-reducing policies.Source: §XI · pp. 10–11
- The proposed maximum weight clique algorithm runs in polynomial time, and its quadratic-time heuristic tracks optimal performance while outperforming random and maximum-clique algorithms.Source: §XI · p. 11
- In broadcast, the proposed algorithms almost attain globally optimal random-network-coding completion delay while retaining IDNC's benefits and simplicity.Source: §XI · p. 11
APPENDIX A PROOF OF THEOREM 1
These appendices establish expected primary-graph quantities used in the theorem proofs: edge-set cardinality and primary degrees. The proofs condition on packet receptions and use a nonnegative term to establish the stated theorem.
APPENDIX A PROOF OF THEOREM 1
- For given ϕ and ψ vectors, Theorem 4 states that the expected edge-set cardinality of the primary graph is equal to a specified expression.The proof first introduces two theorems, proved in Appendices D and E, respectively.Source: Appendix A · p. 11
- Theorem 5 expresses the expected primary degree of a vertex belonging to a targeted receiver after a maximal-clique transmission.The proof conditions on the targeted receivers’ packet-reception outcomes, then takes expectation over those outcomes.Source: Appendix A · p. 11
APPENDIX B PROOF OF THEOREM 2
- Theorem 6 gives the expected primary degree of vertices induced by receiver i for given ϕ and ψ vectors.The proof expands the expression in (25).Source: Appendix B · p. 12
APPENDIX C PROOF OF THEOREM 3
- Theorem 3 follows because, for ψk > 0 and ψk > qk, the last term in (28) is non-negative.The proof rearranges the expression using the definition of βi in (11).Source: Appendix C · p. 12
APPENDIX D PROOF OF THEOREM 4
Appendix D derives the expected primary-graph edge count using vertex degrees and expected set intersections. Appendix E derives a targeted receiver’s expected primary degree after a maximal-clique transmission.
APPENDIX D PROOF OF THEOREM 4
- Theorem 4 uses the graph identity that edge-set size is half the sum of vertex degrees to derive the expected primary-graph edge count.The proof treats intersections of unknown sets drawn from the same pool as hypergeometric random variables.Source: Appendix D · p. 12
- When the indicator for packet j is one, j cannot belong to Wk ∩ Li, so the intersection can involve only the other ϕi − 1 packets among N − 1 remaining packets.This restriction is used to evaluate the expectation involving the indicator and the intersection size.Source: Appendix D · pp. 12–13
APPENDIX E PROOF OF THEOREM 5
- Appendix E derives the expected primary degree of a targeted receiver after serving maximal clique κ, identifying the first term as that receiver’s expected degree at time t.The derivation conditions on the reception vector X defined in Appendix A.Source: Appendix E · p. 13
APPENDIX F PROOF OF THEOREM 6
Appendix F derives a primary-degree expression from the graph’s adjacency conditions, then uses it to obtain the expected primary degree of a receiver’s vertices.
APPENDIX F PROOF OF THEOREM 6
- Vertices induced by the same receiver are not adjacent, and the adjacency conditions restrict links to vertices induced by other receivers.For j ∈ Wk, adjacency to primary vertices of receiver k is excluded except for vkj; for j ∈ Rk, certain vertices induced from Li are excluded.Source: Appendix F · p. 13
- The proof expresses the primary degree of vertex vij using indicators for packet membership and the size of Wk minus its intersection with Li.The indicator function equals one when its condition is true and zero otherwise.Source: Appendix F · p. 13
- The expected primary degree is derived by ignoring the content of the different sets, then substituting (31) into (38) and rearranging.Source: Appendix F · pp. 13–14