2.2.1 Throughput as a Function of Window Size

Consider the model shown in Figure 2.1, with a single TCP Reno controlled traffic source passing through a single bottleneck node. Even though this is a very simplified picture of an actual network, Low and Varaiya [8] have shown that there is no loss of generality in replacing all the nodes along the path by a single bottleneck node. Define the following:

Note that T, which is the fixed part of the round trip latency for a connection, is given by

$T=T_d+T_u+\frac{1}{C}$

We first consider the simplest case when the window size is in equilibrium with size W_max, there is sufficient buffering at the bottleneck node, so no packets get dropped because of overflows, and the link is error free. These assumptions are relaxed in the following sections as the sophistication of the model increases.

Consider the case when T>W_max/C, or W_max/T<C (Figure 2.2). The diagram illustrates the fact that in this case the sender transmits the entire window full of packets before it receives the ACK for first packet back. Hence, the average connection throughput R_avg is limited by the window size and is given by

$R_{avg}=\frac{W_{\max }}{T}\mathrm{when}{\mathrm{W}}_{\max }<\mathrm{CT}$ (1)

(1)

Because the rate at which the bottleneck node is transmitting packets is greater than or equal to the rate at which the source is sending packets into the network, the bottleneck node queue size is zero. Hence, at any instant in time, all the packets are in one of two places: either in the process of being transmitted in the downstream direction (= R_avg.T_d packets), or their ACKs are in the process of being transmitted in the upstream direction (= R_avg.T_u ACKs).

In Figure 2.3, we consider the case when T<W_max/C, i.e., W_max/T>C. As the figure illustrates, the ACKs for the first packet in the window arrive at the sender before it has finished transmitting the last packet in that window. As a result, unlike in Figure 2.2, the sender is continuously transmitting. The system throughput is no longer limited by the window size, and is able to attain the full value of the link capacity, that is,

$R_{avg}=C\mathrm{when}{\mathrm{W}}_{\max }>\mathrm{CT}$ (2)

(2)

Combining equations 1 and 2, we get

$R_{avg}=\min \left(\frac{W_{\max }}{T},C\right)$ (3)

(3)

In this case, C.T_d packets are the process of being transmitted in the downstream direction, and C.T_u ACKs are in the process of being transmitted in the upstream direction, for a total of C.(T_d+T_u)=CT packets and ACKs. Because CT<W_max, this leaves (W_max−CT) packets from the TCP window unaccounted for, and indeed they are to be found queued up in the bottleneck node! Hence, in equilibrium, the maximum buffer occupancy at the bottleneck node is given by

$b_{\max }=\max (W_{\max }-CT,0)$ (4)

(4)

Using equations 3 and 4, R_avg can also be written as

$R_{avg}=\frac{W_{\max }}{T+\frac{b_{\max }}{C}}$ (5)

(5)

This shows that the average throughput is given by the window size divided by the total round trip latency, including the queuing delay.

This discussion illustrates the rule of thumb that the optimum maximum window size is given by W_max=CT, i.e., it should equal the delay-bandwidth product for the connection because at this point the connection achieves its full bandwidth (equal to the link rate). Any increase in W_max beyond CT increases the length of the bottleneck queue and hence end-to-end delay, without doing anything to increase the throughput.

Figure 2.4 plots R_avg vs W_max based on equation 3, and as the graph shows, there a knee at W_max=CT, which is the ideal operating point for the system.

Figure 2.5 plots the maximum buffer occupancy b_max as a function of W_max based on equation 4. When W_max increases to B+CT, then b_max=B, and any increase of W_max beyond this value will cause the buffer to overflow. Note that until this point, we have made no assumptions about the specific rules used to control the window size. Hence, all the formulae in this section apply to any window-based congestion control scheme in the absence of packet drops.

In Section 2.2.2, we continue the analysis for TCP Reno for the case W_max>B+CT, when packets get dropped because of buffer overflows.

2.2.2 Throughput as a Function of Buffer Size

In Section 2.2.1, we found out that if W_max>B+CT, then it results in packet drops because of buffer overflows. In the presence of overflows, the variation of the window size W(t) as a function of time is shown in Figure 2.6 for TCP Reno. We made the following assumptions in coming up with this figure:

We now define two additional continuous time variables b(t) and T(t), where b(t) is the fluid approximation to the buffer occupancy process at time t, given by

$b(t)=W(t)-CT$

and T(t) is the total round trip latency at time t, given by

$T(t)=T+\frac{b(t)}{C}$

The throughput R(t) at time t is defined by

$R(t)=\frac{W(t)}{T(t)}$

and the average throughput is given by

$R_{avg}=\underset{t\to \mathrm{\infty }}{\lim }\frac{1}{t}\underset{0}{\overset{t}{\int }}R(t)dt$

As shown in Figure 2.7, W(t) increases up to a maximum value of W_f=(B+CT) and is accompanied by an increase in buffer size to B, at which point a packet is lost at the bottleneck node because of buffer overflow. TCP Reno then goes into the congestion recovery mode, during which it retransmits the missing packet and then reduces the window size to W_f/2. Using equation 2, if W_f/2 exceeds the delay-bandwidth product for the connection, then R_avg=C. Note that $\frac{W_f}{2}\ge CT$ implies that

$\frac{B+CT}{2}\ge CT$

which leads to the condition

$B\ge CT$ (6)

(6)

Hence, if the number of buffers exceeds the delay-bandwidth product of the connection, then the periodic packet loss caused by buffer overflows does not result in a reduction in TCP throughput, which stays at the link capacity C. Combining this with the condition for buffer overflow, we get

$W_{\max }-CT\ge B\ge CT$

as the conditions that cause a buffer overflow but do not result in a reduction in throughput. Equation 6 is a well-known rule of thumb that is used in sizing up buffers in routers and switches. Later in this chapter, we show that equation 6 is also a necessary condition for full link utilization in the presence of multiple connections passing through the link, provided the connections are all synchronized and have the same round trip latency.

When B<CT, then the reduction in window size to W_f/2 on packet loss leads to the situation where all the packets are either in transmission or being ACK’d, thus emptying the buffer periodically, as a result of which the system throughput falls below C (Figure 2.8). An analysis of this scenario is carried out next.

We compute the throughput by obtaining the duration and the number of packets transmitted during each cycle. The increase of the TCP window size happens in two phases, as shown in Figure 2.8:

In phase 1, W(t)<CT, which implies that the queue at the bottleneck node is empty during this phase. Hence, the rate at which ACKs are returning to the sender is equal to the TCP throughput R(t)=W(t)/T. This implies that the rate at which the window is increasing is given by

$\frac{dW(t)}{dt}=\frac{dW}{da}\cdot \frac{da}{dt}=\frac{1}{W(t)}\cdot \frac{W(t)}{T}=\frac{1}{T}$ (7)

(7)

where a(t) is the number of ACKs received in time t and da/dt is the rate at which ACKs are being received.

Hence,

$W(t)-\frac{W_f}{2}=\underset{0}{\overset{t}{\int }}\frac{dt}{T}=\frac{t}{T}$

This results in a linear increase in the window size during phase 1, as shown in Figure 2.6. This phase ends when W=W_f=CT, so if t_A is the duration of this phase, then

$CT-\frac{W_f}{2}=\frac{t_A}{T},$

so that

$t_A=T\left(CT-\frac{W_f}{2}\right).$ (8)

(8)

The number of packets n_A transmitted during phase 1 is given by

$\begin{array}{ll}{n}_A\hfill & ={\int }_0^{t_A}R(t)dt={\int }_0^{t_A}\frac{W(t)}{T}dt\hfill \\ \hfill & =\frac{1}{T}{\int }_0^{t_A}\left(\frac{W_f}{2}+\frac{t}{T}\right)dt\hfill \\ \hfill & =\frac{1}{T}\left(\frac{W_f\cdot t_A}{2}+\frac{t_A^2}{2T}\right)\hfill \end{array}$ (9)

(9)

In phase 2, W(t)>CT so that the bottleneck node has a persistent backlog. Hence, the rate at which ACKs are returning back to the sender is given by C. It follows that the rate of increase of the window is given by

$\frac{dW(t)}{dt}=\frac{dW(t)}{da}\cdot \frac{da}{dt}=\frac{C}{W(t)}$ (10)

(10)

Hence,

$\begin{array}{l}{\int }_{CT}^{W}W(t)\cdot dW={\int }_0^{t}C\cdot dt\hfill \\ W^2(t)-{(CT)}^2=2Ct\hfill \end{array}$

so that

$W(t)=\sqrt{2Ct+{(CT)}^2}$ (11)

(11)

Equation 11 implies that the increase in window size during phase 2 happens in a sublinear fashion, as illustrated in Figure 2.6. During this phase, the window increases until it reaches W_f, and by equation 11, the time required to do this, t_B, is given by

$t_B=\frac{W_f^2-{(CT)}^2}{2C}$ (12)

(12)

Because of the persistent backlog at the bottleneck node, the number of packets n_B transmitted during phase 2 is given by

$n_B=C{t}_B=\frac{W_f^2-{(CT)}^2}{2}$ (13)

(13)

The average TCP throughput is given by

$R_{avg}=\frac{n_A+n_B}{t_A+t_B}$ (14)

(14)

From equations 9 and 13, it follows that

$n_A+n_B=\frac{1}{T}\left(\frac{W_f\cdot t_A}{2}+\frac{t_A^2}{2T}\right)+\frac{W_f^2-{(CT)}^2}{2}$

Substituting for t_A from equation 8, and after some simplifications, we get

$n_A+n_B=\frac{3W_f^2}{8}$ (15)

(15)

Thus, the number of packets transmitted during a cycle is proportional to the square of the maximum window size, which is an interesting result in itself and is used several times in Part 2 of this book. Later in this chapter, we will see that this relation continues to hold even for the case when the packet losses are because of random link errors.

Similarly, from equations 8 and 12, we obtain

$t_A+t_B=T\left(CT-\frac{W_f}{2}\right)+\frac{W_f^2-{(CT)}^2}{2C}$

which after some simplifications becomes

$t_A+t_B=\frac{W_f^2+{(CT)}^2-CT{W}_f}{2C}$ (16)

(16)

Substituting equations 15 and 16 back into equation 14, we obtain

$R_{avg}=\frac{\frac{3}{4}{W}_f^{2}C}{W_f^2+{(CT)}^2-CT{W}_f}$ (17)

(17)

Note that W_f=B+CT, so that (17) simplifies to

$R_{avg}=\frac{0.75}{\left[1-\frac{B\cdot CT}{{(B+CT)}^2}\right]}C$ (18)

(18)

Define $\beta =\frac{B}{CT}\le 1$, so that

$R_{avg}=\frac{0.75}{\left[1-\frac{\beta }{{(1+\beta )}^2}\right]}C$ (19)

(19)

Define f

$f=\frac{0.75}{\left[1-\frac{\beta }{{(1+\beta )}^2}\right]}$ (20)

(20)

and note that

$\underset{\beta \to 0}{\lim }f=0.75\mathrm{and}\underset{\beta \to 1}{\lim }f=1$

As shown in Figure 2.9, f monotonically increases from 0.75 to 1 as $\beta$ increases from 0 to 1, so that $R_{avg}\le C$.

Equations 19 to 21 imply that in a network with a large delay bandwidth product (relative to the buffer size), a TCP Reno–controlled connection is not able to attain its full throughput C. Instead, the throughput maxes out at 0.75C because of the lack of buffering at the bottleneck node. If B exceeds CT, then the throughput converges to C as expected. However, the fact that the throughput is able to get up to 0.75C even for very small buffer sizes is interesting and has been recently used in the design of the CoDel AQM Scheme (see Chapter 4).

2.2.3 Throughput as a Function of Link Error Rate

In the presence of random link errors, TCP may no longer be able to attain the maximum window size of B+CT; instead, the window increases to some value that is now a random variable. This is clearly illustrated in Figure 2.10, with the maximum window and consequently the starting window varying randomly. To analyze this case, we have to resort to probabilistic reasoning and find the expected value of the throughput. In Section 2.2.3.1, we consider the case when the lost packets are recovered using the duplicate ACKs mechanism, and in Section 2.2.3.2, we consider the more complex case when packet losses result in timeouts.

To take the random losses into account, we need to introduce a second model in to the system, that of the packet loss process. The simplest case is when packet losses occur independently of one another with a loss probability p; this is the most common loss process used in the literature. Wireless links lead to losses that tend to bunch together because of a phenomenon known as fading. In Section 2.4, we analyze a system in which the packet loss intervals are correlated, which can be used to model such a system.

The type of analysis that is carried out in the next section is known as mean value analysis (MVA) in which we work with the expectations of the random variables. This allows us to obtain closed form expressions for the quantities of interest. There are three other alternative models that have been used to analyze this system:

2.2.3.1 Link Errors Recovered by Duplicate ACKs

The TCP model used in this section uses discrete states for the window size, as opposed to the fluid model used in Section 2.2.2 [5]. We define a cycle as the time between two loss events (Figure 2.11) and a subcycle as the time required to transmit a single window of packets followed by reception of their ACKs.

In addition to assumptions 1 and 2 from Section 2.2.2, we make the following additional assumptions:

4. All the packets in a window are transmitted back to back at the start of a subcycle, and no other packets are sent until the ACK for the first packet is received, which marks the end of the subcycle and the start of the next one.

5. The time needed to send all the packets in a window is smaller than the round trip time. This assumption is equivalent to stating that the round trip time T(t) is fixed at T(t)=T and equals the length of a subcycle. This is clearly an approximation because we observed in Section 2.2.2 that the T(t) increases linearly after the window size exceeds CT because of queuing at the bottleneck node.

Another consequence of this assumption is that the window increase process stays linear throughout, so we are approximating the sublinear increase for larger window sizes shown in Figure 2.6 (which is caused by the increase in T(t)), by a straight line.

6. Packet losses between cycles are independent, but within a cycle when a packet is lost, then all the remaining packets transmitted until the end of the cycle are also lost. This assumption can be justified on the basis of the back-to-back transmission assumption and the drop-tail behavior of the bottleneck queue.

Define the following:

W_i: TCP window size at the end of the i_th cycle

A_i: Duration of the ith cycle

X_i: Number of subcycles in the i_th cycle

Y_i: Number of packets transmitted in the i_th cycle

R_avg: Average TCP throughput

p: Probability that a packet is lost because of random link error given that it is either the first packet in its round or the preceding packet in its round is not lost.

As shown in Figure 2.11, cycles are indexed using the variable i, and in the i^th cycle, the initial TCP window is given by the random variable W_i-1/2, and the final value at the time of packet loss is given by W_i. Within the i^th cycle, the sender transmits up to X_i windows of packets, and the time required to transmit a single window of packets is constant and is equal to the duration of the (constant) round trip latency T, so that there are X_i subcycles in the i^th cycle. Within each subcycle, the window size increases by one packet as TCP goes through the congestion avoidance phase, so that by the end of the cycle, the window size increases by X_i packets.

We will assume that the system has reached a stationary state, so that the sequences of random variables {W_i}, {A_i}, {X_i} and {Y_i} converge in distribution to the random variables W, A, X and Y, respectively. We further define the expected values of these stationary random variables as E(W), E(A), E(X), and E(Y), so that:

E(W): Expected TCP window size at time of packet loss

E(Y): Expected number of packets transmitted during a single cycle

E(X): Expected number of subcycles within a cycle

E(A): Expected duration of a cycle

Our objective is to compute R_avg, the average throughput. From the theory of Markov regenerative processes, it follows that

$R_{avg}=\frac{E(Y)}{E(A)}$ (21)

(21)

We now proceed to compute E(Y), followed by E(A).

After a packet is lost, W_i–1 additional packets are transmitted before the cycle ends. We will ignore these packets, so that Y_i equals the number packets transmitted until the first drop occurs. Under this assumption, the computation of E(Y) is straightforward, given that the number of packets transmitted during a cycle is distributed according to the Bernoulli distribution, that is,

$P(Y_i=k)={(1-p)}^{k-1}p,\mathrm{k}=1,2,\dots$ (22)

(22)

Hence,

$E(Y)=\frac{1}{p}$ (23)

(23)

Next, note that E(A) is given by

$E(A)=E(X)\cdot T$ (24)

(24)

where T is the fixed round trip delay for the system. Furthermore, because

$W_i=\frac{W_{i-1}}{2}+X_i,\forall i$ (25)

(25)

it follows by taking expectations on both sides, that the average number of subcycles E(X) is given by

$E(X)=\frac{E(W)}{2}$ (26)

(26)

To compute E(W), note that in each subcycle, the TCP window size increases by 1; hence, if we ignore the packets transmitted in the last subcycle, we get

$\begin{array}{ll}{Y}_i\hfill & =\sum _{k=0}^{X_i-1}\left(\frac{W_{i-1}}{2}+k\right)\hfill \\ \hfill & =\frac{X_i}{2}{W}_{i-1}+\frac{(X_i-1)X_i}{2}\hfill \\ \hfill & =\frac{X_i}{2}\left(W_{i-1}+W_i-\frac{W_{i-1}}{2}-1\right)\hfill \\ \hfill & =\frac{X_i}{2}\left(W_i+\frac{W_{i-1}}{2}-1\right)\hfill \end{array}$ (27)

(27)

Assuming that {X_i} and {W_i} are mutually independent sequences of iid random variables and taking the expectation on both sides, we obtain

$E(Y)=\frac{E(X)}{2}\left(E(W)+\frac{E(W)}{2}-1\right)=\frac{E(X)}{2}\left(\frac{3E(W)}{2}-1\right)$ (28)

(28)

Substituting the value of E(X) from (27) and using the fact that E(Y)=1/p, we obtain

$\frac{3{(E(W))}^2}{8}-\frac{E(W)}{4}-\frac{1}{p}=0$ (29)

(29)

Solving this quadratic equation yields

$E(W)=\frac{1+\sqrt{1+\frac{24}{p}}}{3}\mathrm{packets}$ (30a)

(30a)

This is approximately equal to

$E(W)\approx \sqrt{\frac{8}{3p}}\text{packets},$ (30b)

(30b)

and from equation 26, we conclude

$E(X)\approx \sqrt{\frac{2}{3p}}$ (31)

(31)

Finally, it follows from equations 21, 23, 24, and 31 that

$R_{avg}\approx \frac{1/p}{T\sqrt{2/3p}}=\frac{1}{T}\sqrt{\frac{3}{2p}}\text{packets}/\text{sec}$ (32)

(32)

Equation 32 is the well-known “square root” law for the expected throughput of a TCP connection in the presence of random link errors that was first derived by Mathis and colleagues [7]. Our derivation is a simplified version of the proof given by Padhye et al. [5]

2.2.3.2 Link Errors Recovered by Duplicate ACKs and Timeouts

In this section, we derive an expression for the average TCP throughput in the presence of duplicate ACK as well as timeouts. As in the previous section, we present a simplified version of the analysis in the paper by Padhye and colleagues [5].

As illustrated in Figure 2.12, we now consider a supercycle that consists of a random number of cycles (recall that cycles terminate with a duplicate ACK–based packet recovery) and a single timeout interval.

Define the following random variables:

${\mathrm{Z}}_{\mathrm{i}}^{\mathrm{DA}}$: Time duration during which missing packets are recovered using duplicate ACK triggered retransmissions in the i^th supercycle. This interval is made of several cycles, as defined in the previous section.

n_i: Number of cycles within a single interval of length ${\mathrm{Z}}_{\mathrm{i}}^{\mathrm{DA}}$ in the i^th supercycle

Y_ij: Number of packets sent in the j^th cycle of the i^th supercycle

X_ij: Number of subcycles in the j^th cycle of the i^th supercycle

A_ij: Duration of the j^th cycle of the i^th supercycle

${\mathrm{Z}}_{\mathrm{i}}^{\mathrm{TO}}$: Time duration during which a missing packet is recovered using TCP timeouts

M_i: Number of packets transmitted in the i_th supercycle

P_i: Number of packets transmitted during the timeout interval ${\mathrm{Z}}_{\mathrm{i}}^{\mathrm{TO}}$

S_i: Time duration of a complete supercycle, such that

${\mathrm{S}}_{\mathrm{i}}={\mathrm{Z}}_{\mathrm{i}}^{\mathrm{DA}}+{\mathrm{Z}}_{\mathrm{i}}^{\mathrm{TO}}$ (33)

(33)

As in the previous section, we assume that the system is operating in a steady state in which all the random variables defined above have converged in distribution. We will denote the expected value of these random variables with respect to their limit distribution by appending an E before the variable name as before.

Note that the average value of the system throughput R_avg, is given by

$R_{avg}=\frac{E(M)}{E(S)}$ (34)

(34)

We now proceed to compute the expected values E(M) and E(S). By their definitions, we have

$M_i=\sum _{j=1}^{n_i}{Y}_{ij}+P_i$ (35)

(35)

$S_i=\sum _{j=1}^{n_i}{A}_{ij}+Z_i^{TO}$ (36)

(36)

Assuming that the sequence {n_i} is iid and independent of the sequences {Y_ij} and {A_ij}, it follows that

$E(M)=E(n)\cdot E(Y)+E(P)$ (37)

(37)

$E(S)=E(n)\cdot E(A)+E(Z^{TO})$ (38)

(38)

so that the average throughput is given by

$R_{avg}=\frac{E(Y)+E(P)/E(n)}{E(A)+E(Z^{TO})/E(n)}$ (39)

(39)

Let Q be the probability that the packet loss that ends a cycle results in a timeout, that is, the lost packet cannot be recovered using duplicate ACKs. Then

$\mathrm{Pr}(n=k)={(1-Q)}^{k-1}Q,k=1,2,\dots$

so that

$E(n)=\frac{1}{Q}$ (40)

(40)

which results in the following expression for R_avg

$R_{avg}=\frac{E(Y)+QE(P)}{E(A)+QE(Z^{TO})}$ (41)

(41)

We derived expressions for E(Y) and E(A) in the last section, namely

$E(Y)=\frac{1}{p}\mathrm{and}$ (42)

(42)

$E(A)=T\sqrt{\frac{2}{3p}}$ (43)

(43)

and we now obtain formulae for E(P), E(Z^TO) and Q.

1. E(P)
The same packet is transmitted one or more times during the timeout interval Z^TO. Hence a sequence of k TOs occurs when there are (k−1) consecutive losses followed by a successful transmission. Hence,

$\mathrm{Pr}(P=k)=p^{k-1}(1-p),\mathrm{k}=1,2,\dots$

from which it follows that

$E(P)=\frac{1}{1-p}.$ (44)

(44)

2. E(Z^TO)
Note that the time duration for Z^TO with k timeouts are given by

$Z^{TO}(k)=\{\begin{array}{c}(2^k-1)T_0,fork\le 6\\ [63+64(k-6)]T_0,fork\ge 7\end{array}$ (45)

(45)

This formula follows from the fact that the value of the timeout is doubled for the first six timer expiries and then kept fixed at 64T₀ for further expirations. It follows that

$\begin{array}{ll}E(Z^{TO})\hfill & =\sum _{k=1}^{\infty }{Z}^{TO}(k)\cdot \mathrm{Pr}(P=k)\hfill \\ \hfill & =T_0\frac{1+p+2p^2+4p^3+8p^4+16p^5+32p^6}{1-p}\hfill \end{array}$ (46)

(46)

Define f(p) as

$f(p)=1+p+2p^2+4p^3+8p^4+16p^5+32p^6$ (47)

(47)

so that

$E(Z^{TO})=T_0\frac{f(p)}{1-p}$ (48)

(48)

3. Q
Q is approximated by the formula (see Appendix 2.A for details)

$Q=\min \left(1,\frac{3}{E(W)}\right)=\min \left(1,3\sqrt{\frac{3p}{8}}\right)$ (49)

(49)

From equations 41 to 44, 48, and 49, it follows that

$R_{avg}=\frac{\frac{1}{p}+\frac{1}{1-p}\min \left(1,3\sqrt{\frac{3p}{8}}\right)}{T\sqrt{\frac{2}{3p}+\frac{T_{0}f(p)}{1-p}\min \left(1,3\sqrt{\frac{3p}{8}}\right)}}$ (50)

(50)

which after some simplification results in

$R_{avg}=\frac{1-p+p\min \left(1,3\sqrt{\frac{3p}{8}}\right)}{T(1-p)\sqrt{\frac{2}{3p}+T_{0}pf(p)\min \left(1,3\sqrt{\frac{3p}{8}}\right)}}$ (51)

(51)

For smaller values of p, this can be approximated as

$R_{avg}=\frac{1}{T\sqrt{\frac{2}{3p}+T_{0}p(1+32p^2)\min \left(1,3\sqrt{\frac{3p}{8}}\right)}}$ (52)

(52)

This formula was empirically validated by Padhye et al. [5] and was found to give very good agreement with observed values for links in which a significant portion of the packet losses are attributable to timeouts.

A General Procedure for Computing the Average Throughput

Basing on the deterministic approximation, we provide a procedure for computing the average throughput for a congestion control algorithm with window increase function given by W(t) and maximum window size W_m. This procedure is used in the next section as well as several times in Part 2 of this book:

1. Compute the number of packets Y transmitted per cycle by the formula

$Y_{\alpha }(W_m)=\frac{1}{T}{\int }_0^{T}W(t,\alpha )dt$

In this equation, T is the round trip latency, and $\alpha$ represents other parameters that govern the window size evolution.

2. Equate the packet drop rate p to Y, using the formula

$Y_{\alpha }(W_m)=\frac{1}{p}$

If this equation can be inverted, then it leads to a formula for W_m as a function of p, that is,

$W_m=Y_{\alpha }^{-1}\left(\frac{1}{p}\right)$

3. Compute the cycle duration $\tau (W_m)$ for a cycle as a function of the maximum window size.

4. The average throughput is then given by

$R_{avg}=\frac{1/p}{\tau (W_m)}=\frac{1/p}{\tau (Y_{\alpha }^{-1}(\frac{1}{p}))}$

The formula for the window increase function $W(t,\alpha )$ can usually be derived from the window increase-decrease rules. Note that there are algorithms in which the inversion in step 2 is not feasible, in which case we will have to resort to approximations. There are several examples of this in Chapter 5.

2.3.1 Throughput for General Additive Increase/Multiplicative Decrease (AIMD) Congestion Control

Recall that the window increase–decrease rules for TCP Reno can be written as:

$W\leftarrow \{\begin{array}{llllll}W+1\hfill & per\hfill & RTT\hfill & on\hfill & ACK\hfill & receipt\hfill \\ \frac{W}{2}\hfill & \hfill & \hfill & on\hfill & packet\hfill & loss\hfill \end{array}$ (65)

(65)

This rule can be generalized so that the window size increases by a packets per RTT in the absence of loss, and it is reduced by a fraction bW on loss. This results in the following rules:

$W\leftarrow \{\begin{array}{llllll}W+a\hfill & per\hfill & RTT\hfill & on\hfill & ACK\hfill & receipt\hfill \\ (1-b)W\hfill & \hfill & \hfill & on\hfill & packet\hfill & loss\hfill \end{array}$ (66)

(66)

This is referred to as an AIMD congestion control [11], and has proven to be very useful in exploring new algorithms; indeed, most of the algorithms in this book fall within this framework. In general, some of the most effective algorithms combine AIMD with increase decrease parameters (a,b) that are allowed to vary as a function of either the congestion feedback or the window size itself. Here are some examples from later chapters:

Using the deterministic approximation technique from the previous section, we derive an expression for the throughput of AIMD congestion control.

With reference to Figure 2.14, the TCP window size reduces from W_m to (1-b)W_m on packet loss (i.e., a reduction of bW_m packets). On each round trip, the window size increases by a packets, so that it takes bW_m/a round trips for the window to get back to W_m. This implies that the length of a cycle is given by

$\tau =T{W}_m\frac{b}{a}\mathrm{seconds}.$

The average number of packets transmitted over a single cycle is then given by:

$\begin{array}{ll}Y\hfill & =\underset{0}{\overset{T{W}_{m}b/a}{\int }}\frac{W(t)}{T}dt\hfill \\ \hfill & =\frac{1}{T}\left[T\frac{W_{m}b}{a}(1-b)W_m+\frac{T}{2}\frac{W_m}{2}\frac{b}{a}{W}_m\right]\hfill \\ \hfill & =\left(\frac{2b-b^2}{2a}\right)W_m^2\hfill \end{array}$ (67)

(67)

By step 2 of the deterministic approximation procedure, equating Y to 1/p leads to

$\frac{1}{p}=\left(\frac{2b-b^2}{2a}\right)W_m^2$

so that

$W_m=\sqrt{\frac{2a}{(2b-b^2)}\frac{1}{p}}$ (68)

(68)

The average response time R_avg is then given by

$R_{avg}=\frac{1/p}{T{W}_{m}b/a}=\frac{1}{T}\sqrt{\frac{a(2-b)}{2bp}}$ (69)

(69)

Comparing equation 69 with the equivalent formula for TCP Reno (equation 57), it follows that an AIMD congestion control algorithm with parameters (a,b) has the same average throughput performance as TCP Reno if the following equation is satisfied:

$a=\frac{3b}{2-b}.$ (70)

(70)

In Chapter 3, we generalize the notion of AIMD congestion control by introducing nonlinearities in the window increase–decrease rules, which is called generalized AIMD or GAIMD congestion control. Note that equation 69 holds only for the case when the parameters a and b are constants. If either of them is a function of the congestion feedback or the current window size, it leads to a nonlinear evolution of the window size for which this analysis does not hold.

2.3.2 Differentiating Buffer Overflows from Link Errors

The theory developed in Sections 2.2 and 2.3 can be used to derive a useful criterion to ascertain whether the packet drops on a TCP connection are being caused because of buffer overflows or because of link errors.

When buffer overflows are solely responsible for packet drops, then N packets are transmitted per window cycle, where N is given by equation 15

$N=\frac{3W_f^2}{8}.$

Because one packet is dropped per cycle, it follows that packet drop rate is given by

$p=\frac{1}{N}=\frac{8}{3W_f^2}.$ (71)

(71)

Because $W_f\approx CT$ (ignoring the contribution of the buffer size to W_f), it follows that

$p{(CT)}^2\approx \frac{8}{3}$ (72)

(72)

when buffer overflows account for most packet drops.

On the other hand, when link errors are the predominant cause of packet drops, then the maximum window size W_m achieved during a cycle may be much smaller than W_f. It follows that with high link error rate,

$W_m^2\ll W_f^2$

so that by equation 53,

$p=\frac{1}{E(Y)}=\frac{8}{3E(W_m^2)}\gg \frac{8}{3W_f^2}.$

It follows that if

$p{(CT)}^2\gg \frac{8}{3}$ (73)

(73)

then link errors are the predominant cause of packet drops. This criterion was first proposed by Lakshman and Madhow [4] and serves as a useful test for the prevalence of link errors on a connection with known values for p, C, and T.

2.6.1 Homogeneous Case

We will initially consider the homogeneous case in which the propagation+transmission delays for all the sessions are equal (i.e., T=T_i=T_j, i, j=1, 2,…,K).

The basic assumption that is used to simplify the analysis of this model is that of session synchronization. This means that the window size variations for all the K sessions happen together (i.e., their cycles start and end at the same time). This assumption is justified from observations made by Shenker et al. [3] in which they observed that tail drop causes the packet loss to get synchronized across all sessions. This is because packets get dropped because of buffer overflow at the bottleneck node; hence, because typically multiple sessions encounter the buffer overflow condition at the same time, their window size evolution tends to get synchronized. This also results in a bursty packet loss pattern in which up to K packets are dropped when the buffer reaches capacity. This implies that

$\frac{d{W}_i(t)}{dt}=\frac{d{W}_j(t)}{dt}\forall i,j$ (82)

(82)

because the rate at which a window increases is determined by the (equal) round trp latencies. From the definition of W(t) and equations 7 and 82, it follows that

$\frac{dW(t)}{dt}=\frac{K}{T}\mathrm{when}W(t)\le CT$ (83)

(83)

From equations 10 and 82, we obtain

$\frac{dW(t)}{dt}=\frac{KC}{W(t)}\mathrm{when}W(t)>\mathrm{CT}$ (84)

(84)

Note that

$R_i(t)=\frac{R(t)}{K}\mathrm{i}=1,2,\dots ,\mathrm{K}$ (85)

(85)

so that it is sufficient to find an expression for total throughput R(t).

As in Section 2.2.2, the time evolution of the total window W(t) shows the characteristic sawtooth pattern, with the sum of the window sizes W(t) increasing until it reaches the value W_f=B+CT. This results in synchronized packet losses at all the K connections and causes W(t) to decrease by half to W_f/2. When this happens, there are two cases:

1. W_f/2>CT (i.e., B>CT)
This condition holds for a network with a small delay-bandwidth product. In this case, the bottleneck queue is always occupied, hence

$R(t)=C\text{and}{R}_i(t)=\frac{C}{K}\mathrm{i}=1,2,\dots ,\mathrm{K}$ (86)

(86)

2. W_f/2<CT (i.e., B<CT)
This condition holds for a network with a large delay-bandwidth product. In this case, there are two phases with W(t)<CT in phase 1 and W(t)>CT in phase 2. The calculations are exactly the same as in Section 2.2.2, and they lead to the following formula for the average total throughput R^avg

$R^{avg}=\frac{0.75}{\left[1-\frac{\beta }{{(1+\beta )}^2}\right]}C,\mathrm{where}\beta =\frac{B}{CT}$ (87)

(87)

which leads to

$R_i^{avg}=\frac{0.75}{\left[1-\frac{\beta }{{(1+\beta )}^2}\right]}\frac{C}{K}\mathrm{i}=1,2,\dots ,\mathrm{K}$ (88)

(88)

Note that the total throughput R^avg is independent of the number of connections K. Equation 87 also implies that as a result of the lack of buffers in the system and the synchronization of the TCP sessions, the link does not get fully used even with a large number of sessions. Case 1 also leads to the interesting result that for the fully synchronized case, the amount of buffering required to keep the link continuously occupied is given by CT and is independent of the number of connections passing through the link.

2.6.2 Heterogeneous Case

In this case, the session propagation delays T_i, i=1,2,…,K may be different.

Recall that the throughput R_i(t) for session i is defined by the formula

$R_i(t)=\frac{W_i(t)}{T_i+\frac{b(t)}{C}}\mathrm{i}=1,2,\dots ,\mathrm{K}$ (89)

(89)

Hence, for the case when the bottleneck link is fully used, we have

$\sum _{i=1}^K{R}_i(t)=C,$

so that

$\sum _{i=1}^K\frac{W_i(t)}{b(t)+C{T}_i}=1$ (90)

(90)

The following equation follows by reasoning similar to that used to derive equation 7.

$\frac{d{W}_i(t)}{dt}=\frac{1}{T_i+\frac{b(t)}{C}}\mathrm{i}=1,2,\dots ,\mathrm{K}$ (91)

(91)

Following the analysis in Section 2.2.2, the average throughput for the i^th session is given by

$R_i^{avg}=\frac{\frac{3}{8}{(W_i^f)}^2}{t_i^A+t_i^B}\mathrm{i}=1,2,\dots ,\mathrm{K}$ (92)

(92)

where, as before, ${\mathrm{t}}_{\mathrm{i}}^{\mathrm{A}}$ is the average time interval after a packet loss when the buffer is empty, and ${\mathrm{t}}_{\mathrm{i}}^{\mathrm{B}}$ is the average time interval required for the buffer to fill up.

In general, it is difficult to find closed form solutions for W_i(t) and an expression for $W_i^f$ from these equations, even if synchronization among sessions is assumed. Hence, following Bonald [14], we do an asymptotic analysis, which provides some good insights into the problem.

1. The case of large buffers
Define ${\beta }_i=\frac{B}{C{T}_i}$, i=1,2,…,K and assume that ${\beta }_i$ is very large, that is, the delay bandwidth product for all sessions is negligible compared with the number of buffers in the bottleneck node. This means that the bottleneck buffer is continuously occupied, so that ${\mathrm{t}}_{\mathrm{i}}^{\mathrm{A}}=0$. Using equation 91, this leads to

$\frac{d{W}_i(t)}{dt}\approx \frac{C}{b(t)},\mathrm{i}=1,2,\dots ,\mathrm{K}$ (93)

(93)

Equation 93 implies that all the K windows increase at the same rate; hence, the maximum window sizes are also approximately equal, so that $W_i^f\approx W_j^f$, and $t_i^B\approx t_j^B$ for all i,j. From equation 92, it then follows that

$R_i^{avg}\approx R_j^{avg}\mathrm{i},\mathrm{j}=1,2,\dots ,\mathrm{K}$ (94)

(94)

Hence, when the number of buffers in the bottleneck node is large, each connection gets a fair share of the capacity despite any differences in propagation delays.

2. The case of large delay-bandwidth product
We assume that ${\beta }_i$, i=1,2,…,K is very small, that is, the delay-bandwidth product for each session is very large compared with the number of buffers in the bottleneck node. We also make the assumption that the K connections are synchronized, so that they drop their packets at the bottleneck node at the same time.

From equation 91, it follows that

$\frac{d{W}_i(t)}{dt}\approx \frac{1}{T_i}$

so that

$\frac{W_i(t)}{W_j(t)}\approx \frac{T_j}{T_i}\mathrm{i},\mathrm{j}=1,2,\dots ,\mathrm{K}$ (95)

(95)

and from equations 63 and 69, it follows that

$\frac{R_i(t)}{R_j(t)}\approx \frac{W_i/T_i}{W_j/T_j}\approx {\left(\frac{T_j}{T_i}\right)}^2\mathrm{i},\mathrm{j}=1,2,\dots ,\mathrm{K}$ (96)

(96)

Hence, for large delay-bandwidth products, TCP Reno with tail drop has a very significant bias against connections with larger propagation delays. At first glance, it may seem that equation 96 contradicts the formula for the average throughput (60) because the latter shows only an inverse relationship with the round trip latency T. However, note that by making the assumption that the K sessions are synchronized, their packet drop probabilities p become a function of T as well, as shown next. We have

$\frac{R_{avg}^i}{R_{avg}^j}=\frac{T_j}{T_i}\sqrt{\frac{p_j}{p_i}}\mathrm{and\; furthermore}$ (97)

(97)

$p_i\approx \frac{1}{E(W_i)(t/T_i)}$ (98)

(98)

where t is common cycle time for all the K connections and E(W_i)t/T_i is expected number of packets transmitted per cycle. Substituting $E(W_i)=\sqrt{\frac{8}{3p}}$ from equation 30b, it follows that $p_i=\frac{3}{8}{(\frac{T_i}{t})}^2$. Substituting this expression into equation 97, we obtain

$\frac{R_{avg}^i}{R_{avg}^j}={\left(\frac{T_j}{T_i}\right)}^2.$ (99)

(99)

Using heuristic agreements, equation 99 can be extended to the case when the average throughput is given by the formula:

$R_{avg}=\frac{h}{T^e{p}^d}$ (100)

(100)

where h, e, and d are constants. Equations such as equation 100 for the average throughput arise commonly when we analyze congestion control algorithms in which the window increase is no longer linear (see Chapter 5 for several examples of this). For example, for TCP CUBIC, e=0.25, and d=0.75.

It can be shown that the throughput ratio between synchronized connections with differing round trip latencies is given by

$\frac{R_{avg}^i}{R_{avg}^j}={\left(\frac{T_j}{T_i}\right)}^{\frac{e}{1-d}}$ (101)

(101)

To prove equation 101, we start with equation 100 so that

$\frac{R_{avg}^i}{R_{avg}^j}={\left(\frac{T_j}{T_i}\right)}^e{\left(\frac{p_j}{p_i}\right)}^d$ (102)

(102)

Because the probability of a packet loss is the inverse of the number of packets transmitted during a cycle and t/T_i is the number of round trips in t seconds, it follows that

$p_i=\frac{1}{E(W_i)(t/T_i)}=\frac{T_i^e{p}^d}{th}$ (103)

(103)

where we have used the formula

$E(W)=R_{avg}T=\frac{h}{T^{e-1}{p}^d}$

From equation 103, it follows that

$p_i={\left(\frac{T_i^e}{th\prime }\right)}^{1/1-d}$ (104)

(104)

Substituting equation 104 into equation 102 leads to equation 101. This equation was earlier derived by Xu et al. [15] for the special case when e=1. It has proven to be very useful in analyzing the intraprotocol fairness properties of congestion protocols, as shown in Chapter 5.

Equation 101 is critically dependent on the assumption that the packet drops are synchronized among all connections, which is true for tail-drop queues. A buffer management policy that breaks this synchronization leads to a fairer sharing of capacity among connections with unequal latencies. One of the objectives of RED buffer management was to break the synchronization in packet drops by randomizing individual packet drop decisions. Simulations have shown that RED indeed achieves this objective, and as a result, the ratio of the throughputs of TCP connections using RED varies as the first power of their round trip latencies rather than the square.