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]
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
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?
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.
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.
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.
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)