Design of efficient robust network codes for multicast connections

We consider the problem of establishing reliable multicast connections across a communication network. Our goal is to provide instantaneous recovery from single edge failures. With instantaneous recovery, all destination nodes can decode the packets sent by the source node even if one of the edges in the network fails, without the need of retransmission or rerouting. We build on the novel technique of network coding that offers significant advantages over standard solutions such as disjoint path routing and diversity coding. We begin by focusing on the case in which all network edges have equal capacity. For this case we present a network coding algorithm that constructs a robust network code over a small field. The algorithm takes advantage of special properties of the Maximum Rank Distance codes. Second, we consider a case of non-uniform edge capacities. We show that for the special case in which a small number of packets need to be transmitted from the source to destination nodes, special combinatorial properties of minimum coding networks can be exploited for constructing efficient robust network codes.