Robust Network Coding for Bidirected Networks
Alex Sprintson, Salim Y. El Rouayheb, C.N. Georghiades · 2007
We consider the problem of finding a linear network code that guarantees an instantaneous recovery from edge failures in communication networks. With instantaneous recovery, lost data can be recovered at the destination without the need for path re-routing or packet re-transmission. We focus on a special class of bidirected networks. In such networks, for each edge there exists a corresponding edge in the reverse direction of equal capacity. We assume that at most one pair of bidirected edges can fail at any time. For unicast connections, we establish an upper bound ofO(22h) on the minimum required field size and present an algorithm that constructs a linear network code overGF(22h). For multicast connections, we show that the minimum required field size is bounded by O (tldr 22h), wheretis the number of terminals. We also discuss link- and flow-cyclic bidirected coding networks with instantaneous recovery.