Hierarchical packet scheduling method and apparatus

• US 5,850,399 A
• Filed: 03/27/1998
• Issued: 12/15/1998
• Est. Priority Date: 04/04/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Inventors: Yang, Tao, Ganmukhi, Mahesh N.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US09/049,511
• Time in Patent Office: 263 Days
• Field of Search: 370/411, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417-418, 370/428-429, 395/200.57, 395/200.58, 395/200.59
• US Class Current: 370/412
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of fairly and efficiently scheduling transmission of a packet from a plurality of sessions onto a network is presented. The method includes providing an input having a plurality of sessions, grouping the sessions into a plurality of classes, scheduling the classes with first level schedulers associated with one of the classes, scheduling the outputs of some of the first level schedulers with a second level scheduler, and prioritizing among the output of the remaining first level scheduler(s) and the output of the second level scheduler to provide an hierarchical scheduler output. The scheduler accepts traffic types at its input, and provides an output suitable for scheduling cell based traffic such as Asynchronous Transfer Mode (ATM) network traffic.

Claims

1. A method for scheduling packet transmission in a network communication device comprising the steps of:

receiving a plurality of packets, wherein each of said packets is associated with one of a plurality of classification types;

segregating said received packets into a plurality of sessions, each of said sessions having at least one of said plurality of classification types;

forwarding said packets for each of said plurality of sessions to inputs of a corresponding plurality of first level schedulers, each of said schedulers having said input for receiving packets within respective sessions and an output, and wherein each one of said schedulers employs one of a plurality of first level scheduling protocols;

receiving packets at inputs of a second level scheduler from the outputs of at least some of said plurality of first level schedulers, wherein said second level scheduler further includes an output and is operative in accordance with a second level scheduling protocol;

forwarding packets from the output of said second level scheduler to a first input a third level scheduler, and forwarding packets from the output of at least one of said first level schedulers to a second input of said third level scheduler, wherein said third level scheduler has an output and is operative in accordance with a third level scheduling protocol; and

forwarding packets from the output of said third level scheduler in accordance with said third level scheduling protocol.

2. The method of claim 1 wherein said segregating step comprises the step of segregating said packets into a plurality of sessions wherein each of said sessions is associated with one of said classification types, and each of said sessions includes packets associated with at least one of a plurality of Quality of Service (Q_o S) levels.

3. The method of claim 2 wherein said communication device comprises an Asynchronous Transfer Mode (ATM) switch and said plurality of Q_o S levels comprise Constant Bit Rate (CBR), real time Variable Bit Rate (rtVBR), non-real time Variable Bit Rate (nrtVBR) , Available Bit Rate (ABR), Unspecified Bit Rate+(UBR+) and Unspecified Bit Rate (UBR) Quality of Service levels.

4. The method of claim 1 wherein each of said first level schedulers, said second level scheduler and said third level scheduler comprise one of a CBR shaper, a Minimum Start Time Clocked Fair Queuing Plus (MSTCFQ+) scheduler, a Weighted Round Robin (WRR) scheduler, a Round Robin (RR) scheduler and a Static Priority (SP) scheduler.

5. The method of claim 1 wherein said classification types comprise CBR, rtVBR, nrtVBR, ABR, UBR+, and UBR Q_o S levels.

6. The method of claim 5 wherein said first level schedulers comprise a CBR shaper scheduler, an MSTCFQ+ scheduler, a plurality of WRR schedulers and at least one RR scheduler.

7. The method of claim 6 wherein said second level scheduler comprises an MSTCFQ+ scheduler.

8. The method of claim 7 wherein said third level scheduler comprises a Static Priority scheduler.

9. The method of claim 8 wherein said CBR shaper receives at the input of said shaper packets associated with said CBR classification type.

10. The method of claim 6 wherein said first level MSTCFQ+ scheduler receives at the input of such scheduler, packets associated with said rtVBR classification type.

11. The method of claim 6 wherein said plurality of WRR schedulers comprise first, second and third WRR schedulers.

12. The method of claim 11 wherein said inputs of first, second and third WRR schedulers receive at respective inputs packets corresponding to said nrtVBR, ABR and UBR classification types.

13. The method of claim 1 wherein said second level scheduling protocol comprises one of said first level scheduling protocols.

14. The method of claim 10 wherein said second level scheduling protocol comprises the same scheduling protocol associated with the rtVBR classification type.

15. The method of claim 1 wherein said plurality of packets comprise voice transmissions, video transmissions or data transmissions.

16. A method for scheduling packet transmission in a network communication device comprising the steps of:

receiving a plurality of packets, wherein each of said packets is associated with one of a plurality of Quality of Service (QOS) levels, said Q_o S levels comprising Constant Bit Rate (CBR), real time Variable Bit Rate (rtVBR), non-real time Variable Bit Rate (nrtVBR), Available Bit Rate (ABR), Unspecified Bit Rate + (UBR+) and Unspecified Bit Rate (UBR) Quality of Service levels;

segregating said received packets into a plurality of sessions, each of said sessions having at least one of said plurality of Q_o S levels;

forwarding said packets for each of said plurality of sessions to inputs of a corresponding plurality of first level schedulers, each of said schedulers having said input for receiving packets within respective sessions and an output, and wherein each one of said schedulers employs one of a plurality of first level scheduling protocols, said first level scheduling protocols comprising a CBR shaper, a Minimum Start Time Clocked Fair Queuing Plus (MSTCFQ+) scheduler, a Weighted Round Robin (WRR) scheduler, a Round Robin (RR) scheduler and a Static Priority (SP) scheduler;

receiving packets at inputs of a second level scheduler from the outputs of at least some of said plurality of first level schedulers, wherein said second level scheduler further includes an output and is operative in accordance with a second level scheduling protocol comprising a MSTCFQ+ scheduler;

forwarding packets from the output of said second level scheduler to a first input a third level scheduler, and forwarding packets from the output of at least one of said first level schedulers to a second input of said third level scheduler, wherein said third level scheduler has an output and is operative in accordance with a third level scheduling protocol comprising a Static Priority Scheduler; and

forwarding packets from the output of said third level scheduler in accordance with said third level scheduling protocol.