One packet suffices - Highly efficient packetized Network Coding with finite memory
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 setti...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121161 |
| _version_ | 1811068218426523648 |
|---|---|
| author | Haeupler, Bernhard Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Haeupler, Bernhard Medard, Muriel |
| author_sort | Haeupler, Bernhard |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T07:53:05Z |
| format | Article |
| id | mit-1721.1/121161 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:53:05Z |
| publishDate | 2019 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1211612022-09-23T09:25:26Z One packet suffices - Highly efficient packetized Network Coding with finite memory Haeupler, Bernhard Medard, Muriel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Haeupler, Bernhard 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. 2019-05-20T14:48:05Z 2019-05-20T14:48:05Z 2011-10 2011-08 Article http://purl.org/eprint/type/ConferencePaper 978-1-4577-0595-3 2157-8095 2157-8117 https://hdl.handle.net/1721.1/121161 Haeupler, Bernard and Muriel M´edard. "One packet suffices - Highly efficient packetized Network Coding with finite memory." 2011 IEEE International Symposium on Information Theory Proceedings, July - August 2011, St. Petersburg, Russia, Institute of Electrical and Electronics Engineers (IEEE), October 2011. © 2011 IEEE en_US http://dx.doi.org/10.1109/ISIT.2011.6033713 2011 IEEE International Symposium on Information Theory Proceedings Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Haeupler, Bernhard Medard, Muriel One packet suffices - Highly efficient packetized Network Coding with finite memory |
| title | One packet suffices - Highly efficient packetized Network Coding with finite memory |
| title_full | One packet suffices - Highly efficient packetized Network Coding with finite memory |
| title_fullStr | One packet suffices - Highly efficient packetized Network Coding with finite memory |
| title_full_unstemmed | One packet suffices - Highly efficient packetized Network Coding with finite memory |
| title_short | One packet suffices - Highly efficient packetized Network Coding with finite memory |
| title_sort | one packet suffices highly efficient packetized network coding with finite memory |
| url | https://hdl.handle.net/1721.1/121161 |
| work_keys_str_mv | AT haeuplerbernhard onepacketsufficeshighlyefficientpacketizednetworkcodingwithfinitememory AT medardmuriel onepacketsufficeshighlyefficientpacketizednetworkcodingwithfinitememory |