\section{Congestion Avoidance Mechanisms}

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

   \begin{sitem}
      \item TCP's strategy
      \begin{sitem}
         \item to control congestion once it happens
         \item to repeatedly increase load in an effort to find the point
               at which congestion occurs, and then back off
      \end{sitem}
      \item Alternative strategy
      \begin{sitem}
         \item predict when congestion is about to happen, and reduce
               the rate at which hosts send data just before packets start
               being discarded
         \item we call this congestion {\it avoidance}, to distinguish it
               from congestion {\it control}
      \end{sitem}
      \item Two possibilities
      \begin{sitem}
         \item router-centric: DECbit and RED Gateways
         \item host-centric: TCP Vegas
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{DECbit}

   \begin{sitem}
      \item Add binary congestion bit to each packet header

      \item Router
      \begin{sitem}
         \item monitors average queue length over last busy+idle cycle
         \pichere{decbit.eps,height=2in}
         \item set congestion bit if average queue length greater
               than 1 when packet arrives
         \item attempts to balance throughput against delay
      \end{sitem}

      \item End Hosts
      \begin{sitem}
         \item destination echos bit back to source
         \item source records how many packets resulted in set bit
         \item if less than 50\% of last window's worth had bit set,
               then increase {\tt CongestionWindow} by 1 packet
         \item if 50\% or more of last window's worth had bit set,
               then decrease {\tt CongestionWindow} by 0.875 times
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Random Early Detection (RED) Gateways}

   \begin{sitem}
      \item Notification is implicit
      \begin{sitem}
         \item just drop the packet (TCP will timeout)
         \item could make explicit by marking the packet
      \end{sitem}

      \item Early random drop
      \begin{sitem}
         \item rather than wait for queue to become full, drop each arriving
               packet with some {\it drop probability} whenever the queue 
               length exceeds some {\it drop level}
      \end{sitem}

      \item RED: fills in the details
      \begin{sitem}
         \item compute average queue length
         \begin{verbatim}
   AvgLen = (1 - Weight) * AvgLen
            + Weight * SampleLen
         \end{verbatim}
         \begin{sitem}
            \item 0 $<$ {\tt Weight} $<$ 1 (usually 0.002)
            \item {\tt SampleLen} is queue length each time a packet arrives
         \end{sitem}
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \begin{sitem}
         \item two queue length thresholds
         \begin{verbatim}
   if AvgLen <= MinThreshold then
      enqueue the packet
   if MinThreshold < AvgLen < MaxThreshold
      calculate probability P
      drop arriving packet with probability P
   if MaxThreshold <= AvgLen
      drop arriving packet
         \end{verbatim}

         \pichere{red.eps,height=1.5in}

         \item probability P
         \begin{sitem}
            \item not fixed
            \item function of {\tt AvgLen} and how long since last drop 
                  ({\tt count}) keeps track of new packets that have been 
                  queued while {\tt AvgLen} has been between the two thresholds
         \end{sitem}
         \begin{verbatim}
      TempP = MaxP * (AvgLen - MinThreshold) 
              / (MaxThreshold - MinThreshold)
      P = TempP/(1 - count * TempP)
         \end{verbatim}
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Notes
      \begin{sitem}
         \item probability of dropping a particular flow's
               packet(s) is roughly proportional to the share
               of the bandwidth that flow is currently getting
         \bigskip
         \item {\tt MaxP} is typically set to 0.02, meaning that when the
               average queue size is halfway between the two thresholds, 
               the gateway drops roughly one out of 50 packets.
         \bigskip
         \item if traffic is bursty, then {\tt MinThreshold} should be
               sufficiently large to allow link utilization to be
               maintained at an acceptably high level
         \bigskip
         \item difference between two thresholds should be larger than
               the typical increase in the calculated average queue length
               in one RTT; setting {\tt MaxThreshold} to twice 
               {\tt MinThreshold} is reasonable for traffic on today's Internet
         \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}
 
   \subsection{TCP Vegas}

   \begin{sitem}
      \item Idea: source watches for some sign that some router's
            queue is building up and congestion will happen soon; e.g.,
      \begin{sitem}
         \item RTT is growing
         \item sending rate flattens
      \end{sitem}

      \item Intuition
      \pichere{trace3.eps,height=4in}

   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Algorithm
      \begin{sitem}
         \item let {\tt BaseRTT} be the minimum of all measured RTTs
               (commonly the RTT of the first packet)
         \item if not overflowing the connection, then
         \begin{verbatim}
   ExpectedRate = CongestionWindow / BaseRTT
         \end{verbatim}
         \item source calculates current sending rate ({\tt ActualRate})
               once per RTT
         \item source compares {\tt ActualRate} with {\tt ExpectedRate}
\bigskip\bigskip\bigskip

\begin{tt}
Diff = ExpectedRate - ActualRate\\
if Diff < $\alpha$\\
$\longrightarrow$ increase CongestionWindow linearly\\
else if Diff > $\beta$\\
$\longrightarrow$ decrease CongestionWindow linearly\\
else\\
$\longrightarrow$ leave CongestionWindow unchanged
\end{tt}
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}   
      \item Parameters
      \begin{sitem}
         \item $\alpha$: 1 packet
         \item $\beta$: 3 packets
      \end{sitem}
      \item Example trace
      \pichere{vegas.eps,height=2.75in}
      \item Even faster retransmit
      \begin{sitem}
         \item keep fine-grained timestamps for each packet
         \item check for timeout on first duplicate ACK
      \end{sitem}
   \end{sitem}
\end{slide}