HAVE messages (formerly "[bittorrent] Open letter to the BBC")

Elliott Mitchell ehem at m5p.com
Mon Jun 20 18:48:34 EDT 2005


>From: David P. Mott <dpmott at sep.com>
> There was a protocol extension suggested awhile back for consolidating 
> (grouping) or otherwise encoding HAVE messages.  The reasoning was that, 
> for a dial-up user, the HAVE messages took up a significant amount of the 
> bandwidth.  I think that the dial-up v/s broadband speeds constitutes 
> something close to the "orders of magnitude" condition.

So you'll save the message header if you manage to group large numbers
of HAVEs together. Should approach 50% savings if you manage to do this
ideally (send HAVE messages for every PIECE at the same time). As Olaf
mentioned though, most of the packet overhead will be IP, TCP and
ethernet headers. Your TCP/IP stack should already pack those together.

There is another simple strategy that will (not approach, *will*)
generate 50% savings, and further doesn't require any extensions. Supress
HAVE messages to peers that already have the piece. Notably on completing
a piece the baseline client will send a HAVE message to *every* peer,
including the source of the piece and other peers that already have the
piece.

With the baseline client, if a pair of peers do not have a piece, when
one downloads it, it will send a HAVE message. The other peer will
eventually download it from somewhere, and send a HAVE back. By
surpressing the second HAVE message, we're guarenteed to reduce the
number sent by 50%.

> The bittorrent protocol is centered around the concept of "every peer 
> knows what every other peer has at all times".  I'm still undecided if 
> this is the best way to go about it.

That is the tone the protocol specification takes, but is not actually
strictly true. As noted above, peers are only interested in knowing about
which peers have pieces that they themselves do not have. If a peer has a
piece, then it doesn't care whether any other peer has that piece. The
peer does want to ensure other peers that do not have the piece know that
it has the piece, so that they can request it in exchange, but otherwise
the model need not be complete.

Though it has downfalls, the number of HAVE messages, this model does
seem to work pretty well.

> For instance -- let's say that I wrote a protocol that was similiar to BT, 
> but didn't do that whole awkward choking/choked/interesting/interested 
> thing, and I didn't include HAVE messages.
> 
> Instead:
> 1.  Peers can request whatever they want, but I'll only service one request
>      at a time and discard the rest.

Ouch! Your protocol's maximum speed is now chained to network latency.
You must queue requests, otherwise you need a full roundtrip to request
a new piece. With any high speed network, the bandwidth/latency ratio is
likely to be very unfavorable.

I strongly suspect the baseline client's default queue depth is too
small. I believe it should be possible to make a client that auto-tunes
the queue depth. 

> 2.  I'll upload at a rate that I think is appropriate.  They can block on
>      their TCP/IP socket waiting for data.
> 3.  With #1 and #2, there's no need for
>      "choking/choked/interesting/interested".

The specification explains why this was done. Most TCP stacks not
handling large numbers of connections gracefully. Though inelegant, this
/does/ work reasonably well. Revisiting the problems they solved would be
a good thing, but simply removing them without carefully considering what
they fixed is a bad idea.

> 4.  The protocol provides a way to ask for the bitfield that is initially
>      exchanged in the BT protocol.  Peers may ask for it initially, and
>      when they get all of the pieces from me that they are interested in,
>      then they can ask for the bitfield again to see if I have gotten more.
> 5.  If there is an absolute need to be kept periodically "up to date" on
>      what the swarm looks like, then I can request the bitfield or some
>      delta representation from my peers on a periodic basis.  If the
>      bitfield thing is too big, then (as the extension was presented so
>      long ago) a MULTIHAVE message could be included in the protocol
>      and sent by my peers to me on a periodic (10 minutes?) basis.

How does this improve on BitTorrent? You've just reinserted the piece of
BT you were complaining about.

Problem is differing peers will need differing levels of accuracy of this
information. Notably a peer on a high-speed network may complete multiple
pieces a second, a peer on a dial-up network may take 10 seconds to
complete a single piece. The first one will need data that is much more
up to date as its state is rapidly changing, the second can use data
that lags far behind with no deficit.

> Thoughts?  Discussion?

Peers are going to have to know about the state of other peers somehow.
Even the scheme of simply randomly asking for pieces will result in you
knowing which pieces a peer has by the requests that refused.

Therefore forget about getting rid of it. The only possible goal is to
exchange that information more efficiently. Though less than ideal, BT's
method is quite effective, and not all that bandwidth intensive.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \BS (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_CS\   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/





More information about the BitTorrent mailing list