Introduction of Network Coding Theory

Consider a network consisting of point-to-point communication channels. Each channel transmits information noiselessly subject to the channel capacity. Data is to be transmitted from the source node to a prescribed set of destination nodes. Given the transmission requirements, a natural question is whether the network can fulfill these requirements and how it can be done efficiently. In existing computer networks, information is transmitted from the source node to each destination node through a chain of intermediate nodes by a method known as store-and-forward. In this method, data packets received from an input link of an intermediate node are stored and a copy is forwarded to the next node via an output link. In the case when an intermediate node is on the transmission paths toward multiple destinations, it sends one copy of the data packets onto each output link that leads to at least one of the destinations. It has been a folklore in data networking that there is no need for data processing at the intermediate nodes except for data replication.

Recently, the fundamental concept of network coding was first introduced for satellite communication networks in [211] and then fully

2 Introduction
developed in [158], where in the latter the term “network coding” was coined and the advantage of network coding over store-and-forward was first demonstrated, thus refuting the aforementioned folklore. Due to
its generality and its vast application potential, network coding has generated much interest in information and coding theory, networking, switching, wireless communications, complexity theory, cryptography, operations research, and matrix theory. Prior to [211] and [158], network coding problems for special networks had been studied in the context of distributed source coding [207][177][200][212][211]. The works in [158] and [211], respectively, have inspired subsequent investigations of network coding with a single information source and with multiple information sources. The theory of network coding has been developed in various directions, and new applications of network coding continue to emerge. For example, network coding technology is applied in a prototype file-sharing application [176]1. For a short introduction of the subject, we refer the reader to [173]. For an update of the literature, we refer the reader to the Network Coding Homepage [157]. The present text aims to be a tutorial on the basics of the theory of network coding. The intent is a transparent presentation without necessarily presenting all results in their full generality. Part I is devoted to network coding for the transmission from a single source node to other nodes in the network. It starts with describing examples on network coding in the next section. Part II deals with the problem under the more general circumstances when there are multiple source nodes each intending to transmit to a different set of destination nodes. Compared with the multi-source problem, the single-source network coding problem is better understood. Following [188], the best possible benefits of network coding can very much be achieved when the coding scheme is restricted to just linear transformations. Thus the tools employed in Part I are mostly algebraic. By contrast, the tools employed in Part II are mostly probabilistic. While this text is not intended to be a survey on the subject, we nevertheless provide at <http://dx.doi.org/10.1561/0100000007>

1.2 Some examples

Terminology. By a communication network we shall refer to a finite directed graph, where multiple edges from one node to another are allowed. A node without any incoming edges is called a source node. Any other node is called a non-source node. Throughout this text, in the figures, a source node is represented by a square, while a non-sourc node is represented by a circle. An edge is also called a channel and represents a noiseless communication link for the transmission of a data unit per unit time. The capacity of direct transmission from a node to a neighbor is determined by the multiplicity of the channels between them. For example, the capacity of direct transmission from the node W to the node X in Figure 1.1(a) is 2. When a channel is from a node X to a node Y , it is denoted as XY . A communication network is said to be acyclic if it contains no directed cycles. Both networks presented in Figures 1.1(a) and (b) are examples of acyclic networks. A source node generates a message, which is propagated through the network in a multi-hop fashion. We are interested in how much information and how fast it can be received by the destination nodes.

However, this depends on the nature of data processing at the nodes in relaying the information.

 Fig. 1.1 Multicasting over a communication network.

Assume that we multicast two data bits b1 and b2 from the source node S to both the nodes Y and Z in the  acyclic network depicted by Figure 1.1(a). Every channel carries either the bit b1 or the bit b2 as indicated. In this way, every intermediate node simply replicates and sends out the bit(s) received from upstream. The same network as in Figure 1.1(a) but with one less channel appears in Figures 1.1(b) and (c), which shows a way of multicasting 3 bits b1, b2 and b3 from S to the nodes Y and Z in 2 time units.This achieves a multicast rate of 1.5 bits per unit time, which is actually the maximum possible when the intermediate nodes perform just bit replication (See [209], Ch. 11, Problem 3). The network under discussion is known as the butterfly network. Example 1.1. (Network coding on the butterfly network) Figure 1.1(d) depicts a different way to multicast two bits from the source node S to Y and Z on the same network as in Figures 1.1(b) and (c). This time the node W derives from the received bits b1 and b2 the exclusive-OR bit b1  b2. The channel from W to X transmits b1  b2, which is then replicated at X for passing on to Y and Z. Then, the node Y receives b1 and b1  b2, from which the bit b2 can be decoded. Similarly, the node Z decodes the bit b1 from the received bits b2 and b1  b2. In this way, all the 9 channels in the network are used exactly once. The derivation of the exclusive-OR bit is a simple form of coding. If the same communication objective is to be achieved simply by bit replication at the intermediate nodes without coding, at least one channel in the network must be used twice so that the total number of channel usage would be at least 10. Thus, coding offers the potential advantage of minimizing both latency and energy consumption, and at the same time maximizing the bit rate.