Slot allocation fairness
Moderator: Moderators
Slot allocation fairness
How does the slot allocation take place when a user tries to download a file but fails due to outage in upload slots? I guess allocation is done by a first come first served basis. Such random slot allocation algorithm is unfair to the downloaders. More reasonable would be that each request for a slot is given a ticket number valid for some amount of time and that requests are served in the order the tickets have been handed out. This would make sure that waiting for a slot will eventually give you a slot (which is fair to the downloaders). With random slot allocation this is not true, i.e., you could be left waiting forever and other downloaders that "arrived" after you get serviced before you.
Comments?
Comments?
-
- Forum Moderator
- Posts: 366
- Joined: 2004-03-06 02:46
Well, seeing as an upload queue is a rejected feature and it's always been this way, it's going to take a lot to get this done. The Law of Averages says that people who have been waiting for longer have more of a chance of getting a slot anyway, and if it's a file that's very rare, you can usually ask for a slot and get it.
One problem that I've noticed with asking for a slot is that people just aren't infront of their comps. Usually you leave the client on for long periods of time while being absent (which is of cause ok).
An outline of a fair slot allocation algoritm:
Each downloader with nick N connects at regular intervals with a period time of T to request a file. The client that share the file keeps a map M of where M(N) is a counter of how many times N has been denied a download slot.
When a download slot becomes available the client waits 2T and grants the slot to the client with the highest counter value.
N is removed from M if not asked for a slot during the last 2T period.
An outline of a fair slot allocation algoritm:
Each downloader with nick N connects at regular intervals with a period time of T to request a file. The client that share the file keeps a map M of where M(N) is a counter of how many times N has been denied a download slot.
When a download slot becomes available the client waits 2T and grants the slot to the client with the highest counter value.
N is removed from M if not asked for a slot during the last 2T period.
-
- Forum Moderator
- Posts: 366
- Joined: 2004-03-06 02:46
Well, even if they're not there when you ask, there's a very good chance they'll be back within 24 hours, and I have no problem waiting that long. The "I must have this right now" mentality works much better with programs like BitTorrent than it does with DC.
The major flaw with that algorithm is that slots will stay empty for a decent period of time, and with all the "slow download speed" people running around, that means that a decent percentage of the person's upload won't be being used. It's much, much better to have the uploader connect himself and give the downloader the chance to request the file right when the slot opens up than to wait for the downloader to connect.
The simplest way to do this, I think, is to make the downloading algorithm favor even distribution of slots among downloaders. Look for an upcoming post on this in the multisource downloading thread.
The major flaw with that algorithm is that slots will stay empty for a decent period of time, and with all the "slow download speed" people running around, that means that a decent percentage of the person's upload won't be being used. It's much, much better to have the uploader connect himself and give the downloader the chance to request the file right when the slot opens up than to wait for the downloader to connect.
The simplest way to do this, I think, is to make the downloading algorithm favor even distribution of slots among downloaders. Look for an upcoming post on this in the multisource downloading thread.
-
- DC++ Contributor
- Posts: 3212
- Joined: 2003-01-07 21:46
- Location: .pa.us
Yes, that's an upload queue. You may not have to wait 2T though, you can likely to a $RCTM to get the user to connect.Sarge wrote:Each downloader with nick N connects at regular intervals with a period time of T to request a file. The client that share the file keeps a map M of where M(N) is a counter of how many times N has been denied a download slot.
When a download slot becomes available the client waits 2T and grants the slot to the client with the highest counter value.
N is removed from M if not asked for a slot during the last 2T period.
And you're aware that some DC++ modified clients already have upload queues, correct?
Oh, and you have a big flaw - if a client hammers you in requesting a slot, they'll get the slot first, regardless of how long they've been waiting.
-
- Posts: 506
- Joined: 2003-01-03 07:33
Instead of keeping a count for each it easier to have a strict queue and the connection attempts are just used to notify that the client still want to stay in the queue. When a slot become available a $RCTM is sent to the first client in the queue.
I know there are clients out there that have an upload queue. But the mechanism only works if a majority of the clients implements an upload queue (and dc++ is in majority I think).
I know there are clients out there that have an upload queue. But the mechanism only works if a majority of the clients implements an upload queue (and dc++ is in majority I think).
-
- DC++ Contributor
- Posts: 3212
- Joined: 2003-01-07 21:46
- Location: .pa.us
About that... This is from the sticky in the Feature topic:Sarge wrote:But the mechanism only works if a majority of the clients implements an upload queue (and dc++ is in majority I think).
GargoyleMT wrote:It's also a good decision to check the Rejected Feature Tracker for features that, for one reason or another, have been explicitly rejected. Some of the more popular rejected suggestions:
[ 659382 ] Upload queue display