Systems and methods for selectively performing explicit congestion notification

• US 7,359,321 B1
• Filed: 07/30/2002
• Issued: 04/15/2008
• Est. Priority Date: 01/17/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Basu, Debashis, Godbole, Avanindra, Sindhu, Pradeep, Boddu, Jayabharat
• Primary Examiner(s): Phunkulh; Bob A.
• Application Number:
  US10/206,990
• Time in Patent Office: 2,086 Days
• Field of Search: None
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• 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/35 by embedding flow control information in regular packets, e.g. piggybacking

Abstract

A system provides congestion control and includes multiple queues that temporarily store data and a drop engine. The system associates a value with each of the queues, where each of the values relates to an amount of memory associated with the queue. The drop engine compares the value associated with a particular one of the queues to one or more programmable thresholds and selectively performs explicit congestion notification or packet dropping on data in the particular queue based on a result of the comparison.

Claims

1. A system for providing congestion control, comprising:

a plurality of queues to temporarily store data, a value being associated with each of the queues, each of the values relating to an amount of memory associated with the queue; and

a drop engine to;

compare the value associated with a particular one of the queues to first and second programmable thresholds,

perform selective explicit congestion notification on data in the particular queue based on a first drop probability when the value is greater than the first threshold but less than or equal to the second threshold, and

perform selective dropping of the data in the particular queue based on a second drop probability when the value is greater than the second threshold.

2. The system of claim 1, wherein the value relates to an amount of memory used by the particular queue.

3. The system of claim 1, wherein the value relates to an amount of memory allocated to the particular queue.

4. The system of claim 1, wherein the value relates to an amount of memory used by the particular queue divided by a maximum of an amount of memory statically and dynamically allocated to the particular queue.

5. The system of claim 1, wherein when performing selective dropping of the data, the drop engine:

obtains the second drop probability corresponding to the particular queue, and

determines whether to drop the data based on the second drop probability.

6. The system of claim 5, further comprising:

a drop table configured to store a plurality of the second drop probabilities.

7. The system of claim 6, wherein when obtaining the second drop probability, the drop engine:

generates an index for the drop table based on an amount of memory used by the particular queue, and

reads one of the second drop probabilities from the drop table using the generated index.

8. The system of claim 7, wherein when selectively dropping the data, the drop engine:

compares the second drop probability with a random number, and

generates a drop decision based on a result of the comparison.

9. The system of claim 1, wherein when performing selective dropping of the data, the drop engine:

determines whether the data includes an attribute that indicates that the data should not be dropped, and

marks the data as not to be dropped when the data includes the attribute.

10. The system of claim 1, wherein when the value is less than or equal to the first threshold, the drop engine is configured to:

perform no explicit congestion notification and no dropping of the data in the particular queue.

11. The system of claim 1, wherein when performing selective explicit congestion notification, the drop engine:

obtains the first drop probability corresponding to the particular queue, and

determines whether to perform the explicit congestion notification based on the first drop probability.

12. The system of claim 11, wherein when performing explicit congestion notification, the drop engine:

sets a field relating to the data to indicate that congestion exists, and

marks the data for transmission without being dropped.

13. The system of claim 1, wherein when the value is greater than a predetermined value that is greater than the second threshold, the drop engine:

drops the data from the particular queue.

14. A method for providing congestion control, comprising:

temporarily storing data in a plurality of queues;

associating a value with each of the queues, each of the values relating to an amount of memory associated with the queue;

comparing the value associated with a particular one of the queues to first and second programmable thresholds;

performing no explicit congestion notification and no dropping of data in the particular queue when the value is less than or equal to the first threshold;

selectively performing explicit congestion notification on data in the particular queue when the value is greater than the first threshold but less than or equal to the second threshold; and

selectively performing dropping of data in the particular queue when the value is greater than the second threshold.

15. The method of claim 14, wherein each of the values relates to an amount of memory used by the associated queue.

16. The method of claim 14, wherein each of the values relates to an amount of memory allocated to the associated queue.

17. The method of claim 14, wherein each of the values relates to an amount of memory used by the associated queue divided by a maximum of an amount of memory statically and dynamically allocated to the associated queue.

18. The method of claim 14, wherein the selectively performing dropping of the data includes:

obtaining a drop probability corresponding to the particular queue, and

determining whether to drop the data based on the drop probability.

19. The method of claim 18, further comprising:

providing a drop table configured to store a plurality of drop probabilities.

20. The method of claim 19, wherein the obtaining a drop probability includes:

generating an index for the drop table based on an amount of memory used by the particular queue, and

reading one of the drop probabilities from the drop table using the generated index.

21. The method of claim 20, wherein the selectively performing dropping of the data includes:

comparing the drop probability with a random number, and

generating a drop decision based on a result of the comparison.

22. The method of claim 14, wherein the selectively performing dropping of the data includes:

determining whether the data includes an attribute that indicates that the data should not be dropped, and

marking the data as not to be dropped when the data includes the attribute.

23. The method of claim 14, wherein the selectively performing explicit congestion notification includes:

obtaining a drop probability corresponding to the particular queue, and

determining whether to perform the explicit congestion notification based on the drop probability.

24. The method of claim 23, wherein the selectively performing explicit congestion notification further includes:

setting a field relating to the data to indicate that congestion exists, and

marking the data for transmission without being dropped.

25. The method of claim 14, further comprising:

dropping the data from the particular queue when the value is greater than a predetermined value that is greater than the second threshold.

26. A network device, comprising:

a switching fabric;

a first processor to;

receive data from a network, and

transmit data to the network;

a second processor to;

receive data from the switching fabric, and

transmit data to the switching fabric; and

a memory subsystem to facilitate communication between the first processor and the second processor, the memory subsystem comprising;

a plurality of queues for temporarily storing the data received by the first and second processors, a value being associated with each of the queues, each of the values relating to an amount of memory associated with the queue,

a dequeue engine configured to dequeue data from the queues, and

a drop engine to;

compare the value associated with a particular one of the queues to first and second programmable thresholds,

perform no explicit congestion notification and no dropping of data in the particular queue when the value is less than or equal to the first threshold,

selectively perform explicit congestion notification on data in the particular queue when the value is greater than the first threshold but less than or equal to the second threshold, and

selectively drop data in the particular queue when the value is greater than the second threshold.

27. A method comprising:

determining an amount of memory associated with one of a plurality of queues;

generating a value based on the amount of memory associated with the queue;

comparing the value to first and second programmable thresholds;

performing no explicit congestion notification and no dropping of data in the queue when the value is less than or equal to the first threshold;

performing selective explicit congestion notification on data in the queue when the value is greater than the first programmable threshold but less than or equal to the second programmable threshold; and

selectively dropping data from the queue when the value is greater than the second programmable threshold.

28. The method of claim 27, wherein the performing selective explicit congestion notification includes:

obtaining the first drop probability corresponding to the queue, and

determining whether to perform the explicit congestion notification based on the first drop probability.

29. The method of claim 28, wherein the performing selective explicit congestion notification further includes:

setting a field relating to the data to indicate that congestion exists, and

marking the data for transmission without being dropped.

30. The method of claim 27, wherein the selectively dropping the data includes:

obtaining a second drop probability corresponding to the queue, and

determining whether to drop the data based on the second drop probability.

31. The method of claim 30, wherein the selectively dropping the data includes:

comparing the drop probability with a random number, and

generating a drop decision based on a result of the comparison.

32. The method of claim 27, wherein the selectively dropping the data includes:

determining whether the data includes an attribute that indicates that the data should not be dropped, and

marking the data as not to be dropped when the data includes the attribute.

33. A device for performing congestion control, comprising:

a plurality of queues to temporarily store data; and

a drop engine to;

determine an amount of memory associated with a first one of the queues,

generate a value based on the amount of memory associated with the first queue,

compare the value to first and second programmable thresholds,

perform no explicit congestion notification and no packet dropping on the data in the first queue when the value is less than or equal to the first threshold,

perform selective explicit congestion notification on the data in the first queue when the value is greater than the first threshold but less than or equal to the second threshold, and

selectively drop the data in the first queue when the value is greater than the second threshold.

34. The device of claim 33, wherein when performing selective explicit congestion notification, the drop engine:

obtains a drop probability corresponding to the first queue, and

determines whether to perform explicit congestion notification based on the drop probability.

35. The device of claim 34, wherein when performing explicit congestion notification, the drop engine:

sets a field relating to the data to indicate that congestion exists, and

marks the data for transmission without being dropped.

36. The device of claim 33, wherein when selectively dropping the data, the drop engine:

obtain a drop probability corresponding to the first queue, and

determine whether to drop the data based on the drop probability.

37. The device of claim 36, wherein when selectively dropping the data, the drop engine:

compares the drop probability with a random number, and

generates a drop decision based on a result of the comparison.

38. The device of claim 33, wherein when selectively dropping the data, the drop engine:

determine whether the data includes an attribute that indicates that the data should not be dropped, and

marks the data as not to be dropped when the data includes the attribute.

39. The device of claim 33, wherein the drop engine:

drops the data from the first queue when the value is greater than a predetermined value that is greater than the second threshold.

40. The device of claim 33, wherein the selective dropping occurs to protect the device from denial of service attacks.