Method and system for a hierarchical traffic shaper

Abstract

A method of sorting packets for transmission over a communication network. The packets are sorted into groups in accordance with predetermined criteria, wherein the number of groups is equal to at least three times the square root of a fraction whose numerator is the maximum transmission rate and whose denominator is the minimum transmission rate. Each group is assigned a first departure time in accordance with the predetermined criteria. Each packet of each group is assigned a second departure time. Wherein the number of the departure time is equal to the square root of a fraction whose numerator is the maximum rate and whose denominator is the minimum transmission rate. Each packet is transmitted over the communication network in accordance with the second departure time.

1. A method of sorting packets for transmission over a communication network including the steps of:
 (a) sorting the packets into groups in accordance with predetermined criteria, wherein the number of groups is equal to at least three times the square root of a fraction whose numerator is the maximum transmission rate and whose denominator is the minimum transmission rate;  
 (b) assigning to each group a first departure time in accordance with said predetermined criteria;  
 (c) assigning to each packet of each group a second departure time, wherein the number of said departure time is equal to the square root of a fraction whose numerator is the maximum rate and whose denominator is the minimum transmission rate; and  
 (d) and transmitting each said packet over said communication network in accordance with said second departure time.  
 
     
     
       2. A method comprising:
   a network node assigning a departure parameter to a first packet, wherein the departure parameter includes a first value that corresponds to a first set of queues and a second value that corresponds to a second set of queues;        the network node selecting one of the first set of queues and the second set of queues to store the first packet responsive to the departure parameter;        the network node storing the first packet into a queue within the selected one of the first set of queues and the second set of queues; and        responsive to storing the first packet in one of the first set of queues, moving the first packet from the first set of queues to the second set of queues prior to transmitting the packet onto a communication network.     
     
     
       3. The method as recited in  claim 2  further comprising the network node storing the first packet in a virtual channel queue corresponding to a virtual channel of the first packet, and wherein the departure parameter is assigned responsive to another packet from the virtual channel being transmitted onto the communication network. 
     
     
       4. The method as recited in  claim 2  wherein the first value is relative to a first pointer to the first set of queues, wherein the first pointer indicates a given queue of the first set of queues. 
     
     
       5. The method as recited in  claim 5  wherein the second value is relative to a second pointer indicating a given queue in the second set of queues from which a packet is being read. 
     
     
       6. The method as recited in  claim 5  wherein at least one packet from the given queue is moving to the second set of queues at a time that the first pointer is indicating the given queue. 
     
     
       7. The method as recited in  claim 2  further comprising the network node calculating the departure parameter dependent on a traffic contract corresponding to the first packet. 
     
     
       8. The method as recited in  claim 2  further comprising the network node calculating the departure parameter dependent on a quality of service associated with the first packet. 
     
     
       9. The method as recited in  claim 8  wherein the quality of service is constant bit rate service. 
     
     
       10. The method as recited in  claim 8  wherein the quality of service is variable bit rate service. 
     
     
       11. The method as recited in  claim 8  wherein the quality of service is available bit rate service. 
     
     
       12. The method as recited in  claim 8  wherein the quality of service is guaranteed frame rate service. 
     
     
       13. The method as recited in  claim 8  wherein the quality of service is unspecified bit rate service. 
     
     
       14. The method as recited in  claim 2  wherein the communication network comprises cable media. 
     
     
       15. The method as recited in  claim 2  wherein the communication network comprises digital subscriber line (DSL). 
     
     
       16. The method as recited in  claim 2  wherein the first packet is a cell. 
     
     
       17. The method as recited in  claim 2  wherein the first packet is an asynchronous transfer mode communication. 
     
     
       18. A method comprising:
   a network node assigning a departure parameter to a first packet, the departure parameter including a first value that is relative to a first pointer to a first set of queues and further including a second value that is relative to a second pointer to a second set of queues;        the network node comparing the first value to the first pointer;        the network node storing the first packet in one of the first set of queues responsive to a first result of the comparing; and        the network node storing the first packet in one of the second set of queues responsive to a second result of the comparing;        wherein packets stored in the first set of queues are subsequently moved to the second set of queues responsive to the first pointer, and wherein packets stored in the second set of queues are subsequently moved to a departure queue responsive to the second pointer.     
     
     
       19. The method as recited in  claim 18  wherein the first result comprises the first value equaling the first pointer. 
     
     
       20. The method as recited in  claim 19  wherein the first result further comprises the first value equaling the first pointer plus one. 
     
     
       21. The method as recited in  claim 20  wherein the second result comprises any result other than the first result. 
     
     
       22. The method as recited in  claim 18  wherein the assigning is performed responsive to receiving the first packet. 
     
     
       23. The method as recited in  claim 18  further comprising the network node storing the first packet in a virtual channel queue corresponding to a virtual channel of the first packet, and wherein the assigning is performed responsive to another packet from the virtual channel departing from the departure queue. 
     
     
       24. The method as recited in  claim 18  wherein the second pointer changes values at a more rapid rate than the first pointer changes values. 
     
     
       25. The method as recited in  claim 18  further comprising the network node moving at least one packet from one of the second set of queues to the departure queue and changing the value of the second pointer. 
     
     
       26. The method as recited in  claim 25  further comprising the network node moving at least one packet from one of the first set of queues to one of the second set of queues and changing the value of the first pointer. 
     
     
       27. The method as recited in  claim 18  wherein the one of the first set of queues into which the first packet is stored is determined responsive to the first value. 
     
     
       28. The method as recited in  claim 18  wherein the one of the second set of queues into which the first packet is determined responsive to the second value. 
     
     
       29. A network node comprising a first set of queues and a second set of queues, wherein the network node is coupled to receive a first packet and is configured to assign a departure parameter to the first packet, wherein the departure parameter includes a first value relative to a first pointer to the first set of queues and a second value relative to the second set of queues, wherein the network node is configured to store the first packet into a queue within one of the first set of queues or the second set of queues, wherein the network node is configured to select the first set or the second set responsive to the departure parameter, and wherein, if the first packet is stored in one of the first set of queues, the network node is configured to move the first packet from the first set of queues to the second set of queues prior to transmitting the packet onto a communication network. 
     
     
       30. The network node as recited in  claim 29  further comprising a set of virtual channel queues, wherein the network node is configured to store the first packet in a virtual channel queue corresponding to a virtual channel of the first packet, and wherein the network node is configured to assign the departure parameter responsive to transmitting another packet from the virtual channel on the communication network. 
     
     
       31. The network node as recited in  claim 29  wherein the first pointer indicates a given queue of the first set of queues, wherein the network node is configured to move at least one packet from the given queue to a corresponding queue in the second set of queues. 
     
     
       32. The network node as recited in  claim 29  wherein the network node is further configured to calculate the departure parameter dependent on a traffic contract corresponding to the first packet. 
     
     
       33. The network node as recited in  claim 29  wherein the network node is further configured to calculate the departure parameter dependent on a quality of service associated with the first packet. 
     
     
       34. The network node as recited in  claim 33  wherein the quality of service is constant bit rate service. 
     
     
       35. The network node as recited in  claim 33  wherein the quality of service is variable bit rate service. 
     
     
       36. The network node as recited in  claim 33  wherein the quality of service is available bit rate service. 
     
     
       37. The network node as recited in  claim 33  wherein the quality of service is guaranteed frame rate service. 
     
     
       38. The network node as recited in  claim 33  wherein the quality of service is unspecified bit rate service. 
     
     
       39. The network node as recited in  claim 29  wherein the communication network comprises cable media. 
     
     
       40. The network node as recited in  claim 29  wherein the communication network comprises digital subscriber line ( DSL ). 
     
     
       41. The network node as recited in  claim 29  wherein the first packet is a cell. 
     
     
       42. The network node as recited in  claim 29  wherein the first packet is an asynchronous transfer mode communication.