Priority-aware hierarchical communication traffic scheduling

Abstract

Priority-aware hierarchical communication traffic scheduling methods and apparatus are disclosed. Communication traffic is scheduled by schedulers. Each scheduler supports a multiple priority scheduling function to schedule communication traffic having any of multiple priorities. The communication traffic scheduled by the schedulers is further scheduled based on the priorities of the communication traffic scheduled by each of the schedulers. Traffic shaping may also be integrated into a hierarchical scheduler. The priority-aware further scheduling and the optional shaping may be implemented, for example, using multiple Active lists, one per traffic priority, and a Pending list to which a scheduler can be added if it has communication traffic to schedule but is not allowed to schedule that traffic due to the shaping.

1 . An apparatus comprising:
 a plurality of schedulers that schedule communication traffic, each scheduler supporting a multiple priority scheduling function to schedule communication traffic having any of a plurality of priorities; and   a priority-aware scheduler, operatively coupled to the plurality of schedulers, that further schedules communication traffic from the plurality of schedulers based on priorities of communication traffic scheduled by each of the plurality of schedulers.   
     
     
         2 . The apparatus of  claim 1 , wherein the priority-aware scheduler further schedules traffic based on priorities by maintaining a plurality of Active lists respectively associated with the plurality of priorities, and wherein each scheduler of the plurality of schedulers schedules communication traffic to the Active list associated with the priority of communication traffic it is currently scheduling. 
     
     
         3 . The apparatus of  claim 1 , wherein the priority-aware scheduler services the plurality of Active lists in priority order according to a Deficit Round Robin (DRR) scheduling algorithm. 
     
     
         4 . The apparatus of  claim 1 , further comprising:
 a shaper, operatively coupled between a scheduler of the plurality of schedulers and the priority-aware scheduler, that controls scheduling of communication traffic to the priority-aware scheduler by the scheduler to which the shaper is operatively coupled.   
     
     
         5 . The apparatus of  claim 4 , wherein the shaper allows the scheduler to which it is operatively coupled to schedule communication traffic to the priority-aware scheduler at up to a maximum rate, and wherein the scheduler is added to a Pending list after the shaper has reached its maximum rate. 
     
     
         6 . The apparatus of  claim 2 , further comprising:
 a shaper, operatively coupled between a scheduler of the plurality of schedulers and the priority-aware scheduler, that controls scheduling of communication traffic to the priority-aware scheduler by the scheduler to which the shaper is operatively coupled,   wherein the shaper allows the scheduler to which it is operatively coupled to schedule communication traffic to the priority-aware scheduler at up to a maximum rate, and wherein the scheduler is added to a Pending list after the shaper has reached its maximum rate.   
     
     
         7 . The apparatus of  claim 6 , wherein the shaper manages the maximum rate by issuing tokens to the scheduler to which it is operatively coupled, and wherein the scheduler schedules communication traffic to an Active list when it has communication traffic to schedule and it has sufficient shaper tokens to schedule the communication traffic, and wherein the scheduler is added to the Pending list when it has communication traffic to schedule but it does not have sufficient shaper tokens to schedule the communication traffic. 
     
     
         8 . The apparatus of  claim 6 ,
 wherein the shaper comprises one of a plurality of shapers operatively coupled between respective schedulers of the plurality of schedulers and the priority-aware scheduler, each shaper controlling scheduling of communication traffic to the priority-aware scheduler by the scheduler to which the shaper is operatively coupled,   wherein each shaper allows the scheduler to which it is operatively coupled to schedule communication traffic to the priority-aware scheduler at up to a respective maximum rate, and   wherein each scheduler that is operatively coupled to a shaper is added to a Pending list after its shaper has reached its maximum rate.   
     
     
         9 . The apparatus of  claim 8 , wherein a scheduler that is operatively coupled to a shaper moves from the Pending list to an Active list when it has communication traffic to schedule and it is issued sufficient tokens to schedule the communication traffic by its shaper. 
     
     
         10 . The apparatus of  claim 8 , wherein the plurality of shapers comprises shapers having different respective maximum rates. 
     
     
         11 . A method comprising:
 scheduling communication traffic in a plurality of schedulers, each scheduler supporting a multiple priority scheduling function to schedule communication traffic having any of a plurality of priorities; and   further scheduling the communication traffic scheduled in the plurality of schedulers based on priorities of communication traffic scheduled by each of the plurality of schedulers.   
     
     
         12 . The method of  claim 11 , wherein the further scheduling comprises maintaining a plurality of Active lists respectively associated with the plurality of priorities, and wherein the scheduling in the plurality of schedulers comprises each scheduler scheduling communication traffic to the Active list associated with the priority of communication traffic it is currently scheduling. 
     
     
         13 . The method of  claim 11 , wherein the further scheduling comprises servicing the plurality of Active lists in priority order according to a Deficit Round Robin (DRR) scheduling algorithm. 
     
     
         14 . The method of  claim 11 , further comprising:
 shaping the communication traffic that is scheduled by a scheduler of the plurality of schedulers prior to the further scheduling.   
     
     
         15 . The method of  claim 14 , wherein the shaping comprises:
 allowing communication traffic to be scheduled by the scheduler at up to a maximum rate; and   maintaining a Pending list to which the scheduler is added after the maximum rate is reached.   
     
     
         16 . The method of  claim 12 , further comprising:
 shaping the communication traffic that is scheduled by a scheduler of the plurality of schedulers prior to the further scheduling by allowing the scheduler to schedule communication traffic at up to a maximum rate, and maintaining a Pending list to which the scheduler is added after the maximum rate is reached.   
     
     
         17 . The method of  claim 16 ,
 wherein the allowing comprises managing the maximum rate by issuing tokens to the scheduler,   wherein the scheduling by the scheduler comprises scheduling communication traffic to an Active list when it has communication traffic to schedule and it has sufficient shaper tokens to schedule the communication traffic, and   wherein the scheduler is added to the Pending list when it has communication traffic to schedule but it does not have sufficient shaper tokens to schedule the communication traffic.   
     
     
         18 . The method of  claim 16 , wherein the shaping comprises shaping the communication traffic that is scheduled by respective schedulers of the plurality of schedulers prior to the further scheduling by:
 allowing communication traffic to be scheduled by the respective schedulers at up to a respective maximum rate; and   maintaining a Pending list to which each scheduler of the respective schedulers is added after the respective maximum rate of the shaping is reached.   
     
     
         19 . The method of  claim 18 , wherein the scheduling comprises moving a scheduler from the Pending list to an Active list when it has communication traffic to schedule and it is issued sufficient shaper tokens to schedule the communication traffic. 
     
     
         20 . The method of  claim 18 , wherein the allowing comprises allowing communication traffic to be scheduled by the respective schedulers at up to different respective maximum rates. 
     
     
         21 . An apparatus comprising:
 an interface that enables the apparatus to receive communication traffic from a plurality of schedulers that support a multiple priority scheduling function to schedule communication traffic having any of a plurality of priorities; and   a priority-aware scheduler, operatively coupled to the interface, that further schedules communication traffic scheduled by the plurality of schedulers based on priorities of communication traffic scheduled by each of the plurality of schedulers.   
     
     
         22 . The apparatus of  claim 21 , wherein the priority-aware scheduler further schedules communication traffic by maintaining a plurality of Active lists, respectively associated with a plurality of communication traffic priorities, to which the plurality of schedulers can schedule communication traffic. 
     
     
         23 . The apparatus of  claim 21 , wherein the priority-aware scheduler services the plurality of Active lists in priority order according to a Deficit Round Robin (DRR) scheduling algorithm.