Kerim Fouli, Muriel Médard (MIT), and Kavim Shroff, Code On Network Coding LLC
Published: 6 Aug 2018
CTN Issue: July 2018
A note from the editor:
This edition we take a look beyond the latest codes used in 5G and other transmission standards towards coding designed to support the network rather than just the link. Flexible and multi layered coding techniques are just beginning to get some traction especially, in this editor’s experience, in coding for redundant storage. But Kerim, Muriel and Kavim paint a much larger use case picture while explaining the basic principles. Your comments and questions are, as always, very welcome.
Random Linear Network Coding: A Technical Feature Overview
Coding and Random Linear Network Coding (RLNC)
The discipline of coding has two main traditional branches: source coding and channel coding. Source coding (e.g., MPEG) eliminates redundancy in data to reduce the size of a file. Channel coding (e.g. Reed Solomon, Turbo Codes) introduces redundancy and is used when sending data over a link or connection that has losses.
Channel codes were designed to optimize data delivery between two points with a focus on recovering lost or corrupted data (“Erasure or Error Correction”). Channel codes are most commonly found in chip implementations and are always set up between a source and one or more receivers. System designers typically insert a channel code as a standalone module within a network link or at the ingress and egress points of a network. These circumscribed, point-to-point solutions add network complexity since they require state tracking and are not necessarily interoperable with the rest of the network.
Breakthrough innovations in coding schemes occur every 10 – 20 years. Figure 1 shows a timeline of the channel codes that have enabled modern networks.
RLNC’s main innovation is its ability to operate without a complex structure. Unlike prior coding schemes, RLNC is able to generate coded data units from any two or more coded or uncoded data units locally and on the fly. RLNC owes this major feature to its reliance on simple linear algebraic operations as well as to the random generation of its linear coefficients. This allows the code (i.e., the coefficients) to be carried with its data units, hence enabling fully distributed operation.
Figure 2 illustrates the difference in the coding landscape stemming from the advent of RLNC. While current codes operate as end-to-end codes, RLNC can be applied to the wide scope of topologies required by emerging applications. It is important to note that RLNC’s usage encompasses not only reliability, like conventional codes, but extends to enabling communications across the listed topologies and applications. This is well illustrated by the recoding section below.
As a consequence, RLNC is the first code that can be used as a block, convolutional or rateless code in a point-to-point (PtP) or multicast setting, while extending the functionality of both source and channel coding. More importantly, RLNC is the first practical code designed for distributed network environments, i.e., the first network code. As such, RLNC uniquely enables intermediate nodes to participate to network reliability with minimal coordination[1,2].
The key differences between RLNC and other traditional codes are recapitulated in table 1 below.
|Code Capabilities||RLNC||Rateless Codes||Block Codes||Characteristics / Benefits|
|Erasure Correction||✔||✔||✔||Corrects for missing or corrupted data packets|
|Encode data in a sliding window||✔||✘||✘||Coding matches protocol behavior ➤ fewer retransmissions|
|Code is carried within each packet||✔||✘||✘||Eliminates tracking overhead|
|Composability without decoding (adding incremental redundancy)||✔||✘||✘||Only adds redundancy when and where needed|
|Completely distributed operation||✔||✘||✘||Enables stateless management|
|Able to generate valid codes from coded or uncoded packets||✔||✘||✘||Gradual implementation; no forklift|
|Decode using uncoded packets||✔||✘||✘||No forklift; implementation tunability|
Table 1: Next-generation capabilities of Random Linear Network Coding.
Coding in a sliding window and in a composable way (an operation called recoding) are fundamental unique features that flow directly from RLNC’s reduced structure and flexibility. Those abilities are not shared with structured codes, whether block or rateless[1,2,19].
This technical overview is divided into two sections. The first section covers sliding window coding and recoding, two unique technical features of RLNC that enable most of its applications. The second section is a brief description of its growing implementations and traction.
Coding in a 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. Figure 3 below illustrates how RLNC introduces flexibility to block codes and how it enables sliding window coding.
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, unlike legacy block codes such a Reed Solomon, RLNC can generate useful coded packets from incomplete coded/uncoded blocks. 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 structured 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, where coding is performed across a dynamic set of packets. Sliding window coding removes the limitation of fixed blocks by creating a variable-sized sliding window. Source, or native, packets can be added or removed from the sliding window dynamically. Coded packets associated to a given sliding window position (i.e., first packet index) and size can be inserted into 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 Transmission Control Protocol (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[7,8,9].
Sliding window coding brings significant latency gains in a number of markets such as Over The Top (OTT) streaming and transport over any topology (e.g., OTT Internet streaming, satellite communications)[3,6,7,8,9]. In addition, it enables powerful Quality of Experience (QoE) tradeoffs in access and multicast networks, particularly in minimizing interruption in media playback[4,5].
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.
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 4 (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 4 (B) above, where recoding can combine a previously encoded packet with a previously absent original packet.
Figures 5 (A), (B) and (C) below illustrate how recoding fits within the encoding and decoding scheme when applied to multi-hop, mesh, and cache networks. In Figure 5 (A), four packets are transmitted across a multi-hop network where systematic coding is used to compensate for losses. In this network, recoding enables intermediate nodes to compensate for dynamic losses locally without returning to the source.
In Figure 5 (B), the source sends four packets across a mesh network with two distinct paths. In this network, recoding allows intermediate nodes to bring a sufficient number of degrees of freedom to the receiver with little need for coordination. The amount of redundancy may depend on multiple factors such as path/link losses, path/link capacity, device capability, etc. This example shows how the capacity of the multiple paths can be combined dynamically.
In Figure 5 (C), two caching nodes are populated from an intermediate cache without need to return to the four uncoded pieces. Recoding is used here as a dynamic caching enabler that is particularly suitable for mobile caching or fast storage repair. Note the fact that some of the caches may not be allowed to have enough degrees of freedom to decode the original pieces, leading to new security and Digital Right Management (DRM) tools[2,30].
Recoding therefore enables, for the first time, coding across mesh networks and distributed storage topologies[6,12,19]. It allows powerful extensions and novel protocols in relay and mesh topologies[16,17,20]. 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[14,17].
RLNC recoding also minimizes the total number of packet transmissions across a mesh network or storage system. The energy gains thus generated typically exceed encoding energy requirements.
This section focuses on four networking application areas, and how:
- RLNC enables the next-generation multicast features required for satellite, mobile 5G, connected cars, video streaming.
- RLNC enables improved communications in high-RTT environments such as Satellite Communications.
- RLNC is an important distributed storage and caching technology, providing innovative capabilities for data storage retrieval, reliability, and repair.
- RLNC brings new tools to mesh and IoT networks, including novel routing, dissemination, collection and reliability paradigms, all the while breaking latency barriers.
As the number of receivers increases, managing feedback with individual receivers is not scalable, hence the advent of complex multicasting protocols such as NACK Oriented Reliable Multicast (NORM). Overall, exploiting RLNC enables significant reduction of feedback while enabling high-QoE broadcast solutions[12, 13, 14, 15, 18, 25].
Code On Ecosystem partner and licensee Steinwurf is active in this space, where it has developed and tested RLNC-based multicasting reference designs based on their innovative RLNC-based SCORE protocol. Steinwurf also developed the Kodo RLNC software library, demonstrating coding speedups for both Intel and ARM chipsets, where the multi-platform RLNC library is compatible with hardware acceleration.
RLNC (and coding in general) is being adopted in Satellite communications, an industry that is generally at the forefront of developing and integrating new technologies. RLNC clearly differentiates itself by generating coded data units from any source units on the fly, leading to new coding schemes where latency, bandwidth, complexity, and reliability can be tuned dynamically to match link conditions and network requirements.
RLNC’s inherent flexibility enables a wider scope of tradeoffs and optimizations compared to conventional coding techniques, making it suitable for high Round Trip Time (RTT) environments.
In a test implementation, RLNC was recently used to carry Internet services via satellite to a group of Pacific islands, multiplying goodput performance and reducing bandwidth utilization swings.
Owing to its recoding feature, RLNC is the only coding technology that can create coded sectors from other coded (and uncoded) sectors without decoding first. This enables storage nodes and intermediate caches to generate additional redundancy on demand and in a decentralized fashion, leading to tremendous reductions in required transportation, overall storage, energy, and drive repair speed (i.e., the time it takes to replace missing or failing nodes or sectors).
More importantly, RLNC removes the need for the complex bookkeeping and scheduling required to ensure the availability of original sectors in conventional systems. This ability to reduce the need for state information (a.k.a., “stateless communications”) eliminates much of the management overhead traditionally associated with distributed storage[1,2].
RLNC’s storage solutions apply to all distributed storage applications, including multi-drive storage, edge caching, and hybrid cloud applications. As a consequence, RLNC storage solutions stand to play a crucial role in Peer-to-Peer (P2P) networks and applications, Content Delivery Networks (CDN), cloud services, and cloud security[21,22,23].
Code On licensee Chocolate Cloud is active in this space where it has implemented Skyflok, its secure distributed storage product.
Mesh Networking and IoT
As discussed above, a number of RLNC technologies are combined to create superior wireless mesh networks[17,19,20,25].
First, RLNC-enhanced mesh protocols allow nodes that are adjacent to any given route, to opportunistically store overheard packets and code them to create new redundancy. Second, wireless overhearing, inherent multicast, and multipath opportunities can be exploited dynamically. Third, RLNC has the unique ability to code on the fly. Novel protocols making use of RLNC are capable of reducing network latencies and improving throughput and resilience significantly across mesh networks[17, 20].
Furthermore, RLNC can facilitate channel and network bundling to combine the throughput and reliability of multiple networks. This is an increasingly useful feature, since technology integration trends are turning wireless access networks into heterogeneous multipath environments. RLNC thus enables network offloading and multipath communications across multiple applications[4,6,10,11,20].
RLNC has shown strong potential in mesh, multi-path and multi-source use cases due to the code’s flexibility and portability advantages. As a consequence, it is actively being investigated and tested across multiple consumer and industrial infrastructures such as 5G, Over the Top (OTT), terrestrial, vehicle to vehicle (V2V) and time-sensitive networks for its low-latency reliable mesh topologies, seamless multipath operation and stream aggregation, as well as sliding-window coding techniques to reduce in-order latencies in point-to-point settings [32, 33].
- https://www.codeontechnologies.com/en/technology/ Retrieved August 2018
- Random Linear Network Coding: A Tutorial – Code On White Paper
- M. Toemoeskoezi, F. H. P. Fitzek, D. E. Lucani, M. V. Pedersen and P. Seeling, "On the Delay Characteristics for Point-to-Point Links using Random Linear Network Coding with On-the-Fly Coding Capabilities," European Wireless 2014; 20th European Wireless Conference, Barcelona, Spain, 2014, pp. 1-6.
- A. ParandehGheibi, M. Médard, A. Ozdaglar and S. Shakkottai, "Access-network association policies for media streaming in heterogeneous environments," 49th IEEE Conference on Decision and Control (CDC), Atlanta, GA, 2010, pp. 960-965.
- A. ParandehGheibi, M. Medard, A. Ozdaglar and S. Shakkottai, "Avoiding Interruptions - A QoE Reliability Function for Streaming Media Applications," in IEEE Journal on Selected Areas in Communications, vol. 29, no. 5, pp. 1064-1074, May 2011.
- J. Krigslund, J. Hansen, D. E. Lucani, F. H. P. Fitzek and M. Medard, "Network Coded Software Defined Networking: Design and Implementation," Proceedings of European Wireless 2015; 21th European Wireless Conference, Budapest, Hungary, 2015, pp. 1-6
- M. Kim et al., "Congestion control for coded transport layers," 2014 IEEE International Conference on Communications (ICC), Sydney, NSW, 2014, pp. 1228-1234.
- Jason Cloud, Douglas Leith, and Muriel Medard “Network Coded TCP (CTCP) Performance over Satellite Networks” SPACOMM 2014 (ISBN: 978-1-61208-317-9), pp53-56 Network Coded TCP Performance over Satellite Networks. (http://arxiv.org/abs/1310.6635) Retrieved August 2018
- L. Urbina, “Applying Network Coding to TCP,” M.Eng. Thesis, Dept. Electrical Engineering and Computer Science, MIT, 2012
- J. Cloud, F. du Pin Calmon, W. Zeng, G. Pau, L. M. Zeger and M. Medard, "Multi-Path TCP with Network Coding for Mobile Devices in Heterogeneous Networks," 2013 IEEE 78th Vehicular Technology Conference (VTC Fall), Las Vegas, NV, 2013, pp. 1-5.
- A. Kulkarni, M. Heindlmaier, D. Traskov, M.J. Montpetit, M. Médard (2011) An Implementation of Network Coding with Association Policies in Heterogeneous Networks. In: Casares-Giner V., Manzoni P., Pont A. (eds) NETWORKING 2011 Workshops. NETWORKING 2011. Lecture Notes in Computer Science, vol 6827. Springer, Berlin, Heidelberg
- U. J. Ferner, T. Wang and M. Médard, "Network coded storage with multi-resolution codes," 2013 Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2013, pp. 652-656.
- M. Kim, D. Lucani, X. Shi, F. Zhao and M. Medard, "Network Coding for Multi-Resolution Multicast," 2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010, pp. 1-9.
- J. Heide, F. H. P. Fitzek, M. V. Pedersen and M. Katz, "Green mobile clouds: Network coding and user cooperation for improved energy efficiency,"2012 IEEE 1st International Conference on Cloud Networking (CLOUDNET), Paris, 2012, pp. 111-118.
- L. Lima, S. Gheorghiu, J. Barros, M. Medard and A. L. Toledo, "Secure network coding for multi-resolution wireless video streaming," in IEEE Journal on Selected Areas in Communications, vol. 28, no. 3, pp. 377-388, April 2010.
- M. Hundebøll, M. V. Pedersen, D. E. Lucani and F. H. P. Fitzek, "Supporting Dynamic Adaptive Streaming over HTTP in wireless meshed networks using random linear network coding," 2014 International Symposium on Network Coding (NetCod), Aalborg, 2014, pp. 1-6.
- M. Hundeboll, P. Pahlevani, D. E. Lucani and F. H. P. Fitzek, "Throughput vs. Delay in Lossy Wireless Mesh Networks with Random Linear Network Coding," European Wireless 2014; 20th European Wireless Conference, Barcelona, Spain, 2014, pp. 1-6.
- A. Rezaee, F. d. P. Calmon, L. M. Zeger and M. Medard, "Speeding Multicast by Acknowledgment Reduction Technique (SMART) Enabling Robustness of QoE to the Number of Users," in IEEE Journal on Selected Areas in Communications, vol. 30, no. 7, pp. 1270-1280, August 2012.
- Steven Max Patterson - Network World (http://www.networkworld.com/article/2342846/data-breach/how-mit-and-caltech-s-coding-breakthrough-could-accelerate-mobile-network-speeds.html) Retrieved August 2018
- P. Pahlevani, D. E. Lucani, M. V. Pedersen and F. H. P. Fitzek, "PlayNCool: Opportunistic network coding for local optimization of routing in wireless mesh networks,"2013 IEEE Globecom Workshops (GC Wkshps), Atlanta, GA, 2013, pp. 812-817.
- M. Sipos, F. H. P. Fitzek, D. E. Lucani and M. V. Pedersen, "Distributed cloud storage using network coding," 2014 IEEE 11th Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, 2014, pp. 127-132.
- F. H. P. Fitzek et al., "Implementation and performance evaluation of distributed cloud storage solutions using random linear network coding," 2014 IEEE International Conference on Communications Workshops (ICC), Sydney, NSW, 2014, pp. 249-254.
- U. J. Ferner, M. Médard and E. Soljanin, "Toward sustainable networking: Storage area networks with network coding," 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, 2012, pp. 517-524.
- Kodo Library, Steinwurf (http://www.steinwurf.com/products/kodo.html) Retrieved August 2018
- Q. Zhang, J. Heide, M. V. Pedersen and F. H. P. Fitzek, "MBMS with User Cooperation and Network Coding," 2011 IEEE Global Telecommunications Conference - GLOBECOM 2011, Kathmandu, 2011, pp. 1-6.
- Steinwurf (http://steinwurf.com/) Retrieved August 2018
- Steinwurf SCORE Protocol (https://www.youtube.com/watch?v=slN_CyyrLQw) (https://www.youtube.com/watch?v=svPOLWZRdeg) Retrieved August 2018
- Chocolate Cloud (https://www.chocolate-cloud.cc/) Retrieved August 2018
- Skyflok (https://www.skyflok.com/us/) Retrieved August 2018
- Network Coding: Evolving to 5G – Code On White Paper
- U. Speidel, E. Cocker, P. Vingelmann, J. Heide and M. Medard, "Can network coding bridge the digital divide in the pacific?" 2015 International Symposium on Network Coding (NetCod), Sydney, NSW, 2015, pp. 86-90.
- N. Lavi, T. Philosof and M. Laifenfeld, "VehiCache: Vehicle Updates via Mobile Phones," 2017 IEEE 86th Vehicular Technology Conference (VTC-Fall), Toronto, ON, 2017, pp. 1-5.
- A. Ramakrishnan, C. Westphal, and J. Saltarin. "Adaptive Video Streaming over CCN with Network Coding for Seamless Mobility". 2016 IEEE International Symposium on Multimedia.
Statements and opinions given in a work published by the IEEE or the IEEE Communications Society are the expressions of the author(s). Responsibility for the content of published articles rests upon the authors(s), not IEEE nor the IEEE Communications Society.