Subject: LINK discussion of RED

From: Phil Karn <[email-masked]>
Date: Fri, 6 Jul 2001 19:03:10 -0700 (PDT)

LINK currently has this text:

   One well known example of an active queue management the Random Early
   Detection (RED) algorithm [RED93].  RED maintains an exponential
   weighted moving average of the queue depth.  When this average queue
   depth is between a maximum threshold max_th, and a minimum threshold
   min_th, packets are dropped with a probability which is proportional
   to the amount by which the average queue depth exceeds min_th.  When
   this average queue depth is equal to max_th, the drop probability is
   equal to a configurable parameter max_p.  When this average queue
   depth is greater than max_th, packets are always dropped.  Numerous
   variants on RED appear in the literature, and there are other active
   queue management algorithms which claim advantages over RED in
   various dimensions.

This implies that the packet dropping probability has a discontinuity
at an average queue depth of max_th, where it jumps from max_p just
below max_th to unity just above. Is this correct?

Phil

---

From: Gorry Fairhurst <[email-masked]>
Date: Mon, 09 Jul 2001 12:42:26 +0100

>    One well known example of an active queue management the Random Early

Insert "is" before the.

>    Detection (RED) algorithm [RED93]. 

Perhaps say that the router drops/marks packets prior
to running out of buffer space in an attempt to trigger more appropriate
congestion behavior by the TCP protocol in the end hosts.

>  RED maintains an exponential
>    depth is greater than max_th, packets are always dropped. 

The problem is there are many variants of RED, many ways to tune, 
implement, etc. This is really one example of how RED could be done.

If I remember correct, Sally Floyd recently suggested the "always" drop
at 
max threshold may not be optimal. There's now a move to make this 
an increased probability of dropping, and always drop only after a queue 
overflow.

> Numerous

Now ECN is being more actively thought about do you want to say drop/mark?

Gorry

---

From: Phil Karn <[email-masked]>
Date: Tue, 10 Jul 2001 22:50:58 -0700

Okay, I've reworked the RED text as follows:

 One form of active queue management is the Random Early Detection
 (RED) algorithm [RED93], actually a family of related algorithms. In
 one version of RED, an exponentially weighted moving average of the
 queue depth is maintained.  When this average queue depth is between a
 maximum threshold max_th, and a minimum threshold min_th, packets are [...]

the intent is to show that this is just one form of RED. If I can get cites to
alternative forms, I can include them too.

 With an active queue management algorithm, dropped packets become a
 feedback signal to trigger more appropriate congestion behavior by the
 TCPs in the end hosts.  Randomization of dropping tends to break up [...]

>Now ECN is being more actively thought about do you want to say drop/mark?

I already have the following text. Do I need more?

 Another possible approach to flow control in the subnet would be to work with 
 TCP Explicit Congestion Notification (ECN) semantics [RFC2481].  Routers at 
 the edges of the subnet, rather than shaping, would set the ECN bit in those 
 IP packets that are received in subnet packets that have an ECN indication.  
 Nodes in the subnet would need to implement an  active queue management 
 protocol that marks subnet packets instead of dropping them. However, RFC2481 is 
 presently experimental, and TCPs that can use ECN are not widely deployed.

---

From: "Saverio Mascolo" <[email-masked]>
Date: Wed, 11 Jul 2001 13:56:49 +0200

----- Original Message -----
From: Phil Karn <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>
Sent: Wednesday, July 11, 2001 7:50 AM
Subject: Re: LINK discussion of RED

> alternative forms, I can include them too.

Hi all,

at

http://www-ictserv.poliba.it/mascolo/papers/Easy_red.zip

or

http://www-ictserv.poliba.it/mascolo/papers/Easy_red.pdf

you may be interested to the Tech. Report "Easy Red: Improving fairness via
simple early discard" by Saverio Mascolo and Alfredo Grieco. The Tech.
Report is on the performance of RED and Easy Red that is a
simplified version of RED.

Saverio