queue length is above the minimum threshold, RED
starts dropping packets. The rate of packet drop increases
linearly as the average queue size increases, until the average
queue size reaches the maximum threshold. Maximum
threshold: When the average queue size is above the maximum
threshold, all packets are dropped. Mark
probability denominator: This number is the fraction of
packets that are dropped when the average queue depth is at the
maximum threshold. For example, if the denominator is 512, one
out of every 512 packets is dropped when the average queue is
at the maximum threshold. The linear increase of packet drops
from the minimum threshold (0 drops) to the maximum threshold
is based on this parameter and the queue size between the
minimum and maximum thresholds. The minimum
threshold value should be set high enough to maximize link
utilization. If the minimum threshold is too low, packets may
be dropped unnecessarily, and the transmission link will not be
fully used. The difference between the maximum threshold and
the minimum threshold should be large enough to avoid global
synchronization. If the difference is too small, many packets
may be dropped at once, resulting in global synchronization.
RED Modes
Figure shows the three RED dropping modes
used in TCP that are based on the average queue size:
- When the average queue size is between 0 and the
configured minimum threshold, no drops occur and all packets
are queued.
- When the average queue size is between
the configured minimum threshold and the configured maximum
threshold, random drops occur, which is linearly proportional
to the mark probability denominator and the average queue
length.
- When the average queue size is at or higher
than the maximum threshold, RED performs full (tail) drop in
the queue. This situation is unlikely, because RED should slow
down TCP traffic ahead of congestion. If a lot of non-TCP
traffic is present, RED cannot effectively drop traffic to
reduce congestion, and tail drops are likely to occur.
TCP Traffic Before and After RED
Figure shows
TCP throughput behavior compared to link bandwidth in a
congested network scenario where the tail-drop and RED
mechanisms are in use on the link. Before RED, when all
sessions slow down, congestion on the router interface is
removed and all TCP sessions restart their transmission at
about the same time. Again, the router interface quickly
becomes congested, causing tail drop. As a result, all TCP
sessions back off again. This behavior cycles constantly,
resulting in a link that is generally underutilized. After RED
is applied, RED randomly drops packets, influencing a small
number of sessions at a time, before the interface reaches
congestion. Overall throughput of sessions is increased, as is
average link utilization. Global synchronization is very
unlikely to occur because of selective, but random, dropping of
adaptive traffic.
Content 4.6 Congestion
Avoidance 4.6.4 Weighted Random Early
Detection Interestingly, Cisco does not support RED.
Instead, Cisco supports weighted random early detection (WRED)
which combines RED with IP precedence or DSCP and performs
packet dropping based on IP precedence or DSCP markings. For
example, a packet with an IP precedence value of 0 might have a
minimum threshold of 20 packets, whereas a packet with an IP
precedence of 1 might have a minimum threshold of 25 packets.
In this example, packets with an IP precedence of 0 would start
to be discarded before packets with an IP precedence of 1.As
with RED, WRED monitors the average queue length in the router
and determines when to begin discarding packets based on the
length of the interface queue. When the average queue length
exceeds the user-specified minimum threshold, WRED begins to
randomly drop packets with a certain probability. If the
average length of the queue continues to increase so that it
becomes larger than the user-specified maximum threshold, WRED
reverts to a tail-drop packet-discard strategy, in which all
incoming packets are dropped. The idea behind using WRED is to
maintain the queue length at a level somewhere below the
maximum threshold and to implement different drop policies for
different classes of traffic. WRED can selectively discard
lower-priority traffic when the interface becomes congested and
can provide differentiated performance characteristics for
different classes of service. WRED can also be configured to
produce nonweighted RED behavior. For interfaces configured to
use Resource Reservation Protocol (RSVP), WRED chooses packets
from other flows to drop rather than the RSVP flows. Also, IP
precedence or DSCP helps determine which packets are dropped,
because traffic at a lower priority has a higher drop rate than
traffic at a higher priority (and, therefore, lower-priority
traffic is more likely to be throttled back). In addition, WRED
statistically drops more packets from large users than from
small users. The traffic sources that generate the most traffic
are more likely to be slowed than traffic sources that generate
little traffic. WRED reduces the chances of tail drop by
selectively dropping packets when the output interface begins
to show signs of congestion. By dropping some packets early
rather than waiting until the queue is full, WRED avoids
dropping large numbers of packets at once and minimizes the
chances of global synchronization. As a result, WRED helps
maximize the utilization of transmission lines. WRED treats
non-IP traffic as precedence 0, the lowest precedence.
Therefore, non-IP traffic, in general, is more likely to be
dropped than IP traffic. WRED should be used wherever there is
a potential congested link (bottleneck), which could very well
be an access or edge link; however, WRED is normally used in
the core routers of a network rather than at the network edge.
Edge routers assign IP precedence or DSCP to packets as they
enter the network. WRED uses these assigned values to determine
how to treat different types of traffic. Note that Cisco does
not recommend WRED for any voice queue, although you may enable
WRED on an interface carrying voice traffic. WRED will not
throttle back voice traffic because voice traffic is User
Datagram Protocol (UDP)-based. The network itself should be
designed not to lose voice packets because lost voice packets
result in reduced voice quality. WRED controls congestion by
affecting prioritized traffic other than voice, and avoiding
congestion helps to ensure voice quality. Figure summarizes
these points. WRED Building Blocks
Figure shows how
to implement WRED and the parameters used by WRED to influence
packet-drop decisions. The router constantly updates the WRED
algorithm with the calculated average queue length, which is
based on the recent history of queue lengths. Configured in the
traffic profile are the parameters that define the drop
characteristics used by WRED (minimum threshold, maximum
threshold, and mark probability denominator). These parameters
define the WRED probability slopes. When a packet arrives at
the output queue, the IP precedence or DSCP value is used to
select the correct WRED profile for the packet. The packet is
then passed to WRED for processing. Based on the selected
traffic profile and the average queue length, WRED calculates
the probability for dropping the current packet and either
drops the packet or passes it to the output queue. If the queue
is already full, the packet is dropped. Otherwise, the packet
is eventually transmitted out to the interface. If the average
queue length is greater than the minimum threshold but less
than the maximum threshold, based on the drop probability, WRED
either queues the packet or performs a random drop.
Class-Based WRED
Traditionally, Cisco IOS software
used stand-alone RED and WRED mechanisms to avoid congestion on
an interface. Those mechanisms can perform a differentiated
drop based on the IP precedence or DSCP value. The class-based
weighted fair queuing (CBWFQ) system supports the use of WRED