Random linear network coding for streams with unequally sized packets: Overhead reduction without zero-padded schemes

Maroua Taghouti, Daniel Enrique Lucani Roetter, Morten Videbæk Pedersen, Ammar Bouallegue

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

4 Citations (Scopus)

Abstract

State of the art Random Linear Network Coding (RLNC) schemes assume that data streams generate packets with equal sizes. This is an assumption that results in the highest efficiency gains for RLNC. A typical solution for managing unequal packet sizes is to zero-pad the smallest packets. However, the efficiency of this strategy depends heavily on the packet size distribution and can significantly curb the gains of network coding in practice. The work by Compta et al. showed that this strategy could introduce an overhead as high as 100\% for Internet traffic. Our work advocates for an alternative encoding and decoding designs, focused on processing macro-symbols (composed by a number of symbols in the appropriate finite field) instead of full zero-padded packets. Our proposed schemes provide on-the-fly decoding strategies to manage heterogeneous packet sizes without the need for fragmentation or bundling of packets, which are strategies that require additional signalling. Performance is evaluated using CAIDA TCP packets and 4k video traces. Our results show that our mechanisms reduce significantly the padding overhead even for small field sizes. Finally, our strategies provide a natural trade-off between computational complexity and overhead due to the low density of the code when decoded at a macro-symbol level.
Original languageEnglish
Title of host publication23rd International Conference on Telecommunications (ICT), 2016
Number of pages6
PublisherIEEE
Publication date2016
ISBN (Electronic)978-1-5090-1990-8
DOIs
Publication statusPublished - 2016
EventICT 2016 - Thessaloniki, Greece
Duration: 16 May 201618 May 2016
Conference number: 23
http://ict-2016.org/

Conference

ConferenceICT 2016
Number23
CountryGreece
CityThessaloniki
Period16/05/201618/05/2016
Internet address

Fingerprint

Linear networks
Network coding
Macros
Decoding
Curbs
Computational complexity
Internet
Processing

Cite this

Taghouti, M., Roetter, D. E. L., Pedersen, M. V., & Bouallegue, A. (2016). Random linear network coding for streams with unequally sized packets: Overhead reduction without zero-padded schemes. In 23rd International Conference on Telecommunications (ICT), 2016 IEEE. https://doi.org/10.1109/ICT.2016.7500495
Taghouti, Maroua ; Roetter, Daniel Enrique Lucani ; Pedersen, Morten Videbæk ; Bouallegue, Ammar. / Random linear network coding for streams with unequally sized packets : Overhead reduction without zero-padded schemes. 23rd International Conference on Telecommunications (ICT), 2016. IEEE, 2016.
@inproceedings{41f7409a5f13474ca8cfc72728c94e62,
title = "Random linear network coding for streams with unequally sized packets: Overhead reduction without zero-padded schemes",
abstract = "State of the art Random Linear Network Coding (RLNC) schemes assume that data streams generate packets with equal sizes. This is an assumption that results in the highest efficiency gains for RLNC. A typical solution for managing unequal packet sizes is to zero-pad the smallest packets. However, the efficiency of this strategy depends heavily on the packet size distribution and can significantly curb the gains of network coding in practice. The work by Compta et al. showed that this strategy could introduce an overhead as high as 100\{\%} for Internet traffic. Our work advocates for an alternative encoding and decoding designs, focused on processing macro-symbols (composed by a number of symbols in the appropriate finite field) instead of full zero-padded packets. Our proposed schemes provide on-the-fly decoding strategies to manage heterogeneous packet sizes without the need for fragmentation or bundling of packets, which are strategies that require additional signalling. Performance is evaluated using CAIDA TCP packets and 4k video traces. Our results show that our mechanisms reduce significantly the padding overhead even for small field sizes. Finally, our strategies provide a natural trade-off between computational complexity and overhead due to the low density of the code when decoded at a macro-symbol level.",
author = "Maroua Taghouti and Roetter, {Daniel Enrique Lucani} and Pedersen, {Morten Videb{\ae}k} and Ammar Bouallegue",
year = "2016",
doi = "10.1109/ICT.2016.7500495",
language = "English",
booktitle = "23rd International Conference on Telecommunications (ICT), 2016",
publisher = "IEEE",
address = "United States",

}

Taghouti, M, Roetter, DEL, Pedersen, MV & Bouallegue, A 2016, Random linear network coding for streams with unequally sized packets: Overhead reduction without zero-padded schemes. in 23rd International Conference on Telecommunications (ICT), 2016. IEEE, ICT 2016, Thessaloniki, Greece, 16/05/2016. https://doi.org/10.1109/ICT.2016.7500495

Random linear network coding for streams with unequally sized packets : Overhead reduction without zero-padded schemes. / Taghouti, Maroua; Roetter, Daniel Enrique Lucani; Pedersen, Morten Videbæk; Bouallegue, Ammar.

23rd International Conference on Telecommunications (ICT), 2016. IEEE, 2016.

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Random linear network coding for streams with unequally sized packets

T2 - Overhead reduction without zero-padded schemes

AU - Taghouti, Maroua

AU - Roetter, Daniel Enrique Lucani

AU - Pedersen, Morten Videbæk

AU - Bouallegue, Ammar

PY - 2016

Y1 - 2016

N2 - State of the art Random Linear Network Coding (RLNC) schemes assume that data streams generate packets with equal sizes. This is an assumption that results in the highest efficiency gains for RLNC. A typical solution for managing unequal packet sizes is to zero-pad the smallest packets. However, the efficiency of this strategy depends heavily on the packet size distribution and can significantly curb the gains of network coding in practice. The work by Compta et al. showed that this strategy could introduce an overhead as high as 100\% for Internet traffic. Our work advocates for an alternative encoding and decoding designs, focused on processing macro-symbols (composed by a number of symbols in the appropriate finite field) instead of full zero-padded packets. Our proposed schemes provide on-the-fly decoding strategies to manage heterogeneous packet sizes without the need for fragmentation or bundling of packets, which are strategies that require additional signalling. Performance is evaluated using CAIDA TCP packets and 4k video traces. Our results show that our mechanisms reduce significantly the padding overhead even for small field sizes. Finally, our strategies provide a natural trade-off between computational complexity and overhead due to the low density of the code when decoded at a macro-symbol level.

AB - State of the art Random Linear Network Coding (RLNC) schemes assume that data streams generate packets with equal sizes. This is an assumption that results in the highest efficiency gains for RLNC. A typical solution for managing unequal packet sizes is to zero-pad the smallest packets. However, the efficiency of this strategy depends heavily on the packet size distribution and can significantly curb the gains of network coding in practice. The work by Compta et al. showed that this strategy could introduce an overhead as high as 100\% for Internet traffic. Our work advocates for an alternative encoding and decoding designs, focused on processing macro-symbols (composed by a number of symbols in the appropriate finite field) instead of full zero-padded packets. Our proposed schemes provide on-the-fly decoding strategies to manage heterogeneous packet sizes without the need for fragmentation or bundling of packets, which are strategies that require additional signalling. Performance is evaluated using CAIDA TCP packets and 4k video traces. Our results show that our mechanisms reduce significantly the padding overhead even for small field sizes. Finally, our strategies provide a natural trade-off between computational complexity and overhead due to the low density of the code when decoded at a macro-symbol level.

U2 - 10.1109/ICT.2016.7500495

DO - 10.1109/ICT.2016.7500495

M3 - Article in proceeding

BT - 23rd International Conference on Telecommunications (ICT), 2016

PB - IEEE

ER -

Taghouti M, Roetter DEL, Pedersen MV, Bouallegue A. Random linear network coding for streams with unequally sized packets: Overhead reduction without zero-padded schemes. In 23rd International Conference on Telecommunications (ICT), 2016. IEEE. 2016 https://doi.org/10.1109/ICT.2016.7500495