Method and apparatus for queue management

• US 6,917,585 B1
• Filed: 05/25/2000
• Issued: 07/12/2005
• Est. Priority Date: 06/02/1999
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Borden, Marty, Firoiu, Victor
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/578,564
• Time in Patent Office: 1,874 Days
• Field of Search: 370/229, 370/235, 370/236, 370/238, 370/241, 370/252, 370412-418
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method, apparatus, and computer program product for determining a drop probability for use in a congestion control module located in a node in a network is disclosed. A weight value for determining a weighted moving average of a queue in a node is first systematically calculated. The weighted moving average is calculating and an average queue size for the node is determined based upon the weighted moving average. A control function associated with the congestion control module is evaluated using the average queue size to determine the drop probability. In a further embodiment, the control function is calculated based upon a queue function where the queue function is calculated based upon predetermined system parameters. Thus, when the congestion control module drops packets based upon the drop probability determined by the control function the queue will not oscillate.

Claims

1. A method for controlling a transmission rate of packets in response to a calculated drop probability of the packets at a queue in a receiving node includes the steps of:

systematically calculating a weight for determining a weighted moving average fullness of the queue in a node;

calculating the weighted moving average;

determining an average queue size based upon the weighted moving average; and

evaluating a control function using the average queue size, the control function defining a drop behavior of packets at the node for a range of average queue sizes as defined by a congestion control process executing at the node to determine the drop probability with regard to the average queue size, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside a queue law function defined for the queue; and

controlling the sending rate of the packets by feeding the calculated drop probability back to the sender.

2. The method according to claim 1, wherein systematically calculating a weight comprises:

determining a sampling period for measuring the queue size;

determining a time period for which samples significantly contribute to the average queue size; and

determining the weight based upon the sampling period and the time period.

3. The method of claim 1, wherein evaluating a control function comprises:

determining the queue law function based upon predetermined system parameters; and

determining the control function based upon the queue law function.

4. The method according to claim 3 wherein determining the control function further comprises:

selecting a queue policy;

determining a threshold value based upon the selected queue policy;

determining a point based upon the threshold value, wherein the maximum point is outside of the queue function;

selecting the control function such that when the control function is evaluated a point passes through the maximum point.

5. The method according to claim 4 wherein the queue policy is a delay conservative

policy and wherein determining a threshold value comprises:

determining a value for the average queue size.

6. The method according to claim 4 wherein the queue policy is a drop conservative policy and wherein determining a threshold value comprises:

determining a maximum value for the drop probability.

7. A method for reducing oscillations in queue size in a link using a congestion control process that operates in a TCP environment, the method comprising:

determining a queue law function defining an average queue size for a link based at least upon a drop probability characteristic of the congestion control process;

defining a control function for the queue which identifies a drop probability of the congestion control process across a range of average queue sizes, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside the queue law functions; and

dropping packets from the queue at a packet drop rate defined at a point of intersection for the control function and the queue law function.

8. The method according to claim 7, wherein the step of defining the control function, the control function is further defined as a function having no discontinuities.

9. The method according to claim 7, wherein the control function is piecewise linear.

10. A method for increasing utilization of a link capable of receiving a number of flows into a buffer, the link residing in a TCP network, the link having a congestion control module which drops packets to avoid buffer overflow, the method comprising:

determining a quality representative of a capacity for the link;

calculating a quantity representative of the throughput for the link;

determining the utilization based on the capacity of the link, the throughput of the link, the numbers of flows and a packet drop probability calculated based on an average queue size and control function associated with a congestion control process of the link;

automatically adjusting the packet drop probability to maintain a desired utilization of the link in accordance with a control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside a queue law function defined for the queue.

11. A method for execution of a congestion control process in server having a queue which resides in a network wherein each data transmission from a sender to a receiver is sent at a transmission rate and the data transmission is acknowledged by the receiver, wherein if the data transmission is not acknowledged, the sender reduces the transmission rate, the method comprising:

ascertaining a network function which defines an average queue size of the queue based upon a server drop rate;

determining a control function for the server which defines a given server drop rate for a range of average queue sizes for a given congestion control process, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside the network function;

calculating an equilibrium point based upon the intersection of the network function and control function;

setting the drop rate of the server to the equilibrium point.

12. An apparatus for controlling a transmission rate of packets issued by a sender in response to a calculated drop probability, the apparatus comprising:

a buffer receiving data into a node, the buffer forming a queue;

a weight module for systematically calculating a weight for determining a weighted moving average of the queue in a node;

a queue estimator for calculating the weighted moving average based on the weight and the received data in the queue and determining an average queue size based upon the weighted moving average;

a processor for evaluating a control function using the average queue size to determine the drop probability, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside a queue law function defined for the queue; and

a feedback mechanism for forwarding the determined drop probability to the sender to control the sender'"'"'s transmission of packets such that a desired drop probability is attained.

13. The apparatus according to claim 12, wherein the weighted module:

determines the weight by first accessing a sampling period for measuring the queue size and a time period for which samples significantly contribute to the average queue size.

14. The apparatus according to claim 12, further comprising:

a configuration module for determining the queue function based upon predetermined system parameters and determining the control function based upon the queue function.

15. An apparatus for reducing oscillations in queue size in a link using a congestion control process that operates in a TCP environment, the apparatus comprising:

a queue law module for determining a queue law function based on system parameters, the queue law function defining the average queue size for a link based at least upon a drop probability of the congestion control process;

a control function module defining a control function which defines the drop probability of the congestion control process for a range of average queue sizes, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside the queue law function defined for the queue;

a processor for dropping packets from the queue based upon a packet drop rate defined at a point of intersection of the control function and the queue law function.

16. An apparatus for reducing oscillations in queue size in a link using a congestion control process that operates in a TCP environment, the apparatus comprising:

a configuration module for automatically determining configuration function configuration parameters based upon traffic characteristics;

a control function module receiving the control function configuration parameters which define a control function representing a range of packet drop probabilities across a range of queue sizes using the congestion control process and receiving an estimated queue size, the estimated queue size used in conjunction with the defined control function to determine a drop probability, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside a queue law function defined for the queue; and

a processor for dropping packets from the queue based upon a packet drop rate selected in accordance with the drop probability, wherein the packet drop rate is automatically updated in response to changing traffic characteristics.

17. A computer program product for controlling a transmission rate of packets issued by a sender in response to a calculated drop probability, wherein the computer program product has computer code on a computer readable medium, the computer code comprising:

computer code for systematically calculating a weight for determining a weighted moving average of a queue in a node;

computer code for calculating the weighted moving average;

computer code for determining an average queue size based upon the weighted moving average;

computer code for evaluating a control function based on a congestion control process executing at the node, the control function defining a range of drop probabilities for a range of average queue sizes responsive to the congestion control process using the average queue size to determine the drop probability, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside a queue law function defined for the queue; and

computer code providing a feedback mechanism for forwarding the determined drop probability to the sender to control the sender'"'"'s transmission of packets such that a desired drop probability is attained.

18. The computer program product according to claim 17, wherein the computer code for systematically calculating a weight comprises:

computer code for determining a sampling period for measuring the queue size;

computer code for determining a time period for which samples significantly contribute to the average queue size; and

computer code for determining the weight based upon the sampling period and the time period.

19. The computer program product according to claim 17, wherein the computer code for determining the control function comprises:

computer code for determining the queue function based upon predetermined system parameters; and

computer code for determining the control function based upon the queue function.

20. The computer program product according to claim 19 wherein the computer code for determining the control function further comprises:

computer code for selecting a queue policy;

computer code for determining a threshold value based upon the selected queue policy computer code for determining a maximum point based upon the threshold value, wherein the maximum point is outside of the queue function computer code for selecting the control function such that when the control function is evaluated a point passes through the maximum point.

21. The computer program product according to claim 20 wherein the queue policy is a delay conservative policy and wherein the computer code for determining a threshold value comprises:

computer code for determining a maximum value for the average queue size.

22. The computer program product according to claim 20 wherein the queue policy is a drop conservative policy and wherein the computer code for determining a threshold value comprises:

computer code for determining a maximum value for the drop probability.

23. A computer program product for reducing oscillations in queue size in a node using a congestion control process that operates in a TCP environment, wherein the computer program product has computer code on a computer readable medium, the computer code comprising:

computer code for determining a queue law function defining a range of packet drop probabilities across a range of queue sizes using the congestion control process;

computer code for defining a control function which defines a drop probability for a range of average queue sizes, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside the queue law function; and

computer code for selecting a packet drop rate equal in response to the packet drop probability defined at a point of intersection of the control function and the queue law function.

24. The computer program product according to claim 23, wherein the computer code for defining the control function, the control function is further defined as a function having no discontinuities.

25. The computer program product according to claim 23, wherein the function is piecewise linear.

26. A computer program product for increasing utilization of a link capable of receiving a number of flows into a buffer, the link residing in a TCP network, the link having a congestion control module which drops packets to avoid buffer overflow according to a congestion control process, wherein the computer program product has computer code on a computer readable medium, the computer code comprising:

computer code for determining a quantity representative of a capacity for the link;

computer code for calculating a quantity representative of the throughput for the link;

computer code for determining the utilization based on the capacity of the link;

the throughput the link, the number of flows and a packet drop probability associated with the congestion control process; and

computer code for automatically adjusting the packet drop probability in accordance with a control function to maintain a desired utilization of the link, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside a queue law function defined for the queue.

27. A computer product for executing a congestion control process in a server having a queue which resides in a network wherein each data transmission from a sender to a receiver is sent at a transmission rate and the data transmission is acknowledged by the receiver, wherein if the data transmission is not acknowledged the sender reduces the transmission rate, wherein the computer program product has computer code on a computer readable medium, the computer code comprising:

computer code for ascertaining a network function which defines an average queue size of the queue based upon a range of server drop rates for the congestion control process;

computer code for determining a control function for the server which defines an average queue size based upon a range of given server drop rates, the control function having a first segment which defines expected operational range of the average queue size and a second segment which defines overload operation for the average queue size, wherein the first segment has a maximum value which lies outside the network function; and

computer code for calculating an equilibrium point based upon the intersection of the network function and control function.