Using a Hrrn scheduler for uploads

arne_bab · #1 (**permalink**) March 28th, 2009

I just doublechecked an evaluation I did a few months ago, and I could verify the efficiency of using a Hrrn scheduler for uploads instead of the current FIFO scheduler (I found mistakes in the previous evaluation - compared transfer-times instead of wait times - it did smell wrong back then, but it took me some time to have another go at it).

The result data can be found in svn at https://phex.svn.sourceforge.net/svn...uing_strategy/

I parsed them with pyxplot to generate some human digestable graphs which clearly show that the Hrrn scheduler provides massive improvements for small files while giving only a moderate penalty to large files (both relative to the time a transfer needs to complete).

To say it frankly: With FIFO most small files have to wait about a few hundred times longer than they need to be transferred (see image 2).

With Hrrn small file uploads finish after a tiny fraction of the time needed with FIFO (see image 2), while large files have to wait about as long as they need for the transfer before the upload starts (see image 1).

Also with Hrrn the wait time for downloads is roughly proportional to the file size, which in turn is roughly proportional to the upload time.

conclusion

If these evaluations are correct (I'm quite sure that they are, now) Phex should use the Hrrn scheduler for uploads.

With experience the algorithm could be tuned to account for the download mesh which reduces the transfer time for large files, since these are often downloaded from multiple sources at the same time, while the same seldomly happens for small files (the transfer time for the file is lower than the target time for one segment, so Phex downloads the file in two segments: the first 16kBit + the rest of the file). The parameter is simply the length of the upload queue.

The shorter the upload queue, the closer the real queuing is to a FIFO, since a short queue will fill up with big files for which the wait time is more important than the file size (since their difference in filesize isn't that big). As soon as one big file gets an upload slot, smaller files can get in, until another big file enters the queue.

Note: To prevent far too high wait times for large files, this algorithm depends on a short upload queue (for example the current default length of 10). If a far longer upload queue should be desired at some time, it should be implemented as additional FIFO queue before the short Hrrn queue, with the Hrrn queue ensuring a faster change rate for that queue (because small files are served first in the Hrrn queue, the chance to have all upload slots blocked by big files is far lower). Currently a longer upload queue isn't needed, though, because the mean uptime of clients is too low to allow a later entry in a very long queue to get to its front.

Also the Hrrn queuing reduces the need for a longer queue, since it increases the rate with which slots get freed (because statistically a smaller fraction of the queue is taken up by small files at any given time).

images

For the images look at the attachments:

1 - Wait times overally.

2 - Wait times for small files with the transfer time as errorbar.

3 - Wait times for all file sizes again, but now with the transfer time as errorbar, too.

(the images are in the next message - seems I shouldn't edit a message with attachments if I want the thumbnails to show)

arne_bab · #2 (**permalink**) March 28th, 2009

the graph images

arne_bab · #3 (**permalink**) April 5th, 2009

I now did an additional test with continuous filesize ranges.

The result is similar to the previous one, but I think I found a cleaner way for displaying it

Just read the attached graphs (and mind the x-axis. It shows the filesize)

arne_bab · #4 (**permalink**) July 30th, 2009

Do the results warrant adding the HRRN upload scheduler for real usage?