Method and apparatus for queuing data flows

• US 7,272,144 B2
• Filed: 06/26/2002
• Issued: 09/18/2007
• Est. Priority Date: 06/26/2002
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Arris International, Inc. (CommScope Holding Company, Inc.)
• Inventors: Cloonan, Thomas J., Howe, Jeffrey J., Urban, Kevin P.
• Primary Examiner(s): Sam; Phirin
• Application Number:
  US10/180,736
• Publication Number:
  US 20040001493A1
• Time in Patent Office: 1,910 Days
• Field of Search: None
• 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, 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 result of a first function of each eligible data packet'"'"'s current latency and 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 based on the calculated result of the first function.

2. The method of claim 1 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.

3. The method of claim 1 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.

4. The method of claim 1 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.

5. The method of claim 3 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.

6. The method of claim 1 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.

7. The method of claim 3 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.

8. The method of claim 5 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.

10. The method of claim 1 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.

11. The method of claim 1 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.

9. 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 result of 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 based on the calculated result of the first function;

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. 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 data 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 result of 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 based on the calculated result of the first function.