Engineers from the Massachusetts Institute of Technology under the leadership of Muriel Medard (Muriel Médard) have been developing TCP / NC extensions for TCP for many years, with which you can save the maximum data transfer rate in networks with packet loss. First of all, TCP / NC plan to use in wireless networks WiFi, where packet loss is usually 2-5%, and sometimes up to 10%. Finally it came to real experiments.

During the first field tests of TCP / NC in the local WiFi network of the MIT hostel (packet loss of 2%), the average data transfer rate over WiFi increased from 1 Mbit / s to 16 Mbit / s. The test in the train at high speed (5% packet loss) showed an increase in WiFi speed from 0.5 Mbit / s to 13.5 Mbit / s. This is completely consistent with theoretical calculations.

An increase in speed is possible due to the effective recovery of random packet loss on the receiver side, without re-sending these packets. Packages are recovered through banal mathematical operations known to each of the school algebra course, namely, from the section on linear equations. The linear network coding algorithm itself is interesting, but more on that below. First you need to understand why the data transfer rate in the network drops sharply with relatively small (2-10%) packet loss.
')
The diagram shows a decrease in the speed of data transmission in the TCP network, depending on the number of lost packets.



The TCP problem is that this protocol “stupidly” perceives packet loss as a sign of network congestion. At the time of TCP creation, there was no WiFi and 3G yet, so it’s understandable why developers didn’t immediately apply network coding to recover lost packets, although the corresponding algorithms were already developed and probably were successfully used in the army, space communications and intelligence.

So, TCP has one “cure” against congestion: reducing the window. The trigger to reduce the window is a timeout (TO) and a triple duplicate (TD, packet duplication). In practice, reducing the window leads to the fact that the data transfer rate is artificially lowered tenfold.

Using network coding solves the problem by recovering as many packets as possible (ideally everything), so the sender does not receive loss information (ACK), does not register TD and TO, does not reduce the window - and the data transfer rate remains at the same level, as required.

The graph below shows a theoretical calculation of the TCP and TCP / NC data transfer rates with different levels of packet loss. As you can see, in the case of TCP, the speed decreases dramatically, and in the case of TCP / NC it remains almost at the same level, decreasing by approximately the network heading overhead (by the way, the overhead in TCP / NC is quite small). The more packet loss in TCP - the greater the effect of network coding.



A diagram from 2009 shows a comparison of the TCP and TCP / NC data transfer rates at different levels of packet loss.

The main advantage of TCP / NC is that it can be connected as an intermediate layer in the TCP / IP stack, without changing anything in TCP itself, as shown in the diagram.



In other words, you can implement TCP / TC even at the software level by installing the appropriate application on the client and server side, although the developers still recommend implementing TCP / NC support in routers and other devices.

Linear network coding algorithm

Network coding involves changing data packets at intermediate nodes to increase the capacity of the communication channel. The principle of operation is usually illustrated by the classic example of the Butterfly network, in which one of the nodes applies network coding on packets A and B, using the XOR operation to obtain the A + B packet. This subsequently allows you to recover the missing packet B in the lower left corner and the missing packet A in the lower right corner. As a result, network bandwidth increases, because without network coding in such a network topology, it is impossible to transmit packets A and B simultaneously to both recipients in a single clock.



The TCP / NC protocol also uses network coding according to a linear equation. Each byte and each packet in the TCP stream is multiplied by a coefficient from the Galois field F ₂₅₆ and fit into the linear equation. Not packets, but degrees of freedom are transmitted over the network. Accordingly, if there is a loss of one packet, then it can be recovered from known values, that is, from neighboring packets. As applied to TCP, this principle is well illustrated in the illustration.



Network coding is a rather old section of information theory, and there are already many different algorithms for recovering lost packets (bits). The problem is that so far no one has found a way to use network coding on a TCP network without a strong upgrade of equipment and without strict requirements for computing resources. The add-on over TCP / NC seems to allow this. The inventors have already registered Code On Network Coding, LLC and are selling licenses. It is possible that in the near future many mobile operators will introduce the technology, so do not be surprised if after installing a new version of Android, your internet suddenly starts working 10 times faster.

Scientific papers describing TCP / NC
“An algebraic approach to network coding” (2003) . Mathematical model of linear network coding.
“Network coding meets TCP” (2009) . Basic principles.
“Interfacing network coding with TCP: an implementation” (2009) . Scheme specific implementation.
“Modeling Network Coded TCP Throughput: A Simple Model and its Validation” (2010) . The results of laboratory experiments.