Random early packet discard (RED)

• US 20040179473A1
• Filed: 03/13/2003
• Published: 09/16/2004
• Est. Priority Date: 03/13/2003
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Thibodeau, Mark, Du, Bin
• Granted Patent: US 7,636,307 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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/326 with random discard, e.g. random early discard [RED]

Abstract

At telecommunications switches and routers, RED (random early packet discard) uses the queue depth to determine whether to keep or discard each packet as it arrives at a queue. This is done by determining a discard probability (P), which is dependent on the average depth of the queue, and comparing the discard probability to a random number. One way of performing the invention uses the summed discard probabilities, instead of counting the number of packets (count) and multiplying that by the current discard probability, as in the prior art. The resulting sum is compared to the random number for discard operation. The disclosure further describes a more accurate way of calculating average depth of a queue, especially when the queue encounters periods of idleness.

Claims

1. A method of controlling a queue of a communications system, comprising steps of:

(a) deciding an accept/discard operation on a packet arriving at the queue, based on comparison between a discard probability sum for the packet and a random variable;

(b) calculating a discard probability for the packet, using an average depth of the queue, and

(c) generating a new discard probability sum for a next packet arriving at the queue, by summing the discard probability sum and the calculated discard probability.

2. The method according to claim 1, further comprising a step of:

(d) accepting a packet arriving at the queue if a discard probability sum for the packet is smaller than or equal to a random variable.

3. The method according to claim 1, further comprising steps of:

(e) discarding the packet arriving at the queue if the discard probability sum for the packet is larger than the random variable;

(f) setting the discard probability sum to zero, and

(g) generating another random variable to replace the aforementioned random variable.

4. The method according to claim 2, further comprising steps of:

repeating steps (a) to (d) for each packet arriving at the queue;

discarding a packet arriving at the queue the most recently, if the discard probability sum for the most recent packet is larger than the random variable;

setting the discard probability sum to zero;

generating another random variable to replace the aforementioned random variable, and

repeating steps (a) to (d) for further packets arriving at the queue.

5. The method according to claim 4, further comprising steps of:

calculating the average depth of the queue every time a new packet arrives at the queue, and

calculating the discard probability for the newly arrived packet based on the calculated average depth of the queue.

6. The method according to claim 5 wherein the step of calculating the average depth of the queue comprises further steps of:

measuring a current queue depth, N_cur;

retaining a previous average queue depth, Previous N_avg;

monitoring whether or not the queue is empty, and

updating the average queue depth, New N_avg, by the following formulae;

if the queue is not empty,

New N_avg=Previous N_avg+W×

(N_cur−

Previous N_avg);

if the queue is empty,

New N_avg=Previous N_avg×

function(idle time, W), and

if the queue is empty and also New N_avg=Previous N_avg;

New N_avg=Previous N_avg+W×

(N_cur−

Previous N_avg);

where W is a running weight between 0 and 1.

7. The method according to claim 2 wherein the packet has a drop precedence of a plurality of levels expressed in colours and each colour has its discard probability and discard probability sum, the method further comprising steps of:

checking the colour of the packet arriving at the queue, and

accepting or discarding the packet based on discard probability sum for the colour.

8. The method according to claim 3 wherein the packet has a drop precedence of a plurality of levels expressed in colours and each colour has its discard probability and discard probability sum, the method further comprising steps of:

checking the colour of the packet arriving at the queue, and

accepting or discarding the packet based on discard probability sum for the colour.

9. The method according to claim 4, further comprising steps of:

calculating a discard probability for the colour, using an average depth of the queue, and

generating a new discard probability sum for a next packet of the colour arriving at the queue, by summing the discard probability sum and the calculated discard probability for the colour.

10. The method according to claim 5, further comprising steps of:

calculating a discard probability for the colour, using an average depth of the queue, and

generating a new discard probability sum for a next packet of the colour arriving at the queue, by summing the discard probability sum and the calculated discard probability for the colour.

11. The method according to claim 6, further comprising steps of:

calculating a discard probability for the colour, using an average depth of the queue, and

generating a new discard probability sum for a next packet of the colour arriving at the queue, by summing the discard probability sum and the calculated discard probability for the colour.

12. In performing a random early packet discard procedure in a telecommunications system, a method of calculating an average depth of a queue when a packet arrives thereat, comprising steps of:

measuring a current queue depth, N_cur;

retaining a previous average queue depth, Previous N_avg;

monitoring whether or not the queue is empty, and

updating the average queue depth, New N_avg, by the following formulae;

if the queue is not empty,

New N_avg=Previous N_avg+W×

(N_cur−

Previous N_avg);

if the queue is empty,

New N_avg=Previous N_avg×

function(idle time, W), and

if the queue is empty and also New N_avg=Previous N_avg,

New N_avg=Previous N_avg+W×

(N_cur−

Previous N_avg);

where W is a running weight between 0 and 1, and the function is a function that returns values based on the idle time of the queue and W.

13. The method according to claim 12, wherein W is ½

^M and M is an integer between 0 and 15.

14. The method of claim 12, further comprising steps of:

deciding an accept/discard operation on a packet arriving at the queue, based on comparison between a discard probability sum for the packet and a random variable;

calculating a discard probability for the packet, using an average depth of the queue, and

generating a new discard probability sum for a next packet arriving at the queue, by summing the discard probability sum and the calculated discard probability.

15. The method according to claim 14, further comprising steps of:

accepting each packet arriving at the queue if a discard probability sum for the packet is smaller than or equal to a random variable.

discarding a packet arriving at the queue the most recently, if the discard probability sum for the most recent packet is larger than the random variable;

setting the discard probability sum to zero;

generating another random variable to replace the aforementioned random variable, and

deciding an accept/discard operation on further packets arriving at the queue.

16. The method according to claim 15 wherein packets arriving at the queue have a drop precedence of a plurality of levels expressed in colours and each colour has its discard probability and discard probability sum, the method further comprising steps of:

checking the colour of each packet arriving at the queue, and

accepting or discarding the packet based on discard probability sum for the colour.

17. A mechanism for controlling a queue of a communications system, comprising:

a receiver for receiving and sending a packet to a queue for storage;

discard probability calculation module for calculating the discard probability sum which is the summation of discard probabilities of all packets that have arrived at the queue since a packet was last discarded from the queue;

a random number generator for generating a random number when instructed, and

discard module for discarding the just arrived packet from the queue if the discard probability sum is greater than the random number, and instructing the discard probability calculation module to set the discard probability sum to zero and to generate another random number to replace the aforementioned random number.

18. The mechanism according to claim 17, further comprising:

a sum operator for producing a new discard probability sum by a summation of a newly calculated discard probability for the just arrived packet and a previous discard probability sum.

19. The mechanism according to claim 18, further comprising:

a processor for obtaining an average depth of the queue by using following equations,

if the queue is not empty,

New N_avg=Previous N_avg+W×

(N_cur−

Previous N_avg);

if the queue is empty,

New N_avg=Previous N_avg×

function(idle time, W), and

if the queue is empty and also New N_avg=Previous N_avg,

New N_avg=Previous N_avg+W×

(N_cur−

Previous N_avg);

where N_cur is a current queue depth, Previous N_avg is a previous average queue depth, New N_avg is the average queue depth, W is a running weight between 0 and 1, and the function is a function that returns values based on the idle time of the queue and W.

20. The mechanism according to claim 18, wherein the receiver further comprises means for checking drop precedence of the just arrived packet.