TCP Testing with Linear Network Encoding (TCP / NC)
Engineers at the Massachusetts Institute of Technology under the direction of Muriel Médard have been developing the TCP / NC extension for TCP for many years, with which you can maintain the maximum data transfer rate on packet-loss networks. First of all, they plan to use TCP / NC in wireless WiFi networks, 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 MIFI hostel WiFi network (packet loss 2%), the average data transfer rate over WiFi increased from 1 Mbps to 16 Mbps. A test in a train at high speed (packet loss of 5%) showed an increase in WiFi speed from 0.5 Mbps to 13.5 Mbps. This completely coincides with the theoretical calculations.
The increase in speed is possible due to the effective recovery of random packet loss on the receiver side, without re-sending these packets. Packet recovery is carried out due to the banal mathematical operations known to each of the school course in algebra, namely, from the section on linear equations. The linear network coding algorithm is interesting in itself, but more on that below. First you need to understand why the network data rate drops sharply with relatively small (2-10%) packet loss.
The diagram shows a decrease in the data transfer rate in a TCP network, depending on the number of lost packets.
The problem with TCP is that this protocol "stupidly" perceives packet loss as a sign of network congestion. At the time of the creation of TCP, there was no WiFi and 3G yet, so it’s understandable why the developers did not immediately apply network encoding to recover lost packets, although the corresponding algorithms were already developed at that time and were probably successfully used in the army, space communications and reconnaissance.
So, TCP has one “cure” against congestion: window reduction. The trigger for reducing the window is timeout (TO) and triple duplicate (TD, packet duplication). In practice, reducing the window leads to the fact that the data transfer rate is artificially lowered by tens of times.
Using network encoding solves the problem by recovering the maximum possible number of lost packets (ideally, all), so that the sender does not receive information about the loss (ACK), does not register TD and TO, does not reduce the window - and the data transfer rate remains the same. as required.
The graph below shows a theoretical calculation of the TCP and TCP / NC data rates for different packet loss rates. As you can see, in the case of TCP, the speed drops sharply, while in the case of TCP / NC it remains almost at the same level, decreasing by about an overhead of network encoding (by the way, the overhead in TCP / NC is very small). The greater the packet loss in TCP, the greater the effect of network coding.
2009 chartshows a comparison of TCP and TCP / NC data rates at different packet loss levels.
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 / TS even at the software level by installing the appropriate application on the client and server side, although developers recommend that you still implement 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 operating principle shown 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 receive the packet A + B. This subsequently allows you to restore the missing package B in the lower left corner and the missing package 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 in a single cycle to both recipients.
The TCP / NC protocol also uses linear coding. Each byte and each packet in the TCP stream is multiplied by a coefficient from the Galois field F 256and fits into the linear equation. No packets are transmitted over the network, but degrees of freedom. Accordingly, if there is a loss of one packet, then you can restore it from known values, that is, from neighboring packets. When applied to TCP, this principle is well illustrated.
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 apply network coding in a TCP network without a strong hardware upgrade and without strict requirements for computing resources. An add-on to the TCP / NC protocol seems to allow this. Inventors have already registered Code On Network Coding, LLCand sell licenses. Perhaps in the near future many mobile operators will introduce the technology, so do not be surprised if, after installing the 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 of a specific implementation.
“Modeling Network Coded TCP Throughput: A Simple Model and its Validation” (2010) . The results of laboratory experiments.