?

Log in

No account? Create an account

Mon, Jun. 20th, 2005, 08:51 am
Avalanche

A bunch of people have been pestering me about Avalanche recently, so I'll comment on it.

First of all, I'd like to clarify that Avalanche is vaporware. It isn't a product which you can use or test with, it's a bunch of proposed algorithms. There isn't even a fleshed out network protocol. The 'experiments' they've done are simulations.

It's a bad idea to give much weight to simulations, especially of something so hairy as real-world internet behavior. I spent most of my talk at stanford explaining why it's difficult to benchmark, much less simulate, BitTorrent in a way which is useful. But we can look at their simulation to see if it might at least be ballpark.

Let's see, here's their simulation of 'tit-for-tat':

To simulate a tit-for-tat scenario, the simulator keeps track of the difference between uploaded blocks minus downloaded blocks from a user S (source) to a user D (destination). If the difference is larger than the pre-configured value (typically 2 when we study tit-for-tat), then the source S will not send any block to D even if there is spare upload capacity at S and spare download capacity at D.


I can't fathom how they came up with this. Researching either the source code or the documentation on the BitTorrent web site would have shown that the real choking algorithms work nothing like this. Either they just heard 'tit-for-tat' and just made this up, or they for some odd reason dredged up BitTorrent 1.0 and read the source of that. You see, BitTorrent work this way when it was nowhere near functional yet, and the first test among multiple peers (6 if my memory serves) showed that it sucks. It was promptly rewritten, way back in late 2001. This gaffe alone makes their simulation completely worthless, but it isn't the only one:

Whenever a user joins the system it picks four nodes at random and makes them its neighbors (provided that they have not exceeded the maximum number of neighbors, which is set to six in most of our experiments). The simulator supports dynamic user populations with nodes joining and leaving the system, and topology reconfigurations. In fact, at the end of each round, if a node determines that the utilization of its download capacity in the most recent rounds drops below a certain threshold (10% in most of our experiments), then it tries to discover and connect to new neighbors. Similarly, if the user has exceeded its maximum number of neighbors, then it will drop some of the old neighbors at random.


So in their simulations peers have 4-6 neighbors with a strong preference for 4. BitTorrent in the real world typically uses 30-50. Since BitTorrent depends entirely on its neighbors for information related to piece selection, this limitation has ratcheted the amount of useful information BitTorrent gets to the absolute minimum possible without making the system not work at all.

They also don't simulate varying transfer rate abilities, transfer rate abilities varying over time, or endgame mode.

In other words, intentionally or not, the simulation is completely rigged against BitTorrent.

The central idea here is basically 'Let's apply error correcting codes to BitTorrent'. This isn't a new idea, everybody comes up with it. In fact I saw fit to mention that it's a dubious idea before. (Some people will point out that 'error correcting codes' isn't the right term for the latest and greatest of this sort of technology, to which I say 'whatever'.) The main reason that this is a popular idea is that recent work in error correcting techology is very cool. While it is very cool, and very applicable to sending information across lossy channels, the case for using it in BitTorrent is unconvincing.

What error correction can in principle help with is that it the chances that any given peer has data which is of interest to another peer. In practice this isn't really a problem, because rarest first does a very good job of piece distribution, but error correction can in principle do as well as is theoretically possible, and rarest first is in fact less than perfect in practice.

One thing badly missing from this paper is back-of-the-envelope calculations about all of the work necessary to implement error correction. Potential problems are on the wire overhead, CPU usage, memory usage, and disk access time. Particularly worrisome for their proposed scheme is disk access. If the size of the file being transferred is greater than the size of memory, their entire system could easily get bogged down doing disk seeks and reads, since it needs to do constant recombinations of the entire file to build the pieces to be sent over the wire. The lack of any concrete numbers at all shows the typical academic hand-wavy 'our asymptotic is good, we don't need to worry about reality' approach. Good asymptotics are one thing, but constant multipliers can be killer, and it's necessary to work out constant multipliers for all pontentially problematic constants, not just the easy ones like CPU.

The really big unfixable problem with error correction is that peers can't verify data with a secure hash before they pass it on to other peers. As a result, it's quite straightforward for a malicious peer to poison an entire swarm just by uploading a little bit of data. The Avalanche paper conveniently doesn't mention that problem.

As you've probably figured out by now, I think that paper is complete garbage. Unfortunately it's actually one of the better academic papers on BitTorrent, because it makes some attempt, however feeble, to do an apples to apples comparison. I'd comment on academic papers more, but generally they're so bad that evaluating them does little more than go over epistemological problems with their methodology, and is honestly a waste of time.

If you're interested in doing more fleshed out research on error correction in BitTorrent, I suggest starting with a much less heavyweight approach. Having peers transfer the xor of exactly two pieces could potentially get most of the benefits of full-blown network coding.

Mon, Jun. 20th, 2005 07:47 pm (UTC)
(Anonymous): The authentication problem _is_ addressed.

You state:
The really big unfixable problem with error correction is that peers can't verify data with a secure hash before they pass it on to other peers. As a result, it's quite straightforward for a malicious peer to poison an entire swarm just by uploading a little bit of data. The Avalanche paper conveniently doesn't mention that problem.

You really should learn to read papers to the end Bram. They do address the problem. Directly. The last paragraph of the paper addresses the problems of authenticating blocks in a rateless coding system. It references the public literature on the subject. It describes the computation cost of performing the check using the extant disclosed methods. It states that the authors have devised a scheme which does not have this computational cost that they are not disclosing at the moment.


Mon, Jun. 20th, 2005 08:28 pm (UTC)
uf_arachnid: Re: The authentication problem _is_ addressed.

This paper describes a homomorphic hash algorithm that can be used to verify individual encoded blocks. Unfortunately, it's extremely slow to compute and verify, the resultant hashes are generally large, and it expands encoded blocks by 1 bit per sub-block (not much overhead, but generally in the "what a pain" category).


If the authors of this paper have come up with something better, I wish they'd hurry up and show us!

Tue, Jun. 21st, 2005 01:05 am (UTC)
ocker3: Error correction paragraph correction

What error correction can in principle help with is that it the chances that any given peer has data which is of interest to another peer.

Surely saying "What error correction can in principle help with is that it increases the chance . . ." makes more sense?

And the rest of the paragraph makes it unclear with method you prefer, error correction or rarest first (perhaps neither?).

Tue, Jun. 21st, 2005 04:30 pm (UTC)
(Anonymous): Re: Error correction paragraph correction

I think it's obviously rarest first.

Tue, Jun. 21st, 2005 01:59 am (UTC)
(Anonymous): Angry Geek?

Bram,

There is too much vernacular, execration and self-aggrandisement in your response to consider it seriously from an academic perspective. Rework.

Tue, Jun. 21st, 2005 02:25 am (UTC)
(Anonymous): Re: Angry Geek?

Good thing an academic perspective doesn't have much application to reality =)
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand
Re: Angry Geek? - (Anonymous) - Expand

Tue, Jun. 21st, 2005 02:15 am (UTC)
(Anonymous): ipv6 checksum

hi i'm watching your standford talk - it's interesting - first thing - there must be a reasonable way to simulate torrent setups - if scientists can model airflow, nuclear reactions, QCD lattice etc..

also you expressed concern about the checksum in ipv4 being only 4 bytes and hoped that ipv6 has more - i just did a cursory check - it seems to have less - 2 bytes - do they know something more about error correction here? I don't know, but probably they do??

http://www.protocols.com/pbook/tcpip2.htm

regards

Tue, Jun. 21st, 2005 08:06 pm (UTC)
(Anonymous): Re: ipv6 checksum

do they know something more about error correction here?

Perhaps they are merely doing error detection, 16-bits was always sufficient for sectors on a floppy disc, where the length of data over which the CRC is calculated is relatively short. Doing correction requires significantly more bits, and will be related to the size and number of holes you're trying to fix.


The problem would seem to be preventing poisoned or damages blocks from further propogation. For example using public-private key signing of blocks so the torrent can route around the "damage". The "correction" process is to discard the block, not try to fix it.

Re: ipv6 checksum - (Anonymous) - Expand
Re: ipv6 checksum - (Anonymous) - Expand

Tue, Jun. 21st, 2005 03:05 am (UTC)
(Anonymous): Focus.

Greetings Bram, Ignore the haters. Don't bog yourself down considering every single bit of input. Stay focused on the important things. Good luck.

Tue, Jun. 21st, 2005 03:21 am (UTC)
(Anonymous): Simple Question

Um... It seems legit to me... Then again, what do I know. meh.

P.S. Logging in would mean that I would have to remember a password and stuff. Much easier to just spam posts that sound like an ex-boyfriend that just can't get over the fact that your little lady actually found something that treats her like a woman...

Happy Cheese

Tue, Jun. 21st, 2005 06:58 am (UTC)
hydrocrates: Simply...thanks

Bram, BitTorrent has and is useful. Thank you for writing it, slaving over it to make it better and sharing it with the world.

Thanks for the stanford video link, it was helpful to watch and then read the rest of your commentary.

Would that we could all get along and devote more of our energies into building better than bickering.

Keep the faith.
Cheers,
Joe
aka Tragen
http://www.WebWarrior.Net

Tue, Jun. 21st, 2005 08:41 am (UTC)
cflava5

Nice Stuff Bram. I'm going a little off topic looking for some torrent help. The web server i use currently block all forms of torrent activity thorough packet shaping(mangling). I really need to use torrents because thats how i share big files with other family members. I tried explaining to the network director at my college but she wouldnt even consider. I was wondering if theres any upgrade or new technology thats enables torrents to work even though on packet shaper technology.

Thanks. Appreciate what your doing for the community and nice presentation at Stanford!!!

Tue, Jun. 21st, 2005 07:20 pm (UTC)
(Anonymous): Secure tunnels?

I'm at the same stage as you: the University I work in has traffic-shaped everything. I don't know whether it would be a good idea for bittorrent clients to support encrypted sessions a la ssh. That way, it would look like supposedly legit traffic ;-)
Now, I haven't used torrents for almost a year, so perhaps this is already supported.
HTTPTUNNEL - (Anonymous) - Expand

Tue, Jun. 21st, 2005 09:37 am (UTC)
hunkymouse: The importance of Skype andIM and VoIP

You'll notice http://www.theikew.co.uk/2005/06/avalanche_vapou.html this piece, by an old colleague of Dvorak's, suggests a reason why Microsoft might be trying to get its own P-2-P technology.

Essentially, it points out that IM servers are big and expensive, and MSN runs one of the biggest - and points out, also, that Skype is actually a very successful IM. An interesting point!

Wed, Oct. 26th, 2005 06:30 am (UTC)
fallibledragon: Re: The importance of Skype andIM and VoIP

I think the most obvious reason for MS wanting to get involved in P2P is that they hope they can dominate it with superior technology that no one can give up, and then introduce DRM.

Also -- and this just occurred to me when reading Bram's article -- BitTorrent doesn't have a built in search system, which makes it hard to swamp with fake information, like Gnutella gets from a few bad nodes injecting junk. For a company like MS, keeping track of popular sites that kids use, and injecting fake stuff in a way that's convincing is probably much tougher.

Tue, Jun. 21st, 2005 01:30 pm (UTC)
ciphergoth

This article is indirectly linked from Slashdot. I recommend editing it to block or screen anonymous comments...

Tue, Jun. 21st, 2005 02:25 pm (UTC)
(Anonymous): Me too...

ciphergoth is right...I, also, recommend editing it to block or screen anonymous comments.
(no subject) - (Anonymous) - Expand

Tue, Jun. 21st, 2005 02:59 pm (UTC)
(Anonymous): Disk access

I believe that they can solve the poisoning problem. But I suspect that the disk access problem can be fateful for the technology. Their paper lacks any detail about how to pick the pockets to recombine. It suggests that they combine every available pocket whenever they construct any one outgoing pocket. Of course, this is not feasible. Bram, what's your guess, how do they choose the pockets to combine? Maybe they use a queue of outgoing pockets, randomly recombined with each other and incoming pockets? Would this work?

For the conspiracy-theory crowd: Avalanche is a Microsoft Research project. Most probably the only reason for its existence is that the Microsoft researcher thinks that p2p is a sexy research topic. Hundreds of researchers work at Microsoft Research on projects that will never be commercialized. I know some of them, and most of the time there is no pressure on them from the business side.

Daniel Varga

Tue, Jun. 21st, 2005 07:47 pm (UTC)
secondshadow: Re: Disk access

it might be kindof interesting if the paper described how to effectively pick pockets... :)
Re: Disk access - (Anonymous) - Expand
Re: Disk access - (Anonymous) - Expand

Tue, Jun. 21st, 2005 03:35 pm (UTC)
(Anonymous): Good job


why are you saying stuff like: "The really big unfixable problem with error correction is that peers can't verify data with a secure hash before they pass it on to other peers. As a result, it's quite straightforward for a malicious peer to poison an entire swarm just by uploading a little bit of data"?

You should never point the flaws of your system to your ennemies...





Tue, Jun. 21st, 2005 05:20 pm (UTC)
(Anonymous): Re: Good job

enemies??

we're still talking about data transfer protocols and not international warfare, right?
Re: Good job - (Anonymous) - Expand
Re: Good job - (Anonymous) - Expand
Re: Good job - (Anonymous) - Expand

Tue, Jun. 21st, 2005 04:26 pm (UTC)
griffjon

Potential problems [with Avalanche] are on the wire overhead, CPU usage, memory usage, and disk access time. Particularly worrisome for their proposed scheme is disk access

[MS-bashing]I thought these were design specs for most MS code anyhow. [/MS-bashing]

MS's catchup strategy has been hit and miss. They hit (hard) with IE, and they hit low and painfully with MSOffice, but MSN Search remains non-competitive with Google, this smells like the same -- bt is too embedded into the file sharing crowd (not to mention the large-file-distribution crowd) for anything but a true successor to knock it out, and Avalanche is not that, certainly now, and dubiously ever.

Fri, Apr. 14th, 2006 07:08 am (UTC)
kaldosh

Unfortunately, if Avalanche comes with Windows (Vista or next service packs) then it will become more used, especially if it also handles real torrents, but it will only be able to create its own version of .torrent files thus making everyone merge over, without realising the overhead and complexity they are creating.
just like the Netscape vs IE war: IE comes with windows, Netscape vanishes, security problems for years, firefox finaly triumphs.
while OSS will probably eventually win, it is still a hit to widespread usage (and therefore widespread accomodation, such as for what browser webmasters design their pages)
there are some nice ideas in Avalanche, but IMHO not enough to make it worth the overheads it would create.

Tue, Jun. 21st, 2005 04:43 pm (UTC)
(Anonymous): More Microsoft FUD

Let the information warfare puzzle begin! Can you estimate how many postings were written by MSFT agents?

Tue, Jun. 21st, 2005 06:14 pm (UTC)
(Anonymous)

Uh, the public docs on your site state that BT uses "tit for tat" still. Can't blame them for using it!

Tue, Jun. 21st, 2005 06:49 pm (UTC)
(Anonymous)

BitTorrent does use tit-for-tat, but not they braindead way they implemented it in the simulation. BitTorrent is based on an instantaneous transfer rate rather than total block counts.
(no subject) - (Anonymous) - Expand