Queue scheduling with priority and weight sharing
View Patent ↗A Balanced Packet Transmit Opportunity (BPTO) mechanism allows balanced bandwidth traffic to be serviced while still maintaining the service levels desired for high priority traffic. The above embodiment achieved the result by distinguishing both queue types and slot style types, and performing selections differently depending upon the relative styles of the queues and slots. This arrangement provides a number of advantages. Because the selection method is fast and relatively simple to implement, a large number of queues may be integrated into the decision process while maintaining a desired output bandwidth. In addition, the selection process provides a flexibility, allowing multiple traffic shaping considerations to be modified during operations to support changing network requirements. In addition, the selection process provides a flexibility, allowing multiple traffic shaping considerations to be modified during operations to support changing network requirements.
1. A method for selecting one of a plurality of data sources as a source of data, wherein the data sources are apportioned into a first types of data source and a second type of data source, the method comprising the steps of:
providing a plurality of vectors, each vector associated with one of the plurality of data sources, each vector comprising a series of N bits, where each bit corresponds to one of N time slots, each bit representing whether the associated one of the plurality of data sources is assigned to the corresponding time slot;
determining, for each time slot, a slot style of the time slot; and
selecting, at each time slot, one of the plurality of data sources as the source of data, the step of selecting operating in response to the slot style of the time slot and the plurality of vectors, wherein the step of selecting further operates in response to whether an assigned data source is ready.
2. The method according to claim 1 , wherein the step of selecting further operates in response to a value of each bit associated with the time slot from each vector of the plurality of vectors.
3. The method according to claim 1 , wherein the first type of data source is a priority queue, and wherein the step of selecting selects a highest priority queue that is assigned to the time slot and is ready.
4. The method according to claim 3 , wherein the second type of data source is a balanced bandwidth queue, a subset of the plurality of data sources are balanced bandwidth queues, and at least one of the balanced bandwidth queues is assigned to the time slot, wherein the step of selecting selects the balanced bandwidth queue if the balanced bandwidth queue is ready and if no assigned priority queue is ready.
5. The method according to claim 4 , wherein a Some Balanced Bandwidth queue indicator is provided to indicate whether one of the plurality of data sources.
6. The method according to claim 5 , further comprising the step of advancing the time slot responsive to no assigned priority queue being ready, the assigned balanced bandwidth queue not being ready and the Some Balanced Bandwidth queue indicator being set.
7. The method according to claim 1 , further comprising a third type of data source, wherein the third type of data source is a best effort queue, and wherein the step of selecting selects a best effort queue as the source of data for a time slot when none of the plurality of data queues assigned to the time slot are of the first data type or the second data type.
8. A queueing system comprising:
a plurality of queues, each queue having a type associated therewith;
a selector, coupled to the plurality of queues, the selector for selecting one of the plurality of queues to provide data to an output, the selector comprising a control structure including a plurality of vectors, each vector associated with one of the plurality of queues and comprising a number of bits corresponding to a number of time slots, wherein each of the time slots has a type associated therewith, wherein a set of the plurality of queues are assigned to each of the time slots, and wherein the selector selects, in response to whether a queue is ready, one of the plurality of queues to provide an output for each time slot based on the type of the each time slot, bit values in the plurality of vectors and the type of the queue.
9. The queuing system of claim 8 , further comprising a rate limiter disposed between the plurality of queues and the selector.
10. The queueing system of claim 8 , wherein the plurality of queues comprises a plurality of priority queues and a plurality of balanced bandwidth queues, wherein the selector further comprises an indictor for indicating that at least one of the plurality of the balanced bandwidth queues is ready to transmit data.
11. The queueing system of claim 10 , wherein the selector operates to select a priority queue if the priority queue is ready and assigned.
12. The queueing system of claim 11 , wherein the selector operates to select a priority queue if the priority queue is ready but not assigned, and the associated time slot stype is a priority time slot type.
13. The queueing system of claim 11 , wherein the selector operates to select a balanced bandwidth queue if the assigned priority queue is not ready, and the balanced bandwidth queue is assigned and ready.
14. The queueing system of claim 13 , wherein the selector operates to advance the time slot if the assigned priority queue is not ready, and the balanced bandwidth queue is assigned but not ready, and the indicator is set to indicate that at least one of the plurality of balanced bandwidth queues is ready.
15. A network line card comprising:
an ingress data path for forwarding a packet from a device to a fabric;
an egress data path for forwarding a packet from a fabric to a device, the egress data path comprising a queueing system, the queueing system comprising:
a plurality of queues, each queue having a type associated therewith;
a selector, coupled to the plurality of queues, the selector for selecting one of the plurality of queues to provide data to an output, the selector comprising a control structure including a plurality of vectors, each vector associated with one of the plurality of queues and comprising a number of bits corresponding to a number of time slots for indicating an availability of the time slot to the associated queue, wherein each of the time slots has a type associated therewith, wherein a set of the plurality of queues are assigned to each of the time slots, and wherein the selector selects, in response to whether a queue is ready, one of the plurality of queues to provide an output for each time slot based on the type of the each time slot, bit values for the each time slot in the plurality of vectors and the type of the queue.
16. The network line card of claim 15 , wherein the queueing system further comprises a rate limiter disposed between the plurality of queues and the selector.
17. The network line card of claim 15 , wherein the plurality of queues comprises a plurality of priority queues and a plurality of balanced bandwidth queues, wherein the selector further comprises an indictor for indicating that at least one of the plurality of the balanced bandwidth queues is ready to transmit data.
18. The network line card of claim 17 , wherein the selector operates to select a priority queue if the priority queue is ready and assigned.
19. The network line card of claim 17 , wherein the selector operates to select a priority queue if the priority queue is ready but not assigned, and the associated time slot stype is a priority time slot type.
20. The network line card of claim 19 , wherein the selector operates to select a balanced bandwidth queue if the assigned priority queue is not ready, and the balanced bandwidth queue is assigned and ready.
21. The network line card of claim 20 , wherein the selector operates to advance the time slot if the assigned priority queue is not ready, and the balanced bandwidth queue is assigned but not ready, and the indicator is set to indicate that at least one of the plurality of balanced bandwidth queues is ready.