Queues
From MLDonkey
Contents |
[edit] Intro
A queue is an ordered list of tasks to be performed. The most usual queue is FIFO (first in, first out).
In the edonkey network, queues are used when there is no free slots. eMule has a queue based on credits rather than time. (Time affects credits though. See eMuleCreditSystem.) MLdonkey currently has no queue.
There has been much discussion about queues, especially long ones. This is an attempt to summarize the relevant arguments.
[edit] Variants
- No Queue: No queue at all
- Pool: a random queue, an (unordered) list of tasks
- \"Normal\" queue: a FIFO-queue
[edit] No Queue
- random selection
- change in demand affects distribution of uploadslots instantly
MLdonkey currently has no queue. This results in random selection when a slot frees up (the first one to ask gets it). Best chance of downloading is achieved by trying to connect as often as possible (without getting banned).
[edit] Pools
- random selection
- change in demand affects distribution of uploadslots instantly
- keeps track of users, making hammering pointless
- allows prioritizing
No known implementation. Pools keeps a list of users wanting a file. The next one to get a slot is chosen randomly from the list. Thanks to the list of clients hammering becomes pointless. As clients already are known (in the list) bandwidth could possibly be saved in communication. The list also allows prioritizing of different kinds to be made (e.g. for rare files). (With random one can use probability.)
[edit] FIFO Queues
- ordered selection, the waiting longest client gets the next slot
- change in demand affects distribution of uploadslots after a queuecycle
- keeps track of users, making hammering pointless
- allows prioritizing
- lower standard variation than random (higher predictability)
Implemented by the original client. eMule has a similar system. Queues are actually a subset of Pools (where time is prioritized). Has the same benefits as Pools conserning the list. Has different properties concerning selection though as more time waiting means higher probability of getting chosen next.
[edit] Conclusion
[edit] No Queue vs Pool
The only thing in favor of no queue that I can think of is simplicity and memory and/or cpu usage.
[edit] Pools vs Queues
In a closed network, sum(amount of upload) = sum(amount of download). Therefore the all over the network average download time will be the same for all implementations*, which have an equal overhead. I.e. what can be changed is overhead, spreading rate and standard variation.
[edit] Predictability
Standard variation is much lower with queues, and this increases predictability. This should be possible to use to reduce overhead. (E.g. ask more seldom when far back in queue.) Actually the low predictability with random could lead to wasted bandwidth when the next client chosen is not prepared to recieve data. To counter this I suggest a very small queue just before serving. Another issue with low predictability is that it's very hard to accurately calculate an ETA. What I suggest here is to use the fact that average download time is equal and calculate an estimation, based on the time it would have taken with a queue.
_On the other hand, if anything goes wrong while you're being queued (some router goes down, whatever), you may lose your hard earned rank. With random pools, you simply have the same probability of being selected when you come back. It is less \"fragile\", and gives users more peace of mind. And don't over estimate the need of predictability. Random events become predictable when they're in large quantities (so it only matters for rare files), and remember that many people play luck games for fun and entertainment ;)_
_Yes. The counteraction of queues requires storing of all seen hosts' waitingtime, along with a way to identify old users. More complex and requires more memory (although it can be stored on hd)._
[edit] Flexibility
Because queues prioritize old requests flexibility is reduced. If changes in demand occur this is does not affect queues until a queuecycle has passed. A change can be e.g. a chunk in a new file being shared (demand jumps from 0). With random the new chunk may be downloaded instantly. Here the higher standard variation is positive. It leads to a more uniform distribution of upload (among files) over time. This also applies for shorter sessions, as you continously have a chance of getting the file. Note that the spreading effect mostly affect small and new files. This is due to the fact that you can queue for any chunk of a file you want (since you decide when it's time to download). A way of reducing the bad effect of queues on short session is to store total waitingtime, even inbetween sessions. (This of course only works when connecting to the same client.)
So finally, I'd say pools win over queues on flexibility.
_--I favor pools over queues (because of the superiour flexibility) and my arguing may be biased by that. Feel free to defend queues if you have any good arguments. /Vaste_
