TCP and congestion control¶
Warning
This is an unpolished draft of the second edition of this ebook. If you find any error or have suggestions to improve the text, please create an issue via https://github.com/obonaventure/cnp3/issues?milestone=2
A complete TCP implementation includes several mechanisms that interact together : reliable transfert that uses acknowledgements, timers, retransmissions, flow control that relies on sliding windows and congestion control. To understand the interactions between these different mechanisms, we analyse how TCP reacts in various situations where some of these mechanisms are disabled. Then we progressively add new mechanisms to end the exercises with a fairly complete TCP implementation.
Unless otherwise noted, we assume for the exercices in this section that the following conditions hold.
- the sender/receiver performs a single send(3) of x bytes
- the round-trip-time is fixed and does not change during the lifetime of the TCP connection. We assume a fixed value of 100 milliseconds for the rtt and a fixed value of 200 milliseconds for the retransmission timer.
- the delay required to transmit a single TCP segment containing MSS bytes is small and set to 1 milliseconds, independently of the MSS size
- the transmission delay for a TCP ack is negligible
- the initial value of the congestion window is one MSS-sized segment
- the value of the duplicate ack threshold is fixed and set to 3
- TCP always acks each received segment
Congestion control¶
- To understand the operation of the TCP congestion control, it is often useful to write time-sequence diagrams for different scenarios. The example below shows the operation of the TCP congestion control scheme in a very simple scenario. The initial congestion window (cwnd) is set to 1000 bytes and the receive window (rwin) advertised by the receiver (supposed constant for the entire connection) is set to 2000 bytes. The slow-start threshold (ssthresh) is set to 64000 bytes.
- Can you explain why the sender only sends one segment first and then two successive segments (the delay between the two segments on the figure is due to graphical reasons) ?
- Can you explain why the congestion window is increased after the reception of the first ack ?
- How long does it take for the sender to deliver 3 KBytes to the receiver ?
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$25 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=2000 \\
cwnd=1000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(3k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,8) node [midway, fill=white] {0:1000};
\draw[black,thick, ->] (7,8) -- (3,7) node [midway, fill=white] {ack 1000};
\node [state] at (0,6) {\begin{small}\begin{tabular}{l}
rwin=2000 \\
cwnd=2000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[black,thick, ->] (3,7) -- (7,6) node [midway, fill=white] {1000:2000};
\draw[black,thick, ->] (3,6.5) -- (7,5.5) node [midway, fill=white] {2000:3000};
\draw[black,thick, ->] (7,6) -- (3,5) node [midway, fill=white] {ack 2000};
\draw[black,thick, ->] (7,5.5) -- (3,4.5) node [midway, fill=white] {ack 3000};](_images/tikz-d915172c069f26c4712af625cf2bc432b297ee2b.png)
- Same question as above but now with a small variation. Recent TCP implementations use a large initial value for the congestion window. Draw the time-sequence diagram that corresponds to an initial value of 10000 bytes for this congestion window.
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$25 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=2000 \\
cwnd=10000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(3k)} -- (3,9);](_images/tikz-a393cf81353585edefbfc9b74757e05c18aa6c69.png)
- Same question as the first one, but consider that the MSS on the sender is set to 500 bytes. How does this modification affect the entire delay ?
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$25 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=2000 \\
cwnd=1000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(10k)} -- (3,9);](_images/tikz-346e977043bc07f6a3f9abeb8638f277713e0e92.png)
- Assuming that there are no losses and that there is no congestion in the network. If the sender writes x bytes on a newly established TCP connection, derive a formula that computes the minimum time required to deliver all these x bytes to the receiver. For the derivation of this formula, assume that x is a multiple of the maximum segment size and that the receive window and the slow-start threshold are larger than x.
- In question 1, we assumed that the receiver acknowledged every segment received from the sender. In practice, many deployed TCP implementations use delayed acknowledgements. Assuming a delayed acknowledgement timer of 50 milliseconds, modify the time-sequence diagram below to reflect the impact of these delayed acknowledgement. Does their usage decreases or increased the transmission delay ?
- The congestion control scheme in a TCP implementation can operate in slow-start or in congestion avoidance mode. For this, the implementation compares the current value of the congestion window with the slow-start threshold.
Among the TCP states shown below, which is the one that corresponds to a connection operating in congestion avoidance ?
cwnd=64000 and ssthresh=64000
cwnd=4000 and ssthresh=2000
cwnd=4000 and ssthresh=48000
cwnd=2000 and ssthresh=4000
cwnd=4000 and ssthresh=8000
- Let us now explore the impact of congestion on the slow-start and congestion avoidance mechanisms. Consider the scenario below. For graphical reasons, it is not possible anymore to show information about the segments on the graph, but you can easily infer them.
- Redraw the same figure assuming that the second segment that was delivered by the sender in the figure experienced congestion. In a network that uses Explicit Congestion Notification, this segment would be marked by routers and the receiver would return the congestion mark in the corresponding acknowledgement.
- Same question, but assume now that the fourth segment delivered by the sender experienced congestion (but was not discarded).
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=4000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(10k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[black,thick, ->] (3,8.7) -- (7,7.45);
\draw[black,thick, ->] (3,8.4) -- (7,7.15);
\draw[black,thick, ->] (3,8.1) -- (7,6.85);
\draw[black,thick, ->] (7,7.75) -- (3,6.5);
\draw[black,thick, ->] (7,7.45) -- (3,6.2);
\draw[black,thick, ->] (7,7.15) -- (3,5.9);
\draw[black,thick, ->] (7,6.855) -- (3,5.6);
\node [state] at (0,6) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=8000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[black,thick, ->] (3,6.5) -- (7,5.25);
\draw[black,thick, ->] (3,6.25) -- (7,5);
\draw[black,thick, ->] (3,6) -- (7,4.75);
\draw[black,thick, ->] (3,5.75) -- (7,4.5);
\draw[black,thick, ->] (3,5.5) -- (7,4.25);
\draw[black,thick, ->] (3,5.25) -- (7,4);
\draw[black,thick, ->] (7,5.25) -- (3,4);
\draw[black,thick, ->] (7,5) -- (3,3.75);
\draw[black,thick, ->] (7,4.75) -- (3,3.5);
\draw[black,thick, ->] (7,4.5) -- (3,3.25);
\draw[black,thick, ->] (7,4.25) -- (3,3);
\draw[black,thick, ->] (7,4) -- (3,2.75);
\node [state] at (0,2.5) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=16000 \\
ssthresh=64000\\
\end{tabular}\end{small}};](_images/tikz-efcf7be7f8005c1d8bcc098f591036db970e0c36.png)
- A TCP has been active for some time and reached a congestion window of 8000 bytes (its initial value was 1000 bytes). At this point, there is no unacknowledged data and the application running on the sender tries to send 2000 bytes of data.
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=8000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(2k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[black,thick, ->] (3,8.7) -- (7,7.45);](_images/tikz-6c0693e5b5f5b64c1cb05bdfaa6922fdcdfcb9d8.png)
None of these two segments reaches the receiver. Which of the graphs below corresponds to a correct reaction of the TCP stack running on the sender ?
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=8000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(2k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[black,thick, ->] (3,8.7) -- (7,7.45);
%timeout
\draw[blue, <->] (2,9) -- (2,4) node [midway, fill=white] {timeout};
\node [state] at (0,3) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=2000 \\
ssthresh=32000\\
\end{tabular}\end{small}};
\draw[black,thick, ->] (3,4) -- (7,2.75);
\draw[black,thick, ->] (3,3.75) -- (7,2.5);
\draw[black,thick, ->] (7,2.75) -- (3,1.5);
\draw[black,thick, ->] (7,2.5) -- (3,1.25);](_images/tikz-901e76e3c6d49e5850f3bf5782054926f4c86ade.png)
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=8000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(2k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[black,thick, ->] (3,8.7) -- (7,7.45);
%timeout
\draw[blue, <->] (2,9) -- (2,4) node [midway, fill=white] {timeout};
\node [state] at (0,3) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=2000 \\
ssthresh=4000\\
\end{tabular}\end{small}};
\draw[black,thick, ->] (3,4) -- (7,2.75);
\draw[black,thick, ->] (3,3.75) -- (7,2.5);
\draw[black,thick, ->] (7,2.75) -- (3,1.5);
\draw[black,thick, ->] (7,2.5) -- (3,1.25);](_images/tikz-d469272480251d670d52f36487e01b1c38564708.png)
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=8000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(2k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[black,thick, ->] (3,8.7) -- (7,7.45);
%timeout
\draw[blue, <->] (2,9) -- (2,4) node [midway, fill=white] {timeout};
\node [state] at (0,3) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=2000 \\
ssthresh=2000\\
\end{tabular}\end{small}};
\draw[black,thick, ->] (3,4) -- (7,2.75);
\draw[black,thick, ->] (3,3.75) -- (7,2.5);
\draw[black,thick, ->] (7,2.75) -- (3,1.5);
\draw[black,thick, ->] (7,2.5) -- (3,1.25);](_images/tikz-bcff2580d10255de94b3a610d2d1f13aa2f9d02a.png)
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=8000 \\
ssthresh=64000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(2k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[black,thick, ->] (3,8.7) -- (7,7.45);
%timeout
\draw[blue, <->] (2,9) -- (2,4) node [midway, fill=white] {timeout};
\node [state] at (0,3) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=1000 \\
ssthresh=4000\\
\end{tabular}\end{small}};
\draw[black,thick, ->] (3,4) -- (7,2.75);
\draw[black,thick, ->] (7,2.75) -- (3,1.5);
\draw[black,thick, ->] (3,1.5) -- (7,0.25);](_images/tikz-4498cc5a22c8fc34f1ea2b5d6ccecbc2819bea61.png)
- A TCP connection has been active for some time and has reached a congestion window of 4000 bytes. Four segments are sent, but the second (shown in red in the figure) is corrupted.
![\colorlet{lightgray}{black!20}
\tikzstyle{arrow} = [thick,->,>=stealth,font=\tiny]
\draw[step=0.5cm,lightgray,very thin] (0,0) grid (10,10);
\draw[very thick, <->] (9.7,10) -- (9.7,9.5) node [anchor=west, fill=white] {$20 msec$};
\tikzset{state/.style={rectangle, dashed, draw, fill=white} }
\node [black, fill=white] at (3,10) {Sender};
\node [black, fill=white] at (7,10) {Receiver};
\draw[very thick,->] (3,9.5) -- (3,0.5);
\draw[very thick,->] (7,9.5) -- (7,0.5);
% initial state
\node [state] at (0,11) {\begin{small}\begin{tabular}{l}
rwin=64000 \\
cwnd=4000 \\
ssthresh=4000\\
\end{tabular}\end{small}};
\draw[red, ->] (0,9) node [anchor=north, fill=white] {send(10k)} -- (3,9);
\draw[black,thick, ->] (3,9) -- (7,7.75);
\draw[red,thick, dashed, ->] (3,8.7) -- (7,7.45);
\draw[black,thick, ->] (3,8.4) -- (7,7.15);
\draw[black,thick, ->] (3,8.1) -- (7,6.85);
\draw[black,thick, ->] (7,7.75) -- (3,6.5);
\draw[black,thick, ->] (7,7.15) -- (3,5.9);
\draw[black,thick, ->] (7,6.855) -- (3,5.6);](_images/tikz-021209435ef945b83f9c765804de7e558eacd9dc.png)
What is the new state of the TCP connection upon reception of the acknowledgements for the first, third and fourth segments ?
- Upon reception of the first acknowledgement, cwnd is set to 4250 bytes and ssthresh is unchanged
- Upon reception of the third acknowledgement, cwnd and ssthresh are unchanged
- Upon reception of the fourth acknowledgement, cwnd and ssthresh are unchanged
- Upon reception of the first acknowledgement, cwnd is set to 4250 bytes and ssthresh is unchanged
- Upon reception of the third acknowledgement, cwnd is set to 2225 bytes and ssthresh is set to 2000 bytes
- Upon reception of the fourth acknowledgement, cwnd and ssthresh are unchanged
- Upon reception of the first acknowledgement, cwnd is set to 5000 bytes and ssthresh is unchanged
- Upon reception of the third acknowledgement, cwnd is set to 6000 bytes and ssthresh is unchanged
- Upon reception of the fourth acknowledgement, cwnd is set to 7000 bytes and ssthresh is unchanged
- Upon reception of the first acknowledgement, cwnd is set to 4250 bytes and ssthresh is unchanged
- Upon reception of the third acknowledgement, cwnd is set to 4485 bytes and ssthresh is unchanged
- Upon reception of the fourth acknowledgement, cwnd is set to 4707 bytes and ssthresh is unchanged
- Draw the complete time-sequence diagram for the scenario used in question 9.