Title :
One packet suffices - Highly efficient packetized Network Coding With finite memory
Author :
Haeupler, Bernhard ; Médard, Muriel
Author_Institution :
RLE, Massachusetts Inst. of Technol., Cambridge, MA, USA
fDate :
July 31 2011-Aug. 5 2011
Abstract :
Random Linear Network Coding (RLNC) has emerged as a powerful tool for robust high-throughput multicast. Projection analysis, a recently introduced technique, shows that the distributed packetized RLNC protocol achieves (order) optimal and perfectly pipelined information dissemination in many settings. In the original approach to RNLC intermediate nodes code together all available information. This requires intermediate nodes to keep considerable data available for coding. Moreover, it results in a coding complexity that grows linearly with the size of this data. While this has been identified as a problem, approaches that combine queuing theory and network coding have heretofore not provided a succinct representation of the memory needs of network coding at intermediates nodes. This paper shows the surprising result that, in all settings with a continuous stream of data, network coding continues to perform optimally even if only one packet per node is kept in active memory and used for computations. This leads to an extremely simple RLNC protocol variant with drastically reduced requirements on computational and memory resources. By extending the projection analysis, we show that in all settings in which the RLNC protocol was proven to be optimal its finite memory variant performs equally well. In the same way as the original projection analysis, our technique applies in a wide variety of network models, including highly dynamic topologies that can change completely at any time in an adversarial fashion.
Keywords :
information dissemination; linear codes; network coding; queueing theory; random codes; RNLC intermediate node code; coding complexity; computational resource; distributed packetized RLNC protocol; dynamic topology; finite memory variant; high-throughput multicast; memory resource; one packet suffices-highly efficient packetized network coding; pipelined information dissemination; projection analysis; queuing theory; random linear network coding; Encoding; Memory management; Network coding; Network topology; Protocols; Topology;
Conference_Titel :
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
Conference_Location :
St. Petersburg
Print_ISBN :
978-1-4577-0596-0
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2011.6033713