UDP + Math = Fast File Transfers 449
Wolfger writes: "A new file transfer protocol talked about in EE Times gets data from one place to another without actually transmitting the data..." Well, the information is transmitted, just not in its original form. I think there are a couple of other places working on similar ideas - wasn't there a company using this for a fast file download application? User would go to download a game demo or something, receive pieces from several different places, and knit them together? Wish I could recall the company's name.
heh.. (Score:5, Insightful)
> than transmitted electronically. "FedEx is a
> hell of a lot more reliable than FTP when
> you're running 20 Mbytes,"
Having worked in the industry they mention, I'd hazard that they don't use ftp more because of the illusion of security than anything else. People in the EDA world (which is where I worked, and has a close relationship with chip manufacturers) are immensely paranoid about people getting ahold of their chip designs, because if someone steals that.. you not only lose your next chip, you enable someone else to make it for you.
These people just don't trust firewalls and ftp yet, but they do trust putting a tape in an envelope and snail mailing it. At the very least it makes someone liable if the letter gets stolen, which you can't do with electronic transfers..
At any rate, ftp is plenty reliable for transfering 20mb files.. I do it every time a new game demo comes out.
Re:Vectors... (Score:3, Insightful)
Exactly. This is also the point where a equasion to represent the data is going to end up bigger than the data its trying to send. But it depends on the algorythm used too. If the data may be sent out of order, one could try block-sorting and then compressing (like bzip2 does), but since this is UDP, out of order packets will be dropped or either not delt with (I think).
DISCLAIMER: I am not a protocol god, nor am I trying to be. Just spouting my views :-)
Yea, Right. (Score:1, Insightful)
Who does this guy think he is kidding?? We regulary FTP AutoCad files of 100 Megs and ISO images of 500 Megs with no issues what so ever.
Sure it might take an hour or or so to complete but, that beats the hell out of FedEx and it's a lot cheaper too. This guy's been smoking a few too many of his own marketing brochures.
Technique: FEC (Forward Error Correction) (Score:1, Insightful)
How it works (Score:5, Insightful)
The technique used by Digital Fountain is called Forward Error Correction. It allows a message M with m parts to be encoded into n parts, where n > m. The interesting thing about this is that any m of the n parts will allow the original message M to be reconstructed.
This means that if a part of the message is missed, the receiver doesn't have to request a resend
Re:FTP Unreliable? (Score:1, Insightful)
It should most likely read something like "20Gb"
Raid 5 Errors...Disks (Score:3, Insightful)
Re:A little math... (Score:4, Insightful)
X+Y=4
X+2Y=5
X+3Y=6
X+4Y=7
then you may find X=3, Y=1 from *any* pair of equations you recieve.
Re:Article is wrong (Score:2, Insightful)
I would trust UDP with anything I would trust TCP with as long as the application does the error checking on the data, which is exactly what they are saying their product does. TCP is really high overhead compared to UDP, and not always necessary. One of the reasons for TCP was so that programers wouldn't have to deal with as much, but if you can make something that handles it more efficiently then you only have to send a retransmit request whenever there is lost data, and not after every window.
Maybe it's my tendacy to fight for the underdog but I feel UDP has gotten the shaft. It's a great way to slam traffic around, and as secure as your application is written to make it.
Nice little doc over TCP and sliding windows for anyone that might want one. [cisco.com]
Re:All about Digital Fountain (Score:3, Insightful)
First, 2% packet loss is terrible, even on a WAN.
Second, 200ms is terrible latency, unless you're crossing an ocean.
Neglecting packet loss (which ought to be neglectable, though admittedly isn't at 2%), your maximum TCP throughput will be (TCP Window Size)/(2 * Latency), or the bandwidth, whichever is more. That comes to about 1280kbps on that 200ms link if you aren't using TCP window scaling options, and much higher if you do.
Re:All about Digital Fountain (Score:3, Insightful)
This depends on the parameters of your FEC algorithm. Most FEC algorithm do indeed divide the data to be transmitted into "slices" of n blocks, to which they add k blocks. If more than k blocks are lost per slice, you're SOL, even if enough extra blocks are available in other slices. However, there is a way around that: just tune your FEC algorithm so as to make n large enough that all of your file fits into one slice.
The downside of this is that the larger the slice is, the more computationnally intensive it is. If the only thing you're concerned about are burst errors, just interleave your slices.
You can literally unplug the ethernet, wait a while, and plug it back in, and you're still good to go with Digital Fountain, as long as you listen long enough.
This is possible with run-of-the-mill FEC algorithms as well, as long as you put your entire file into a single giant slice.
If there's redundancy, there has to be overhead (Score:3, Insightful)
I'd guess they have to send about 2x as much data as the original for this to work. Maybe they're applying a compressor (like gzip) up front, and taking credit for that.
As others have pointed out, there are lots of other schemes in this class. Bear in mind that this is a protocol for broadcast and multicast, not general file transfer.
In a word, it's like mp3 (Score:1, Insightful)
You convert a digital document into a mathematical function which when applied retrieves the elements one by one composing the document.
Mp3 do the same but in addition, they remove what you don't hear to make the mathematical function easier to produce (actually it is discreet values for a Fourier equation that is calculated, but the idea is the same).
Now, as to how they can charge so much, I have no clue. I am sure a skilled university student could do the same... unless there is a new 'patent protected' sticker on the package.
Artaxerxes
FEC very common in wireless (Score:1, Insightful)
FEC is widely used in transmission media like cell phones and cable modems. These channels regularly introduce all kinds of distortion and interference. It's the use of FEC that allows you to still hear conversations despite the interference.
There are basically two kinds of FEC -- block codes and convolutional codes. Block codes are just that. They take in a block of bits (say N) and spit out (N+K) bits. The K is your added redundancy more or less. Convolutional codes operate like finite state machines. They continually take in a stream of bits and spit out more bits at a higher rate. Tornado codes, which these guys use, are (I believe) a type of block code. Most digital cell phones use a convolutional code. In fact, the founder of Qualcomm, Andrew Viterbi, is the "inventor" of the mechanism by which convolutional codes are decoded.
Hope this helps.