diff options
| -rw-r--r-- | assignment4.tex | 116 |
1 files changed, 116 insertions, 0 deletions
diff --git a/assignment4.tex b/assignment4.tex new file mode 100644 index 0000000..33be394 --- /dev/null +++ b/assignment4.tex @@ -0,0 +1,116 @@ +\documentclass[a4paper,9pt]{article} + +\author{Camil Staps\\\small{s4498062}} +\title{Networking\\\large{Assignment 4}} + +\usepackage{polyglossia} +\setmainlanguage{english} +\usepackage{geometry} +\usepackage[hidelinks]{hyperref} +\usepackage{caption} +\usepackage{enumitem} +\setenumerate{label=\alph*)} +\usepackage{amsmath} + +\usepackage{minted} +\setminted{fontsize=\scriptsize} + +\usepackage{subcaption} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,shapes} +% underline to right side; see http://tex.stackexchange.com/a/137505/23992 +\usepackage[normalem]{ulem} + +\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} + |