Back to results
US 7,461,159 B2Granted
Weighted fair queuing scheduler
AssigneeBeckett Mining LLC
InventorsHaitham F. Tayyar, Hussein Alnuweiri
Life of this patent
Estimating the term…
Abstract
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).
Claims52
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.
6 more elements
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.
7 more elements
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.
7 more elements
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.
8 more elements
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.
4 more elements
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.
5 more elements
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.
6 more elements
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.
3 more elements
Dependencies are inferred from the claim text.