1 Background and purpose

Random early detection, often abbreviated RED, is a queue management method used in packet-switched networks to reduce congestion before a device reaches overload. Instead of waiting for a buffer to fill completely, it begins to drop or mark packets when signs of persistent buildup appear. The approach was developed as a way to make congestion control more proactive and less abrupt.

1.1 Network congestion

Network congestion occurs when traffic demand exceeds the ability of routers, switches, or links to forward packets in a timely manner. As more packets arrive than can be transmitted, delays increase and queues grow. If the condition persists, packets may be discarded, retransmitted, or delayed enough to affect application performance.

1.2 Buffering and queue growth

Routers and switches typically keep incoming packets in buffers while waiting for output links to become available. A modest queue can absorb short bursts of traffic, but sustained pressure causes the queue to expand. Long queues may improve short-term acceptance of traffic yet also raise latency and increase the chance of packet loss when the buffer eventually fills.

1.3 Motivation for early packet dropping

RED was created to avoid the all-at-once behavior of conventional queue overflow. By signaling congestion early, it encourages senders to slow down before severe backlog develops. This can produce smoother traffic adjustment, fewer full-buffer losses, and more stable overall performance.

2 Algorithm overview

RED bases its decisions on the average queue size rather than the instantaneous queue length. This makes it less sensitive to brief spikes and better suited to detecting sustained congestion. When the average exceeds certain thresholds, the device starts to drop or mark packets with a probability that rises as congestion increases.

2.1 Average queue size

The average queue size is a smoothed estimate of how busy the buffer has been over time. It is usually calculated with a weighted moving average, so recent conditions matter more than distant ones. This prevents the algorithm from reacting to every tiny fluctuation.

2.2 Thresholds

RED typically uses two queue thresholds to define different congestion regions. Below the lower threshold, packets are accepted normally. Between the thresholds, the chance of dropping or marking packets increases gradually. Above the upper threshold, congestion is treated as severe.

2.2.1 Minimum threshold

The minimum threshold is the point at which RED begins to react to congestion. When the average queue size stays below this level, packets are usually forwarded without special action. This allows the network to handle light or intermittent traffic without unnecessary loss.

2.2.2 Maximum threshold

The maximum threshold marks a heavier congestion zone. Once the average queue size reaches or exceeds this level, packets are dropped or marked with a much higher probability, and in some implementations nearly all new packets may be affected. The goal is to force traffic reduction before the buffer becomes completely full.

2.3 Probabilistic dropping and marking

Rather than dropping every packet once congestion begins, RED uses randomization. This distributes loss across different flows and helps avoid synchronized reactions from many senders at once. In networks that support explicit congestion notification, packets may be marked instead of dropped.

2.4 Weighting and smoothing

The smoothing factor controls how quickly the average queue size responds to new arrivals. A smaller weight makes the average change slowly and reduces sensitivity to short bursts. A larger weight makes RED react faster, but it can also make the algorithm more reactive to temporary traffic variation.

3 Operation

RED operates continuously as packets arrive at an interface. It observes queue conditions, updates the moving average, and then decides whether a packet should be forwarded normally, dropped, or marked. The sequence is intended to be lightweight enough for use in high-speed forwarding devices.

3.1 Packet arrival handling

When a packet reaches the queue, RED updates its estimate of average occupancy. It then compares that value with the configured thresholds. The decision is made on a per-packet basis, which allows fine-grained control over congestion signaling.

3.2 Congestion detection

Congestion is inferred from persistent queue growth rather than from a single momentary burst. This design helps distinguish between harmless short-term loading and sustained pressure that can degrade performance. The use of an average is central to that distinction.

3.3 Drop decision process

If the average queue size is below the lower threshold, the packet is normally accepted. If the value lies between the thresholds, the drop probability rises gradually. Once the upper threshold is exceeded, the algorithm becomes much more aggressive, signaling that the queue is approaching an undesirable state.

3.4 ECN marking behavior

When explicit congestion notification is available, RED may mark packets instead of discarding them. The marking indicates congestion to the sender without destroying the packet itself. This can improve efficiency when endpoints are capable of responding to congestion signals without relying on loss.

4 Design goals

RED was created to improve the behavior of congested networks in several ways at once. It aims to reduce loss bursts, keep queues from becoming too large, and provide earlier feedback to transport protocols. These goals are related and often reinforce one another.

4.1 Avoiding global synchronization

A common problem in drop-based congestion control is that many senders reduce their rates at the same time after a shared loss event. RED’s randomization spreads out packet loss so that flows are less likely to react in lockstep. This helps prevent repeated cycles of simultaneous backoff and recovery.

4.2 Maintaining low delay

Large queues increase waiting time for packets already in the buffer. By intervening before the queue becomes excessive, RED helps keep latency lower than it would be under a pure tail-drop approach. This is especially important for interactive traffic.

4.3 Improving throughput stability

Early congestion signals can make sending behavior steadier over time. Instead of alternating between empty and overflowed queues, the network is encouraged to operate in a more balanced range. That can support more predictable throughput for many flows.

4.4 Preventing buffer overflow

A direct objective of RED is to reduce the chance that the buffer reaches capacity. Full buffers cause hard packet loss and may create long retransmission delays. Early action makes overflow less frequent and often less disruptive.

5 Parameters and tuning

RED depends heavily on configuration. The thresholds, probability curve, and averaging weight all influence how the algorithm behaves under real traffic. Because networks differ in speed, buffer size, and traffic mix, careful tuning is usually necessary.

5.1 Threshold selection

The thresholds should be chosen with reference to buffer size and expected load. If set too low, RED may drop packets too early and waste capacity. If set too high, it may behave almost like tail drop and lose many of its benefits.

5.2 Drop probability settings

The rate at which the drop probability rises between the thresholds shapes how forcefully RED signals congestion. A gentle increase produces softer feedback, while a steeper one responds more aggressively. The best setting depends on the desired balance between delay control and throughput preservation.

5.3 Queue weight adjustment

The averaging weight determines how rapidly RED notices changes in queue behavior. A slow average can ignore brief bursts and reduce false alarms. A faster average can improve responsiveness but may react too strongly to traffic that is only temporarily intense.

5.4 Sensitivity to traffic patterns

RED performs differently depending on whether traffic is bursty, steady, or highly variable. It may work well when congestion builds gradually, but it can be less effective if traffic changes too abruptly. Its behavior also depends on how transport protocols interpret drops or marks.

6 Variants and extensions

Several modified versions of RED were created to improve its behavior in particular environments. These variants preserve the core idea of early congestion signaling but adjust the details of how probabilities or averages are computed.

6.1 Weighted RED

Weighted RED uses a weighted average of queue occupancy to smooth short-term variation. The weighting scheme is intended to make congestion detection more stable. It is closely associated with the practical deployment of RED in devices that need to handle mixed traffic.

6.2 Adaptive RED

Adaptive RED changes its parameters automatically in response to observed conditions. Instead of relying entirely on fixed thresholds, it adjusts to load levels and traffic patterns over time. This can reduce the amount of manual tuning required.

6.3 Gentle RED

Gentle RED modifies how the algorithm behaves when the queue exceeds the upper threshold. Rather than switching to an abrupt high-drop regime, it increases the probability more gradually. The aim is to make the transition smoother and more predictable.

6.4 Explicit congestion notification support

Some RED implementations are designed to work with explicit congestion notification. In such cases, packets can be marked to indicate congestion without immediate loss. This allows endpoints to react while preserving packet delivery when possible.

7 Performance characteristics

RED has been studied extensively because its benefits are real but dependent on configuration and traffic conditions. It often improves delay and loss behavior compared with simpler drop policies, yet it can also underperform if parameters are poorly chosen.

7.1 Advantages

The main advantages of RED include earlier congestion warning, reduced queue buildup, and less synchronized loss among flows. It can also help keep latency from rising too sharply under load. These properties make it attractive as a general active queue management method.

7.2 Limitations

RED can be difficult to tune, and its performance may vary across links and traffic mixes. If thresholds are not well matched to the network, it may drop packets too often or too rarely. In some situations, simple policies with better calibration can produce comparable or better results.

7.3 Sensitivity to configuration

The algorithm’s behavior is highly dependent on its parameter set. Small changes in thresholds or averaging behavior can lead to noticeable differences in delay, drop rate, and fairness. This sensitivity has been one reason for the development of multiple refinements.

7.4 Comparison with tail drop

Tail drop waits until the queue is full before discarding packets. RED intervenes earlier and randomly, so loss is spread out and congestion is signaled in advance. Tail drop is simpler, but it often produces larger queues and more abrupt packet loss when congestion becomes severe.

8 Implementation and deployment

RED has been implemented in many networking devices and software systems, although its level of use has varied over time. Practical deployment requires accounting for link speed, queue structure, and the expected mix of transport protocols.

8.1 Router and switch support

Routers and switches that support active queue management may include RED or related features in their forwarding logic. The algorithm must be efficient enough to run at line speed or near it. Hardware and software implementations may differ in how they compute the average and apply drop decisions.

8.2 Simulation and testing

RED has often been evaluated in simulation before or alongside deployment. Simulated environments allow researchers to vary traffic patterns, buffer sizes, and transport behavior. Such testing helps identify parameter ranges that produce useful congestion signaling.

8.3 Real-world operational considerations

In practice, operators must decide how RED fits into a broader queueing strategy. It can interact with buffer sizing, link asymmetry, and traffic composition. Its usefulness depends on whether the surrounding environment responds well to early congestion feedback.

8.4 Interaction with transport protocols

RED’s value is closely tied to how end hosts react to packet loss or marking. Transport protocols that reduce sending rates promptly can benefit from early signals. If senders do not respond effectively, the advantages of RED become less pronounced.

RED belongs to a wider family of queue management methods that aim to regulate delay and loss before buffers overflow. Some related approaches rely on different measurements or decision rules but share similar goals.

9.1 Blue

Blue is an active queue management method that adjusts drop probability based on packet loss and link idle events. It does not depend primarily on average queue size. Its feedback mechanism is different from RED’s threshold-based design.

9.2 CoDel

CoDel focuses on controlling packet delay by observing how long packets remain in the queue. It aims to reduce standing queues without requiring extensive parameter tuning. This makes it a distinct approach from RED’s average-occupancy model.

9.3 PIE

PIE, or proportional integral controller enhanced, adjusts dropping behavior using a control-theoretic feedback loop. It seeks to keep queue delay near a target. Like RED, it is intended to manage congestion proactively, but it uses a different control method.

9.4 Tail drop

Tail drop is the simplest queue discipline: packets are accepted until the buffer is full, then later arrivals are discarded. It requires little configuration but can lead to large queues and sudden loss bursts. RED was developed partly as an alternative to that behavior.

10 Historical context

RED emerged from research on congestion control and router queue behavior in the late twentieth century. It became one of the best-known active queue management algorithms and influenced later work in both theory and device design.

10.1 Origins of RED

RED was introduced to address limitations of full-queue dropping in packet networks. Its early formulation combined average queue monitoring with random early loss to provide advance warning of congestion. The concept represented a shift from passive buffering toward active management.

10.2 Influence on active queue management

The algorithm helped establish active queue management as an important topic in networking. Its core ideas, especially early signaling and probabilistic action, shaped later proposals and refinements. Many subsequent algorithms were developed in response to the strengths and weaknesses of RED.

10.3 Adoption in networking research and devices

RED became a standard reference point in networking studies and was incorporated into a range of implementation experiments. Even where it was not used as the final production policy, it served as a benchmark for comparing congestion management methods. Its influence remains visible in later queue management designs.