Random Linear Network Coding Schemes for Reduced Zero-Padding Overhead: Complexity and Overhead Analysis

Conference: European Wireless 2017 - 23th European Wireless Conference
05/17/2017 - 05/19/2017 at Dresden, Germany

Proceedings: European Wireless 2017

Pages: 7Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Authors:
Taghouti, Maroua (Tunisia Polytechnic School, University of Carthage, Tunisia & Deutsche Telekom Chair of Communication Networks, Technische Universität Dresden, Germany & Communications Systems Laboratory, National Engineering School of Tunis, University of Tunis El Manar, Tunisia)
Lucani, Daniel (Department of Engineering, Aarhus University, Aarhus 8200, Denmark)
Fitzek, Frank H. P. (Deutsche Telekom Chair of Communication Networks, Technische Universität Dresden, Germany)
Bouallegue, Ammar (Communications Systems Laboratory, National Engineering School of Tunis, University of Tunis El Manar, Tunisia)

Abstract:
The zero-padding overhead created when performing Random Linear Network Coding (RLNC) on unequal-sized packets can curb its promising benefits since it can be as high as the data to convey. The concept of macro-symbol coding was introduced recently in order to reduce the zero-padding overhead that RLNC has brought. Macro-symbols are subsets of the packets, i.e. concatenated bytes. They allow performing coding mainly on the payload and they proved to be efficient against the naive padding. This paper studies the properties of macro-symbols and provides a characterization of their impact on the computational complexity as well as the overall overhead. Furthermore, we provide a theoretical framework for the encoding and decoding complexity for the state-of-the-art schemes for unequal-sized packets. Our simulations results performed on a series of benchmark video traces show that small macro-symbols guarantee a dramatic reduction of padding overhead, whilst it results on a higher decoding complexity on the other hand compared with RLNC in the worst case.