Method and apparatus for packet transmission with configurable adaptive output scheduling

Abstract

A configurable adaptive variable length data packet transmission output scheduler for enabling substantially simultaneous transmission on a common transmission link, as of fiber optics, of differentiated services for various different traffic types, executing different QOS algorithms while co-existing in a converged network environment, with simultaneous preserving of the different service characteristics for real-time or high-priority traffic and providing differentiated bandwidth allocation while achieving maximal link utilization—all through a fine and balanced control as to which type of traffic is transmitted on the link for a given duration, and how much of that traffic is transmitted on the link.

What is claimed is: 
     
       1. In a switch/router that routes variable length data packets in a converged network environment, a method comprising:
 receiving a plurality of data packet flows, each received data packet flow of the plurality having respective customer-assigned service requirements, including definition of service, priority, delay, jitter and bandwidth characteristics; 
 directing the received data packet flows to corresponding egress queues; 
 allocating amounts of bandwidth to each data packet traffic flow of the plurality of data packet flows in accordance with the respective customer-assigned service requirements by:
 selecting amounts of bandwidth assigned to each of the egress queues and determining an amount of data to be released from each egress queue; 
 monitoring an occupancy of each egress queue to determine an amount of unused bandwidth that is allocated to but not used in any given egress queue; 
 managing the unused bandwidth in a repository for unused bandwidth, so as to be available for allocation to other egress queues that can utilize the unused bandwidth; and 
 making at least a portion of the unused bandwidth available from the repository for use by another egress queue that has more data to send than the allocated bandwidth will permit; and 
 
 scheduling a departure order of the each of the plurality of data packet traffic flows from the switch/router to a common communication link based upon and adapted to the respective customer-assigned service requirements, by selecting, independently of bandwidth allocation, at least one of an order and a priority of data packet release from the egress queues to the common communication link, 
 whereby the switch/router provides differentiated services for the plurality of data packet traffic flows, while simultaneously substantially filling a total data packet flow capacity utilization of the common communication link. 
 
     
     
       2. The method of  claim 1  wherein making at least a portion of the unused bandwidth available from the repository for use by another egress queue comprises making the unused bandwidth available for use without crediting or debiting any egress queue. 
     
     
       3. The method of  claim 2  wherein each egress queue is provided with a base weight system and counter to enable users to control a percentage of unused bandwidth distributed among the egress queues, and wherein making at least a portion of the unused bandwidth available from the repository for use by another egress queue comprises assigning unused bandwidth to another egress queue based upon weights of the weight system, an amount of data present in queue memory, and on the unused bandwidth available. 
     
     
       4. The method of  claim 1 , wherein allocating amounts of bandwidth comprises allocating percentages of bandwidth. 
     
     
       5. A switch/router that routes variable length data packets in a converged network environment, the switch/router comprising, in combination:
 means for receiving a plurality of data packet flows, each received data packet flow of the plurality having respective customer-assigned service requirements, including definition of service, priority, delay, jitter and bandwidth characteristics; 
 means for directing the received data packet flows to corresponding egress queues; 
 means for allocating amounts of bandwidth to each data packet traffic flow of the plurality of data packet flows in accordance with the respective customer-assigned service requirements through:
 means for selecting amounts of bandwidth assigned to each of the egress queues and determining an amount of data to be released from each egress queue; 
 means for monitoring an occupancy of each egress queue to determine an amount of unused bandwidth that is allocated to but not used in any given egress queue; 
 means for managing the unused bandwidth in a repository for unused bandwidth, so as to be available for allocation to other egress queues that can utilize the unused bandwidth; and 
 means for making at least a portion of the unused bandwidth available from the repository for use by another egress queue that has more data to send than the allocated bandwidth will permit; and 
 
 means for scheduling a departure order of the each of the plurality of data packet traffic flows from the switch/router to a common communication link based upon and adapted to the respective customer-assigned service requirements, by selecting, independently of bandwidth allocation, at least one of an order and a priority of data packet release from the egress queues to the common communication link, 
 whereby the switch/router provides differentiated services for the plurality of data packet traffic flows, while simultaneously substantially filling a total data packet flow capacity utilization of the common communication link. 
 
     
     
       6. The switch/router of  claim 5  wherein means for making at least a portion of the unused bandwidth available from the repository for use by another egress queue comprise means for making the unused bandwidth available for use without crediting or debiting any egress queue. 
     
     
       7. The switch/router of  claim 6  wherein each egress queue is provided with a base weight system and counter to enable users to control a percentage of unused bandwidth distributed among the egress queues, and wherein means for making at least a portion of the unused bandwidth available from the repository for use by another egress queue comprise means for assigning unused bandwidth to another egress queue based upon weights of the weight system, an amount of data present in queue memory, and on the unused bandwidth available. 
     
     
       8. The method of  claim 5 , wherein means for allocating amounts of bandwidth comprise means for allocating percentages of bandwidth. 
     
     
       9. A method, comprising:
 receiving, at a switch/router, a plurality of packet data flows;   the switch/router directing the received plurality of data packet flows to one or more corresponding egress queues;   the switch/router assigning, for an egress queue of the one or more egress queues, at least an amount of allocated bandwidth and an amount of data to be released;   the switch/router monitoring an occupancy of the one or more egress queues to determine an amount of unused bandwidth allocated to but not used by the one or more egress queues;   the switch/router managing the amount of unused bandwidth in an unused-bandwidth repository to enable allocation of the amount of unused bandwidth by at least one egress queue of the one or more egress queues that can utilize unused bandwidth;   the switch/router making at least a portion of the amount of unused bandwidth available from the unused-bandwidth repository for use by the at least one egress queue that can utilize the unused bandwidth; and   the switch/router selecting, independently of bandwidth allocation, at least one of an order and a priority of data packet release from the one or more egress queues to a common communication link.   
     
     
       10. The method of claim 9, further comprising:
 the switch/router transmitting a packet based on the at least one of the order and the priority of data packet release.   
     
     
       11. The method of claim 9, wherein assigning, for the egress queue of the one or more egress queues, at least the amount of bandwidth and the amount of data to be released comprises assigning, for the egress queue, a scheduling priority, and wherein the scheduling priority is selected from round robin and strict priority. 
     
     
       12. The method of claim 9, wherein monitoring, for each of the one or more egress queues, the occupancy to determine the amount of unused bandwidth allocated to but not used by the one or more egress queues comprises determining a difference between the amount of allocated bandwidth and the amount of data to be released. 
     
     
       13. The method of claim 9, wherein the switch/router further comprises an output first-in-first-out (FIFO) associated with the common communication link. 
     
     
       14. The method of claim 13, further comprising:
 determining a packet is to be released to the common communication link; and   accumulating the packet to be released in the output FIFO.   
     
     
       15. The method of claim 13, the switch/router further comprises a switch for the output FIFO, wherein the method further comprises:
 determining whether an amount of accumulation in the output FIFO exceeds a threshold value; and   in response to determining that the amount of accumulation exceeds the threshold value, switching off the switch for the output FIFO.   
     
     
       16. The method of claim 13, wherein the switch/router further comprises a rate controller, and wherein the method further comprises:
 the rate controller receiving a rate of accumulation for the output FIFO;   the rate controller comparing the rate of accumulation to a threshold;   in response to the rate of accumulation being below the threshold, increasing a scheduling rate for the traffic manager; and   in response to determining that the amount of accumulation being above the threshold, decreasing the scheduling rate for the traffic manager.   
     
     
       17. The method of claim 13, further comprising:
 receiving a feedback signal related to the common communication link; and   adjusting a data-transfer rate from the output FIFO based on the feedback signal.   
     
     
       18. The method of claim 9, wherein managing the amount of unused bandwidth in the unused-bandwidth repository comprises managing the amount of unused bandwidth based on a unit amount of bandwidth. 
     
     
       19. The method of claim 18, further comprising:
 for each of the one or more egress queues, maintaining a deficit counter comprising a value related to the amount of unused bandwidth allocated to but not used by the egress queue;   determining a summation of the one or more deficit counters;   adjusting the unit amount of bandwidth based on the summation.   
     
     
       20. An apparatus, comprising:
 one or more egress queues;   one or more ingress ports, configured to at least:
 receive a plurality of packet data flows and 
 direct the received plurality of data packet flows to the one or more corresponding egress queues; 
   a traffic manager, comprising an unused-bandwidth repository, and configured to at least:
 assign, for an egress queue of the one or more egress queues, at least an amount of allocated bandwidth and an amount of data to be released; 
 monitor an occupancy of the one or more egress queues to determine an amount of unused bandwidth allocated to but not used by the one or more egress queues; 
 manage the amount of unused bandwidth in the unused-bandwidth repository to enable allocation of the amount of unused bandwidth by at least one egress queue of the one or more egress queues that can utilize unused bandwidth; 
 make at least a portion of the amount of unused bandwidth available from the unused-bandwidth repository for use by the at least one egress queue that can utilize the unused bandwidth; and 
 select, independent of bandwidth allocation, at least one of an order and a priority of data packet release from the one or more egress queues to a common communication link. 
   
     
     
       21. The apparatus of claim 20, wherein the traffic manager is further configured to transmit a packet from at least one of the plurality of packet data flows based on the at least one of the order and the priority of data packet release. 
     
     
       22. The apparatus of claim 20, wherein the traffic manager is configured to assign, for the egress queue of the one or more egress queues, at least the amount of bandwidth and the amount of data to be released by at least assigning, for the egress queue, a scheduling priority, and wherein the scheduling priority is selected from round robin and strict priority. 
     
     
       23. The apparatus of claim 20, wherein the traffic manager is configured to monitor the occupancy to determine the amount of unused bandwidth allocated to but not used by the one or more egress queues by at least determining a difference between the amount of allocated bandwidth and the amount of data to be released. 
     
     
       24. The apparatus of claim 20, further comprising an output first-in-first-out (FIFO) associated with the common communication link. 
     
     
       25. The apparatus of claim 24, wherein the traffic manager is further configured to:
 determine a packet is to be released to the common communication link; and   accumulate the packet to be released in the output FIFO.   
     
     
       26. The apparatus of claim 24, further comprising a switch for the output FIFO, and wherein the traffic manager is further configured to:
 determine whether an amount of accumulation in the output FIFO exceeds a threshold value; and   in response to determining that the amount of accumulation exceeds the threshold value, switch off the switch for the output FIFO.   
     
     
       27. The apparatus of claim 26, wherein the traffic manager further comprises a rate controller, and wherein the rate controller is configured to at least:
 receive a rate of accumulation for the output FIFO;   compare the rate of accumulation to a threshold;   in response to the rate of accumulation being below the threshold, increasing a scheduling rate for the traffic manager; and   in response to determining that the amount of accumulation being above the threshold, decreasing the scheduling rate for the traffic manager.   
     
     
       28. The apparatus of claim 24, wherein the traffic manager is further configured to at least:
 receive a feedback signal related to the common communication link; and   adjust a data-transfer rate from the output FIFO based on the feedback signal.   
     
     
       29. The apparatus of claim 20, wherein the traffic manager is configured to manage the amount of unused bandwidth in the unused-bandwidth repository by at least managing the amount of unused bandwidth based on a unit amount of bandwidth. 
     
     
       30. The method of claim 29, wherein the traffic manager is further configured to at least:
 for each of the one or more egress queues, maintain a deficit counter comprising a value related to the amount of unused bandwidth allocated to but not used by the egress queue;   determine a summation of the one or more deficit counters;   adjust the unit amount of bandwidth based on the summation.