Slashdot Log In
Replacing TCP?
Posted by
michael
on Thu Oct 21, 2004 10:36 AM
from the step-by-step-the-largest-network-can-be-replaced dept.
from the step-by-step-the-largest-network-can-be-replaced dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Has anyone considered Decnet? (Score:4, Interesting)
Re:Has anyone considered Decnet? (Score:5, Informative)
http://en.wikipedia.org/wiki/DECnet
John.
Parent
nonsense (Score:4, Interesting)
Re:nonsense (Score:4, Interesting)
Somehow, the title of your post is appropriate for the subject of your mesaage.
Did you pull that 50 years out of your..... you know.
Change is not going to happen overnight. They are suggesting a better protocol which is still in the labs for the most part.
Remember how long since IPv6 is out? And now check what we are still using. It's all about changing it gradually.
Parent
Re:nonsense (Score:5, Funny)
Duuude, you can't compare TCP to IP, they're different units! You have to divide them (TCP/IP)!
Parent
Evil Bit? (Score:5, Funny)
A working wikipedia link for Kademlia (Score:4, Informative)
Old!=bad (Score:5, Insightful)
Re:Old!=bad (Score:5, Interesting)
This problem stems from the fact that TCP calculates the congestion of the channel based on its round-trip time. The round-trip 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.
I find it kind of interesting that these are two competing problems: one having to do with high bandwidth (and presumably high-reliability) connections, the other with low-reliability connections. My home DSL, however, often fits into the latter category: 3% packet loss is not uncommon on bad days. So maybe the two aren't so incompatible after all.
Parent
Re:Old!=bad (Score:5, Informative)
That's what selective ack is for. It's pretty old hat at this point, everyone has it implemented.
Parent
Re:Old!=bad (Score:5, Informative)
So you're really only concerining yourself with ordered delivery when the delay in the natural order is greater than that of the sliding window (the cache of received packets that you're not going to tell the software about just yet)
This takes care of trivial things where packets arrive "just barely" out of order, but in a true packet loss situation, can block the channel for quite some time.
So the strict sequence you refer to is the sequence the packets are presented to the next layer (usually the application in Ethernet), not the sequence the packets are received by the machine.
Parent
Re:Old!=bad (Score:5, Insightful)
As they mention on their site, TCP's bandwidth usage is dependent on the latency of the link. This is due to the fact that sliding windows (the number of packets that are allowed to be out on the network) have a limited size. TCP sends a windowful of packets, then waits until one is acknowledged before sending another one. On high-latency links, this can cause a lot of bandwidth to go unused. There is an extension to TCP that allows for larger windows, addressing this problem.
Another problem with TCP is slow start and rapid back-off. IIRC, a TCP connection linearly increases its bandwidth, but will halve it immediately when a packet is lost. The former makes for a very slow startup, whereas the latter causes a connection to slow down dramatically, even though a lost packet can be due to many factors other than congestion. Slow start has been addressed by allowing connections to speed up quicker, about rapid back-off I'm not sure.
The solution this company provides seems to play nice with TCP by varying the transmission speed in waves. Apparently, this improves speed over TCP's back-off mechanism, but it obviously doesn't provide optimal bandwidth utilization.
Parent
Re:Old!=bad (Score:5, Informative)
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.
Parent
Is it an open protocol? (Score:5, Insightful)
Re:Is it an open protocol? (Score:5, Informative)
It doesn't look good. Their webpage [rateless.com] says:``We are planning to release Rateless Codes for free, non-commercial use, in open source under the GNU Public License.'' They are seriously confused about the terms of their own license. The GPL doesn't lend itself to ``free, non-commercial use'': it lets the licensee use and distribute freely, at any price, for any use.
Either they'll loose that ``non-commercial use'' crap, or this will go nowhere.
Parent
Re:Is it an open protocol? (Score:5, Interesting)
Don't get me wrong, I think they mean well, but they are trying to prohibit commercial use of GPL-linked works. Nobody said the GPL was always friendly to your business plan, but you can either take it or leave it, not have it both ways. I know one of the founders of this company, Chris Coyne - he used to regularly come to my parties in college. Nice guys, and I am sure they mean well. They could use some serious guidance though on licensing and IP issues, not to mention trying to make a viable business out of network software, which is a tough proposition in itself.
Feel free to contact me if you need help guys.
Parent
Re:Is it an open protocol? (Score:5, Funny)
No point really not releasing it under a BSD licence in the first place, save leting the BSD guys write a far better version for the world to use.
The RFC is more important than the code anyway, and there fools for not writing the RFC first.
Parent
Re:Is it an open protocol? (Score:5, Informative)
Almost true. It gives you a license to distribute that code, under certain terms. No license is needed to use a copy. Read section 5 of the GPL [gnu.org] for an elegant confirmation of that.
When they say "free, non-commercial use", and they talk about the GPL, they are making sense. The Linux kernel, which is GPL, may use their implementation.
Sorry, you're way off here. Redhat sells Linux, and their customers use it for commercial purposes. Therefore, the Redhat version of the Linux kernel can't use their implementation. The issue is moot, however, since the non-commercial restriction would make their license non-GPL-compatible. Their implementation couldn't be included even in a kernel which would see non-commercial use only.
Microsoft cannot use their implementation in any of its Windows OSes ...
Wrong. If MS wanted to make a version which they would give free of charge to private individuals and charitable organizations, they could use it, since that would be entirely non-commercial, both in distribution and in use.
For MS, that would be a problem, but it's the GPL part, not the non-commercial part, that would bite them. As I said above, the non-commercial restriction would render this license incompatible with the GPL.
The GPL does not lend itself to "commercial use", because the "standard" model of software licensing is paying a price per use/copy of the binary, and the GPL doesn't work this way.
Sorry, you've mis-construed non-commercial. Non-commercial typically means not used in commerce. Believe it or not, is is possible to sell software for non-commercial use. If you run your business using the software, that's commercial use. By the way, you should tell Redhat and Novell that bit about the GPL not working for ``paying a price per use/copy of the binary'', that'll be a revelation to them.
Parent
What exactly about TCP is getting old? (Score:4, Insightful)
TCP is old...so what? (Score:5, Insightful)
This isn't a general TCP Replacement (Score:5, Insightful)
- They have a "TCP-friendliness" option that varies the transmission rate in a way that TCP windowing can probably cooperate with, so you can set the rate knobs to something less than full blast,
- but nothing they've documented appears to address the problem of multiple users of this application trying to use a transmission path at the same time, and
- they also don't document anything that does path rate discovery - so it may work fine if you've got a couple of small pipes feeding a fat network, but if you've got a fat pipe on the sending end and a skinny pipe on the receiving end, they don't document anything that figures out what rate is safe to transmit at.
They also don't document when you would want to use this and when you would want to use TCP and when you would want to use this on top of TCP.Parent
I wouldn't make any mention of bittorrent, etc.. (Score:5, Insightful)
It's good to see innovation though, nonetheless.
Rateless Internet (slashdotted) (Score:5, Informative)
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.
What? (Score:5, Informative)
1. TCP does not use round trip time to calculate any "congestion levels." It increases the connection rate until packets get dropped, presumably because some router in the middle got overloaded.
2. Packet loss is used as a signal to TCP to slow down because it tried to send too fast. The lost packets are subsequently retransmitted, so TCP can indeed not only tolerate but recover from packet loss. The only real case they have is packet loss due to reasons other than TCP's own aggressive sending rate, such as UDP traffic, wireless links, etc.
Given these concerns, I can't help but think that they are inventing a protocol that works well only if used on a small scale. TCP is designed to back down if it thinks it's sending too fast, and is not really optimal. One can always hack a pair of TCP nodes to not play by the rules and get more than the fair share, but the problem is that that solution wouldn't work if it were adopted network-wide.
Parent
Re:What? (Score:5, Insightful)
TCP doesn't use round trip time to calculate a link speed. In fact, it doesn't just the opposite. It uses a sliding window method so it can send many packets before any one has ACKed. This is done to soften the blow that round trip times will have on your send rates!
TCP regulates its send rates by slowly sending faster and faster, then when a packet is dropped, it drops its rate fast. Slow increases and exponential backoffs make for VERY efficient link utilization on reliable networks with many active nodes whether it be a fast office LAN or world wide network.
Their method appears to just spray data without paying attention to what other nodes are doing. It sounds like it is much better suited for point to point communications on unreliable networks. E.g. cellular data networks, packets get dropped much more frequently because of interference rather than congestions. TCP might back off too quickly in this condition because it is optimized to deal with congestion. Their protocol might be great for that first/last hop between your cell phone and the cell tower but otherwise, it undermines the great balance that TCP achieves on our amazing little internet.
Parent
Brilliant! (Score:4, Insightful)
A slightly faster equivelent to TCP that I have to pay for and no-one else uses.
Sign me up for that sucker right now.
Whew! (Score:5, Funny)
Often stories are posted that refer to products or code names, with no description, which is quite annoying.
I'm glad to see this post doesn't run that risk.
Thanks for clearing that up for me.
-d
Is replacing TCP necessary? (Score:5, Insightful)
If you want to replace TCP, you have to do more than just develop a new protocol that is faster. It would have to outperform TCP in speed, reliability, and substantially so in order to outweigh the costs of ditching a well-established and trusted protocol.
Ugh -- eyes are playing tricks on me. (Score:5, Funny)
The guy who started it, Petar Maymounkov, is of Kademlia fame."
The guy who started it, Petar Maymounkov, is of Chlamydia fame."
I was about to wonder what sort of "fame" you could get from that. Need coffee. Need sleep.
IronChefMorimoto
Respect! (Score:5, Funny)
Find out what it means to me
R-E-S-P-E-C-T
Take care, TCP
Oh socket to me, socket to me,
socket to me, socket to me...
Re:Respect! (Score:5, Funny)
Parent
ANY loss level?? (Score:5, Funny)
Not gonna work if encumbered (Score:5, Insightful)
2. They don't seem to understand the GPL:
"We are planning to release Rateless Codes for free, non-commercial use, in open source under the GNU Public License."
The GPL doesn't restrict commercial use, and hence the only way that they can do this is either they try to add some conditions to the GPL, or they use another mechanism to restrict commercial use: e.g. patents.
No matter how good this technology is it's not going to get wide adoption is an alternative to TCP unless it's unencumbered.
John.
Re:Not gonna work if encumbered (Score:5, Insightful)
Parent
Encoded Packets doesn't Solve Problems (Score:5, Insightful)
1) The major problem a TCP packet will face is getting dropped. They mention this problem. They claim their encoding will solve this problem. It won't. No ECC algorithm will allow you to recover a dropped packet.
2) Most packets that are corrupted are corrupted well beyond the repair of most ECCs.
3) ECCs will cause packet size to increase. Not a huge problem, but why do it when ECCs don't help too much to begin with?
Re:Encoded Packets doesn't Solve Problems (Score:5, Informative)
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.
Parent
Re:Encoded Packets doesn't Solve Problems (Score:5, Informative)
Rateless codes are important because they are the first step to a "digital fountain" model of data transfer. The idea is this: say you have a file of 10KB. Using erasure codes, you can "oversample" this file -- that is, turn this file into 40 1KB chunks. Now by collecting ANY 10 of these 1KB chunks, you can reconstruct the original file.
The reason the digital fountain is so cool (and the reason for its name) is because it would make the most amazing BitTorrent client ever. Why? In BitTorrent, you're doing things like choking/unchoking, aggressively seeking the rarest pieces, and hoping that some guy who has the ONLY COPY of piece X doesn't leave the network before it is replicated. Using Erasure Codes, everyone would just blindly get whatever data is sent to them (where each data unit is an "oversample"), and blindly forward it on all outbound links. But if you're getting data in this manner, isn't there a chance you'd get the same piece of data twice (which is like getting the same piece twice in BitTorrent, which is no use)? If you oversample enough, you can make the chance of this happening approach 0. Note in this scheme, there's no choking or unchoking here (so you'll never go through a period of time on a rare torrent where EVERYONE is choking you, and your download rate is 0KB/s), and you don't have to worry about that one guy leaving the swarm with some critical piece -- not just because you can always reconstruct it, but also because that piece is no more critical than any other.
It's beautiful, really. So why aren't we doing it? Simple -- erasure codes are computationally expensive to compute, although
they're getting easier as new sorts of erasure codes are being developed, and PCs get faster. The first big breakthrough was with Tornado codes [ucla.edu], if I remember correctly. Anyway, we'll see what the future holds...
- shadowmatter
Parent
Good luck, but it will never happen (Score:5, Insightful)
Yawn (Score:5, Insightful)
ASCII is still around, despite its numerous shortcomings. There's this small thing called "backward compatibility" that people/consumers seem to love, for some reason. Well, same thing for TCP/IP. Even IPv6 has trouble taking off in the general public, despite being essentially just a small change in the format, so never mind the YAWN Protocol this article is about...
Doesn't work. Sorry, do not collect $200. (Score:5, Informative)
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.
Re:Doesn't work. Sorry, do not collect $200. (Score:5, Informative)
Just transfered a ~600MB (Linux CD) ISO from Europe to Australia.
rateless-copy did about 400K/s
scp managed 2.8M/s
At least both files were intact
Parent
SCTP (Score:5, Interesting)
Intro here [uni-essen.de]
- SCTP can be used in many "modes"
* Provides reliable messaging (like UDP,but reliable)
* Can be used as a stream protocol (like TCP).
* One connection/association can hold multiple streams.
* One-to-many relation for messaging.
* Better at dealing with syn flooding than TCP.
Then again, I guess inveting the wheel is more "fun"
Transport latency and TCP (Score:5, Informative)
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 [mit.edu] 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 [ieee.org] 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
Replacing TCP indeed (Score:5, Insightful)
As far as I can tell (their website could use some more straightforward actual content), this is more like bittorrent, where a file is cut up into blocks, the blocks get distributed across the network, and anyone interested in the file then reconstructs it from available data from all sources, not necessarily having to get the entire file correctly from a single source. Only it does it more efficiently than bittorrent.
The two protocols target very different uses. TCP excels in interactive use, where the data is sent as it is generated, and no error is tolerable in the single sender-to-receiver link. Bittorrent (and other distributed network protocols) target batch jobs, where throughput is more important than reliability (because reliability can be reconstructed on the client through clever hashing schemes), and where responsiveness is entirely irrelevant.
So, this could not possibly replace TCP, since it does not do what TCP is most useful for. At the same time, the criticisms aimed at TCP by the rateless designers are valid, but well known, since TCP is indeed poorly suited for high-volume high-throughput high-delay transmissions of prepackaged data.
Still, good job to them for trying to come up with better protocols for niche or not-so-niche markets. I wish them all the best.
I have a better protocol (Score:5, Funny)
How does it work? Well, it's layered over Rateless Internet, in which (as we all know) packets do not have to be resent. So it carefully loses all packets and relies on Rateless Internet to make sure they arrive safely at the other side and do not have to be resent. Because no packets need to make it from A to B, you don't need any network hardware, and data can be sent just as fast as your machine can drop packets.
Guess I'd better apply for a patent...
Their key error (Score:5, Insightful)
That's for just them. What if all hosts on the entire Internet were by design stuffing packets at a 3-5% error rate? Meltdown, that's what. Their "real-life" measurements do not scale, suffering from the usual assumed linearity of new designs for complex systems.
Sometimes people fall in love with their new ideas, thinking that the rest of the world missed something obvious.
Well... (Score:5, Informative)
So others can have fun slashdotting other technologies, here are some websites. There are probably others, but this should keep those who do really want to move away from TCP happy.
EC over IP I have been doing this for years. (Score:5, Interesting)
it was a 64K shared line with 90% packet loss, I received 60Kbps for the video stream. ( I have the video to prove it )
We even filled preliminary patents on this back in 1996 but they were never followed through with.
Luigi Rizzo (now head of the FreeBSD project)also did some excellent work on this also. http://info.iet.unipi.it/~luigi/fec.html [unipi.it]
He calls it Erasure codes.
Which is more accurate since UDP doesn't have errors, it either come across 99.999% perfect or not at all.
So there is more information then in an error situation where ever bit is questionable.
What this means almost 1/2 the hamming distance in the codes in needed to correct an errasure verses and error.
Turns out the Error/Erasure correcting scheme it critical and not obvious. I spent almost 5 years working on this part time before it started making some real breakthroughs.
My original system was designed for 25% packet loss (not uncommon in 1996).
In the inital idea we added 1 exored packet for every three data packets, but at 25% packet loss, it turns out that it didn't increase reliablity at all! Working this out with probablities was a major eye opener!
Even when you work the problem out you realize you will still need some retransmissions to make up for lost packets, there is no possible solutions without this.
I have been trying to find people to help opensource this since I have working far too hard just to survive since 2000 to even consider taking on another task.
Anyone interested in my research and carring this forward please see my site and contact me.
John L. Sokol
It's hooey... (Score:5, Insightful)
This is a load of fluff, trying to capitalize on the 'p2p craze'. There are plenty of TCP replacements out there, that actually make sense. As far as TCP not being able to utilize 'today's bandwidth', again...hooey. Gigabit ethernet (when backed by adequate hardware, and taking advantage of jumbo frames) moves a HELL (two orders of magnitude) of a lot more data than your typical home broadband connection...using TCP.
Re:Yet another "reliable UDP" layer (Score:5, Insightful)
Parent