FSW: Fulcrum Sliding Window Coding for Low-Latency Communication

Fulcrum Random Linear Network Coding (RLNC) combines outer coding in a large Galois Field, e.g., GF(28), with inner coding in GF(2) to flexibly trade off the strong protection (low probability of linear dependent coding coefficients) of GF(28) with the low computational complexity of GF(2). However, the existing Fulcrum RLNC approaches are generation based, leading to large packet delays due to the joint processing of all packets in a generation in the encoder and decoder. In order to avoid these delays, we introduce Fulcrum Sliding Window (FSW) coding. We introduce two flavors of FSW: Fulcrum Non-systematic Sliding Window (FNSW), which divides a given generation into multiple partially overlapping blocks, and Fulcrum Systematic Sliding Window (FSSW), which intersperses coded packets among the uncoded (systematic) transmission of the source packets in a generation. Our extensive evaluations indicate that FSSW substantially reduces the in-order packet delay (for moderately large generation and window sizes down to less than one fourth) and more than doubles the encoding and decoding (computation) throughput compared to generation-based Fulcrum.