Systems and method for dropping data using a drop profile

• US 7,746,776 B1
• Filed: 09/11/2007
• Issued: 06/29/2010
• Est. Priority Date: 01/25/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): Patel; Jayanti K
• Assistant Examiner(s): ZHU, BO HUI ALVIN
• Application Number:
  US11/853,190
• Time in Patent Office: 1,022 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/23 Bit dropping
• 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/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A system selectively drops data from queues. The system includes a drop table that stores drop probabilities. The system selects one of the queues to examine and generates an index into the drop table to identify one of the drop probabilities for the examined queue. The system then determines whether to drop data from the examined queue based on the identified drop probability.

Claims

1. A system for selectively dropping data from a queue, the system comprising:

a plurality of queues to temporarily store data; and

a drop engine to select one of the queues to examine, the drop engine comprising;

a drop table to store a plurality of drop probabilities,

indexing logic to generate an index into the drop table based on an amount of memory used by the examined queue, and identify one of the drop probabilities in the drop table using the generated index, and

drop decision logic to determine whether to drop data from a head of the examined queue based on the identified drop probability, where the drop decision logic includes;

a random number generator to generate a random number,

a comparator to;

compare the identified drop probability to the random number, and

generate a drop decision based on a result of the comparison, and

a logic operator to;

perform a logical operation on the result of the comparison and a signal based on an attribute extracted from the data, and

output, based on the logical operation, a decision signal that indicates whether to drop data from the examined queue.

2. The system of claim 1, where, when generating the index, the indexing logic is to:

determine a static amount of memory allocated to the examined queue,

determine the amount of memory used by the examined queue, and

determine the index into the drop table based on the static amount of memory allocated to the examined queue and the amount of memory used by the examined queue.

3. The system of claim 2, where when determining the index, the indexing logic is to:

generate the index based on a ratio of the amount of memory used by the examined queue to a maximum of the static amount of memory allocated to the examined queue and the amount of memory that should be made available to the examined queue.

4. The system of claim 1, where the drop table includes:

a plurality of drop tables, each drop table of the plurality of drop tables to store a plurality of drop probabilities.

5. The system of claim 4, where the indexing logic is further to:

select one of the drop tables, and

identify one of the drop probabilities in the selected drop table using the generated index.

6. The system of claim 5, where when selecting one of the drop tables, the indexing logic is to:

use one or more attributes of the data to select among the drop tables.

7. The system of claim 5, where the attributes include one or more of a Transmission Control Protocol or a Packet Level Protocol relating to the data.

8. The system of claim 1, where the logic operator is an AND gate.

9. The system of claim 1, where the drop decision logic is to:

determine whether to drop data from the examined queue based on the identified drop probability and other information including information extracted from the data.

10. The system of claim 8, where the information includes an attribute that indicates that the data should not be dropped.

11. The system of claim 1, where the drop probability is based on a ratio of an amount of memory being used by the examined queue to one of a maximum of a static amount of memory allocated to the examined queue or an amount of memory that should be made available to the examined queue.

12. The system of claim 11, where the drop decision logic is to:

identify the data for dropping when the amount of memory being used by the examined queue is greater than the maximum of the static amount of memory allocated to the examined queue and the amount of memory that should be made available to the examined queue.

13. The system of claim 1, where the drop decision logic is to:

determine not to drop the data when the index generated by the indexing logic is below an index threshold.

14. A method for selectively dropping data from each of a plurality of queues that temporarily store data, the method comprising:

selecting one of the queues to examine;

providing a drop table associated with the selected queue, where the drop table stores a plurality of drop probabilities;

determining an amount of memory used by the selected queue,

generating an index into the drop table based on the determined amount of memory, and

identifying one of the drop probabilities in the drop table using the generated index; and

determining whether to drop data from a head of the examined queue based on the identified drop probability, where determining whether to drop data from the head of the examined queue includes;

generating a random number,

comparing the identified drop probability to the random number,

performing a logical operation on the result of the comparison and a signal that is generated based on an attribute extracted from the data, and

outputting, based on the logical operation, a decision signal that indicates whether to drop data from the selected queue.

15. The method of claim 14, where the generating the index includes:

determining a static amount of memory allocated to the selected queue, and

generating the index into the drop table based on the static amount of memory allocated to the selected queue and the amount of memory used by the selected queue.

16. The method of claim 15, where the generating the index includes:

generating the index based on a ratio of the amount of memory used by the selected queue to one of;

a maximum of the static amount of memory allocated to the selected queue, or the amount of memory that should be made available to the selected queue.

17. The method of claim 14, where the drop table includes a plurality of drop tables, each drop table of the plurality of drop tables to store a plurality of drop probabilities;

and

where the method further comprises;

selecting one of the drop tables, and

identifying one of the drop probabilities in the selected drop table using the generated index.

18. The method of claim 17, where the selecting one of the drop tables includes:

using one or more attributes of the data to select among the drop tables.

19. The method of claim 14, where the performing the logical operation includes:

ANDing the result of the comparison and the signal.

20. The method of claim 14, where the determining whether to drop data includes:

determining whether to drop the data from the selected queue based on the identified drop probability and other information including information extracted from the data.

21. The method of claim 14, further comprising:

establishing an index threshold; and

where the determining whether to drop data includes;

determining not to drop the data when the index is below the index threshold.