System performance in a data network through queue management based on ingress rate monitoring

• US 6,252,848 B1
• Filed: 03/22/1999
• Issued: 06/26/2001
• Est. Priority Date: 03/22/1999
• Status: Expired due to Term

• Current Assignee: Parity Networks LLC
• Original Assignee: Pluris, Inc
• Inventors: Skirmont, David A.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/273,847
• Time in Patent Office: 827 Days
• Field of Search: 370/465, 370/234-236, 370/400, 370/253, 370/342, 370/229, 370/395, 370/232-235, 370/474, 375/142, 714/20-26, 714/47, 714/57, 709/103, 709/228, 709/229, 345/965, 345/418
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• 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/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method optimizes performance in a data network including a plurality of ingress ports and output queues. Ingress rates of a plurality of flows are monitored, where each flow includes a sequence of packets passing from an ingress port to an output queue and each flow has a profile related to flow characteristics. Each packet is marked with a marking based on criteria including the ingress flow rate and the flow profile. A drop probability of each packet is adjusted at an output queue according to a value of a drop function taken as a function of a queue size. The drop function is selected according to the marking on the packet. The drop functions are zero for queue sizes less than a lower threshold range and positive for queue sizes greater than the lower threshold range. By selecting drop functions according to ingress flow rate measurements and flow profiles, the data network can be optimized for overall system performance.

Claims

1. A method for optimizing performance in a data network including a plurality of ingress ports and output queues, each of the plurality of ingress ports receiving packets from a plurality of flows, comprising the steps of:

monitoring ingress rates of a plurality of flows, each flow including a plurality of packets passing from an ingress port to an output queue, each flow having a profile related to flow characteristics;

marking each packet with one of a plurality of flow markings based on criteria including the ingress rate and the flow profile;

adjusting a drop probability of each packet at an output queue, according to a value of a drop function taken as a function of a queue size, the drop function being selected from a plurality of drop functions, each drop function being associated with one of the plurality of markings, wherein

the drop functions are zero for queue sizes less than a lower threshold range, and

the drop functions are positive for queue sizes greater than the lower threshold range.

2. The method of claim 1, wherein

the lower threshold range has a smallest value that is greater than 60% of a lower RED threshold value, and

the lower threshold range has a largest value that is less than the sum of 40% of the lower RED threshold value and 60% of a maximum average buffer size of the network.

3. The method of claim 1, wherein

the lower threshold range has a smallest value that is greater than 20% of a lower RED threshold value, and

the lower threshold range has a largest value that is less than the sum of 80% of the lower RED threshold value and 20% of a maximum average buffer size of the network.

4. The method of claim 1, wherein the lower threshold range consists of a lower threshold value.

5. The method of claim 1, wherein

the drop functions are uniformly one for queue sizes greater than an upper threshold range.

6. The method of claim 5, wherein

the lower threshold range has a smallest value that is greater than 60% of a lower RED threshold value,

the lower threshold range has a largest value that is less than the sum of 40% of the lower RED threshold value and 60% of a maximum average buffer size of the network,

the upper threshold range has a smallest value that is greater than 60% of an upper RED threshold value, and

the upper threshold range has a largest value that is less than the sum of 40% of the upper RED threshold value and 60% of the maximum average buffer size of the network.

7. The method of claim 5, wherein

the lower threshold range has a smallest value that is greater than 20% of a lower RED threshold value, and

the lower threshold range has a largest value that is less than the sum of 80% of the lower RED threshold value and 20% of a maximum average buffer size of the network.

the upper threshold range has a smallest value that is greater than 20% of an upper RED threshold value, and

the upper threshold range has a largest value that is less than the sum of 80% of the upper RED threshold value and 20% of the maximum average buffer size of the network.

8. The method of claim 5, wherein

the lower threshold range consists of a lower threshold value, and

the upper threshold range consists of an upper threshold value.

9. The method of claim 8, wherein the drop functions are linear functions for queue sizes between the upper threshold value and the lower threshold value.

10. The method of claim 1, wherein the drop functions are non-decreasing functions of queue size.

11. The method of claim 1, wherein the plurality of drop functions includes functions identified for “

low marking”

, “

normal marking”

, and “

high marking.”

12. The method of claim 1, wherein the flow profile includes an average rate, a burst rate and a burst length.

13. The method of claim 1, wherein the flow profile includes at least one of an average rate, a burst rate and a burst length.

14. The method of claim 1, wherein the monitoring of ingress rates includes a leaky-bucket algorithm.

15. A method for optimizing performance independently of user in a data network including a plurality of ingress ports and output queues, each of the plurality of ingress ports receiving packets from a plurality of flows, comprising the steps of:

monitoring ingress rates of a plurality of flows, each flow including a plurality of packets passing from an ingress port to an output queue, each flow having a profile related to flow characteristics;

marking each packet with one of a plurality of flow markings based on criteria including the ingress rate and the flow profile;

adjusting a drop probability of each packet at an output queue, according to a value of a drop function taken as a function of a queue size, the drop function being selected from a plurality of drop functions, each drop function being associated with one of the plurality of markings.

16. The method of claim 15, wherein the drop functions are zero for queue sizes less than a lower threshold value.

17. The method of claim 16, wherein the drop functions are one for queue sizes greater than an upper threshold value.

18. The method of claim 17, wherein the drop functions are linear functions for queue sizes between the upper threshold value and the lower threshold value.

19. The method of claim 15, wherein the drop functions are non-decreasing functions of queue size.

20. The method of claim 15, wherein the plurality of drop functions includes functions identified for “

low marking”

, “

normal marking”

, and “

high marking.”

21. The method of claim 15, wherein the flow profile includes an average rate, a burst rate and a burst length.

22. The method of claim 15, wherein the flow profile includes at least one of an average rate, a burst rate and a burst length.

23. The method of claim 15, wherein the monitoring of ingress rates includes a leaky-bucket algorithm.

24. A method for optimizing performance in a data network including a plurality of ingress ports and output queues, each of the plurality of ingress ports receiving packets from a plurality of flows, comprising the steps of:

monitoring ingress rates of a plurality of flows, each flow including a plurality of packets passing from an ingress port to an output queue, each flow having a profile related to flow characteristics;

marking each packet with one of a plurality of flow markings based on criteria including the ingress rate and the flow profile;

adjusting a drop probability of each packet at an output queue, according to a value of a drop function taken as a function of a queue size, the drop function being selected from a plurality of drop functions, each drop function being associated with one of the plurality of markings, the plurality of drop functions including functions identified for “

low marking”

, “

normal marking”

, and “

high marking.”

25. The method of claim 24, wherein the drop functions are zero for queue sizes less than a lower threshold value.

26. The method of claim 25, wherein the drop functions are one for queue sizes greater than an upper threshold value.

27. The method of claim 26, wherein the drop functions are linear functions for queue sizes between the upper threshold value and the lower threshold value.

28. The method of claim 24, wherein the drop functions are non-decreasing functions of queue size.

29. The method of claim 24, wherein the flow profile includes an average rate, a burst rate and a burst length.

30. The method of claim 24, wherein the flow profile includes at least one of an average rate, a burst rate and a burst length.

31. The method of claim 24, wherein the monitoring of ingress rates includes a leaky-bucket algorithm.