Scaleable channel scheduler system and method

• US 20070070895A1
• Filed: 09/26/2005
• Published: 03/29/2007
• Est. Priority Date: 09/26/2005
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Narvaez, Paolo
• Application Number:
  US11/236,324
• Publication Number:
  US 20070070895A1
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/623 Weighted service order

Abstract

A data flow egress scheduler and shaper provides multiple levels of scheduling for data packets exiting communications devices. A classifier separates data from multiple sources by data flow and by priority within a data flow. An output controller requests a data packet for transmission and the scheduler selects a next available highest priority packet from a next in sequence data flow or from a management data queue. The shaper can control the rates of classes of service to be scheduled by the device. The scheduler typically comprises three levels of scheduling. Large numbers of output ports can be implemented in a single device by a virtual scheduler that services each data flow, output port and data source as a shared component, maintain context for groups of schedulers and data flows.

Claims

1. A method for scheduling data flows comprising the steps of:

sequencing data packets within a plurality of data flows according to a first characteristic to provide corresponding sequenced data flows;

selecting a next-in-sequence data flow to identify a transmittable data packet, wherein the next-in-sequence data flow is selected from the sequenced data flows according to a second characteristic; and

scheduling the transmittable data packet.

2. The method of claim 1 wherein the first characteristic is a strict priority scheduler.

3. The method of claim 1 wherein the first characteristic is a round robin scheduler.

4. The method of claim 1 wherein the second characteristic is a strict priority scheduler.

5. The method of claim 1 wherein the second characteristic is a round robin scheduler.

6. The method of claim 1 wherein the step of scheduling includes shaping transmitted data traffic for one or more selected ports and one or more classes of service.

7. The method of claim 1 wherein at least one of the first and second characteristics includes a weighted round robin scheduler for ordering data packets based in part on weighting factors associated with each of the data flows.

8. The method of claim 7 wherein the weighting factors are selected according to factors including a desired scheduling profile, system load and system configuration parameters.

9. The method of claim 7 wherein the weighting factors are associated with a scheduling context related to a predetermined configuration of network ports, scheduling classes and data flows.

10. The method of claim 6, and further comprising the step of computing a service quantum, wherein the service quantum is calculated based on the weighting factors and quantum scale factors associated with one or more network ports.

11. A virtual queuing system, comprising:

a priority-based scheduler;

a fairness-based scheduler; and

one or more state machines for executing the priority based scheduler and the round-robin scheduler, the one or more state machines being shared by a plurality of data flows,

wherein the priority-based scheduler and fairness-based scheduler are configured to sequence data packets for transmission from among a plurality of data flows, sequencing being based on a plurality of scheduling classes.

12. The system of claim 11 wherein the priority-based scheduler is for prioritizing data packets within a data flow and the fairness-based scheduler is for selecting one of the plurality of data flows to supply a data packet for transmission.

13. The system of claim 11 wherein the fairness-based scheduler is for prioritizing data packets within a data flow and the priority-based scheduler is for selecting one of the plurality of data flows to supply a data packet for transmission.

14. The system of claim 11 and further comprising an output scheduler for selecting between management data packets and data packets provided by a combination of fairness-based and priority-based schedulers.

15. The system of claim 11, wherein the state machine maintains information associated with one or more of the plurality of data flows, the information including location and status of queues, condition of deficit counters, available quanta and credits, priorities and service level selections.

16. The system of claim 11, and further comprising a shaper for regulating bandwidth allocation among the plurality of data flows.

17. The system of claim 16, wherein the one or more state machines is further for executing the shaper.

18. The system of claim 16, wherein the shaper maintains context associated with one or more network ports, one or more data flows and one or more scheduling classes.

19. The system of claim 16 wherein the shaper shapes using one or more token buckets.

20. A method for scheduling data flows comprising the steps of:

choosing a data flow from among a plurality of data flows to provide one or more data packets for transmission, wherein the chosen data flow is selected according to a first characteristic;

identifying a next data packet among the one or more data packets according to a second characteristic; and

controlling transmission of the next data packet,

wherein the first and second characteristics includes a strict priority scheduler and a round robin scheduler.