RLNC stands for Random Linear Network Coding. It is a powerful new technology that can be used to improve the performance of many of today’s communication systems. For example, RLNC can speed up the internet, improve video quality for streaming movies and live events, and decrease size while increasing reliability for the datacenters used for cloud computing. The benefits are huge. In some cases, we see 5-fold increases in throughput over the internet, 80% improvements in data availability for streaming video, and 20-50% reductions in storage center energy consumption.
This section explains RLNC’s unique capabilities through descriptions of applicable markets and topology implementations, a comparison of RLNC with traditional codes, as well as a set of use cases, simulations and demos.
TCP transmissions are a bit like collecting baseball cards. If packets were sent out like baseball cards, then you would suffer the fate of collectors everywhere: collecting cards is easy, but getting the ones you want is hard. Said another way, collecting sequential packets would be similar to collecting baseball cards in alphabetical order. If we discard all cards that aren’t the next in line alphabetically, then keeping track of what we have is easy, but getting a complete collection may be hard. You certainly wouldn’t collect baseball cards this way…
To add to the challenge, TCP / IP interprets packet loss as a sign of network congestion, so the rate of packet transmission is halved when a packet loss occurs and increased again slowly after a sequence of successful packet receipts. This is a pretty good approach in wired networks where congestion is a likely explanation for packet loss, but doesn’t work well in wireless networks where dropped packets can be caused by many other factors. In these networks, TCP / IP can magnify even small error rates into large delays in downloading data.
RLNC changes the paradigm by noticing that packets are not baseball cards. Each packet is a string of zeros and ones that can be represented by a number. TCP / IP sends packets 1 and 2 by sending precisely these numbers. If the first data packet is lost or delivered too slowly, then no acknowledgment is received in time, and data packet 1 is transmitted again. This process repeats until data packet 1 is received and acknowledged. An RLNC alternative of the same protocol would calculate “coded packets” 1 and 2 and send those in place of the “data packets.” The coded packets are formed by multiplying the numbers represented by data packets 1 and 2 by constants and then adding the two together, giving
code packet 1 = random number 1 x data packet 1 + random number 2 x data packet 2
code packet 2 = random number 3 x data packet 1 + random number 4 x data packet 2
The random numbers are constants, meaning that they do not depend on the data packets. These constants can be sent to the receiver in the header (that is, at the beginning) of the coded packets in which they are used.
If the receiver gets random numbers 1 through 4, then it can easily solve for packets 1 and 2. As a result, the coded scheme is similar to the standard scheme when no packets are lost. One advantage of coding becomes evident under packet loss. As you remember from high school algebra, any two distinct equations are enough to solve for two unknowns. As a result, in the coded system, the transmitter can keep on sending out new combinations:
code packet 3 = random number 5 x data packet 1 + random number 6 x data packet 2
code packet 4 = random number 7 x data packet 1 + random number 8 x data packet 2
and so on until at least two distinct combinations are received. With coded packets, it doesn’t matter which packets are lost and which received; any two receipts are sufficient to solve for data packets 1 and 2. What’s remarkable about this approach is that there are so many different combinations possible, that we need not choose the coefficients carefully. Instead, we choose these coefficients at random, effectively rolling some dice to choose random numbers; this is the “random” in RLNC.
There are many ways to apply RLNC. One is to stop keeping track of which combinations have been received and simply acknowledge each time a new packet arrives. The transmitter just sends out a sequence of random combinations and the receiver acknowledges each time a new combination is received. The transmission is completed once the number of distinct equations received equals the number of packets to be received. No packets need ever be thrown out, and the transmitter need never know which packets have and haven’t been received. Transmission stops when the number of distinct packets received equals the number of packets x_i to be transmitted. Certainly you couldn’t do better than that.
RLNC is versatile code and thus, can improve transmissions in a range of different implementations at different layers of the network — often with cumulative results. For explanation purposes, this section describes a typical implementation used in cloud-based applications — it is implemented at the application or TCP / IP layer.
Today’s Internet operates under very strict rules or Internet protocols like TCP / IP to effectively transmit information. Communications under these protocols are based on ‘packets’ or small, broken down pieces of the information that is being sent. In a TCP communication packets are transmitted sequentially from their point of origin and only accepted at the destination if they arrive in order. Every packet is acknowledged by the recipient. If the Internet were set up to wait for each packet arrival to be acknowledged before transmitting the next packet, it would run way too slowly. Instead, the sender keeps sending out packets, assuming that they will get through. If, however, the sender doesn’t receive the next acknowledgment that it is expecting within some reasonable time frame or it receives the acknowledgment for a later packet before receiving the one it expects, then it treats the unacknowledged packet as lost and sends it again. The sender may be sending Packet #83 when it learns that Packet #21 didn’t arrive. It then re-sends Packet #21 and all subsequent packets. If there are a lot of missing packets, you can imagine that most of the time is spent on re-sending.
in TCP transmissions, RLNC improves communication efficiency by using linear algebra to combine the information of several packets into one, same sized packet. The same number of packets still need to be sent and received, but the packets are now interchangeable, so that if Packet #21 does not arrive, the receiver can use Packet #22 as a substitute, avoiding the need to resend Packets #22 through #83. This packet versatility enables RLNC greatly reduces packet re-sends and the associated signaling needed to track ‘lost packets’.