Slashdot Mirror
Replacing TCP?
olau writes "TCP, the transfer protocol that most of the Internet is using, is getting old. These guys have invented an alternative that combines UDP with rateless erasure codes, which means that packets do not have to be resent. Cool stuff! It also has applications for peer-to-peer networks (e.g. for something like BitTorrent). They are even preparing RFCs! The guy who started it, Petar Maymounkov, is of Kademlia fame."
Here is a summary of their technology copied from their website:
Rateless Internet The Problem
Rateless Internet is an Internet transport protocol implemented over UDP, meant as a better replacement of TCP. TCP's legacy design carries a number of inefficiencies, the most prominent of which is its inability to utilize most modern links' bandwidth. This problem stems from the fact that TCP calculates the congestion of the channel based on its round-trip time. The round-trim time, however, reflects not only the congestion level, but also the physical length of the connection. This is precisely why TCP is inherently unable to reach optimal speeds on long high-bandwidth connections.
A secondary, but just as impairing, property of TCP is its inability to tolerate even small amounts (1% - 3%) of packet loss. This additionally forces TCP to work at safe and relatively low transmission speeds with under 1% loss rates. Nevertheless, our extended real-life measurements show that highest throughput is generally achieved at speeds with anywhere between 3% and 5% loss.
The Solution
By using our core coding technology we were able to design a reliable Internet transmission protocol which can circumvent both of the fore-mentioned deficiencies of TCP, while still remaining TCP-friendly. By using encoded, rather than plain, transmission we are able to send at speeds with any packet loss level. Rateless coding is used in conjunction with our Universal Congestion Control algorithm, which allows Rateless Internet to remain friendly to TCP and other congestion-aware protocols.
Universal Congestion Control is an algorithm for transmission speed control. It is based on a simple and clean idea. Speed is varied in a wave-like fashion. The top of the wave achieves near-optimal throughput, while the bottom is low enough to let coexisting protocols like TCP smoothly receive a fair share of bandwidth. The time lengths of the peaks and troughs can be adjusted parametrically to achieve customized levels of fairness between Rateless Internet and TCP.
The Rateless Internet transport is now available through our Rateless Socket product in the form of a C/C++ socket library. Rateless Internet is ideal for Internet-based applications, running on the network edges, that require high bandwidth in a heterogenous environment. It was specifically built with peer-to-peer and live multimedia content delivery applications in mind.
It was quite a complicated set of protocols and IIRC the final versions were using TCP/IP as their transport layer and below. The versions before that were using OSI.
http://en.wikipedia.org/wiki/DECnet
John.
Tried their "Rateless Copy" utility, transferring a 5.8 mb binary file from my web server in Texas to my local connection in Toronto.
With Rateless Copy: time between 31-41 seconds, average of 200k/s, the resulting file is corrupted. Tried it again to ensure, same result.
Without rateless copy (http file download) 8 seconds, average of 490k/s, the resulting file works fine as expected.
Sorry, but I don't think it's all that great.
You'd be right if they were talking about an error correcting code designed to repair damage to a packet in transit.
They're actually talking about erasure correction, where each symbol is a packet as a whole. In a very simple form, you send a packet sequence like this:
A B (A^B) C D (C^D)
So if you lose packet A, you reconstruct it from (B ^ (A^B)) = A. This simple scheme increases the number of packets sent by 50%, but allows you to tolerate a 33% loss, presuming you don't lose bursts of packets. There are more sophisticated schemes, of course, and there are various tradeoffs of overhead versus robustness.
This work seems to be about two things (which I am not sure I see a strong connection between): lowering transport latency, and using available bandwidth better. The latter has been the subject of many papers in the last few years. There are now several serious proposals of how to fix TCP with respect to long fat pipes. They don't seem to support the idea that retransmissions are harmful. So I'm going to talk about the first issue, transport latency.
The idea of using error-correcting codes (ECC) to eliminate the need for retransmissions is an interesting one. The main benefit is to reduce transport latency (the total time it takes to send data from application A to B). Here is another paper proposes has a similar idea, applied at a different level of the network architecture.
The root problem here is that network loss leads to increases in the transport latency experienced by applications. In TCP, the latency increases because TCP will resend data that is lost. That means at least one extra round-trip-time per retransmission. This "Rateless TCP" approach uses ECC so that the lost data can be recovered from other packets that were not dropped. In this way, the time to retransmit packets may not be needed. I say may, because there will be a loss rate threshold which will exceed the capability of the ECC, and retransmission will become necessary to ensure reliability. But, as long as the loss rate is below the threshold, then retransmissions will not be necessary. Note that the more "resilient" you make the ECC (meaning supporting a higher loss threshold), the more work will be needed at the ends. So you are not eliminating latency due to packet loss, you are simply moving it away from packet retransmission into the process of ECC. However, if you've got good ECC, the total latency will go down.
The ECC approach may be a nice middle ground. But, it the ultimate solution to minimize latency is probably through a combination of active queue management (AQM) and early congestion notification (ECN). Unlike ECC, this approach really would aim to eliminate packet loss in the network due to congestion, and therefore completely eliminate the associated latency. Either ECC or regular TCP would benefit. In a controlled testbed using AQM and ECN, I've completely saturated a network with gigabits of traffic, consisting of thousands of flows, and had virtually no packet loss.
It should also be noted that retransmission is NOT the dominant source of transport latency in of TCP. I am a co-author on a paper that shows another way (other than eliminating retransmission) to greatly reduce the transport latency of TCP. The basic idea is that the send-side socket buffer turns out to be the dominant source of latency (data sits in the kernel socket buffer waiting for transmission). In the above paper, we show how a dynamic socket buffer (one that tracks the congestion window) can dramatically reduce the transport latency of TCP. We allow applications to select this behaviour through a TCP_MINBUF socket option.
-- Buck
Actually, TCP increases exponentially until the first packet is dropped. It backs off to half, then increases linearly, until another packet is dropped, backs off to half ...
This means that a TCP connection uses ~75% of the bandwidth available to it (after all this stabilizes). So if there is only a single tcp connection over a given length, it will be 75% full at best. However, the whole reason for doing a lot of this is to allow many connections to coexist. If you transmit as fast as possible, you will get the highest throughput possible, but you will end up with a lot of dropped packets and won't play nice with others.