[bittorrent] Introductory/endgame algorithms

Andreas Aardal Hanssen bittorrent at andreas.hanssen.name
Tue Sep 27 02:00:25 EDT 2005


On Mon, 26 Sep 2005, Elliott Mitchell wrote:
>That is the cited reason for the existance of end-game mode. I'm
>suggesting that though that may be a legitimate reason, it isn't good
>enough as the cost outweighs the benefit. Notably the large cost. Also
>note in the paper mentioned, the time spent in endgame is minimal so
>those gains are minimal even in an optimistic situation.

..that also means the overhead is minimal.If you've got a DVD image of
2000 pieces, downloading on average 2-3 pieces twice means you've got 0.1%
overhead.

>The issue comes that ideally requests won't spend _any_ time in the
>remote queue. In this case there isn't any window of opportunity for the
>CANCEL message to overtake the REQUEST message. As such the CANCEL
>message becomes worthless because it can't ever do its job.

Agreed.

>Though at worst you only need to down evil+1 copies of the piece (evil
>being the number of evil attacking clients). The moment you see one block
>that two peers gave different data for a particular block, you *know*
>that at least one of those peers is evil. Run the hash only using blocks
>from one of the two, if the hash checks out you know the other peer is
>the evil one. Otherwise run the hash using the peer's blocks, if it is
>correct you can declare the first peer to be evil. If neither verifies
>then you've got multiple evil peers.

That's a pretty smart algorithm. But it does require you to keep all
duplicate blocks, and also means that you need to download the full piece
from at least one of them, from what I can see.

>You get major perform damage if you keep 100 peers alive. The number of
>HAVE messages is directly related to the number of peers. At 30 peers the
>HAVE messages account for 50% of the BitTorrent protocol overhead, or 1%
>of the payload size. At 100 peers, HAVE messages are accounting for 75%
>of the overhead, 3% of the size of the payload.

True.

>Though 3% isn't a huge percentage, considering the size that payloads
>run, 3% is likely to be several megabytes. Do you see a reason that
>justifies an additional 2% overhead?
>I'm surprised Bram increased the defaults in 4.0.4. Though the
>performance gain from auto-tuning queue depth likely more than makes up
>for this loss.

I tried his stuff on a local network, and although it produced good
download results, his client is DoS'ing me with block requests. I've seen
burst requests of 32++ blocks, and that seems quite pointless. I agree
some auto-tuning to keep the pipeline filled is a good idea, but it's
quite necessary to cap the outbound queue too.

Andreas

--
Andreas Aardal Hanssen
http://www.andreas.hanssen.name/gpg2
http://www.trolltech.com/




More information about the BitTorrent mailing list