A Comprehensive Stochastic Model for TCP

Latency and Throughput

Dong Zheng, Georgios Y. Lazarou, Rose Hu, and Junshan Zhang

Abstract— Understanding the nature of TCP behavior is critical in order to properly engineer, operate, and evaluate the performance of the Internet, as well as to properly design and implement future networks. In this paper, we first develop a better and tractable model for the congestion window growth pattern in the slow-start phase. Using this new slow-start phase model, we construct an accurate model for the short-lived TCP flows and then an extended and more accurate TCP steadystate model. We validate our models with simulations and compare them against existing models. The results show that our model for the short-lived flows yields more accurate performance predictions (up to 20%) than the ones developed in [1] and [2]. In addition, our extended steady-state model is up to 75% more accurate than the model proposed in [3].

Index Terms— TCP, performance evaluation, stochastic model

I. Introduction

A multitude of Internet applications, such as the world wide web, usenet news, file transfer and remote login, have opted TCP as the transport mechanism. Thus, TCP greatly influences the performance of Internet [4], [5], and a well-designed TCP is of utmost importance to the level of satisfaction of Internet users. Several stochastic TCP models have been proposed [1]- [3], [6] for predicting its performance in terms of latency and throughput. Considerable emphasis has been given into better understanding of the dynamics of TCP and its sensitivity to network parameters, such as the TCP round trip time and the

Parts of this paper were presented at ICC’03, \begin{matrix}c \\ ◯ \end{matrix}IEEE 2003, and CIIT’03,

\begin{matrix}c \\ ◯ \end{matrix}IASTED 2003

Dong Zheng and Junshan Zhang are with the Department of Electrical Engineering, Fulton School of Engineering, Arizona State University ({dong.zheng, junshan.zhang}@asu.edu).

Georgios Y. Lazarou and Rose Hu are with the Department of Electrical and Computer Engineering, Mississippi State University ({glaz, hu}@ece.msstate.edu).

packet loss rate. Understanding the impact of TCP dynamics on its performance is critical for optimizing TCP and the design of active queue management techniques [7], [8] and TCPfriendly multicast protocols [9], [10]. However, TCP is a very complex protocol, and the fast-changing network conditions make the development of an accurate TCP stochastic model to be a very challenging task.

Stochastic models of TCP can be classified into three classes: (1) steady-state models for predicting the performance of bulk transfer flows [11], [3], (2) models for short-lived flows assuming low loss rates [12], [6], [13], and (3) models that combine the two above models [2], [1].

To the best of our knowledge, none of the steady-state models proposed so far account for the slow-start phase which begins at the end of every single time-out. The work in [3] assumes that the slow-start phase happens less frequently than the congestion-avoidance phase and the throughput in the slow-start phase is less than that in the congestion-avoidance phase, and that the slow-start phase can be ignored safely. While this could be the case with very small loss rates, the assumption does not hold in general. Empirical measurements show that 90% of the packet losses lead to time-outs [3]. Since TCP enters the slow-start phase when a time-out occurs, accurate TCP performance models must take into consideration of the aggregate effects of the slow-start phases.

All steady-state models assume the availability of unlimited data to send. Hence, the impact of the transient phase on performance is considered insignificant, and therefore is ignored. These models work well only for predicting the TCP send rate or the throughput of bulk data transfers, and are not applicable to predicting the performance of short-lived TCP flows.

It is noted in [14]-[15] that the majority of TCP traffic in the Internet consists of short-lived flows, i.e., the transmission comes to an end during the slow-start phase before switching to the congestion-avoidance phase. Hence, new models are needed that are capable of predicting the performance of shortlived TCP flows; and this is one of the main subject of our study.

In this paper, we first develop a better and tractable model for the congestion window growth pattern in the slow-start phase. Using this new slow-start phase model, we construct an accurate model for the short-lived TCP flows and then an extended and more accurate TCP steady-state model. Major improvement in both models is achieved by relaxing key assumptions and enhancing critical approximations that have been made in existing popular models.

The remainder of the paper is organized as follows. Section II presents an analysis in developing the improved and extended steady-state model. Section III builds the stochastic model for short-lived flows. In section IV, both models are validated with simulations and compared against existing models. Finally, Section V concludes the paper.

II. Steady-state Model Incorporating the Slow-start Phase

A. Assumptions

As in [3], we develop our models based on the BSD TCP Reno release [16]. We assume that the link speed is very high, the round-trip time (RTT) remains fairly constant at all times, and the sender sends full-sized segments whenever the congestion window (cwnd) allows. The advertised window is assumed to be always a constant and large. Thus, the congestion window evolution alone determines the send rate, which roughly can be described as cwnd/RT T.

We model the dynamics of TCP in terms of “rounds” as done in [3]. A round starts when a window of packets is sent by the sender and ends when one or more acknowledgments are received for these packets. The effect of the delayed acknowledgment is taken into consideration, but neither the Nagle algorithm nor the silly window syndrome avoidance is considered. In addition, we assume that the packet losses are in accordance with the bursty loss model. The packet losses in different rounds are independent, but they are correlated within a single round; that is, if one packet in a round is lost, then

Fig. 1. The extended steady state model - evolution of congestion window size when loss indications are triple-duplicate ACK’s and time-outs.

the following back to back packets in the same round are also assumed to be lost. This is an idealization of the packet loss dynamics observed in the paths where FIFO drop-tail queues are used [1]. Finally, we assume that the sender has unlimited data to send.

B. Model Development

Fig. 1 depicts an instance of the congestion window’s evolution over time. As shown in the figure, when a timeout occurs due to lost packets, TCP enters into the slow-start phase to recover from a perceived network congestion.

Let TDP be the period between two triple-duplicate (T D) losses, Z_{i}^{ss} be the time spent in the slow-start phase, Z_{i}^{T D} be the duration of the congestion-avoidance phase, and Z_{i}^{T O} be the time interval of the time-out phase. Let M_{i} be the number of packets sent during the total time S_{i}. Then, we have that

M_{i} = Y_{i}^{ss} + ∑_{j=1}^{n_{i}} Y_{ij} + R_{i},  (1)
S_{i} = Z_{i}^{ss} + Z_{i}^{T D} + Z_{i}^{T O}
= Z_{i}^{ss} + ∑_{j=1}^{n_{i}} A_{ij} + Z_{i}^{T O},  (2)

where Y_{i}^{ss} is the number of packets sent during the slowstart phase, A_{ij} is the duration of the jth TDP, n_{i} is the total number of the TDPs in the interval Z_{i}^{T D}, Y_{ij} is the number of packets sent during the jth TDP of interval Z_{i}^{T D}, and R_{i} is the number of packets sent during the time-out phase. W_{i}^{ss} is the window size at the end of a slow start and finally W_{ij}^{T D} is the window size at the end of the j^{th} TDP.

Assuming (S_{i}, M_{i}) to be a sequence of independent and identically distributed (i.i.d.) random variables, we determine the send rate as

B = \frac{E[M]}{E[S]}.

Considering n_{i} to be i.i.d. random variables and independent of Y_{ij} and A_{ij}, we have

B = \frac{E[Y^{ss}] + E[∑_{j=1}^{n_{i}} Y_{ij}] + E[R]}{E[Z^{ss}] + E[∑_{j=1}^{n_{i}} A_{ij}] + E[Z^{T O}]}
= \frac{E[Y^{ss}] + E[n]E[Y] + E[R]}{E[Z^{ss}] + E[n]E[A] + E[Z^{T O}]}.  (3)

We next derive the closed form expressions for these expected values in the different TCP phases: the slow-start, the congestion-avoidance and the time-out phases.

1) The Slow-Start Phase: According to TCP Reno [17], [16], the current state of a TCP connection is determined based upon the values of the congestion window size (cwnd) and the slow-start threshold (ssthresh). If cwnd is less than ssthresh, TCP is in the slow-start phase, otherwise, it is in the congestion-avoidance phase.

Since TCP has no knowledge of the network conditions, during the slow-start phases, it probes for the available bandwidth “greedily”, i.e., it increases the cwnd by one upon the receipt of a non-repeated acknowledgment. This algorithm can be formulated as

cwnd_{i} = ⌈\frac{cwnd_{i−1}}{2} ⌉ + cwnd_{i−1},  (4)

in which cwnd_{i} is the congestion window size for the i^{th} round. Equation (4) is due to the fact that assuming no loss, in round (i − 1), there is a total of cwnd_{i−1} packets sent to the destination, which, in turn, causes the receiver to generate ⌈cwnd_{i−1}/2⌉ acknowledgments^{1}. According to the slow-start algorithm, upon receiving these ACKs, the sender increases the cwnd by the number of ACKs it has obtained, which is ⌈cwnd_{i−1}/2⌉.

Noting that the congestion window is an integer, we can simplify (4) as follows^{2}:

cwnd_{i} = ⌈\frac{3}{2}cwnd_{i−1}⌉.  (5)

1⌈x⌉ =the smallest integer bigger than x.

2In deriving a model for the latency of the short-lived TCP flows, (5) was approximated in [1] as: cwnd_{i} = 3cwnd_{i−1}/2.

Rearranging, we get

⌈\frac{cwnd_{i−1}}{2} ⌉ = ⌈\frac{1}{2}⌈\frac{3}{2}cwnd_{i−2}⌉⌉
≈ cwnd_{i−2}.  (6)

Substituting this in (4), we get the following:

cwnd_{i} ≈ cwnd_{i−2} + cwnd_{i−1}.  (7)

In order to examine the accuracy of this approximation, a typical evolution of cwnd is given as follows:

1, 2, 3, 5, 8, 12, 18, 27...

Compared with the sequence generated by (7):

1, 2, 3, 5, 8, 13, 21, 34...

and the evolution of cwnd proposed by the model in [1]:

1, 1.5^{1}, 1.5^{2}, 1.5^{3}, 1.5^{4}, 1.5^{5}, 1.5^{6}, 1.5^{7}...

or calculated as

1, 1.5, 2.25, 3.38, 5.06, 7.59, 11.39, 17.09...

The similarity between the two previous sequences and the discrepancy between the real evolution of cwnd with the proposed model in [1] show that (7) gives a better approximation of the slow-start phase.

Noting that (7) generates the Fibonacci sequence, we can therefore express cwnd as follows:

cwnd_{n} = C_{1}X_{1}^{n} + C_{2}X_{2}^{n}, n = 1, 2, 3...  (8)

where^{3}

X_{1,2} = \frac{1 ± \sqrt{5}}{2}.  (9)

C_{1} and C_{2} are determined by the initial value of cwnd. Assuming the initial value of cwnd is 1, we get

C_{1,2} = \frac{5 ± \sqrt{5}}{10}.  (10)

By knowing the evolution of the congestion window, we can calculate the total number of packets, Y_{n}^{ss}, that are sent until the n_{th} round, by summing the congestion window size during each round:

Y_{n}^{ss} = ∑_{i=1}^{n} cwnd_{i}
= C_{1}X_{1}^{n+2} + C_{2}X_{2}^{n+2} − 2
≈ C_{1}X_{1}^{n+2} − 2.  (11)

3X_{1} is also called the golden number which will be denoted as g in the later parts of this paper.

The last approximation is due to the fact that:

C_{2}X_{2}^{n+2} ≤ |\frac{5 − \sqrt{5}}{10} × (\frac{1 − \sqrt{5}}{2})^{3}| = 0.065

Thus, from Equation (11), the number of rounds, n, can be computed as:

n = log_{g}(\frac{Y_{n}^{ss} + 2}{C_{1}}) − 2.  (12)

Substituting (12) into (8), we can get the approximate relationship between the congestion window size and the total number of packets that have been sent, as follows:

cwnd_{n} = \frac{Y_{n}^{ss} + 2}{g^{2}}.  (13)

Taking the expectation of both sides of Equation (13), we have:

E[W^{ss}] = \frac{E[Y^{ss}] + 2}{g^{2}}  (14)

in which E[W^{ss}] is the expectation of cwnd_{n}.

If the slow-start phase is ended by a packet loss, the expected data that have been sent during this phase can be calculated as

E[Y^{ss}] = \frac{1 − p}{p},  (15)

where p is the loss rate.

Substituting the value of E[Y^{ss}] in (14), we get:

E[W^{ss}]^{∗} = \frac{1 + p}{pg^{2}}.  (16)

This is the expected value of the congestion window when the slow-start phase ends due to a lost packet. Observing that when p is small, the expected value would be much bigger than the expected value of ssthresh, i.e.,

E[W^{ss}]^{∗} ≫ E[ssthresh] = \frac{E[W^{T D}]}{2},  (17)

where the last equality comes from the fact that after each time-out, the slow-start threshold is set to half of the current congestion window W^{T D}.

Thus, it is safe to assume that TCP enters the congestionavoidance phase before a packet gets lost. That is, we assume that TCP always switches from the slow-start to congestionavoidance phase when the congestion window reaches the value of ssthresh. We show the proof of this in the next section after obtaining the closed-form solution of E[W^{T D}].

As a consequence, we have that the expected congestion window size at the end of the slow start be constrained by the limitation of the slow-start threshold:

E[W^{ss}] = E[ssthresh] = \frac{E[W^{T D}]}{2}.  (18)

Fig. 2. Packets sent during a TDP. Adopted from [3].

Using (18) in (14) and rearranging, we obtain the expected number of packets sent during the slow-start phase:

E[Y^{ss}] = \frac{E[W^{T D}]g^{2}}{2} − 2.  (19)

The time spent in the slow-start phase is obtained by multiplying the number of rounds described in (12) with RTT:

E[Z^{ss}] = log_{g}(\frac{E[W^{T D}]}{2C}) · RT T.  (20)

2) The Congestion-Avoidance Phase: Let Y_{i} be the number of packets sent during the ith TDP, A_{i} be the duration, and W_{i}^{T D} be the window size at the end of the TDP. With reference to Fig. 2, we obtain the following relations [3]^{4}:

Y_{i} = α_{i} + W_{i}^{T D} − 1,  (21)
A_{i} = ∑_{j=1}^{X_{i}+1} r_{ij},  (22)
W_{i}^{T D} = \frac{W_{i−1}^{T D}}{2} + \frac{X_{i}}{b} − 1,  (23)

and

Y_{i} = \frac{X_{i}}{2} (\frac{W_{i−1}^{T D}}{2} + W_{i}^{T D} − 1) + β_{i},  (24)

where X_{i} is the penultimate round in the TDP which experiences packet losses, r_{ij} is the round trip time, α_{i} is the number of packets sent in a TDP until the first loss happens, b is the number of packets acknowledged by a received ACK, and β_{i} is the number of packets sent in the fast retransmit phase, which is the last round [3].

4For details see [3]. Note that (23) captures more accurately the window size at the end of the TDP than the one presented in [3].

Based on our assumptions, α_{i} is obviously geometrically distributed. Hence,

P [α_{i} = k] = (1 − p)^{k−1}p,  k = 1, 2, … (25)

and therefore, we have that

E[Y] = \frac{1 − p}{p} + E[W^{T D}].  (26)

In addition, based on (23) and (24), we also have that

E[X] = b( \frac{E[W^{T D}]}{2} + 1)  (27)
E[Y] = \frac{E[X]}{2} ( \frac{E[W^{T D}]}{2} + E[W^{T D}] − 1) + E[β], (28)

where we assume X_{i} and W_{i}^{T D} are mutually independent. Combining (26), (27), and (28), we get

\frac{1 − p}{p} + E[W^{T D}] = \frac{E[X]}{2} ( \frac{E[W^{T D}]}{2} + E[W^{T D}] − 1) + E[β]
= \frac{b( \frac{E[W^{T D}]}{2} + 1)}{2} ×
( \frac{E[W^{T D}]}{2} + E[W^{T D}] − 1) + E[β]. (29)

Since β_{i} is the number of packets sent when k packets in the penultimate round are ACKed, its value equals to k with probability

A(w, k) = \frac{(1 − p)^{k}p}{1 − (1 − p)^{w}} .  (30)

Therefore,

E[β] = E[ ∑_{k=0}^{w−1} k · P (β = k)|w]
= E[ ∑_{k=0}^{w−1} \frac{k(1 − p)^{k}p}{1 − (1 − p)^{w}} |w]
= E[ \frac{(1 − p)(1 − pw(1 − p)^{w−1} − (1 − p)^{w})}{p(1 − (1 − p)^{w})} |w]
≈ (E[W^{T D}] − 1)(1 − p)  (31)

for p small. Using (31) in (29) and rearranging, we get:

E[W^{T D}] = − \frac{2(b − 2p)}{3} + \sqrt{\frac{4(bp + 2(1 − p^{2}))}{3bp} + ( \frac{2b − 4p}{3b} )^{2}}. (32)

Inserting (32) in (27), we obtain

E[X] = \frac{(2p + 3)b − b^{2}}{3} +\sqrt{\frac{b^{2}p + 2b(1 − p^{2})}{3p} + ( \frac{b − 2p}{3} )^{2}}, (33)

and

E[A] = (E[X] + 1)E[r]
= RT T ( − \frac{b^{2} − (2p + 6)b}{3}
+\sqrt{\frac{b^{2}p + 2b(1 − p^{2})}{3p} + (\frac{b − 2p}{3})^{2}}), (34)

where we assume r_{ij}’s to be i.i.d. and E[r] ≈ RT T.

In the previous subsection, we stated without proof that the slow-start phase will enter the congestion-avoidance phase before a packet loss happens. This can be proved if E[W^{ss}]^{∗}, the expected congestion window size at the end of the slowstart phase due to a packet loss, is bigger than the value of E[ssthresh] = E[W^{T D}]/2, which is the expected threshold at the beginning of the slow-start phase. In other words, we need to show that:

\frac{1 + p}{pg^{2}} ≥ \frac{E[W^{T D}]}{2},  (35)

where E[W^{T D}] is given by (32). This is easily shown below, under the (normal) condition that p is small:

\frac{1 + p}{pg^{2}} ≥ \sqrt{\frac{2}{3bp}}
⇔ 1 − 0.3p + p^{2} ≥ 0

The last inequality stands obviously. In fact, (35) is valid ∀p ∈ [0, 1].

3) The Time-out Phases: The probability that a loss indication is a time-out under the current congestion window size w, is given in [3] as:

min(1, \frac{(1 − (1 − p)^{3})(1 + (1 − p)^{3}(1 − (1 − p)^{w−3}))}{1 − (1 − p)^{w}})

(36)

which gets simplified when the loss rate, p, is small:

Q^{T D}(w) = min(1, \frac{3}{w}).

Thus, Q^{T D}, the expected probability that a loss leads to a time-out at the end of the congestion-avoidance phase, is approximated in [3] as follows:

Q^{T D} = E[Q^{T D}(w)]
= min(1, \frac{3}{E[W^{T D}]}).  (37)

The traffic traces collected in [3] indicate that the effect of the time-outs must always be captured by any TCP performance prediction model. In most of the traces, time-out events out-numbered the fast retransmit events, i.e., Q^{T D} is around 90% of the total loss. This value is larger than the value given by the formula of (37), as we further calculated that the E[W^{T D}] is greater than 10, which, in turn, renders the Q^{T D} to be less than 30%. So, we believe that this approximation underestimates the real Q^{T D}. As a matter of fact, the underestimation of Q^{T D} in [3] is due to the approximation of E[1/W] ≈ 1/E[W] by noting that:

\begin{aligned}& E[(\frac{1}{\sqrt{W}})(\sqrt{W})]^{2} & ≤ & E[(\frac{1}{\sqrt{W}})^{2}]E[(\sqrt{W})^{2}] \\ ⟹ & \frac{1}{E[W]} & ≤ & E[\frac{1}{W}] \end{aligned}

The equality holds only when W is a constant.

Now, using Taylor’s formula and expectation properties, we obtain the following^{5}

E[\frac{1}{W} ] ≈ \frac{1}{E[W]}(1 + \frac{V ar(W)}{E[W]^{2}}).  (38)

Hence, to find a more accurate approximation of Q^{T D}, we must find the variance of W.

After a rigorous analysis^{6}, we obtain the variance of W^{T D}, the congestion window size at the end of TDP, to be:

V ar[W^{T D}]_{p→0} ≈ \frac{8(\sqrt{3} − 1)}{3bp}.  (39)

Substituting (32) and (39) into (38), we get:

E[\frac{1}{W^{T D}}] = \frac{1}{E[W^{T D}]}(1 + \frac{V ar(W^{T D})}{E[W^{T D}]^{2}})
= \frac{1}{E[W^{T D}]}(1 + ^{\frac{\frac{8(\sqrt{3}−1)}{3bp}}{\frac{8}{3bp}}})
= \frac{\sqrt{3}}{E[W^{T D}]}.  (40)

Equation (40) gives a better, but still simple, estimation of E[1/W^{T D}]. Then, Q^{T D}, the probability that a loss detection is a time-out (TO), can be found to be:

Q^{T D} ≈ min(1, \frac{3\sqrt{3}}{E[W^{T D}]}).  (41)

The probability of n_{i}, the number of TDPs, is derived according to Q^{T D}:

p(n_{i} = k) = (1 − Q^{T D})^{(k−1)} · Q^{T D}.

This is due to the fact that, with probability Q^{T D}, the packets lost at the end of the congestion control phase lead to a TO, and, with probability 1 − Q^{T D} the TCP connection stays in TDP. By taking the expectation of n_{i}, we get:

E[n] = \frac{1}{Q^{T D}} .  (42)

The expressions for the number of packets sent in the timeout phase, E[R] and its duration, E[Z^{T O}] are given in [3]

5See Appendix I for the derivation.

6See Appendix II for details.

as:

E[R] = \frac{1}{1 − p}  (43)
E[Z^{T O}] = T_{0} \frac{f(p)}{1 − p},  (44)

where f(p) is defined as:

f(p) = 1 + p + 2p^{2} + 4p^{3} + 8p^{4} + 15p^{5} + 32p^{6}. (45)

4) The Steady State Send Rate and Throughput: Substituting Equations (19), (20), (26), (32), (34), (41), (42), (43) and (44) into (3), and taking into consideration the limitation of the window size [3], we finally derive the send rate as:

B = \{ \frac{\frac{E[W^{T D}]g^{2}}{2} −2+ \frac{1}{Q^{T D} (E[W^{T D}])} ( \frac{1−p}{p} +E[W^{T D}])+ \frac{1}{1−p}}{(log_{g}( \frac{E[W^{T D}]}{2C_{1}} )+ \frac{1}{Q^{T D} (E[W^{T D}])} ( \frac{bE[W^{T D}]}{2} +b+1))RT T + \frac{f(p)T_{0}}{1−p}} when E[W^{T D}] < W_{m} \frac{\frac{Wmg^{2}}{2} −2+_{\frac{1}{Q^{T D} (Wm)}} ( \frac{1−p}{p} +W_{m})+ \frac{1}{1−p}}{log_{g}( \frac{Wm}{2C_{1}} )RT T +_{\frac{1}{Q^{T D} (Wm)}} (( \frac{b}{8} W_{m}+ \frac{1−p}{pWm} +2)+1)RT T + \frac{f(p)T_{0}}{1−p}} when E[W^{T D}] ≥ W_{m}.

(46)

This can be further simplified as

\begin{matrix}min(\frac{W_{m}}{RT T} , \\ _{\frac{1}{RT T \sqrt{\frac{2bp}{3}} +min(1,9\sqrt{\frac{bp}{8}})p( \frac{RT T}{2} log_{g}(_{\frac{2}{3bpC^{2}_{1}}} )+T_{0}(1+32p^{2}))}}). \end{matrix}

(47)

To derive the throughput, we only need to change E[Y], the expected size of packets that have been sent in a TDP, to E[Y′], the expected size of packets that have been received in a TDP. E[Y′] can be expressed as:

E[Y′] = E[α] + E[β] − 1,  (48)

where E[α] is 1/p and E[β] is given by Equation (31). Also we substitute E[R] with E[R′], the expected number of packets received in the time out phase, where [3]

E[R′] = 1

Thus, the throughput can be formulated as:

H = \frac{E[Y^{ss}] + E[n]E[Y′] + E[R′]}{E[Z^{ss}] + E[n]E[A] + E[Z^{T O}]}  (49)

or

H = \{ \frac{\frac{E[W^{T D}]g^{2}}{2} −2+ \frac{1}{Q^{T D} (E[W^{T D}])} ( \frac{1−p}{p} +(E[W^{T D}]−1)(1−p))+1}{(log_{g}( \frac{E[W^{T D}]}{2C_{1}} )+ \frac{1}{Q^{T D} (E[W^{T D}])} ( \frac{bE[W^{T D}]}{2} +b+1))RT T + \frac{f(p)T_{0}}{1−p}} when E[W^{T D}] < W_{m} \frac{\frac{Wmg^{2}}{2} −2+_{\frac{1}{Q^{T D} (Wm)}} ( \frac{1−p}{p} +(W_{m}−1)(1−p))+1}{log_{g}( \frac{Wm}{2C_{1}} )RT T +_{\frac{1}{Q^{T D} (Wm)}} (( \frac{b}{8} W_{m}+ \frac{1−p}{pWm} +1)+1)RT T + \frac{f(p)T_{0}}{1−p}} when E[W^{T D}] ≥ W_{m}

(50)

Fig. 3. Our proposed model is compared with the one developed in [3] in terms of the predicted throughput difference versus the loss rate (p) for the case of: RT T = 200ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec, W_{m} = 20segments, b = 2.

which, when p is small, can be simplified as (47). This can be explained by noting that, if a loss seldom happens, then the send rate should just equal to the throughput.

Fig. 3 compares our model against the one proposed in [3]. It shows the predicted throughput difference versus p for the case of RT T = 200 ms, MSS = 536 bytes, w_{1} = 1 segment, T_{0} = 1 sec, W_{m} = 20 segments, and b = 2. With both models, when p → 0, then H → W_{m}/RT T. However, for 10^{−3} < p < 10^{−1}, the model in [3] overestimates the throughput by up to a factor of 2.5 (at p ≈ 10^{−2}). Obviously, when p → 1, again both models obtain the same performance values.

III. Stochastic Model for Short-lived Flows Our proposed model for the short-lived TCP flows is par-

tially based on our results given in Section II-B.1. In addition, it is composed of four parts according to a typical shortlived flow evolution: the start of the connection (three-way-handshake), the initial slow-start phase, the first loss, and the subsequent losses. We first derive the latency a flow experience in each part, and then sum them to obtain the total latency.

A. The Connection Start-up Phase

Every TCP connection starts with the three-way-handshake process. Assuming that no ACK packets can get lost, this process can be well modeled as follows [1]:

E[T_{twhs}] = RT T + T_{s}(\frac{1 − p}{1 − 2p} − 1)  (51)

where T_{s} is the duration of SYN time-out and p is the packet loss rate.

We further assume that two or more time-outs within the three-way-handshake process is very rare. Otherwise, the slow-start threshold would get set to one, and therefore, the connection would get forced directly into the congestionavoidance phase instead of into the slow-start phase.

B. The Initial Slow-start Phase

After the three-way-handshake, the slow-start phase begins. In this phase, the sender’s congestion window (cwnd) increases exponentially until either of the following two events occur: a packet gets lost or the cwnd reaches its maximum value W_{m}.

In order to derive the latency for this phase, E[Y_{init}], the expected number of packets sent until a loss occurs is given by the following enhanced equation (based on the one given in [1]):

E[Y_{init}] = \frac{(1 − (1 − p)^{d})(1 − p)}{p}  (52)

where d is the total file size measured in packets that must be transmitted.

Substituting (52) in (14), we obtain the expected congestion window size at the end of the slow-start phase due to packet losses as:

E[W_{init}] = \frac{(1 − (1 − p)^{d})(1 − p) + 2p}{pg^{2}}  (53)

If E[W_{init}] > W_{m}, then the congestion window first grows to W_{m} and then remains there while sending the rest of the packets. Thus, the whole procedure is divided into two parts [1]. From (14), the number of packets sent when the cwnd grows to W_{m} is given by:

data_{1} = g^{2} · W_{m} − 2.  (54)

Substituting (54) into (12), we can obtain the duration of this step measured in rounds:

n_{1} = log_{g}(\frac{W_{m}}{C_{1}} ).  (55)

In the second part,

n_{2} = \frac{E[Y_{init}] − data_{1}}{W_{m}}  (56)

Fig. 4. An illustration of a triple-duplicate (TD) event.

rounds are needed to transmit the remaining E[Y_{init}] − data_{1} packets.

Combining the previous results together and using (12) for the E[W_{init}] ≤ W_{m} case, the expected slow-start latency is computed as follows:

E[n] = \{ \begin{matrix}[⌈log_{g}(\frac{W_{m}}{C_{1}} )⌉ + \frac{1}{W_{m}} (E[Y_{init}] − g^{2}W_{m} − 2)] \\ when E[W_{init}] > W_{m} \\ ⌈log_{g}(\frac{E[Y_{init}]+2}{C_{1}})⌉ − 2 when E[W_{init}] ≤ W_{m} \end{matrix}

(57)

C. The First Loss

The initial slow-start phase ends when a packet loss is detected with a probability of 1−(1−p)^{d}. When a packet gets lost, it could cause retransmission time-out (RTO) or lead to a triple duplicate ACKs, in which case TCP could recover in a round or two by using the fast retransmit and the fast recovery mechanism. We first derive the probability that a packet loss leads to a time-out (TO).

Due to the exponential growing pattern of cwnd in the slowstart phase, Q^{ss}, the probability that a packet loss leads to a TO is different from the probability that when the sender is in the congestion-avoidance phase. With reference to Fig. 4, we derive the expression of Q^{ss} as follows.

In the round with a TD event, let W^{ss} be the current size of cwnd, which has a value w. In this round, w packets were sent. Among them, k packets are assumed to be ACKed. Since the connection is still in the slow-start phase, cwnd increases to w + k and another 2k packets are sent in the next round^{7}. If more than three packets from these 2k packets get ACKed, then a TD would occur; otherwise, a TO would take place. Letting

h(m) = ∑_{i=0}^{2}(1 − p)^{i}p  if m ≥ 3,  (58)

be the probability that no more than 2 packets have been transmitted successfully in a round of m packets, we then obtain Q^{ss} to be

Q^{ss}(W^{ss}) = \{ \begin{matrix}1, W^{ss} ≤ 2 \\ ∑_{k=0}^{1} A(W^{ss}, k) \\ + ∑_{k=2}^{W^{ss}−1} A(W^{ss}, k)h(2k), otherwise, \end{matrix}

(59)

where A(w, k) is as given by (30) and gives the probability that the first k packets have been successfully transmitted and ACKed in a round of w packets, provided that there might be one or more packets got lost. Simplifying (59), we get Q^{ss}(W^{ss}) to be equal to

min(1, \frac{p(2 − p) + (1 − (1 − p)^{3})(1 − p)^{2}(1 − (1 − p)^{W^{ss}−2})}{1 − (1 − p)^{W^{ss}}} ).

(60)

As p approaches zero, (60) reduces to

Q^{ss} = lim_{p→0} E[Q^{ss}(W^{ss})] = min(1, \frac{2}{E[W^{ss}]}). (61)

In case of delayed acknowledgment, k successfully received packets generate ⌊k/2⌋^{8} ACKs, and thus the size of the cwnd increases to ⌊k/2⌋ + w and ⌊k/2⌋ + k packets are sent. Therefore Q^{ss} can be computed as:

Q^{ss} = \{ \begin{matrix}1, W^{ss} ≤ 2 \\ ∑_{k=0}^{1} A(W^{ss}, k) \\ + ∑_{k=2}^{W^{ss}−1} A(W^{ss}, k)h(⌊\frac{k}{2} ⌋ + k), otherwise \end{matrix}

which is same as (60) since

h(2k) = h(⌊\frac{k}{2} ⌋ + k) for k ≥ 2.

The expected time that TCP spends in the RTOs is given by (44). The time that TCP spends in the fast retransmit phase, n_{t}, depends on where the loss would happen [2]:

n_{t} = \{ \begin{matrix}2RT T,  if the lost packet is in the last \\ three packets of the window \\ RT T,  otherwise \end{matrix} (62)

7The delayed acknowledgment concept is not applied here, but we show later that it does not affect the analysis of the Q^{ss}. 8⌊k/2⌋ is the biggest integer small than k/2.

Thus, when the congestion window size W^{ss} is bigger than three, the expected time, E[n_{t}] can be found to be:

E[n_{t}] = \frac{1 − (1 − p)^{W^{ss}−3}}{1 − (1 − p)^{W^{ss}}} × 2RT T

+\frac{(1 − p)^{W^{ss}−3}(1 − (1 − p)^{3})}{1 − (1 − p)^{W^{ss}}} × RT T

= RT T · \frac{2 − (1 − p)^{W^{ss}−3} − (1 − p)^{W^{ss}}}{1 − (1 − p)^{W^{ss}}} .(63)

Finally, the expected latency that this loss would incur is:

T_{loss} = (1 − (1 − p)^{d})(Q^{ss}E[Z^{T O}] + (1 − Q^{ss})E[n_{t}]), (64)

where W^{ss} is

W^{ss} = min(W_{m}, \frac{E[Y_{init}] + 2}{g^{2}}).  (65)

D. Sending the Rest of the Packets

After the first packet loss, the transmission latency of the rest (d − E[Y_{init}]) packets is obtained by using our extended steady-state model as follows:

T_{rest} = \frac{d − E[Y_{init}]}{H}
= \frac{dp − (1 − (1 − p)^{d})(1 − p)}{p · H},  (66)

where H is as given by (49).

E. Total Latency

Grouping (51), (57), (63) and (66) together and considering the delay (T_{delay}) caused by the delayed acknowledgment for the first packet (whose mean value is 100ms for the BSDderived implementations), we now have the total expected latency:

T_{latency} = E[T_{twhs}]+E[n]RT T +T_{loss}+T_{rest}+T_{delay}−\frac{RT T}{2} .

(67)

Note that the last term is due to the fact that only half of a round is needed to send the last window of packets.

In Fig. 5, we compare this model for short-lived TCP connections against our steady-state model. Clearly, as the transferred file size increases, the short-lived TCP connection model approaches the steady state model. This is because when a connection has a large amount of data to send, TCP spends most of its time in the steady-state. In addition, as the loss rate increases, the throughput predicted by the short-lived TCP connection model approaches the one predicted by the

Fig. 5. The model for short-lived TCP connections is compared with the steady-state model in terms of throughput versus loss rate for different file sizes. Model parameter values: RT T = 200ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec, W_{m} = 20segments, b = 2.

Fig. 6. The ns-2 model that was used to validate our analytical TCP models.

steady-state model. This is because as the connection loses its packets more frequently, the transient slow-start phase ends quickly and the remaining packets are sent in the steady-state phase.

IV. Model Validation through Simulation

We validated our proposed analytical models with simulation experiments. We performed all experiments in ns-2 [18] using the FullTCP agent. The FullTCP agent is modeled based on the 4.4BSD TCP implementation and can simulate all the important features of TCP Reno. The ns-2 simulation model used in all experiments is shown in Fig. 6.

Unlike in [1] where the Bernoulli loss model is used, in our experiments packets were getting lost according to the bursty loss model. Since ns-2 does not have built-in bursty packet loss model, we added our own BurstyError Model, which was derived from the basic Error Model class. This BurstyError Model drops packets with probability p, which is a Bernoulli trial. After a packet is selected to be dropped with probability p, all the subsequent packets in transit are also dropped. This emulates the DropTail queues behavior under congestion conditions.

We used FTP^{9} as the application for sending a controlled number of packets over a 10Mbps link. The experiments were designed such that the minimum RTT was 200ms.

A. The Steady-state Model

Using the same system parameter values that were used to generate Fig. 3, we performed 1000 simulation experiments for each value of p, where p was varied from 0.005 to 0.1. The file size was set to 10MB. Fig. 7 compares the simulation results against the analytical results obtained from our proposed steady-state model (Full: Equation (50), and Approximate: Equation (47)) and the one developed in [3]. Clearly, the results match our expectations. The predicted throughput values at each value of p obtained from our model much closer to the simulation values.

To quantify the accuracy of our model relative to the simulation data, we computed the average error using the following expression taken from [3]):

\frac{∑_{observations} |T h_{predicted}(p) − T h_{observed}(p)|/T h_{observed}(p)}{Number of observations} ,

where T h_{predicted} is the throughput predicted by the models and T h_{observed} is the throughput observed from the simulation experiments. A smaller average error value indicates a better model accuracy. We plotted these average errors against loss rates in Fig. 8. It shows that in most cases the average error is under 8% for our proposed full model (Equation (50)) and above 20% for the one from [3]. Approximately, in most cases, our model is 75% more accurate than the model proposed in [3]. This supports our claim that by including the slow-start phase into the steady-state model more accurate predictions can be obtained.

9FTP is a major Internet application that is used to remotely transfer files.

Fig. 7. Predicted throughput obtained by our proposed steady-state model and the one developed in [3] are compared against simulation results for the case of 0.005 < p < 0.1 RT T = 200ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec, W_{m} = 20segments.

In addition, Fig. 8 depicts the following: the average error in predicted throughput from both analytical models increases as p approaches zero. Let say that p = 0 and the initial slow-start threshold is set to the maximum window size. Then, the initial slow-start phase is extended until the congestion window reaches the maximum window size. Since there are no packet losses, TCP never switches to the congestion avoidance phase, but rather continues transmitting packets at its maximum sending rate allowed by the maximum window size. For these cases that p ≈ 0, our short-lived TCP flow model should be used instead of the steady-state model.

B. Short-lived Flows Model: Latency versus Transferred File Size

Figure 9 shows the relationship between the latency and the transferred file size under no loss conditions. It compares the latency predictions given by our proposed short-lived TCP model (Equation (67)) and the ones obtained by the short-lived TCP models developed in [1] and [2] against the simulation results. Obviously, our model’s prediction values match the simulated values better that the values obtained by the other models. Our model resulted in 5.83% average error, compared to 9.40% and 14.53% obtained by the models in [1] and [2], respectively.

Fig. 8. Our proposed steady-state model is compared with the one developed in [3] in terms of the average error for the case of 0.005 < p < 0.1 RT T = 200ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec, W_{m} = 20segments.

Analyzing the results, we also observed that all prediction errors resulted from our model are within [−RT T/2, RT T/2]. We believe that this is because our model accounts for the delayed acknowledgment mechanism. Thus, for the cases where RT T is small, the prediction errors are insignificant. This is not valid for the other models propose by [1] and [2].

C. Short-lived Flows Model: Throughput versus Loss Rate and File Size

Figures 10, 11 and 12 compares the throughput versus loss rate predictions given by our proposed short-lived TCP model and the one obtained by the short-lived TCP models developed in [1] against the simulation results for the cases of 2KB, 6KB, and 11KB file sizes. Table I compares the two models in terms of the average error.

As can be observed, when the transferred file size is small and the loss rate is low, our model yields more accurate predictions than the model from [1]. Again, this is because our model accounts for the delay acknowledgment mechanism and uses g (golden number) instead of γ (see [1]). However, for large file sizes and loss rates, both models yield similar predictions and in agreement with our steady-state model, as expected.

Fig. 9. Predicted latency versus transferred file size obtained by our shortlived TCP connection model and the ones developed in [1] and [2] are compared against simulation results for the case of p = 0, RT T = 100ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec, W_{m} = 20segments.

TABLE I

Our short-lived TCP connection model is compared against the one proposed in [1] in terms of the average error.

Loss Rate  p = 0  3 × 10^{−3} ∼ 10^{−1} File Size 0.5 ∼ 26KB 2KB  6KB 11KB [CSA00]  9.40%  4.08% 6.43% 8.38% Proposed  5.83%  0.59% 7.54% 7.64% Fig. 10. Predicted throughput versus loss rate obtained by our short-lived TCP connection model and the one developed in [1] are compared against simulation results for the case of a 2KB-file-size and RT T = 100ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec,W_{m} = 20segments.

Fig. 11. Predicted throughput versus loss rate obtained by our short-lived TCP connection model and the one developed in [1] are compared against simulation results for the case of a 6KB-file-size and RT T = 100ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec,W_{m} = 20segments.

Fig. 12. Predicted throughput versus loss rate obtained by our short-lived TCP connection model and the one developed in [1] are compared against simulation results for the case of a 11KB-file-size and RT T = 100ms, MSS = 536bytes, w_{1} = 1segment, T_{0} = 1sec,W_{m} = 20segments.

V. Conclusion

In this paper, we first developed a better and tractable model

for the congestion window growth pattern in the slow-start

phase. Using this new slow-start phase model, we constructed

an accurate model for the short-lived TCP flows and then an

extended and more accurate TCP steady-state model. Major

improvement in both models was achieved by relaxing key

assumptions and enhancing critical approximations that have

been made in existing popular models. We validated our mod-

els with simulations and compared them against the models

developed in [1], [2], [3]. The results support our claim that

our models yield more accurate predictions.

References

[1] N. Cardwell, S. Savage, and T. Anderson, “Modeling TCP latency,” in Proc. IEEE INFOCOM ’2000, Tel Aviv, Israel, Mar. 2000, vol. 3, pp. 1742–1751.

[2] Biplab Sikdar, Shivkumar Kalyanaraman, and Kenneth S. Vastola, “An integrated model for the latency and steady-state throughput of TCP connections,” Performance Evaluation, vol. 46, no. 2-3, pp. 139–154, 2001.

[3] J. Padhye, V. Firoiu, D. F. Towsley, and J. F. Kurose, “Modeling TCP reno performance: A simple model and its empirical validation,” IEEE/ACM Trans. Networking, vol. 8, no. 2, pp. 133–145, Apr. 2000.

[4] K. Thompson, G. J.Miller, and R. Wilder, “Wide-area internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, November 1997.

[5] K. Claffy, G. Miller, and K. Thompson, “The nature of the beast: Recent traffic measurements from an internet backbone,” in Proc. of the INET ’98, July 1998.

[6] J. Heidemann, K. Obraczka, and J. Touch, “Modeling the performance of HTTP over several transport protocols,” IEEE/ACM Trans. Networking, vol. 5, no. 5, pp. 616–630, Oct. 1997.

[7] S. Floyd and K. Fall, “Promoting the use of end-to-end congestion control in the internet,” IEEE/ACM Transactions on Networking, August 1999.

[8] T. J. Ott, T. V. Lakshman, and L. H. Wong, “Sred: Stabilized red,” in Proceedings of the INFOCOM ’99, March 1999.

[9] J. Blot and T. Turletti, “Experience with rate control mechanisms for packet video in the internet,” Computer Communications Review, vol. 28, no. 1, January 1998.

[10] L. Vivisano, L. Rizzo, and J. Crowcroft, “Tcp-like congestion control for layered multicast data transfer,” in Proc. of IEEE INFOCOM ’98, April 1998.

[11] J. Bolliger, T. Gross, and U. Hengartner, “Bandwidth modeling for network-aware applications,” in In Proceedings of the INFOCOM’99, March 1999.

[12] C. Partridge and T. J. Shepard, “TCP/IP performance over satellite links,” IEEE Network, pp. 44–49, September 1997.

[13] J. Mahdavi, “TCP performance tuning,” April 1997.

[14] C. R. Cunha, A. Bestavros, and M. E. Crovella, “Characteristics of WWW client-based traces,” technical report BU-CS-95-010, Boston University, July 1995.

[15] M. Mellia, I. Stoica, and H. Zhang, “TCP model for short lived flows,” IEEE Commun. Lett., vol. 6, pp. 85–87, Feb. 2002.

[16] W. R. Stevens, TCP/IP illustrated, vol. 1, Addison-Wesley, Reading, MA, 1994.

[17] V. Jacobson, “Congestion avoidance and control,” in Proc. SIGCOMM ’88, Stanford, CA, 1988, pp. 314–329.

[18] UCB/LBNL/VINT, “The network simulator ns-2,” 2002.

[19] M. Mitzenmacher and R. Rajaraman, “Towards more complete models of tcp latency and throughput,” Journal of Supercomputing, vol. 20, no. 2, September 2001.

[20] T. Lakshman and U. Madhow, “The performance of TCP/IP for networks with high bandwidth-delay products and random loss,” IEEE/ACM Trans. Networking, vol. 5, no. 3, pp. 336–350, July 1997.

[21] A. Kumar, “Comparative performance analysis of versions of TCP in a local network with a lossy link,” IEEE/ACM Trans. Networking, vol. 6, no. 4, pp. 485–498, 1998.

[22] J. Mahdavi and S. Flyod, “Tcp-friendly unicast rate-based flow control,” Jan 1997, Note sent to end2end-interest mailing list.

[23] M. Mathis, J. Semske, J. Mahdavi, and T. Ott, “The macroscopic behavior of the tcp congestion avoidance algorithm,” Computer Communication Review, vol. 27, no. 3, July 1997.

[24] T. Ott, J. Kemperman, and M. Mathis, “Promoting the use of end-to-end congestion control in the internet,” August 1996, ftp://ftp.bellcore.com/pub/tjo/TCPwindow.ps.

[25] C. Casetti and M. Meo, “A new approach to model the stationary behavior of TCP connections,” in Proc. IEEE INFOCOM ’2000, Tel Aviv, Israel, Mar. 2000, pp. 367–375.

[26] H. Balakrishnan, V. Padmanabhan, S. Seshan, R. H. Katz, and M. Stemm, “TCP behavior of a busy internet server. analysis and improvements,” in Proc. IEEE INFOCOM ’98, San Francisco, CA, Apr. 1998, pp. 252–262.

[27] J. C. Hoe, “Start-up dynamics of TCP’s congestion control an davoideance schemes,” M.S. thesis, Massachusetts Institute of Technology, Cambridge, June 1995.

Appendix I

The expectation of 1/w

From Taylor formula, we know:

f(W) = ∑_{i=0}^{∞} \frac{f^{i}(a)}{i!}(W − a)^{i}  (68)

Let f(W) and a be 1/W and E[W] respectively. We thus

have:

f^{n}(W) = (−1)^{n}n!W^{−(n+1)}  (69)

Substituting f^{i}(a) in (68) and making use of (69) and E[W],

we get:

\frac{1}{W} = ∑_{i=0}^{∞} \frac{(−1)^{i}i!E[W]^{−(i+1)}}{i!} (W − E[W])^{i}

= ∑_{i=0}^{∞} \frac{(−1)^{i}(W − E[W])^{i}}{E[W]^{(i+1)}}  (70)

Taking expectation on both sides of (70), results in:

E[\frac{1}{W} ] = E[∑_{i=0}^{∞} \frac{(−1)^{i}(W − E[W])^{i}}{E[W]^{(i+1)}} ]

= ∑_{i=0}^{∞} E[\frac{(−1)^{i}(W − E[W])^{i}}{E[W]^{(i+1)}} ]

= ∑_{i=0}^{∞} \frac{(−1)^{i}E[(W − E[W])^{i}]}{E[W]^{(i+1)}}

= \frac{1}{E[W]} + \frac{V ar(W)}{E[W]^{3}} + ∑_{i=3}^{∞} \frac{(−1)^{i}E[(w − E[W])^{i}]}{E[W]^{(i+1)}}
≈ \frac{1}{E[W]} + \frac{V ar(W)}{E[W]^{3}}
= \frac{1}{E[W]}(1 + \frac{V ar(W)}{E[W]^{2}})  (71)

The approximation holds when E[W]^{(i+1)} ≫ E[(W −

E[W])^{i}].

Appendix II

The variance of W^{T D}

Using similar assumptions as in the previous analysis, from

(25), we know

V ar[α] = \frac{1 − p}{p^{2}}  (72)

Thus from (21):

V ar[Y] = \frac{1 − p}{p^{2}} + V ar[W^{T D}]  (73)

Using (23), we get the auto-correlation at the zero point^{10}:

R_{w}(0) = \frac{R_{w}(0)}{4} + \frac{R_{x}(0)}{b^{2}}
R_{x}(0) = \frac{3b^{2}}{4} R_{w}(0)  (74)

10This is equal to E[X^{2}].

And using (30), (31) and (32), we can compute the variance of β as following:

V ar[β] = R_{β}(0) − E[β]^{2}
= E[β^{2}] − E[β]^{2}
= E[∑_{k=0}^{w−1} k^{2}p(β = k)|w] − E[β]^{2}
= E[∑_{k=0}^{w−1} \frac{k^{2}(1 − p)^{k}p}{1 − (1 − p)^{w}} |w] − E[β]^{2}
≈ \frac{2(1 − p)^{2}}{p^{2}} − (1 − p)[\sqrt{\frac{8}{3bp}} − 1]^{2} (75)

Using (24), we can also get:

V ar[Y] = V ar[\frac{X_{i}}{2} (\frac{W_{i−1}^{T D}}{2} + W_{i}^{T D} − 1)] + V ar[β]
= E[(\frac{X_{i}}{2} )^{2}]E[(\frac{W_{i−1}^{T D}}{2} + W_{i}^{T D} − 1)^{2}]

−(E[\frac{X_{i}}{2} (\frac{W_{i−1}^{T D}}{2} + W_{i}^{T D} − 1)])^{2} + V ar[β]

= \frac{R_{x}(0)}{4} \frac{5R_{w}(0)}{4} − E[\frac{X}{2} ]^{2}E[\frac{W_{i−1}^{T D}}{2} + W_{i}^{T D} − 1]^{2}

+V ar[β]

= \frac{\frac{3b^{2}}{4} R_{w}(0)}{4} \frac{5R_{w}(0)}{4} − \frac{E[X]^{2}}{4} [\frac{3}{2}E[W^{T D}] − 1]^{2}

+V ar[β]

= \frac{15b^{2}}{64} [V ar[W^{T D}] + E[W^{T D}]^{2}]^{2}

−\frac{E[X]^{2}}{4} [\frac{3}{2}E[W^{T D}] − 1]^{2} + V ar[β]

≈ \frac{15b^{2}}{64} [V ar[W^{T D}] + \frac{8}{3bp}]^{2}

−\frac{1}{4}(\frac{b}{2}\sqrt{\frac{8}{3bp}} + b)^{2}(\frac{3}{2}\sqrt{\frac{8}{3bp}} − 1)^{2}

+\frac{2(1 − p)^{2}}{p^{2}} − (1 − p)[\sqrt{\frac{8}{3bp}} − 1]^{2}  (76)

Combining (76) and (73), we obtain the final equation:

\frac{1 − p}{p^{2}} + V ar[W^{T D}] = \frac{15b^{2}}{64} [V ar[W^{T D}] + \frac{8}{3bp}]^{2}

− \frac{1}{4} ( \frac{b}{2} \sqrt{\frac{8}{3bp}} + b)^{2}( \frac{3}{2} \sqrt{\frac{8}{3bp}} − 1)^{2}

+ \frac{2(1 − p)^{2}}{p^{2}} − (1 − p)[\sqrt{\frac{8}{3bp}} − 1]^{2} (77)

Solving (77), we obtain the variance of W^{T D} as follows:

V ar[W^{T D}]_{p→0} ≈ \frac{8(\sqrt{3} − 1)}{3bp}  (78)