[bittorrent] Re: HAVE messages

David P. Mott dpmott at sep.com
Wed Jun 22 18:12:23 EDT 2005


> From: Olaf van der Spek <olafvdspek at gmail.com>
> Subject: Re: [bittorrent] Re: HAVE messages
>
> 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.

> 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.

>> I should also be able to gain some insight into the speed of each peer
>
> You should? How?

Doesn't the tracker make available the progress (uploaded and/or 
downloaded bytes) of each peer, if you ask for it?  If you monitor that, 
then you can gauge the progress of your peers.





> From: Elliott Mitchell <ehem at m5p.com>
> Subject: Re: HAVE messages (formerly "[bittorrent] Open letter to the BBC")


> 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.

> 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.

True, and well stated.


>> 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".


>> 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.

Well stated.  Specifically what about large numbers of connections do the 
TCP stack implementations have issues with?  Is it just having them 
connected, or trying to push/pull data through all of them at once?


>> 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.



> 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.

Or maybe I could request that peers send me their HAVE messages -- perhaps 
discrete settings like up-to-the-minute, or grouped and sent every X 
minutes.


>> 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.

For instance... I read an article (it was posted on this list) where one 
of the proposed enhancements was to have the tracker hand out peers which 
matched your connection speed.  If this were done, then no one peer would 
receive a disproportionate number of HAVE messages from the swarm, and in 
fact it might be interested in all of them.  It's when there is a 
low-bandwidth peer connected to a high-bandwidth swarm (or subset of a 
swarm) that they get showered with HAVE messages that they can't possibly 
make use of in a timely manner.


-dpmott




More information about the BitTorrent mailing list