Network coding, first studied by Yeung and Zhang and Ahlswede et al., reveals that if coding is applied at the nodes in a network, rather than routing alone, the network capacity can be increased. Li et al. and subsequently Koetter and Medard proved that linear network coding is sufficient to achieve the maximum capacity in a single-source finite acyclic network.
Consequently, linear network coding for single-source finite acyclic networks has been a subject of much research interest. We refer the reader to (see also) for a tutorial on the subject. In this work, they classify linear network codes for single-source finite acyclic networks into four classes: generic; linear dispersion; linear broadcast; linear multicast. These four classes of linear network codes possess properties of decreasing strength.
Although there has been much investigation into various properties of linear network codes with a fixed rate, little research has been undertaken to investigate into the possible relationships among codes with different rates. In our previous work, the linkage among linear broadcasts of different rates was studied and the concept has been adopted by J. Goseling and J. H. Weber for minimum-cost multicasting. This paper is an extension of, and variable-rate linear network coding with link failure is studied for the first time.
This paper is organized as follows. Section 2 presents various classes of linear network code, including linear broadcast. Section 3 presents the concept of variable-rate linear network coding and provides algorithms for efficient implementations of variable-rate linear network coding. In Section 4, the results in Section 3 are extended to the scenario with link failure. Section 5 concludes this paper.
