DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Standard

DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding. / Nguyen, VU; Tasdemir, Elif; Nguyen, Giang T.; Lucani Rötter, Daniel Enrique; Fitzek, Frank H P; Reisslein, Martin.

I: IEEE Access, Bind 8, 2020, s. 78293-78314.

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Harvard

Nguyen, VU, Tasdemir, E, Nguyen, GT, Lucani Rötter, DE, Fitzek, FHP & Reisslein, M 2020, 'DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding', IEEE Access, bind 8, s. 78293-78314. https://doi.org/10.1109/ACCESS.2020.2989619

APA

Nguyen, VU., Tasdemir, E., Nguyen, G. T., Lucani Rötter, D. E., Fitzek, F. H. P., & Reisslein, M. (2020). DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding. IEEE Access, 8, 78293-78314. https://doi.org/10.1109/ACCESS.2020.2989619

CBE

Nguyen VU, Tasdemir E, Nguyen GT, Lucani Rötter DE, Fitzek FHP, Reisslein M. 2020. DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding. IEEE Access. 8:78293-78314. https://doi.org/10.1109/ACCESS.2020.2989619

MLA

Vancouver

Nguyen VU, Tasdemir E, Nguyen GT, Lucani Rötter DE, Fitzek FHP, Reisslein M. DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding. IEEE Access. 2020;8:78293-78314. https://doi.org/10.1109/ACCESS.2020.2989619

Author

Nguyen, VU ; Tasdemir, Elif ; Nguyen, Giang T. ; Lucani Rötter, Daniel Enrique ; Fitzek, Frank H P ; Reisslein, Martin. / DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding. I: IEEE Access. 2020 ; Bind 8. s. 78293-78314.

Bibtex

@article{1a955066911a49fc8c8d004a3ab2f6fe,
title = "DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding",
abstract = "Fulcrum coding combines a high-field outer Random Linear Network Coding (RLNC) that generates outer coding expansion packets with a small-field inner RLNC that combines the source packets and the outer coding expansion packets. This two-layer Fulcrum coding allows flexible decoding in receivers with heterogeneous computational capabilities. Fulcrum coding has so far only been studied for conventional dense RLNC, which randomly selects all coding coefficients, and only for a statically fixed number of outer expansion packets. However, the probability that the coding coefficient row of a newly received packet is linearly independent of prior received coding coefficient rows (a prerequisite for successful decoding) is highly dynamic. We propose to exploit the dynamics of this probability to reduce the computational complexity of Fulcrum coding. In particular, we vary the density of non-zero coding coefficients, i.e., equivalently, the sparsity of coding coefficients, and the number of outer expansion packets to keep the complexity low while maintaining a reasonably high decoding probability. We introduce the general principles of dynamic sparsity and expansion packets (DSEP) for Fulcrum coding as well as two specific example DSEP policies. Our evaluations indicate that DSEP Fulcrum can increase the encoding throughput tenfold and increase the decoding throughput 1.4 to 4.3 fold while achieving decoding probabilities that are typically less than 1% lower than the conventional Fulcrum decoding probabilities. We also find that DSEP achieves somewhat higher encoding and decoding throughputs than the CodornicesRq (Release 2.1) implementation of RaptorQ block coding for small blocks (generations) of source packets, while RaptorQ is substantially faster for large generation sizes. Furthermore, we develop and evaluate an elementary DSEP recoding mechanism that achieves a recoding throughput more than double the decoding throughput.",
keywords = "Computational complexity, RaptorQ, heterogeneous devices, random linear network coding (RLNC), recoding, sparsity, throughput, COMPUTE-AND-FORWARD, DESIGN, PERFORMANCE, Receivers, Throughput, ENERGY-CONSUMPTION, RELIABILITY, Decoding, MODEL, DECODING DELAY, PROBABILITY, CODES, Network coding, OPTIMIZATION, Block codes",
author = "VU Nguyen and Elif Tasdemir and Nguyen, {Giang T.} and {Lucani R{\"o}tter}, {Daniel Enrique} and Fitzek, {Frank H P} and Martin Reisslein",
year = "2020",
doi = "10.1109/ACCESS.2020.2989619",
language = "English",
volume = "8",
pages = "78293--78314",
journal = "IEEE Access",
issn = "2169-3536",
publisher = "Institute of Electrical and Electronics Engineers",

}

RIS

TY - JOUR

T1 - DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding

AU - Nguyen, VU

AU - Tasdemir, Elif

AU - Nguyen, Giang T.

AU - Lucani Rötter, Daniel Enrique

AU - Fitzek, Frank H P

AU - Reisslein, Martin

PY - 2020

Y1 - 2020

N2 - Fulcrum coding combines a high-field outer Random Linear Network Coding (RLNC) that generates outer coding expansion packets with a small-field inner RLNC that combines the source packets and the outer coding expansion packets. This two-layer Fulcrum coding allows flexible decoding in receivers with heterogeneous computational capabilities. Fulcrum coding has so far only been studied for conventional dense RLNC, which randomly selects all coding coefficients, and only for a statically fixed number of outer expansion packets. However, the probability that the coding coefficient row of a newly received packet is linearly independent of prior received coding coefficient rows (a prerequisite for successful decoding) is highly dynamic. We propose to exploit the dynamics of this probability to reduce the computational complexity of Fulcrum coding. In particular, we vary the density of non-zero coding coefficients, i.e., equivalently, the sparsity of coding coefficients, and the number of outer expansion packets to keep the complexity low while maintaining a reasonably high decoding probability. We introduce the general principles of dynamic sparsity and expansion packets (DSEP) for Fulcrum coding as well as two specific example DSEP policies. Our evaluations indicate that DSEP Fulcrum can increase the encoding throughput tenfold and increase the decoding throughput 1.4 to 4.3 fold while achieving decoding probabilities that are typically less than 1% lower than the conventional Fulcrum decoding probabilities. We also find that DSEP achieves somewhat higher encoding and decoding throughputs than the CodornicesRq (Release 2.1) implementation of RaptorQ block coding for small blocks (generations) of source packets, while RaptorQ is substantially faster for large generation sizes. Furthermore, we develop and evaluate an elementary DSEP recoding mechanism that achieves a recoding throughput more than double the decoding throughput.

AB - Fulcrum coding combines a high-field outer Random Linear Network Coding (RLNC) that generates outer coding expansion packets with a small-field inner RLNC that combines the source packets and the outer coding expansion packets. This two-layer Fulcrum coding allows flexible decoding in receivers with heterogeneous computational capabilities. Fulcrum coding has so far only been studied for conventional dense RLNC, which randomly selects all coding coefficients, and only for a statically fixed number of outer expansion packets. However, the probability that the coding coefficient row of a newly received packet is linearly independent of prior received coding coefficient rows (a prerequisite for successful decoding) is highly dynamic. We propose to exploit the dynamics of this probability to reduce the computational complexity of Fulcrum coding. In particular, we vary the density of non-zero coding coefficients, i.e., equivalently, the sparsity of coding coefficients, and the number of outer expansion packets to keep the complexity low while maintaining a reasonably high decoding probability. We introduce the general principles of dynamic sparsity and expansion packets (DSEP) for Fulcrum coding as well as two specific example DSEP policies. Our evaluations indicate that DSEP Fulcrum can increase the encoding throughput tenfold and increase the decoding throughput 1.4 to 4.3 fold while achieving decoding probabilities that are typically less than 1% lower than the conventional Fulcrum decoding probabilities. We also find that DSEP achieves somewhat higher encoding and decoding throughputs than the CodornicesRq (Release 2.1) implementation of RaptorQ block coding for small blocks (generations) of source packets, while RaptorQ is substantially faster for large generation sizes. Furthermore, we develop and evaluate an elementary DSEP recoding mechanism that achieves a recoding throughput more than double the decoding throughput.

KW - Computational complexity

KW - RaptorQ

KW - heterogeneous devices

KW - random linear network coding (RLNC)

KW - recoding

KW - sparsity

KW - throughput

KW - COMPUTE-AND-FORWARD

KW - DESIGN

KW - PERFORMANCE

KW - Receivers

KW - Throughput

KW - ENERGY-CONSUMPTION

KW - RELIABILITY

KW - Decoding

KW - MODEL

KW - DECODING DELAY

KW - PROBABILITY

KW - CODES

KW - Network coding

KW - OPTIMIZATION

KW - Block codes

U2 - 10.1109/ACCESS.2020.2989619

DO - 10.1109/ACCESS.2020.2989619

M3 - Journal article

VL - 8

SP - 78293

EP - 78314

JO - IEEE Access

JF - IEEE Access

SN - 2169-3536

ER -