Technology

RLNC vs Traditional Codes

RLNC has a number of unique features compared to other coding schemes.

RLNC Vs Traditional Codes

Code On uses a proprietary algorithm, Random Linear Network Coding (RLNC), to enable a range of Network Coding applications for networks, storage and mobility applications.

The key differences between RLNC and other, traditional codes are captured in the below table.

 

 

Code Capabilities RLNC Rateless Codes Block Codes Characteristics/Benefits
Erasure correction Corrects for missing or corrupted data packets
Code is carried within each packet Eliminates tracking overhead
Completely distributed operation Enables stateless management
De-code using both unencoded and coded packets No forklift upgrade; adds implementation tunability
Able to generate valid codes from coded or unencoded packets Gradual implementation; no forklift
Composability without decoding (adding incremental redundancy) Enables addition of redundancy when and where needed
Encode data in a sliding window Flexible integration with protocols for greater efficency

 

Sliding Window

RLNC’s latency gains in latency-sensitive applications such as over-the-top (OTT) video streaming are made possible by its unique capability to code in a sliding-window. Coding in a sliding window presents a number of advantages over traditional block coding. The figure below illustrates how RLNC applies these two techniques.

In block coding, packet blocks are usually predefined. The illustration below shows blocks with a fixed number of packets. RLNC can generate redundancy (i.e., coded packets) from each block independently. When round trip times (RTTs) are high, redundancy rates are usually fixed. However, for low enough RTTs, redundancy rates can fluctuate dynamically with channel state information (CSI) or depend on feedback information. RLNC therefore allows for rateless coding with dynamic block sizes, as shown below.

Note that, for each block, and contrary to legacy block codes, all packets in a block need not be present for RLNC to start generating useful coded packets. This means that redundancy can be generated before the block is complete. This technique is termed on-the-fly coding and allows for removing coding delays at transmit buffers.

The problem with block codes is their rigidity: blocks do not overlap and are often fixed in size. As a result, packets from a given block cannot be passed to higher layers, (e.g., the application layer), as reliable goodput before a sufficient number of original or coded packets is received. This creates a lower limit in latency and decoding complexity that may affect delay-sensitive applications such as streaming or control.  

RLNC enables a more flexible technique called sliding window coding. Sliding window coding removes the limitation of fixed blocks by creating a variable-sized sliding window. Coded packets associated to a given sliding window position and size can be inserted in the stream, as shown below. The window definition, window size, redundancy rate, and transmission policy may depend on a number of factors such as receiver feedback, streaming requirements, CSI, congestion control, load control, etc.

Sliding window coding was developed in the context of coded TCP. RLNC enables the coded TCP source to transmit coded representations of its congestion window, thus stabilizing the flow and avoiding connection breakdowns due to the random packet losses or RTT swings seen at the transport layer.

Sliding window coding brings tremendous latency gains in a number of markets such as OTT streaming and transport over any topology (e.g., OTT Internet streaming, satellite communications). It is an integral part of Code On’s mesh, multipath, and multicast solutions.

Please refer to our white papers for illustrative implementations and results.

Recoding

Recoding is a unique RLNC feature. With recoding, coded symbols (i.e., packet / file / drive chunks) can be recombined without decoding. This feature is only possible in RLNC owing to the portability of the coding coefficients and the random nature of code selection (see white paper section). 

Recoding enables intermediate transport nodes and storage caches to combine coded packets/sectors to create new coded packets/sectors that are effective representations of all original packets/sectors involved in the first coding stage. This is illustrated in Figure (A) below, where plain-colored original packets can be combined using encoding, then re-combined with other encoded packets through recoding.

Recoding involves the linear combination of coded packets and the recalculation of new coding coefficients. It is a flexible process where data can be encoded as it becomes available, as shown in Figure (B), where recoding can combine a previously encoded packet with a previously absent original packet.

The unique flexibility of RLNC also allows for the removal of an original packet from a coded representation. This is illustrated in Figure (C) below, where the yellow packet is removed from existing coded packets. Figure (D) illustrates how recoding fits within the encoding and decoding scheme.

Recoding enables, for the first time, coding across mesh networks and distributed storage topologies. It allows powerful extensions and novel protocols in relay and mesh topologies. For instance, RLNC recoding alone can double the throughput of a single relay link. In a cooperative mobile mesh, this gain multiplies, while latency drops proportionally.

RLNC recoding also minimizes the total number of packet transmissions across a mesh network or storage system. The energy gains thus generated far exceed any encoding energy requirements.

Recoding is an integral part of Code On’s mesh, storage, multicast, and multipath solutions, where it brings significant latency, goodput, and reliability gains in all associated markets.

Please refer to our white papers for illustrative implementations and results.