4.4.1 Available Bandwidth Estimation and TCP Westwood

A number of TCP algorithms that use ABE to set their window sizes have appeared in the literature. The original one was proposed by Casetti et al. [4], and the resulting TCP congestion algorithm was named TCP Westwood. This still remains one of the more popular algorithms in this category and is currently deployed in about 3% of servers worldwide (see Yalu [5]).

The TCP Westwood source attempts to measure the rate at which its traffic is being received, and thus the bottleneck rate, by filtering the stream of returning ACKs. This algorithm does not use out-of-band probing packets to measure throughput because they have been shown to significantly bias the resulting measurement. It was later shown that the original Westwood proposal overestimates the connection bandwidth because of the phenomenon of ACK compression [6]. In this section, we will present a slightly modified version called TCP Westwood+, which corrects for this problem.

The rate_control procedure for the original TCP Westwood is as follows:

rate_control( )

 {

     if (n DUPACKS are received)

          ssthresh = (ABE * RTT_min)/seg_size

          if (cwin > ssthresh)

                 cwin = ssthresh

          endif

     endif

     if (coarse timeout expires)

            ssthresh = (ABE * RTT_min)/seg_size

             if ssthresh < 2

               ssthresh = 2

            endif

     cwnd = 1

     endif

}

In the above pseudocode, ABE is the estimated connection bandwidth at the source, RTT_min is the estimated value of the minimum round trip delay, and seg_size is the TCP packet size. The key idea in this algorithm is to set the window size after a congestion event equal to an estimate of the bottleneck rate for the connection rather than reducing the window size by half as Reno does. Hence, if the packet loss is attributable to link errors rather than congestion, then the window size remains unaffected because the ABE value does not change significantly as a result of packet drops.

Note that from the discussion in Chapter 2, ABE*RTT is an estimate of the ideal window size that the connection should use, given estimated bandwidth ABE and round trip latency RTT. However, by using RTT_min instead of RTT, Westwood sets the window size to a smaller value, thus helping to clear out the backlog at the bottleneck link and creating space for other flows.

The key innovation in Westwood was to estimate the ABE using the flow of returning ACKs, as follows:

Define the following:

The LPF estimate of the bandwidth is then given by

${\hat{R}}_k=\frac{2\tau -{\mathrm{\Delta }}_k}{2\tau +{\mathrm{\Delta }}_k}{\hat{R}}_{k-1}+\frac{{\mathrm{\Delta }}_k}{2\tau +{\mathrm{\Delta }}_k}(R_k+R_{k-1})$ (6)

(6)

As pointed out by Mascolo et al. [7], low-pass filtering is necessary because congestion is caused by the low-frequency components and because of the delayed ACK option. The filter coefficients are time varying to counteract the fact that the sampling intervals ${\mathrm{\Delta }}_k$ are not constant.

It was subsequently shown [6,7] that the filter (equation 6) overestimates the available bandwidth in the presence of ACK compression. ACK compression is the process in which the ACKs arrive back at the source with smaller interarrival times that do not reflect the bottleneck bandwidth of the connection. To correct this problem, Mascolo et al. [7] made the following change to the filtering algorithm to come up with Westwood+: Instead of computing the bandwidth R_k after every ACK is received, compute it once every RTT seconds. Hence, if D_k bytes are acknowledged during the last RTT interval ${\mathrm{\Delta }}_k$, then

$R_k=\frac{D_k}{{\mathrm{\Delta }}_k}$ (7)

(7)

By doing this, Westwood+ evenly spreads the bandwidth samples over the RTT interval and hence is able to filter out the high-frequency components caused by ACK compression.

Note that the window size after a packet loss is given by

$W\leftarrow \hat{R}\times Twhere\hat{R}(t)=\frac{W(t)}{T_s}$

where T is the minimum round trip latency and T_s is the current smoothed estimate of the round trip latency. This can also be written as

$W\leftarrow W\frac{T}{T_s}$

Hence, the change in window size is given by W(T_s−T)/T_s. This equation shows that Westwood uses a multiplicative decrease policy, where the amount of decrease is proportional to the queuing delay in the network. It follows that TCP Westwood falls in the class of additive increase/multiplicative decrease (AIMD) algorithms; however, the amount of decrease may be more or less than that of TCP Reno, depending on the congestion state of the network. Hence, it is important to investigate its fairness when competing with other Westwood connections and with Reno connections. Casetti et al. [4] carried out one such simulation study in which they showed that when competing with Reno connections, Westwood gets 16% more bandwidth than its fair share, which they deemed to be acceptable. Figure 4.3 shows the throughput of Westwood and Reno as a function of link error rate for a link of capacity 2 mbps. As can be seen, there is a big improvement in Westwood throughput over that of Reno when the loss rates are around 0.1%.

Other schemes to estimate the connection bandwidth include the work by Capone et al. [8] as part of their TCP TIBET algorithm, in which they use a modified version of the filter used in the Core Stateless Fair Queuing Estimation algorithm [9] and obtained good results. Another filter was proposed by Xu et al. [10] as part of their TCP Jersey design. This filter was derived from the Time Sliding Window (TSW) estimator that was proposed by Clarke and Fang [11].

4.4.1.1 TCP Westwood Throughput Analysis

It has been shown by Greico and Mascolo [12] that the expected throughput of TCP Westwood in the presence of link error rate p is given by

$R_{avg}\propto \frac{1}{\sqrt{p{T}_s(T_s-T)}}$ (8)

(8)

Equation 8 can be derived used the machinery developed in Section 3.2.1 of Chapter 3, and we proceed to so next using the same notation that was used there. Recall that in the fluid limit, the window size for TCP Reno obeyed the following equation (equation 29 in Chapter 3):

$\frac{dW(t)}{dt}=\frac{R(t-T(t))[1-Q(t)]}{W(t)}-\frac{R(t-T(t))Q(t)W(t)}{2}$ (9)

(9)

For TCP Westwood, the first term on the RHS remains the same because this governs the window size increase during the congestion avoidance phase. The second term changes because the window decrease rule is different, and the resulting equation is given by

$\frac{dW(t)}{dt}=\frac{R(t-T(t))[1-Q(t)]}{W(t)}+R(t-T(t))Q(t)(\hat{R}(t)T-W(t))$ (10)

(10)

In equation 10 we replaced $\frac{W(t)}{2}$, which is window decrease rule for Reno by $\hat{R}(t)T-W(t)$, which the window change under Westwood. Next using the approximation that $R(t)\approx \frac{W(t)}{T_s}$ and $\hat{R}(t)\approx R(t)$, we obtain

$\frac{dR(t)}{dt}=\frac{1-Q(t)}{T_s^2}+Q(t)R^2(t)\frac{T}{T_s}-Q(t)R^2(t)$ (11)

(11)

Setting $\frac{dR(t)}{dt}=0$ and Q(t)=P(t-T)=p, in equilibrium, we obtain

$R_{avg}=\frac{1}{\sqrt{T_s(T_s-T)}}\sqrt{\frac{1-p}{p}}\approx \frac{1}{\sqrt{p{T}_s(T_s-T)}}$ (12)

(12)

where R_avg and p are the steady state values of R(t) and P(t), respectively.

Assuming that the queuing delay (T_s–T) can be written as a fraction k of the average round trip latency,

$T_s-T=k{T}_s\mathrm{such}\mathrm{that}0\le k\le 1.$

Then equation 12 can be written as

$R_{avg}=\frac{1}{T_s}\sqrt{\frac{1}{kp}}$

On comparing this equation with that for TCP Reno, it follows that TCP Westwood has the effect of a net reduction in link error rate by the fraction k. This reduction is greatest when the queuing delay is small compared with the end-to-end latency. From this, it follows that Westwood is most effective over long-distance links and least effective in local area network (LAN) environments with a lot of buffering.

4.4.2 Loss Discrimination Algorithm (LDA)

Loss Discrimination Algorithms are useful tools that can be used to differentiate between packet losses caused by congestion versus those caused by link errors. This information can be used at sender to appropriately react on receiving duplicate ACKs by not reducing the window size if link errors are the cause of the packet drop.

We will describe an LDA that was proposed by Fu and Liew as part of their TCP Veno algorithm [13]. This mechanism was inspired by the rules used by TCP Vegas to detect an increase in queue size along the connection’s path.

Readers may recall from the description of TCP Vegas from Chapter 1 that this algorithm uses the difference between expected throughput and the actual throughput values to gauge the amount of congestion in the network. Defining R_E(t) to be the expected value of the throughput and D(t) the difference between the throughputs, we have

$D(t)=R_E(t)-R(t)=\frac{W(t)}{T}-\frac{W(t)}{T_s}=R(t)[T_s-T]$ (13)

(13)

In equation 13, T_s is a smoothed value of the measured round trip time. By Little’s law, D(t) equals the queue backlog along the path.

The congestion indicator in the LDA is set to 0 if D(t) is less than 3 and is set to 1 otherwise. Fu and Liew [13] used this rule in conjunction with Reno’s regular multiplicative decrease rule and a slightly modified additive increase rule and observed a big increase in TCP performance in the presence of random errors.

Another LDA was proposed by Xu et al. [10] and works as follows: Unlike the LDA described earlier, this LDA requires that the network nodes pass on congestion information back to the source by appropriately marking the ACK packets traveling in the reverse direction if they observe that their average queue length has exceeded some threshold. The average queue length is computed using a low-pass filter in exactly the same way as for marking packets in the RED algorithm. The only difference is that a much more aggressive value for the smoothing parameter is used. Xu et al. [10] suggest a value of 0.2 for the smoothing parameter as opposed to 0.002, which is used for RED. Using this LDA, they showed that their algorithm, TCP Jersey, outperformed TCP Westwood for the case when the link error rate equaled or exceeded 1%, and they attributed this improvement to the additional boost provided by the LDA.

4.4.3 Zero Receive Window (ZRW) ACKs

A problem that is unique to wireless is that the link may get disconnected for extended periods, for a number of different reasons. When this happens, the TCP source will time out, perhaps more than once, resulting in a very large total time-out interval. As a result, even after the link comes back up, the source may still be in its time-out interval.

The situation described can be avoided by putting the TCP source into a state where it freezes all retransmit timers, does not cut down its congestion window size, and enters a persist mode. This is done by sending it an ACK in which the receive window size is set to zero. In this mode, the source starts sending periodic packets called Zero Window Probes (ZWPs). It continues to send these packets until the receiver responds to a ZWP with a nonzero window size, which restarts the transmission.

There have been two proposals in the literature that use ZRW ACKs to combat link disconnects:

In general, client disconnect times have been steadily reducing as the mobile hand-off protocols improve from GPRS onward to LTE today. Hence, the author is not aware of any significant deployment of these types of protocols. They may be more relevant to wireless local area networks (WLANs) or ad-hoc networks in which obstructions could be the cause of link disconnects.

4.4.4 TCP with Available Bandwidth Estimates and Loss Discrimination Algorithms

The following pseudocode, adapted from Xu et al. [10], describes the modified congestion control algorithm in the presence of both the ABE and LDA algorithms. Note that the variable LDA is set to 1 if the sender decides that the packet loss is attributable to congestion and set to 0 if it is attributable to link errors. Also, SS, CA, fast_recovery, and explicit_retransmit are the usual TCP Reno Slow Start, Congestion Avoidance, Fast Recovery, and packet retransmission procedures as described in Chapter 1. An example of a rate_control procedure is the one given for TCP Westwood in Section 4.4.1.

recv( )                                  1

 {

      ABE( )                            2

      If ACK and LDA= 0                     3

            SS( ) or CA( )                4

      end if                            5

      if ACK and LDA= 1                     6

            rate_control( )                7

            SS( ) or CA( )                 8

      end if                            9

      if nDUPACK and LDA = 1                    10

          rate control( )                   11

          explicit_retransmit( )               12

          fast_recovery( )                   13

      end if                             14

      if nDUPACK and LDA = 0                    15

          explicit_retransmit( )               16

           fast_recovery( )                  17

      end if                             18

  }

Note that if packet loss is detected (nDUPACK=true) but LDA=0 (i.e., there is no congestion detected), then the source simply retransmits the missing packet (line 16) without invoking the rate_control procedure. On the other hand, even if there is no packet loss but congestion is detected, then the source invokes rate_control without doing any retransmits (lines 6–9).

4.5.1 Performance of TCP with Link-Level Forward Error Correction (FEC)

Link-level FEC techniques include algorithms such as convolutional coding, turbo coding, and Reed-Solomon coding, and all modern cellular protocols, including 3G and LTE, incorporate them as part of the physical layer. FEC algorithms were discovered in the 1950s, but until 1980 or so, their use was confined to space and military communications because of the large processing power they required. With the advances in semiconductor technology, link-level FEC is now incorporated in every wireless communication protocol today and has started to move up the stack to the transport and even application layers. The algorithms have also become better with time; for example, turbo coding, which was discovered in the 1990s, is a very powerful algorithm that takes the system close to the theoretical Shannon bound. When compared with ARQ, FEC has some advantages; ARQ results in additional variable latency because of retransmissions that can throw off the TCP retransmit timer, but this is not an issue for FEC. This is especially problematic for long satellite links, for which ARQ may be an inappropriate solution.

Following Barakat and Altman [18], we present an analysis of the TCP throughput over a link that is using a link-level block FEC scheme such as Reed-Solomon coding.

Define the following (Figure 4.4):

We now use the square-root formula (see Chapter 2) to derive an expression for the TCP throughput as a function of the link and FEC parameters.

Because there are KX FEC data units that make up a TCP packet, it follows that the average TCP throughput in the presence of FEC with parameters (N,K) is given by

$R_{avg}(N,K)=\min \left(\frac{KX}{T}\sqrt{\frac{3}{2p_{FEC}(N,K)}},\frac{K}{N}C\right)$ (14)

(14)

Also, as a result of the block FEC, the link capacity reduces by a factor of (K/N).

We now derive an expression for the TCP packet loss probability p(N,K).

A TCP packet is lost when one or more of the X LL PDUs that constitute it arrive in error. Hence, it follows that

$p_{FEC}(N,K)=1-{(1-q_T)}^X$ (15)

(15)

An LL PDU is lost when more than (N-K) of its FEC block units are lost because of transmission errors, which happens with probability

$q_T=\sum _{i=N-K+1}^N\left(\begin{array}{c}N\\ i\end{array}\right)q^i{(1-q)}^{N-i}$ (16)

(16)

From equations 15 and 16, it follows that the probability that a TCP packet is lost is given by

$p_{FEC}(N,K)=1-{\left[1-(\sum _{i=N-K+1}^N\left(\begin{array}{c}N\\ i\end{array}\right)q^i{(1-q)}^{N-i}\right)]}^X$ (17)

(17)

From equation 16, it is clear that the addition of FEC reduces the loss probability of LL PDUs (and as a result that of TCP packets), which results in an increase in TCP throughput as long as the first term in the minimum in equation 14 is less than the second term. As we increase N, we reach a point where the two terms become equal, and at this point, the FEC entirely eliminates all link errors. Any increase in FEC beyond this point results in the deterioration of TCP throughput (i.e., there is more FEC than needed to clean up the link). This implies that the optimal amount of FEC is the one that causes the two terms in equation 14 to be equal, that is,

$\frac{NX}{T}\sqrt{\frac{3}{2p_{FEC}(N,K)}}=C$ (18)

(18)

Figure 4.5 plots the TCP throughput as a function of the ratio N/K, for K=10, 20, and 30. Increasing N/K while keeping K fixed leads to more FEC blocks per LL PDU, which increases the resulting throughput. Figure 4.5 also plots (K/N)C and the intersection of this curve with the throughput curve is the point that is predicted by equation 18 with the optimal amount of FEC.

The analysis presented assumed that the LL PDU loss probabilities form an iid process. A more realistic model is to assume the Gilbert loss model, in which errors occur in bursts. This reflects the physics of an actual wireless channel in which burst errors are common because of link fading conditions. However, this complicates the analysis considerably, and a closed form simple expression is no longer achievable. Interested readers are referred to Barakat and Altman [18] for details of the analysis of this more complex model.

4.5.2 Performance of TCP with Link-Level Automatic Retransmissions and Forward Error Correction

Link-level ARQ or retransmission is an extremely effective way of reducing the link error rate. Figures 4.6A and 4.6B are plotted from measurements made from a functioning broadband wireless system [19] that has been commercially deployed. As shown in Figure 4.6A, even with an error rate as high as 10%, the TCP throughput remains at 40% of the maximum. Figure 4.6B shows that the throughput performance improves as the number of ARQ retransmissions is increased, but after six or so retransmissions, there is no further improvement. This is because at high error rates, the number of retransmissions required to recover a packet grows so large that the resulting increase in end-to-end latency causes the TCP retransmit timer to expire, thus resulting in a time-out. This observation also points to an important issue when using ARQ at the link layer. Because of its interaction with TCP’s retransmissions, ARQ can in fact make the overall performance worse if not used carefully. Hence, some guidelines for its use include:

Modern implementations of ARQ in wireless protocols such as LTE or WiMAX follow these rules in their design.

In this section, following Barakat and Fawal [20], we extend the analysis in Section 4.5.1 to analyze the performance of TCP over a link implementing a Selective Repeat ARQ scheme (in addition to FEC) and in-order delivery of packets to the IP layer at the receiver. We will reuse the definitions used in Section 4.5.1, so that a TCP packet of size KX FEC blocks is split into X LL PDUs, each of which is made up of K FEC blocks (see Figure 4.4). To each of these K FEC blocks we add (N-K) redundant FEC blocks to obtain a Reed Solomon–encoded LL PDU of size N FEC blocks. If the FEC does not succeed in decoding an LL PDU, the SR-ARQ scheme is invoked to recover it by doing retransmissions. The retransmissions will be done a maximum number of times, denoted by M. If the LL PDU fails to get through even after M retransmissions, the ARQ-SR assumes that it cannot be recovered and leaves its recovery to TCP.

Recall from equation 52 in Chapter 2 that the expression for average TCP throughput in the presence of random loss and time-outs is given by

$R_{avg}=\min \left(\frac{KX}{E(T_{ARQ})\sqrt{\frac{2p_{ARQ}}{3}}+RTO\cdot p_{ARQ}(1+32p_{ARQ}^2)\min \left(1,3\sqrt{\frac{3p_{ARQ}}{8}}\right)},\alpha C\right)$ (19)

(19)

where the throughput is in units of FEC units per second and $\alpha$ is the fraction of the link bandwidth lost because of the FEC and LL PDU retransmissions, p_ARQ is the probability that a TCP packet is lost despite ARQ, E(T_ARQ) is the average round trip latency, C is the capacity of the link, and RTO is the TCP timeout value.

Note that in equation 19, we have replaced T, which is the nonqueuing part of the round trip latency in equation 52 of Chapter 2, by the average value E(T_ARQ). The reason for this is that in the presence of ARQ, the nonqueuing part of the round trip latency is no longer fixed but varies randomly depending on the number of link retransmissions.

As in the previous section, we will assume that q is the probability that an LL PDU transmission fails because of link errors in the absence of FEC and ARQ. Note that to find R_avg, we need to find expressions for E(T_ARQ), p_ARQ, and $\alpha$ as functions of the link, ARQ, and FEC parameters q, N, K, M, and X.

The ARQ-SR receiver acknowledges each LL PDU either with an ACK or a NACK. The LL PDUs that are correctly received are resequenced before being passed on to the IP layer. A TCP packet is lost if one or more of its constituent LL PDUs is lost. Under the assumption that LL PDUs are lost independently of each other with loss rate q_F, we obtain the probability of a TCP packet loss as

$p_{ARQ}=1-{(1-q_F)}^X$ (20)

(20)

We now obtain an expression for q_F. Note that an LL PDU is lost if all M retransmissions fail, in addition to the loss of the original transmission, for a total of (M+1) tries. The probability that a single LL PDU transmission fails in the absence of ARQ but with FEC included is given by

$q_T=\sum _{i=N-K+1}^N\left(\begin{array}{c}N\\ i\end{array}\right)q^i{(1-q)}^{N-i}$ (21)

(21)

so that the probability that an LL PDU is lost after the M ARQ retransmissions is given by

$q_F=q_T^{M+1}$ (22)

(22)

By substituting equation 22 in equation 20, we obtain the following expression for the TCP packet loss probability p_ARQ in the presence of both FEC and ARQ:

$p_{ARQ}=1-{\left[1-{\left(\sum _{i=N-K+1}^N\left(\begin{array}{c}N\\ i\end{array}\right)q^i{(1-q)}^{N-i}\right)}^{M+1}\right]}^X$ (23)

(23)

To obtain an expression for $\alpha$, which is the amount of link bandwidth left over after the FEC and ARQ overheads are accounted for, note the following:

Hence, the fraction of the link bandwidth that is available for TCP packet transmission is given by

$\alpha ={(1-q_F)}^{X-1}(1-q_T)\frac{K}{N}$ (24)

(24)

We next turn to the task of finding the average round trip latency E(T_ARQ) for the TCP packets.

Define the following:

Then $\tau$ is given by

$\tau =2D+\frac{N}{C}$ (25)

(25)

Assume that all the X LL PDUs that make up a TCP packet are transmitted back to back across the link. Then the ith LL PDU starts transmission at time $\frac{(i-1)N}{C}$, and it takes $\frac{N}{C}+2D+M_i\tau$ seconds to finish its transmission and receive a positive acknowledgement. Hence, it follows that

$t=t_0+2D+\underset{1\le i\le X}{\max }\left(\frac{iN}{C}+M_i\tau \right)$ (26)

(26)

We will now compute the expected value of t under the condition that the TCP packet whose delay is being computed has been able to finish its transmission.

Define Z as

$Z=\underset{1\le i\le X}{\max }\left(\frac{iN}{C}+M_i\tau \right)$ (27)

(27)

It follows that

$E(T_{ARQ})=T_0+2D+E^0(Z)$ (28)

(28)

where

$E^0(Z)={\int }_0^{\frac{XN}{C}+M\tau }{P}^0(Z>z)dz$ (29)

(29)

Note that the upper limit of integration is given by $\frac{XN}{C}+M\tau$ because this is the maximum value of Z. Note that

$P^0(Z>z)=1-P^0(Z\le z)=1-\prod _{i=1}^X{P}^0\left(\frac{iN}{C}+M_i\tau \le z\right)$ (30)

(30)

so that

$E^0(Z)=\frac{XN}{C}+M\tau -\underset{0}{\overset{\frac{XN}{C}+M\tau }{\int }}\prod _{i=1}^X{P}^0\left\{M_i\le \lfloor \frac{z-\frac{iN}{C}}{\tau }\rfloor \right\}dz$ (31)

(31)

Next we derive a formula for the probability distribution for M_i.

Note that the probability that all X LL PDUs that make up the packet are received successfully (after ARQ) is given by ${(1-q_T^{M+1})}^X$ because the $q_T^{M+1}$ is the probability that an LL PDU is received in error even after M retransmissions. It follows that

$P^0(M_i=k)=\frac{q_T^k(1-q_T)}{1-q_T^{M+1}}and{P}^0(M_i\le k)=\frac{\sum _{j=0}^k{q}_T^k(1-q_T)}{1-q_T^{M+1}}=\frac{1-q_T^{k+1}}{1-q_T^{M+1}}$ (32)

(32)

Equations 23 and 32 can then be used to evaluate E⁰(Z) in equation 31. This allows us to evaluate T in equation 28 and subsequently the average TCP throughput by using equation 19.

4.6.1 Active Queue Management (AQM) Techniques to Combat Bufferbloat

AQM techniques such as Random Early Detection (RED) were designed in the mid 1990s but have not seen widespread deployment because of the difficulty in configuring them with the appropriate parameters. Also, the steadily increasing link speeds in wireline networks kept the network queues under control, so operators did not feel the need for AQM. However, the bufferbloat problem in cellular networks confronted them with a situation in which the size of the bottleneck queue became a serious hindrance to the system performance; hence, several researchers have revisited the use of traditional RED in controlling the queue size; this work is covered in Section 4.6.1.1.

Nichols and Jacobsen [21] have recently come up with a new AQM scheme called Controlled Delay (CoDel) that does not involve any parameter tuning and hence is easier to deploy. It is based on using delay in the bottleneck buffer, rather than its queue size, as the indicator for link congestion. This work is covered in Section 4.6.1.2.

4.6.1.1 Adaptive Random Early Detection

Recall from the description of RED in Chapter 1, that the algorithm requires that the operators choose the following parameters: the queue thresholds min_th and max_th, the maximum dropping probability max_p and the averaging parameter w_q. If the parameters are not set properly, then the analysis in Chapter 3 showed that it can lead to queue length oscillations, low link utilizations, or buffer saturation, resulting in excessive packet loss. Using the formulae in Chapter 3, it is possible to choose the appropriate parameters for a given value of the link capacity C, the number of connections N, and the round trip latency T. However, if any of these parameters is varying, as C is in the wireless case, then the optimal parameters will also have to change to keep up with it (i.e., they have to become adaptive).

Adaptive RED (ARED) was designed to solve the problem of automatically setting RED’s parameters [22]. It uses the “gentle” version of RED, as shown in Figure 4.8. The operator has to set a single parameter, which is the target queue size, and all the other parameters are automatically set and adjusted over time, as a function of this. The main idea behind the adaptation in ARED is the following: With reference to Figure 4.8, assuming that averaging parameter w_q and the thresholds min_th and max_th are fixed, the packet drop probability increases if the parameter max_p is increased and conversely decreases when max_p is reduced. Hence, ARED can keep the buffer occupancy around a target level by increasing max_p if the buffer size is more than the target and decreasing max_p if the buffer size falls below the target. This idea was originally proposed by Feng et al. [23] and later improved upon by Floyd et al. [22], who used an AIMD approach to varying max_p, as opposed to multiplicative increase/multiplicative decrease (MIMD) algorithm used by Feng et al. [23]

The ARED algorithm is as follows:

ared( )

Every interval seconds:

     If (avg> target and max_p <= 0.5)

          Increase max_p:

          max_p ← max_p + a

     elseif (avg<target and max_p>= 0.01)

          Decrease max_p:

          max_p ← max_p * b            1

The parameters in this algorithm are set as follows:

Avg: The smoothed average of the queue size computes as

$avg\leftarrow (1-w_q)avg+w_{q}q$

w_q: This is set to

$w_q=1-e^{-\frac{1}{C}}$ (34)

(34)

interval: The algorithm is run periodically every interval seconds, where interval=0.5 sec

a: The additive increment factor is set to a=min(0.01, max_p/4).

b: The multiplicative decrement factor is set to 0.9.

target: The target for the average queue size is set to the interval

$t\text{arg}et=[{\min }_{th}+0.4({\max }_{th}-{\min }_{th}),{\min }_{th}+0.6({\max }_{th}-{\min }_{th})]$

max_th: Is set to 3*min_th

min_th: This is the only parameter that needs to be manually set by the operator.

ARED was originally designed for wireline links, in which the capacity C is fixed and the variability is attributable to the changing load on the link (i.e., the number of TCP connections N). The algorithm needs to be adapted for the wireless case, in particular the use of equation 34 to choose w_q needs to be clarified because C is now varying. If w_q is chosen to be too large relative to the link speed, then it causes queue oscillations because the average tends to follow the instantaneous variations in queue size. Hence, one option is to choose the maximum possible value for the link capacity in equation 34, which would correspond to the mobile occupying the entire channel at the maximum modulation.

Also, the value of interval needs to be revisited because the time intervals during which the capacity changes are likely to be different than the time intervals during which the load on the link changes. Floyd et al. [22] showed through simulations that with interval=0.5 sec, it takes about 10 sec for ARED to react to an increase in load and bring the queue size back to the target level. This is likely too long for a wireless channel, so a smaller value of interval is more appropriate.

4.6.1.2 Controlled Delay (CoDel) Active Queue Management

The CoDel algorithm is based on the following observations about bufferbloat, which were made by Nichols and Jacobsen [21]:

• Networks buffers exist to absorb transient packet bursts, such as those that are generated during the slow-start phase of TCP Reno. The queues generated by these bursts typically disperse after a time period equal to the round trip latency of the system. They called this the “good” queue. In a wireless system, queue spikes can also be caused to temporary decreases in the link capacity.

• Queues that are generated because of a mismatch between the window size and the delay bandwidth product, as given by equation 33, are “bad” queues because they are persistent or long term in nature and add to the delay without increasing the throughput. These queues are the main source of bufferbloat, and a solution is needed for them.

Based on these observations, they gave their CoDel algorithm the following properties:

• Similar to the ARED algorithm, it is parameter-less

• It treats the “good” queue and “bad” queues, differently, that is, it allows transient bursts to pass through while keeping the nontransient queue under control.

• Unlike RED, it is insensitive to round trip latency, link rates, and traffic loads.

• It adapts to changing link rates while keeping utilization high.

The main innovation in CoDel is to use the packet sojourn time as the congestion indicator rather than the queue size. This comes with the following benefits: Unlike the queue length, the sojourn time scales naturally with the link capacity. Hence, whereas a larger queue size is acceptable if the link rate is high, it can become a problem when the link rate decreases. This change is captured by the sojourn time. Hence, the sojourn time reflects the actual congestion experienced by a packet, independent of the link capacity.

CoDel tracks the minimum sojourn time experienced by a packet, rather than the average sojourn time, because the average can be high even for the “good” queue case (e.g., if a maximum queue size of N disperses after one round trip time, the average is still N/2). On the other hand, if there is even one packet that has zero sojourn time, then it indicates the absence of a persistent queue. The minimum sojourn time is tracked over an interval equal to the maximum round trip latency over all connections using the link. Moreover, because the sojourn time can only decrease when a packet is dequeued, CoDel only needs to be invoked at packet dequeue time.

To compute an appropriate value for the target minimum sojourn time, consider the following equation for the average throughput that was derived in Section 2.2.2 of Chapter 2:

$R_{avg}=\frac{0.75}{\left[1-\frac{\beta }{{(1+\beta )}^2}\right]}Cwhere\beta =\frac{B}{CT}$ (35)

(35)

Even at $\beta =0.05$, equation 37 gives $R_{avg}=0.78C$. Because $\beta$ can be also interpreted as $\beta$=(Persistent sojourn time)/T, it follows that the above choice can also be interpreted as: The persistent sojourn time threshold should be set to 5% of the round trip latency, and this is what Nichols and Jacobsen recommend. The sojourn time is measured by time stamping every packet that arrives into the queue and then noting the time when it leaves the queue.

When the minimum sojourn time exceeds the target value for at least one round trip interval, a packet is dropped from the tail of the queue. The next dropping interval is decreased in inverse proportion to the square root to the number of drops since the dropping state was entered. As per the analysis in Chapter 2, this leads to a gradual linear decrease in the TCP throughput, as can be seen as follows: Let N(n) and T(n) be the number of packets transmitted in n^th drop interval and the duration of the n^th drop interval, respectively. Then the TCP throughput R(n) during the n^th drop interval is given by

$R(n)=\frac{N(n)}{T(n)}\mathrm{n}=1,2,\dots$ (36)

(36)

Note that $T(n)=\frac{T(1)}{\sqrt{n}}$, while N(n) is given by the formula (see Section 2.3, Chapter 2)

$N(n)=\frac{3}{8}{W}_m^2(n)$ (37)

(37)

where W_m(n) is the maximum window size achieved during the n^th drop interval. Because the increase in window size during each drop interval is proportional to the size of the interval, it follows that $W_m(n)\propto \frac{1}{\sqrt{n}}$, from which it follows from equation 37 that $N(n)\propto \frac{1}{n}$. Plugging these into equation 36, we finally obtain that $R(n)\propto \frac{1}{\sqrt{n}}$.

The throughput decreases with n until the minimum sojourn time falls below the threshold at which time the controller leaves the dropping state. In addition, no drops are carried out if the queue contains less than one packet worth of bytes.

One way of understanding the way CoDel works is with the help of a performance measure called Power, defined by

$Power=\frac{Throughput}{Delay}=\frac{R_{av}}{T_s}$

Algorithms such as Reno and CUBIC try to maximize the throughput without paying any attention to the delay component. As a result, we see that in variable capacity links, the delay blows up because of the large queues that result. AQM algorithms such as RED (and its variants such as ARED) and CoDel, on the other hand, can be used to maximize the Power instead by trading off some of the throughput for a lower delay. On an LTE link, simulations have shown that Reno achieves almost two times the throughput when CoDel is not used; hence, the tradeoff is quite evident here. The reasons for the lower throughputs with CoDel are the following:

• As shown using equation 35, even without a variable link capacity, the delay threshold in CoDel is chosen such that the resulting average throughput is about 78% of the link capacity.

• In a variable capacity link, when the capacity increases, it is better to have a large backlog (i.e., bufferbloat) because the system can keep the link fully utilized. With a scheme such as CoDel, on the other hand, the buffer soon empties in this scenario, and as a result, some of the throughput is lost.

Hence, CoDel is most effective when the application needs both high throughput as well as low latency (e.g., video conferencing) or when lower speed interactive applications such as web surfing are mixed with bulk file transfers in the same buffer. In the latter case, CoDel considerably improves the latency of the interactive application at the cost of a decrease in the throughput of the bulk transfer application. If Fair Queuing is combined with CoDel, so that each application is given its own buffer, then this mixing of traffic does not happen, in which CoDel can solely be used to improve the performance of applications of the video conferencing type.

The analysis presented above also points to the fact that the most appropriate buffer management scheme to use is a function of the application. This idea is explored more fully in Chapter 9.

4.6.2 End-to-End Approaches Against Bufferbloat

AQM techniques against bufferbloat can be deployed only if the designer has access to the wireless base station whose buffer management policy is amenable to being changed. If this is not the case, then one can use congestion control schemes that work on an end-to-end basis but are also capable of controlling delay along their path. If it is not feasible to change the congestion algorithm in the remote-end server, then the split-TCP architecture from Section 4.3 can be used (see Figure 4.2). In this case, the new algorithm can be deployed on the gateway (or some other box along the path) while the legacy TCP stack continues to run from the server to the gateway.

In this section, we will describe a congestion control algorithms called Low Extra Delay Background Transport (LEDBAT) that is able to regulate the connections’ end-to-end latency to some target value. We have already come across another algorithm that belongs to this category (i.e., TCP Vegas; see Chapter 1).

In general, protocols that use queuing delay (or queue size) as their congestion indicator, have an intrinsic disadvantage when competing with protocols such as Reno that use packet drops as the congestion indicator. The former tends to back off as soon as the queues start to build up, allowing the latter to occupy the all the bandwidth. However, if the system is designed in the split-connection approach, then the operator has the option of excluding the Reno-type algorithm entirely from the wireless subnetwork, so the unfairness issue will not arise in practice.

4.6.2.1 TCP LEDBAT

LEDBAT has been Bit Torrent’s default transport protocol since 2010 [24] and as a result now accounts for a significant share of the total traffic on the Internet. LEDBAT belongs to the class of Less than Best Effort (LBE) protocols, which are designed for transporting background data. The design objective of these protocols is to grab as much of the unused bandwidth on a link as possible, and if the link starts to get congested, then quickly back off.

Even though LEDBAT was designed to be a LBE protocol, its properties make it suitable to be used in wireless networks suffering from bufferbloat. This is because LEDBAT constantly monitors its one-way link latency, and if it exceeds a configurable threshold, then it backs off its congestion window. As a result, if the wireless link capacity suddenly decreases, then LEDBAT will quickly detect the resulting increase in latency caused by the backlog that is created and decrease its sending rate. Note that if the split-TCP design is used, then only LEDBAT flow will be present at the base station (and furthermore, they will be isolated from each other), so that LEDBAT’s reduction in rate in the presence of regular TCP will never be invoked.

LEDBAT requires that that each packet carry a timestamp from the sender, which the receiver uses to compute the one-way delay from the sender, and sends this computed value back to the sender in the ACK packet. The use of the one-way delay avoids the complications that arise in other delay-based protocols such as TCP Vegas that use the round trip latency as the congestion signal, and as a result delays experienced by ACK packets in the reverse link introduce errors in the forward delay estimates.

Define the following:

$\theta (t)$: Measured one-way delay between the sender and receiver

$\tau$: The maximum queuing delay that LEDBAT may itself introduce into the network, which is set to 100 ms or less

T: Minimum measured one-way downlink delay

$\gamma$: The gain value for the algorithm, which is set to one or less.

The window increase–decrease rules for LEDBAT are as follows (per RTT):

$W\leftarrow W+\gamma \left[1-\frac{\theta (t)-T}{\tau }\right]$ (38)

(38)

if no loss and

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

(39)

on packet loss.

LEDBAT tries to maintain a fixed packet delay of $\tau$ seconds at the bottleneck. If the current queuing delay given by $\theta (t)-T$, exceeds the target $\tau$, then the window is reduced in proportion to their ratio. When the measured queuing delay less that the target $\tau$, then LEDBAT increases its window, but the amount of increase per RTT can never exceed 1.

There are some interesting contrasts between LEDBAT and Westwood even though their designs are similar:

• Whereas Westwood uses a smoothed estimate of the round trip latency to measure congestion, LEDBAT uses the latest unfiltered 1-way latency.

• LEDBAT is less aggressive in its window increase rule because Westwood follows Reno in increasing its window by 1 every RTT, but LEDBAT uses a window increase that is less than 1.

• The rule that LEDBAT uses to decrease its window size in congestion is similar to the one that Westwood uses on encountering a packet loss, as seen below:

$\mathrm{LEDBAT}:\mathrm{\Delta }W=\gamma \left[\frac{\theta -T}{\tau }-1\right]$

$\text{Westwood}:\mathrm{\Delta }W=W\left(\frac{T_s-T}{T_s}\right)$

Hence, in both cases, the decrease is proportional to the amount of congestion delay, but in LEDBAT, the decrease is additive, but in Westwood, it is multiplicative.

Note that even though two different clocks are used to measure the one-way delays in LEDBAT because only the difference $\theta (t)-T$ appears in equation 38, any errors attributable to a lack of synchronization get cancelled out.

LEDBAT has been shown to have intraprotocol fairness issue if multiple LEDBAT connections are competing for bandwidth at a single node. If the bottleneck is at the wireless base station, then interaction between LEDBAT flows from different mobiles should not be an issue, since the per mobile queues are segregated from each other.