Princeton University
Computer Science Department

Computer Science 461
Computer Networks

Jennifer Rexford

Spring 2006


Directory
Summary | Administrivia | Schedule | Assignments



Programming Assignment #3 - MYSOCK/STCP

Due : May 19th, 11:59pm

submit by email to mhw@cs.princeton.edu


Contents


Overview

In the first assignment, 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 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 get to learn how the socket interface is implemented by the kernel and how a reliable transport protocol like TCP runs on top of an unreliable delivery mechanism.  The goal is to run your ftp client from Assignment HW1 unchanged (apart from renaming the kernel socket calls) to work with your very ownnew socket and transport layer. We're going to call your socket layer MYSOCK and it will contain all the features and calls that you used in Assignment #1. Your socket layer will implement a transport layer that we'll call STCP (Simple TCP), which is in essence a stripped down version of TCP. STCP is compatible with TCP, and 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 the MYSOCK and STCP layers. In fact, the MYSOCK layer has already been implemented for you;  you get to add the the functionality needed for the transport layer. The skeleton consists of a network layer, a bogus transport layer, and also a dummy client and server application to help you debug your socket and transport layer. When you have debugged your transport layer and had it work with the dummy client and server, you'll be compiling it with your ftp client code from the first assignment. We will provide an ftp server against which you can then test your new ftp client code.

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.

The structure of the code

Network layer

At the lowest layer is the network layer. We provide you with a fully functional network layer that emulates an reliable datagram communication service with a peer application; i.e. it will send and receive data between a client and server. As you'll see if you delve into our code, we actually implemented the so-called 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.

Transport 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.

Application layer

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; in fact, we might grade your project with some other (simple and similar) application. Both client and server accept the -U flag to make the network layer unreliable.  The client also accepts the -q option, which suppresses the output of the received data to the file.


Getting Started

Download this file into a suitable directory and then run the command:

tar zxvf tcp.tgz

This will create a directory "tcp" into which all the stub files will be put. The only file that you should edit is transport.c, and the only API that you should call are in stcp_api.h. Note that there are a few structures and macros in transport.h that you might be interested in using.

We provide a Makefile which will build a version of the dummy client and server suitable for use under gdb. The Makefile expects all of your code to be put into the file transport.c. Please do not change the Makefile for the first two milestones. If you need to modify it to test something, create a new Makefile and use "make -f NewMakefile". This new makefile will not be used in the grading.


MYSOCK layer interface definition

The interface provided by this layer is the same as the socket interface with the words "my" prefixed to every function call name. You should look in the files mysock_api.c, mysock.c, and mysock.h for these functions. We have provided you with the functions: mysocket, mybind, myconnect, mylisten, myaccept, myclose, myread, mywrite corresponding to the socket interface provided by the kernel. You are not allowed to change any of these functions.


STCP Protocol Definition

This section details the protocol your transport layer will implement. Be sure to also read RFC 793, which describes TCP in more detail.

Overview

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 FTP client of HW#1 that "actively" opens a control connection and "passively" listens on a data connection).

The networking terms we use in the protocol specification have precise meanings in terms of STCP. Please refer to the glossary.

STCP Packet Format

An STCP packet has a maximum size of 536 bytes. It has the same header format as TCP. The header format is defined in transport.h as follows:

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 */
#ifdef _BIT_FIELDS_LTOH
        u_int   th_x2:4,                /* (unused) */
                th_off:4;               /* data offset */
#else
        u_int   th_off:4,               /* data offset */
                th_x2:4;                /* (unused) */
#endif
        uint8_t th_flags;
#define TH_FIN  0x01
#define TH_SYN  0x02
#define TH_RST  0x04
#define TH_PUSH 0x08
#define TH_ACK  0x10
#define TH_URG  0x20
        uint16_t th_win;                 /* window */
        uint16_t th_sum;                 /* checksum */
        uint16_t th_urp;                 /* urgent pointer */
        /* options follow */
};

typedef struct tcphdr STCPHeader;

For this assignment, you are not required to handle all fields in this header. Specifically, the provided 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.

The packet header field format (for the relevant fields) is 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, 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'ed 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.

Sequence Numbers

STCP assigns sequence numbers to the streams of application data by numbering the bytes. The rules for sequence numbers are:

Data Packets

The following rules apply to STCP data packets:

ACK Packets

In order to guarantee reliable delivery, data must be be acknowledged. The rules for acknowledging data in STCP are:

Sliding Windows

There are two windows that you will have to take care of: the receiver and sender windows.

The receiver 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 as and when data has been acknowledged. The size of the sender window indicates the maximum amount of data that can be unacknowledged at any instant. Its size is equal to the other side's receiver window.

The rules for managing the windows are:

Options

The following rules apply for handling TCP options:

Network Initiation

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.

Network Termination

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; see in particular the state diagram. Note that you are not required to support TIME_WAIT.

Glossary

ACK packet
An acknowledgment packet; any segment with the ACK bit set in the flags field of the packet header.
Connection
The entire data path between two hosts, in both directions, from the time STCP obtains the data to the time it is delivered to the peer.
Data packet
Any segment which has a payload; i.e. the th_off field of the packet header corresponds to an offset less than the segment's total length.
FIN packet
A packet which is participating in the closing of the connection; any segment with the FIN bit set in the flags field of the packet header.
Payload
The optional part of the segment which follows the packet header and contains application data. Payload data is limited to a maximum size of 536 bytes in STCP.
Segment
Any packet sent by STCP. A segment consists of a required packet header and an optional payload.
Sequence Number
The uniquely identifying index of a byte within a stream.
Network
The data path between two hosts provided by the network layer.
Stream
An ordered sequence of bytes with no other structure imposed. In an STCP connection, two streams are maintained: one in each direction.
Window
Of a receiver's incoming stream, the set of sequence numbers for which the receiver is prepared to receive data. Defined by a starting sequence number and a length. In STCP, the length is fixed at 3072.

Transport Layer

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 initialises 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.


Network Layer

The network layer provides an interface for the connectionless and unreliable datagram service delivery mechanism. 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. You are not required, but are highly recommended, to study the implementation of the functions in the network layer.

Please note that you may only use the interfaces declared in stcp_api.h in your own code. You must not call any other (internal) functions used in the mysock implementation.


Assignment FAQ

A FAQ is also available. Please look over it before asking your question to your TA.


Description of Requirements


Testing your code

A test script is currently in the works. Please check back for details on how to use it.

Miscellaneous Notes and Hints

  1. The calls 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.
  2. 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.

Deliverables

  1. Your modified transport.c (You are not allowed to modify or submit any other .c or .h file)
  2. README describing the design of your transport layer. One page is enough for the writeup.
  3. *.c - Source code for ftpclient (only if using your ftpcopy)
  4. Makefile

Links