[bittorrent] Basic Queuing Algorithm question.

Elliott Mitchell ehem at m5p.com
Sat Jun 10 22:27:32 EDT 2006

>From: robert <robert.jackman at ntlworld.com>
> I have a question re the queuing algorithm.
> On the www.bittorrent.org/protocol.html page it states "that downloaders 
> should keep several piece requests queued up at once in order to get good TCP 
> performance ...".
> On the wiki.theory.org/BiTtorrentSpecification page it says that peers are to 
> keep a few unfulfilled requests on each connection.
> My question is this,is it the receiver of the request that queues requests or 
> does the requesting client wait until it has 5 requests to send before 
> sending.
> It might only be me , but i felt that the one of the docs gave different 
> emphasis in terms of who was doing the queuing,the receiver or the sender.!??
> My hunch is that its the receiver that queues the incoming requests.!?
> If so,say we are using the default 5 static que.
> if 4 more requests don't come in.
> Is it common to implement somesort of timeout so that the request gets 
> fulfilled with a peice message eventually,or will that connection just get 
> choked off after x amount of time?

The network queues the requests. Peers are pretty well required (though
it isn't explicitly stated) to queue requests they cannot immediately
fulfill from unchoked peers (you can though drop requests on the floor if
you choke them). What is being stated is that peers should keep some
number of unfulfilled requests "in flight". The protocol definition
doesn't require this though, this is actually an implementation detail,
but one so crucial it bears mentioning in the protocol specification.

The key point is if you don't keep some requests in flight you couple
your maximum download speed to the link RTT, rather than the link
bandwidth, and this is a very bad thing.

Think about how things work without queuing. In order to download a
block, you would have to request it, one round-trip, then wait for the
block to download and finally move on to the next block. So it takes one
round-trip plus one block-period to get a piece. This isn't a huge deal
if you've got a 56kbps, .5sec RTT link. .5sec to request and then 4.5sec
to download the block. 256kb/5sec, 51.2kbps, a pretty good utilization of
your link. On an 8mbps, .05sec RTT link, this is a problem. .05sec to
request, then .03sec to download. 256kb/.08sec, 3.2mbps is a pathetic
utilization of your 8mbps link.

So queuing and thereby avoiding linking your bandwidth to your RTT is a
very good thing. Bandwidth is going up very fast, RTT hasn't been going
down very much.

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