2011/02/15 by Bernhard Haeupler, Haeupler, Bernhard, Muriel Médard +1
Computer Science · Engineering · #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Full-Duplex Wireless Communications #Information Theory (cs.IT) #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1102.3204
openalex publication_date 2011/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Random Linear Network Coding (RLNC) has emerged as a powerful tool for robust\nhigh-throughput multicast. Projection analysis - a recently introduced\ntechnique - shows that the distributed packetized RLNC protocol achieves\n(order) optimal and perfectly pipelined information dissemination in many\nsettings. In the original approach to RNLC intermediate nodes code together all\navailable information. This requires intermediate nodes to keep considerable\ndata available for coding. Moreover, it results in a coding complexity that\ngrows linearly with the size of this data. While this has been identified as a\nproblem, approaches that combine queuing theory and network coding have\nheretofore not provided a succinct representation of the memory needs of\nnetwork coding at intermediates nodes.\n This paper shows the surprising result that, in all settings with a\ncontinuous stream of data, network coding continues to perform optimally even\nif only one packet per node is kept in active memory and used for computations.\nThis leads to an extremely simple RLNC protocol variant with drastically\nreduced requirements on computational and memory resources. By extending the\nprojection analysis, we show that in all settings in which the RLNC protocol\nwas proven to be optimal its finite memory variant performs equally well. In\nthe same way as the original projection analysis, our technique applies in a\nwide variety of network models, including highly dynamic topologies that can\nchange completely at any time in an adversarial fashion.\n