Method and apparatus for queuing data flows

Abstract

In a data system, such as a cable modem termination system, different-priority flows are scheduled to be routed to their logical destinations by factoring both the priority level and the time spent in queue. The time that each packet of each flow spends waiting for transmission is normalized such that the waiting times of all flows are equalized with respect to each other. A latency scaling parameter is calculated.

1. In a data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to its destination according to a relative scheduling priority, a method of scheduling the delivery of packets to a destination, comprising:
 assigning at least one desired latency characteristic to each relative scheduling priority; 
 determining a maximum latency value for the packets in each one of a plurality of queues, each queue being associated with a relative scheduling priority; 
 determining a scaled latency value for each of the plurality of queues based on a function of the at least one desired latency characteristic and a function of the maximum latency value corresponding to each of the plurality of queues; and 
 selecting for transmission a packet from among the plurality of queues based on a comparison of the scaled latency values for each of the plurality of queues. 
 
   
   
     2. The method of  claim 1  wherein one of the at least one desired latency characteristics is a desired maximum amount of time a data packet should stay in a given queue. 
   
   
     3. The method of  claim 1  wherein one of the at least one desired latency characteristics is a desired minimum amount of time a data packet should stay in a given queue. 
   
   
     4. The method of  claim 3  wherein another desired latency characteristic is a desired maximum amount of time a packet should stay in the given queue. 
   
   
     5. The method of  claim 4  wherein the function of the at least one desired latency characteristic is the inverse of the difference between the desired maximum and the desired minimum amounts of time a packet should remain in a queue. 
   
   
     6. The method of  claim 5  wherein the function of the at least one desired latency characteristic is multiplied by a shifted latency value for the oldest packet in a queue to generate the scaled latency value for the oldest packet in the queue. 
   
   
     7. The method of  claim 6  wherein the respective scaled latency values of the oldest packet in each of a plurality of queues are compared to one another such that the packet having the highest scaled latency value is scheduled for transmission next.