\section{Reliable Byte-Stream (TCP)}

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

   \subsection{Overview}

   \begin{sitem}
      \item Connection-oriented
      \item Byte-stream
      \begin{sitem}
         \item sending process writes some number of bytes
         \item TCP breaks into {\it segments} and sends via IP
         \item receiving process reads some number of bytes
      \end{sitem}
      \pichere{tcp_stream.eps,height=3in}
      \item Full duplex
      \item Flow control: keep sender from overrunning receiver
      \item Congestion control: keep sender from overrunning network
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{End-to-End Issues}

   Based on sliding window protocol used at data link level, but
   the situation is very different.

   \begin{sitem}
      \item Potentially connects many different hosts
      \begin{sitem}
         \item need explicit connection establishment and termination
      \end{sitem}

      \item Potentially different RTT
      \begin{sitem}
         \item need adaptive timeout mechanism
      \end{sitem}

      \item Potentially long delay in network
      \begin{sitem}
         \item need to be prepared for arrival of very old packets
      \end{sitem}

      \item Potentially different capacity at destination
      \begin{sitem}
         \item need to accommodate different amounts of buffering
      \end{sitem}

      \item Potentially different network capacity
      \begin{sitem}
         \item need to be prepared for network congestion
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Segment Format}

   \pichere{tcp_format.eps,height=2in}

   \begin{sitem}
      \item Each connection identified with 4-tuple:
      \begin{sitem}
         \item {\tt $\langle$SrcPort, SrcIPAddr, DstPort, DstIPAddr$\rangle$}
      \end{sitem}

      \item Sliding window + flow control
      \begin{sitem}
         \item {\tt Acknowledgment, SequenceNum, AdvertisedWindow}
      \end{sitem}
      \pichere{tcp_flow.eps,height=1in}

      \item Flags
      \begin{sitem}
         \item {\tt SYN, FIN, RESET, PUSH, URG, ACK}
      \end{sitem}

      \item Checksum
      \begin{sitem}
         \item pseudo header + tcp header + data
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Connection Establishment and Termination}

   Three-Way Handshake

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

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

   State Transition Diagram

   \pichere{tcp_std.eps, height=6in}   

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

   \subsection{Sliding Window Revisited}

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

   \begin{sitem}
      \item Each byte has a sequence number
      \item ACKs are cumulative
      \item Sending side
      \begin{sitem}
         \item {\tt LastByteAcked $\le$ LastByteSent}
         \item {\tt LastByteSent $\le$ LastByteWritten}
         \item bytes between {\tt LastByteAcked} and {\tt LastByteWritten} 
               must be buffered
      \end{sitem}
      \item Receiving side
      \begin{sitem}
         \item {LastByteRead $<$ NextByteExpected}
         \item {\tt NextByteExpected $\le$ LastByteRcvd + 1}
         \item bytes between {\tt NextByteRead} and {\tt LastByteRcvd} 
               must be buffered
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Flow Control}

   \begin{sitem}
      \item Sender buffer size: {\tt MaxSendBuffer}
      \item Receive buffer size: {\tt MaxRcvBuffer}
      \item Receiving side
      \begin{sitem}
         \item {\tt LastByteRcvd - NextByteRead $\le$ MaxRcvBuffer}
         \item {\tt AdvertisedWindow = MaxRcvBuffer - (LastByteRcvd - 
               NextByteRead)}
      \end{sitem}
      \item Sending side
      \begin{sitem}
         \item {\tt LastByteSent - LastByteAcked $\le$ AdvertisedWindow}
         \item {\tt EffectiveWindow = AdvertisedWindow - (LastByteSent - 
               LastByteAcked)}
         \item {\tt LastByteWritten - LastByteAcked $\le$ MaxSendBuffer}
         \item block sender if {\tt (LastByteWritten - LastByteAcked) + $y$ 
               $>$ MaxSendBuffer}
      \end{sitem}
      \item Always send ACK in response to an arriving data segment       
      \item Persist when {\tt AdvertisedWindow=0}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}
  
   \subsection{Keeping the Pipe Full}

   Wrap Around: 32-bit {\tt SequenceNum}

\begin{center}
\begin{tabular}{l|l}
\hline
Bandwidth & Time Until Wrap Around\\
\hline
T1 (1.5Mbps) & 6.4 hours \\
Ethernet (10Mbps) & 57 minutes \\
T3 (45Mbps) & 13 minutes \\
FDDI (100Mbps) & 6 minutes \\
STS-3 (155Mbps) & 4 minutes \\
STS-12 (622Mbps) & 55 seconds \\
STS-24 (1.2Gbps) & 28 seconds \\
\hline
\end{tabular}
\end{center}
  
   Bytes in Transit: 16-bit {\tt AdvertisedWindow}

\begin{center}
\begin{tabular}{l|l}
\hline
Bandwidth & Delay $\times$ Bandwidth Product\\
\hline
T1 (1.5Mbps) & 18KB \\
Ethernet (10Mbps) & 122KB \\
T3 (45Mbps) & 549KB \\
FDDI (100Mbps) & 1.2MB \\
STS-3 (155Mbps) & 1.8MB \\
STS-12 (622Mbps) & 7.4MB \\
STS-24 (1.2Gbps) & 14.8MB \\
\hline
\end{tabular}
\end{center}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Adaptive Retransmission}

   Original Algorithm

   \begin{sitem}
      \item Measure {\tt SampleRTT} for each segment/ACK pair   
      \item Compute weighted average of RTT
      \begin{sitem}
         \item {\tt EstimatedRTT = $\alpha \times$ EstimatedRTT + \\
               $\beta \times$ SampleRTT}
         \item where {\tt $\alpha$ + $\beta$ = 1}
         \item $\alpha$ between 0.8 and 0.9
         \item $\beta$ between 0.1 and 0.2
      \end{sitem}
      \item Set timeout based on {\tt EstimatedRTT}
      \begin{sitem}
         \item {\tt TimeOut = 2 $\times$ EstimatedRTT}
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   Karn/Partridge Algorithm

   \pichere{tcp_karn.eps,height=2.5in}

   \begin{sitem}
      \item Do not sample RTT when retransmitting
      \item Double timeout after each retransmission
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   Jacobson/Karels Algorithm

   \begin{sitem}
      \item New calculation for average RTT\\
      \begin{tt}
      Difference = SampleRTT - EstimatedRTT\\
      EstimatedRTT = EstimatedRTT + ($\delta\ \times$ Difference)\\
      Deviation = Deviation + $\delta$ ( \vline Difference \vline - Deviation)
      \end{tt}
      \begin{sitem}
         \item where $\delta$ is a fraction between 0 and 1
      \end{sitem}
      \item Consider variance when setting timeout value\\
      \begin{tt}
      TimeOut = $\mu$ $\times$ EstimatedRTT + $\phi$ $\times$ Deviation
      \end{tt}
      \begin{sitem}
         \item where $\mu$ = 1 and $\phi$ = 4
      \end{sitem}      
      \item Notes
      \begin{sitem}
         \item algorithm only as good as granularity of clock (500ms on Unix)
         \item accurate timeout mechanism important to congestion control 
               (later)
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{TCP Extensions}

   \begin{sitem}
      \item Implemented as header options
      \item Store timestamp in outgoing segments
      \item Use 32-bit timestamp to extend sequence space (PAWS)
      \item Shift (scale) advertised window
   \end{sitem}
\end{slide}
