Random linear network codes can be designed and implemented in a distributed manner, with low computational complexity. However, these codes are classically implemented [1] over finite fields whose size depends on some global network parameters (size of the network, the number of sinks) that may be unknown prior to code design. Also, the entire network code may have to be redesigned when a new node joins. In this work, we present the first universal and robust distributed linear network coding schemes. Our schemes are universal since they are independent of all network parameters. They are robust since in case nodes join or leave, the remaining nodes do not need to change their coding operations and the receivers can still decode. They are distributed since nodes need only have topological information about the part of the network upstream of them, which can be naturally streamed as part of the communication protocol. We present both probabilistic and deterministic schemes that are all asymptotically rate-optimal in the coding block length, and have guarantees of correctness. Our probabilistic designs are computationally efficient, with order-optimal com plexity. Our deterministic designs guarantee zero error decoding, albeit via codes with high computational complexity in general. Our coding schemes are based on network codes over "scalable fields". Instead of choosing coding coefficients from one field at every node as in [1], each node uses linear coding operations over an "effective field-size" which depends on the node's distance from the source node. The analysis of our schemes requires technical tools that may be of independent interest. In particular, we generalize the Schwartz-Zippel lemma [2] by proving a non uniform version, wherein variables are chosen from sets of possibly different sizes. We also provide a novel robust distributed algorithm to assign unique IDs to network nodes. The paradigm of network coding allows each node in a network to process information in a non-trivial manner. As shown in [3] , [4] , [5] , if intermediate nodes simply perform linear operations over some finite field, the resulting network codes can be rate-optimal for a large class of communication problems. In particular, algorithms that generate codes for multicast communication problems, wherein each of multiple sinks requires the same information from a source node, have been well-studied. computationally efficient deterministic [6], [7] and probabilistic [1], [8] designs of such codes exist. However, for all current network codes, some information of network parameters is necessary to determine the size of The authors are listed in alphabetical order.
Reference REF discussed the influence of joining nodes in the network.
Universal and robust distributed network codes
2011 Proceedings IEEE INFOCOM
2011 Proceedings IEEE INFOCOM
Mathematics Computer Science