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
Will it blend?
So this only covers TCP packets? What about UDP, ICMP, NETBIOS and other IP based protocols?
Sounds like a solution that is way too specialized.
What the fuck were they thinking?
It's like if tomorrow I invent a new protocol for mobile phones and I call it GSM.
Or is this a fucking joke?
To everyone who grew up saying that they never used math after high school, and it didn't have any meaningful use further than simple addition... you can kindly eat your own words now.
I'll just sit here and watch.
Pretty sure this has been done before, but perhaps not specifically applied to wireless networks.
This isn't data compression, it is however the same technique used for Par2 files used in usnet since, forever - not that new applications of existing technology shouldn't be lauded.
... 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.
That's what I thought. If any old packet could be represented as an equation, then I'll just send you a quick text and you can solve for the 50MB file your ISP's email is blocking.
So they basically re-invented forward error correction.
MIT, Caltech, Harvard, and other universities in Europe
I understand what they mean, but it's a silly way to write it. Maybe Slashdot should have someone who edits submissions.
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]
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?
Seems like they've solved the nasty issue with wireless, that the near constant packet loss really screws over TCP.
Losing a packet causes nasty delays while the error is bucked up and down the network/application stack. Wireless, do to it's nature, nearly always loses packets.
Wonder what the overhead is.
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.
It's been a while since I read the paper on exactly how it works, but isn't this basically the same principle as the par2 file recovery slices that have been used for Usenet binaries for quite some time?
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.
Overall throughput? I'm skeptical. I have yet to consistently get 3G speeds out of even a 4G phone.
I once took an excursion to Reddit, and later HN. Unlimited up/down voting sucks when dealing with a hive-mind.
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.
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
Think of it like really fancy checksums. Most of the data we no longer have to transfer is redundant packets re-sent due to errors.
Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
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
If your new error correction technology eliminates lost packets, and you lose 5% normally, then using this you gain 5% back not 10x. What they actually invented is data compression, and it's been around for decades.
While using complex algbraic expressions this is somewhat like raid or even the udpsender tool. Nice.
Efficiency in wireless communication is something of a purple elephant, mostly due to interference concerns that aren't at issue in wired Ethernet transactions. True, wired connections will have the occasional collision (though this is largely solved by modern algorithms and operating systems) but digital transmissions over an analog medium are difficult enough when they aren't running into each other in the air. And then you have other interference introduced by microwaves, whether from devices like cell phones, microwaves, or sunspots. It's a very noisy environment!
The concept of using algebra is a unique step forward in this field. Most here would agree, if you're in a crowded cafe and trying to carry on a conversation, it's easier to shout "Pythagoreas" than to talk about squares and triangles. But with computers it happens to be exactly the opposite because they're designed to compute -- it's what they do and what they like to do. So feed it generalities and, often, it can come up with specifics, much like the Monty Hall Paradox.
The next step appears to be to move from algebraics to broad descriptions of the type of data you want to download. This is waiting on computers with a great deal more processing power and perhaps emergent AI, but there will come a time where instead of feeding a bunch of packets over a noisy channel the Internet will simply say to your computer "short film with 20-something actor wondering whether to marry now or enjoy life for a while longer" and your system will fill in the rest, completing the transfer mathematically. This is down the road a ways, but newer technology such as lossy compression for data is already available and potentially lucrative for those who are willing to think outside of the conventional box and try something with a few more holes in it.
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
3G speeds out of my 3G phone.
HSPDA+ 'should' be capable of providing me with WAY more bandwidth than I could possibly need from my phone (42MB/ps?).
I know this is a theoretical speed, but at least in the UK there is a order of magnitude difference between what you actually get using this tech, based on your operator. I.e. the majority of telcos could up their average speed, but for cost reasons choose not to (or more fairly, wouldn't expect the investment to pay off due to the complete lack of interest from the majority of their customers).
I completely fail to see why LTE will be any different for the consumer - the case for the telco is fantastic, as it removes the need to keep on increasing their pt2pt backhaul, but consumers paying extra for 'LTE' now... eejits. If you want speed switch to a decent 3G telco. If you want to save money, just wait a bit and select the telco that's small/flexible enough to bite the bullet and ask/pay for you to switch.
Wait. Wait... wait.
I am going to use algebra for something in my life?
I just lost a bet 12 years ago.
It's called forward error correction and it requires sending additional redundant data so you can solve for what is missing. Sending additional redundant data does use more spectrum for the same throughput, because you're sending more data. It may be worth it to avoid retransmissions when data is lost, but it definitely use using additional spectrum.
This is nothing new, your computer uses FEC on its storage (HDD or SSD) and maybe even on its RAM (if it has ECC RAM).
http://lkml.org/lkml/2005/8/20/95
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 makes me glad that I learned Algebra in high school. At last I can apply it!
I've only read the abstract of the article and this is probably a stupid question but as i understand it, this algorithm is designed to efficiently recover lost packets in the transmission, so when the article claims that "MIT found that campus WiFi (2% packet loss) jumped from 1Mbps to 16Mbps" shouldn't the increase in speed be only 2% and not 16x?
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
Seems to me it is a much data compression as RAID-5 is. Spread 2 packets of information across 3 packets. Lose any one of them and you are still OK. You didn't send any less data (in fact, you sent more) but you can tolerate lost packets now.
Note that I am NOT saying that is what they are doing, just giving an example where being able to lose data does not imply compression.
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.
It's obvious that nothing new has been invented here. It's just that they have put one previous idea cleverly together with another. What they are trying to do is to create Coded TCP... IP!!
*** Don't be dull.***
Not data compression, more like ECC or forward error correction
in Europe? Since when have they been in Europe?
I think the summary was meant to read
MIT, Caltech, Harvard, and several universities in Europe
:)
Ah yes, all we have to do is find an algebraic equation whose 1542 roots happen to match packet #1767 of the Angry Birds video. And whose coefficients take up less than 5%, 75 bytes lets say.
I thought up this compression scheme in 8th grade. even then I knew there just had to be some basic problem with it.
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.
Then the mathematic representation of the packet is effectively nothing, and even a computer with unplugged network cable becomes infinitely fast.
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.
We'll get the extra packets that were re-transmits for sure. But the throughput gain (if I understand their sketchy details correctly) is from dropped packets not causing a pause at the TCP window size limit waiting for the dropped packet. You can just keep streaming them and generally assume the other end is happy.
But this doesn't increase the available bandwidth of your transport network. And if every packet from 300 users is going out back-to-back with another users packet then it doesn't "fix spectrum crunch" any further than eliminating retries. They were estimating the fast moving train had a 5% drop rate. Assuming your area's 4G is saturated (I'm looking at you AT&T) with the same drop rate, you can expect 1) fewer pauses and a steadeir transmission 2) 5% more bandwidth.
Applying this technology to the "long fat pipe" problem for ftp-style transfers to Europe however sounds like a grand plan. I hope it becomes an IEEE standard soon.
You've invented data compression.
This is NOT data compression. It is more like "RAID for packets". If a packet is dropped, you can recreate it from the other packets instead of requesting it again.
Hasn't this already been solved for before? There are tons of FEC implementations out there. Shoot, from their description, they just PAR'd them all together and transmitted the parity as an (or some) extra packet(s). They just used "algebra" to generate their PAR.
Cool that someone's using it. Dynamic parity/FEC is a much better loss tolerant scenario than TCP's algorithm, but that doesn't make it new or novel. Silver Peak is a network acceleration device (like Riverbed) that integrates FEC, so it's been out commercially available for years. Putting it on an AP (with a matched wireless client) isn't that interesting. I could have done it 2 years ago with Silver Peak VMs running on the AP and my computer, though not as practical.
Maybe I'm just jaded because FEC and parity are things I've been working with for 20+ years.
Learn to love Alaska
Yeah, but you have to consider how they do math. You assume they calculate profit based on usage and rates. The reality is they calculate the rate based on the desired profit and usage. So when you use less data (fewer retransmits) they will just charge you more for the bits that get through.
The point is it will give them higher data rates for free which they can then charge extra for.
We hope your rules and wisdom choke you / Now we are one in everlasting peace
so, it's RAID for file transfers?
I didn't see the compression built in part? The correction allows better utilization but that's different than compression.
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.
It's called network coding
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
Another satisfied AT&T customer...
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!
You mean we get to keep all the hardware as is, and not pay more to get more..... I am in, but alas, Canadian Monopoly companies will see through this, and implant some way of getting more money for the lost bandwidth they are able to charge us for....too bad it is not credible business model.
It is news for nerds after all.
it's not awesome, sorry.
Isn't this a layering violation? Shouldn't this occur at the link layer? There is no reason for these redundant packets to be sent across the whole internet, just over wireless hops. In fact, over the rest of the internet, the old TCP behavior is the correct behavior.
No, they've invented forward error correction.
How novel.
"While the exact process is being kept secret (and has already been licensed by “several companies”), "
Fuck 'em and the horse they rode in to town on.
Watch this Heartland Institute video
The packets lost get resent and there is a time delay in that process if you don't have to do that then you save more TIME which could be used for more transmission. The difference is 2% packet loss being DATA and 16Mpbs being a data RATE.
The rate is impacted by the round trip delay for each lost packet-- which is not just 2 steps; it is 1 to send, 1 to request a resend, 1 to respond back. The nature of the traffic also impacts the speed because you have buffering and operations that block until the message is constructed before the next step can be performed which can amplify the delay. In a broadcast network like Wifi you can also have issues with the shared load impacting the rates where you can cross thresholds where the congestion causes rates to drop. The drop can be large relative to the small increase in load if a threshold is crossed.
Mod this ++good.
Watch this Heartland Institute video
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.
MIT always gives the impression that they are the first to accomplish anything. It's to the point that everyone outside of MIT take everything they crow about with a huge grain of salt.
RAIP: Redundant Array of Inexpensive Packets
I can see why they didn't use that acronym...
Think of it as bitmap vs vector graphic.
I drank what? -- Socrates
Yawn, they re-invented Turbo Coding and packet interleaving for FEC, and just used larger packets... https://en.wikipedia.org/wiki/Turbo_code
I understand what they mean, but it's a silly way to write it.
"MIT, Caltech, Harvard, and elite European universities." Either that, or California Institute of Technology and Massachusetts Institute of Technology are in Sweden. I've never been to Sweden, for all I know, there is a California, Sweden.
Learn to love Alaska
RAIP: Redundant Array of Inexpensive Packets
I can see why they didn't use that acronym...
From the Cloud:
Redundant Array of Packet Expediters.
As well as the resources it takes, in both CPU and storage, to compute pi out that far.
I would call it "RAID-5 for WiFi" Or how about RAID-Fi... :-)
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.
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.
So does this make bufferbloat better or worse?
MIT, Caltech, Harvard, and other universities in Europe
I understand what they mean, but it's a silly way to write it. Maybe Slashdot should have someone who edits submissions.
How would you revise it without adding anything?
Best I can come up with is
MIT, Caltech, and Harvard, as well as some European universities
It increases the amount transferred with the intention of minimizing total throughput. Not sending something isn't compression. Compression is sending less than you started with, and recovering the whole thing at the other end. This is FEC, where you send more than the original and then reconstruct the original at the other end.
Learn to love Alaska
Could that be overcome by conventionally breaking up pi into blocks of certain sizes, then conceptualizing those blocks as matrices of conventional height and width?
Esoteric reference.
From the excerpt, it sounds a little like wavelet compression. But that works well for lossy compression like video/audio. It's just really hard to get a formula that describes 'random-ish' data that would typically be going over WiFi.
To be honest, it smells like an infinite recursive compression story. I'd like to see proof of this before I get excited.
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?
While I agree with the people who say that it is not data compression, it is also worth noting that the question is beside the point - you may as well say 'it is communication' as if the fact that something of that nature has been done before renders it irrelevant. The point is that it is a clever, useful and significant extension to the state of the art.
Actually, on average, the number of bits needed to express the starting position in pi would greatly exceed the number of bits being transmitted.
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 always knew that cloud hosting companies were screwing us.
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.
Something must be awfully broken in order to make putting this in have a big impact.
They aren't compressing the data by making the router solve an equation. It sounds like there are so many dropped packets being dropped due to a few corrupted bits that adding a little redundancy overcomes that. Why are there so many corrupted bits? Somebody else mentioned that the routers are throttling back when packets drop because there's an assumption that dropped packets mean congestion. Maybe the real solution is to just not throttle back so eagerly. Don't get me wrong. It sounds like a great hack; but it also sounds like a band-aid as opposed to a real solution.
It's not compression, it would be closer to expansion. We're talking about creating and sending an equation to represent a value instead of sending the value itself. 1 + 32 = 33 is far larger than just sending 33. The difference is, if the receiver gets x +32 = 33, it can solve for x and thus rebuild the missing packet.
MIT, Caltech, Harvard, and other universities in Europe
I understand what they mean, but it's a silly way to write it. Maybe Slashdot should have someone who edits submissions.
How would you revise it without adding anything?
Best I can come up with is
MIT, Caltech, and Harvard, as well as some European universities
MIT, Caltech, Harvard, and some universities in Europe
MIT, Caltech, Harvard, and several universities in Europe
MIT, Caltech, Harvard, and a handful of universities in Europe
MIT, Caltech, Harvard, and a number of universities in Europe
Best Case, per your criteria of no additions:
MIT, Caltech, Harvard, and universities in Europe
No need for superfluous words, especially words that imply specific connection... like 'other.'
An enigma, wrapped in a riddle, shrouded in bacon and cheese
You don't know how to use question marks?
All very well and good, except that the encoded representation of the starting position may take up more space than the length of data you are wanting to send.
File under 'M' for 'Manic ranting'
Indeed, and I was tempted to post a comment about how researchers had rediscovered forward error correction. This technique is already used extensively absolutely everywhere, from optical media to DSL lines. What's so new and impressive about this "new" version of FEC?
Mod this ++good.
Double plus good ; where have I heard that before?
The article and the slashdot recap were dumbified to death. Trying to explain something in "layman terms" just makes it incomprehensible to both the layman and the expert. I work in communications department of an university and we do have practical research in coding methods for LTE. Though we can use industry and research community agreed terms, like Turbo Coding to describe the process of coding across the data.. Expert can just nod in acknowledgment and laymen can go use wikipedia.
So, dear Slashdot Editor and dear TFA-writer, stick your terms so deep in your Algebra that you can taste them.
Straw and hay are not the same thing, smart ass.
Imagine what it would do in a Boeing 777!!!
She does? But she's a teenager? She's totally going to watch Breaking Dawn part 2?
Then you must live in high foliage, a building with lead paint or some other signal bashing source. Even in my home at -115dB on my 4G device I can still get a sustained 8+Mb speeds on the hotspot connection.
"That's right...I said it."
because none of my linux/android gadgets running, (l)ubuntu 12.04, Nook Color, LG Optimus V, seem to speak on that bandwidth, and I would hate to fall back on the evil Win7 which seems to have no problem speaking 5Ghz.
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)
But there is a connection, MIT, Caltech, Harvard and the universities in Europe are all universities.
Removing the word "other" implies every university in Europe was involved.
So have a super-fast readonly ram module which contains 1gb(or however little would be necessary to get a valid set of permutations) of Pi, the starting position is simply a pointer address to that module.
"Here's an example of how it might work."
let us know when you can give an example of how it does work.
The Kruger Dunning explains most post on
But there is a connection, MIT, Caltech, Harvard and the universities in Europe are all universities. Removing the word "other" implies every university in Europe was involved.
No, including the word other implies that all the schools are in Europe.
"Sam and the other boys..." implies that Sam is a boy.
"Chevy, Ford, and other manufacturers in Japan" implies that Chevy and Ford are Japanese.
Same deal here.
An enigma, wrapped in a riddle, shrouded in bacon and cheese
I can understand the logic of adding extra information to a transmission so the end point receiver can extrapolate the complete packet due to data loss. My question is what if there is no or very little data loss won't the extra overhead work against you ?
Removing the word "other" implies every university in Europe was involved.
Forgot to address this one: No again.
"MIT, Caltech, and universities in Europe" does not imply all universities in Europe; it makes a distinction between MIT, Caltech, and European universities.
"MIT, Caltech, and all the universities in Europe" less implies it, and more just says it.
An enigma, wrapped in a riddle, shrouded in bacon and cheese
No it doesn't. "A team of researchers from MIT, Caltech, and universities in Europe" does not, even a little bit, imply that the "team of researchers" included researchers from every university in Europe. Whereas "A team of researchers from MIT, Caltech, and other universities in Europe" definitely states that MIT, Caltech, and the other universities from which the researchers on the team come are all in Europe, which is just a little bit wrong.
Search for the mentioned paper and you'll find the details.
cheers,
inno
I'm having trouble imagining how a bank account balance is going to require more than one decimal to express, regardless of how big it gets.
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.
Because, although slightly, it makes it bigger.
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)
You've invented data compression.
Are you sure? It sounds like he invented striping.
If you are not allowed to question your government then the government has answered your question.
Note the multiple deliveries in the butterfly network.
It doesn't increase capacity for unicast case. And TCP is unicast.
http://lkml.org/lkml/2005/8/20/95
I will NAK that as a joke....
Yay, another type of compression. I'm sure it's very easy to decompress. I shudder to think of the effort on the transmitter to describe packets algebraically. But I agree that in a high-loss environment, it's better than re-transmission.
Nope, Nowadays we have pi on tap
To paraphrase Churchill, "Gentlemen, we have run out of spectral bandwidth. Now we have to think."
They're comparing to standard TCP, and claiming gains on the discarded future data after a lost packet.
Standard TCP Options exist for this purpose, Selective ACK (RFC2018) is widely supported and allows a TCP stream to acknowledge receipt of data that is not immediately next in the sequence and thereby avoid retransmitting all that data.
TCP/NC seems like it's just error correction used for that purpose, though it additionally avoids the retransmit of the initially lost packet. I wonder how much it adds to the packet size.
The gain is from their TCP not reacting to packet drops. They essentially stole the entire spectrum from other users on their cell tower, using the error correction to hide any packets drops (which are a normal part of TCP operation!!!) from TCP.
In other words, terminate them for violation of TOS.
Less NACKs should give you more for your money though.
It's almost a win, win...
Cheers
I was always under the impression with wifi that retransmissions were done at the link level. When you do a ping packets are often delayed for 100s of ms. indicating retransmits. I was also under the impression that wifi was all algibra being developed by the csiro to effectivly turn almost noise into some sort of coherent siginal. surely this packet level correction can be done with more buffering at an in between layer. Alternatively a transparent proxy at the ap. You wouldn't want it at the server as it would be sending redundent data over links that don't need it.
I bet the throughput remains constant, or gets worse for large downloads. All that excess baggage in the packet to prevent resends improves network connection speed but the packets now contain data that may never be used.
As an adaptive protocol it makes more sense, i.e. if packet loss starts to rise then switch over to this mode.
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."
We assume that there is are [sic] random erasures within in the network.
802.11n aggregates frames. This means that (at least for throughput-limited flows) multiple packets will be transmitted at once, and they're likely to all be lost together. This won't help. In any case, it makes sense for inherently lossy links to do their own FEC -- the end-to-end principle is not a good way to maximize capacity. But hacking around TCP like this seems silly -- just fix the problem at the link layer.
You burn overall throughput for resiliency in the face of partial loss.
I want to delete my account but Slashdot doesn't allow it.
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.
But they're claiming greater than 10x increases in network throughput when the packet loss rates were only 2% to 5%. That doesn't add up. If the packet loss rates were in the single digits, only 2% to 5% of packets should have to be retransmitted. The retransmit request requires another packet the other way, so that the throughput should be 90% to 96% of packets originally transmitted. In other words, a 2% to 5% packet loss rate shouldn't slow down a network so dramatically and if that's the case, it shouldn't be POSSIBLE to increase the maximum throughput by a large factor.
The problem is that TCP's congestion control is very poorly designed for wireless communications. TCP is designed with the mindset that if everything is working well, there is no packet loss and any packet loss is a sign of congestion or other abnormal network patterns. For wireless links, this is simply untrue, so TCP is way over conservative in how many packets to send over wireless links. The article is about using error correction to fix that.
They've rediscovered forward error correction?
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.
But.... TCP/IP already has parity bits, so how is this different? this is still sending an extra something so the math can be done to figure out the missing data, sounds like the same thing we've been doing for ages...
my karma will be here long after I'm gone
What they seem to say they're doing forward error correction, but with giant coding blocks (superblocks) comprising multiple TCP packets. Presumably this is accomplished by swapping the bits around between the packets and then using a conventional block coding algorithm on smaller blocks within each packet. So a whole packet can be lost and the block-decoding algorithm will still decode the superblock correctly even with a missing packet (but not two missing packets).
It's a clever idea to work around the problem of RF interference in wireless networks (and I'm ashamed I didn't think of it first long ago.).
Conventional wireless network protocols use FEC in the link layer as well, but they lose packets due to collisions and interference from other devices that share spectrum with them. The only piece of it that I have trouble believing is that there can be a 10x or more increase in network throughput when the original packet drop rates were
This mechanism has been in place for years with the PAR encoding used in USENET messages. A little redundancy permits one or more messages to be dropped without losing the transmission.
A much simpler mechanism could get most of the claimed benefit:
In TCP, a packet erasure is assumed to have resulted from congestion. However, if we start receiving packets out of order when the window size is large, we could instead presume that a packet erasure may have occurred. In a sequence of packets sent when the window size is 20 packets, say packets 1-20, packet 5 is missing, instead of NAKing packet 5 and dropping 6-20, ACKing packets 6-20+ could provoke a response of retransmitting packet 5 and once 5 is ACKed, the transmitter can move on past packet 21 (by the time packet 5 is presumed lost, the transmitter would have transmitted even more packets) - thus only lost packets are retransmitted.
The size of the transmit window can be reduced modestly when this occurs, instead of resetting it to one - perhaps the appropriate adjustment is to where the transmit window would be after successfully ACKing 19 packets after a reset. This can be generalized for multiple lost packets within the transmit window, and no "algebra" on packets would be required, only a similar amount of memory at the receiver and transmitter to the coded TCP scheme. Coded TCP takes additional bandwidth because (1) more redundant packets are sent than are needed (2) the overhead of sending which packets are algebraically combined in each packet.
The proposal assumes a constant erasure rate with packet size - for many networks this is not true. Reducing the packet size often improves the erasure rate. I've seen this in practice, in a DSL line where reducing the MTU from 1500 to a few hundred made the line usable (until I could get it fixed).
The coded TCP scheme (or the above scheme) could be implemented in software using UDP packets. Why it needs new (and licensed!?!) hardware is beyond my understanding.
The way they describe it, it appears to be a simple point-to-point adaptive error correction which is like FEC.
A simple way to think about this is to think about a trivial code. Consider the situation where a transmitter batches up 10 TCP packets and the receiver receives 9/10. If the transmitter thinks that any of those 10 packets weren't received (say because of a timeout), it could just send the parity of all 10 packets. In a pure FEC system, it would always send that parity packet. In an adaptive system, it would only send that packet if it thought any 1 of 10 was lost. Of course you can replace parity with more sophisticated coding schemes that can more easily correct for more than 1 lost packet out of 10, and you can look at the packet loss statistics and speculatively send some of the "parity" packets in anticipation. Of course if all 10 packets are lost, you'd have to send all 10 new "parity" packets (can't avoid that).
Contrast this with normal TCP where if you lost the 1st and the 10'th packet, you'd probably have to wait until the transmitter sent all 10 packets (because the receiver can't communicate this back to the transmitter using standard TCP). With an adaptive FEC-like scheme, as soon as 2 packets were recieved, you could correct both the 1st and the 10th packet (not have to wait for packets 2-9 which you already got). I'm sure the scheme is a bit more sophisticated than this, but I'm pretty sure that's the general idea. They are probably are using a simple punctured convolution code instead of basic parity packets, but the idea is the same.
The Linear Network Coding idea is slightly different. It attempts to optimize the multi-cast scenario (not the point-to-point scenario). As I understand LNC, you take advantage of looking at broadcast packets and reconstructing your stream out of the ones you receive (kinda like how CDMA works over the shared air medium).
How about naming the European universities as well? That would solve the syntax problem while giving credit where it is due.
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.
Uhh, that sounds like an extremely convoluted reinvention of TCP SACK (RFC 2018) using some knockoff of Reed-Solomon instead of, y'know, "I got packets 1-4 and 6-10, please retransmit #5".
Range Voting: preference intensity matters
Here's one, imagine you driving to the supermarket to buy tampons, on the way back you spill, err coffee, yes boiling coffee on it and ruin them. In the old way, you'd have to double back and buy em again experiencing all the awkwardness all over. In the proposed new way, these tampons are resilient in such a way you can wring the coffee from em and they'd be good as new and you'll get to enjoy your coffee after all. No need to double back to the supermarket.
P.S: Logic gap on how spilled coffee can ruin tampons in plastic wrap noted and ignored for illustrative purposes.
Could this be adapted to make over the air HDTV signals less likly to freeze and such?
It's ironic that an article related to mathematics is written by someone who doesn't understand that an increase by a factor of 10 is a 900% increase, not a 1000% increase.
From the PDF you yourself linked: "Of course, no algorithm using a bounded amount of memory can generate a nonrepeating sequence such as the digits of p indefinitely, so we have to allow arbitrary-precision arithmetic, or some other manifestation of dynamic memory allocation."
It looks like RFC 1072 (TCP extensions for long-delay paths, 1996) and RFC 2018 (TCP selective Acknowlegement options, 1988) already does what I suggest. Does anyone know why it's not already widely adopted? If these RFCs were in place, the additional speed-up of coded TCP ought to be negligible.
Here's a quote from the coded TCP paper: "Other variants include those with selective acknowledgment schemes [21]. It may be interesting to compare the performance of the TCP variants with that of TCP/NC. However, we focus on traditional TCP here." The footnote [21] is to a paper that appears to be based on RFC 2018 with matching authors. I'd suggest that if they compared TCP/NC to RFC 2018, they'd see that their mechanism is way more complicated and has negligible advantages.
This only helps with decoding, and it still takes exponential time to decode an n-bit message.
So....I wonder if we knew "all" of pi, it could be used to represent all the data in the universe. The we'd just need the pointers to pick bits of data out of it. cool...
AB HOC POSSUM VIDERE DOMUM TUUM
Yes, it would.
Yes, it would.
But TCP already adjust its packet rate if it experiences too many losses, it could instead adaptively choose to include more redundancy if the current level of redundancy is not enough.
c++;
Well... Look at it as "parity bits on steroids". This method is sort of the same, but much more powerful.
The most important difference is that you can't repair damage with a simple parity/checksum, but with these algorithms you can actually use the extra data to fix most of the missing data.
c++;
Mods, this sounds kinda on-topic to me.
How is this different, or better than Luby codes.
http://en.wikipedia.org/wiki/Luby_transform_code
Dr. Luby founded a company, Digital Fountain, then that company was sold to Qualcomm.
Even better, they send you the instructions detailing how to put the piece back in the event that it is rattling around.
They know how TCP works and you don't.
Pi is a non-terminating irrational number. You can't know it "all"... so conceivably an infinitely long number to represent an unfathomably (and for all intents and purposes, "infinitely") deep volume of data...? Sure, why not? The answer still comes out to 42.
even with standard TCP you need only retransmit the missing packet (fast retransmit)
RFC 2018 is widely adopted -- it's supported in modern linux, Windows, and Mac OS (generally called "SACK" in the TCP tuning parameters) and on by default in all those for a number of years.
RFC 1072 was not implemented mostly because it was never proposed as a standard, just as a basis for further study. And as of RFC 6247 it is now a "historic" RFC.
It's an error-correction method that happens to have compression built-in.
Don't have many existing compression methods error-correction built-in?
Uh, no, under TCP in most implementations I've seen, you'd ack '4 until you received '5, then you'd ack '10. In a perfect world, this would mean only 11 packets were transmitted, unless the sender chose to re-send 6 to 10.
Spending some time with a packet sniffer on different networks can be illuminating :)
Because not every implementation of TCP works the same, that makes for an effective tool to exploit vulnerabilities also in some cases, where the packets as subsequently sent contain different data from the original - as some IDSs don't cope well with understanding which packet to keep.
GrpA
Enjoy science fiction? "Turing Evolved" - AI, Mecha, Androids and rail-gun battles. What more could you want?
Also known as "selective repeat" instead of "go back n".
"the technology has already been commercially licensed to several hardware makers."
Yeah I was thinking 'Thats kinda cool' until I read the last line... so not as open as TCP.
Duh - Adding FEC to TCP improves operation over wireless links. Call me unimpressed.
Excuse me, but please get off my Pennisetum Clandestinum, eh!
I'm genuinely surprised the TCP window algorithm would throw away packet 6-20 in this case. Kermit sliding windows wouldn't, they would NAK 5, ACK the rest, and then the sender would re-send 5 and pick back up again at 20 once it got the ACK to 5.
And that was described in detail in The Kermit Protocol back in 1986.
But this sounds precisely like standard error correction.
Since turbo codes were discovered in the 90ies, transmissions can now be sent at near their theoretical maximal speed.
So, what is different here? Some kind of RAID5 similar scheme? A data fountain? All well known not new technology.
It is not FEC in the sense of reed solomon. It is not linear network coding. This is not interleaving recovery information throughout the stream (FEC) or at either end of the data. It is applying a transformation on the data such that the result is a new stream of data that is transformed using algebra, The data as sent looks nothing like the original data. The new data stream is the result of the algebraic transformation and recovering the data is simply performing the algebra in reverse. Its very clever but its been done before. Typically digital fountain or fountain codes and Raptor Codes are applied to UDP streams but you can (and we have) been applying them to TCP flows as well. The result is two things, you can essentially eliminate retransmissions and in the case of large pipes you can eliminate bandwidth delay product.
I don't know about their solution because the article has so little detail but fountain codes and more recently raptor codes are extremely clever and useful.
I think you missed part of the point. Removing the need to send lost packets is only part of the issue. It looks like it also increases the data stored in each packet.
So, not only do you remove the 5% packet loss, but you also, for the same amount of data, remove 90% of the remaining packets.
Of course, like any compression algorithm, there is probably variability, so it is possible that there will be some variability, but the data in TFS, that 90% is probably an average, not a peak.
Self proclaimed typo king, and inventor of the bear destroying coffee table (patent not pending).
My browser timed-out the first time I loaded this page.
"Algebraic packet reconstruction fee: $.01/kb"
How about this:
MIT, the University of Porto in Portugal, Harvard University, Caltech, and Technical University of Munich.
That's straight from the article. Wouldn't it have been easier to just copy that than for some inexplicable reason dumb it down to "other universities in Europe", like it's only the American universities that matter?
Maybe it was strategic genius, as the main thing that got me clicking through to the article was wondering which European universities were involved in this research.
www.clarke.ca
This implies a disturbing amount of foresight about probable failure modes...
Overall throughput? I'm skeptical. I have yet to consistently get 3G speeds out of even a 4G phone.
Since you have no way of actually measuring your speed between your phone and the cell tower, that's a pretty bold claim to make. 4G is only the wireless portion of your connection, and in many cases the bottleneck is due to the tower not having enough backhaul capacity as opposed to a bandwidth crunch on the wireless portion.
That's *always* the case. It's the classic pigeon hole problem. In order to encode absolutely every possible string of bytes there must be some encodings which use at least that many bytes to do so. You see this readily with lossless image/audio compression algorithms. They make everything smaller in the average case (normal songs, spoken audio, landscape pics, family photos), but shove a randomly generated mess at them and they almost always produce a file larger than the original.
But I'm sure there's something about a car exploding and all traffic backs up for tens of miles along the wa
Well if you figure the packet is like a car, and the data is like a nice moist cake in that car, and using wireless is like having that car driven by a very fat lady.... much of the time when the car reaches the destination the fat lady has eaten the cake. So then she has to drive back and tell you the cake was "lost", so now you have to send another cake. This means that there are a lot of cars making a lot of extra trips, so traffic gets really congested.
Using this technology is like sending a teenage girl with bulimia as a driver- when she eats the cake and gets to the destination, she runs to the bathroom and pukes it back up where it can be put back together, and thus she doesn't have to make a second trip.
Think of it as bitmap vs vector graphic of a mustang.
FTFY. Analogy fail. He was looking for a car analogy.
So, not only do you remove the 5% packet loss, but you also, for the same amount of data, remove 90% of the remaining packets.
You're talking about two different ways to view the bandwidth at the same time, and are confusing the issue.
The amount of data, from the point of view of the transport, is still the same, and the bandwidth hasn't actually changed regardless of how many retransmits you eliminate or how much information you pack into each packet.
What you seem to be talking about is the effective bandwidth from the point of view of the application. If you need to send 100 megs of data, and can compress that into a single meg, then you can say that your 1 meg pipe is effectively acting as a 100 meg pipe.
Removing retransmits also does not actually increase the bandwidth from a physical layer point of view, but again from a higher layer point of view it does.
If it's encoded and knows what each packet is based upon the equation, why not just send the packet equation (if it's less data than the packets themselves) and have the other end run the numbers. Isn't this like compressing/zipping a file?
Well, all common desktop OS implementations of TCP support SACK (selective acknowledgments) so the big retransmits (6-20 in your example) are an issue only if the TCP/IP stack doesn't implement RFC 2018. Said RFC is 25 years old...
A successful API design takes a mixture of software design and pedagogy.
4G is only the wireless portion of your connection, and in many cases the bottleneck is due to the tower not having enough backhaul capacity as opposed to a bandwidth crunch on the wireless portion.
DING! DING! DING! We have a WINNER! Let's hear it for A.C.!
I once took an excursion to Reddit, and later HN. Unlimited up/down voting sucks when dealing with a hive-mind.
That's essentially what Error Corrective Coding is.
This has been being done for years. Originated at a company called Digital Fountain back in 2000. The sender side would generate and send equations that described the data at the bit level, then the receiver could solve for the data once it had enough equations. Companies like Disney and Warner used Digital Fountain to make movies in New Zealand and blast the dailies back over the Internet at line speed. Packet loss didn't matter because the next packet coming down the pipe had equations just as valuable to solving the content. Didn't matter which equations you received just as long as you had enough of them.
When reading this paper it is important to not loose sight of reality.
"This is due to the fact that TCP requires in-order reception."
ORLY...
"A single packet loss within a transmission window forces all subsequent packets in the window to be out of order. Thus, they are discarded by the TCP receiver."
More like selective amnesia (SACK).
Translation "our ECC shit only works on sequential frames"
If you assume the link layer is reliable (trivial to no packet loss in absence of congestion) and error free then the Internet works.. If you don't then it quickly turns to mush.
TCP is simply the wrong place for this crap. You need to do retransmission/correcting code at link layer if you have a noisy enough environment to warrant.
We don't see TCP checksums being relied upon to catch actual errors all the heavy lifting is done at link layer with fancy algorithms for a reason: It is closer to the real world/source of error.
If you have a radio then integrate predictive moderation of correcting codes with QOS/channel provisioning and current knowledge of the RF environment. This way higher layers do not see mixed signals with respect to congestion avoidance.
Their answer to this was simply to rely on the threshold of loss where the correction scheme was still able to fill in the gaps. This is naive and far from optimal.
Another benefit if you do these things at radio link there is less lag on detection of head end frame as other frames for unrelated sessions may be used to assist in rapid detection of missing frames.
Delaying or otherwise bundling frames into some sort of super cork is not the answer either as your just trading throughput for latency.
Finally I think it is important to consider possibility just maybe TCP/HTTP is the wrong solution for every single problem in the first place. Ultimatly attempting to mask these realities will not only never be optimal but can actually cause harm *IF* people are willing to trade congestion avoidance for gains they don't deserve to have in the first place.
To be clear I'm not saying there is no merit to error correction schemes... I just don't think they belong in IP.
From the summary, I was under the impression that there was de facto compression involved: There was less information transmitted that losslessly could be converted back to full packets. Perhaps I should have RTFA.
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
Straw and hay are not the same thing, smart ass.
No shit, Sherlock.
An enigma, wrapped in a riddle, shrouded in bacon and cheese
Back in the 90's I worked with error correction methods called "Golay" codes. It is not compression, in fact it sometimes Doubled the size of the packets. But, in the presents of occasional noise bursts it could have the same apperrent effect as compression.
The overall result is as though the noise level was less. But it still fails if the noise level is too high. The real use is where the noise is in bursts, instead of being constant, so that a bad packet is not all bad. In some types of noise it can have startling improvements. It is quite possible that this could be true of the WiFi signals.
Most network connections don't need error correction, because the noise is very low. Others can't use it because when they go out, they go really bad. But for some, it can be quite useful.
It sounds like the original designers of the WiFi systems were -way- too accustomed to wired connections! 8-)
Thank you for the many thoughtful comments. There are a couple of recurring points I would like to address.
The first is about the relation between this and traditional FECs. The codes here are not like conventional FECs, such as block codes (think Reed-Solomon and their ilk) or rateless codes (think Fountain Codes and the such). Such codes can be used over UDP readily. Using such codes over TCP is quite difficult.
Besides the usual difficulties, traditional codes have a structure that precludes their composability. There are several issues with this. One is that they cannot be re-encoded without being decoded. The ability to re-encode blindly is crucial to achieving capacity. For a theoretical treatment of this, I would refer you to:
http://202.114.89.42/resource/pdf/1131.pdf
The article is rather mathematical but the abstract provides the gist of the results "
We consider the use of random linear network coding in lossy packet networks. In particular, we consider the following simple strategy: nodes store the packets that they receive and, whenever they have a transmission opportunity, they send out coded packets formed from random linear combinations of stored packets. In such a strategy, intermediate nodes perform additional coding yet do not decode nor wait for a block of packets before sending out coded packets. Moreover, all coding and decoding operations have polynomial complexity.
We show that, provided packet headers can be used to carry an amount of side-information that grows arbitrarily large (but independently of payload size), random linear network coding achieves packet-level capacity for both single unicast and single multicast connections and for both wireline and wireless networks. "
The benefit of this composability, which we had first shown theoretically, is illustrated in TCP in the following paper that recently appeared in Proceedings of IEEE
http://dandelion-patch.mit.edu/people/medard/papers2011/Network%20CodingMeets%20TCP-%20Theory%20and%20Implementation.pdf
The theory of network coding promises significant benefits in network performance, especially in lossy networks and in multicast and multipath scenarios. To realize these benefits in practice, we need to understand how coding across packets interacts with the acknowledgment (ACK)-based flow control mechanism that forms a central part of today’s Internet protocols such as transmission control protocol (TCP). Current approaches such as rateless codes and batch-based coding are not compatible with TCP’s retransmission and sliding-window mechanisms. In this paper, we propose a new mechanism called TCP/NC that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the con- gestion window. At the heart of our scheme is a new interpretation of ACKs the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately (...) An important feature of our solution is that it allows intermediate nodes to perform re-encoding of packets, which is known to provide significant throughput gains in lossy networks and multicast scenarios.
The exciting news that prompted the piece in TR is that we now had an implementation "in the wild", in a simple Amazon proxy, which required significant engineering and works remarkably well.
The article refers to the issue of composability by pointing out that there would be advantage if it were built "directly into transmitters and routers, she says". The more places you build this, the better. Dave Talbot also provided a link to work that our group has done with researchers at Alcatel-Lucent
http://arxiv.org/pdf/1203.2841.pdf
which touches on this point to show the very important energy savings that could be obtained by implementing network coding in different parts of the network.
T
Well, then the coded TCP researchers excluded technology that's in modern TCP that makes their work redundant. In colloquial terms, they slayed a paper tiger. Is SACK used in current smartphones, or does a 2% or 5% erasure rate (the rates indicated in the benchmark figures of the paper) somehow prevent it from working? Omitting SACK from a cellphone's TCP implementation (or implementing it poorly) would be a cause of low transfer rates and wasted traffic in the airwaves.
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]
====================
on hard disks and server memories, we have ecc correction. A bad bit can be recalculated. If one uses a form of xor chain encoding, I believe that any block with a neighbor on each side can be used to construct a damaged or missing block. One has to appreciate XOR use
Leslie Satenstein Montreal Quebec Canada
What if E=mc^2 is really Goatse compressed?
Table-ized A.I.
they are not all using 10mbps / 1mbps all the time - get more throughput of users - on-downloadpage-off
It really depends where you are.
When I was on holiday 2 weeks ago before my just recently-dismissed-from-hospital (4 hours ago) second week holiday, I was getting insane speeds on my wireless dongle. But around here, my speeds are average-ish. Strange thing is this town is larger than the other, now considerably faster place. Both are seaside towns too.
The problem is more the data than the speed though. It is PAYG... so I accept the non-contract restrictions since I'm usually not doing intense internet stuff while away anyway. Contract bandwidth is better.