\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}