=head1 Random Early Detection Gateways for Congestion Avoidance
Sally Floyd and Van Jacobson, LBL 1993

B<Summary.> Common gateways today have large queues to handle periods of
congestion. These large queues, however, cause long delays.  A better
scenario would be to maximize throughput while still keeping queue
sizes small. Secondly, the common congestion control schemes used
today are implemented at the transport layer (i.e., in TCP) where
there is no global view of the network traffic. A better place for
control would be at the gateway level where a global view is 
possible. 

Random Early Detection (RED) gateways provide I<congestion avoidance>
at the gateway level via a queue-size (QS) estimator and a policy for
I<marking> or dropping packets. When the calculated average QS (AQS)
has grown above a certain level, the arriving packets are marked or
dropped with a certain probability. The probability is determined by
the current QS.

=head1 More Detail

B<Goals.> The Goals of the RED design and how those goals are met:

=over

=item *

Congestion avoidance using the average queue size. 

=item *

Avoid I<global synchronization> (when many flows back off their
sending rate simultaneously such that bandwidth is wasted). This is
done by choosing the packets to mark/drop using probability rather
than just marking/droping packets once the QS grows beyond a certain
threshold.

=item *

Avoid bias against bursty traffic (i.e., slow-start). This is done
by using a I<Exponential Weighted Moving Average> which allows the
average calculation to reflect only long-term (several RTTs) changes. 

=item *

Maintain an upper bound on QS. Once the AQS grows beyond a maximum
threshold, the gateway will drop I<all> packets that come in. 

=back

B<Previous Work.> Other gateway congestion avoidance work (and their
shortcomings) include:

=over 4

=item 1.

Drop Tail - when queue large, indiscriminately drop every packet that
arrives; bias toward bursty traffic since bursty traffic likely to
cause/add to queue overflowing (since other flows don't normally take
into account so there's no bw left for it); causes global
synchronization since many flows likely to be notified once AQS gets
large. 

=item 2.

Early Random Drop - if the QS exceeds a I<drop level>, drop packet
with a fixed probability; doesn't control misbehaving users, but 
"deserves further investigation"; RED does have a I<potential> method
for controlling misbehaving users. 

=item 3.

DECbit - computes AQS using past period of busy/idle/busy (didn't
choose EWMA because they said that it introduced bias (toward what, I
don't know); marks all arriving packet headers with congestion flag
when AQS exceeds a certain threshold; suffers from global synchronization
and bias against bursty traffic.

=back

B<Algorithm.> The AQS is calculated using an EWMA. The weight should
be determined carefully (hints are given in the paper) so that the 
AQS only reflects long-term QS changes rather than just temporary changes.
This is key in handling bursty traffic. A I<minimum threshold> (MIN) and 
I<maximum threshold> (MAX) are set. If (AQS < MIN), no action is
taken. If (MIN < AQS < MAX), incoming packets are mark/dropped according to 
a certain probability P that is a function of the AQS I<and> the number
of packets that have been seen since the last packet was mark/dropped.
If (AQS > MAX), all incoming packets are mark/dropped. 

The authors claim that we can use an EWMA because the randomized manner
in which we choose the mark/dropped packets avoids network bias (?). 

P is determined using a method the authors call "uniform random variables". 
This is apparently because the alternative method, "geometric random 
variables" tends to cluster the marked packets. 

Optionally, the queue can be measured in terms of bytes rather than
packets. In this case, large packets are more likely to be dropped than
smaller packets. 

If desired, the gateway can keep track of the last I<n> packets that
have been marked. If a certain flow owns a disproportionate number
of those packets, the gateway can label that flow as "misbehaved"
and treat its packets separately. 

=head1 Class notes.

Fair: Max-Min Fairness. All flows get access to the same base level of
bandwidth. If there is leftover, it is shared equally amongst those
flows that can use it.

Geometric: like tossing a coin for each packet that arrives. Easier
to implement.

Random: like choosing a packet from the queue. Not as easy to implement,
but doesn't result in clustered marked packets. 

Rewards to flows not using their share of bandwidth via a "bid". The
bid is set by a I<delta> parameter. If (I<delta> = 0), there is
no reward. If (I<delta> = large), favor low-usage flows.