Weighted fair queuing scheduler
View Patent ↗A scheduler which uses a GPS simulation to determine an order in which to service entities uses a novel dynamic data structure with a sophisticated, but simple, pointer update mechanism. Preferred embodiments of the scheduler perform a fixed amount of work per scheduling event. A scheduling event can be either computing a new virtual finish timestamp upon a new arrival to the scheduler, or determining which entities are to leave the GPS system because their finish timestamp has expired. The scheduler may be used in packet scheduling in a packet handling device, such as a router, scheduling access of software processes to a computer processor or the like. The scheduler may implement weighted fair queuing (WFQ).
1. A method for scheduling entities in a system, comprising:
receiving, at a scheduler, entities to be scheduled, an entity being associated with one of a plurality of sessions, a session comprising a share;
associating a timestamp with each entity based at least in part upon a virtual time;
determining a backlog rate representing a sum of shares for backlogged sessions, wherein determining said backlog rate comprises:
associating a share sum and a next sum with the timestamp, the share sum representing a sum of shares for sessions for entities associated with the timestamp, and the next sum representing a sum of shares for sessions for an entity comprising the timestamp and at least one other entity associated with another timestamp that is greater than the timestamp; and
determining said backlog rate representing said sum of shares for backlogged sessions based on the share sum and the next sum;
maintaining the virtual time based at least in part upon the backlog rate; and
computing timestamps for subsequently received entities based at least in part upon the virtual time.
2. The method according to claim 1 , wherein a timestamp record is associated with a linked list of records corresponding at least in part to packets comprising the timestamp associated with the timestamp record.
3. The method according to claim 1 , wherein maintaining the backlog rate comprises:
adding to the backlog rate the next sum; and
subtracting from the backlog rate the share sum.
4. The method according to claim 1 , wherein maintaining the backlog rate is performed if the timestamp equals a current virtual time.
5. The method according to claim 1 , further comprising:
maintaining a timestamp priority queue data structure comprising a timestamp record associated with the timestamp; and
associating the share sum and the next sum with the timestamp record.
6. The method according to claim 5 , wherein the priority queue data structure comprises a balanced heap.
7. The method according to claim 5 , wherein the priority queue data structure comprises a calendar queue.
8. The method according to claim 5 , wherein the priority queue data structure comprises a hardware priority queue.
9. The method according to claim 8 , further comprising dispatching the entities in order of their respective timestamps.
10. The method according to claim 9 , further comprising:
maintaining an eligible group of entities satisfying an eligibility criterion; and
dispatching the eligible group of entities.
11. The method according to claim 10 , further comprising:
computing a virtual start time for the entities, wherein the virtual start time is not earlier than a current virtual time; and
including the virtual start time in the eligible group of entities.
12. The method according to claim 11 , wherein the entities comprise packets to be dispatched on a communication Link,
the method further comprising dispatching the packets in order of the respective time stamps associated with the packets.
13. The method according to claim 11 , wherein the entities comprise processes to be executed on a processor, and the method further comprises executing the processes in order of their timestamps.
14. The method according to claim 1 , further comprising dispatching the entities in order of their associated timestamps.
15. The method according to claim 1 , wherein the entities comprise packets to be dispatched on a communication link,
the method further comprising dispatching the packets in order of time stamps associated with the packets.
16. The method according to claim 1 , wherein the entities comprise processes to be executed on a processor,
the method further comprising executing the processes in order of time stamps associated with the processes.
17. The method according to claim 1 , wherein the virtual time is computed substantially according to:
VT=VT init +[Time−t init ]/backlog rate
wherein VT comprises the virtual time, VT init comprises an initial virtual time, Time comprises a system time and t init comprises an initial system time.
18. The method according to claim 1 , further comprising:
creating a record for the entities in a priority queue data structure, and
organizing the record in the priority queue data structure by timestamp value.
19. The method according to claim 1 , further comprising keeping a record of the timestamps in sorted order.
20. The method according to claim 1 , wherein the virtual time comprises a function comprising a slope that is inversely proportional to the backlog rate.
21. The method according to claim 1 , further comprising computing the virtual dine for a newly backlogged session, and for an entity that departs from Generalized Processor Sharing.
22. The method according to claim 1 , further comprising:
maintaining a system time value;
computing a finish time for a minimum assigned timestamp; and
departing each entity associated with the timestamp from Generalized Processor Sharing for a finish time that is not less than the system time value.
23. An article comprising: a computer readable medium having stored thereon instructions that, if executed, result in:
receiving, at a scheduler, entities to be scheduled, an entity being associated with one of a plurality of sessions, a session comprising a share;
associating a timestamp with each entity based at least in part upon a virtual time;
determining a backlog rate representing a sum of shares for backlogged session, wherein determining the backlog rate comprises:
associating a share sum and a next sum with the timestamp, the share sum representing a sum of shares for sessions for entities associated with the timestamp and the next sum representing a sum of shares for sessions for an entity comprising the timestamp and at least one other entity associated with another timestamp that is greater than the timestamp; and
determining the backlog rate based on the share sum and the next sum;
maintaining the virtual time based at least in part upon the backlog rate; and
computing timestamps for subsequently received entities based at least in part upon the virtual time.
24. An article according to claim 23 , wherein a timestamp record is associated with a linked list of records corresponding at least in part to packets comprising the timestamp associated with the timestamp record.
25. An article according to claim 23 , wherein maintaining the backlog rate comprises:
adding to the backlog rate the next sum; and
subtracting from the backlog rate the share sum.
26. An article according to claim 23 , wherein maintaining the backlog rate is performed if the timestamp equals a current virtual time.
27. An article according to claim 23 , further comprising:
maintaining a timestamp priority queue data structure comprising a timestamp record associated with the timestamp; and
associating the share sum and the next sum with the timestamp record.
28. An article according to claim 27 , wherein the priority queue data structure comprises a balanced heap.
29. An article according to claim 27 , wherein the priority queue data structure comprises a calendar queue.
30. An article according to claim 27 , wherein the priority queue data structure comprises a hardware priority queue.
31. An article according to claim 30 , further comprising dispatching the entities in order of their respective timestamps.
32. An article according to claim 31 , further comprising:
maintaining an eligible group of entities satisfying an eligibility criterion; and
dispatching the eligible group of entities.
33. An article according to claim 31 , further comprising:
computing a virtual start time for the entities, wherein the virtual start time is not earlier than a current virtual time; and
including the virtual start time in the eligible group of entities.
34. An article according to claim 33 , wherein the entities comprise packets to be dispatched on a communication link,
the method further comprising dispatching the packets in order of time stamps associated with the packets.
35. An article according to claim 33 , wherein the entities comprise processes to be executed on a processor, and the method further comprises executing the processes in order of their timestamps.
36. An article according to claim 23 , further comprising dispatching the entities in order of their associated timestamps.
37. An article according to claim 23 , wherein the entities comprise packets to be dispatched on a communication link,
the method further comprising dispatching the packets in order of time stamps associated with the packets.
38. An article according to claim 23 , wherein the entities comprise processes to be executed on a processor,
the method further comprising executing the processes in order of time stamps associated with the processes.
39. An article according to claim 23 , wherein the virtual time is computed substantially according to:
VT=VT init +[Time−t init ]/backlog rate
wherein VT comprises the virtual time, V init comprises an initial virtual time, Time comprises a system time and t init comprises an initial system time.
40. An article according to claim 23 , further comprising:
creating a record for the entities in a priority queue data structure, and
organizing records in the priority queue data structure by timestamp value.
41. An article according to claim 23 , further comprising keeping a record of timestamps in sorted order.
42. An article according to claim 23 , wherein the virtual time comprises a function comprising a slope that is inversely proportional to the backlog rate.
43. An article according to claim 23 , further comprising computing the virtual time for a newly backlogged session, and for an entity that departs from Generalized Processor Sharing.
44. An article according to claim 23 , further comprising:
maintaining a system time value;
computing a finish time for a minimum assigned timestamp; and
departing each entity associated with the timestamp from Generalized Processor Sharing for a finish time that is not less than the system time value.
45. A method, comprising:
receiving a packet to be dispatched on a communication link, the packet being associated with a session comprising a share;
computing a virtual time based at least in part upon a backlog rate representing a sum of shares for backlogged sessions,
assigning a timestamp to the packet based at least in part upon the virtual time;
inserting a record for the packet into a priority queue data structure sorted by timestamp, the priority queue data structure comprising a share sum and a next sum for each timestamp in the priority queue data structure, the share sum representing a sum of shares for entities associated with the timestamp, and the next sum representing a sum of shares for entities associated with the timestamp and at least one entity associated with a second timestamp that is greater than the timestamp;
determining a minimum timestamp in the priority queue data structure;
determining a finish time for the minimum timestamp;
deeming packets associated the minimum timestamp to be finished if the virtual time exceeds the finish time;
updating the backlog rate based at least in part upon the share sum and the next sum for the minimum timestamp; and
dispatching on the communication link packets deemed to be finished in order of their respective timestamps.
46. The method according to claim 45 , further comprising assigning the timestamp to the packet based at least in part upon a previous timestamp of a previous packet that was backlogged immediately prior to receipt of the packet.
47. An article comprising: a computer readable medium having stored thereon instructions that, if executed, result in:
receiving a packet to be dispatched on a communication link, the packet being associated with a session comprising a share;
computing a virtual time based at least in part upon a backlog rate representing a sum of shares for backlogged sessions,
assigning a timestamp to the packet based at least in part upon the virtual time;
inserting a record for the packet into a priority queue data structure sorted by timestamp, the priority queue data structure comprising a share sum and a next sum for each timestamp in the priority queue data structure, the share sum representing a sum of shares for entities associated with the timestamp, and the next sum representing a sum of shares for entities associated with the timestamp and at least one entity associated with a second timestamp that is greater than the timestamp;
determining a minimum timestamp in the priority queue data structure;
determining a finish time for the minimum timestamp;
deeming packets associated the minimum timestamp to be finished if the virtual time exceeds the finish time;
updating the backlog rate based at least in part upon the share sum and the next sum for the minimum timestamp; and
dispatching on the communication link packets deemed to be finished in order of their respective timestamps.
48. An article according to claim 47 , further comprising assigning the timestamp to the packet based at least in part upon a previous timestamp of a previous packet in the session.
49. An apparatus for bandwidth management and traffic prioritization in a network of devices, the apparatus having a processor and comprising:
means for receiving, at a network device, a packet to be scheduled, wherein the packet is associated with one of a plurality of sessions, a session comprising a share;
means for maintaining a record of a backlog rate representing a sum of shares for sessions that are backlogged based at least in part upon a share sum and a next sum associated with a timestamp, the share sum for the timestamp representing a sum of shares for entities associated with the timestamp, and the next sum for the timestamp representing a sum of shares for entities associated with the timestamp and at least one other entity associated with a second timestamp that is greater than the timestamp;
means for updating the record of the backlog rate for the packet, wherein the packet is received or dispatched;
means for associating, based at least in part upon the backlog rate, the timestamp to the packet, wherein the packet arrives at an idle session;
means for maintaining for the timestamp the share sum and the next sum; and
means for dispatching the packet in order based on the timestamp.
50. An article comprising: a computer readable medium having stored thereon instructions that, if executed, result in:
receiving, at a network device, packets to be scheduled, wherein each of the packets is associated with one of a plurality of sessions, a session comprising a share;
maintaining a record of a backlog rate representing a sum of shares for sessions that are backlogged based at least in part upon share sums and next sums associated with each timestamp, the share rate sum representing a sum of shares for entities associated with the timestamp, and the next sum representing a sum of shares for entities associated with the timestamp and at least one other entity associated with a second timestamp that is greater than the timestamp;
updating the record of the backlog rate for a packet that is one of received and dispatched;
associating, based at least in part upon the backlog rate, a timestamp to the packet, wherein the packet arrives at a session that was idle immediately prior to the arrival of the packet;
maintaining for the timestamp a share sum and a next sum; and
dispatching the packets in order of their timestamps.
51. Apparatus for scheduling entities, the apparatus having a processor and comprising:
means for assigning timestamps to newly received entities based at least in part upon a state of a set of Generalized Processor Sharing queues and a virtual time, the set of Generalized Processor Sharing queues comprising records of timestamps associated with entities that are associated with one of a plurality of sessions, wherein each of the sessions comprises a share;
means for holding a value representing a backlog rate representing a sum of shares for those of the sessions that are backlogged in the Generalized Processor Sharing queues;
a priority queue data structure comprising a record for a unique timestamp in the Generalized Processor Sharing queues, the record comprising:
a share sum representing a sum of shares for sessions that comprise entities comprising the unique timestamp; and
a next sum representing a sum of shares for those of the sessions that comprise: an entity comprising the unique timestamp and at least one other entity comprising a second timestamp greater than the unique timestamp; and
means for dispatching packets in order of their timestamps.
52. Packet forwarding apparatus, the apparatus having a processor and comprising:
means for assigning timestamps to received packets;
a plurality of Generalized Processor Sharing session queues configured to receive packets comprising timestamps assigned by the means for assigning;
a priority queue data structure comprising a record of packets in the queues arranged in order of timestamp, the priority queue data structure comprising, for a unique timestamp in the Generalized Processor Sharing queues, a share sum representing a sum of shares for sessions corresponding at least in part to queues which comprise packets comprising the unique timestamp, and a next sum representing a sum of shares for those of the sessions corresponding at least in part to queues which comprise: a packet comprising the unique timestamp and at least one other packet comprising a second timestamp greater than the unique timestamp; and
means for inserting records for a newly arrived packet into appropriate ones of the Generalized Processor Sharing session queues and the priority queue data structure.