Igor Bajatovski | 5 Aug 03:41 2007
Picon

(no subject)

--

-- 
Игор Бајатовски
_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Alan McGovern | 5 Aug 06:36 2007
Picon

Queuing algorithm section

I'm just going to give a heads up that i'm going to rewrite the 'Queuing Algorithm' section on the bittorrent spec page. It's been under dispute long enough that i'm going to resolve it.

The text will change to something along the lines of this:

1) A static queue is a bad idea.

a) Slow peers will have lots of unneccessary pending requests with a static queue
b) Fast peers won't have enough pending requests
2) Dynamic queue is a good idea:
a) The easiest way to do this is to give each peer a static queuedepth of at least 2 blocks (2x16kB). For each 10kB/sec upload the peer has, add one extra pending request. So, the pending requests can be calculated as: 2 + (downloadSpeedInKilobytes / 10).
b) The pending requests should have an upper limit of 100. You shouldn't have more than 100 pending requests off a single peer.


So, does anyone have any comments about that before i go ahead and make that change. The 10kB/sec figure is one i chose from testing different values. The choice of 10kB/sec means that for peers with large upload bandwidth, you'll end up having a lot more data requested than they can supply in one second. For example, with 500kB/sec available, there would be 832kB of data requsted. For a peer with 2000kB/sec available, you'll have 3200kB of pending requests. This should avoid most issues caused by a high latency connection. Latencies of up to 1second can be handled with this algorithm (i think, feel free to correct me ;) ).

Also, is it worth putting in a hard limit of 100? Should it be less? More? Not there?

Let me know your thoughts, unless someone can come up with a good reason as to why this shouldn't be added, i'll change the text on http://wiki.theory.org/BitTorrentSpecification on monday or tuesday.
_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Alan McGovern | 5 Aug 06:40 2007
Picon

Endgame mode

I was thinking, the best condition for entering endgame mode would be when there are zero blocks free to be requested. There's no point in having a fixed limit like '20 pieces remaining'. I want to reword that section to indicate that 'zero pieces remaining' is the preferred indicator of when to enter endgame.

The reason is that suppose you have 50 open connections downloading the last 50 pieces, 40 of those peers could be really slow with 10 being fast, so there's no point in those 10 peers waiting around until 20 slow peers finish so the threshold of '20 pieces remaining' is reached. This is counter productive.

_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Elliott Mitchell | 5 Aug 07:12 2007

Re: Queuing algorithm section

>From: Alan McGovern <alan.mcgovern <at> gmail.com>
> I'm just going to give a heads up that i'm going to rewrite the 'Queuing
> Algorithm' section on the bittorrent spec page. It's been under dispute long
> enough that i'm going to resolve it.

Needed. Two people can argue, hopefully a third party is neutral.  :-)

> The text will change to something along the lines of this:
> 
> 1) A static queue is a bad idea.
> a) Slow peers will have lots of unneccessary pending requests with a static
> queue
> b) Fast peers won't have enough pending requests
> 2) Dynamic queue is a good idea:

I'd agree with this.

> a) The easiest way to do this is to give each peer a static queuedepth of at
> least 2 blocks (2x16kB). For each 10kB/sec upload the peer has, add one
> extra pending request. So, the pending requests can be calculated as: 2 +
> (downloadSpeedInKilobytes / 10).

Thinking about it, since the algorithm for queue depth does not effect
protocol conformance, merely performance, perhaps this should be a
sub-section "sample queuing algorithms". *Something* definitely needs to
be said, since this is a *crucial* performance issue. 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.

> b) The pending requests should have an upper limit of 100. You shouldn't
> have more than 100 pending requests off a single peer.
> 
> 
> So, does anyone have any comments about that before i go ahead and make that
> change. The 10kB/sec figure is one i chose from testing different values.
> The choice of 10kB/sec means that for peers with large upload bandwidth,
> you'll end up having a lot more data requested than they can supply in one
> second. For example, with 500kB/sec available, there would be 832kB of data
> requsted. For a peer with 2000kB/sec available, you'll have 3200kB of
> pending requests. This should avoid most issues caused by a high latency
> connection. Latencies of up to 1second can be handled with this algorithm (i
> think, feel free to correct me ;) ).

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. Problem is, both of
these situations exist in Real Life. Satellite links (Antarctica? places
without wired high speed) are known to have high latencies. Where I am, I
can get to many sites in well under 50ms. I'm unsure whether it effects
current generation cable modems, but they used to cause huge latency as
you approached their maximum bandwidth.

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.

> Also, is it worth putting in a hard limit of 100? Should it be less? More?
> Not there?

No. Once you get gigabit to the home, that will be too shallow.  :-)
There have been experiments on backbone links that make that halfway
plausible, though right now only Universities are likely to be in this
category.

--

-- 
(\___(\___(\______          --=> 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\_|_/___/
Alan McGovern | 5 Aug 07:35 2007
Picon

Re: Queuing algorithm section

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.

_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Joris Guisson | 5 Aug 09:42 2007
Picon

Re: Endgame mode

I agree, figured that one out a long time ago and once I came to that conclusion, I also realized that a special endgame mode is useless.

My client just distributes the peers over the pieces that are currently downloading, it tries to avoid multiple peers on the same piece, by starting the download of new pieces. (when all pieces have a peer)

At the end of the download, there are no more pieces left to start, so it automatically assigns free peers to the remaining ones, resulting in multiple peers for the same piece. So you end up in some sort of 'endgame' mode without even having to switch to a different algorithm.

Joris,


On 8/5/07, Alan McGovern <alan.mcgovern <at> gmail.com> wrote:
I was thinking, the best condition for entering endgame mode would be when there are zero blocks free to be requested. There's no point in having a fixed limit like '20 pieces remaining'. I want to reword that section to indicate that 'zero pieces remaining' is the preferred indicator of when to enter endgame. 

The reason is that suppose you have 50 open connections downloading the last 50 pieces, 40 of those peers could be really slow with 10 being fast, so there's no point in those 10 peers waiting around until 20 slow peers finish so the threshold of '20 pieces remaining' is reached. This is counter productive.

_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent


_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Alan McGovern | 5 Aug 16:58 2007
Picon

Re: Endgame mode

An 'EndGame' mode is still useful with your kind of algorithm though.

I changed from a one-piece-per-peer algorithm to a multiple-peers-per-piece algorithm as it offers major benefits (not going to go into that here though). However, depending on your request pipelining algorithm, you can still benefit majorly from EndGame.For example if you have a static queue of 5 pieces, and the last peer has 5 requests and is uploading at 0.5-1kB a second, it's going to take quite a long time to finish the torrent. EndGame would finish it within seconds.

Alan.

On 8/5/07, Joris Guisson <joris.guisson <at> gmail.com> wrote:
I agree, figured that one out a long time ago and once I came to that conclusion, I also realized that a special endgame mode is useless.

My client just distributes the peers over the pieces that are currently downloading, it tries to avoid multiple peers on the same piece, by starting the download of new pieces. (when all pieces have a peer)

At the end of the download, there are no more pieces left to start, so it automatically assigns free peers to the remaining ones, resulting in multiple peers for the same piece. So you end up in some sort of 'endgame' mode without even having to switch to a different algorithm.

Joris,


On 8/5/07, Alan McGovern < alan.mcgovern <at> gmail.com> wrote:
I was thinking, the best condition for entering endgame mode would be when there are zero blocks free to be requested. There's no point in having a fixed limit like '20 pieces remaining'. I want to reword that section to indicate that 'zero pieces remaining' is the preferred indicator of when to enter endgame. 

The reason is that suppose you have 50 open connections downloading the last 50 pieces, 40 of those peers could be really slow with 10 being fast, so there's no point in those 10 peers waiting around until 20 slow peers finish so the threshold of '20 pieces remaining' is reached. This is counter productive.

_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent



_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Alan McGovern | 5 Aug 17:18 2007
Picon

Re: Queuing algorithm section

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.

_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Carsten Otto | 5 Aug 17:19 2007
Picon
Picon

Re: Queuing algorithm section

On Sun, Aug 05, 2007 at 12:36:10AM -0400, Alan McGovern wrote:
> Also, is it worth putting in a hard limit of 100? Should it be less? More?
> Not there?

I am enjoying bittorrent with a gigabit line at home. I reach about 10
MByte/sec downloading, up to 23 MByte/sec uploading (from/to many peers
of course). I have doubts that 100 as a limit is enough for speeds like
this (and more?), but I do not know exactly how the queue is used.

Bye,
--

-- 
Carsten Otto
c-otto <at> gmx.de
www.c-otto.de
_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent
Joris Guisson | 5 Aug 20:38 2007
Picon

Re: Endgame mode

No, when multiple peers are assigned to the same piece, I send requests to all assigned peers.

So even if one is being slow, the other assigned peers can pick up the slack.

Joris,

On 8/5/07, Alan McGovern <alan.mcgovern <at> gmail.com> wrote:
An 'EndGame' mode is still useful with your kind of algorithm though.

I changed from a one-piece-per-peer algorithm to a multiple-peers-per-piece algorithm as it offers major benefits (not going to go into that here though). However, depending on your request pipelining algorithm, you can still benefit majorly from EndGame.For example if you have a static queue of 5 pieces, and the last peer has 5 requests and is uploading at 0.5-1kB a second, it's going to take quite a long time to finish the torrent. EndGame would finish it within seconds.

Alan.

On 8/5/07, Joris Guisson < joris.guisson <at> gmail.com> wrote:
I agree, figured that one out a long time ago and once I came to that conclusion, I also realized that a special endgame mode is useless.

My client just distributes the peers over the pieces that are currently downloading, it tries to avoid multiple peers on the same piece, by starting the download of new pieces. (when all pieces have a peer)

At the end of the download, there are no more pieces left to start, so it automatically assigns free peers to the remaining ones, resulting in multiple peers for the same piece. So you end up in some sort of 'endgame' mode without even having to switch to a different algorithm.

Joris,


On 8/5/07, Alan McGovern < alan.mcgovern <at> gmail.com> wrote:
I was thinking, the best condition for entering endgame mode would be when there are zero blocks free to be requested. There's no point in having a fixed limit like '20 pieces remaining'. I want to reword that section to indicate that 'zero pieces remaining' is the preferred indicator of when to enter endgame. 

The reason is that suppose you have 50 open connections downloading the last 50 pieces, 40 of those peers could be really slow with 10 being fast, so there's no point in those 10 peers waiting around until 20 slow peers finish so the threshold of '20 pieces remaining' is reached. This is counter productive.

_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent




_______________________________________________
BitTorrent mailing list
BitTorrent <at> lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/bittorrent

Gmane