Network Coding

Consider a large network with one source and one destination node and edges with unit capacity. It is known that the point-to-point capacity of such network can be achieved by routing a single bit. Such simple scheme does not achieve the capacity of the network when a single source communicates to many receivers. However, the multicast theorem in network coding shows that, the common min-cut value towards N> 1 receivers can be achieved using packets of length log Nbits and linear operations at intermediate nodes, if the operations are deterministically known at the receivers.

In practical networks, where such deterministic knowledge is not sustainable, the most popular approaches are to append coding vectors at the headers of the packets to keep track of the operations performed on the source packets, or using algebraic subspace coding constructions which does not need the coding vector overheads. In this work we examine what are the information theoretical rates that can be achieved in a network where the intermediate node operations are unknown.