Thursday, November 02, 2006

I finally got rate limiting pegged. Method 4 out of my last post with a few slight modifications was what finally worked for me, i knew i was onto a winner!

As i found out, relying directly on DownloadSpeed to implement rate limiting made it next to impossible to get accurate rate limiting, but without using the current DownloadSpeed it's impossible to get accurate rate limiting. A bit of a conundrum, isn't it. So, the solution is to use what is best described as a feedback loop a.k.a. a Proportional Intergral controller for those of you not studying electronic engineering ;)

My final algorithm works as follows:
1) Each chunk of data i send is (ideally) exactly 2kB in size.
2) Every second i calculate the error rate in my download speed. The Error rate is the difference between the download speed i want and what i'm currently downloading at.

int errorRateDown = maxDownloadSpeed - actualDownloadSpeed;

3) I also have stored the error rate from the previous second which i then use to get a weighted average. This average is weighted to give the error rate from the last second more importance than the error rate in the current second.

int averageErrorRateDown = (int)(0.4 * errorRateDown + 0.6 * this.SavedErrorRateDown);

4) Finally, to calculate the number of 2kB blocks i should be transferring this second, i just run the simple calculation:
int numberOfBlocksToRequest = (maxDownloadSpeed + this.averageErrorRateDown) / ConnectionManager.ChunkLength;

As you can probably see, the closer i get to my requested download speed, the smaller and smaller averageErrorRateDown will get, thus reducing the number of blocks i request. If i'm downloading to slowly, averageErroRate will be a large positive number (increasing the number of blocks). If i download too fast, averageErrorRate will become a large negative number (decreasing the number of blocks).

Then every time i want to send a block, if numberOfBlocksToRequest is greater than zero, i decrement it by one and send the block. If numberOfBlocksToRequest is zero, i just hold the block in memory in a queue and as soon as i'm allowed, i'll send it. Obviously a FIFO queue is used ;)

The only issue with this method is that the size of the blocks i send aren't always exactly 2kB in size, so this method will always settle at a download rate just below the requested download rate. But that can be compensated for.

6 comments:

knocte said...

Nice tool, I'll try it out soon.

BTW, do you have plans in supporting e2dk too? I have the sources of a version of lphant (C#) that was still free, if you're interested.

Alan said...

Hi,

Thats not a bad plan, but at the moment i'm just trying to get the Bittorrent side of things up and running with all the bells and whistles. I'll only ever extend the library to support other protocols when i'm happy that i have BitTorrent pretty much bug-free.

John said...

The solution you have arrived at is so very close to a PI controller.

Integral action has a natural averging effect.And yes you are correct, a integral controller asymptotically approaches the limit.

this.SavedErrorRateDown is very close to the integral term I suggested in my previous comment. You appear to disregard the sign however, so may have trouble tracking back to the limit once you exceed it.

Good to hear you got something going

Alan said...

int errorRateDown = maxDownloadSpeed - actualDownloadSpeed;

if my maxDownloadSpeed is 100kB/sec but i actually am downloading at 120kB/sec, errorRateDown will become -20.

Then, when i calculate:
int numberOfBlocksToRequest = (maxDownloadSpeed + this.averageErrorRateDown) / ConnectionManager.ChunkLength;

That becomes:
int numberOfBlocksToRequest = (100 - 20) / 2kB;

=> numberOfBlocksToRequest = 40.

So if i do go too fast, it will actually slow down ;) Unless i've misunderstood something...

Ryan said...

Hi,

This is a great description of a bandwidth limiter for Bittorrent, I'm implementing it in my client now.

Thanks for the writeup!

knocte said...

As some people have asked me for the sources of lphant (because I said I had them before it became non-open source, in the first comment), I have put them in github:

https://github.com/knocte/lphant

Hit Counter