Have compression (was Re: Standards (was [BitTorrent] Back to

Justin Cormack justin at street-vision.com
Wed Feb 9 06:29:45 EST 2005


> >>>increase the latency of them.
> >>
> >>What's the definition of latency here?
> > 
> > 
> > Latency is the time between when you download something (the minimum
> > downloadable unit) and when you announce a have so another client can get it
> > from you. It clearly has a major effect on throughput. Note the BT1 way of
> 
> Clearly? Why?
> 
> > having a minimum downloadable unit (chunk) smaller than the verifiable unit
> > unavoidably increases latency, probably by too much or the endgame stuff
> > wouldnt be needed.
> 
> As far as I know, end game mode has nothing to do with have messages.

It has to do with latency.

ok, some numbers.

assume connections are 1Mbit ie 128kbyte/s

Downloading a piece takes us best case 2s for 256k pieces, then we have to
checksum it. However in fact we might be downloading at a typical time
maybe 8 pieces (whats a typical number? clearly depends on the stage of your
download etc, not sure) from different peers, so on average each might take 16s
even assuming you are never choked (unlikely). So the time between you 
downloading the (first) minimum download unit (16k say in BT1 - which will
take 1s at same contention) is 15s. Average latency is 8s, best case.

If you have lots of things to download from your peers this really doesnt
matter, the arrival of a new have message is fairly unimportant. But at the
beginning (when most peers dont have anything) and the end (when most peers
have the same as you), you can cut this latency by a huge amount by sending
the have message for a smaller unit (like the minimum verifable unit), so
that it can be sent along a chain of peers much faster).

This gives us another strategy for out have compression algorithm: if the peer
is interested, dont send haves, batch them up so they can be coalesced into
haves for larger amounts. After all the peer is already saying it is happy
to download what we are offering. This reduces bandwidth used for have 
messages even more.

Your solution of chunk-haves can be used for reducing latency, but doesnt
suggest strategies for how to use it, and when you use it it always increases
bandwidth. My version starts to suggest how to use it, and has other side
effects like reducing the load on seeds and near-seeds as they dont have
to send out bitmaps, they can send high order have messages.

Justin


  


 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list