[bittorrent] Re: HAVE messages

Elliott Mitchell ehem at m5p.com
Wed Jun 22 23:42:43 EDT 2005

>From: David P. Mott <dpmott at sep.com>
> >From: Olaf van der Spek <olafvdspek at gmail.com>
> > Why not?
> > You can put multiple HAVEs in a singel TCP packet.
> Yes, you're right, this can be done.  But you still have the overhead of 
> the BT protocol for each piece index.  That's all I'm saying.

4 bytes for the message length (interesting given how no messages other
than the bitfield, can even approach 64K). 1 byte for the message type.
4 bytes for the piece number. So 9 bytes total for a HAVE message.

A MULTIHAVE message would share the 4 byte message length, and 1 byte
message type. If we stick with the theme of only long integers, we'd have
a 4 byte have count. Then 4 bytes for each piece. So 9 bytes plus 4 bytes
for each piece.

For one piece, we use 9 bytes with a conventional HAVE and 13 with
MULTIHAVE message. At two pieces, we use 18 bytes with HAVE and 17 with
MULTIHAVE. At three it becomes 27 and 21. Until we're averaging 3 pieces
per message, the savings aren't much. So the question becomes, how many
HAVE messages are sent?

If you're in a heavily seeded swarm, your peers will never send HAVE
messages as seeds will only need BITFIELD messages to advertise their
status. In a fresh swarm with one seed, your peers will end up sending
HAVE messages for every piece. The average is likely to be one HAVE
recieved from each peer for every two pieces. Suppression of unneed HAVEs
would further drop this to one HAVE for every four pieces.

Most clients request blocks of 32K at a time (while the baseline defaults
to 16K), for which it takes 8 messages to complete a piece. Multiplying
those two numbers, we should expect to receive a wave of HAVE messages
every 32 blocks we download. So with 32 peers each HAVE message will be
interleaved with one other block, resulting in zero savings from
MULTIHAVE. At 64 peers MULTIHAVE would save some, but not much.

The baseline client only seeks 20 peers and refuses connections at 55
peers. Generally 50 peers is the worst case used for discussions. With
these sorts of numbers, HAVE supression seems profitable, while MULTIHAVE

> > If you don't update your view of the world you won't be able to
> > execute rarest first properly.
> True, but so long as you can see at least one copy of each piece, I'm not 
> sure that this is so important.  The whole "rarest first" algorithm is an 
> arbitrary algorithm which isn't called out in the BT spec (right?).  So 
> long as you're pulling down content, I don't think it matters.

Olaf van der Spek got to this first. If only one peer has a piece and
that peer disappears, you've got a problem.

I suspect weighting the random number generator may be a better approach
than simply choosing those pieces first though. Notably at the start it
is more notable that pieces all peers have are worthless (you won't be
able to upload them), than that rare pieces are valuable.

> >From: Elliott Mitchell <ehem at m5p.com>
> > 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.
> Yes, I believe that this was also mentioned on the Yahoo mailing list. 
> It's a good improvement to the current protocol, no argument.  I have no 
> reason to belive that client authors are not currently doing this.

I haven't seen the mainline implement it despite being obvious. I figure
there is a reason, but I've never seen it mentioned.

> >> 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.
> I won't argue that queueing is necessary to overcome network latency.  I 
> was trying to point out that clients should reserve the right to simply 
> drop requests (i.e. if they get flooded with requests or if requests 
> become "stale" because it is taking too long to get to them).
> Auto-tuning would be nice, but even some basic rules like "don't send me 
> more than 5 outstanding requests, and expect me to drop any request over 5 
> minutes old".

Dropping and then notifying helps auto-tuning, as you can detect queue
depth on the opposite end with certainty. You simply keep queuing more
requests and when requests get dropped, you reduce the number you queue.

At the same time I doubt 5 is sufficient in the general case. Figure DSL
lines have around 50ms round-trip, and 2-10mbps (I've heard of 100mbps in
some places). So 10-50KB in-flight, about 3 requests; perhaps the
defaults aren't as bad as I thought, and 5 might work here. Local
transfers, or very high bandwidth areas might do 5ms round-trip and
1000mbps though. In this case we see a need for 30 requests in-flight,
and the defaults don't work.

> >> 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.
> Because it's not sending a solitary HAVE message every time I complete a 
> piece -- it's grouping them together in a MULTIHAVE or putting the 
> information into a bitfield.

Okay, you sounded like you were suggesting scrapping the existing
handling of this problem. Now, see above for why MULTIHAVE is unlikely to
gain much.

> > 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.
> Even (or especially?) given that, I'd prefer a protocol that allowed me to 
> ask for the information that I want, instead of sending it to me 
> unsolicited.

At some point, you're going to have to deal with unsolicited data. Might
merely be requests for updates, but will happen.

> >> 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.
> I think that we're on the same page here -- the information is necessary 
> to make the protocol "flow" better (polling for available pieces is every 
> bit as inelegant, or moreso, than the current protocol).  I'm just saying 
> that it could be reworked to keep the lower bandwidth peers from getting 
> swamped in HAVE messages.

Now now instead of being swamped with HAVE messages, they'll be swamped
with requests for HAVE messages? In such cases it might be better to
simply disconnect from high-bandwidth peers, unless they have rare

(\___(\___(\______          --=> 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