Upload queue idea: Candidate selection based on on the response ratio

Hi, 

I wrote this idea as proposal. 

Please tell me what you think about it. 

* Did I miss something? (advantagees, drawbacks, ...)

* Do you think it would be beneficial to Gnutella? 

* Is it something you would use in _your_ application, if you had free coding 
time right now (reserved for nothing else)? 

Best wishes, 
Arne


Selecting upload candidates based on their response ratio
=========================================================

Proposal
--------

To improve the experience for downloaders of small files, I propose to change 
the upload queue from a simple FIFO to a "highest response ration next" queue. 

- http://en.wikipedia.org/wiki/Highest_response_ratio_next

This changes the election parameter from "wait time" to "(wait time + 
estimated download time) / estimated download time", or 

priority = 1 + (wait time / estimated download time)

For same file size files nothing changes. 

For files with different file sizes, smaller files get selected a bit earlier, 
but no downloader will have to wait forever (big file downloads don't starve). 

The maximum wait time for any file is approximately the time needed to do the 
full transfer + the time till the next upload finishes. 

Since a Gnutella client normally has only about 100 clients in queue, a more 
expensive selection algorithm should prove useful. 

An example algorithm for sorting the downloaders would be: 

def sort(downloader_list): 
    tmp = [] # new list
    for request in downloader_list: 
	# first get the response_ration
	estimated_dl_time = request.size * upload_slots / upload_speed
	wait_time = current_time - request.arrival_time
	response_ration = 1 + wait_time / estimated_dl_time
	
	# now create a list entry. 
	tmp.append(response_ration, request)
    
    # sort the list by response ratio
    tmp.sort()
    # return only the downloaders, now sorted
    sorted_list = [request for ratio, request in tmp]
    return sorted_list

A selection strategy of a request for a free upload slot would be

def select(downloader_list): 
    sorted_list = sort(downloader_list)
    # return the 
    return sorted_list[-1]


This has one drawback: Users can see "someone just got put in front of me". 

But the FIFO strategy we currently have strongly favors big file downloads, 
while small files are for what people mostly use Gnutella, so using FIFO seems 
rather contraproductive. 

The proposed selection strategy has the advantage of making downloads of small 
files more efficient and removing the current unfairness without needing 
multiple queues. 

For example it becomes feasible to download a music file from a source which 
mostly serves videos. 

Also the queues will be less full, because small files leave them faster and 
the chance of having a few big downloads block all download slots is reduced, 
so the general "responsiveness" of Gnutella should increase. 

And I think these advantages outwheight the user interface disadvantage. 


Background calculations
-----------------------

The maximum wait time depends on the rate with which slots get available and 
the file_size. 

For a big download (video file) I estimate a size of about 200 times a small 
download (music file). 

When a slot gets free, a new request has wait time of the time needed till the 
next upload finishes, which should on average be half the transfer time of a 
small file. 

Assuming that an uploader always has at least one small file in an upload slot 
(since they are preferenced with this algorithm I feel I can take this 
assumtion), most small file requests will start with a priority of 1.5 which 
rises by 1 each time another process gets chosen (wait_time / 
estimated_dl_time). 

A big download will start with 1 + (1/2 * 1/200) = 1.0025
This ratio will rise by 0.005 per finished upload. 

So a big download will have to wait for at most 200 small file downloads till 
it starts. 

More generally speaking, the highest wait time for a big file download till it 
gets a slot is about the time it needs to complete once it has the slot. 



[Non-text portions of this message have been removed]