1.2.1 The Congestion Control Problem Definition

To define the congestion control problem more formally, consider the graph in Figure 1.2 in which the throughput of a data source has been plotted on the y-axis and the network traffic load from the source has been plotted on the x-axis. We observe the following:

To avoid congestion collapse, each data source should try to maintain the load it is sending into the network in the neighborhood of the knee. An algorithm that accomplishes this objective is known as a congestion avoidance algorithm; a congestion control algorithm tries to prevent the system from going over the cliff. This task is easier said than done and runs into the following challenge: The location of the knee is not known and in fact changes with total network load and traffic patterns. Hence, the problem of congestion control is inherently a distributed optimization problem in which each source has to constantly adapt its traffic load as a function of feedback information it is receiving from the network as it tries to stay near the knee of the curve.

The original TCP Tahoe algorithm and its descendants fall into the congestion control category because in the absence of support from the network nodes, the only way they can detect congestion is by filling up the network buffers and then detecting the subsequent packet drops as a sign of congestion. Many routers today implement a more sophisticated form of buffer management called Random Early Detection (RED) that provides early warnings of a congestive situation. TCP in combination with RED then qualifies as a congestion avoidance algorithm. Algorithms such as TCP Vegas operate the system around the knee without requiring special support in the network nodes.

Some of the questions that need to be answered in the design of a congestion control algorithm include the following (all of the new terms used below are defined in this chapter):

There is a function closely related to congestion control, called flow control, and often the two terms are used interchangeably. For the purposes of this book, flow control is defined as a function that is used at the destination node to prevent its receive buffers from overflowing. It is implemented by providing feedback to the sender, usually in the form of window-size constraints. Later in this book, we will discuss the case of video streaming in which the objective is to prevent the receive buffer from underflowing. We classify the algorithm used to accomplish this objective also in the flow control category.

1.2.2 Optimization Criteria for Congestion Control

This section and the next are based on some pioneering work by Chiu and Jain [2] in the congestion control area. They defined optimization criteria that the congestion control algorithms should satisfy, and then they showed that there is a class of controls called AIMD that satisfies many of these criteria. We start by enunciating the Chiu-Jain optimization criteria in this section.

Consider a network with N data sources and define r_i(t) to be the data rate (i.e., load) of the i^th data source. Also assume that the system is operating near the knee of the curve from Figure 1.2 so that the network rate allocation to the i^th source after congestion control is also given by r_i(t). We assume that the system operation is synchronized and happens in discrete time so that the rate at time (t+1) is a function of the rate at time t, and the network feedback received at time t. We will also assume that the network congestion feedback is received at the sources instantaneously without any delay.

Define the following optimization criteria for selecting the best control:

• Efficiency: Every source has a bottleneck node, which is the node where it gets the least throughput among all the nodes along its path. Let A_i be the set of other sources that also pass through this bottleneck node; then the efficiency criterion states that $\sum _{j\in A_i}{r}_i(n)$ should be as close as possible to C, where C is the capacity of the bottleneck node.

• Fairness: The efficiency criterion does not put any constraints on how the data rates are distributed among the various sources. A fair allocation is when all the sources that share a bottleneck node get an equal allocation of the bottleneck link capacity. The Jain fairness index defined below quantifies this notion of fairness.

$F(r_1,\dots ,r_N)=\frac{{\left(\sum r_i\right)}^2}{N\left(\sum r_i^2\right)}$ (1)

(1)

Note that this index is bounded between 0 and 1, so that a totally fair allocation (with all r_i’s equal) has an index of 1, but a totally unfair allocation (in which the entire capacity is given to one user) has an index of 1/N.

• Convergence: There are two aspects to convergence. The first aspect is the speed with which the rate r_i(t) gets to its equilibrium rate at the knee after starting from zero (called responsiveness). The second aspect is the magnitude of its oscillations around the equilibrium value while in steady state (called smoothness).

1.2.3 Optimality of Additive Increase Multiplicative Decrease Congestion Control

In this section, we restrict ourselves to a two-source network that shares a bottleneck link with capacity C. As shown in Figure 1.3, any rate allocation (r₁,r₂) can be represented by a point in a two-dimensional space. The objective of the optimal congestion control algorithm is to bring the system close to the optimal point (C/2, C/2) irrespective of the starting position.

We assume that the system evolves in discrete time, such that at the n^th step the following linear controls are used:

Rate Increase Rule

$r_i(n+1)=a_I+b_I{r}_i(n)\mathrm{i}=1,2\mathrm{if}\mathrm{the}\mathrm{bottleneck}\mathrm{is}\mathrm{not}\mathrm{congested}$ (2)

(2)

Rate Decrease Rule

$r_i(n+1)=a_D+b_D{r}_i(n)\mathrm{i}=1,2\mathrm{if}\mathrm{the}\mathrm{bottleneck}\mathrm{is}\mathrm{congested}$ (3)

(3)

Note the following special cases:

With reference to Figure 1.3, note the following:

• All allocations for which r₁+r₂=C are efficient allocations, which correspond to points on the “efficiency line” in Figure 1.3. All points below the efficiency line represent underloaded systems, and the correct control decision in this region is to increase the rates. Conversely, all points above the efficiency line represent overloaded systems, and the correct control decision in this region is to decrease the rates.

• All allocations for which r₁=r₂ are fair allocations, which corresponds to points on the “fairness line” in Figure 1.3. Also note that because the fairness at any point (r₁, r₂) is given by

$F(r_1,r_2)=\frac{{(r_1+r_2)}^2}{2(r_1^2+r_2^2)},$

multiplying both the rates by a factor b does not change the fairness, that is, (br₁, br₂) has the same fairness as (r₁, r₂). Hence all points on the straight line joining (r₁, r₂) to the origin have the same fairness and such a line is called an “equi-fairness” line.

• The efficiency line and the fairness line intersect at the point (C/2, C/2), which is the optimal operating point.

• The additive increase policy of increasing both users’ allocations by a_I corresponds to moving up along a 45-degree line. The multiplicative decrease policy of increasing both users’ allocations by b_I corresponds to moving along the line that connects the origin to the current operating point.

Figure 1.3 shows the trajectory of the two-user system starting from point a R₀ using an AIMD policy. Because R₀ is below the efficiency line, the policy causes an additive increase along a 45-degree line that moves the system to point R₁ (assuming a big enough increment value), which is above the efficiency line. This leads to a multiplicative decrease in the next step by moving to point R₂ toward the origin on the line that joins R₁ to the origin (assuming a big enough decrement value). Note that R₂ has a higher fairness index than R₀. This increase–decrease cycle repeats over and over until the system converges to the optimal state (C/2, C/2).

Using similar reasoning, it can be easily seen that with both the MIMD or the AIAD policies, the system never converges toward the optimal point but keeps oscillating back and forth across the efficiency line. Hence, these systems achieve efficiency but not fairness. The MIAD system, on the other hand, is not stable and causes one of the rates to blow up over time.

These informal arguments can be made more rigorous [2] to show that the AIMD policy given by

$r_i(n+1)=a_I+r_i(n)\mathrm{i}=1,2$ (4)

(4)

$r_i(n+1)=b_D{r}_i(n)\mathrm{i}=1,2$ (5)

(5)

is the optimal policy to achieve the criteria defined in Section 1.2.2. Indeed, most of the algorithms for congestion control that are described in this book adhere to the AIMD policy. This analysis framework can also be extended to nonlinear increase–decrease algorithms of the type

$r_i(n+1)=r_i(n)+\alpha {(r_i(n))}^k$ (6)

(6)

Nonlinear algorithms have proven to be especially useful in the congestion control of high-speed links over large propagation delays, and several examples of this type of algorithm are presented in Chapter 5 of this book.

Two assumptions were made in this analysis that greatly simplified it: (1) the network feedback is instantaneous, and (2) the sources are synchronized with each other and operate in discrete time. More realistic models of the network that are introduced in later chapters relax these assumptions; as a result, the analysis requires more sophisticated tools. The simple equations 2 and 3 for the evolution of the transmit rates have to be replaced by nonlinear delay-differential equations, and the proof of system stability and convergence requires sophisticated techniques from control theory such as the Nyquist criterion.

1.2.4 Window-Based Congestion Control

Window-based congestion control schemes have historically preceded rate-based schemes and, thanks to the popularity of TCP, constitute the most popular type of congestion control scheme in use today. As shown in Figure 1.4, a window whose size can be set either in bytes or in multiples of the packet size drives the basic operation. Assuming the latter and a window size of N packets, the system operates as follows:

This simple windowing scheme with the Go Back N Acking strategy is basically the way in which TCP congestion control operated before 1988.

Figure 1.5 illustrates the mechanism by which a simple static window scheme is able to react to congestion in the network. This served as the primary means of congestion control in the Internet before the introduction of the TCP Slow Start algorithm. As shown, if a node is congested, then the rate at which ACKs are sent back is precisely equal to the rate at which the congested node is able to serve the packets in its queue. As a result, the source sending rate gets autoregulated to the rate at which the bottleneck node can serve the packets from that source. This is also known as the “self-clocking” property and is one of the benefits of the window-based congestion control over the rate-based schemes.

The window-based scheme also functions as an effective flow control algorithm because if the destination is running out of buffers, then it can withhold sending ACKs and thereby reduce the rate at which packets are being transmitted in the forward direction.

Readers will notice that there are a number of potential problems with the static window congestion control algorithm. In particular:

Partially as a result of a lack of mechanism to address the first two issues, the Internet suffered a so-called “congestion collapse” in 1986, during which all traffic ground to a halt. As a result, a number of proposals made by Van Jacobsen and Karels [1] were adopted that addressed these shortcomings. These are described in detail in Section 1.3.

1.2.5 Rate-Based Congestion Control

Instead of using a window to regulate the rate at which the source is sending packets into the network, the congestion control algorithm may alternatively release packets using a packet rate control mechanism. This can be implemented by using a timer to time the interpacket intervals. In practice, the end-to-end rate-based flow control (EERC) algorithm, which was part of the Asynchronous Transfer Mode (ATM) Forum Available Bit Rate (ABR) traffic management scheme, was one instance when a rate-based control was actually put into practice [3]. However, because ABR was not widely implemented in even ATM networks, there is less practical experience with rate-based schemes than with dynamic window schemes. More recently, rate-based control has been used for the TCP Friendly Rate Control (TFRC) algorithm, which is used for streaming applications. Video streaming was thought to be an area in which rate-based control fits in more naturally than window-based control. However, even for video, the industry has settled on a scheme that uses TCP for congestion control for reasons that are explained in Chapter 6. Rate control has been used in recent years in non-TCP contexts, and a couple of examples of this are provided in this book: The IEEE802.1Qau algorithm, also known as Quantum Congestion Notification (QCN; see Chapter 8), uses rate-based control, and so does the Google Congestion Control (GCC; see Chapter 9) algorithm that is used for real-time interbrowser communications.

Compared with window-based schemes, rate-based schemes have the following disadvantages:

1.2.6 End-to-End versus Hop-by-Hop Congestion Control

In the discussion thus far, we have implicitly assumed that the congestion control mechanism exists on an end-to-end basis (i.e., other than providing congestion feedback, the network nodes do not take any other action to relieve the congestion). However, there exists an alternate design called hop-by-hop congestion control, which operates on a node-by-node basis. Such a scheme was actually implemented as part of the IBM Advanced Peer to Peer Network (APPN) architecture [4] and was one of the two competing proposals for the ATM ABR congestion control algorithm [3].

Hop-by-hop congestion control typically uses a window-based congestion control scheme at each hop and operates as follows: If the congestion occurs at the n^th node along the route and its buffers fill up, then that node stops sending ACKs to the (n-1)^rst node. Because the (n-1)^rst node can no longer transmit, its buffers will start to fill up and consequently will stop sending ACKs to the (n-2)^nd node. This process continues until the backpressure signal reaches the source node. Some of the benefits of hop-by-hop congestion control are:

Note that these benefits require that the hop-by-hop window be controlled on a per-connection basis. This can lead to greater complexity of the routing nodes within the network, which is the reason why hop-by-hop schemes have not found much favor in the Internet community, whose design philosophy has been to push all complexity to the end nodes and keep the network nodes as simple as possible.

The big benefit of hop-by-hop schemes is that they react to congestion much faster than end-to-end schemes, which typically take a round trip of latency or longer. The rise of DCNs, which are very latency sensitive, has made this feature more attractive, and as seen in Chapter 7, some recent data center–oriented congestion control protocols feature hop-by-hop congestion control. Also, hop-by-hop schemes are attractive for systems that cannot tolerate any packet loss. An example of this is the Fiber Channel protocol used in Storage Area Networks (SAN), which is a user of hop-by-hop congestion control.

1.2.7 Implicit versus Explicit Indication of Network Congestion

The source can either implicitly infer the existence of network congestion, or the network can send it explicit signals that it is congested. Both of these mechanisms are used in the Internet. Regular TCP is an example of a protocol that implicitly infers network congestion by using the information contained in the ACKs coming back from the destination, and TCP Explicit Congestion Notification (ECN) is an example of a protocol in which the network nodes explicitly signal congestion.

1.3.1 Basic TCP Windowing Operations

TCP uses byte-based sequence numbering at the transport layer. The sender maintains two counters:

To maintain the window operation, the sender enforces the following rule:

$(SN-ASN)\le W$ (7)

(7)

where W is the transmit window size in bytes and SN is the sequence number of the next packet that sender wishes to transmit. If the inequality is not satisfied, then the transmit window is full, and no more packets can be transmitted.

The receiver maintains a single counter:

The receiver inserts the NSN value into the ACK field of the next packet that is being sent back. Note that ACKs are cumulative, so that if one of them is lost, then the next ACK makes up for it. Also, an ACK is always generated even if SN of a received packet does not match the NSN. In this case, the ACK field will be set to the old NSN again. This is a so-called Duplicate ACK, and as discussed in Section 1.3.4, the presence of Duplicate ACKs can be used by the transmitter as an indicator of lost packets, and indirectly, network congestion.

ACKs are usually piggybacked on the data flowing back in the opposite direction, but if there is no data flowing back, then the receiver generates a special ACK packet with an empty data field. To reduce the number of ACK packets flowing back, most receiver implementations start a 200-msec timer on receipt of a packet, and if another packet arrives within that period, then a single ACK is generated. This rule, which is called Delayed ACKs, cuts down the number of ACKs flowing back by half.

The receiver also implements a receive window (RW), whose value is initially set to the number of bytes in the receive buffer. If the receiver has one or more packets in the receive buffer whose total size is B bytes, then it reduces the RW size to RW=(RW−B). All ACKs generated at the receiver carry the current RW value, and on receipt of the ACK, the sender sets the transmit window to W=min(W, RW). This mechanism, which was referred to as flow control in Section 1.2.1, allows the receiver with insufficient available buffer capacity to throttle the sender.

Note that even though TCP maintains byte counters to keep track of the window sizes, the congestion control algorithms to be described next are often specified in terms of packet sizes. The packet that is used in these calculations is of size equal to the TCP packet size.

1.3.2 Window Size Decrements, Part 1: Timer Operation and Timeouts

The original TCP congestion control algorithm used a retransmit timer as the sole mechanism to detect packet losses and as an indicator of congestion. This timer counts in ticks of 500-msec increments, and the sender keeps track of the number of ticks between when a packet is transmitted and when its gets ACKed. If the value of the timer exceeds the value of the retransmission timeout (RTO), then the sender assumes that the packet has been lost and retransmits it. The sender also takes two other actions on retransmitting a packet:

Choosing an appropriate value for RTO is critical because if the value is too low, then it can cause unnecessary timeouts, and if the value is too high, then the sender will take too long to react to network congestion. The current algorithm for RTO estimation was suggested by Jacobsen and Karels [1] and works as follows:

Define the following:

The calculations are as follows:

$\begin{array}{l}Err=M-A\hfill \\ A\leftarrow A+gErr\hfill \\ D\leftarrow D+h(|Err|-D)\hfill \\ RTO=A+4D\hfill \end{array}$ (8)

(8)

Before Jacobsen and Karels’ [1] work, the RTO value was set to a multiple of A alone, which underestimated the timeout value, thus leading to unnecessary retransmissions.

1.3.3 Window Size Increments: Slow Start and Congestion Avoidance

1.3.3.1 Slow Start

The windowing algorithm described in Section 1.3.1 assumed static windows. Among other problems, this led to the scenario whereby on session start-up, a whole window full of packets would be injected at back to back into the network at full speed. This led to packet drops as buffers became overwhelmed. To correct this problem, Jacobsen and Karels [1] proposed the Slow Start algorithm, which operates as follows:

• At the start of a new session, set the TCP transmit window size to W=1 packet (i.e., equal to MSS bytes). The sender sends a packet and waits for its ACK.

• Every time an ACK is received, increase the window size by one packet (i.e., W←W+1).

Even though the algorithm is called Slow Start, it actually increases the window size quite rapidly: W=1 when the first packet is sent. When the ACK for that packet comes back, W is doubled to 2, and two packets are sent out. When the ACK for the second packet arrives, then W is set to 3, and the ACK for the third packet causes W to increase to 4. Hence, during the Slow Start phase, the correct reception of each windowfull of packets causes the W to double (i.e., the increase is exponential) (Figure 1.6). The rapid increase is intentional because it enables the sender to quickly increase its bandwidth to the value of the bottleneck capacity along its path, assuming that the maximum window size is large enough to achieve the bottleneck capacity. If the maximum window size is not large enough to enable to connection to get to the bottleneck capacity, then the window stops incrementing when the maximum window size is reached. Also note that during the Slow Start phase, the receipt of every ACK causes the sender to inject two packets into the network, the first packet because of the ACK itself and second packet because the window has increased by 1.

1.3.3.2 Congestion Avoidance

During normal operation, the Slow Start algorithm described in Section 1.3.3.1 is too aggressive with its exponential window increase, and something more gradual is needed. The congestion avoidance algorithm, which was also part of Van Jacobsen and Karels’ [1] 1988 paper, leads to a linear increase in window size and hence is more suitable. It operates as follows:

1. Define a new sender counter called ssthresh. At the start of the TCP session, ssthresh is initialized to large value, usually 64 KBytes.

2. Use the Slow Start algorithm at session start, which will lead to an exponential window increase, until the bottleneck node gets to the point where a packet gets dropped (assuming that there are enough packets being transmitted for the system to get to this point). Let’s assume that this happens at W=W_f.

3. Assuming that the packet loss is detected because of a timer expiry, then the sender resets the window to W=1 packet (i.e., MSS bytes) and sets ssthresh=W_f/2 bytes.

4. After the session successfully retransmits the lost packet, the Slow Start algorithm is used to increment the window size until W≥ssthresh bytes. Beyond this value, the window is increased using the following rule on the receipt of every ACK packet:

$\mathrm{W}\leftarrow \mathrm{W}+1/\mathrm{W}\mathrm{in}\mathrm{units}\mathrm{of}\mathrm{packets}$ (9)

(9)

5. In step 3, if the packet gets dropped because of Duplicate ACKs (these are explained in Section 1.3.4) rather than a timer expiry, then a slightly different rule is used. In this case, the sender sets W=W_f/2 as well as ssthresh=W_f/2. After the lost packet is recovered, the sender directly transitions to the congestion avoidance phase (because W=ssthresh) and uses equation 9 to increment its windows.

Note that as a result of the window increment rule (equation 9), the receipt of ACKs for an entire window full of packets leads to an increase in W by just one packet. Typically, it takes a round trip or more to transmit a window of packets and receive their ACKs; hence, under the congestion avoidance phase, the window increases by at most one packet in every round trip (i.e., a linear increase) (see Figure 1.6) This allows the sender to probe whether the bottleneck node is getting close to its buffer capacity one packet at a time, and indeed if the extra packet causes the buffer to overflow, then at most one packet is lost, which is easier to recover from.

1.3.4 Window Size Decrements, Part 2: Fast Retransmit and Fast Recovery

Section 1.3.3 discusses the rules that TCP Reno uses to increment its window in the absence of network congestion. This section discusses the rules that apply to decrementing the window size in the presence of congestion. TCP uses the design philosophy that dropped packets are the best indicator of network congestion, which falls within the implicit congestion indicator category from Section 1.2.4. When TCP Slow Start was first designed, this was the only feedback that could be expected from the simpler routers that existed at that time. In retrospect, this decision came with a few issues: The only way that the algorithm can detect congestion is by driving the system into a congestive state (i.e., near the cliff of the curve in Figure 1.2). Also, if the packet losses are because of a reason other than congestion (e.g., link errors), then this may lead to unnecessary rate decreases and hence performance loss. This problem is particularly acute for error-prone wireless links, as explained in Chapter 4.

As alluded to in Section 1.3.3.2, TCP uses two different mechanisms to detect packet loss. The first technique uses the retransmit timer RTO and is discussed in Section 1.3.2. The second technique is known as Fast Retransmit (Figure 1.7) and tries to make the system more responsive to packet losses. It works as follows:

The justification for this is the following: When the receiver finally receives the missing packet, the next ACK acknowledges all the other packets that it has received in the window, which on the average can be half the transmit window size. When the sender receives this ACK, it is allowed to transmit up to half a window of back-to-back packets (because W is now at half the previous value), which can potentially overwhelm the buffers in the bottleneck node. However, by doing FAST Recovery, the sender keeps sending additional packets while it waits for the ACK for the missing packet to arrive, and this prevents the sudden onslaught of new packets into the network. When the ACK for the missing packet arrives, W is set back to the ssthresh value in the previous step. This behavior can be seen in Figure 1.8; note that the window size shows a spike of 3 MSS on error detection and falls back to W/2 after the missing packet is received.

The Fast Retransmit mechanism is able to efficiently recover from packet losses as long as no more than one packet is lost in the window. If more than one packet is lost, then usually the retransmit timer for the second or later expires, which triggers the more drastic step of resetting W back to one packet.

1.3.5 TCP New Reno

Not long after the introduction of TCP Reno, it was discovered that it is possible to improve its performance significantly by making the following change to the Fast Recovery phase of the algorithm: If a Partial ACK is received during the Fast Recovery period that acknowledges some but not all of the packets that were outstanding at the start of the Fast Recovery period, then this is treated as an indication that the packet immediately following the acknowledged packet has also been lost and should be retransmitted. Thus, if multiple packets are lost within a single window, then New Reno can recover without a retransmission timeout by retransmitting one lost packet per round trip until all the lost packets from the window have been retransmitted. New Reno remains in Fast Recovery until all data outstanding at the start of the Fast Recovery phase has been acknowledged.

In this book, we will assume that legacy TCP implies Reno, with the understanding that the system has also implemented the New Reno changes.

1.3.6 TCP Reno and AIMD

Even though it may not be very clear from the description of TCP Reno in the last few sub-sections, this algorithm does indeed fall into the class of AIMD congestion control algorithms. This can be most clearly seen by writing down the equations for the time evolution of the window size.

In the Slow Start phase, as per the description in Section 1.3.3.1, the window size after n round trip times is given by

$W(nT)=2^n{W}_0$ (10)

(10)

where W₀ is the initial window size. This equation clearly captures the exponential increase in window size during this phase.

During the Congestion Avoidance phase (Section 1.3.3.2), the window size evolution is given by

$W\leftarrow W+1\mathrm{per}\mathrm{round}\mathrm{trip}\mathrm{delay}$ (11)

(11)

because each returning ACK causes the window size to increase by 1/W, and equation 11 follows from the fact that there are W returning ACKs for a window of size W.

Detection of a lost packet at time t because of Duplicate ACKs causes a reduction in window size by half, so that

$W\leftarrow \frac{W}{2}$ (12)

(12)

Note that with New Reno, multiple packet losses within a window result in a single reduction in the window size.

The AIMD nature of TCP Reno during the congestion avoidance/fast retransmit phases is clearly evident from equations 11 and 12.

1.4.1 Passive Queue Management

The simplest congestion feedback that a switch can send back to the source is by simply dropping a packet when it runs out of buffers, which is referred to as tail-drop feedback. This was how most routers and switches operated originally, and even today it is used quite commonly. Packet loss triggers congestion avoidance at the TCP source, which takes action by reducing its window size.

Even though tail-drop feedback has the virtue of simplicity, it is not an ideal scheme for the following reasons:

An attempt to improve on this led to the invention of RED-based queue management, which is described in the next section.

1.4.2 Active Queue Management (AQM)

To correct the problems with tail-drop buffer management, Floyd and Jacobsen [5] introduced the concept of AQM, in which the routing nodes use a more sophisticated algorithm called RED to manage their queues. The main objectives of RED are the following:

As explained later, RED provides congestion feedback to the source when the average queue size exceeds some threshold, either by randomly dropping a packet or by randomly marking the ECN bit in a packet. Furthermore, the packet dropping probability is a function of the average queue size, as shown in Figure 1.9.

The RED algorithm operates as follows:

For each packet arrival,

1. Calculate the average queue size avg as $avg\leftarrow (1-w_q)avg+w_{q}q$, where q is the current queue size. The smoothing constant w_q determines the time constant of this low-pass filter. This average is computed every time a packet arrives at the node.

2. Define constants min_th and max_th, such that min_th is the minimum threshold for the average queue size and max_th is the maximum threshold for the average queue size (see Figure 1.9). If ${\min }_{th}\le avg\le {\max }_{th}$, then on packet arrival, calculate the probability p_b and p_a as

$\begin{array}{l}{p}_b\leftarrow \frac{{\max }_p(avg-{\min }_{th})}{({\max }_{th}-{\min }_{th})}\hfill \\ p_a\leftarrow \frac{p_b}{(1-count\cdot p_b)}\hfill \end{array}$ (13)

(13)

where max_p is the maximum value for p_b and count is the number of packets received since the last dropped packet. Drop the arriving packet with probability p_a. Note that p_a is computed such that after each drop, the algorithm uniformly chooses one of the next 1/p_b packets to drop next.
This randomized selection of packets to be dropped is designed to avoid the problem of synchronized losses that is seen in tail-drop queues.

3. If $avg\ge {\max }_{th}$, then drop the arriving packet.

RED has been heavily analyzed, with the objective of estimating the optimal queue thresholds and other parameters. Some of this work is covered in Chapter 3, where tools from optimal control theory are brought to bear on the problem. In general, researchers have discovered that RED is not an ideal AQM scheme because there are issues with its responsiveness and ability to suppress queue size oscillations as the link capacity or the end-to-end latency increases. Choosing a set of RED parameters that work well across a wide range of network conditions is also a nontrivial problem, which has led to proposals that adapt the parameters as network conditions change.

However, it is widely implemented in routers today, and furthermore, all the analysis work done on RED has led to the discovery of other more effective AQM schemes. More recent AQM algorithms that build off the ideas in RED include the Data Center Congestion Control Protocol (DCTCP) (see Chapter 7), the IEEE 802.1Qau QCN algorithm (see Chapter 8), and an influential protocol designed for high-speed networks called eXpress Control Protocol (XCP) (see Chapter 5).

Floyd [6] also went on to design a follow on enhancement to RED called ECN. In ECN systems, the queue does not discard the packet but instead marks the ECN bits in TCP packet header. The receiver then receives the marked packets and in turn marks the ECN bit in the returning ACK packet. When the sender receives ACKs with marked packets, then it reacts to them in the same way as if it had detected a lost packet using the duplicate ACK mechanism and proceeds to reduce its window size. This avoids unnecessary packet drops and thus unnecessary delays for packets. It also increases the responsiveness of the algorithm because the sender does not have to wait for three duplicate ACKs before it can react to congestion.