Method and apparatus for queuing data flows

• US 20040001493A1
• Filed: 06/26/2002
• Published: 01/01/2004
• Est. Priority Date: 06/26/2002
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: ARRIS Group, Inc. (CommScope Holding Company, Inc.)
• Inventors: Cloonan, Thomas J., Howe, Jeffrey J., Urban, Kevin P.
• Granted Patent: US 7,272,144 B2
• Time in Patent Office: Days
• US Class Current: 370/395.42
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

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.

Claims

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 it'"'"'s 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.

2. 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 it'"'"'s 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;

scheduling the delivery of at least one data packet to a destination using the at least one desired latency characteristic assigned to the packet'"'"'s relative scheduling priority.

3. 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 it'"'"'s 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 latency for at least one data packet;

scheduling the delivery of at least one data packet to a destination using the at least one desired latency characteristic assigned to the packet'"'"'s relative scheduling priority and the packet'"'"'s latency.

4. 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 it'"'"'s 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 latency for at least one data packet;

scheduling the delivery of at least one data packet to a destination as a first function of the packet'"'"'s latency and the at least one desired latency characteristic assigned to the relative scheduling priority for said packet.

5. The method of claim 4 wherein said first function is comprised of a ratio of a second function of said packet'"'"'s latency to a third function of the at least one desired latency characteristic.

6. 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 it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, a method of scheduling the delivery of packets to a destination comprising:

assigning at least one desired latency characteristic to each relative scheduling priority;

storing at least one data packet into a queue corresponding to the packet'"'"'s relative scheduling priority;

determining a latency for at least one data packet;

scheduling the delivery of at least one data packet to a destination as a first function of the packet'"'"'s latency and the at least one desired latency characteristic assigned to the relative scheduling priority for said packet.

7. The method of claim 6 wherein said first function is comprised of a ratio of a second function of said packet'"'"'s latency to a third function of the at least one desired latency characteristic.

8. 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 it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, a method of scheduling the delivery of packets to a destination comprising:

assigning at least one desired latency characteristic to each relative scheduling priority;

storing at least one data packet into a queue corresponding to the packet'"'"'s relative scheduling priority;

for at least one data packet in each data queue, determining a latency for said at least one data packet;

for said at least one data packet from each data queue, the latencies of which were determined, calculating a first function of;

a) each packet'"'"'s latency and b) the at least one desired latency characteristic assigned to the relative scheduling priority for each packet;

scheduling the delivery of at least one data packet to a destination using a selection function.

9. The method of claim 8 wherein said selection function is comprised of comparing the results obtained from the first function calculations and identifying a queue with the result best approximating the desired latency characteristic thereof and selecting the oldest packet from that queue

10. The method of claim 8 wherein said first function is comprised of a ratio of a second function of said packet'"'"'s latency to a third function of the at least one desired latency characteristic.

11. The method of claim 10 wherein said desired latency characteristic represents the maximum desired latency and the selection function is comprised of identifying a data queue with the greatest result of the first function calculations and selecting the oldest packet from that data queue.

20. The method of claim 8 wherein said desired latency characteristics include a maximum desired latency, when at least one data queue has an oldest packet whose current latency exceeds the maximum desired latency assigned to the relative scheduling priority corresponding to said data queue (i.e., a latency violating queue), the selection function is comprised of selecting a queue from all latency violating queues with the highest relative scheduling priority (i.e. strict priority), and selecting the oldest packet from that queue.

12. 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 it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, 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 at least one latency scaling parameter for each relative scheduling priority, as a function of the at least one desired latency characteristic;

for each data packet, assigning a data value indicating the packet'"'"'s arrival time;

storing each data packet, and it'"'"'s assigned data value, into at least one queue corresponding to the packet'"'"'s relative scheduling priority;

for each data queue, determining the current latency value for the packet that has been in the queue the longest (i.e., the oldest data packet) using it'"'"'s assigned data value and the current time;

for each data queue, determining if the oldest data packet is eligible to be routed (i.e., an eligible data packet) to a destination based on said oldest data packet'"'"'s current latency value and the desired latency characteristics assigned to the relative scheduling priority corresponding to said data queue;

for each data queue having an eligible data packet, calculating a first function of at least one of;

a) each eligible data packet'"'"'s current latency;

b) the desired latency characteristic assigned to the relative scheduling priority corresponding to said data queue;

c) the latency scaling parameter determined for the relative scheduling priority corresponding to said data queue;

scheduling the delivery of at least one data packet to a destination using a selection function.

13. The method of claim 12 wherein said selection function is comprised of comparing the results obtained from the first function calculations and identifying a queue with the result best approximating the desired latency characteristic thereof and selecting the oldest packet from that queue.

14. The method of claim 12 wherein one of said desired latency characteristics includes a minimum desired latency, said first function is comprised of subtracting the minimum desired latency from said packet'"'"'s current latency and multiplying the results of said subtraction by the latency scaling parameter.

15. The method of claim 12 wherein said desired latency characteristics includes a minimum desired latency and a maximum desired latency, said latency scaling parameter is inversely proportional to the difference between the maximum desired latency and the minimum desired latency.

16. The method of claim 14 wherein said desired latency characteristics includes a minimum desired latency and a maximum desired latency, said latency scaling parameter is inversely proportional to the difference between the maximum desired latency and the minimum desired latency.

17. The method of claim 12 wherein said desired latency characteristic includes a minimum desired latency, said eligibility of said oldest data packet is established when the oldest data packet'"'"'s current latency is equal to or greater than the minimum desired latency.

18. The method of claim 14 wherein the selection function is comprised of identifying a data queue with the greatest result of the first function calculations and selecting the oldest packet from that data queue.

19. The method of claim 16 wherein the selection function is comprised of identifying a data queue with the greatest result of the first function calculations and selecting the oldest packet from that data queue.

21. The method of claim 12 wherein said desired latency characteristics include a maximum desired latency, when at least one data queue has an oldest packet whose current latency exceeds the maximum desired latency assigned to the relative scheduling priority corresponding to said data queue (i.e., a latency violating queue), the selection function is comprised of selecting a queue from all latency violating queues with the highest relative scheduling priority (i.e. strict priority), and selecting the oldest packet from that queue.

22. The method of claim 12 wherein said desired latency characteristics includes a minimum desired latency, the step of determining if the oldest data packet is eligible includes determining if said oldest data packet'"'"'s current latency value is greater than or equal to the minimum desired latency.

23. A method of controlling the flow of data packets of a data flow through a data system comprising:

receiving a first data packet of a first data flow at a port of said data system;

identifying the first data packet'"'"'s time of arrival at the port;

storing the first data packet in a queue, for a latency time that is greater than or equal to a minimum latency time and less than or equal to a maximum latency time;

outputting the first data packet from a port of the data system.

24. A method of controlling the flow of data packets of a data flow through a data system comprising:

receiving a first data packet of a first data flow at a port of said data system;

storing the first data packet in a queue;

identifying the first data packet'"'"'s time of arrival in the queue;

after the passage of a time that is greater than or equal to a minimum latency time and less than or equal to a maximum latency time, outputting the first data packet from a port of the data system.

25. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

processor means for assigning at least one desired latency characteristic to each relative scheduling priority.

26. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

processor means for assigning at least one desired latency characteristic to each relative scheduling priority;

a scheduling engine, scheduling the delivery of at least one data packet to a destination using the at least one desired latency characteristic assigned to the packet'"'"'s relative scheduling priority.

27. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

means for assigning at least one desired latency characteristic to each relative scheduling priority;

means for determining a latency for at least one data packet;

a scheduling engine, for scheduling the delivery of at least one data packet to a destination using the at least one desired latency characteristic assigned to the packet'"'"'s relative scheduling priority and the packet'"'"'s latency.

28. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

means for assigning at least one desired latency characteristic to each relative scheduling priority;

means for determining a latency for at least one data packet;

a scheduling engine for scheduling the delivery of at least one data packet to a destination as a first function of the packet'"'"'s latency and the at least one desired latency characteristic assigned to the relative scheduling priority for said packet.

29. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

means for assigning at least one desired latency characteristic to each relative scheduling priority;

a memory, storing at least one data packet into a queue corresponding to the packet'"'"'s relative scheduling priority;

means for determining a latency for at least one data packet;

a scheduling engine, for scheduling the delivery of at least one data packet to a destination as a first function of the packet'"'"'s latency and the at least one desired latency characteristic assigned to the relative scheduling priority for said packet.

30. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

processor means for assigning at least one desired latency characteristic to each relative scheduling priority;

processor means for determining at least one latency scaling parameter for each relative scheduling priority, as a function of the at least one desired latency characteristic;

a time stamp circuit means for assigning a data value indicating the packet'"'"'s arrival time;

a memory, storing each data packet, and it'"'"'s assigned data value, into at least one queue corresponding to the packet'"'"'s relative scheduling priority;

means for determining for each data queue, the current latency value for the packet that has been in the queue the longest (i.e., the oldest data packet) using it'"'"'s assigned data value and the current time; and

for determining for each data queue, if the oldest data packet is eligible to be routed (i.e., an eligible data packet) to a destination based on said oldest data packet'"'"'s current latency value and the desired latency characteristics assigned to the relative scheduling priority corresponding to said data queue;

for each data queue having an eligible data packet, calculating a first function of at least one of;

a) each eligible data packet'"'"'s current latency;

b) the desired latency characteristic assigned to the relative scheduling priority corresponding to said data queue;

c) the latency scaling parameter determined for the relative scheduling priority corresponding to said data queue;

scheduling engine for scheduling the delivery of at least one data packet to a destination using a selection function.

31. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

means for receiving a first data packet of a first data flow at a port of said data system;

means for identifying the first data packet'"'"'s time of arrival at the port;

means for storing the first data packet in a queue, for a latency time that is greater than or equal to a minimum latency time and less than or equal to a maximum latency time;

means for outputting the first data packet from a port of the data system.

32. A data system that receives data packets and routes said data packets to one or more destinations, each data packet to be routed to it'"'"'s destination according to a relative scheduling priority, said data system having a plurality of data queues corresponding to the relative scheduling priorities of said packets, said data system comprising:

means for receiving a first data packet of a first data flow at a port of said data system;

means for storing the first data packet in a queue;

means for identifying the first data packet'"'"'s time of arrival in the queue;

means for outputting the first data packet from a port of the data system after the passage of a time that is greater than or equal to a minimum latency time and less than or equal to a maximum latency time.

33. A data distribution system comprised of:

a cable distribution network;

a cable modem termination system operatively coupled to said cable distribution network and comprised of;

processor means for assigning at least one desired latency characteristic to each relative scheduling priority;

a scheduling engine, scheduling the delivery of at least one data packet to a destination using the at least one desired latency characteristic assigned to the packet'"'"'s relative scheduling priority.