[bittorrent] Queuing algorithm section

Alan McGovern alan.mcgovern at gmail.com
Sun Aug 5 01:35:50 EDT 2007


>
> You've also made a
>
critical mistake in your sample algorithm here, queue depth needs to be
> effected by both bandwidth (which you've accounted for) and RTT (which
> you've missed). The moment you hit a link with high latency (across the
> world or perhaps a satellite link), performance will fall apart.


Not a critical mistake, a calculated error margin which allows for a
dirt-simple algorithm. I'm assuming that modern connections have a latency
of far less than 2 seconds. I think most satellite connections will fall
into this category, but obviously not all. I'd give an estimate that maybe
90% of connections are low-latency (less than 1000ms). This means the above
algorithm will work perfectly. At latencies of up to 1500 miliseconds, it
should still work fairly well, but at latencies of over 1500ms, it won't be
optimal anymore (as you'll need a larger queue depth).

Works as long as one's latency is less than 1 second. OTOH if someone has
> a link with 33ms, the queue depth will be excessive.


That doesn't matter. So what if it's 'excessive'. The point is it's not too
small. If a user has 100kB/sec upload, with 1ms ping, i'll still want to
queue 12 pieces off him, because i know he'll fulfill them all pending
requests within 2 seconds, so there's no 'wastage' as such. A deeper queue
isn't a problem and has no detrimental effect.

I'm unsure whether it effects
> current generation cable modems, but they used to cause huge latency as
> you approached their maximum bandwidth.


Thats because you were saturating the uplink/downlink. If you ever saturate
your uplink, you will experience higher pings. Thats a fact of life, nothing
will change that.

The problem isn't simple. You need to know what the maximums of each
> individual connection is, and queue appropriately. Attempting to probe
> each connection by slowly increasing depth, seems a reasonable approach.


It may seem reasonable, but it's over complicated and near impossible to
implement effectively. The benefits it offers over my 'algorithm' are fairly
negligible. In a small number of cases (satellite connections with a ping >>
1500ms), you're algorithm would perform better, but in all others, mine is
more than sufficient. The other main advantage is my algorithm can be
implemented with 1 line of code. I couldn't even guess how many yours would
take.

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


More information about the BitTorrent mailing list