Systems and methods for dropping data using a drop profile

• US 8,654,645 B2
• Filed: 12/17/2012
• Issued: 02/18/2014
• Est. Priority Date: 01/25/2002
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Sindhu, Pradeep, Basu, Debashis, Boddu, Jayabharat, Godbole, Avanindra
• Primary Examiner(s): Zhu, Alvin
• Application Number:
  US13/717,060
• Publication Number:
  US 20130128734A1
• Time in Patent Office: 428 Days
• Field of Search: 370/230, 370/230.1, 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/235
• 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 comprising:

a plurality of queues to store data; and

a processor to;

select a queue of the plurality of queues to examine,

store a drop table that includes a plurality of drop probabilities,

generate an index into the drop table based on an amount of data stored by the selected queue,

identify, using the generated index, a drop probability of the plurality of drop probabilities in the drop table, and

determine whether to drop data, from a head of the selected queue, based on the identified drop probability,

the processor, when determining whether to drop the data, being to;

compare the identified drop probability to a random number,

 

the random number having a greater number of bits than a number of bits in the identified drop probability, and

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

2. The system of claim 1, where the processor, when storing the drop table, is further to:

store a plurality of drop tables, each of which is to store two or more of the plurality of drop probabilities.

3. The system of claim 2, where the processor is further to:

select one drop table of the plurality of drop tables, and

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

4. The system of claim 3, where, when selecting the one drop table, the processor is to:

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

5. The system of claim 1, where the processor is to:

determine whether to drop data from the head of the selected queue based on the identified drop probability and other data including information extracted from the data,

the other data including an attribute that indicates whether the data should be dropped.

6. The system of claim 1, where the processor is further to:

determine to drop the data when the random number is less than the identified drop probability.

7. The system of claim 1, where the processor is to:

determine not to drop the data when the generated index is less than or equal to an index threshold.

8. A method comprising:

selecting, by a device, a queue of a plurality of queues;

providing, by the device, a drop table associated with the selected queue,

the drop table storing a plurality of drop probabilities;

determining, by the device, an amount of data stored by the selected queue;

generating, by the device, an index into the drop table based on the determined amount of data;

identifying, by the device, a drop probability of the plurality of drop probabilities, stored in the drop table, using the generated index; and

determining, by the device and based on the identified drop probability, whether to drop data from a head of the selected queue,

the determining including;

comparing the identified drop probability to a random number,

the random number having a greater number of bits than a number of bits in the identified drop probability, and

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

9. The method of claim 8, where

the drop table includes a plurality of drop tables, each of the plurality of drop tables storing two or more drop probabilities and

the method further comprises:

selecting a drop table of the plurality of drop tables, and

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

10. The method of claim 9, where selecting the drop table includes:

using one or more attributes of the data, in the head of the selected queue, to select among the plurality of drop tables.

11. The method of claim 8, further including:

generating the random number.

12. The method of claim 8, where the determining whether to drop data includes:

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

13. The method of claim 8, further comprising:

establishing an index threshold,

where the determining whether to drop data includes;

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

14. A non-transitory computer-readable medium including instructions executable by one or more processors, the instructions comprising:

one or more instructions that, when executed by the one or more processors, cause the one or more processors to;

select a queue of a plurality of queues to examine,

store a drop table that includes a plurality of drop probabilities,

generate an index into the drop table, based on an amount of memory used by the selected queue, to identify a drop probability of the drop probabilities, and

determine whether to drop data from a head of the selected queue based on the identified drop probability,

the one or more instructions to determine whether to drop the data including instructions to;

compare the identified drop probability to a random number,

 

the random number having a greater number of bits than a number of bits in the identified drop probability, and

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

15. The computer-readable medium of claim 14, where the instructions further include:

one or more instructions to store a plurality of drop tables, each of which is configured to store two or more drop probabilities.

16. The computer-readable medium of claim 14, where the instructions further include:

one or more instructions to;

generate the random number.

17. The computer-readable medium of claim 14, where the instructions further include:

one or more instructions to determine whether to drop data from the head of the selected based on the identified drop probability and other data including information extracted from the data,

the other data including an attribute that indicates whether the data should be dropped.

18. The computer-readable medium of claim 14, where the instructions further include:

one or more instructions to determine not to drop the data when the generated index is less than or equal to an index threshold.

19. The computer-readable medium of claim 14, where

the drop table includes a plurality of drop tables, each of the plurality of drop tables storing two or more drop probabilities, and

the instructions further include:

one or more instructions to select a drop table of the plurality of drop tables, and

one or more instructions to identify one of the two or more drop probabilities in the selected drop table using the generated index.

20. The computer-readable medium of claim 19, where the one or more instructions to select the drop table of the plurality of drop tables include:

one or more instructions to use one or more attributes of the data, in the head of the selected queue, to select among the plurality of drop tables.