Random Early Detection Gateways for Congestion Avoidance

Previous

5.0.- Random Early Detection Gateways for Congestion Avoidance

In 1993, Sally Floyd and Van Jacobson presented a very interesting work about how to detect congestion in networks using routers provided by a random early detection mechanism. Here is a summary of their job:

The most effective place to detect congestion is in the gateway itself. The gateway can reliably distinguish between propagation delay and persistent queueing delay. Only the gateway has an unified view of the queueing behavior over time; the perspective of individual connections is limited by the packet arrival patterns for those connections. In addition, a gateway is shared by many active connections with a wide range of roundtrip times, tolerance of delay, throughput requirements, etc.; decisions about the duration and magnitude of transient congestion to be allowed at the gateway are best made by the gateway itself.

The paper proposes a different congestion avoidance mechanism at the gateway, RED (Random Early Detection) gateways, with somewhat different methods for congestion detection and for choosing which connection to notify of this congestion. RED gateways are specifically targeted to TCP/IP networks. The RED gateway is designed for a network where a single marked or dropped packet is sufficient to signal the presence of congestion to the transport-layer protocol. In addition, the emphasis on avoiding the global synchronization that results from many connections reducing their windows at the same time is particulary relevant in a protocol like TCP, where each connection goes through slow-start, reducing the window to one, in response to a dropped packet.

One advantage of a gateway congestion control mechanism that works with current transport protocols, and that does not require that all gateways in the internet use the same gateway congestion control mechanism, is that it could be deployed gradually in the current internet. RED gateways are a simple mechanism for congestion avoidance that could be implemented gradually in current TCP/IP networks with no change to transport protocol.

Design guidelines

The main goal of RED gateways is to provide congestion avoidance by controlling the average queue size. Additional goals include the avoidance of a global synchronization and a bias against bursty traffic and the ability to maintain an upper bound on the average queue size even in the absence of cooperation from transport-layer protocols. (Another advantage of using RED gateways is the reduction of packet dropping and connection biased behavior induced by the TCP phase effect - LB).

The first job of a congestion avoidance mechanism at the gateway is to detect incipient congestion; a congestion avoidance mechanism maintains the network in a region of low delay and high throughput. The average queue size should be kept low, while fluctuations in the actual size should be allowed to accommodate bursty traffic and transient congestion. Because the gateway can monitor the size of the queue over time, the gateway is the appropriate agent to detect incipient congestion.

The second job of a congestion avoidance gateway is to decide which connections to notify of congestion at the gateway. If congestion is detected before the gateway buffer is full, it is not necessary for the gateway to drop packets to notify sources of congestion. We say that the gateway marks a packet, and notifies the source to reduce the window for that connection. This marking and notification can consist of dropping a packet, setting a bit in a packet header, or some other method understood by the transport protocol; current feedback of TCP/IP networks is for the gateway to drop packets.

In order to avoid problems such as biases against bursty traffic and global synchronization, congestion avoidance gateways can use distinct algorithms for congestion detection and for deciding which connection to notify of this congestion. The RED gateways use randomization in choosing which arriving packets to mark; with this method, the probability of marking a packet from a particular connection is roughly proportional to that connection's share of the bandwidth through the gateway.

For controlling the average queue size in absence of cooperating sources, the RED gateways drop arriving packets when the average queue size exceeds some maximum threshold (rather than setting a bit in the packet header).

The RED algorithm

The RED algorithm calculates the average queue size, using a low-pass filter with an exponential weighted moving average; the average queue size is compared against two thresholds: a minimum threshold and a maximum threshold. When the average queue size is greater than the maximum threshold, every arriving packet is marked. If marked packets are in fact dropped, or if all source nodes are cooperative, this ensures that the average queue size does not significantly exceed the maximum threshold.

When the average queue size is between the minimum and the maximum threshold, each arriving packet is marked with probability pa, where pa is a function of the average queue size avg. Each time that a packet is marked, the probability that a packet is marked from a particular connection is roughly proportional to that connection's share of the bandwidth at the gateway.

Thus the RED gateway has two separate algorithms. The algorithm for computing the average queue size determines the degree of burstiness that will be allowed in the gateway queue. The algorithm for calculating the packet-marking probability determines how frecuently the gateway marks packets, given the current level of congestion. The goal is for the gateway to mark packets at fairly evenly-spaced intervals, in order to avoid biases and to avoid global synchronization, and to mark packets sufficiently frequent to control the average queue size.

When the queue is empty (the idle period) the average queue size is calculates by estimating the number of small packets that could have been transmitted by the gateway during the idle period. As avg (average queue size) varies from min.th to max.th, the packet marking probability pb varies linearly from 0 to maxp:

The final packet-marking probability pa increases slowly as the count increases since the last marked packet:

Where count is the number of non-marked packet since last marked packet. When avg exceeds max.th the gateway marks every packet.

One option for RED gateways is to measure the queue in bytes rather than in packets. When this option is used, the algorithm would be modified to ensure that the probability that a packet is marked is proportional to the packet size in bytes:

In this case a large FTP packet is more likely to be marked than is a small telnet packet.

Simulation

Authors made some simulations to validate RED. They used four FTP sources sending 1000-byte packets always as soon as the congestion control window allows them to do so. A sink immediately sends an ACK packet when it receives a data packet. Congestion control algorithm was:

A threshold is set initially to half the receiver's advertised window.
In the slow-start phase, the current window is double each roundtrip time until the window reach the threshold.
Then congestion-avoidance takes care the current window is increased by roughly one packet each roundtrip time.
The window is never allowed to increase more than the receiver's advertised window.
A dropped packet is treated as a "congestion experienced" signal. The source reacts to a packet loss by setting the threshold to half the current window, decreasing the current window to one packet, and entering the slow-start phase.

Note: above algorithm correspond to the TCP Tahoe implementation (LB).

Simulations show that network power (ratio of throughput to delay) is higher with RED gateways than with Drop Tail gateways.

Bounding for wq

The RED gateway uses a low-pass filter to calculate the average queue size; it's an exponential weighted moving average (EWMA) filter:

The weight wq determines the time constant of the low-pass filter. How to select a good value for wq? If wq is too large, then the averaging procedure will not filter out transient congestion at the gateway. If wq is set too low, the avg responds too slowly to changes in the actual queue size. In this case, the gateway is unable to detect the initial stages of congestion. In the paper the authors proved that a good value for wq would be 0.002, having un upper bound of 0.042.

Setting min.th and max.th

Optimal values for min.th and max.th depend on the desired average queue size. If the traffic is fairly bursty, then min.th must be correspondingly large to allow the link utilization to be maintained at an acceptably high level. On the other side, the optimal value for max.th depend in part on the maximum average delay then can be allowed by the gateway. The RED gateway functions most effectively when (max.th - min.th) is larger than the typical increase in the calculated average queue size in one roundtrip time. A useful rule-of-thumb is set max.th to at least twice min.th.

Note: the authors normally use max.th = 3 * min.th (LB).

Calculating the packet marking probability

In the paper the authors proved by testing that the best method to calculate the packet-marking probability is by using an uniform random variable to set the number of arriving packets between marked packets. The initial packet-marking probability (pa) is computed as a linear function of average queue size as:

The final packet-marking probability (pb) is calculated using an uniform random variable; this is achieved if the marking probability for each arriving packet is:

Where count is the number of unmarked packets that have arrived since the last marked packet.

They presented an experiment in the paper comparing two methods for marking packets. In method #1 each packet is marked with a constant probability p, where p = 0.02. In method #2 each packet is marked with a probability p / ( 1 + i * p), where p = 0.01 and i the number of unmarked packets since the last marked packet. Both methods marked roughly 100 out of 5000 arriving packets. As expected, the marked packets are more clustered with method 1 than with method 2. Method 2 has a more uniform packet marking along the time.

In simulations done in the paper, the authors set maxp to 1/50. Then, when the average queue size was halfway between min.th and max.th, the gateway drops, on the average, roughly one out of 50 (or one out of 1/maxp) arriving packets. Experimenting with maxp they didn't find a reason to set maxp greater than 0.01. When maxp = 0.01 the RED gateway marks close to 1/5th of the arriving packets when the average queue size is close to the maximum threshold. If congestion is sufficiently heavy that the average queue size cannot be controlled by marking close to 1/5th of the arriving packets, then after the average queue size exceeds the maximun threshold, the gateway will mark every arriving packet.

Evaluation of RED gateways

Goals meet by RED gateways:

Congestion avoidance: if the RED gateway in fact drops packets arriving at the gateway when the average queue size reaches the maximum threshold, then the RED gateway guarantees that the calculated average queue size does not exceed the maximum threshold. If the RED gateway marks packets, rather than dropping packets, then the RED gateway relies on the cooperation of the source to control the average queue size.
Appropriate time scales: in RED gateways the time scale for the detection of congestion roughly matches the time scale required for connections to respond to congestion. RED gateways don't notify connections to reduce their windows as a result of transient congestion at the gateway.
No global synchronization: RED gateways avoid global synchronization by marking packets at as low a rate as possible. The rate at which RED gateways mark packets depend on the level of congestion.
Simplicity: the RED gateway algorithm could be implemented with moderate overhead in current networks.
Maximizing global power: simulation shows that global power is higher with RED gateways than with DropTail gateways. Power is defined as the ratio of throughput to delay.
Fairness: the RED gateway does not discriminate against particular connections or classes of connection; the fraction of marked packets for each connection is roughly proportional to that connection's share of the bandwidth. However, RED gateways do not attempt to ensure that each connection receives the same fraction of the total throughput, and do not explicity control misbehaving users.
Appropriate for a wide range of environments: the randomized mechanism of marking packets is appropriate for networks with connections with a large range of roundtrip times and throughput, and for large range in the number of active connections at one time.

Parameter sensitivity

Ensure adequate calculation of the average queue size: set wq >= 0.001. The weight wq should not be set too low, so that the calculated average queue length does not delay too long in reflecting increase in the actual queue length.
Set min.th sufficiently high to maximize network power: The thresholds min.th and max.th should be sufficiently high to maximize power. Because network traffic is often bursty, the actual queue size can also be quite bursty; if the average queue size is kept too low, then the output link will be underutilized.
Make (max.th - max.th) sufficiently large to avoid global synchronization: Make (max.th - min.th) larger than the typical increase in the average queue size during a roundtrip time, to avoid the global synchronization that results when the gateway marks many packets at one time. One rule of thumb would be to set max.th to at least twice min.th.

Some simulations

The authors implemented some simulation tests to verify the RED gateway performance. Having a look to the paper, tests show that the RED gateway is effective in controlling the average queue size. When congestion is low, the average queue size and the rate of marking packets is also low at the gateway. As congestion increase, the average queue size and the rate of markings both increase.

Also was shown that the RED gateways do not have a bias against bursty traffic. Some tests made with a FTP connection with a long delay-bandwidth product but a small window showed than compared to drop tail and random drop gateways, the RED gateways performance is a lot better and some observations are:

With drop tail or random gateways, the queues are more likely to overflow when they contain packets from a bursty traffic connection.
With drop tail or random drop gateways, packets from a bursty traffic connection have a disproportionated probability of been dropped.
With RED gateways the throughput for bursty traffic connections are close to the maximum possible throughput. On the contrary, drop tail and random drop gateway panalize these traffics by applying a disproportionate share of the packet drops.
For bursty traffic using RED gateways the share of dropped packets reflects the share of the throughput. In contrast, for drop tail and random drop gateways these traffics receive a small fraction of the throughput but a large fraction of the packet drops.

Identifying misbehaving users

Because RED gateways randomly choose packets to be marked during congestion, RED gateways could easily identify which connections have received a significant fraction of the recently-marked packets. When the number of packets marked is sufficiently large, a connection that has received a large share of the marked packets is also likely to be a connection that has received a large share of the bandwidth.

If some TCP connection is receiving a large fraction of the bandwidth, that connection could be a misbehaving host that is not following current TCP protocols, or simply a connection with either a shorter roundtrip time or a larger window than other active connections. In either case, if desired, the RED gateway could be modified to give lower priority to those connections that receive a large fraction of the bandwidth during times of congestion.

Implementation

In the paper, authors show that calculation required to implement RED gateways are simple and can be executed using little resources. They argued that the RED gateway algorithm can be implemented efficiently, with only a small number of add and shift instructions for each packet arrival. Also, they say that much of the work of the RED gateway algorithm, such as the computation of the average queue size and of the packet-marking probability pb, could be performed in parallel with packet forwarding, or could be computed by the gateway as a lower priority task as time permits.

If the RED gateway's method of marking packets is to set a congestion indication bit in the packet header, rather than dropping the arriving packet, then setting the congestion indication bit itself adds overhead to the gateway algorithm. However, because RED gateways are designed to mark as few packets as possible, the overhead of setting the congestion indication bit is kept to a minimun.

For every packet arrival at the gateway queue, the RED gateway calculates the average queue size. This can be implemented as follows:

As long as wq is chosen as a (negative) power of two, this can be implemented with one shift and two additions (given scaled versions of the parameters).

When the queue is empty, the gateway calculates the average queue size as if m packets has arrived at the gateway with a queue size of zero. The calculation is as follows:

where q_time is the start of the queue idle time, and s is a typical transmission time for a small packet. After the idle time (time - q_time) has been computed to a rough level of accuracy, a table lookup could be used to get the term ( 1 - wq )^ m, which could itself be an approximation by a power of two.

When a packet arrives at the gateway and the average queue size avg exceeds the threshold max.th, the arriving packet is marked. There is no reacalculation of the packet-marking probability. However, when a packet arrives at the gateway and the average queue size avg is between the two thresholds min.th and max.th, the initial packet-marking probability is calculated as follows:

Parameters maxp, max.th and min.th are fixed parameters that are determined in advance. The values for max.th and min.th are determined by the desired bounds on the average queue size, and might have limited flexibility. The fixed parameter maxp, however, could easily be set to a range of values. In particular, maxp could be chosen so that C1 is a power of 2. Thus, the calculation of pb can be accomplished with one shift and one add instruction.

The algorithm for implementing RED gateways requires a random number R = [0,1], from the uniform distribution on [0,1]. These random numbers could be gotten from a table of random numbers stored in memory or could be computed fairly efficiently on a 32-bit computer. Also, in the algorithm, the arriving packet is marked if R < pb/(1-count*pb). If pb is approximated by a negative power of two, then this can be efficiently computed.

Finally, the memory requirements of the RED gateway algorithm are modest. Instead of keeping state for each active connection, the RED gateway requires a small number of fixed and variable parameters for each output line. This is not a burden on gateway memory.

Further research on RED gateways

Determining the optimum average queue size for maximizing throughput and minimizing delay for various network configurations.
Investigating traffic dynamics with a mix of DropTail and RED gateways, as would result from partial deployment of RED gateways in the current internet.
Investigating the behavior of the RED gateway machinery with transport protocols other than TCP.
As was saw, the list of packets marked by the RED gateway could be used to identify connections that are receiving a large fraction of the bandwidth; this information could be used to give such connections lower priority at the gateway.
Investigating whether the queue size should be measured in bytes or in packets. For networks with a range of packet sizes at the congestion gateway the difference can be significant.
Some investigation has to be done with RED gateways that provide priority service for short control packets to reduce problems with compressed ACKs. For example, RED gateways where different classes of traffic are treated differently and each class has its own separated Random Early Detection queue.

Complete RED algorithm

Previous

Content

Next