Strategies for Optimal Transmission and Delay Reduction in Dynamic Index Coding Problem

Dynamic index coding is a practical generalization of conventional index coding that deals with real dynamic traffic streams. We identify the code-constrained capacity region of a dynamic index coding problem with a complete bi-directional side information graph and introduce the performance metric of dynamic index coding gain to measure how dynamic index coding reduces the required data transmissions. A greedy dynamic index coding scheme is proposed that achieves the maximum coding gain almost everywhere in the identified capacity region. Although the greedy scheme attains the maximum coding gain, its selfish nature may unacceptably increase transmission delay. To address this issue, a time-shared friendly dynamic index coding scheme is introduced that achieves the maximum coding gain over the entire capacity region and offers a lower delay than its greedy counterpart. To obtain the minimum delay, a constrained optimization problem is formulated to tune time-sharing weights in the friendly scheme. The closed-form solution of the optimization is derived for the special two-flow case. Furthermore, the results and analysis are extended to dynamic index coding problems with arbitrary side information graphs. We also use analytical and simulation results to provide graphical intuition for the obtained results.

Automated summary

Dynamic index coding is a practical extension of traditional index coding for handling real traffic streams. Our work focuses on identifying the code-constrained capacity region and introducing the performance metric of dynamic index coding gain. We propose a greedy scheme and a time-shared friendly scheme, with the latter achieving maximum coding gain and lower delay. We also provide a closed-form solution for the optimization problem in the two-flow case and extend the results to problems with arbitrary side information graphs. Analytical and simulation results are used to provide graphical intuition.