[bittorrent] Queuing algorithm section

Alan McGovern alan.mcgovern at gmail.com
Sun Aug 5 11:18:51 EDT 2007


>
> I agree with the min of 2 blocks, but a linear increase just doesn't
>
take into consideration that increased bandwidth usually implies lower
> latencies. So at lower speeds you should request more pieces per kB
> than at high speeds.


Yes, yes it does. Also, you've just shot yourself in the foot by requesting
less pieces when you have a lower latency connection. As a test, get a
client and modify it to only pipeline 2 requests per peer. Then run a lan
transfer. Modify the client to pipeline 100 requests per peer, run a lan
transfer again. You'll find that the second transfer is *much much* faster.
I'd also estimate the latency to be << 1ms in both cases, the exact
situation where you claim less requests == better.

A cable modem downloading from a peer at 8kB/s needs a much larger
> queue than just the 2 you suggest. The second piece will already be in
> transit when you finish the first one, the piece you are uploading to
> the peer must finish before you can send the request message, and the
> request message must arrive.


If a cable modem has an upload capacity of 8kB/sec to me, then 2 pieces is
perfect. It would take that peer 4 entire seconds to empty that queue. So,
if i have two requests pipelined, and he completes one, i have 2 entire
seconds, thats 2000 miliseconds in which to transmit an additional request
to him before his queue empties.

Of course, if you are uploading to that peer, you may have problems keeping
his queue filled (if you have low upload speed). So yes, in that scenario
you could add a little check:

if(iAmUploadingToThisPeer && pendingRequestsOnPeer < 6)
    pendingRequestsOnPeer = 6;

Of course, you could do this better by applying a little maths and
calculating roughly how long it takes to upload a piece to that peer and
from there calculate the min queuedepth.

psuedo code:
int timeToUploadABlock = uploadSpeedToPeer / BlockLength;
int timeNeededForPeerToEmptyHisQueue = (BlockLength * NumberOfRequests) /
downloadSpeedFromPeer;

if(timeToUploadABlock  > timeNeededForPeerToEmptyHisQueue )
     IncreasesQueueDepth();

This would definitely be worth mentioning as part of the algorithm.

Around the 8kb/s region, you might as well request 10 blocks or so.
> Space on the queues aren't a precious commodity.


This is actually horribly inefficient. If you are approaching the end of a
torrent and you have a large number of requests pending on slow peers (
0.5-3kB/sec) and a small number of requests on high bandwidth peers, then
you'll find it will take *ages* to complete the torrent. This scenario is
exactly what this algorithm avoids. It gives fast peers more requests, which
is exactly what you want. Trying to judge things by latency (however the
hell you can measure that) is not a good idea.

> b) The pending requests should have an upper limit of 100. You shouldn't
> > have more than 100 pending requests off a single peer.
>
> It's bad enough we ended up with the de facto 16kB limit, please don't
> make it worse.


There is nothing wrong with the 16kB 'limit'. Have you ever thought of what
would happen if there was no limit? While 100 is an artificial limit, it
does allow people to know the worst-case and so when optimizing, they know
the limits. That's the only reason for inserting that limit.

Anyway, i'm not saying this algorithm is the most efficient one possible.
What i am saying is that it's much better than a static queue, and in all
the most common scenarios (i.d say 95% of scenarios), it will perform quite
well. If you need to tune the algorithm, the only value you have to change
is the 10kB/sec value which is used to decide when an additional request
should be pipelined.


Alan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ibiblio.org/pipermail/bittorrent/attachments/20070805/f3661ea0/attachment.html 


More information about the BitTorrent mailing list