\section{Reliable Transmission}

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

   \subsection{Overview}

   Recover from Corrupt Frames 
   \begin{sitem}
      \item Error Correction Codes (ECC); also called Forward Error
	    Correction (FEC)
      \item Acknowledgements and Timeouts; also called Automatic Repeat
	    reQuest (ARQ)
   \end{sitem}

   \pichere{ack_timeout.eps,height=4.5in}

\end{slide}

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

   \subsection{Stop-and-Wait}

   \pichere{stop_wait.eps,height=3in}

   \bigskip
   Problem: Keeping the pipe full. 

   \bigskip
   Example: 1.5Mbps link $\times$ 45ms RTT = 67.5Kb (8KB). Assuming
   frame size of 1KB, stop-and-wait uses about one-eighth of the link's
   capacity. Want the sender to be able to transmit up to 8 frames
   before having to wait for an ACK.
\end{slide}

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

   \subsection{Sliding Window}

   Idea: Allow sender to transmit multiple frames before receiving
   an ACK, thereby keeping the pipe full. There is an upper limit
   on the number of outstanding (un-ACKed) frames allowed.

   \pichere{slide_win.eps,height=4in}

\end{slide}

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

   Sender:
   \begin{sitem}
      \item Assign sequence number to each frame ({\tt SeqNum})
      \item Maintain three state variables:
      \begin{sitem}
         \item send window size ({\tt SWS})
         \item last acknowledgment received ({\tt LAR})
         \item last frame sent ({\tt LFS})
      \end{sitem}
      \item Maintain invariant:  {\tt LFS - LAR + 1} $\le$ {\tt SWS}

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

      \item When ACK arrives, advance {\tt LAR}, thereby opening window
      \item Buffer up to {\tt SWS} frames
   \end{sitem}
\end{slide}

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

   Receiver:
   \begin{sitem}
      \item Maintain three state variables:
      \begin{sitem}
         \item receive window size ({\tt RWS})
         \item last frame acceptable ({\tt LFA})
         \item next frame expected ({\tt NFE})
      \end{sitem}
      \item Maintain invariant:  {\tt LFA - NFE + 1} $\le$ {\tt RWS}

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

      \item Frame {\tt SeqNum} arrives:
      \begin{sitem}
         \item if {\tt NFE $\le$ SeqNum $\le$ LFA} $\longrightarrow$ accept
         \item if {\tt SeqNum $<$ NFE} or {\tt SeqNum $>$ LFA} $\longrightarrow$ discarded
      \end{sitem}
      \item Send cumulative ACK
      \item Variations
      \begin{sitem}
         \item selective acknowledgements
         \item negative acknowledgements (NAK)
      \end{sitem}
   \end{sitem}

\end{slide}

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

   Sequence Number Space
   \begin{sitem}
      \item {\tt SeqNum} field is finite; sequence numbers wrap around
      \item Sequence number space must be larger than number of
            outstanding frames
      \item {\tt SWS $\le$ MaxSeqNum-1} is not sufficient
      \begin{sitem}
         \item suppose 3-bit {\tt SeqNum} field ({\tt 0..7})
         \item {\tt SWS=RWS=7}
         \item sender transmit frames {\tt 0..6}
         \item arrive successfully, but ACKs lost
         \item sender retransmits {\tt 0..6}
         \item receiver expecting {\tt 7,0..5}, but receives second
               incarnation of {\tt 0..5}
      \end{sitem}
      \item {\tt SWS $<$ (MaxSeqNum+1)/2} is correct rule
      \item Intuitively, {\tt SeqNum} ``slides'' between two halves
            of sequence number space
   \end{sitem}
\end{slide}

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

   \subsection{Concurrent Logical Channels}

   \begin{sitem}
      \item Multiplex several logical channels over a single point-to-point
            link; run stop-and-wait on each logical channel.

      \bigskip
      \item Maintain three bits of state for each channel:
      \begin{sitem}
         \item boolean saying whether the channel is currently busy
         \item sequence number for frames sent on this logical channel
         \item next sequence number to expect on this logical channel
      \end{sitem}

      \bigskip
      \item ARPANET supported eight logical channels over each ground link
      (16 over each satellite link).

      \bigskip
      \item Header for each frame included a 3-bit channel number and a 1-bit
      sequence number, for a total of 4 bits; same number of bits as the
      sliding window protocol requires to support up to eight outstanding
      frames on the link.

      \bigskip
      \item Separates reliability from {\it flow control} and {\it frame 
            order}.
   \end{sitem}
\end{slide}






