Method and apparatus for queue modeling

• US 7,149,664 B1
• Filed: 05/25/2000
• Issued: 12/12/2006
• Est. Priority Date: 06/02/1999
• Status: Expired due to Fees

• Current Assignee: Avaya Holdings Corporation (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Firoiu, Victor, Borden, Marty
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US09/579,169
• Time in Patent Office: 2,392 Days
• Field of Search: 703/2, 703/22, 703/13, 703/20, 370/229, 370/223, 370/395, 370230-236, 709/223, 709/224, 709/226, 709/229, 709/235, 702/2
• US Class Current: 703/2
• 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: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/54 Loss aware scheduling
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A method, apparatus, and computer program product for modeling dynamics of a queue are disclosed. A queue law function can be used to determine a control function for use in a congestion control module in a network for dropping packets. A queue law function may be determined based upon traffic conditions in the network. First a quantity that is representative of the link utilization between first and second nodes is determined. If the link is fully utilized, a quantity that is representative of an average round transmission trip time for data to be sent from the first node to the second node and an acknowledgment to be received by the first node is calculated. The queue law function which is dependent on a data drop probability based upon the link utilization, the buffer size, and the average round trip transmission time is determined. From this queue law function, parameters for defining a control function can be derived. These parameters include the minimum buffer size and the maximum expected queue size during normal operation for the node.

Claims

1. A method for operating a second, sending network node relative to a first, receiving network node, the receiving node being operable to receive data packets sent by the sending node via a plurality of flows, the method comprising:

determining a queue law function of the first, receiving node based upon predetermined system traffic conditions, the queue law function being representative of average queue size of an exemplary queue of the receiving node based on traffic conditions and percentage of dropped packets; and

determining a control function for the second, sending node based upon the queue law function, the control function defining a drop percentage when a buffer of the second node is filled above a predetermined threshold based upon an average queue size, wherein the control function prompts a gradual increase of drop probability of all data packets in flows bound for the receiving network node in an overload condition defined by intersection of the queue law function and the control function,

whereby each flow between the sending node and receiving node is proportionally affected regardless of sending rate of particular flows.

2. A method according to claim 1, wherein the control function is a random early detection control function.

3. A method according to claim 1, wherein the control function does not have a non-bounded discontinuity.

4. A method according to claim 1, wherein the control function comprises two piecewise linear segments.

5. A method for modeling dynamics of a queue in a first, sending node having a buffer in order to determine a steady-state operating point of the first node relative to a second, receiving node, the receiving node being operable to receive data packets sent by the sending node via a plurality of flows, the method comprising:

calculating a queue law function dependent on traffic conditions at the second node, the queue law function being representative of average queue size of an exemplary queue of the receiving node based on traffic conditions and percentage of dropped packets; and

determining a point of operation for the first node as the intersection of the queue law function and a predetermined control function for the first node, the control function defining a drop percentage when a buffer of the second node is filled above a predetermined threshold based upon an average queue size,

wherein the control function increases drop probability of all data packets in flows bound for the receiving network node gradually in an overload condition,

whereby each flow between the sending node and receiving node is proportionally affected regardless of sending rate of particular flows.

6. A method according to claim 5, wherein the point of operation defines a packet drop percentage for dropping a percentage of packets from the buffer.

7. A method for improving congestion control according to claim 5, wherein the node resides in a network.

8. A method for improving congestion control according to claim 7, wherein the network operates in a TCP environment.

9. A method for improving congestion control according to claim 5, wherein data received at a node is acknowledged.

10. A method according to claim 5, wherein the traffic conditions which determine the queue law function are the number of flows into the node, an average packet size and an average round trip transmission time.

11. A method according to claim 5, wherein the function is determined by assuming that the node does not experience feedback.

12. A method according to claim 5, wherein the point of operation determines a drop rate.

13. A method according to claim 5, further comprising:

dropping packets from the buffer at the determined drop rate.