\documentclass{article}
\usepackage{lscape}
\input{../6829-preamble}

\renewcommand{\theproblem}{\arabic{problem}}
\renewcommand{\thesubproblem}{\arabic{subproblem}}
\renewcommand{\thesubsubproblem}{\alph{subsubproblem}}

\newcommand{\asn}[1]{AS \#\texttt{#1}}

% Scruntch lists and bibliography
\let \olditemize = \itemize
\renewcommand{\itemize}{\olditemize{}\itemsep=-\parskip}
\let \oldenumerate = \enumerate
\renewcommand{\enumerate}{\oldenumerate{}\itemsep=-\parskip}
\let \oldlist = \list
\renewcommand{\list}[2]{\oldlist{#1}{#2}\itemsep=-\parskip}

\sloppy

\begin{document}
\psetnum{3}
\date{2005/10/14}
\collab{Collaborators: $\set{\mathtt{amdragon}}$}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      \begin{subsubproblem}
        The following table shows the percentage of total bandwidth
        usage that is used by each connection, with connection $i$
        having $0.5i$ delay.

        \begin{center}
          \begin{tabular}{rr|cccc|}
            \multicolumn{6}{c}{\textbf{Connection}} \\
            & & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\
            \hline
            & \textbf{2} & 62\% & 38\% & & \\
            \textbf{\# Connections}& \textbf{3} & 57\% & 25\% & 17\% & \\
            & \textbf{4} & 54\%  & 26\% & 12\% & 8\%
          \end{tabular}
        \end{center}
      \end{subsubproblem}

      \begin{subsubproblem}
        \-\\
        \begin{center}
          \input{figures/1.1.2-n2}\\
          \input{figures/1.1.2-n3}\\
          \input{figures/1.1.2-n4}        
        \end{center}
      \end{subsubproblem}

      \begin{subsubproblem}
        \-\\
        \begin{center}
          \input{figures/1.1.3}
        \end{center}
        We can see that as the RTT increases, the throughput
        decreases.
      \end{subsubproblem}
    \end{subproblem}

    \begin{subproblem}
      \begin{subsubproblem}
        The following table shows the percentage of total bandwidth
        usage that is used by each connection, with connection $i$
        having $0.05i$ loss.

        \begin{center}
          \begin{tabular}{rr|cccc|}
            \multicolumn{6}{c}{\textbf{Connection}} \\
            & & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\
            \hline
            & \textbf{2} & 63\% & 78\% & & \\
            \textbf{\# Connections} & \textbf{3} & 55\% & 32\% & 13\% & \\
            & \textbf{4} & 52\%  & 23\% & 16\% & 9\%
          \end{tabular}
        \end{center}
      \end{subsubproblem}

      \begin{subsubproblem}
        \-\\
        \begin{center}
          \input{figures/1.2.2-n2}\\
          \input{figures/1.2.2-n3}\\
          \input{figures/1.2.2-n4}        
        \end{center}
      \end{subsubproblem}

      \begin{subsubproblem}
        \-\\
        \begin{center}
          \input{figures/1.2.3}
        \end{center}
        We can see that as the loss rate increases, the throughput
        decreases.
      \end{subsubproblem}
    \end{subproblem}    
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      For each of these three configurations, graphs of the throughput
      along each path for different parameter values follow. The
      shared case scales the throughput by $\nicefrac14$ to show the
      average throughput on each connection.
      
      \input{figures/p21-a}\\
      \input{figures/p21-b}\\
      \input{figures/p21-c}
    \end{subproblem}

    \begin{subproblem}
      
    \end{subproblem}
    \begin{landscape}
      \begin{subsubproblem}
        The following four graphs show the evolution of the
        \texttt{cwnd} size for configuration a, with varying loss rates.
        \vspace{2em}
        
        \begin{center}          
          \begin{tabular}{|cc|}
            \hline
            \input{figures/p22-a-00} &
            \input{figures/p22-a-05} \\
            \input{figures/p22-a-10} &
            \input{figures/p22-a-15} \\
            \hline
          \end{tabular}
        \end{center}
      \end{subsubproblem}
    \end{landscape}

    \begin{landscape}
      \begin{subsubproblem}
        The following four graphs show the evolution of the
        \texttt{cwnd} size for configuration b, with varying delays.
        \vspace{2em}
        
        \begin{center}          
          \begin{tabular}{|cc|}
            \hline
            \input{figures/p22-b-00} &
            \input{figures/p22-b-05} \\
            \input{figures/p22-b-10} &
            \input{figures/p22-b-15} \\
            \hline
          \end{tabular}
        \end{center}
      \end{subsubproblem}
    \end{landscape}

    \begin{landscape}
      \begin{subsubproblem}
        The following four graphs show the evolution of the
        \texttt{cwnd} size for configuration c, with varying loss
        rates.
        \vspace{2em}
        
        \begin{center}          
          \begin{tabular}{|cc|}
            \hline
            \input{figures/p22-c-00} &
            \input{figures/p22-c-05} \\
            \input{figures/p22-c-10} &
            \input{figures/p22-c-15} \\
            \hline
          \end{tabular}
        \end{center}
      \end{subsubproblem}
    \end{landscape}

    \begin{subproblem}
      The current design of TCP uses a shared window. In all of these
      multihoming configurations, we see that the shared window case
      gives lower average throughput than even the slowest of the
      paths would with a separate window. This suggests that
      performance of TCP could be improved if each link could be given
      a separate window.
    \end{subproblem}

    \begin{subproblem}
      We see that fast retransmissions improve the performance of
      \texttt{aimd}, and reduce the performance of
      \texttt{shared}. This is because fast retransmit can function
      normally on the \texttt{aimd} case, and improve performance just
      as it would for a single-homed link. In the \texttt{shared}
      case, fast retransit is not useful: the shared connection window
      sees many out of order ACKs since packets are reordered by the
      different delays on the multihomed links, and so packets are
      retransmitted and cwnd is decreased unnecessarily. This does not
      occur on the \texttt{aimd} case because each link does not
      adjust cwnd in response to ACKs from other links.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      The TCP congestion window over time forms a sawtooth plot in the
      steady state: it increases additively until it reaches a maximum
      $W_{\max}$ and a packet is dropped; then it will drop to
      $\frac{W_{\max}}{2}$ and begin increasing again. Packets are
      first dropped when both the available bandwidth and buffer space
      are exhausted. $P$ bytes per RTT can be transmitted over the
      link, and $B$ bytes can be stored in the buffer, so $W_{\max} =
      P + B$. This is $2P$ if $B = P$. So the window size is always at
      least $P$, and so at least $P$ packets are transmitted each
      RTT: this is full link utilization by definition.

      For 40 Gb/s and 100 ms, this is 4 gigabits, or half a gigabyte
      of buffer memory.
    \end{subproblem}

    \begin{subproblem}
      If negligible buffer space is available, packets will be dropped
      as soon as the window size exceeds $P$. So the window size will
      oscillate between $\nicefrac{P}2$ and $P$; thus, the average
      window size is $\nicefrac{3}{4}P$, and so the average link
      utilization is $\nicefrac{3}{4}$.
    \end{subproblem}

    \begin{subproblem}
      Let $B = rP$. Then by the reasoning of problem 3.1, the TCP
      window size will oscillate between $P+B = P(1+r)$ and half this
      amount. The link utilization will be $\frac{1}{P}$ the window
      size, but not greater than 1. We can consider this
      geometrically:

      \vspace{3in}

      The total area is the area of the triangle from $0$ to $\left(\frac{2}{2+r}
        -1\right)$, the area of the rectangle below it, and the area
      of the rectangle that represents the region truncated at $1$:
      \begin{align*}
        U(r) &=
        \frac{\left(1 - \frac{1+r}{2}\right)\left(\frac{2}{1+r}
            -1\right)}{2} + \left(\frac{2}{1+x} -
          1\right)\left(\frac{1+r}{2}\right) + \left(2 -
          \frac{2}{1+r}\right) \\
        &= \frac{5}{4} + \frac{r}{4} - \frac{r-1}{2} - \frac{1}{r+1}
      \end{align*}
    \end{subproblem}

    \begin{subproblem}
      $U(r)$ is plotted below:
      
      \input{figures/3.4}
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      The fairness controller attempts to make changes proportional to
      the expected packet rate; since we are reporting the throughput
      directly, this is the throughput reported by the sender. So
      lying about the RTT will have no effect on the fairness
      controller because it allocates proportional to feedback.

      (In XCP as in the paper, with \texttt{cwnd} as a header
      parameter, lying about the RTT would cause extra positive
      feedback to be applied, but not affect negative feedback: 
       rather than the congestion window, If
      the link is underutilized and positive feedback is being
      applied, sending a high RTT would cause extra positive feedback
      to be applied to the sender because $rtt^2$ appears in the
      numerator, and only one factor of $rtt$ is canceled by the
      scaling by $\frac{true\_RTT}{declared\_RTT}$. The negative
      feedback term has only one $rtt$ factor in the numerator, so
      this is canceled, and thus lying has no effect.)
      
      The efficiency controller sets its aggregate feedback
      proportional to the average RTT multiplied by the amount of
      spare bandwidth. So if a sender sends a high RTT, it may
      increase the average RTT enough to cause the efficiency control
      to be underdamped and oscillate. If it sends a low RTT, it may
      decrease the average RTT enough to cause the efficiency
      controller's adjustments to be too small, and converge too
      slowly to be useful.
    \end{subproblem}

    \begin{subproblem}
      The fairness controller makes positive changes equally to all
      flows, and negative changes inversely proportional to each
      link's throughput. So if the link is underutilized and positive
      feedback is being applied, lying about the throughput has no
      effect; if the link is congested and negative feedback is being
      applied, giving a low throughput value would cause the link to
      receive less feedback and thus gain and advantage.
      
      The utilization controller does not take congestion windows into
      account, so lying about this would not affect link utilization.
    \end{subproblem}
  \end{problem}
\end{pset}
\end{document}