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.
Kazaa does that (Score:2, Informative)
The file sharing networks based on fasttrack technology do that. You download a movie or game from different users at the same time. Kazaa stitches it back together.
Re:Kazaa does that (Score:2)
Lots of programs do that (Score:2)
They called it "Segmented Downloads", ie the program would hit multiple ftp sites for the same file, doing a resume to get different parts at the same time. Heck, it would even locate the mirrors for you.
And yes, it caused a substantial improvement in download speed. It seems thus that the bottleneck is seldom in the last mile.
But this has little to do with the article, which as far as I can tell is mostly gibberish.
Re:Kazaa does that (Score:2)
getright (Score:4, Informative)
A bit insulting (Score:2)
With the GetRight solution, 100 people downloading from my FTP mirror = 100 TCP streams worth of bandwidth and CPU consumption. With the Digital Fountain solution, 100 people downloading from my mirror = 1 stream worth of bandwidth and CPU consumption.
Other Applications (Score:2, Informative)
GetRight uses multiple sites to download from and then pieces them back together.
http://www.getright.com [getright.com]
And cheap, too! (Score:5, Funny)
Oh, boy, I'm gonna stop by CompUSA on the way home and grab one of these.
Re:And cheap, too! (Score:2)
No kidding - It's kind of like a FAX machine: That'll be about $70,000 if you just want to send or receive, or about $150,000 if you want to send and receive, give or take $10k.
-"Zow"
Vectors... (Score:2)
I wonder what equations are used to convert raw unpredictable streams of data to formulas, and how come that the formulas used aren't bigger than the sent packets themselves? They mentioned XOR, but that just sounds silly, because XOR does nothing with data except do some reversible equation on them which does neither shrink or grow data.
Does anyone have more info? It does sound interesting though...
Re:Vectors... (Score:5, Informative)
Please note that I'm not saying this is a good scheme. It is just an example one, and one that doesn't detail the chunk polynomial conversion, which would be very important. There are several papers describing schemes where people have actually worked at making them tenable.
Modulo compression, if you want such a system to require only receiving k packets (although you send more than that), the sum of the size of the k packets must be at least the size of the original file (otherwise, you could use such a scheme to compress the file).
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 :-)
Re:Vectors... (Score:2)
Compression? (Score:3, Interesting)
In essence, is not this the same as file compression? The amount of information is the same
(for those, who remember, what Bit is). It is just, that the usual one character per byte is awfully wastefull. Which is why the various compressors are so effective.
Add a modern data transfer protocol and you may :-)
get some start up money
Re:Compression? (Score:4, Informative)
In essence, is not this the same as file compression? The amount of information is the same (for those, who remember, what Bit is).
It is more than merely compression. The received data is compressed, which saves transmission time, but this technology is already well known (and the company isn't claiming a compression rate better than entropy [data-compression.com], or anything else silly). The innovation here is the elimination of acknowledgement or ARQ packets. I'm speculating here, but it looks like they are encoding the data by transforming a file into a huge "codeword" -- when the codeword is transmitted, the receiver waits for enough packets to correctly decode the codeword, which results in the recovery of the file. There's no need for ARQ or TCP because transmitting extra codeword elements will automatically correct any errors incurred in transmission.
Flow Control (Score:3, Informative)
Re:Flow Control (Score:3, Interesting)
Quite correct. This protocol does not sound at all TCP friendly [yahoo.com]. It needs some way of dynamically responding to network conditions to be that way. Even something so simple as doing an initial bandwidth test, then rate limiting the UDP packets to 90% of that would be a big help, though for a large file that would still create a lot of congestion problems.
Does anybody know if IPV6 has any kind of congestion notification ICMP messages so stacks can know to throttle applications when the applications are blasting out data that's congesting the network?
Multicast (Score:4, Interesting)
Multicast is congestion friendly in that it can inherently seriously reduce bandwidth consumption, but it's obviously not congestion adaptive. I think the easiest (and probably best) way to introduce congestion control in a multicast is to have multiple streams at different rates, e.g., you have five simultaneous multicast webcasts of a Victoria Secret show, and folks can join the mulitcast group with the video quality that best suits the bandwidth and congestion on their pipes. This idea works very well for the Digital Fountain-style software distribution: rather than having a server serving the same stream at 10 different rates, you can have 10 servers streaming their own unsynchronized Tornado encodings, and clients can subscribe to however many their pipes can support. With 10 streams of data coming at you, you can reconstruct the original data ~10 times as fast.
Re:Flow Control (Score:5, Interesting)
The 'equations' are broken up into pieces such that if you recieve any N pieces, you can reconstruct the entire file. It's like how some key sharing schemes work. Like Publius for example. Any N 'shares' of the key can be used to reconstruct the entire key. In this case the 'key' is the whole document, and I'm betting they use a different sharing scheme than ones already used for cryptography.
Re:Flow Control (Score:2)
Think about simultaneous equations. If I have 2 unknowns I can solve it if I have two equations. Now imagine that I send you 4 equations, each with the two variables. You only need to receive 2 of the equations to be able to reconstruct the original two pieces of data.
The other neat thing about this is that you can multicast traffic - and each receiver can start listenin when it wants - so if a receiver starts listening halfway through you can still get the whole file!
Re:Flow Control (Score:2, Interesting)
Where TCP acks and controls flow on every single packet, which also must be received by the sender in order, a protocol like this can occasionally send back a report on what kind and how many packets it is receiving (fragmented, packet loss due to bandwith, packet loss due to congestion).
A little math... (Score:2)
X+Y=4
X+2Y=5
2X+4Y=10
2X+2Y=8
With 50% packet loss (as opposed to a 50% chance of loss per packet*) you only get two useful equations 2/3 of the time. Of course, these boxes are expensive and can do a lot more number crunching than just linear algebra. But of course, I wouldn't really have expected a good comparison from a company whose veep of marketing said "FedEx is a hell of a lot more reliable than FTP when you're running 20 Mbytes" Clearly all those game demo sites on the net need to get with the program.
*Computing the chance of loss per packet gives:
1/16 chance of getting all four, 100% success
3/16 chance of getting 3 of 4, 100% success
8/16 chance of getting 2 of 4, 66.666% success
3/16 chance of getting 1 of 4, 0% success
1/16 chance of getting none, 0% success
or 28/48 is a little more than 4/7, slightly worse odds than if you always got 2 of 4.
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:Flow Control (Score:2)
Droppage (Score:2)
Kinda like IFS? (Score:2, Interesting)
Neat idea. Patents: here [uspto.gov] and here [uspto.gov].
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:heh.. (Score:2)
I've heard this said about the diamond business and the postal service. Diamond couriers, who are carrying just diamonds, can be tracked and robbed easily. Once a package enters the postal stream its nearly impossible to steal that specific package.
I dunno if its really true or not, but it has a certain counterintuitive logic that makes it believable.
Re:heh.. (Score:4, Interesting)
Re:heh.. (Score:2)
Please tell me that data was encrypted first.
Re:heh.. (Score:3, Interesting)
Re:heh.. (Score:3, Informative)
Depending on how much noise goes undetected at your physical layers, you should expect a TCP session to pass thru incorrect data about 1 in 10^9 to 10^12 bytes passed (thats the metric I use) - and if this is unacceptable then your application layer should check and/or correct data itself, bearing in mind the end-to-end argument [reed.com] for system design.
T
DAP? (Score:2)
Uh...doesn't something like Download Accelerator Plus (yeah yeah, I know its a hive of spyware) already do that (downloads from multiple locations only to recombine the file later)?
Michael, did you even read it? (Score:5, Informative)
This technology (from the write-up anyway) uses some kind of proprietary technique to re-map the data into another domain and send the information required to reproduce it. It sounds kind of like sending a waveform as a series of Fourier coefficients rather than as actual data samples. By changing to a different domain, it is possible to send metadata from which the original information can be recreated.
I have no idea exactly how they would do it, but it doesn't sound completely impossible.
However, its nothing like Kazaa or GetRight.
PostScript for data (Score:2)
With real vector PS its easy, since you start out by creating vectors (eg, Adobe Illustrator). How you get from a non-vector "destination" to the metadata you really want to transmit sounds complicated.
Re:Michael, did you even read it? (Score:3, Informative)
Tornado codes (Score:5, Informative)
Swarmcast (Score:4, Informative)
Name of company and product (Score:4, Informative)
The company's name is OpenCola [opencola.com] and the name of the product was SwarmCast. The guy who did SwarmCast, Justin Chapewske, is now at a company he started named Onion Networks [onionnetworks.com]. OpenCola appears to have completely abandon its original Open Source approach to their software.
Apparently, Justin has taken the GPL portions of Swarmcast and is improving them at Onion Networks.
Re:OOPS, name of person slightly wrong (Score:3, Informative)
Oops, make that Justin Chapweske. That's what I get for typing out an odd name from memory. :-)
Re:Link to product (Score:3, Informative)
Oh, yes, here's a link to the SourceForge project for SwarmCast [sourceforge.net].
Debian (Score:2)
Debian does something similar with the Pseudo Image Kit [debian.org].
It gets all the parts of the install ISO cd image, from disparate sources, stitches them together, and then uses rsync to patch it to exactly make a duplicate of the original install image.
Very nifty.
Not a new concept (Score:2, Informative)
This is called compression. Everybody is doing it and it has been done before.
When you download a ZIP file, you are not downloading the content. You are downloading a mathematically transformed version of it. You then translate it back. Modems have been compressing and decrompressing on the fly since the late 1980s.
Maybe they have a better compression scheme? (Fractal based?) That would be news. Everything else is a distraction.
Re:Not a new concept (Score:4, Informative)
UDP drops packets. What they are saying is they can packetize things in such a way that as soon as you pick up any N packets, you get the file, no matter what. They are also implying that anything less than N packets leaves you gibberish. This is quite different from file compression. It may be related to fractal file compression, but I think it's probably more related to cryptographic key sharing schemes.
Re:Not a new concept (Score:2)
It won't work if they constantly resend the same packet over and over. They need it set up so that as soon as you get any N pcakets, you can reconstruct the file. This means that each packet needs to be different from all the other packets.
So if one side sends the other 6 packets before recieving the 'stop' request, and only 5 are needed to send the file, it doesn't matter which 5 of the 6 are recieved. No packets are sent from the reciever during the transfer, only at the beginning and end.
And, yes, it is a bandwidth hog, but for reasons that are rather different from the ones you imagine. It has no provision for congestion control, which means that it will keep blasting away with UDP packets at a congested router (keeping it congested) rather than backing off until the congestion ha cleared.
Re:Not a new concept (Score:2)
Maybe they have a better compression scheme? (Fractal based?) That would be news. Everything else is a distraction.
I remember back in the good old BBS days of a program called OWS which did "fractal compression"... In reality, it deleted the file and stored the sector information of the deleted blocks in the "compressed file" -- if you moved the .ows file off the disk, you'd get "decompression" errors. :-)
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
The RFC (Score:5, Informative)
The use of Forward Error Correction in Reliable Multicast
Enjoy.
Re:How it works (Score:2)
Several Forward Error Correction techniques are used in cellular networks, for example. If you have a GPRS or (soon) UMTS phone, it is already using some of the techniques that appear to be incredibly advanced if you read the EETimes article. But in fact, all these things are well known. I think that several DAB/DVB (Digital Audio/Video Broadcasting) protocols do the same as well.
Re:How it works (Score:2)
HH
Re:Not a new concept (Score:2)
Didn't have much chance to look over the algorithms, but we really should have compression used more frequently in network transport.
Basically (Score:2)
"The sending side transmits these symbols until the box on the receiving end confirms that it's collected enough symbols. "
So basically, it's not much more than UDP with a single reply telling the server to stop transmitting.
Not bad, but you better have some good timeouts worked into this thing. UDP by definition is a non-replying "if it gets dropped who cares?" protocol. If the receiver's connection were to go down, wouldn't the server just get flooding all the in-between routers with packets for awhile? That's not good for traffic congestion.
Just send numbered UDF Packats (Score:2, Interesting)
Somewhat unrelated --- Does anyone else miss Z-Modem. We need a zmodem like program for that works over telnet so we don't have to open a separate FTP session. In the BBS days, you just typed rz filename and it came to you.
my take (Score:5, Informative)
Judging from this:
The sending side transmits these symbols until the box on the receiving end confirms that it's collected enough symbols. The receiving box then performs an XOR operation on the symbols to derive the original data.
It appears to me that the transmitting side generates the symbols (parameters of the equations, I guess) and begins sending them to the receiving side as fast as it can. Apparently there are multiple solutions to the equations that will arrive at the same answer, so when the receiving end has received enough symbols to make it works it says, "stop sending already!" Apparently they're getting their speed because A) things don't have to go in any order (that's how the 'net is supposed to work, right?) and B) Alice and Bob don't have to keep up this conversation: Alice: Hey, Bob, can you send me X? Bob: Okay, are you ready? A: Yes, Go ahead? B: Okay, here it comes. A: I'm waiting. B: Here's the first packet." A: What? That packet didn't make it over. B: Okay, here it is again. A: Okay, I got that packet. B: Good. A: Okay, I'm ready for the second packet. B: Okay, here's the second packet.
Okay, I had too much fun with the Alice and Bob conversation there. Anyway, it looks like there scheme is compressing things in the form of their equations, and then just sending them in a burst until the receiver is happy.
Sounds like it might work, but it'll generate a ton of network traffic, I'd bet!
Re:my take (Score:3, Interesting)
It seems to me that article indeed speaks about network that has high latency but high bandwidth with some loss. How about simply compressing [redhat.com] the data and using bigger packets to transmit it? If you can use big enough window while sending data you can push all the data to the network in the beginning. Conversation comes to A) Here it comes A) Done [64 packets, 125MB] B) Okay, listening B) Resend 2,7 and 25 A) Done [3 packets, 6MB] B) OK. Note that A starts sending before getting reply from B. In fact, with fast long-distance connection it could be that A gets to the end before B getting "Here it comes".
I think if we want to speed up file transfer we need an API to tell OS that we're going to send lots of data so make it big packets or the opposite. Currently we just open socket connection to destination and start write()ing. OS has no way to guess whether or not we're going to write 100 or 10e8 bytes. We need a way to tell OS that the data we're sending isn't worth a dime before it's all done so make it big packets to minimize bandwidth wasted to TCP control traffic.
You can opt to waste bandwidth to reduce perceived latency and that's what I think is done here. A sends file twice and in a case some packets were lost the sent copy would be used to fill in missing parts. A has sent missing packet before B had known it's missing it. Yeah, A wasted half the bandwidth for the redundant data that got correctly to the destination at the first time but we aren't interested in that. The key here is to use UDP so that lost packets are really lost instead of automatically resend. This kind of setup increases overall throughput only if latency is the only problem in your network. Perhaps this is needed in the future because increasing bandwidth is easy - not necessarily cheap - but the light crawling inside fiber is so damn slow!
fastest (Score:4, Funny)
word.
Re:fastest (Score:2)
Someday when we all have extraordinarily fast computers, we'll simply be able to send somebody an MD5 sum and the computers will be able to "crack" it back into the original file.
Not familliar with hashes? You can't do it quite like that because an MD5 hash is the same for any number of datasets. Trying to un-do a hash is pretty idiotic at that level.
However, think about this scenario: Send the MD5, byte count and CRC64. Now rattle through all the possible combinations of "byte count" of data that generate the same MD5 and CRC64 and values as were sent. It's still not foolproof but you've reduced the dataset considerably. Of course, now you compare your new file to the GPG sig sent to ensure you got it right.
Perhaps as we approach quantum computing it will become more realistic to brute-force a many-hundred-megabyte file from a number of its hashes.
Entry level is $70k (Score:2)
The key is to build in redundancy without increasing the amount of data sent so much that you counteract the speed gains you get by using UDP.
-josh
FTP already provides for this (Score:2, Informative)
Re:FTP already provides for this (Score:2)
Article is wrong (Score:4, Interesting)
This is incorrect. TCP has a concept of sliding windows where once a number of packets has been received successfully, the receiver increases the number of packets that can be sent without an ack. This is an exponential number, so if it receives 2 packets successfully, it will then tell the sender that it will take 4 before an ack is needed. The only time you get a 1 for 1 ack ratio is if you miss a packet and the window slams shut.
Furthermore, UDP for data is highly unreliable, and I wouldn't trust it across WAN's. Frame Relay switches may drop packets if you exceed your CIR and begin bursting, so that whole transfer will never succeed. Therefore you actually waste bandwidth cause the whole transfer is doomed to fail, and the sender will never know it.
Also some routers have WRED configured in their queues, purposely dropping TCP packets to increase bandwidth on a global scale. This would damage the file transfer process as well if it was UDP based, as this system is.
Stick with the RFC's and the tried and true TCP transport system. This company will fail.
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:Article is wrong (Score:5, Interesting)
You may be right, they may fall on their noses. Or the win with their system might be large enough that we decide that we need to rework the way we do some things. Hard to say at this point.
I do take issue though with your 'Stick with the RFCs' comment. If we stick with what we know works, we will never evolve. If the folks at CERN had had this attitude, we'd still be using GOPHER (side note: my favorate interview question for testing people who claim to have a long time Net experience, 'Explain the difference between Archie and Veronicia'.)
GOPHER was the tried and true text retrieval system. Besides, UDP has an RFC, and is a perfectly legit method of moving data, provided you accept its limitations and ensure you correct for them. TCP has a lot of overhead that is not always required. If our network breaks because someone sends UDP, its we who need to reread our RFCs.
'Nuff Said.
Re:Article is wrong (Score:2)
In contrast, UDP never acknowledges (or disacknowledges) a packet.
Re:Article is wrong (Score:4, Interesting)
You're missing the point of UDP. UDP [faqs.org] is just a *tiny* layer on top of IP, which adds a little extra information (basically the port number) so that the OS can deliver a packet to the right application. UDP can not be compared with TCP - it doesn't provide reliability and flow control, and it has absolutely no notion of a stream of data. If desired, these can be provided in the application layer (see UDP, TFTP, NFS, etc. etc.)
TCP [ibiblio.org] is a reliable transport, but it's much, much more than that. First off, the fact that you're using TCP doesn't make the path between sender/receiver any more reliable. Your packets get dropped just the same as if they were UDP or any other protocol over IP. TCP provides reliability by retransmitting lost packets, but you knew that. It also provides flow control and congestion avoidance - this means detecting when the receiving end (and the router queues in between) are ready for more data, and throttling your transmission rate to match that capacity. It also means being "fair" to other streams sharing the same bottleneck(s). It does this by "backing off" the number of packets in flight, i.e. halving the congestion window, to reduce the data rate. These algorithms are a very active field of research - there's a *lot* more to TCP than meets the eye of a socket programmer.
When TCP loses a packet, that packet must be retransmitted. This is expensive because it means another RTT.
Anyhoo...
You can think of FEC for data transmission as being analogous to RAID 5 for storage. By adding one extra bit (the XOR of the rest of the word) you can lose any single bit and still know it's value. It's very simple. If the word is:
0 1 0 1
And I add an extra "parity" bit, where the parity bit is 1 is the number of ones in the rest of the word is odd, zero if it's even:
0 1 0 1 [0]
I can now lose any one bit (including of course the parity bit). Eg if I have only
0 1 X 1 [0]
Then I know the missing bit is a '0', because if it were '1' then the parity bit would be a zero.
Applying this to data transmission, you can see that by sending just one extra packet, you greatly reduce the chance of having to retransmit anything.
EG if I have to send you 10 packets over a link with 10% packet loss, there's a 65% chance that I'll have to retransmit one of those packets. (and a 10% chance that each retransmitted packet will have to be sent again, and so on).
However if I'm using FEC and I send one extra "parity" packet, then I only have to retransmit if TWO OR MORE packets are lost. The chances of losing TWO out of the eleven packets is only 30%, so you can see that for an overhead of 10%, I've reduced the number of retransmits by a factor of more than two! I hope those figures are right. I used this tool [vassar.edu] to calculate them. Of course there are a lot of knobs you can turn depending on how much overhead you can afford for the parity information, and what degree of packet loss you want to be able to tolerate.
Anyway, you can see that there are lots of possible improvements/alternatives to TCP - it's an old protocol and a lot of research has been done since RFC 793.
Udpcast (Score:2)
XOR = advanced algorithm (Score:2, Informative)
Conclusion: Only sales & marketing would try to sell a product that turns 20MB into 100MB, sends it via UDP, only in order to have the results XOR'd together.
Where do they get these people?
Re:XOR = advanced algorithm (Score:2)
Dropping all feedback is interesting in situations where:
- there is a very high latency, and feedback would arrive so late that it would seriously slow things down (i.e. satellite links)
- the return channel is costly (again, satellite links, with a terrestial (dial-in) return channel). If you can do away with the return channel, you win the cost of dialing in, which is interesting if you are on a metered telco, as is common in Europe.
As far as only a certain number of packets being required to be received on the other end, that is either completely false, or the overhead is astronomical. More likely it is just plain wrong, or this product is complete vaporware to begin with.This is feasible in a way to make the number of extra packets tuneable to the expected loss.
The algorithm is indeed based XOR, but that's not the only component though. The idea is to define a field on the set of all byte (or short, or word...) values. You use XOR as the addition, and Galois multiplication as the multiplication.
Then you treat your data blocks as vectors, of which you can do linear combinations in the Galois field.
If you have n data blocks to transmit, and want to add k redundant blocks, you first arrange your n data blocks in an n-element vector. Then you multiply that vector with an n times n+k Vandermonde matrix to optain a new vector of n+k elements. Those n+k elements are the blocks which will be effectively transmitted
A Vandermonde matrix is a matrix having the following form:
1 x_1^1 x_1^2 x_1^3 ... ... ... ...
.......
1 x_2^1 x_2^2 x_2^3
1 x_3^1 x_3^2 x_3^3
1 x_4^1 x_4^2 x_4^3
A square Vandermonde matrix has the interesting property of being inversible. Moreover, a subset of rows of a Vandermonde matrix is still a Vandermonde matrix. Loosing packets is equivalent to dropping rows (as each one of the n+k transmitted packets is obtained by multiplying one row of the matrix by the vector of the original n packets).
The receiver just calculates the remaining Vandermonde matrix (by striking out the rows that correspond to the dropped packets, plus some more if less than k were dropped), and inverts the remaining matrix. By multiplying this inverse with the vector of received blocks, the receiver can obtain the original vector of n data packets.
The nice thing about this is that k is freely tuneable (as long as the field is big enough: but if you define your field over 4 byte values, that should not be a problem). So, you just take a value for k that matches the expected loss rate plus some comfortable safety margin, and you're set. Considering that, turning 20MB into 100MB will only be necessary if you expect to loose 4 packets out of 5...
Of course, all this doesn't resolve the issue of flow control, so the sender needs to be tuned manually such as not to emit faster than the physical link can handle.
Tornado Codes (Score:5, Informative)
I don't have the paper in a computer format, but the number is TR-98-021 and John and Michael were both at Berkeley at the time (1998), so it should be fairly easy to find if someone is interested. Doubtlessly, a number of other reports on the subject should also exist that deals with the same problem but with different solutions.
Might Be more Related than you think (Score:3, Informative)
Those "Tornado Codes" you mentioned are coauthored by one of the executives of this company (Luby is CTO).
What's going on here? (Score:2)
Now i don't see, how a transformation of content helps here, instead of adding the information where in the file the packet goes (a kind of serial number), now you have to label, where in the equation it should go (a kind of coefficient index), so the receiving end knows, whether it has all information, and which information is still missing, and must be requested again.
Re:What's going on here? (Score:3, Informative)
from P2P to P2net? (Score:2)
More commentary (Score:2)
Think Reliable Multicast + XOR Recovery (Score:2)
You create your data in records and groups. Each group contains a longitudenal XOR of the other records within the block. This comes from tape backups that were proof against bad-spots and was later used in RAID.
You then sequence and shoot your data in records across the network. If one record is dropped, it can be recreated through the XOR redundancy record. If two records are dropped, you need a rerequest mechanism. This can be either on UDP or via a separate TCP link.
If you want an example of prior art, go to the trading room of a bank. How do you think all those prices are delivered to every workstation?
michael didn't read the article carefully, I guess (Score:2)
michael, this is not what the product does. From the article:
It appears as though the singal is broken down into equations, that when combined produce the original data. These equations are all sent from the same server to the destination client. The speed increase then comes from the fact that the size of the equations is less than the size of the data.
The article does not mention that the equations come from multiple servers, which is a very big difference! IMO, this technology is much more newsworthy than yet another multi-server downloading tool like Kazaa.
read then speak, not distributed, not compression (Score:2, Informative)
compression takes data, applies an algorythm to it to generate new data that is representation of the whole.
contrary to that, this transforms the data to an algorythm that simulates the whole.
it is a minor point of order, but one worth thinking about because it is theoretically different.
this is also not distributed, it is point to point, I don't know where the submitter got the distributed model from, I suspect he pulled it out the air, but this is very clearly not that. It requires a machine at each end of the point2point.
however, logically, all data that is not random, can be represented by equations that are smaller than the data. However, the real load exists in the generation of the equations from the data, and not the reconstruction of the data itself, so for me this seems to be quite a possible project, though i suppose it will take quite a bit optimization.
one other thing, the article does not say that it uses a standardized technique, and it would be interesting if they did not use standard vector analysis or the like. If they used vectors, then this could just reduce to a system of file conversion from one standard to another. I think it would be far more interesting to be what it says it is supposed to be a file conversion to mathematical simulation of the file.
FTP Unreliable? (Score:2)
Maybe I'm misunderstanding the quote, but I semi-regularly download 600+ MB iso images and other multiple-hundred-meg files over ftp links at work, and I've never had problems. It's probably just me, but that really sounds like a load of bull, designed to whip up interest in an otherwise lack-lustre product (given it's high price).
Cheers,
Tim
More details of their method (Score:2, Informative)
Forward Error Correction, MojoNation (Score:2, Informative)
Luby Transform Codes (Score:5, Interesting)
security (Score:2, Offtopic)
Swarmcast (Score:5, Informative)
I am the creator of Swarmcast, and we at Onion Networks (http://onionnetworks.com/ [onionnetworks.com]) already have a product that can provide file transfers just as fast as Digital Fountain, but ours is 3-5.5% more efficient and much much cheaper.
On the open source front, we are working on the next generation of the Swarmcast technology which will combine parallel downloads over HTTP, Multicast IP, and UDP (for tunnelling through NAT). We have started work defining a standard for this system called the "Content-Addressable Web" [onionnetworks.com] and hope to see it implemented in everything from Apache to Mozilla.
Please mod this up, people shouldn't be paying $150k for these types of technologies.
FEC Library (Score:5, Informative)
--
Justin Chapweske, Onion Networks [onionnetworks.com]
Re:Swarmcast (Score:2)
You haven't looked at the outrageous prices of Cisco equipment lately, have you?
Assuming these boxes are for accelerating multicast applications and preserving WAN bandwidth, then US$70,000 per box sounds competitive with Cisco. Put a large one of these boxes at the headend of a multicast, and one box for each LAN where there are a number of receiving clients, and there could be considerable savings in WAN usage.
/. readers don't realize how expensive a WAN link costs, and how those costs jump in large multiples when a PHB demands more bandwidth for his pet project. Especially outside of the US where international WAN links cost upwards of $10,000/month for 2Mbit/second, and to add another 2Mbit/sec will cost another $10,000 plus a long wait for turn-up. If the PHboss absolutely has to roll out a multicast application immediately, I'd throw a handful of these boxes on the network, and not bother with buying more bandwidth for a while.
the AC
Raid 5 Errors...Disks (Score:3, Insightful)
It's called Forward Error Correction (Score:2, Informative)
Line reliability in the "normal" sense is classified by bit error rates. Here, the analogous rating would be packet dropped per second. So, it seems like a straightforward application of FEC. It is useful for the reasons that they state. TCP transmissions look like this:
Client: Request Data Packet #00001
Server: Transmit Date Packet #00001 then wait for Client to say OK or Retransmit.
Client: Request Data Packet #00002
Server: Transmit Date Packet #00002 then wait for Client to say OK or Retransmit.
....
Client: Request Data Packet #20343
Server: Transmit Date Packet #20343 then wait for Client to say OK or Retransmit.
DONE
The FEC/UDP form would look like this:
Client: Request Data FILE
Server: Transmit FEC Data Packet #00001
Server: Transmit FEC Data Packet #00002
...
Server: Transmit FEC Data Packet #20343
Client: OK...I got it. Stop Transmitting.
DONE
There is no per-packet dialog between server and client. This removes network latency from the transfer equation. Note that FEC over UDP does require redundant information to be transmitted, so there is no free lunch here, but it is certainly likely to be faster than any TCP/IP implementation.
All about Digital Fountain (Score:5, Informative)
Digital Fountain's core technology is called "meta-content (tm)". The meta-content engine produces packets based on the original content, such that if the receiver receives enough packets (just slightly more than the size of the original content), the original content can be recreated. The neat part is that it doesn't matter which meta-content packets you get. If you need to receive 10 packets, you can get 5, miss 5, get another 5, and it works. Or you can get 1, miss 10, get 9, and it works as well. As long as you receive some 10 packets from the "fountain," you can recreate the original content.
Why is this cool? Several reasons. Digital Fountain claims that TCP connections with RTT of 200ms and 2% packet loss have a bandwidth limitation of 300kbps, no matter how fast the actual transport channel is. So you just go to town to full bandwidth with UDP to use up the entire channel, and use Digital Fountain technology so it doesn't matter which 2% of packets get lost, just as long as you transmit enough packets to make up for the packet loss.
OK, why else is this cool? Imagine a Digital Fountain continuously transmitting meta-data on a multicast address. If you want to receive a file, just listen to the multicast address. It doesn't matter when you start listening, just as long as you listen for enough packets to recreate the original file. Multicast file distribution.
Interestingly enough, Digital Fountain has also pioneered multicast on-demand streaming, but the real secret sauce there is something besides meta-content, but meta-content makes it easier.
As some people have mentioned, you can use UDP with FEC to achieve some error correction. But meta-content can handle long burst errors, whereas FEC is only appropriate for short, random errors. 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.
I should mention, DF has something called "Fair Layered Increase Decrease Protocol," or FLID, to keep their UDP burst from blowing away other TCP traffic on the network.
For more information on the basic Digital Fountain technology, see: A Digital Fountain Approach to Reliable Distribution of Bulk Data [berkeley.edu].
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:2, Informative)
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.
NOT NEWS. (Score:5, Informative)
The concept of "sending equations" instead of data is extremely well-known. It's called Forward Error Correction (FEC). FEC is a very simple idea: take the source data and encode it with parity data so that you can reconstruct the original message from any N chunks of it. One form of FEC that even your stereo components might already do is Reed-Solomon encoding; you can look this up in CS textbooks. If you Google for "Luigi Rizzo Vandermonde", you'll find a fast, free C library for FEC that you can use in your own applications.
Digital Fountain was started by Mike Luby, who is something of a luminary in information theory/cryptography. The kernel of their company's IP is "tornado codes", an FEC codec that is leaner and faster than competing codecs. The basis for their protocols, last time I checked, is FLID/DL and RLC. These protocols set up multiple channels (or "sources" if you must), each transmitting random chunks of FEC-encoded files.
The drawbacks to FEC are that it can take a long time to encode data for transfer, which makes FEC hard for some real-time applications like mail, and that the amount of data transferred is going to be some percentage greater than the original file (owing to parity information). But the drawback to FEC file transfers protocols is much more significant: they aren't TCP-friendly.
The whole Internet depends on protocols that have built-in congestion responses that mimic those of TCP. Protocols that don't either starve TCP flows, or are starved by them. Protocols with no real congestion response at all rapidly destabilize Internet links by consuming all available resources. Digital Fountain originally targeted multicast media transfer. Congestion avoidance in multicast schemes is still an open research question. Does this protocol really scale?
More to the point, what's the benefit? There's obvious payoff for FEC in multicast, where backtraffic from ACKs and NAKs quickly overwhelms the group and kills performance. But in unicast-world, where we will all be living for the next decade, TCP and TCP-friendly forward-reliable protocols like SCTP already provide good performance.
Slow news week at EETimes I guess. Or Digital Fountain just hired a PR firm.
Re:NOT NEWS. (Score:2, Informative)
Yes, their protocol uses TCP-friendly congestion control - read about it in their SIGCOMM paper [acm.org].
I was a skeptic... (Score:5, Informative)
I was a Skeptic, but I'm now that I've read the Digital Fountain white papers: Meta-Content Technology White Paper [digitalfountain.com] and TCP White Paper [digitalfountain.com], I'm a True Believer.
I don't pretend to understand all the details, but the technology is based on the Luby transform [google.com] which was invented by the company's founder. Essentially the content is broken into segments which are then randomly XORed to produce the metacontent. This provides redundancy since each segment of metacontent contains information from several of the original segments. Also the metacontent segments do not require sequential transmission.
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.
Re:A good idea, but old (Score:3, Informative)
BTW, it helps to read the article before posting "insightful" comments.
Re:Compression (Score:2)
All the data doesnt need to come from the same server. I suppose it is like load balancing.
If you have 20kbps to mirror A, and 80kbps to mirror B. Server A and B start spamming you with packets of whatever you are downloading. Then 20% of the total packets you recieve are from A, and 80% of the total are from B. Given all the partial packets you got, you can now reconstruct the porn DivX. This would be faster then getting 100% of the packets from B which would take 25% longer.
Re:Uhh... my shit detector just went off (Score:2)
For example, lets look at a situation where I need to tranfer data from the east coast to the west coast and my round trip time is 70 ms. If I have a 32 Mbps link, I can send 64K in about 2 ms. So I have to wait 68 ms until I send another 64K. This gives an effective throughput of less than 1 Mbps. Throw in the slightest amount of congestion and things go even further downhill real fast.
Thank you for that detailled explanation. It seems that my shit detector is a little trigger-happy. :-) Your comment on the "magic algorithm" is spot-on. I could think of a way to pre-determine an algorithm which recodes 64k chunks of data by precomputing all possible 64k datastreams and then simply selecting the datastream which represents that 64k (or whatever size). Anyway the other comments in this article have already attacked the idea on its use of UDP and its lack of net-friendliness. I predict a number of angry customers who paid $300k for a pair of these and whos data is getting dropped/throttled like crazy by their ISPs or the ISPs in the middle. :-)
Re:Simple working example (Score:2)
Re:Simple working example (Score:2)
For another, a large portion of transmission errors are not localized to a single packet, thus providing for a single packet to be in error (parity scheme) is essentially useless, as you'd probably need to send a negative acknowledgement anyway.