\section{TCP Congestion Control}

% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Idea
      \begin{sitem}
         \item assumes best-effort network (FIFO or FQ routers)
         \item each source determines network capacity for itself
         \item uses implicit feedback
         \item ACKs pace transmission ({\it self-clocking})
      \end{sitem}
      \item Challenge
      \begin{sitem}
         \item determining the available capacity in the first place
         \item adjusting to changes in the available capacity
      \end{sitem}
   \end{sitem}        
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Additive Increase/Multiplicative Decrease}

   \begin{sitem}
      \item Objective: adjust to changes in the available capacity

      \item New state variable per connection: {\tt CongestionWindow}
      \begin{sitem}
         \item limits how much data source has in transit
      \end{sitem}
      \begin{verbatim}
MaxWin = MIN(CongestionWindow, AdvertisedWindow)
EffWin = MaxWin - (LastByteSent - LastByteAcked)
      \end{verbatim}

      \item Idea:
      \begin{sitem}
         \item increase {\tt CongestionWindow} when congestion goes down
         \item decrease {\tt CongestionWindow} when congestion goes up
      \end{sitem}

      \item Question: how does the source determine whether or not
            the network is congested?

      \item Answer: a timeout occurs
      \begin{sitem}
         \item timeout signals that a packet was lost
         \item packets are seldom lost due to transmission error
         \item lost packet implies congestion
      \end{sitem}
   \end{sitem}        
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Algorithm:
      \begin{sitem}
         \item increment {\tt CongestionWindow} by one packet per RTT
	       ({\it linear increase})
         \item divide {\tt CongestionWindow} by two whenever a timeout
               occurs ({\it multiplicative decrease})
      \end{sitem}    

      \pichere{linear.eps,height=3.5in}

      \item In practice: increment a little for each ACK

      \begin{verbatim}
Increment = (MSS * MSS)/CongestionWindow
CongestionWindow += Increment
      \end{verbatim}
   \end{sitem}        
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Example trace: sawtooth behavior
      \pichere{sawtooth.eps,height=1.75in}
   \end{sitem}        
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Slow Start}

   \begin{sitem}
      \item Objective: determine the available capacity in the first place

      \item Idea:
      \begin{sitem}
         \item begin with {\tt CongestionWindow} = 1 packet
         \item double {\tt CongestionWindow} each RTT (increment by 1 packet
               for each ACK)
      \end{sitem}

      \pichere{exponential.eps,height=3.5in}

      \item Exponential growth, but slower than all in one blast
 
      \item Used...
      \begin{sitem}
         \item when first starting connection
         \item when connection goes dead waiting for a timeout
      \end{sitem}
   \end{sitem}        
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Example trace

      \pichere{trace1.eps,height=1.75in}

      \item Problem: lose up to half a {\tt CongestionWindow}'s worth of data
   \end{sitem}        
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Fast Retransmit and Fast Recovery}

   \begin{sitem}
      \item Problem: coarse-grain TCP timeouts lead to idle periods

      \item Fast retransmit: use duplicate ACKs to trigger retransmission

      \pichere{tcp_fast.eps,height=2.75in}

      \item Results

      \pichere{trace2.eps,height=1.75in}

      \item Fast recovery: remove the slow start phase; go directly to
            half the last successful {\tt CongestionWindow}
   \end{sitem}        
\end{slide}
