Commits

Alexandru Moșoi committed e730387

Added more text to report.

  • Participants
  • Parent commits 6ad6e12

Comments (0)

Files changed (1)

File doc/report.tex

 \documentclass[12pt]{article}
 
 \usepackage{url}
+\usepackage{paralist}
 
 \title{TCP Stack: Stop'n'Go \\
        Computer Networks Practicum}
 A connection can be in on the 10 states described in IETF RFC 793:
 \textsf{LISTEN, SYN\_SENT, SYN\_RECEIVED, ESTABLISHED, FIN\_WAIT\_1,
 FIN\_WAIT\_2, CLOSE\_WAIT, CLOSING, LAST\_ACK, TIME\_WAIT, CLOSED}.
-\textsf{TIME\_WAIT} is not implemented by my TCP library because
-it would require connection closing to hang for a very long time.
 
 Every connection is described by a \emph{Transmission Control
 Block} (TCB) implemented by structure \textsf{tcb\_t}. TCB contains
 state, etc. The library is expected to handle a single connection
 so a single global TCB is instantiated.
 
-Every packet transmitted and received packet contains a
-\emph{TCP header} described in IETF RFC 793.
+TCP packets contain a \emph{TCP header} described in IETF RFC 793.
 
 
 \subsection{Top Layer}
 
-Top layer implements the exposed interface of the TCP library.
+Top layer implements and exposes the following interface of the TCP library:
 
-On error top layer functions sets \textsf{errno} to
-value closely mimicking the behaviour of POSIX network functions.
+\begin{verbatim}
+int tcp_socket(void);
+int tcp_listen(int port, ipaddr_t *src);
+int tcp_connect(ipaddr_t dst, int port);
+int tcp_read(char *buf, int max_len);
+int tcp_write(char *buf, int len);
+int tcp_close(void);
+\end{verbatim}
 
-\subsubsection{\textsf{tcp\_listen()}).
+\textsf{tcp\_socket()} initializes the library.
+\textsf{tcp\_listen()} and \textsf{tcp\_connect()} establish
+a connection between a \emph{server} and a \emph{client}.
+\textsf{tcp\_read()} and \textsf{tcp\_write()} exchange information
+and \textsf{tcp\_close()} closes connection. The next pseudocode
+shows a typical use scenario:
 
+\bigskip
+\begin{minipage}{0.5\linewidth}
+  \begin{verbatim}
+client:
+  tcp_socket();
+  tcp_connect(server, port);
+  tcp_read(buf1, max_len);
+  tcp_write(buf2, len);
+  tcp_close();
+  \end{verbatim}
+\end{minipage}
+\begin{minipage}{0.5\linewidth}
+  \begin{verbatim}
+server:
+  tcp_socket();
+  tcp_listen(port, &server);
+  tcp_write(buf1, len);
+  tcp_read(buf2, max_len);
+  tcp_close();
+  \end{verbatim}
+\end{minipage}
+
+
+On error TCP functions return -1 and set \textsf{errno} to value
+closely mimicking the behaviour of POSIX network functions.
+
+Non-blocking functions (\textsf{tcp\_connect(), tcp\_write,
+tcp\_close()}) are implemented by installing an alarm with 1 second
+timeout. If an acknowledgment is not received before the alarm is
+fired, the last operation is performed again up to 10 times.
+
+
+\subsubsection{\textsf{tcp\_socket()}}
+
+\textsf{tcp\_socket()} initializes global variables and the IP
+library.  The connection is put in state \textsf{CLOSED}.
+
+\subsubsection{\textsf{tcp\_listen(port, *src)}}
+
+\textsf{tcp\_listen()} is a blocking operation performed by
+server to accepts new connections on given port.  On success
+it returns the IP address of the other end of the connection.
+
+\textsf{tcp\_listen()} performs the three-way hand-shake protocol:
+when a \textsf{SYN} is received, it sends back a \textsf{SYN-ACK}
+and waits for a \textsf{ACK}.
+
+\textsf{tcp\_listen()} expects the connection in state
+\textsf{CLOSED} (i.e. no connection), immediately puts it in state
+\textsf{LISTEN} and on success it moves the connection in state
+\textsf{ESTABLISHED}. It is possible to move the connection is
+state \textsf{FIN-WAIT-1} if a \textsf{FIN} is received together
+with the last \textsf{ACK}.
+
+
+\textsf{tcp\_listen()} fails if
+\begin{inparaenum}[1)]
+  \item there is a connection already established (i.e.
+  connection not in state \textsf{CLOSED}); or
+  \item if it is unable to receive packets from the IP layer.
+\end{inparaenum}
+
+
+If a client initiates a new connection, but doesn't reply with the
+final \textsf{ACK} of the handshake then \textsf{tcp\_listen()}
+will resend \textsf{SYN-ACK} until handshake is completed or
+until 10 such attempts have been made. If the handshake fails, the
+connection is abandoned and moved back into state \textsf{LISTEN}.
+
+If a new client attempts to connect to server while server is
+negotiating another connection, the old connection is abandoned.
+This, however, can happen only in \textsf{tcp\_listen()}.  After
+connection has reached state \textsf{ESTABLISHED} new connection
+requests are ignored.
+
+\textsf{tcp\_listen()} accepts data with the last \textsf{ACK}
+in the hand-shake. It first moves the connection in state
+\textsf{ESTABLISHED} where it can accept the received data.
+
+
+\subsubsection{\textsf{tcp\_connect(dst, port)}}
+
+\textsf{tcp\_connect()} is a nonblocking operation performed by a client
+to establish a connection to a server listening on a given port.
+
+\textsf{tcp\_connect()} complements \textsf{tcp\_listen()} in
+establishing a connection. It performs the three-way handshake
+protocol: it first sends a \textsf{SYN}, then waits for a \textsf{SYN-ACK}
+and finally replies back with an \textsf{ACK}.
+
+\textsf{tcp\_connect()} fails if a connection is already established
+or no \textsf{SYN-ACK} is received to complete the handshake.
+
+\textsf{tcp\_connect()} expects the connection to be in state
+\textsf{CLOSED} and, on success, leaves the connection in
+state \textsf{ESTABLISHED}.
+
+
+
+\subsubsection{\textsf{tcp\_close()}}
+
+\textsf{tcp\_close()} closes this end of connections. The semantics
+of \textsf{tcp\_close()} is that the caller cannot write anymore,
+but it can still read.
+
+\textsf{tcp\_close()} fails when it is called on already closed
+connection or no connection at all. Normal use of \textsf{tcp\_close()}
+doesn't result in failure.
+
+My implementation ignores state \textsf{TIME-WAIT}. After
+\textsf{FINWAIT-2} and \textsf{CLOSING} connections move
+in state \textsf{CLOSED}. \textsf{TIME-WAIT} would required
+\textsf{tcp\_close()} to block about 2MSL (4 minutes).
+
+
+\subsubsection{\textsf{tcp\_read(buf, max\_len)}}
+
+\textsf{tcp\_read()} is a blocking operation that 
+receives at most \textsf{max\_len} bytes and writes
+it to buffer \textsf{buf}. It returns the number of bytes received.
+
+If there is more data in the reading buffer then \textsf{tcp\_read()}
+returns data from the buffer. If the buffer is empty and the end
+of stream was not signaled \textsf{tcp\_read()} blocks until more
+data is received.
+
+\textsf{tcp\_read()} will stop after at least one byte of data
+can be returned. If peer sends more packets containing data,
+\textsf{tcp\_read()} will read at most one of them from the IP
+library.
+
+Reading is permitted after the connection is closed on the same
+side, but if the end of stream is reached then \textsf{tcp\_read()}
+returns 0.
+
+\textsf{tcp\_read()} fails if
+\begin{inparaenum}[1)]
+  \item there is no connection established; or
+  \item IP library failed to read packet.
+\end{inparaenum}
+
+If two TCP packets contain data for overlapping ranges the oldest
+data will be read. For example if a packet contains data from $A$
+to $B$ and a later packet contains data from $C$ to $D$ and $A \le C
+\le B \le D$ then bytes from $A$ to $B$ will be accepted from the
+first packet and $B$ to $D$ from the second.
+
+
+\subsubsection{\textsf{tcp\_write(buf, len)}}
+
+\textsf{tcp\_write()} is a nonblocking operation that sends at
+most \textsf{len} from buffer \textsf{buf}. It returns the number
+of bytes successfully sent and acknowledged.
+
+\textsf{tcp\_write()} fails if
+\begin{inparaenum}[1)]
+  \item there is no connection established;
+  \item connection was closed on this end;
+  \item IP library failed to deliver at least one packet; or
+  \item peer didn't acknowledged any bytes after 10 send attempts.
+\end{inparaenum}
+
+Unlike \textsf{tcp\_read()}, \textsf{tcp\_write()} will attempt to
+send all data in the buffer, chunking the data into small TCP packets
+if necessary. Assuming no communication errors 1MB bytes
+of data can be sent using a single call to \textsf{tcp\_write()}:
+
+\bigskip
+\begin{minipage}{0.5\linewidth}
+  \begin{verbatim}
+client:
+  tcp_write(large, 1<<20);
+  \end{verbatim}
+\end{minipage}
+\begin{minipage}{0.5\linewidth}
+  \begin{verbatim}
+server:
+  recv = 0;
+  while (recv <= (1<<20))
+    recv += tcp_read(small, 1000);
+  \end{verbatim}
+\end{minipage}
+
+In stop'n'go TCP data in each packet must be acknowledged before
+more data is sent. If sent data is not acknowledged within 1 second
+\textsf{tcp\_write()} will retry sending the last packet. After ten
+attempts \textsf{tcp\_write()} gives up and returns the number of
+bytes sent or if no bytes were sent then it returns an error.
+
+Any data received while establishing connection is ignored. This
+can happen when the last \textsf{ACK} in the hand-shake is
+lost. The client thinks that the connection is established and
+sends some data, but in fact server is still waiting to finish
+the three-way-handshake.
+
+TCP packets sent by \textsf{tcp\_write()} include the \textsf{ACK}
+flag. This helps in when the peer waits for a lost \textsf{ACK}.
+
+
+\subsection{Middle Layer}
 
 
 \subsection{Bottom Layer}
 is to sends packets small enough (under 1400 bytes) to avoid
 fragmentation.
 
-\subsection{Logging}
-
-Logging is implemented in file \textsf{log.h}.  The logging macros
-are used only for debugging so they are disabled in release mode. The
-parameters are in \textsf{printf()} format style.  Messages are
-written to standard output and include line number and file where
-the log was produced.
-
 
 \section{Testing}
 
 Tests perform communication between a \emph{client} and a
-\emph{server} under different scenarios such as packet lost or
-wrong checksum.  Tests are found in \textsf{tests/} directory and
+\emph{server} under different scenarios such as packet loss or
+wrong checksum. Tests are located in \textsf{tests/} directory and
 each test includes a short description which will not be included
 here. The next few sections explain how the library was tested.
 
-The library was also with  various static analysis tools such as:
+The library was verified with various static analysis tools such as:
 \emph{Valgrind}\footnote{\url{http://valgrind.org/}}
 \emph{Splint}\footnote{\url{http://www.splint.org/}} and
 \emph{Clang-Analyzer}\footnote{\url{http://clang-analyzer.llvm.org/}}.
 int client(ipaddr_t client_ip, ipaddr_t server_ip)
 {
         int ret;
-        
+
         ret = tcp_socket();
         assert(ret == 0);
         ret = tcp_connect(server_ip, 1234);
 \end{itemize}
 
 Checks are described using a functional programming style which
-makes it easy to have expressive one line checks.  E.g. 
+makes it easy to have expressive one line checks.  E.g.
 \textsf{F\_and(F\_has\_syn(), F\_has\_dst\_port(777))} checks that
 the packet has SYN flag set and destination port 777.
 
   /* Checks that packet acknowledges received data. */
   F_add(FO_NONE, F_has_ack_nr(301 + strlen(message))));
   /* Drops packet 10 times. Packet is always accepted. */
-  F_repeat(10, FO_DROP, F_always());                                       
+  F_repeat(10, FO_DROP, F_always());
   /* No packet must be sent. */
-  F_add(FO_NONE, F_never());                                               
+  F_add(FO_NONE, F_never());
   /*
    * Checks header has destination port 8888, seq nr 3000
    * and ack nr 1501. Packet is sent twice.