Slashdot Mirror
Increasing Wireless Network Speed By 1000% By Replacing Packets With Algebra
MrSeb writes "A team of researchers from MIT, Caltech, Harvard, and other universities in Europe, have devised a way of boosting the performance of wireless networks by up to 10 times — without increasing transmission power, adding more base stations, or using more wireless spectrum. The researchers' creation, coded TCP, is a novel way of transmitting data so that lost packets don't result in higher latency or re-sent data. With coded TCP, blocks of packets are clumped together and then transformed into algebraic equations (PDF) that describe the packets. If part of the message is lost, the receiver can solve the equation to derive the missing data. The process of solving the equations is simple and linear, meaning it doesn't require much processing on behalf of the router/smartphone/laptop. In testing, the coded TCP resulted in some dramatic improvements. MIT found that campus WiFi (2% packet loss) jumped from 1Mbps to 16Mbps. On a fast-moving train (5% packet loss), the connection speed jumped from 0.5Mbps to 13.5Mbps. Moving forward, coded TCP is expected to have huge repercussions on the performance of LTE and WiFi networks — and the technology has already been commercially licensed to several hardware makers."
...I don't see how it will solve "spectrum crunch" when every nibble of your LTE bandwidth is oversubscribed by 5 to 1. Whether you have 32 users doing 10 Mbps streams, or 320 user doing 1 Mbps streams, it's all accounted for. I'd certainly like to be one of the 10, but 20 Mhz worth of spectrum at 16 symbols/Hertz is not a limitation you can change with fast/excellent forward error correction.
If you've ever used Usenet, and you've used parity files to recover missing segments of data, then you know exactly how this technique works.
Frankly, I'm surprised it took so long for someone to apply it to lossy network environments. It seems obvious in hindsight.
Cyde Weys Musings - Scrutinizing the inscrutable
... the new Linksys 802.11x=(-b+/-sqrt(b^2-4ac))/2a router!
Dear Slashdot: next time you want to mess with the site, add a rich-text editor for comments.
I agree that it's not a magic bullet. The point is, however, that the overall throughput of the network was increased by better usage of the available resources! If the *effective* available bandwidth is increased, then the performance of everyone "nibbling" on that network will *also* presumably increase. Also, think how much more money carriers may be able to squeeze out of users without needing to invest more in infrastructure! [/sarcasm]
Article is very light in details (except "Libraries of Congress" things), but it looks like those guys implemented a kind of error correction code (ECC) to recover lost data through extra data found in other packets. This has been in use for various types of networks (optical, DSL, GSM) for years.
Of course it is all down to how good the actual algorithm ("algebra") is in terms of overhead vs extent/capability of error correction vs introduced coding delay. There is always a trade-off, but a particular algorithm can take into account technology specifics (WiFi) and optimize it very well for a given task (whole packet lost, but not so often).
Journalists like to put BIG BUZZWORDS to well known things.
So basically they're applying interleaved checksumming error correction (a la RAID5)? Good idea. What they didn't say is how much extra data was required to be sent by their solution. If they want to be able to recover 10% packet loss, presumably that means at least 10% more data sent, and there's still a failure point where the loss is greater than the checksum's size.
We've had these algorithms for decades. I've long been frustrated that checksums/ECC are not used at every single transmission and receiving point. Let's put this into the expansion bus, memory bus (ECC), and filesystem (btrfs/zfs), and of course, wifi and wired networks. Unfortunately the drive to the price floor resulted in everyone wanting to shave that 10% to make things cheaper. ECC was once commonly available in consumer hardware too, now you can only find it on ultra-specialized and ultra-pricey rackmount server hardware.
The 1980's assumption that the error is 1e-20, so can be ignored, is demonstrably false in nearly every computer application today. We need to (re-)start designing error correction into everything. Hey, why not use adaptive error correction, that increases the size of the checksum when the measured loss increases?
1^2=1; (-1)^2=1; 1^2=(-1)^2; 1=-1; 1=0.
Forward error correction - there are different algorithms that are dime a dozen.
The one thing that *does* surprise me is that no such thing is built-in to the link layer of 802.11 spec. Physical layer does whatever it can to garner signal from the noise, but there is no redundant data at higher layers at all.
All this has of course resulted in a gazillion papers on that very topic, hoping to see practical application soon.
You know what the best part about UDP jokes is? I don't care if you get it or not.
s/[stupid comments]/[intelligent discourse]/gi
It's an error-correction method that happens to have compression built-in.
Also, I really wish people would stop shitting on new technologies like they're some sort of oracle. This is awesome. Accept it.
It's better to vote for what you want and not get it than to vote for what you don't want and get it.
- E. Debs
By definition, UDP sessions don't have delivery garantees like TCP does. That's what TCP does! It provides a mechanism for clients to ensure integrity and ordering of received packets. Netbios is an encapsulated protocol over IP, which uses TCP to ensure delivery. ICMP... really? Are you really asking for delivery correction on multi packet ICMP? For real? You do realize that fragmented ICMP is a nono, right, and that ICMP should be wholly contained in single packet messages?
While true that I wouldn't work for UDP, the clearing of traffic normally consumed by TCP requests and responses would improve performance of UDP by making the medium more available even if the coded TCP method has no direct implication with UDP. (It is up to the UDP session members to negotiate and handle lost datagrams. Not the network stack. UDP is intended for custom user protocols that can't easily live inside a TCP/IP packet, like large video or streaming audio feeds. Normally these protocols can deal with loss, and the burden of ensuring 100% delivery comes at prohibitive performance costs, so UDP with acceptible loss is ideal.)
Comment removed based on user account deletion
How is it not compression? It reduces the data size being transferred and is recoverable on the other end.
No, it slightly increases the data size being transferred, thus allowing it to be recoverable on the other end if there are minor losses.
Here's an example of how it might work. Say you have a packet that holds 1024 bytes of payload data, plus a few extra for overhead. (Probably not realistic, but this is just to lay out the principles involved.) Now, you could send all 1024 bytes as straight data, but then if even 1 bit is wrong, the whole packet must be re-sent, adding latency. Instead, you send (say) only 896 bytes of actual data, and 128 bytes of recovery data. You break up the data into 64-byte blocks. Thus you have 14 blocks of actual data. The other 2 blocks consist of recovery data, generated by some sort of mathematical equation too complicated to describe here (and which frankly I don't understand myself). Here's the trick: on the receiving end, any 14 of the 16 blocks is enough to recover the whole 896-byte original datagram. Doesn't matter which 2 blocks are bad, as long as no more than 2 are bad, you can recover the whole thing.
This could be useful in an environment where packet loss is very high. A similar method is currently used when transmitting large binary files on Usenet, since many Usenet servers do not have 100% propagation and/or retention.
Just send a starting position in PI and a length.
Implementation is left as an exercise.
How is it not compression? It reduces the data size being transferred and is recoverable on the other end. Maybe I'm not an expert, but isn't that _exactly_ the definition of compression?
It doesn't make it smaller - in fact, it will make the data larger. It gives improved performance because of the way TCP responds to dropped packets:
(1) Normally the receiver has to notice the dropped packet, notify the sender, and wait for the packet to be retransmitted - meaning that the data in question (and any data after it in the stream) is delayed by at least one round-trip. With this scheme, there is enough redundancy in the data that the receiver can reconstruct the missing data provided not too much is lost, improving the latency.
(2)TCP responds to packet loss by assuming that it is an indication of link congestion, and slowing down transmission. With wired links, this is a good assumption, and results in TCP using the full bandwidth of the link fairly smoothly. With wireless links, however, you can get loss due to random interference, and so TCP will often end up going slower than it needs to as a result. The error correction allows this to be avoided too.
Need to type accents and special characters in Windows? Use FrKeys
That's kinda the point. Crappy signal results in high packet loss. If you can recover lost packets through some recipient-side magic (clever math, apparently) rather than retransmission, you avoid the overhead of another roundtrip, and get higher bandwidth as a result. This cuts down massively on latency (huge win) and should also decrease network congestion significantly.
I'm trying to think of a way to put this in the requisite car analogy, but don't honestly know enough about the lower-level parts of the network stack to do so without sounding like an idiot to someone sufficiently informed. But I'm sure there's something about a car exploding and all traffic backs up for tens of miles along the way ;)
How are sites slashdotted when nobody reads TFAs?
Shannon Limit shows that there is only so much information that can fit in a channel.
Plenty of forward error correction codes exist (algebraic encodings) to enable a channel to approach the shannon limit. Most of you have heard of Reed-Solomon or Hamming Code before.
NASA has used these since the 1970s to provide a more robust link with the effect of utilizing more bandwidth of that link.
This is a little fancier than what I mentioned, but conceptually similar I imagine. The advantage of just using some existing forward error correction, perhaps combined with one of the popular compression algorithms, is that techniques that have been in use for the past 4 decades probably can't have enforceable patents placed on it.
“Common sense is not so common.” — Voltaire
Also, think how much more money carriers may be able to squeeze out of users without needing to invest more in infrastructure!
This might actually hurt them then because they charge by what was transmitted, not by what was received.
Don't know something? Look it up. Still don't know? Then ask.
Not data compression, more like ECC or forward error correction
That works, actually!
The problem is that on average, the number of bits needed to express the starting position in pi is equal to the number of bits you are transmitting.
This is why I think this will not catch on easily. You can't just put a new router with their coding functionality into your home and expect this to work. It also needs support from the server hosting the content you want to acces.
The way they designed their system is end to end. Meaning that the internet server has to run a modified TCP stack and the client system (alternatively your router inbetween) also has to understand this modified TCP dialect.
The chance of millions of Internet servers changing to a (likely) patented, proprietary version of TCP is ZERO.
This is why this idea will fail.
Christian
--- Eat my sig.
This is not simple data compression or error control coding. This is network coding, e.g., see http://en.wikipedia.org/wiki/Linear_network_coding [wikipedia.org] and how it can increase the capacity in the butterfly network over traditional packet routing schemes, counter to our intuition for flow networks/water pipes.
It is a fairly hot research topic that has been around for last few years. But it is fairly revolutionary. It is still early days in terms of practical coding schemes and implementations.
This is awesome. Accept it.
I agree, but... this is Slashdot.
systemd is Roko's Basilisk.
My grandpa used to tell me stories of old men who pulled up into town offering medicinal cures for all sorts of diseases, old age, arthur-itis, bad vision, whatever.
"Medicine men" would orchestrate a "medicine show" with all sorts of claims and testimonies of the miracles of the precious snake oils he vended. Fistfuls of cash soon filled the air, and his cronies went through them exchanging their hard-earned cash for bottles of God-knows-what. ( Grandpa tells me the most common ingredients were assortments of oily vegetables with a smattering of creosote - same stuff used to preserve telephone poles - thrown in for good measure - and maybe a smattering of moonshine to give it a medicinal smell ).
These were simple old country folk he sold to - mostly farmers. They knew all about how to run a farm, and respected their doctor - and the charlatans of the medicine show knew full well how to monetize the people's faith in the technical jargon of chemistry.
A few days after the wagon left town, the people discovered they were no better off, and quite a bit poorer, after the medicine man left.
Woe to the medicine man if he visited a town a few weeks after another medicine man had pulled his scheme off.
I think we have seen so much stuff today whose sole purpose is monetizing bullshit, that we are leery of accepting stuff we do not understand. I - for one - would love to understand Rossi's "eCat" cold fusion LENR device, but the shroud of secrecy around it, along with what YouTube video I have seen of it has me believing it is just more snake oil, however much I would love to see something like this actually work..
As far as packet loss is concerned, if its a problem, put each packet through ECC just as we do on CD's or DVD's - and match the ECC size to the packet size. To me that is obvious - and being I am not advanced in this field - I think I would be reasonable in claiming that is an obvious use of the technology
Actually they came up with yet another method of Forward Error Correction (FEC). I haven't had time to read the article and look forward to see how they compare to Reed-Solomon or other Reed-Muller codes (Walsh-Hadamard code is used in CDMA).
This isn't exactly new but I'm glad to see someone take the initiative to apply it to today's WiFi networks. The mentality as of late is that the speed is more than fast enough to deliver the data and the occasional resend. FEC currently used where data rates are quite limited or the latencies are such that retransmissions are prohibitive long.
These comments are my own and do not necessarily reflect the views or opinions of my employer or colleagues...
There is no compression. Its RX error correction. This, seemingly, will reduce latency and increase effective throughput because you are now spending less time in a RX/TX retransmit cycle or a TX-TO retransmit cycle. As such, it allows more time for TCP window scaling to open up, even in the face of lost packets. In turn, a larger window means higher throughput with less protocol overhead.
I completely agree. Its awesome.
Also, I really wish people would stop shitting on new technologies like they're some sort of oracle. This is awesome. Accept it.
But if I keep shitting on new stuff like that, I can point back to my posts and say "LOOK! SEE? I SAID SO! I DID! ADMIT I WAS RIGHT FOR ONCE!!!!1!" if it fails. If it succeeds, though, I'm counting on nobody remembering my old posts so I can join in the praising of it later! It's a foolproof win-win for me, and that's all that matters!
Sorry, but those people were right. They don't need anything more than simple addition to work at Starbucks making crappy burnt coffee drinks. The fact that their mobile phones will work better as they send inane messages to each other on Facebook is nice, but it doesn't require them to know any algebra or other higher math; the engineers (in other countries where math is valued) implementing this stuff need to know that math, but the users don't.
The reason this is a problem at all is because TCP was developed for wired networks in which packet loss was almost always a signal of congestion -- and therefore the logical response was to reduce the rate.
In these newfangled wireless networks losses can be completely random, yet TCP will still assume that congestion is responsible and reduce its rate. So, the answer is to either change TCP or do correction at a lower layer to "hide" the losses from TCP -- and, this has been a subject of research in networking for years now.
Linear coding certainly isn't new -- it has been proposed for a variety of things -- including but not limited to bittorrent, to reduce the reliance on receiving a specific block and rather on simply receiving "enough" information.
So yes, it is all well and good that we are applying this technique to TCP to reduce the impact of random, noncongestion losses, but there had better be something pretty magical in the way they do it for it to be (IMO) novel enough to be patentable/licensable/etc.
The concept of using algebra is a unique step forward in this field.
No it isn't. It's the way all error correcting codes work.
This stuff is maybe 50 years old!
Watch this Heartland Institute video
Think of it as bitmap vs vector graphic.
I drank what? -- Socrates
And the problem with TCP jokes is people keep retelling them slower until you get them.
The actual paper, which I need to read a few more times, proposes at least two mechanisms. One problem with TCP is that, when ICMP Source Quench went away in the 1980s, the assumption was made that a lost packet indicated congestion. So a lost packet means slow down. This is a problem for systems with high packet loss rates and no link level retransmit, like WiFi. Also, with TCP, packets need not arrive in order, but if one is missing, all later packets have to be retransmitted, because the ACK scheme has no way to describe which byte ranges are missing, just the last good sequence number. So losing one packet when there are many in flight costs multiple retransmits.
Their solution involves addressing both of those issues. Then they add the "algebra", which is a simple form of forward error correction. They send M linear combinations of N packets, M > N, from which all N packets can be reconstructed provided that not more than K packets are lost where K Why is that? This is a link layer problem and ought to be dealt with at the link layer. FEC at the WiFi link layer is apparently not as effective as it should be.
Don't be so sure. Lots of people make tons of money in this country without doing any math. Look at contractors (plumbers, HVAC repair, etc.); they make really good money without any real education and without having to do any math. They probably make out better than most engineers. Or look at Mitt Romney: you think he's ever had to do any math in his business? Heck, go all the way back to Thomas Edison: that guy didn't understand math either (that's why he hated AC power). And he got filthy rich basically by using a brute-force method.
The point is it will give them higher data rates for free which they can then charge extra for.
If you believe carriers will get rich and fat from this, then by all means, buy stock! They are public companies. Put your money where your mouth is.
I'd put my money in hay bales, personally, considering people such as AC here's propensity for building strawmen.
An enigma, wrapped in a riddle, shrouded in bacon and cheese
I work in Sattelite Communications and we use these algorithims by default. We call it forward error correction. I would assume that they would use a much less aggressive algorithim, maby 1 correction bit per 8-16 bits rather than a 1 for 1 data, or a 1 for 2 data that you see for dirty links in the space operations. See http://en.wikipedia.org/wiki/Viterbi_algorithm or http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction. The additional throughput is not from compression but from not having to TCP resend entire packets and probably also prevents the TCP window from resetting.
It prevents backtracking the stream.
Say you have 10 packets to transmit. You encode them into 10 linearly combined results, with a 10-byte coefficient header (1 per packet), and transmit those 10 encoded packets.
If the 5th packet was lost, in standard TCP you'd need to retransmit packets 5-10. With this encoding, you could in theory transmit only 1 packet to complete the set, regardless of which was lost, based on how the new ACKs describe the algebraic degrees of freedom remaining in solving for the original packet bytes. That means that you put out 11 packets instead of 15 packets into the same noisy environment, and the existing TCP window controls perceive less losses. If everybody does that, the overall contention might go down compared to stock TCP.
In the case where it's very difficult to get any individual packet through, I could see this still encoding 2-3 packets at a time and saving bandwidth on resending vs regular unencoded serial transmission.
(given my skimming of the paper)
Car analogy: Somebody ships you a car. It arrives with a bent bumper. Instead of having the source shipping you a new car, you just unbend the bumper.
Most of the posters here seem to misunderstand what this is; it is NOT just a simple Forward Error Correction scheme.
TCP has two design decisions (as pointed out by others) that are totally wrong for a WiFi environment where random packet loss is a normal and expected operating condition:
1. A lost packet means a collision or network congestion, therefore the proper response to a lost packet notification is to slow down the transmit rate
2. When packet #2 is lost, even though the client has perfectly cromulent copies of packets 3-1094932, they must *all* be thrown away and the entire stream is restarted. There is no facility to go back and retransmit just the missing packet - the ACK can't say "I got packets 1,3-1094932, please just re-send #2".
This new scheme reconstructs packet #2 in this scenario by using the FEC data in the other packets. This allows the link to tolerate a certain % of packet loss without requiring any re-transmits, thus all those packets from 3 upwards don't have to be retransmitted. It also greatly reduces latency as reconstructing packet #2 is faster (due to the computationally efficient FEC algorithm) than requesting a retransmit. This also prevents the TCP link from scaling back its transmit rate, further improving performance.
It's definitely clever. One of the downsides of relying on older technology (TCP in this case) is when it makes fundamental assumptions that are completely, horribly wrong for new applications (WiFi).
To those who ask why not just do this at the link layer? Because then you are wasting the effort on protocols like UDP, etc that may not want or need this kind of correction. It may also introduce delays that are unacceptable for certain applications (like VoIP). A 50ms delay is great to avoid degrading your file transfer from 10mbit to 0.5mbit, but is completely useless during a VoIP call or a multi-player FPS. Personally I'd like to see this kind of tech rolled into the next version of TCP to make it an official part of the standard... then again I'd like to see the standard MTU size increased given the ubiquity of gigabit ethernet these days, but that still hasn't happened as far as I know, due to incompatibilities, interop issues, etc.
Natural != (nontoxic || beneficial)
Nope, Nowadays we have pi on tap
Sadly, most people who are plumbers are probably better qualified then most people who call themselves programmers. I think that all degrees/diplomas should require some kind of apprenticeship/co-operative education/internship program to get you real on the job experience. There's only so much that can be learned in the classroom. Being on the job, doing actual work allows you to learn a lot of stuff that just would not come up in a classroom.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
better: there is an unknown part that was found rattling around inside. you find out what it was and put it back where it should have been.
--
"It is now safe to switch off your computer."