Scheduler for a packet routing and switching system

• US 7,158,528 B2
• Filed: 12/14/2001
• Issued: 01/02/2007
• Est. Priority Date: 12/15/2000
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Tota, Matthew, Li, Wei, Roper, Walter A., Dell, Martin S., Leshchuk, John
• Primary Examiner(s): Vu; Huy D.
• Assistant Examiner(s): NG, CHRISTINE Y
• Application Number:
  US10/017,503
• Publication Number:
  US 20020136230A1
• Time in Patent Office: 1,845 Days
• Field of Search: 370/230, 370/230.1, 370/235, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418
• US Class Current: 370/416
• 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/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

In one embodiment, queues associated with a first traffic class (FTC) are selected for service. Each FTC queue having at least one enqueued cell is identified as an occupied FTC queue, Where at least one FTC queue is provisioned for burst scheduling of multiple cells when serviced. An occupied FTC queue provisioned for burst scheduling is identified as a super-occupied FTC queue when the number of cells enqueued is greater than a specified number. Each occupied FTC queue is set as eligible for service based on a FTC scheduling algorithm. An eligible FTC queue is selected for service based on a corresponding sub-priority of each eligible FTC queue. Each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells. When the super-occupied queue is serviced, the number of cells dequeued is based on a burst size.

Claims

1. A method of selecting one of a plurality of queues for service, at least one of the plurality of queues associated with a first traffic class, the method comprising the steps of:

(a) identifying each first traffic class (FTC) queue having at least one enqueued cell as an occupied FTC queue wherein at least one FTC queue is provisioned for burst scheduling of multiple cells when serviced;

(b) identifying an occupied FTC queue provisioned for burst scheduling as a super-occupied FTC queue when the number of cells enqueued is greater than a specified number;

(c) setting as eligible for service each occupied FTC queue based on a FTC scheduling algorithm, wherein, for step (c), the FTC scheduling algorithm is a shaped virtual clock algorithm; and

(d) selecting for service an eligible FTC queue based on a corresponding sub-priority of each eligible FTC queue, wherein;

each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells;

when the super-occupied queue is serviced, the number of cells dequeued is based on a burst size; and

for step (c), each FTC queue has a corresponding down counter and service period value, wherein step (c) further comprises the steps of, during a scheduling interval, counting down from the service period value to a predefined value, and setting the corresponding FTC queue as eligible when the down counter reaches the predefined value.

2. The invention of claim 1, wherein, for step (a) the first traffic class comprises traffic having a provisioned guaranteed level of service.

3. The invention of claim 1, wherein step (a) comprises the steps of:

(a1) identifying whether a queue having cells associated with unicast traffic is occupied; and

(a2) identifying whether a queue having cells associated with multicast traffic is occupied.

4. The invention of claim 1, wherein step (c) further comprises the step of continuing to count from the predefined value to generate a service delay value, and for a subsequent scheduling interval adjusting the service period value based on the service delay value.

5. The invention of claim 1, wherein step (c) further comprises the step of further setting an occupied FTC queue as eligible based on congestion information.

6. The invention of claim 1, wherein step (d) comprises the step of, for each sub-priority, addressing with a pointer the FTC queue having the highest priority value within those eligible FTC queues assigned to the sub-priority, the sub-priority of an eligible FTC queue based on the order in which the eligible FTC queue is set as eligible.

7. The invention of claim 6, further comprising the steps of:

ranking each sub-priority, selecting the FTC queue within a sub-queue based on the pointer, and selecting for service the selected FTC queue from among the sub-queues based on the corresponding sub-queue'"'"'s rank.

8. The invention of claim 6, further comprising the steps of generating a bid when the FTC queue selector selects a given FTC queue for service, and servicing the given FTC queue when the bid is granted.

9. The invention of claim 1, wherein at least one of the plurality of queues is associated with a second traffic class (STC), step (a) further comprises the step of identifying each STC queue having at least one enqueued cell as an occupied STC queue, and the method further comprises the steps of:

(e) setting as eligible for service each occupied STC queue based on a STC scheduling algorithm;

(f) selecting for service an eligible STC queue based on the corresponding priority of the eligible STC queue; and

(g) selecting one of the FTC queue selected for service, if present, and the STC queue selected for service, if present.

10. The invention of claim 9, further comprising the steps of assigning each FTC queue priority over each STC queue, and selecting either the FTC queue or the STC queue based on the assigned priority.

11. The invention of claim 9, wherein, for step (e), the STC scheduling algorithm is a weighted round robin scheduling algorithm.

12. The invention of claim 9, wherein step (e) includes the step of accounting for delay in service of each eligible STC queue.

13. The invention of claim 9, for step (e), the second traffic class is best effort traffic.

14. The invention of claim 1, wherein the method is embodied as program steps in a processor of an integrated circuit.

15. The invention of claim 1, wherein more than one cell is dequeued from the super-occupied queue during a single selection of the super-occupied queue for service.

16. A scheduler for selecting one of a plurality of queues for service, at least one of the plurality of queues associated with a first traffic class (FTC), the scheduler comprising:

an occupancy processor configured to identify each FTC queue having at least one enqueued cell as an occupied FTC queue, wherein;

1) at least one FTC queue may be provisioned for burst scheduling of multiple cells when serviced, and

2) an occupied FTC queue provisioned for burst scheduling is also identified as a super-occupied FTC queue when a number of cells enqueued is greater than a provisioned number;

a FTC eligibility processor configured to set as eligible for service each occupied FTC queue based on a FTC scheduling algorithm, wherein the FTC scheduling algorithm is a shaped virtual clock algorithm; and

a FTC queue selector configured to select for service an eligible FTC queue,

wherein each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells, the FTC queue selector selects an eligible FTC queue based on the corresponding sub-priority of each eligible FTC queue, and when the super-occupied FTC queue is serviced, the number of cells dequeued is based on a burst size; and

wherein the FTC eligibility processor comprises a plurality of down counters, each FTC queue having a corresponding down counter and service period value, wherein during a scheduling interval each down counter counts from the service period value to a predefined value, and the corresponding FTC queue is set as eligible when the down counter reaches the predefined value.

17. The invention of claim 16, wherein the first traffic class comprises traffic having a provisioned guaranteed level of service.

18. The invention of claim 16, wherein the occupancy processor comprises:

a unicast occupancy processor configured to identify whether a queue having cells associated with unicast traffic is occupied; and

a multicast occupancy processor configured to identify whether a queue having cells associated with multicast traffic is occupied.

19. The invention of claim 16, wherein, the down counter continues to count from the predefined value to generate a service delay value, wherein for a subsequent scheduling interval the service period value is adjusted based on the service delay value.

20. The invention of claim 16, wherein the FTC eligibility processor receives output port congestion information, and the FTC eligibility processor sets an occupied FTC queue as eligible based on the congestion information.

21. The invention of claim 16, wherein, for each sub-priority, the FTC queue selector comprises a pointer addressing the FTC queue having the highest priority value within those eligible FTC queues assigned to the sub-priority, the priority of an eligible FTC queue based on the order in which the eligible FTC queue is set as eligible by the FTC eligibility processor.

22. The invention of claim 21, wherein each sub-priority is ranked, and the FTC queue selector selects the FTC queue within a sub-queue based on the pointer, and selects for service the selected FTC queue from among the sub-queues based on the corresponding sub-queue'"'"'s rank.

23. The invention of claim 21, wherein, when the FTC queue selector selects a given FTC queue for service, a bid is generated and the given FTC queue is serviced when the bid is granted.

24. The invention of claim 16, wherein at least one of the plurality of queues is associated with a second traffic class (STC), the occupancy processor is configured to identify each STC queue having at least one enqueued cell as an occupied STC queue, and the scheduler further comprises:

a STC eligibility processor configured to set as eligible for service each occupied STC queue based on a STC scheduling algorithm;

a STC queue selector configured to select for service an eligible STC queue based on the corresponding priority of the eligible STC queue; and

a scheduler/arbiter controller configured to select one of the FTC queue selected for service, if present, and the STC queue selected for service, if present.

25. The invention of claim 24, wherein the STC scheduling algorithm is a weighted round robin scheduling algorithm.

26. The invention of claim 16, wherein the scheduler is embodied in a telecommunications switch.

27. The invention of claim 26, wherein the telecommunications switch is a three stage switch, the plurality of queues are associated with connections received at a plurality of input ports of the first stage, and the scheduler is embodied in the first stage to transfer cells to a plurality of input links of the second stage.

28. The invention of claim 26, wherein the telecommunications switch is a three stage switch, the plurality of queues are associated with cells received from output links of the second stage, and the scheduler is embodied in the third stage to transfer cells from the plurality of queues to a plurality of output ports.

29. The invention of claim 16, wherein the scheduler is embodied in an integrated circuit.

30. The invention of claim 16, wherein more than one cell is dequeued from the super-occupied queue during a single selection of the super-occupied queue for service.

31. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method of selecting one of a plurality of queues for service, at least one of the plurality of queues associated with a first traffic class, the method comprising the steps of:

(a) identifying each first traffic class (FTC) queue having at least one enqueued cell as an occupied FTC queue wherein at least one FTC queue is provisioned for burst scheduling of multiple cells when serviced;

(b) identifying an occupied FTC queue provisioned for burst scheduling as a super-occupied FTC queue when the number of cells enqueued is greater than a specified number;

(c) setting as eligible for service each occupied FTC queue based on a FTC scheduling algorithm, wherein, for step (c), the FTC scheduling algorithm is a shaped virtual clock algorithm; and

(d) selecting for service an eligible FTC queue based on a corresponding sub-priority of each eligible FTC queue, wherein;

each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells;

when the super-occupied queue is serviced, the number of cells dequeued is based on a burst size; and

for step (c), each FTC queue has a corresponding down counter and service period value, wherein step (c) further comprises the steps of, during a scheduling interval, counting down from the service period value to a predefined value, and setting the corresponding FTC queue as eligible when the down counter reaches the predefined value.

32. A method of selecting one of a plurality of queues for service, at least one of the plurality of queues associated with a first traffic class, the method comprising the steps of:

(a) identifying each first traffic class (FTC) queue having at least one enqueued cell as an occupied FTC queue wherein at least one FTC queue is provisioned for burst scheduling of multiple cells when serviced;

(b) identifying an occupied FTC queue provisioned for burst scheduling as a super-occupied FTC queue when the number of cells enqueued is greater than a specified number;

(c) setting as eligible for service each occupied FTC queue based on a FTC scheduling algorithm; and

(d) selecting for service an eligible FTC queue based on a corresponding sub-priority of each eligible FTC queue, wherein;

each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells;

when the super-occupied queue is serviced, the number of cells dequeued is based on a burst size; and

step (d) comprises the step of, for each sub-priority, addressing with a pointer the FTC queue having the highest priority value within those eligible FTC queues assigned to the sub-priority, the sub-priority of an eligible FTC queue based on the order in which the eligible FTC queue is set as eligible.

33. The invention of claim 32, further comprising the steps of:

ranking each sub-priority, selecting the FTC queue within a sub-queue based on the pointer, and selecting for service the selected FTC queue from among the sub-queues based on the corresponding sub-queue'"'"'s rank.

34. The invention of claim 32, further comprising the steps of generating a bid when the FTC queue selector selects a given FTC queue for service, and servicing the given FTC queue when the bid is granted.

35. A scheduler for selecting one of a plurality of queues for service, at least one of the plurality of queues associated with a first traffic class (FTC), the scheduler comprising:

an occupancy processor configured to identify each FTC queue having at least one enqueued cell as an occupied FTC queue, wherein;

1) at least one FTC queue may be provisioned for burst scheduling of multiple cells when serviced, and

2) an occupied FTC queue provisioned for burst scheduling is also identified as a super-occupied FTC queue when a number of cells enqueued is greater than a provisioned number;

a FTC eligibility processor configured to set as eligible for service each occupied FTC queue based on a FTC scheduling algorithm; and

a FTC queue selector configured to select for service an eligible FTC queue, wherein;

each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells;

the FTC queue selector selects an eligible FTC queue based on the corresponding sub-priority of each eligible FTC queue;

when the super-occupied FTC queue is serviced, the number of cells dequeued is based on a burst size; and

for each sub-priority, the FTC queue selector comprises a pointer addressing the FTC queue having the highest priority value within those eligible FTC queues assigned to the sub-priority, the priority of an eligible FTC queue based on the order in which the eligible FTC queue is set as eligible by the FTC eligibility processor.

36. The invention of claim 35, wherein each sub-priority is ranked, and the FTC queue selector selects the FTC queue within a sub-queue based on the pointer, and selects for service the selected FTC queue from among the sub-queues based on the corresponding sub-queue'"'"'s rank.

37. The invention of claim 35, wherein, when the FTC queue selector selects a given FTC queue for service, a bid is generated and the given FTC queue is serviced when the bid is granted.

38. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method of selecting one of a plurality of queues for service, at least one of the plurality of queues associated with a first traffic class, the method comprising the steps of:

(a) identifying each first traffic class (FTC) queue having at least one enqueued cell as an occupied FTC queue wherein at least one FTC queue is provisioned for burst scheduling of multiple cells when serviced;

(b) identifying an occupied FTC queue provisioned for burst scheduling as a super-occupied FTC queue when the number of cells enqueued is greater than a specified number;

(c) setting as eligible for service each occupied FTC queue based on a FTC scheduling algorithm; and

(d) selecting for service an eligible FTC queue based on a corresponding sub-priority of each eligible FTC queue, wherein;

each FTC queue is assigned a sub-priority based on a service level of a connection associated with enqueued cells;

when the super-occupied queue is serviced, the number of cells dequeued is based on a burst size; and

step (d) comprises the step of, for each sub-priority, addressing with a pointer the FTC queue having the highest priority value within those eligible FTC queues assigned to the sub-priority, the sub-priority of an eligible FTC queue based on the order in which the eligible FTC queue is set as eligible.

39. The invention of claim 38, further comprising the steps of:

ranking each sub-priority, selecting the FTC queue within a sub-queue based on the pointer, and selecting for service the selected FTC queue from among the sub-queues based on the corresponding sub-queue'"'"'s rank.

40. The invention of claim 38, further comprising the steps of generating a bid when the FTC queue selector selects a given FTC queue for service, and servicing the given FTC queue when the bid is granted.