14   Dynamics of TCP

In this chapter we introduce, first and foremost, the possibility that there are other TCP connections out there competing with us for throughput. In 6.3   Linear Bottlenecks (and in 13.7   TCP and Bottleneck Link Utilization) we looked at the performance of TCP through an uncontested bottleneck; now we allow for competition.


Although the focus of this chapter is on TCP Reno, many, though not all, of the ideas presented here apply to non-Reno TCPs as well, and even to non-TCP mechanisms such as QUIC. Several non-Reno TCP alternatives are presented in the following chapter. The section on TCP Friendliness addresses how to compare TCP Reno’s competitive behavior to other alternatives.

We also consider some router-based mechanisms such as RED and ECN that take advantage of TCP’s behavior to provide better overall performance.

The chapter closes with a summary of the central real-world performance problems faced by TCP today; this then serves to introduce the proposed TCP fixes in the following chapter.

14.1   A First Look At Queuing

In what order do we transmit the packets in a router’s outbound-interface queue? The conventional answer is in the order of arrival; technically, this is FIFO (First-In, First-Out) queuing. What happens to a packet that arrives at a router whose queue for the desired outbound interface is full? The conventional answer is that it is dropped; technically, this is known as tail-drop.

While FIFO tail-drop remains very important, there are alternatives. In an admittedly entirely different context (the IPv6 equivalent of ARP), RFC 4681 states, “When a queue overflows, the new arrival SHOULD replace the oldest entry.” This might be called “head drop”; it is not used for router queues.

An alternative drop-policy mechanism that has been considered for router queues is random drop. Under this policy, if a packet arrives but the destination queue is full, with N packets waiting, then one of the N+1 packets in all – the N waiting plus the new arrival – is chosen at random for dropping. The most recent arrival has thus a very good chance of gaining an initial place in the queue, but also a reasonable chance of being dropped later on. See [AM90].

While random drop is seldom if ever put to production use its original form, it does resolve a peculiar synchronization problem related to TCP’s natural periodicity that can lead to starvation for one connection. This situation – known as phase effects – will be revisited in 16.3.4   Phase Effects. Mathematically, random-drop queuing is sometimes more tractable than tail-drop because a packet’s loss probability has little dependence on arrival-time race conditions with other packets.

14.1.1   Priority Queuing

A quite different alternative to FIFO is priority queuing. We will consider this in more detail in 19.3   Priority Queuing, but the basic idea is straightforward: whenever the router is ready to send the next packet, it looks first to see if it has any higher-priority packets to send; lower-priority packets are sent only when there is no waiting higher-priority traffic. This can, of course, lead to complete starvation for the lower-priority traffic, but often there are bandwidth constraints on the higher-priority traffic (eg that it amounts to less than 10% of the total available bandwidth) such that starvation does not occur.

In an environment of mixed real-time and bulk traffic, it is natural to use priority queuing to give the real-time traffic priority service, by assignment of such traffic to the higher-priority queue. This works quite well as long as, say, the real-time traffic is less than some fixed fraction of the total; we will return to this in 20   Quality of Service.

14.3   TCP Fairness with Synchronized Losses

This brings us to the question of just what is a “fair” division of bandwidth. A starting place is to assume that “fair” means “equal”, though, as we shall see below, the question does not end there.

For the moment, consider again two competing TCP connections: Connection 1 (in blue) from A to C and Connection 2 (in green) from B to D, through the same bottleneck router R, and with the same RTT. The router R will use tail-drop queuing.


The layout illustrated here, with the shared link somewhere in the middle of each path, is sometimes known as the dumbbell topology.

For the time being, we will also continue to assume the synchronized-loss hypothesis: that in any one RTT either both connections experience a loss or neither does. (This assumption is suspect; we explore it further in 14.3.3   TCP RTT bias and in 16.3   Two TCP Senders Competing). This was the model reviewed previously in   A first look at fairness; we argued there that in any RTT without a loss, the expression (cwnd1 - cwnd2) remained the same (both cwnds incremented by 1), while in any RTT with a loss the expression (cwnd1 - cwnd2) decreased by a factor of 2 (both cwnds decreased by factors of 2).

Here is a graphical version of the same argument, as originally introduced in [CJ89]. We plot cwnd1 on the x-axis and cwnd2 on the y-axis. An additive increase of both (in equal amounts) moves the point (x,y) = (cwnd1,cwnd2) along the line parallel to the 45° line y=x; equal multiplicative decreases of both moves the point (x,y) along a line straight back towards the origin. If the maximum network capacity is Max, then a loss occurs whenever x+y exceeds Max, that is, the point (x,y) crosses the line x+y=Max.


Beginning at the initial state, additive increase moves the state at a 45° angle up to the line x+y=Max, in small increments denoted by the small arrowheads. At this point a loss would occur, and the state jumps back halfway towards the origin. The state then moves at 45° incrementally back to the line x+y=Max, and continues to zigzag slowly towards the equal-shares line y=x.

Any attempt to increase cwnd faster than linear will mean that the increase phase is not parallel to the line y=x, but in fact veers away from it. This will slow down the process of convergence to equal shares.

Finally, here is a timeline version of the argument. We will assume that the A–C path capacity, the B–D path capacity and R’s queue size all add up to 24 packets, and that in any RTT in which cwnd1 + cwnd2 > 24, both connections experience a packet loss. We also assume that, initially, the first connection has cwnd=20, and the second has cwnd=1.

T A–C B–D  
0 20 1  
1 21 2  
2 22 3 total cwnd is 25; packet loss
3 11 1  
4 12 2  
5 13 3  
6 14 4  
7 15 5  
8 16 6  
9 17 7  
10 18 8 second packet loss
11 9 4  
12 10 5  
13 11 6  
14 12 7  
15 13 8  
16 14 9  
17 15 10 third packet loss
18 7 5  
19 8 6  
20 9 7  
21 10 8  
22 11 9  
23 12 10  
24 13 11  
25 14 12 fourth loss
26 7 6 cwnds are quite close
32 13 12 loss
33 6 6 cwnds are equal

So far, fairness seems to be winning.

14.3.1   Example 2: Faster additive increase

Here is the same kind of timeline – again with the synchronized-loss hypothesis – but with the additive-increase increment changed from 1 to 2 for the B–D connection (but not for A–C); both connections start with cwnd=1. Again, we assume a loss occurs when cwnd1 + cwnd2 > 24

T A–C B–D  
0 1 1  
1 2 3  
2 3 5  
3 4 7  
4 5 9  
5 6 11  
6 7 13  
7 8 15  
8 9 17 first packet loss
9 4 8  
10 5 10  
11 6 12  
12 7 14  
13 8 16  
14 9 18 second loss
15 4 9 essentially where we were at T=9

The effect here is that the second connection’s average cwnd, and thus its throughput, is double that of the first connection. Thus, changes to the additive-increase increment lead to very significant changes in fairness. In general, an additive-increase value of 𝛼 increases throughput, relative to TCP Reno, by a factor of 𝛼.

14.3.2   Example 3: Longer RTT

For the next example, we will return to standard TCP Reno, with an increase increment of 1. But here we assume that the RTT of the A–C connection is double that of the B–D connection, perhaps because of additional delay in the A–R link. The longer RTT means that the first connection sends packet flights only when T is even. Here is the timeline, where we allow the first connection a hefty head-start. As before, we assume a loss occurs when cwnd1 + cwnd2 > 24.

T A–C B–D  
0 20 1  
1 2  
2 21 3  
3 4  
4 22 5 first loss
5 2  
6 11 3  
7 4  
8 12 5  
9 6  
10 13 7  
11 8  
12 14 9  
13 10  
14 15 11 second loss
15 5  
16 7 6  
17 7  
18 8 8 B–D has caught up
20 9 10 from here on only even values for T shown
22 10 12  
24 11 14 third loss
26 5 8 B–D is now ahead
28 6 10  
30 7 12  
32 8 14  
34 9 16 fourth loss
35 8  
36 4 9  
38 5 11  
40 6 13  
42 7 15  
44 8 17 fifth loss
45 8  
46 4 9 exactly where we were at T=36

The interval 36≤T<46 represents the steady state here; the first connection’s average cwnd is 6 while the second connection’s average is (8+9+…+16+17)/10 = 12.5. Worse, the first connection sends a windowful only half as often. In the interval 36≤T<46 the first connection sends 4+5+6+7+8 = 30 packets; the second connection sends 125. The cost of the first connection’s longer RTT is quadratic; in general, as we argue more formally below, if the first connection has RTT = 𝜆 > 1 relative to the second’s, then its bandwidth will be reduced by a factor of 1/𝜆2.

Is this fair?

Early thinking was that there was something to fix here; see [F91] and [FJ92], §3.3 where the Constant-Rate window-increase algorithm is discussed. A more recent attempt to address this problem is TCP Hybla, [CF04]; discussed later in 15.12   TCP Hybla.

Alternatively, we may simply define TCP Reno’s bandwidth allocation as “fair”, at least in some contexts. This approach is particularly common when the issue at hand is making sure other TCP implementations – and non-TCP flows – compete for bandwidth in roughly the same way that TCP Reno does. While TCP Reno’s strategy is now understood to be “greedy” in some respects, “fixing” it in the Internet at large is generally recognized as a very difficult option.

14.3.3   TCP RTT bias

Let us consider more carefully the way TCP allocates bandwidth between two connections sharing a bottleneck link with relative RTTs of 1 and 𝜆>1. We claimed above that the slower connection’s bandwidth will be reduced by a factor of 1/𝜆2; we will now show this under some assumptions. First, uncontroversially, we will assume FIFO droptail queuing at the bottleneck router, and also that the network ceiling (and hence cwnd at the point of loss) is “sufficiently” large. We will also assume, for simplicity, that the network ceiling C is constant.

We need one more assumption: that most loss events are experienced by both connections. This is the synchronized losses hypothesis, and is the most debatable; we will explore it further in the next section. But first, here is the general argument with this assumption.

Let connection 1 be the faster connection, and assume a steady state has been reached. Both connections experience loss when cwnd1+cwnd2 ≥ C, because of the synchronized-loss hypothesis. Let c1 and c2 denote the respective window sizes at the point just before the loss. Both cwnd values are then halved. Let N be the number of RTTs for connection 1 before the network ceiling is reached again. During this time c1 increases by N; c2 increases by approximately N/𝜆 if N is reasonably large. Each of these increases represents half the corresponding cwnd; we thus have c1/2 = N and c2/2 = N/𝜆. Taking ratios of respective sides, we get c1/c2 = N/(N/𝜆) = 𝜆, and from that we can solve to get c1 = C𝜆/(1+𝜆) and c2 = C/(1+𝜆).

To get the relative bandwidths, we have to count packets sent during the interval between losses. Both connections have cwnd averaging about 3/4 of the maximum value; that is, the average cwnds are 3/4 c1 and 3/4 c2 respectively. Connection 1 has N RTTs and so sends about 3/4 c1×N packets. Connection 2, with its slower RTT, has only about N/𝜆 RTTs (again we use the assumption that N is reasonably large), and so sends about 3/4 c2×N/𝜆 packets. The ratio of these is c1/(c2/𝜆) = 𝜆2. Connection 1 sends fraction 𝜆2/(1+𝜆2) of the packets; connection 2 sends fraction 1/(1+𝜆2).

14.3.4   Synchronized-Loss Hypothesis

The synchronized-loss hypothesis is based on the idea that, if the queue is full, late-arriving packets from each connection will find it so, and be dropped. Once the queue becomes full, in other words, it stays full for long enough for each connection to experience a packet loss.

That said, it is certainly possible to come up with hypothetical situations where losses are not synchronized. Recall that a TCP Reno connection’s cwnd is incremented by only 1 each RTT; losses generally occur when this single extra packet generated by the increment to cwnd arrives to find a full queue. Generally speaking, packets are leaving the queue about as fast as they are arriving; actual overfull-queue instants may be rare. It is certainly conceivable that, at least some of the time, one connection would overflow the queue by one packet, and halve its cwnd, in a short enough time interval that the other connection misses the queue-full moment entirely. Alternatively, if queue overflows lead to effectively random selection of lost packets (as would certainly be true for random-drop queuing, and might be true for tail-drop if there were sufficient randomness in packet arrival times), then there is a finite probability that all the lost packets at a given loss event come from the same connection.

The synchronized-loss hypothesis is still valid if either or both connection experiences more than one packet loss, within a single RTT; the hypothesis fails only when one connection experiences no losses.

We will return to possible failure of the synchronized-loss hypothesis in 14.5.2   Unsynchronized TCP Losses. In 16.3   Two TCP Senders Competing we will consider some TCP Reno simulations in which actual measurement does not entirely agree with the synchronized-loss model. Two problems will emerge. The first is that when two connections compete in isolation, a form of synchronization known as phase effects (16.3.4   Phase Effects) can introduce a persistent perhaps-unexpected bias. The second is that the longer-RTT connection often does manage to miss out on the full-queue moment entirely, as discussed above in the second paragraph of this section. This results in a larger cwnd than the synchronized-loss hypothesis would predict.

14.3.5   Loss Synchronization

The synchronized-loss hypothesis assumes all losses are synchronized. There is another side to this phenomenon that is an issue even if only some reasonable fraction of loss events are synchronized: synchronized losses may represent a collective inefficiency in the use of bandwidth. In the immediate aftermath of a synchronized loss, it is very likely that the bottleneck link will go underutilized, as (at least) two connections using it have just cut their sending rate in half. Better utilization would be achieved if the loss events could be staggered, so that at the point when connection 1 experiences a loss, connection 2 is only halfway to its next loss. For an example, see exercise 18.0.

This loss synchronization is a very real effect on the Internet, even if losses are not necessarily all synchronized. A major contributing factor to synchronization is the relatively slow response of all parties involved to packet loss. In the diagram above at 14.3   TCP Fairness with Synchronized Losses, if A increments its cwnd leading to an overflow at R, the A–R link is likely still full of packets, and R’s queue remains full, and so there is a reasonable likelihood that sender B will also experience a loss, even if its cwnd was not particularly high, simply because its packets arrived at the wrong instant. Congestion, unfortunately, takes time to clear.

14.3.6   Extreme RTT Ratios

What happens to TCP fairness if one TCP connection has a 100-fold-larger RTT than another? The short answer is that the shorter connection may get 10,000 times the throughput. The longer answer is that this isn’t quite as easy to set up as one might imagine. For the arguments above, it is necessary for the two connections to have a common bottleneck link:


In the diagram above, the A–C connection wants its cwnd to be about 200 ms × 10 packets/ms = 2,000 packets; it is competing for the R–C link with the B–D connection which is happy with a cwnd of 22. If R’s queue capacity is also about 20, then with most of the bandwidth the B–C connection will experience a loss about every 20 RTTs, which is to say every 22 ms. If the A–C link shares even a modest fraction of those losses, it is indeed in trouble.

However, the A–C cwnd cannot fall below 1.0; to test the 10,000-fold hypothesis taking this constraint into account we would have to scale up the numbers on the B–C link so the transit capacity there was at least 10,000. This would mean a 400 Gbps R–C bandwidth, or else an unrealistically large A–R delay.

As a second issue, realistically the A–C link is much more likely to have its bottleneck somewhere in the middle of its long path. In a typical real scenario along the lines of that diagrammed above, B, C and R are all local to a site, and bandwidth of long-haul paths is almost always less than the local LAN bandwidth within a site. If the A–R path has a 1 packet/ms bottleneck somewhere, then it may be less likely to be as dramatically affected by B–C traffic.

A few actual simulations using the methods of 16.3   Two TCP Senders Competing resulted in an average cwnd for the A–C connection of between 1 and 2, versus a B–C cwnd of 20-25, regardless of whether the two links shared a bottleneck or if the A–C link had its bottleneck somewhere along the A–R path. This may suggest that the A–C connection was indeed saved by the 1.0 cwnd minimum.

14.4   Notions of Fairness


14.4.1   Max-Min Fairness







14.4.2   Proportional Fairness

A bandwidth allocation of rates ⟨r1,r2,…,rN⟩ for N connections satisfies proportional fairness if it is a legal allocation of bandwidth, and for any other allocation ⟨s1,s2,…,sN⟩, the aggregate proportional change satisfies






14.5   TCP Reno loss rate versus cwnd





M = cwndmean = 1.225 p-1/2







14.5.1   Irregular teeth





14.5.2   Unsynchronized TCP Losses

In 14.3.3   TCP RTT bias we considered a model in which all loss events are fully synchronized; that is, whenever the queue becomes full, both TCP Reno connections always experience packet loss. In that model, if RTT2/RTT1 = 𝜆 then cwnd1/cwnd2 = 𝜆 and bandwidth1/bandwidth2 = 𝜆2, where cwnd1 and cwnd2 are the respective average values for cwnd.





and so

losscounti = k2T / (cwndi × RTTi)

Dividing and canceling, we get


We will make use of this in   Relative loss rates.

We can go just a little further with this: let 𝛾 denote the losscount ratio above:

𝛾 = (cwnd2/cwnd1) × (RTT2/RTT1)

Therefore, as RTT2/RTT1 = 𝜆, we must have cwnd2/cwnd1 = 𝛾/𝜆 and thus

bandwidth1/bandwidth2 = (cwnd1/cwnd2) × (RTT2/RTT1) = 𝜆2/𝛾.

Note that if 𝛾=𝜆, that is, if the longer-RTT connection has fewer loss events in exact inverse proportion to the RTT, then bandwidth1/bandwidth2 = 𝜆 = RTT2/RTT1, and also cwnd1/cwnd2 = 1.

14.6   TCP Friendliness





The point of TCP Friendliness is to regulate the number of the non-Reno connection’s outstanding packets in the presence of competition with TCP Reno, so as to achieve a degree of fairness. In the absence of competition, the number of any connection’s outstanding packets will be bounded by the transit capacity plus capacity of the bottleneck queue. Some non-Reno protocols (eg TCP Vegas, 15.6   TCP Vegas, or constant-rate traffic, 14.6.2   RTP) may in the absence of competition have a loss rate of zero, simply because they never overflow the queue.


We will return to TCP Friendliness in the context of general AIMD in 14.7   AIMD Revisited.

14.6.1   TFRC


From RFC 5348:







14.6.2   RTP


Some RTP features include:

  • The receiver returns periodic summaries of loss rates
  • ACKs are relatively infrequent



We will return to RTP in 20.11   Real-time Transport Protocol (RTP).

The UDP-based QUIC transport protocol (11.1.1   QUIC) uses a congestion-control mechanism compatible with Cubic TCP (15.15   TCP CUBIC), which isn’t quite the same as TCP Reno. But QUIC could just as easily have used TFRC to achieve TCP-Reno-friendliness.

14.6.3   DCCP Congestion Control




The Reno-like profile also includes a slow start mechanism.




14.7   AIMD Revisited


Another approach to TCP Friendliness is to retain TCP’s additive-increase, multiplicative-decrease strategy, but to change the numbers. Suppose we denote by AIMD(𝛼,𝛽) the strategy of incrementing the window size by 𝛼 after a window of no losses, and multiplying the window size by (1-𝛽)<1 on loss (so 𝛽=0.1 means the window is reduced by 10%). TCP Reno is thus AIMD(1,0.5).

Any AIMD(𝛼,𝛽) protocol also follows a sawtooth, where the slanted top to the tooth has slope 𝛼. All combinations of 𝛼>0 and 0<𝛽<1 are possible. The dimensions of one tooth of the sawtooth are somewhat constrained by 𝛼 and 𝛽. Let h be the maximum height of the tooth and let w be the width (as measured in RTTs). Then, if the losses occur at regular intervals, the height of the tooth at the left (low) edge is (1-𝛽)h and the total vertical difference is 𝛽h. This vertical difference must also be 𝛼w, and so we get 𝛼w = 𝛽h, or h/w = 𝛼/𝛽; these values are labeled on the rightmost teeth in the diagram below. These equations mean that the proportions of the tooth (h to w) are determined by 𝛼 and 𝛽. Finally, the mean height of the tooth is (1-𝛽/2)h.

We are primarily interested in AIMD(𝛼,𝛽) cases which are TCP Friendly (14.6   TCP Friendliness). TCP friendliness means that an AIMD(𝛼,𝛽) connection with the same loss rate as TCP Reno will have the same mean cwnd. Each tooth of the sawtooth represents one loss. The number of packets sent per tooth is, using h and w as in the previous paragraph, (1-𝛽/2)hw.


The diagram below shows a TCP Reno tooth (blue) together with some unfriendly AIMD(𝛼,𝛽) teeth on the left (red) and two friendly teeth on the right (green), the second friendly tooth is superimposed on the Reno tooth.



In the rightmost green tooth, superimposed on the Reno tooth, we can see that h = (3/2)×w + (𝛼/2)×w. We already know h = (𝛼/𝛽)×w; setting these expressions equal, canceling the w and multiplying by 2 we get (3+𝛼) = 2𝛼/𝛽, or 𝛽 = 2𝛼/(3+𝛼). Solving for 𝛽 we get

𝛼 = 3𝛽/(2-𝛽)

or 𝛼 ≃ 1.5𝛽 for small 𝛽. As the reduction factor 1-𝛽 gets closer to 1, the protocol can remain TCP-friendly by appropriately reducing 𝛼; eg AIMD(1/5, 1/8).


14.7.1   AIMD and Convergence to Fairness

While TCP-friendly AIMD(𝛼,𝛽) protocols will converge to fairness when competing with TCP Reno (with equal RTTs), a consequence of decreasing 𝛽 is that fairness may take longer to arrive; here is an example. We will assume, as above in 14.3.3   TCP RTT bias, that loss events for the two competing connections are synchronized. Recall that for two same-RTT TCP Reno connections (that is, AIMD(𝛼,𝛽) where 𝛽=1/2), if the initial difference in the connections’ respective cwnds is D, then D is reduced by half on each loss event.

Now suppose we have two AIMD(𝛼,𝛽) connections with some other value of 𝛽, and again with a difference D in their cwnd values. The two connections will each increase cwnd by 𝛼 each RTT, and so when losses are not occurring D will remain constant. At loss events, D will be reduced by a factor of 1-𝛽. If 𝛽=1/4, corresponding to 𝛼=3/7, then at each loss event D will be reduced only to 3/4 D, and the “half-life” of D will be almost twice as large. The two connections will still converge to fairness as D→0, but it will take twice as long.

14.8   Active Queue Management

Active Queue Management (AQM) means that routers take some active steps to manage their queues. The primary goal of AQM is to reduce excessive queuing delays; cf 14.8.1   Bufferbloat. A secondary goal is to improve the performance of TCP connections – which constitute the vast majority of Internet traffic – through the router. By signaling to TCP connections that they should reduce cwnd, overall queuing delays are also reduced.


Broadly speaking, the priority queuing and random drop mechanisms (14.1   A First Look At Queuing, above) might be considered forms of AQM, at least if the goal was to manage the overall queue size. So might fair queuing and hierarchical queuing (19   Queuing and Scheduling). The mechanisms most commonly associated with the AQM category, though, are RED, below, and its successors, especially CoDel. For a discussion of the potential benefits of fair queuing to queue management, see 19.6.1   Fair Queuing and Bufferbloat.

14.8.1   Bufferbloat





14.8.2   DECbit





A consequence of this knee-based mechanism is that DECbit shoots for very limited queue utilization, unlike TCP Reno. At a congested router, a DECbit connection would attempt to keep about 1.0 packets in the router’s queue, while a TCP Reno connection might fill the remainder of the queue. Thus, DECbit would in principle compete poorly with any connection where the sender ignored the marked packets and simply tried to keep cwnd as large as possible. As we will see in 15.6   TCP Vegas, TCP Vegas also strives for limited queue utilization; in 16.5   TCP Reno versus TCP Vegas we investigate through simulation how fairly TCP Vegas competes with TCP Reno.

14.8.3   Explicit Congestion Notification (ECN)













14.8.4   RED


RED is, strictly speaking, a queuing discipline in the sense of 19.4   Queuing Disciplines; FIFO is another. It is often more helpful, however, to think of RED as a technique that an otherwise-FIFO router can use to improve the performance of TCP traffic through it.





pactual = pbase / (1 − count×pbase)




14.8.5   ADT



14.8.6   CoDel








For an example application of CoDel, see 19.10.2   Limiting Delay.

14.9   The High-Bandwidth TCP Problem


1 5.5 8.3 0.02
10 55 83 0.0002
100 555 833 2 × 10-6
1000 5555 8333 2 × 10-8
10,000 55555 83333 2 × 10-10



Packet Loss Rate P cwnd RTTs between losses
10-2 12 8
10-3 38 25
10-4 120 80
10-5 379 252
10-6 1,200 800
10-7 3,795 2,530
10-8 12,000 8,000
10-9 37,948 25,298
10-10 120,000 80,000




14.12   Epilog



14.13   Exercises


0.5. In the section 14.2.3   Example 3: competition and queue utilization, we derived the formula

Q = wA + wB − 2d − 2(𝛼dA+𝛽dB)

under the assumption that the bottleneck bandwidth was 1 packet per unit time. Give the formula when the bottleneck bandwidth is r packets per unit time. Hint: the formula above will apply if we measure time in units of 1/r; only the delays d, dA and dB need to be re-scaled to refer to “normal” time. A delay d measured in “normal” time corresponds to a delay dʹ = r×d measured in 1/r units.

1.0. Consider the following network, where the bandwidths marked are all in packets/ms. C is sending to D using sliding windows and A and B are idle.


Suppose the one-way propagation delay on the 100 packet/ms links is 1 ms, and the one-way propagation delay on the R1–R2 link is 2 ms. The RTTnoLoad for the C–D path is thus about 8 ms, for a bandwidth×delay product of 40 packets. If C uses winsize = 50, then the queue at R1 will have size 10.

Now suppose A starts sending to B using sliding windows, also with winsize = 50. What will be the size of the queue at R1?

Hint: by symmetry, the queue will be equally divided between A’s packets and C’s, and A and C will each see a throughput of 2.5 packets/ms. RTTnoLoad, however, does not change. The number of packets in transit for each connection will be 2.5 packets/ms × RTTnoLoad.

2.0. In the previous exercise, give the average number of data packets (not ACKs) in transit on each individual link:

(a).♢ for the original case in which C is the only sender, with winsize = 50 (the only active links here are C–R1, R1–R2 and R2–D).
(b). for the new case in which B is also sending, also with winsize = 50. In this case all links are active.

Each link will also have an equal number of ACK packets in transit in the reverse direction. Hint: since winsize ≥ bandwidth×delay, packets are sent at the bottleneck rate.

2.5.♢ Consider the following network, with links labeled with one-way propagation delays in milliseconds (so, ignoring bandwidth delay, A’s RTTnoLoad is 40 ms and B’s is 20 ms). The bottleneck link is R–D, with a bandwidth of 6 packets/ms.

A────── 15 ──────┐

Initially B sends to D using a winsize of 120, the bandwidth×round-trip-delay product for the B–D path. A then begins sending as well, increasing its winsize until its share of the bandwidth is 2 packets/ms.

What is A’s winsize at this point? How many packets do A and B each have in the queue at R?

It is perhaps easiest to solve this by repeated use of the observation that the number of packets in transit on a connection is always equal to RTTnoLoad times the actual bandwidth received by that connection. The algebraic methods of 14.2.3   Example 3: competition and queue utilization can also be used, but bandwidth there was normalized to 1; all propagation delays given here would therefore need to be multiplied by 6.

3.0. Consider the C–D path from the diagram of 14.2.4   Example 4: cross traffic and RTT variation:


Link numbers are bandwidths in packets/ms. Assume C is the only sender.

(a).♢ Give propagation delays for the links C–R1 and R2–D so that there will be an average of 5 packets in transit on the C–R1 and R2–D links, in each direction, if C uses a winsize sufficient to saturate the bottleneck R1–R2 link.
(b). Give propagation delays for all three links so that, when C uses a winsize equal to the round-trip transit capacity, there are 5 packets each way on the C–R1 link, 10 on the R1–R2 link, and 20 on the R2–D link.

3.5. Suppose we have the network layout below of 14.2.4   Example 4: cross traffic and RTT variation, except that the R1–R2 bandwidth is 6 packets/ms and the R2–R3 bandwidth is 3 pkts/ms. The delays are as shown, making the C–D RTTnoLoad 10 ms and the A–B RTTnoLoad 16 ms. A connects to B and C connects to D.

(a).♢ Find window sizes wA and wC so that the A–B and C–D connections share the bottleneck R1–R2 bandwidth equally, and there is no queue.
(b). Show that increasing each of wA and wC by 30 packets leaves each connection with 30 packets in R1’s queue – so the bandwidth is still shared equally – and none in R2’s. Hint: As in (a), the A–B bandwidth cannot exceed 3 packets/ms, and C’s packets can only accumulate at R1. To show A cannot have less than 50% of the bandwidth, observe that, if this happened, then A can have no queue at R2 (because packets now leave faster than they arrive), and so all of A’s extra packets must also queue at R1.

4.0. Suppose we have the network layout of 3.5 above. Suppose also that the A–B and C–D connections have settled upon window sizes as in 3.5(b), so that each contributes 30 packets to R1’s queue. Each connection thus has 50% of the R1–R2 bandwidth and there is no queue at R2.

… R2 will then be sending 3 packets/ms to R3 and so will have no queue.

Now A’s winsize is incremented by 10, initially, at least, leading to A contributing more than 50% of R1’s queue. When the steady state is reached, how will these extra 10 packets be distributed between R1 and R2? Hint: As A’s winsize increases, A’s overall throughput cannot rise due to the bandwidth restriction of the R2–R3 link.

5.0. Suppose we have the network layout of exercise 3.5, but modified so that the round-trip C–D RTTnoLoad is 5 ms. The round-trip A–B RTTnoLoad may be different.

The R1–R2 bandwidth is 6 packets/ms, so with A idle the C–D throughput is 6 packets/ms.

(a). Suppose that A and C have window sizes such that, with both transmitting, each has 30 packets in the queue at R1. What is C’s winsize? Hint: C’s throughput is now 3 packets/ms.
(b). Now suppose C’s winsize, with A idle, is 60. In this case the C–D transit capacity would be 5 ms × 6 packets/ms = 30 packets, and so C would have 60−30 = 30 packets in R1’s queue. A then begins sending, with a winsize chosen so that A and C’s contributions to R1’s queue are equal; C’s winsize remains at 60. What will be C’s (and thus A’s) queue usage at R1? Hint: find the transit capacity for a throughput of 3 packets/ms.
(c). Suppose the A–B RTTnoLoad is 10 ms. If C’s winsize is 60, find the winsize for A that makes A and C’s contributions to R1’s queue equal.

6.0. One way to address the reduced bandwidth TCP Reno gives to long-RTT connections is for all connections to use an increase increment of RTT2 instead of 1; that is, everyone uses AIMD(RTT2,1/2) instead of AIMD(1,1/2) (or AIMD(k×RTT2,1/2), where k is an arbitrary scaling factor that applies to everyone).

(a). Construct a table in the style of of 14.3.2   Example 3: Longer RTT above, showing the result of two connections using this strategy, where one connection has RTT = 1 and the other has RTT = 2. Start the connections with cwnd=RTT2, and assume a loss occurs when cwnd1 + cwnd2 > 24.
(b). Explain why this strategy might not be desirable if one connection is over a direct LAN with an RTT of 1 ms, while the second connection has a very long path and an RTT of 1.0 sec. (Hint: the cwnd-increment value for the short-RTT connection would have to apply whether or not the long-RTT connection was present.)

7.0. For each value 𝛼 or 𝛽 below, find the other value so that AIMD(𝛼,𝛽) is TCP-friendly.

(a). 𝛽 = 1/5
(b). 𝛽 = 2/9
(c). 𝛼 = 1/5

Then pick the pair that has the smallest 𝛼, and draw a sawtooth diagram that is approximately proportional: 𝛼 should be the slope of the linear increase, and 𝛽 should be the decrease fraction at the end of each tooth.

8.0. Suppose two TCP flows compete. The flows have the same RTT. The first flow uses AIMD(𝛼1,𝛽1) and the second uses AIMD(𝛼2,𝛽2); neither flow is necessarily TCP-Reno-friendly. The two connections, however, compete fairly with one another; that is, they have the same average packet-loss rates. Show that

𝛼1/𝛽1 = (2-𝛽2)/(2-𝛽1) × 𝛼2/𝛽2.

Assume regular losses, and use the methods of 14.7   AIMD Revisited. Hint: first, apply the argument there to show that the two flows’ teeth must have the same width w and same average height. The average height is no longer 3w/2, but can still be expressed in terms of w, 𝛼 and 𝛽. Use a diagram to show that, for any tooth, average_height = h×(1−𝛽/2), with h the right-edge height of the tooth. Then equate the two average heights of the h1/𝛽1 and h2/𝛽2 teeth. Finally, use the 𝛼iw = 𝛽ihi relationships to eliminate h1 and h2.

8.5. Using the result of the previous exercise, show that AIMD(𝛼1,𝛽) is equivalent to (in the sense of competing fairly with) AIMD(𝛼2,0.5), with 𝛼2 = 𝛼1×(2−𝛽)/3𝛽.


10.0. Consider the following three causes of a 1-second network delay between A and B. In all cases, assume ACKs travel instantly from B back to A.

(i) An intermediate router with a 1-second-per-packet bandwidth delay; all other bandwidth delays negligible
(ii) An intermediate link with a 1-second propagation delay; all bandwidth delays negligible
(iii) An intermediate router with a 100-ms-per-packet bandwidth delay, and a steadily replenished queue of 10 packets, from another source (as in the diagram in 14.2.4   Example 4: cross traffic and RTT variation).

(a). Suppose that, in each of these cases, the packet-pair technique (14.2.6   Packet Pairs) is used to measure the bandwidth. Assuming no packet reordering, what is the minimum time interval we could expect in each case?

(b). What would be the corresponding values of the measured bandwidths? (For purposes of bandwidth measurement, you may assume that the “negligible” bandwidth delay in case (ii) is 0.01 sec.)

11.0. Consider again the three-link parking-lot network from 14.4.1   Max-Min Fairness:


12.0. Consider the two-link parking-lot network:

A       B       C
│       │       │





(b). The bottleneck queue capacity is 1000 packets.
(c). The bottleneck queue capacity is 3000 packets.









Derive a formula expressing the average cwnd in terms of the loss rate p. Hint: the exponent for p should be −2/3, versus −1/2 in the formula in 14.5   TCP Reno loss rate versus cwnd.

16.6. Using the TCP assumptions of exercise 16.5 above, cwnd is incremented by about 2t per each RTT. Show that the cwnd increment rule can be expressed as

cwnd += 𝛼cwnd1/2

and find the value of 𝛼.

16.7. Using the same TCP assumptions as in exercise 16.5 above, show that cwnd is still proportional to p-2/3, where p is the loss rate, assuming the following:


(In the previous exercise we assumed, in effect, that T1 = 0 and that cwnd dropped to 0 after each loss event; here we assume multiplicative decrease is in effect with 𝛽=1/2.) The number of packets sent in one tooth is now k×(T3 − T13), and the mean cwnd is this divided by T−T1.





  • total_packets += packets sent in this tooth
  • RTT_intervals += RTT intervals in this tooth






