EECS 325/425 - Computer Networks I
Project 2: Transmission Control Protocol
1 Introduction
In this project you will be implementing the Transmission Control Protocol, as specified in [RFC793]. How-
ever, instead of implementing it inside the operating system itself, you will be implementing it inside a system
called χTCP 1. This system allows you to write socket-based applications that rely on your TCP implemen-
tation instead of the one included in your operating system. To do this, χTCP provides an alternate socket
library, χsocket , that provides the same functions as the standard socket library (connect, send, recv,
etc.). Although the χsocket functions have the same expected behaviour as the standard socket functions,
they do not implement the entire functionality provided by standard sockets (e.g., non-blocking sockets are
not supported). You will be provided with a code skeleton for your implementation. Section 5 contains
the instructions to install χTCP . Section 4 outlines the data structures and functions that you
might need for your implementations.
In χTCP , the socket layer and all the messy details of how TCP interacts with the other layers of the
protocol stack (including how packets are handed down to the network layer, and how data is passed up to
the application layer) are already implemented for you. In this project, you will focus on implementing the
TCP protocol itself.
2 The χTCP architecture
When using χTCP in place of the operating system’s TCP/IP stack, applications use χsocket functions to
perform standard socket operations, like connect, send, recv, etc. Instead of including the socket.h system
header, a χTCP header must be included:
#include "chitcp/socket.h"
The functions provided by the χsocket library are the same as the ones in the standard socket library,
except they are prefixed with chisocket_. They provide essentially the same functionality, although they do
not support every possible flag and error code. However, this is enough to write simple clients and servers.
For example:
clientSocket = chisocket_socket(PF_INET, // Family: IPv4
SOCK_STREAM, // Type: Full-duplex stream (reliable)
IPPROTO_TCP); // Protocol: TCP;
chitcp_addr_construct(host, port, &serverAddr);
chisocket_connect(clientSocket, (struct sockaddr *) &serverAddr, sizeof(struct sockaddr_in));
chisocket_send(clientSocket, "Hello!", 6, 0);
chisocket_close(clientSocket);
1This project is forked from χTCP project developed by UChicago. http://chi.cs.uchicago.edu/chitcp/index.html
1
Figure 1: The χTCP architecture
For a host to be able to use χTCP or, more specifically, to be able to write servers and clients based on the
χsocket library instead of the regular socket library, that host must run a χTCP daemon (called chitcpd).
This daemon is where your implementation of TCP will reside, with the χsocket library performing the
standard socket operations (connect, send, recv, etc.) through the χTCP daemon, instead of accessing the
operating system’s TCP/IP stack directly.
Figure 1 summarizes the χTCP architecture. Applications that want to use χTCP call the socket functions
in the χsocket library, which communicates with the χTCP daemon. This daemon includes three important
components:
• The χsocket Handlers: This contains the implementation of the socket layer, and is the interface
between an application and your TCP implementation.
• The TCP Implementation (file tcp.c, described in more detail in Section 4): Your TCP implementa-
tion.
• The χTCP Network Layer: This part of the daemon is responsible for getting your TCP packet from
one χTCP daemon to another, the same way that, when using your operating system’s TCP/IP stack,
IP is responsible for getting your TCP packet from your host to another host.
The χTCP Network Layer is actually just regular TCP (i.e., the operating system’s TCP, not the one
you are implementing). So, when χTCP needs to get one of your TCP packets to another host, it does so by
establishing a (real) TCP connection to that other host’s χTCP daemon on port 23300. Figure 2 shows the
packet encapsulation that happens in χTCP . Notice how, from χTCP ’s perspective, (real) TCP is essentially
the Network layer of the protocol stack, while your implementation of TCP is the Transport layer. If we
looked at this from a standard TCP/IP perspective, your TCP would simply be the payload of a (real) TCP
packet.
3 Implementing RFC 793
In this project, you are going to implement a substantial portion of [RFC793]. In particular, you will be
focusing on [RFC793 §3.9] (Event Processing), which provides a detailed description of how TCP should
behave (whereas the preceding sections focus more on describing use cases, header specifications, example
communications, etc.). The second paragraph of this section sums up pretty nicely how a TCP implemen-
tation should behave:
Figure 2: The χTCP layers.
(*) χTCP inserts a special header between the two TCP headers that contains χTCP -specific information.
The activity of the TCP can be characterized as responding to events.
The events that occur can be cast into three categories: user calls,
arriving segments, and timeouts. This section describes the
processing the TCP does in response to each of the events. In many
cases the processing required depends on the state of the connection.
So, we can think of TCP as a state machine where:
• The states are CLOSED, LISTEN, SYN_SENT, etc.
• The inputs are a series of events defined in [RFC793] (described below)
• The transition from one TCP state to another is based on the current state, an event, and a series of
TCP variables (SND.NXT, SND.UNA, etc. These terms are explained in [RFC793])
• Transitions from one TCP state to another result in actions, typically sending a TCP packet with
information dependent on the state of the TCP variables and the send/receive buffers.
The events defined in [RFC793 §3.9] are:
• OPEN: χTCP will generate this event when the application layer calls chisocket_connect.
• SEND: χTCP will generate this event when the application layer calls chisocket_send.
• RECEIVE: χTCP will generate this event when the application layer calls chisocket_recv.
• CLOSE: χTCP will generate this event when the application layer calls chisocket_close.
• ABORT: Not supported by χTCP .
• STATUS: Not supported by χTCP .
• SEGMENT ARRIVES: χTCP will generate this event when a TCP packet arrives.
• USER TIMEOUT: Not supported by χTCP .
• RETRANSMISSION TIMEOUT: Not supported by χTCP .
• TIME-WAIT TIMEOUT: Not supported by χTCP .
As described in the next section, your work in χTCP will center mostly on a file called tcp.c where you
are provided with functions that handle events in given TCP states. These functions are initially mostly
empty, and it is up to you to write the code that will handle each event in each state.
Of course, a TCP implementation would have to consider every possible combination of states and events.
However, many of these are actually invalid combinations. For example, [RFC793 §3.9] specifies that that if
the SEND event happens in the following states:
FIN-WAIT-1 STATE
FIN-WAIT-2 STATE
CLOSING STATE
LAST-ACK STATE
TIME-WAIT STATE
Then the following action must be taken:
Return "error: connection closing" and do not service request.
Actions like this are actually handled in the χsocket layer, and you will not have to worry about them.
For example, in the above case, the chisocket_send function will set errno to ENOTCONN.
Section 6 carves out exactly what state/event combinations you will have to implement. Additionally,
your implementation should take the following into account:
• You can assume a reliable network. You do not need to implement retransmissions or timeouts.
• You do not need to support delayed acknowledgements. An acknowledgement packet is sent immedi-
ately when data is received, although you can piggyback any data in the send buffer that is waiting to
be sent (but you do not need to wait for a timeout to increase the probability that you’ll be able to
piggyback data on the acknowledgement).
• You do not need to support the RST bit.
• You do not need to support the PSH bit.
• You do not need to support the Urgent Pointer field or the URG bit in the TCP header. This also means
you do not need to support the SND.UP, RCV.UP, or SEG.UP variables.
• You do not need to support TCP’s “security/compartment” features, which means you can assume that
SEG.PRC and TCB.PRC always have valid and correct values.
• You do not need to support the checksum field of the TCP header.
• You do not need to support TCP options.
• You do not need to support the TIME_WAIT timeout. You should still update the TCP state to
TIME_WAIT when required, but do not have to implement a timeout. Instead, you should immedi-
ately transition to CLOSED from the TIME_WAIT state.
• You do not need to support simultaneous opens (i.e., the transition from SYN_SENT to SYN_RCVD).
4 Implementing the tcp.c file
Since TCP is essentially a state machine, χTCP ’s implementation boils down to having a handler function for
each of the TCP states (CLOSED, LISTEN, SYN_RCVD, etc.), all contained in the src/chitcpd/tcp.c file.
If an event happens (e.g., a packet arrives) while the connection is in a specific state (e.g., ESTABLISHED),
then the handler function for that state is called, along with information about the event that just happened.
You will only have to worry about writing the code inside the handler function; the rest of the scaffolding
(the socket library, the actual dispatching of events to the state machine, etc.) is already provided for you.
Each handler function has the following prototype:
int chitcpd_tcp_state_handle_STATENAME(serverinfo_t *si,
chisocketentry_t *entry,
tcp_event_type_t event);
The parameters to the function are:
• si is a pointer to a struct with the χTCP daemon’s runtime information (e.g., the socket table, etc.).
You should not need to access or modify any of the data in that struct, but you will need the si pointer
to call certain auxiliary functions.
• entry is a pointer to the socket entry for the connection that is being handled. The socket entry
contains the actual TCP data (variables, buffers, etc.), which can be accessed like this:
tcp_data_t *tcp_data = &entry->socket_state.active.tcp_data;
The contents of the tcp_data_t struct are described below. You should not access or modify any other
information in entry.
• event is the event that is being handled. The list of possible events corresponds roughly to the ones
specified in [RFC793 §3.9]. They are:
– APPLICATION_CONNECT: Application has called chisocket_connect() and a three-way handshake
must be initiated.
– APPLICATION_SEND: Application has called chisocket_send(). The socket layer (which is already
implemented for you) already takes care of placing the data in the socket’s TCP send buffer. This
event is a notification that there may be new data in the send buffer, which should be sent if
possible.
– APPLICATION_RECEIVE: Application has called chisocket_recv(). The socket layer already takes
care of extracting the data from the socket’s TCP receive buffer. This event is a notification that
there may now be additional space available in the receive buffer, which would require updating
the socket’s receive window (and the advertised window).
– APPLICATION_CLOSE: Application has called chisocket_close() and a connection tear-down
should be initiated once all outstanding data in the send buffer has been sent.
– PACKET_ARRIVAL: A packet has arrived through the network and needs to be processed (RFC 793
calls this "SEGMENT ARRIVES")
– TIMEOUT2: A timeout (e.g., a retransmission timeout) has happened.
To implement the TCP protocol, you will need to implement the handler functions in tcp.c. You should
not need to modify any other file. However, you will need to use a number of functions and structs defined
elsewhere.
2Not currently supported in χTCP
4.1 The tcp_data_t struct
This struct contains all the TCP data for a given socket:
The pending packet queue
list_t pending_packets;
pthread_mutex_t lock_pending_packets;
pthread_cond_t cv_pending_packets;
As TCP packets arrive through the network, the χTCP daemon places them in the pending packet
queue of the appropriate socket (you do not need inspect the origin and destination port of the TCP
packet; this is taken care of for you). The list contains pointers to tcp_packet_t structs (described
below) in the heap. It is your responsibility to free this memory when you are done processing a packet.
The queue is implemented with the SimCList3 library, which is already included in the χTCP code, and
the head of the queue can be retrieved using SimCList’s list_fetch function. The lock_pending_packets
mutex provides thread-safe access to the queue. The cv_pending_packets condition variable is used
to notify other parts of the χTCP code that there are new packets in the queue; you should not wait
or signal this condition variable.
The TCP variables
/* Send sequence variables */
uint32_t ISS; /* Initial send sequence number */
uint32_t SND_UNA; /* First byte sent but not acknowledged */
uint32_t SND_NXT; /* Next sendable byte */
uint32_t SND_WND; /* Send Window */
/* Receive sequence variables */
uint32_t IRS; /* Initial receive sequence number */
uint32_t RCV_NXT; /* Next byte expected */
uint32_t RCV_WND; /* Receive Window */
These are the TCP sequence variables as specified in [RFC793 §3.2].
The TCP buffers
circular_buffer_t send;
circular_buffer_t recv;
These are the TCP send and receive buffers for this socket. The circular_buffer_t type is defined in
the include/chitcp/buffer.h and src/libchitcp/buffer.c files. You are provided with the imple-
mentation of this type, which will be enough to run some basic tests with your TCP implementation.
The management of these buffers is already partially implemented:
• The chisocket_send() function places data in the send buffer and generates an APPLICATION_SEND
event.
• The chisocket_recv() function extracts data from the receive buffer and generates an APPLICATION_RECV
event.
You do not need to implement the above functionality; it is already implemented for you. On the other
hand, you will be responsible for the following:
• When an APPLICATION_SEND event happens, you must check the send buffer to see if there is any
data ready to send, and you must send it out if possible (i.e., if allowed by the send window).
3http://mij.oltrelinux.com/devel/simclist/
• When a PACKET_ARRIVAL event happens (i.e., when the peer sends us data), you must extract
the packets from the pending packet queue, extract the data from those packets, verify that the
sequence numbers are correct, and put the data in the receive buffer.
• When an APPLICATION_RECV event happens, you do not need to modify the receive buffer in any
way, but you do need to check whether the size of the send window should be adjusted.
4.2 The tcp_packet_t struct
The tcp_packet_t struct is used to store a single TCP packet:
typedef struct tcp_packet
{
uint8_t *raw;
size_t length;
} tcp_packet_t;
This struct simply contains a pointer to the packet in the heap, along with its total length (including
the TCP header). You will rarely have to work with the TCP packet directly at the bit level. Instead, the
include/chitcp/packet.h header defines a number of functions, macros, and structs that you can use to
more easily work with TCP packets. More specifically:
• Use the TCP_PACKET_HEADER to extract the header of the packet (with type tcphdr_t, also defined
in include/chitcp/packet.h, which provides convenient access to all the header fields. Take into
account that all the values in the header are in network-order: you will need to convert them to
host-order before using using (and viceversa when creating a packet that will be sent to the peer).
• Use the TCP_PAYLOAD_START and TCP_PAYLOAD_LEN macros to obtain a pointer to the packet’s payload
and its length, respectively.
• Use the SEG_SEQ, SEG_ACK, SEG_LEN, SEG_WND, SEG_UP macros to access the SEG.* variables defined
in [RFC793 §3.2]. Take into account that these macros do convert the values from network-order to
host-order.
• Finally, although this header file provides a chitcp_tcp_packet_create function, you should not use
this function directly. Instead, use chitcpd_tcp_packet_create (note the chitcpd prefix, not chitcp)
defined in src/chitcpd/serverinfo.h, which is a wrapper around chitcp_tcp_packet_create (be-
sides creating a packet, it will also correctly initialize the source and destination ports to match those
of the socket).
4.3 The chitcpd_update_tcp_state function
This function is defined in src/chitcpd/serverinfo.h. Whenever you need to change the TCP state, you
must use this function. For example:
chitcpd_update_tcp_state(si, entry, ESTABLISHED);
The si and entry parameters are the same ones that are passed to the TCP handler function.
4.4 The chitcpd_send_tcp_packet function
This function is defined in src/chitcpd/connection.h. Whenever you need to send a TCP packet to the
socket’s peer, you must use this function. For example:
tcp_packet_t packet;
/* Initialize values in packet */
chitcpd_send_tcp_packet(si, entry, &packet);
The si and entry parameters are the same ones that are passed to the TCP handler function.
4.5 The logging functions
The χTCP daemon prints out detailed information to standard output using a series of logging functions
declared in src/include/log.h. We encourage you to use these logging functions instead of using printf
directly. More specifically, you should use the printf-style chilog() function to print messages:
chilog(WARNING, "Asked send buffer for %i bytes, but got %i.", nbytes, tosend);
And the chilog_tcp() function to dump the contents of a TCP packet:
tcp_packet_t packet;
/* Initialize values in packet */
chilog(DEBUG, "Sending packet...");
chilog_tcp(DEBUG, packet, LOG_OUTBOUND);
chitcpd_send_tcp_packet(si, entry, &packet);
The third parameter of chilog_tcp can be LOG_INBOUND or LOG_OUTBOUND to designate a packet that is
being received or sent, respectively (this affects the formatting of the packet in the log). LOG_NO_DIRECTION
can also be used to indicate that the packet is neither inbound or outbound.
In both functions, the first parameter is used to specify the log level:
• CRITICAL: Used for critical errors for which the only solution is to exit the program.
• ERROR: Used for non-critical errors, which may allow the program to continue running, but a specific
part of it to fail (e.g., an individual socket).
• WARNING: Used to indicate unexpected situation which, while not technically an error, could cause one.
• INFO: Used to print general information about the state of the program.
• DEBUG: Used to print detailed information about the state of the program.
• TRACE: Used to print low-level information, such as function entry/exit points, dumps of entire data
structures, etc.
The level of logging is controlled by the -v argument when running chitcpd:
• No -v argument: Print only CRITICAL and ERROR messages.
• -v: Also print WARNING and INFO messages.
• -vv: Also print DEBUG messages.
• -vvv: Also print TRACE messages.
5 Building and testing the χTCP code
We will use the same Virtual Machine image for developing this project. First, clone χTCP repository from
GitHub to your home directory in VM:
git clone https://github.com/uchicago-cs/chitcp.git
Then, download install-chitcp.sh from Canvas and execute the script:
./install-chitcp.sh
You should only need to rerun the above commands if you modify CMake’s CMakeLists.txt (which you
should not need to do as part of this project). Once you have done this, simply run make inside the build
directory to build χTCP . This will generate the χTCP daemon (chitcpd), some sample programs, as well
as the test executables (all starting with test-). Take into account that you must run these programs from
inside the build directory.
By default, make will only print the names of the files it is building. To enable a more verbose output
(including the exact commands that make is running during the build process), just run make like this:
make VERBOSE=1
This will generate two files:
• chitcpd: The χTCP daemon. You can verify that it works correctly by running the following:
./chitcpd -v
You should see the following output:
[2014-02-02 11:36:07] INFO lt-chitcpd chitcpd running. UNIX socket: /tmp/chitcpd.socket. TCP socket: 23300
Note that, by default, chitcpd will run on port 23300. You do not need to run this daemon for
testing your implementation. Instead, you should run the test suite discussed next.
• ./.libs/libchitcp.so: The libchitcp library. Any applications that want to use the χsocket library
will need to link with this library.
Finally, to run the χTCP test suite, run the following command inside the build directory for testing
connection initiation:
LOG=MINIMAL ./test-tcp --filter ’conn_init/*’
or use for colorizing this output for extra readability:
LOG=MINIMAL ./test-tcp --filter ’conn_init/*’ | ../tests/colorize-minimal.sh
To test all the tasks you implemented for this project, run:
LOG=MINIMAL ./test-tcp --filter ’?(conn_init|data_transfer|conn_term)/*’
Take into account that, until you implement TCP, many of these tests will fail.
6 TCP over a Reliable Network
This project will be divided into three sub-tasks:
• Implementing the TCP 3-way handshake (checkpoint-1: March 27th)
• Sending and receiving data (checkpoint-2: April 3st)
• Connection termination (submission deadline: April 10th)
There will be 2 checkpoints during this project. You will be provided with the implementations for subtask
1 and 2 after the checkpoint dates so that you could continue working on the remaining tasks with the
provided code. Thus, it is important to submit your code on time!
NO LATE submissions will be accepted for checkpoint-1 and checkpoint-2. Final
late submissions are accepted within 3 days after the deadline, with 20% late penalty.
Implementing the TCP 3-way handshake
In tcp.c you must implement the following:
• Handling event APPLICATION_CONNECT in chitcpd_tcp_state_handle_CLOSED. This corresponds to
handling the OPEN Call in the CLOSED STATE in [RFC793 §3.9].
• Handling event PACKET_ARRIVAL in:
– chitcpd_tcp_state_handle_LISTEN
– chitcpd_tcp_state_handle_SYN_SENT
– chitcpd_tcp_state_handle_SYN_RCVD
As described in the SEGMENT ARRIVES portion of [RFC793 §3.9].
Suggestion: Instead of writing separate pieces of code in each of the handler functions where you’re
handling the PACKET_ARRIVAL event, you may want to write a single function whose purpose is to handle
packets in any TCP state, following the general procedure described in pages 64-75 of [RFC793]. This will
also make it easier to implement the rest of the project.
Sending and receiving data
In this task, you will complete your TCP implementation. This involves handling the following events in
chitcpd_tcp_state_handle_ESTABLISHED:
• Event PACKET_ARRIVAL, as described in the SEGMENT ARRIVES portion of [RFC793 §3.9], but without
handling FIN packets.
• Event APPLICATION_SEND. This corresponds to handling the SEND Call in the ESTABLISHED STATE in
[RFC793 §3.9]. Take into account that the χsocket layer already takes care of putting data in the send
buffer. So, this event notifies your TCP implementation that there is new data in the send buffer, and
that it should be sent if possible.
• Event APPLICATION_RECEIVE. This corresponds to handling the RECEIVE Call in the ESTABLISHED
STATE in [RFC793 §3.9]. Take into account that the χsocket layer already takes care of retrieving
data from the receive buffer and handing it to the application layer. This event notifies your TCP
implementation that space has become available in the buffer, and you should update the TCP internal
variables accordingly.
Connection tear-down
This involves handling the APPLICATION_CLOSE event in the following handlers:
• chitcpd_tcp_state_handle_ESTABLISHED
• chitcpd_tcp_state_handle_CLOSE_WAIT
Both of these correspond to handling the CLOSE Call in the ESTABLISHED STATE and CLOSE-WAIT STATE
in [RFC793 §3.9].
You also need to handle the PACKET_ARRIVAL event in the following handlers:
• chitcpd_tcp_state_handle_FIN_WAIT_1
• chitcpd_tcp_state_handle_FIN_WAIT_2
• chitcpd_tcp_state_handle_CLOSE_WAIT
• chitcpd_tcp_state_handle_CLOSING
• chitcpd_tcp_state_handle_LAST_ACK
• Modify the handling of this event in chitcpd_tcp_state_handle_ESTABLISHED to handle FIN packets.
All of these are described in the SEGMENT ARRIVES portion of [RFC793 §3.9].
7 Testing your implementation
To test your implementation, we have provided some basic tests. To run these tests, just run:
LOG=MINIMAL ./test-tcp --filter ’conn_init/*’
LOG=MINIMAL ./test-tcp --filter ’data_transfer/*’
LOG=MINIMAL ./test-tcp --filter ’conn_term/*’
More details could be found: http://chi.cs.uchicago.edu/chitcp/testing.html
8 Submission deadlines
• Implementing the TCP 3-way handshake (checkpoint-1: March 27th, 11:59 pm)
• Sending and receiving data (checkpoint-2: April 3st, 11:59 pm)
• Connection termination (submission deadline: April 10th, 11:59 pm)
Again,NO LATE submissions for checkpoint-1 and checkpoint-2 will be accepted.