Back to results
US 7,583,596 B1Granted
Priority scheduling using per-priority memory structures
AssigneeJuniper Networks, Inc.
InventorCraig R. Frink
Life of this patent
Estimating the term…
Abstract
A system schedules traffic flows on an output port using circular memory structures. The circular memory structures may include rate wheels that include a group of sequentially arranged slots. The traffic flows may be assigned to different rate wheels on a per-priority basis.
Claims26
A device comprising:
- a plurality of queues to store data traffic flows that are associated with different transmission priorities;
- a plurality of rate wheels assigned to the traffic flows on a per-priority basis, each of the rate wheels including a plurality of sequentially arranged slots used to schedule the assigned traffic flows;
- an output port coupled to the plurality of rate wheels, the output port receiving data of the traffic flows from the plurality of rate wheels;
- a priority decoder to monitor the slots on the plurality of rate wheels for collisions between rate wheels attempting to output data to the output port, and
- stop the output of data to the output port for those of the colliding rate wheels that are not a highest priority one of the colliding rate wheels;
- and
- counters associated with select ones of the plurality of rate wheels, the counters each storing an indication of a number of times the associated rate wheel was stopped.
4 more elements
A system comprising:
- an output port configured to transmit data from traffic flows that are each associated with a priority designation that designates a transmission priority;
- and
- a scheduling component including
- a plurality of circular memory structures used to schedule a plurality of traffic flows in sequential transmission slots included in each of the circular memory structures, the circular memory structures being assigned to the traffic flows on a per-priority basis,
- a priority decoder configured to, when multiple ones of the circular memory structures attempt to de-queue to the output port in a same time slot, freeze de-queuing those of the circular memory structures that do not correspond to a highest priority of the multiple ones of the circular memory structures, and
- a counter associated with each one of the plurality of circular memory structures, the counter each storing an indication of a number of times the associated circular memory structure was frozen.
3 more elements
A method, performed by a device, for de-queuing data units scheduled from a plurality of traffic flows that include different priority traffic flows, the method comprising:
- associating, by the device, one or more circular memory structures with each of the different priority traffic flows;
- de-queuing, by the device, a first data unit from a first of the circular memory structures associated with a first one of the different priority traffic flows to an output port when the priority of the traffic flow of the first circular memory structure is a highest priority of the circular memory structures attempting to de-queue to the output port;
- freezing, by the device, de-queuing of the first data unit from the first circular memory structure associated with the first one of the different priority traffic flows to the output port when the priority of the first one of the different priority traffic flows is not the highest priority of the circular memory structures attempting to de-queue;
- monitoring, by the device, the circular memory structures for collisions between the circular memory structures attempting to output data to the output port;
- transmitting, by the device, a freeze signal to those of the colliding circular memory structures that are not the highest priority of the colliding circular memory structures;
- storing, by the device, an indication of a number of times select ones of the circular memory structures are frozen;
- and
- increasing, by the device, a rate of scheduling data units on the select ones of the circular memory structures based on the stored indication.
5 more elements
A device for de-queuing data units scheduled from a plurality of traffic flows of different priority, the device comprising:
- means for scheduling each of the different priority traffic flows in different circular memory structures;
- means for transmitting the traffic flows on a physical link;
- means for de-queuing a first data unit from a first of the circular memory structures associated with a first one of the different priority traffic flows to the physical link when the priority associated with the traffic flows of the first circular memory structure is a highest priority of the circular memory structures attempting to de-queue to the output port;
- means for freezing de-queuing of the first data unit from the first of the circular memory structures to the physical link when the priority associated with the first circular memory structure is not the highest priority of the circular memory structures attempting to de-queue;
- means for monitoring the circular memory structures for collisions between the circular memory structures attempting to output data to the physical link;
- means for transmitting a freeze signal to those of the colliding circular memory structures that are not the highest priority of the colliding circular memory structures;
- means for storing an indication of a number of times select ones of the circular memory structures are frozen;
- and
- means for increasing a rate of scheduling data units on the select ones of the circular memory structures based on the stored indication.
6 more elements
Dependencies are inferred from the claim text.