[bittorrent] Re: HAVE messages

Elliott Mitchell ehem at m5p.com
Thu Jun 23 18:40:57 EDT 2005

>From: David Mott <dpmott at sep.com>
> I wasn't thinking that there was a need for a "have count".  Assuming that
> each piece index is the same size, you should be able to figure out how
> many indices you have based on the message length.
> This also makes the case of a MULTIHAVE with one index identical to the
> regular HAVE message (except for the 1 byte message type).  This should
> lend itself to code reuse as well.

Okay, so at the lower value of 32 peers we hit break-even. Even then you
will occasionally need to send sequential HAVE messages, while sometimes
you'll be sending back to back REQUEST/PIECE messages. On second thought,
I didn't account for the REQUEST messages in those calculations so that
factor of two disappears, but comes right back.  %-)

Still, notice that we need a *large* number of peers before MULTIHAVE is
going to produce any savings, let alone significant savings.

>From: Olaf van der Spek <olafvdspek at gmail.com>
> On 6/23/05, Elliott Mitchell <ehem at m5p.com> wrote:
> > 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
> For 1/2 of the pieces if you don't send HAVEs to peer that already
> have that pieces.

Yes, I accounted for that later.

> > 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
> Piece size isn't fixed.

Gah! I was using the default 256KB pieces.

> > 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
> Do you assume your peers download as fast as you?

The calculations assumed so and this should reflect reality pretty well.
If a peer has less bandwidth than you, you're likely to end up choking
them; if the peer has more bandwidth than you, the peer is likely to end
up choking you. So you do tend to get the effect of symetric bandwidth.

Do you feel any of the above invalidate my conclusion though?

> > 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.
> But not that valuable, as it's less likely you can complete them
> before being choked.

At the start pieces that are not common (say no more than 50% of peers
have them) are *highly* valuable, as a peers may request those and 
unchoke in exchange; while common pieces are unlikely to be requested and
so you'll remain choked. At the same time at the start rare piecs are
dangerous as you could get choked partway through and not have any way to
complete them. My main point is that the value of pieces isn't the simple
"high value" versus "low value" that the rarest first model uses, there
are many shades of grey there.

> > I haven't seen the mainline implement it despite being obvious. I figure
> > there is a reason, but I've never seen it mentioned.
> It's 'harder' to implement and your peers don't see your exact
> progress (neither of which is really an issue).

Harder, but that difference is a simple single line of code (I know, the
SI for by-hash mode included it). You simply have to check the piece
number against the bitfield of pieces you know the peer to have.

> > 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.
> It's an issue when bandwidth * delay is high.

Yes, which is more or less what that paragraph says. Bandwidth has been
increasing, *fast*. Latency hasn't been decreasing much. Hence queue
depths need to be increasing.

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