1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
\documentclass[a4paper,9pt]{article}
\author{Camil Staps\\\small{s4498062}}
\title{Networking\\\large{Assignment 4}}
\date{April 13, 2016}
\usepackage{polyglossia}
\setmainlanguage{english}
\usepackage{geometry}
\usepackage{enumitem}
\setenumerate{label=\alph*)}
\usepackage{amsmath}
\begin{document}
\maketitle
\section{Reliable Data Transfer}
\begin{enumerate}
\item \begin{description}
\item[GBN]
A sends first 5, then (timeout) 4 re-transmits, so in total 9 segments.\\
B sends an ACK for 1, then 3 duplicate ACKs, then 4 for segments 2, 3, 4, 5. So the sequence numbers are: 1, 1, 1, 1, 2, 3, 4, 5: 8 in total.
\item[SR]
A sends first 5, then (timeout) 1 re-transmit, so in total 6 segments.\\
B sends an ACK for 1, 3, 4, 5 and finally 2: 5 ACKs.
\item[TCP]
A sends first 5, then (three duplicate ACKs) 4 re-transmits, so in total 9 segments.\\
B sends an ACK for 1, then 3 duplicate ACKs, then 4 for the last segments: 2, 2, 2, 2, 3, 4, 5, 6: 8 in total.
\end{description}
\item Both GBN and SR wait for the timeout to occur. TCP recognises three duplicate ACKs, therefore doesn't need to wait for the timeout, and will be the fastest.
\end{enumerate}
\section{TCP State Machine}
\begin{enumerate}
\item From top to bottom, left to right:
\begingroup\sffamily
\begin{itemize}[itemsep=0pt]
\item closed
\item connect/S(50,0)
\item SYN\_SENT
\item SA(80,51)/A(51,81)
\item FA(81,51)/A(51,82)
\item established
\item close/FA(51,81)
\item close\_wait
\item fin\_wait2
\item close/FA(51,82)
\item FA(81,52)/A(51,82)
\item last\_ack
\item time\_wait
\end{itemize}
\endgroup
\item Input: RST(81,52).
\item \texttt{time\_wait}: according to RFC793, p. 77, the FSM should enter the \texttt{closed} state after the time-wait timeout.
\end{enumerate}
\section{Round-Trip Time Estimation}
\begin{enumerate}
\item Let $\mathit{EtimatedRTT}_i$ be the estimated RTT $i$ measures before `now', i.e. we want a formula for $\mathit{EstimatedRTT}_0$. Furthermore, let $E$ stand for $\mathit{EstimatedRTT}$ and $S$ for $\mathit{SampleRTT}$. Then:
\begin{align*}
E &= E_0 \\
&= (1-\alpha)\cdot E_1 + \alpha\cdot S_1 \\
&= (1-\alpha)\left((1-\alpha)\cdot E_2 + \alpha\cdot S_2\right) + \alpha\cdot S_1 \\
&= (1-\alpha)^2E_2 + \left(\alpha-\alpha^2\right)S_2 + \alpha\cdot S_1 \\
&= (1-\alpha)^2((1-\alpha)\cdot E_3+\alpha\cdot S_3) + (1-\alpha)\cdot\alpha\cdot S_2 + \alpha\cdot S_1 \\
&= (1-\alpha)^3E_3 + (1-\alpha)^2\cdot\alpha\cdot S_3 + (1-\alpha)\cdot\alpha\cdot S_2 + \alpha\cdot S_1 \\
&= (1-\alpha)^3((1-\alpha)\cdot E_4+\alpha\cdot S_4) + (1-\alpha)^2\cdot\alpha\cdot S_3 + (1-\alpha)\cdot\alpha\cdot S_2 + \alpha\cdot S_1 \\
&= (1-\alpha)^4E_4 + (1-\alpha)^3\cdot\alpha\cdot S_4 + (1-\alpha)^2\cdot\alpha\cdot S_3 + (1-\alpha)\cdot\alpha\cdot S_2 + \alpha\cdot S_1. \\
\end{align*}
\item $$E = (1-\alpha)^nE_n + \sum_{i=0}^{n-1}\left((1-\alpha)^i\cdot\alpha\cdot S_{i+1}\right).$$
\item Since $0\le 1-\alpha < 1$, we may discard the first term. We may update the formula by posing a hard limit (say, $k$) instead of $n-1$ on the sum, to approximate the RTT. The weight of the terms of the sum is exponentially dependent on its variable $i$, which is why this is called an exponential moving average.
\end{enumerate}
\section{Congestion window and throughput}
\begin{enumerate}
\item Since the receive buffer is larger than the congestion window, the latter is the factor here. In 150ms we can send $10Mb \cdot 0.15 = 1.5Mb$, i.e. $1000$ segments. Therefore the maximum window size is $1000$ segments.
\item I'm assuming that the window size when loss occurs is $W=1000$. After loss, the window drops to half ($500$) and then linearly increases. This gives an average window size of $750$ segments.
The average throughput is then $3W / 4RTT = 3000 / 600ms = 5$ segments per $ms$, or $7,500,000 bps$.
\item We need to go back from 500 to 1000 segments. Every RTT, the congestion window is increased by one segment, so this takes $500\cdot150ms=75s$.
\end{enumerate}
\section{Congestion control evolution}
\begin{enumerate}
\item Reno: after a reset (e.g. 9) the congestion window increases linearly, while Tahoe would reset to slow-start state (this would give an exponential pattern).
\item $\{[1,4]\}$: we can see the exponential pattern.
\item $\{[4,8], [9,13], [14,15]\}$: the congestion window increases but only linearly.
\item A timeout: if an ACK times out, slow start is used as with Tahoe. The congestion window is more than halved here, so this is the start of slow start.
\item 8: when the congestion window reaches this size, congestion avoidance is activated (note the change from exponentially to linearly increasing).
\item 9: this is the new congestion window size in the 9th round.
\item 4: we're following the same pattern as on $[1,4]$ because we're in slow start mode (see (d)).
\item The new congestion window size is then again 1, because it is halved. The new \texttt{sshthresh} is then also 1, because it is set to the same value.
\item The 5th: in the first round, 1 segment is sent and received; in the second round 2 segments, in the third round 4, and in the 4th round 8. This gives $1+2+4+8=15<17$ segments sent after four rounds. In the fifth round, 9 segments will be successfully sent, so the 17th segment is among those.
\end{enumerate}
\end{document}
|
