Conventional scheduling and routing systems employ Weighted Fair Queuing (WFQ) and Generalized Processor Sharing (GPS). These conventional techniques are typically used in packet routing systems, and assume there is some notion of fixed work per packet and therefore a quantifiable measure of rounds and work needed per round. Other conventional systems can involve simple FIFO-based structures that use a Round-Robin scheduler across multiple FIFO queues (1 for each user).
Weighted Fair Queuing (WFQ) can be seen as a combination of priority queuing and fair queuing involving multiple queues. In WFQ, all queues are serviced so that none are starved, but some queues are serviced more than others. A weight is applied to the queues to give some queues a higher priority. For example, one queue may get half the available bandwidth and other queues will get an allocation of the remaining bandwidth. Traffic may be prioritized according to packet markings, source and destination IP address fields, and port numbers. WFQ weights traffic so that low-bandwidth traffic gets a fair level of priority. If high-priority queues are not in use, then lower-priority traffic uses its queues.
Such conventional systems suffer from the shortcoming of not providing fairness for the scheduling of tasks submitted from a large number of simultaneous users, where such tasks cannot be divided up into smaller tasks or time-shifted. Also, iterating over multiple queues, which is required to manage all users, adds a burdensome layer of complication as to managing keys to compute priority metrics.