COS 461, Princeton University Spring 2015
In the previous assignments, you learned about the socket interface and how it is used by an application. By now, you're pretty much an expert in how to use the socket interface over a reliable transport layer, so now seems like a good time to implement your own socket layer and transport layer! That's what you'll be doing in this assignment. You'll learn how the socket interface is implemented by the kernel and how a reliable transport protocol like TCP runs on top of the network layer. We're going to call your socket layer MYSOCK and it will contain all the features and calls that you used in Assignment 0. Your socket layer will implement a transport layer that we'll call STCP (Simple TCP), which is a stripped down version of TCP. STCP provides a connection-oriented, in-order, full duplex end-to-end delivery mechanism. It is similar to early versions of TCP, which did not implement congestion control or optimizations such as selective ACKs or fast retransmit.
To help you get started, we're providing you with a skeleton system in which you will implement MYSOCK. In fact, the MYSOCK application socket layer has already been implemented for you; you add the functionality needed for the transport layer. The skeleton consists of a network layer, a bogus transport layer that you need to fill in, the MYSOCK socket interface, and also a dummy client and server application to help you debug your socket and transport layer.
To simplify your implementation, you only need to implement the transport layer so that the supplied programs (a dummy client and a dummy server) work in reliable mode. Thus, you need NOT worry about dropped packets, reordering, retransmissions and timeouts in the underlying network layer.
Important: STCP is not TCP! While STCP is designed to be compatible with TCP, there are many distinct differences between the two protocols. When in doubt, the specifications in this assignment description should be used in your implementation.
At the lowest layer is the network layer. We provide you with a fully functional network layer that emulates a reliable datagram communication service with a peer application. As you'll see if you delve into our code, we actually implemented the reliable datagram service over a regular TCP connection. For the purposes of this assignment, it just appears to you and your code as a network layer.
The next layer up is the transport layer. We provide you with a bogus minimal transport layer in which some basic functions are already implemented. It is provided only so that the client and server will compile (but NOT run), and to give you an example of how to use the socket/transport/network layer calls. This is where you will implement the STCP functionality.
The application layers that we give you are the dummy client and dummy server. The dummy client and server are very simple and are provided to aid you with the debugging of your transport layer. When executed, the client prompts for a filename which it sends to the server. The server responds by sending back the contents of the file. The client stores this file locally under the filename "rcvd". The client can also ask for a file from the server on the command line in a non-interactive mode. The client and server work as expected if the file "rcvd" on the machine where the client is running is identical to the file asked for at the server machine. You may change the client and server as much as you like for debugging purposes. We will not use your versions of the dummy client and server for grading. The client accepts the -q option, which suppresses the output of the received data to the file.
Download the STCP tarball linked at the top of this document and extract it into a new directory in your Unix account. A Makefile is included for you in the tarball. If for some reason you need to do something different with make for testing purposes, please create your own Makefile and build with it by calling make -f YourMakefile during development. Your code must build with the standard Makefile when you submit!
This section describes the protocol your transport layer will implement. RFC 793 details the TCP state machine, which if followed carefully will likely decrease the amount of time it will take you to implement STCP and reduce bugs in the process. Some corrections to this RFC were addressed in RFC 1122 (section 4.2) that you will also want to read.
STCP is a full duplex, connection oriented transport layer that guarantees in-order delivery. Full duplex means that data flows in both directions over the same connection. Guaranteed delivery means that your protocol ensures that, short of catastrophic network failure, data sent by one host will be delivered to its peer in the correct order. Connection oriented means that the packets you send to the peer are in the context of some pre-existing state maintained by the transport layer on each host.
STCP treats application data as a stream. This means that no artificial boundaries are imposed on the data by the transport layer. If a host calls mywrite() twice with 256 bytes each time, and then the peer calls myread() with a buffer of 512 bytes, it will receive all 512 bytes of available data, not just the first 256 bytes. It is STCP's job to break up the data into packets and reassemble the data on the other side.
STCP labels one side of a connection active and the other end passive. Typically, the client is the active end of the connection and server the passive end. But this is just an artificial labeling; the same process can be active on one connection and passive on another (e.g., the HTTP proxy of Assignment 1 that "actively" opens a connection to a web server and "passively" listens for client connections).
The networking terms we use in the protocol specification have precise meanings in terms of STCP. Please refer to the glossary.
typedef uint32_t tcp_seq;
struct tcphdr {
uint16_t th_sport; /* source port */
uint16_t th_dport; /* destination port */
tcp_seq th_seq; /* sequence number */
tcp_seq th_ack; /* acknowledgment number */
#if __BYTE_ORDER == __LITTLE_ENDIAN
uint8_t th_x2:4; /* unused */
uint8_t th_off:4; /* data offset */
#elif __BYTE_ORDER == __BIG_ENDIAN
uint8_t th_off:4; /* data offset */
uint8_t th_x2:4; /* unused */
#else
#error __BYTE_ORDER must be defined as __LITTLE_ENDIAN or __BIG_ENDIAN!
#endif
uint8_t th_flags;
#define TH_FIN 0x01
#define TH_SYN 0x02
#define TH_RST 0x04 /* you don't have to handle this */
#define TH_PUSH 0x08 /* ...or this */
#define TH_ACK 0x10
#define TH_URG 0x20 /* ...or this */
uint16_t th_win; /* window */
uint16_t th_sum; /* checksum */
uint16_t th_urp; /* urgent pointer (unused in STCP) */
} __attribute__ ((packed)) STCPHeader;
For this assignment, you are not required to handle all fields in this
header. Specifically, the provided network layer wrapper code sets th_sport,
th_dport, and th_sum, while th_urp is unused; you may thus ignore these fields.
Similarly, you are not required to handle all legal flags specified here:
TH_RST, TH_PUSH, and TH_URG are ignored by STCP. The fields STCP uses are shown
in the following table. Note that any relevant multi-byte fields of the
STCP header will entail proper endianness handling with
htonl/ntohl or
htons/ntohs.
Descriptions of the fields you need to handle are as follows:
| Field | Type | Description |
|---|---|---|
| th_seq | tcp_seq | Sequence number associated with this packet. |
| th_ack | tcp_seq | If this is an ACK packet, the sequence number being acknowledged by this packet. This may be included in any packet. |
| th_off | 4 bits | The offset at which data begins in the packet, in multiples of 32-bit words. (The TCP header may be padded, so as to always be some multiple of 32-bit words long). If there are no options in the header (which there should not be for the packets you send), this is equal to 5 (i.e. data begins twenty bytes into the packet). |
| th_flags | uint8_t | Zero or more of the flags (TH_FIN, TH_SYN, etc.), OR'd together. |
| th_win | uint16_t | Advertised receiver window in bytes, i.e. the amount of outstanding data the host sending the packet is willing to accept. |
STCP assigns sequence numbers to the streams of application data by numbering the bytes. The rules for sequence numbers are:
The following rules apply to STCP data packets:
In order to guarantee delivery, data must be acknowledged. The rules for acknowledging data in STCP are:
There are two windows that you will have to take care of: the receiver and sender windows.
The receive window is the range of sequence numbers which the receiver is willing to accept at any given instant. The window ensures that the transmitter does not send more data than the receiver can handle.
Like TCP, STCP uses a sliding window protocol. The transmitter sends data with a given sequence number up to the window limit. The window "slides" (increments in the sequence number space) when data has been acknowledged. The size of the sender window, which is equal to the other side's receiver window, indicates the maximum amount of data that can be "in flight" and unacknowledged at any instant, i.e. the difference between the last byte sent and the last byte ACK'd.
The rules for managing the windows are:
The following rules apply for handling TCP options:
Because this assignment assumes that the network layer is reliable, you do not need to implement retransimissions since there will be no packet loss, timeouts, or reordering.
Normal network initiation is always initiated by the active end. Network initiation uses a three-way SYN handshake exactly like TCP, and is used to exchange information about the initial sequence numbers. The order of operations for initiation is as follows:
For more details, be sure to read RFC 793. Pay special attention to each state in the connection setup, including the simultaneous open scenario.
As in TCP, network termination is a four-way handshake between the two peers in a connection. The order of closing is independent of the network initialization order. Each side indicates to the other when it has finished sending data. This is done as follows:
RFC 793 includes more details on connection termination; pay special attention to the TCP state diagram as you will need to implement the majority of the FSM in the transport layer. Note that you are not required to support TIME_WAIT.
The interface to the transport layer is given in transport.h. The interface
consists of only one function:
extern void transport_init(mysocket_t sd, bool_t is_active);
This initializes the transport layer, which runs in its own thread, one
thread per connection. This function should not return until the connection
ends. sd is the 'mysocket descriptor' associated with this end of the
connection; is_active is TRUE if you should initiate the connection.
To implement the STCP transport layer, the only file you should modify is
transport.c. While STCP is a simplified version of TCP, it still implements
a lot of the TCP finite state machine (FSM). Within transport.c, aside from
transport_init(), there is also a stub for a local function,
control_loop(), where you should implement the majority of the
"event-driven" STCP transport FSM. By event-driven we mean use of the
stcp_wait_for_event() function to receive signals from the
application layer for data or connection close, and the network layer for
incoming packets. Each iteration of the control_loop() should
handle the current set of pending events and update the state of the transport
FSM accordingly.
The network layer provides an interface to the datagram service delivery
mechanism. Underpinning this interface are a pair of send/recv queues used for
communciation between the transport and network layer threads. Your transport
layer will build reliability on top of this layer using the functions
implemented in the network layer. The interfaces are defined in
stcp_api.h. Study it well. You are not required, but are highly
recommended, to study the implementation of the functions in the network layer.
Note that stcp_network_send() takes a variable number of
arguments, but in general use, you will either use it with a single argument
(full STCP packet buffer or just a STCP header buffer) or with two arguments
(STCP header buffer, STCP data buffer). The last argument to
stcp_network_send() must be NULL to demarcate the end
of the vararg list.
The application level socket interface is used by the client/server programs
to establish STCP connections: myconnect(), mybind(),
mylisten(), myaccept(), etc and to send/recv data.
Underlying the interface between the application and transport layer are a pair
of send/recv queues for communication between the two threads. All the
transport layer needs to know is when there is data available on the recv queue
and when the application has closed the connection, which is communicated via
the stcp_wait_for_event() mechanism. Once again, study the
interface functions defined in stcp_api.h well as they will be the
essential interface for communciation and control between the transport layer
and the application layer above and the network layer below.
Note that you may ONLY call the functions declared in stcp_api.h from your code. You must NOT call any other (internal) functions used in the mysock implementation.
A FAQ is available. Please look it over.
The provided file transfer server and client should be used to test your code. You may modify the code for the client and server however you wish for testing purposes, but your modifications will not be taken into account for grading.
Make sure that your implementation does not drop packets or send them out of order.
myconnect() and myaccept() block till a connection is
established (or until an error is detected during the connection request). To
cause them to unblock and return to the calling code, use the
stcp_unblock_application() interface found in stcp_api.h.
mybind() followed by mygetsockname() does not give the local IP address;
mygetsockname() (like the real getsockname()) does not return the local
address until a remote system connects to that mysocket.
ntohs()
and htons(), etc. calls where appropriate. If you forget them, your code may
seem to work correctly while talking to other hosts of similar endianness, but
break when talking to systems running on a different OS.
stcp_api.c:xxx: ssize_t
stcp_network_send(mysocket_t, const void*, size_t, ...): Assertion `packet_len
+ next_len <= sizeof(packet)' failedThe deliverables for this assignment are:
Submit here.