Slot allocation fairness

Technical discussion about the NMDC and <a href="http://dcpp.net/ADC.html">ADC</A> protocol. The NMDC protocol is documented in the <a href="http://dcpp.net/wiki/">Wiki</a>, so feel free to refer to it.

Moderator: Moderators

Locked
Sarge
Posts: 7
Joined: 2004-05-22 09:36

Slot allocation fairness

Post by Sarge » 2004-05-22 09:48

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?

PseudonympH
Forum Moderator
Posts: 366
Joined: 2004-03-06 02:46

Post by PseudonympH » 2004-05-22 11:47

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.

Sarge
Posts: 7
Joined: 2004-05-22 09:36

Post by Sarge » 2004-05-22 12:34

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.

PseudonympH
Forum Moderator
Posts: 366
Joined: 2004-03-06 02:46

Post by PseudonympH » 2004-05-22 13:39

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. :)

GargoyleMT
DC++ Contributor
Posts: 3212
Joined: 2003-01-07 21:46
Location: .pa.us

Post by GargoyleMT » 2004-05-23 07:32

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.
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.

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.

ivulfusbar
Posts: 506
Joined: 2003-01-03 07:33

Post by ivulfusbar » 2004-05-23 08:34

Not if it counts only one hit / timeinterval T garg. ;)) But you can have more fun with spoofing nicknames. ;))
Everyone is supposed to download from the hubs, - I don´t know why, but I never do anymore.

Sarge
Posts: 7
Joined: 2004-05-22 09:36

Post by Sarge » 2004-05-23 08:46

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).

GargoyleMT
DC++ Contributor
Posts: 3212
Joined: 2003-01-07 21:46
Location: .pa.us

Post by GargoyleMT » 2004-05-23 09:20

Sarge wrote:But the mechanism only works if a majority of the clients implements an upload queue (and dc++ is in majority I think).
About that... This is from the sticky in the Feature topic:
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

Sarge
Posts: 7
Joined: 2004-05-22 09:36

Post by Sarge » 2004-05-23 09:36

Yeah I saw that this was an already rejected feature request. But after I posted to thread.
Sorry about that.

I rest my case even if I think it would be good with some fairness in slot allocation.

Locked