Systems and methods for dropping data using a drop profile

• US 9,106,577 B2
• Filed: 02/12/2014
• Issued: 08/11/2015
• Est. Priority Date: 01/25/2002
• Status: Active Grant

• 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:
  US14/178,815
• Publication Number:
  US 20140160933A1
• Time in Patent Office: 545 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: 1/1
• 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 method comprising:

identifying, by a device and for a queue, a drop probability using an index;

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

determining whether to drop the data 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; and

processing, by the device, the data at the head of the queue based on determining whether to drop the data.

2. The method of claim 1, further comprising:

receiving information identifying a pending visit value associated with the queue; and

selecting the queue based on the information identifying the pending visit value.

3. The method of claim 1, further comprising:

receiving first information identifying a first vector;

receiving second information identifying a second vector; and

selecting the queue based on the first information and the second information.

4. The method of claim 1, further comprising:

determining if a relationship between an amount of memory used by the queue and an allocated amount of memory is greater than a threshold value; and

determining, when the relationship is greater than the threshold value, if the data includes information indicating that the data should not be dropped.

5. The method of claim 4, further comprising:

marking, when the data includes the information indicating that the data should not be dropped, the data with an indication that the data should not be dropped.

6. The method of claim 1, further comprising:

determining if a relationship between an amount of memory used by the queue and an allocated amount of memory is greater than a threshold value,

where, when identifying the drop probability, the method includes;

identifying the drop probability when the relationship is less than the threshold value.

7. The method of claim 1, where, when processing the data, the method includes:

marking, when the identified drop probability is greater than the random number, the data with an indication that the data should be dropped, or

marking, when the identified drop probability is not greater than the random number, the data with an indication that the data should not be dropped.

8. A device comprising:

a memory to store instructions; and

a processor to execute the instructions to;

identify, for a queue, a drop probability using an index;

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

the processor, when determining whether to drop the data, being further 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; and

process the data at the head of the queue based on determining whether to drop the data.

9. The device of claim 8, where the processor is further to:

receive information identifying a pending visit value associated with the queue; and

select the queue based on the information identifying the pending visit value.

10. The device of claim 8, where the processor is further to:

receive first information identifying a first vector;

receive second information identifying a second vector; and

select the queue based on the first information and the second information.

11. The device of claim 8, where the processor is further to:

determine if a relationship between an amount of memory used by the queue and an allocated amount of memory is greater than a threshold value; and

determine, when the relationship is greater than the threshold value, if the data includes information indicating that the data should not be dropped.

12. The device of claim 11, where the processor is further to:

mark, when the data includes the information indicating that the data should not be dropped, the data with an indication that the data should not be dropped.

13. The device of claim 8, where

the processor is further to:

determine if a relationship between an amount of memory used by the queue and an allocated amount of memory is greater than a threshold value, and

the processor, when identifying the drop probability, is further to;

identify the drop probability when the relationship is less than the threshold value.

14. The device of claim 8, where the processor, when processing the data, is further to:

mark, when the identified drop probability is greater than the random number, the data with an indication that the data should be dropped, or

mark, when the identified drop probability is not greater than the random number, the data with an indication that the data should not be dropped.

15. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions which, when executed by a processor, cause the processor to;

identify, for a queue, a drop probability using an index;

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

the processor, when determining whether to drop the data, being further 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; and

process the data at the head of the queue based on determining whether to drop the data.

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

one or more instructions to receive information identifying a pending visit value associated with the queue; and

one or more instructions to select the queue based on the information identifying the pending visit value.

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

one or more instructions to receive first information identifying a first vector;

one or more instructions to receive second information identifying a second vector; and

one or more instructions to select the queue based on the first information and the second information.

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

one or more instructions to determine if a relationship between an amount of memory used by the queue and an allocated amount of memory is greater than a threshold value;

one or more instructions to determine, when the relationship is greater than the threshold value, if the data includes information indicating that the data should not be dropped; and

one or more instructions to mark, when the data includes the information indicating that the data should not be dropped, the data with an indication that the data should not be dropped.

19. The non-transitory computer-readable medium of claim 15, where

the instructions further include:

one or more instructions to determine if a relationship between an amount of memory used by the queue and an allocated amount of memory is greater than a threshold value, and

the one or more instructions to identify the drop probability include;

one or more instructions to identify the drop probability when the relationship is less than the threshold value.

20. The non-transitory computer-readable medium of claim 15, where the one or more instructions to process the data further include:

one or more instructions to mark, when the identified drop probability is greater than the random number, the data with an indication that the data should be dropped, or one or more instructions to mark, when the identified drop probability is not greater than the random number, the data with an indication that the data should not be dropped.