Method and apparatus for queuing data flows
View Patent ↗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. A method executing on hardware, comprising:
associating a scheduling priority for each of a plurality of queues, the scheduling priority comprising desired latency characteristics associated with packets in the respective queue;
identifying latency values associated with the oldest packets in each of the respective plurality of queues;
determining a scaled latency value for each of the plurality of queues based on a function of the desired latency characteristic and a function of the latency value for the oldest packet in the respective queue;
comparing the scaled latency values for each of the plurality of queues; and
identifying a packet for transmission based upon the comparison of the scaled latency values.
2. The method of claim 1 , wherein one of the desired latency characteristics comprises a desired maximum amount of time a data packet stays in an associated queue.
3. The method of claim 1 , wherein one of the desired latency characteristics comprises a desired minimum amount of time a data packet should stay in a given queue.
4. The method of claim 3 , wherein one of the desired latency characteristics comprises a desired maximum amount of time a data packet stays in an associated 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 value 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.
8. The method of claim 1 , further comprising transmitting the identified packet toward a recipient identified within the packet.
9. A system, comprising:
a queuing structure comprising a plurality of queues, the queuing structure being operable to identify a queue associated with incoming packets and store the incoming packets in the respective identified queue associated with each of the incoming packets; and
scheduling engines operable to identify desired latency characteristics associated with the plurality of queues, and latency values associated with the oldest packets in each of the plurality of queues, wherein the scheduling engines are operable to identify a next packet to transmit based upon determination of scaled latency values associated with the plurality of queues, the scaled latency values being based upon a function of the desired latency characteristic and a function of the latency values for the oldest packets in the respective queues.
10. The system of claim 9 , further comprising a transmitter operable to transmit the next packet to transmit based upon the result of the scheduling engines.
11. The system of claim 9 , wherein one of the desired latency characteristics comprises a desired maximum amount of time a data packet stays in an associated queue.
12. The system of claim 9 , wherein one of the desired latency characteristics comprises a desired minimum amount of time a data packet should stay in a given queue.
13. The system of claim 12 , wherein one of the desired latency characteristics comprises a desired maximum amount of time a data packet stays in an associated queue.
14. The method of claim 13 , 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.
15. The method of claim 14 , 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.
16. The method of claim 15 , wherein the respective scaled latency value 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.
17. A method, comprising:
queuing incoming packets into one of a plurality of queues;
identifying latency values associated with the oldest packets in each of the plurality of queues;
determining a scaled latency value for each of the plurality of queues based on a function of a desired latency characteristic associated with the queue and the latency value for the oldest packet in the respective queue;
identifying a packet for transmission based upon a comparison of the scaled latency values.
18. The method of claim 17 , further comprising transmitting the identified packet.
19. The method of claim 17 , wherein the step of queuing comprises providing packets having quality of service requirements a higher priority than packets without quality of service requirements.
20. The method of claim 17 , wherein the scaled latency value comprises a function of the difference between a desired latency characteristic associated with the packet and the current latency value associated with the packet.