Project 3: TCP over IP over UDP

CS168 Computer Networks Fonseca

Due: 11:59 PM, Nov 25, 2014

Contents

1 Introduction 1

2 The Pieces 2

2.1 State Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 Sliding Window Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2.1 Extra Credit: Congestion Control . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.4 Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Implementation 5

4 Tips 6

5 Grading 6

5.1 Milestone I – 5% (Nov 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

5.2 Milestone II – 20% (Nov 8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

5.3 Basic Functionality – 55% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5.4 Performance and Documentation – 20% . . . . . . . . . . . . . . . . . . . . . . . . . 7

6 Getting Started 8

6.1 C Support Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

6.2 TCP Reference Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

7 Handing In and Interactive Grading 8

8 Final Thoughts 9

1 Introduction

In this project, you will implement a simple, but RFC-compliant form of TCP on top of IP from

your last assignment. You will build the transport layer and export a socket API similar to what

you used in Snowcast.

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

Each year, students report this assignment is an order of magnitude harder than its predecessor

(seriously). But when you are done here, you will really understand TCP. We’ve given you a lot of

time for this assignment – use it wisely!

2 The Pieces

In this assignment you will use the library you wrote for IP as the underlying network.

Your TCP implementation will have four major pieces — the state machine that implements

connection setup and teardown, the sliding window protocol that determines what data you are

allowed to send and receive at any point, the API to your sockets layer, and a driver program that

will allow all of us to test your code.

2.1 State Machine

You have to implement a state machine that allows state transitions in your TCP. You can use this

diagram

to help orient yourself.

The state machine is not as complicated as it may seem, but you should be sure that your TCP

follows all state transitions properly, and doesn’t do anything otherwise. For example, you need to

send SYNs for connect, and FINs to close. You will be expected to follow RFC793

and RFC2525

precisely. You don’t have to handle the parts of the RFC that refer to urgent data, precedence, and

security.

You can start coding by just using the diagram and getting connections to set up and close under

ideal conditions. However, there are tons of less obvious cases that the diagram doesn’t cover – for

example, what happens when, after a call to

connect

, you’ve sent a SYN, but you receive a packet

that has an incorrect ACK in it? Once your basic state diagram is working, we recommend that

you look at the RFC for answers to questions such as these. In particular, pages 54 and on contain

info on exactly what you should do in such scenarios.

2.2 Sliding Window Protocol

You need to implement the sliding window protocol that is the heart of TCP. Make sure you

understand the algorithm before you start coding. Also keep in mind how sliding windows will

interact with the rest of TCP. For example, a call to CLOSE (

v_shutdown(s, 1)

in our API) only

closes data ﬂow in one direction. Because data will still be ﬂowing in the other direction, the closed

side will need to send acknowledgments and window updates until both sides have closed.

Be sure that you can accept out-of-order packets.

That is, a packet’s sequence number

doesn’t have to be exactly the sequence number of the start of the window. It can be fully contained

within the window, somewhere in the middle. The easiest way to handle such packets is to place

them on a queue of potentially valid packets, and then deal with them once the window has caught

up to the beginning of that segment’s sequence number.

http://ttcplinux.sourceforge.net/documents/one/tcpstate/tcpstate.html

http://www.faqs.org/rfcs/rfc793.html

http://www.faqs.org/rfcs/rfc2525.html

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

You should strictly adhere to the ﬂow control window as speciﬁed in the RFC, e.g. don’t send packets

outside of your window, etc. You have to ensure reliability – all data must get to its destination in

order, uncorrupted.

2.2.1 Extra Credit: Congestion Control

If you are taking the course for graduate credit, you m

ust implement slow start.

2.3 API

You must implement an API to your TCP implementation. This layer will use constructs appropriate

for whichever language you are using, but the API functions/methods will be essentially the same.

In C, you will create a mock sockets layer, using your own table and set of integers to allow

connecting and listening, reading and writing into buﬀers, etc. In Go, you will provide types similar

to net.TCPConn and net.TCPListener. In Java, you will provide a type similar to java.net.Socket.

An independent thread in your program should be able to use this interface in almost the exact same

way that you would use the normal API in your language. These functions, on error, should return

appropriate error codes (such as negative values in C, error values in Go, or thrown exceptions in

Java). For C, make sure to use the oﬃcial error codes (such as EBADF).

The functionality you need in the C socket API is shown below. Except for

v_socket

and

v_bind

these functions (or some reasonably equivalent function, potentially with a diﬀerent name or

arguments) should be part of the API for any language other than C.

/* returns a new, unbound socket.

on failure, returns a negative value */

int v_socket();

/* binds a socket to a port

always bind to all interfaces - which means addr is unused.

returns 0 on success or negative number on failure */

int v_bind(int socket, struct in_addr *addr, uint16_t port);

/* moves socket into listen state (passive OPEN in the RFC)

bind the socket to a random port from 1024 to 65535 that is unused

if not already bound

returns 0 on success or negative number on failure */

int v_listen(int socket);

/* connects a socket to an address (active OPEN in the RFC)

returns 0 on success or a negative number on failure */

int v_connect(int socket, struct in_addr *addr, uint16_t port);

/* accept a requested connection (behave like unix socket’s \verb|accept|)

returns new socket handle on success or negative number on failure */

int v_accept(int socket, struct in_addr *node);

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

/* read on an open socket (RECEIVE in the RFC)

return num bytes read or negative number on failure or 0 on eof */

int v_read(int socket, unsigned char *buf, uint32_t nbyte);

/* write on an open socket (SEND in the RFC)

return num bytes written or negative number on failure */

int v_write(int socket, const unsigned char *buf, uint32_t nbyte);

/* shutdown an open socket. If type is 1, close the writing part of \\

the socket (CLOSE call in the RFC. This should send a FIN, etc.)\\

If 2 is specified, close the reading part (no equivalent in the RFC; \\

v_read calls should just fail, and the window size should not grow any \\

more). If 3 is specified, do both. The socket is not invalidated.\\

returns 0 on success, or negative number on failure \\

If the writing part is closed, any data not yet ACKed should still be

retransmitted. */

int v_shutdown(int socket, int type);

/* Invalidate this socket, making the underlying connection inaccessible to

any of these API functions. If the writing part of the socket has not been

shutdown yet, then do so. The connection shouldn’t be terminated, though;

any data not yet ACKed should still be retransmitted. */

int v_close(int socket);

2.4 Driver

Your driver should support the following commands (“command/cmd” means that typing both

“command” and “cmd” should have the same eﬀect):

help Print this list of commands.

interfaces/li Print information about each interface, one per line.

routes/lr Print information about the route to each known destination, one per line.

sockets/ls List all sockets, along with the state the TCP connection associated with them is in.

down integer Bring an interface “down”.

up integer

Bring an interface “up” (it must be an existing interface, probably one you brought

down)

accept/a port

Open a socket, bind it to the given port, and start accepting connections on that

port. Your driver must continue to accept other commands.

connect/c ip port

Attempt to connect to the given IP address, in dot notation, on the given port.

Example: c 10.13.15.24 1056.

send/s/w socket data Send a string on a socket.

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

recv/r socket numbytes y/n

Try to read data from a given socket. If the last argument is y, then

you should block until numbytes is received, or the connection closes. If n, then don’t block;

return whatever recv returns. Default is n.

sendﬁle f ilename ip port

Connect to the given IP and port, send the entirety of the speciﬁed ﬁle,

and close the connection. Your driver must continue to accept other commands.

recvﬁle f ilename port

Listen for a connection on the given port. Once established, write every-

thing you can read from the socket to the given ﬁle. Once the other side closes the connection,

close the connection as well.

Your driver must continue to accept other commands.

Hint: give /dev/stdout as the ﬁlename to print to the screen.

window socket Print the socket’s send / receive window size.

shutdown socket read/write/both v_shutdown

on the given socket. If read or r is given, close

only the reading side. If write or w is given, close only the writing side. If both is given, close

both sides. Default is write.

close socket v_close on the given socket.

We actually provide a .c ﬁle which implements most of this functionality. See the Getting Started

section below.

3 Implementation

A few notes:

•

You should use the TCP packet format, exactly as-is. You can use the header found in

netinet/tcp.h

, although technically, you can use anything, since the TCP packet format is

not exposed in the API.

•

TCP uses a pseudo-header in its checksum calculation. Make sure you understand how TCP

checksumming works to ensure interoperability with the TA binary. You may consult online

resources as needed

•

You should

not

use arbitrary sleeps in your code. For example, you might have a thread

which takes care of all your transmission. You shouldn’t have this thread check whether there

is something to be sent every 1 ms, because 1 ms is an eternity on a fast LAN connection.

bqueue, and pthread_cond are your friends.

•

Never send packets greater than the MTU(same as IP). Even if you implemented fragmentation

in your IP, you should assume that fragmentation is not supported.

•

You don’t have to handle any TCP options. You can ignore any options that you see in

incoming packets (but don’t blow up!).

http://www.tcpipguide.com/free/t_TCPChecksumCalculationandtheTCPPseudoHeader-2.htm

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

•

When should v connect() timeout? A good metric is after 3 re-transmitted SYNs fail to be

ACKed. The idea is that if your connection is so faulty that 4 packets get dropped in a row,

you wouldn’t do very well anyway. How long should you wait in between sending SYNs? You

can have a constant multi-second timeout, e.g. 3 seconds. Or, you can start oﬀ at 2 seconds,

and double the time with each SYN you retransmit.

• The RFC states that a lower bound for your RTO should be 1 second. This is way too long!

A common RTT is 350 microseconds for two nodes running on the same computer. Use 1

millisecond as the lower bound, instead.

4 Tips

A few tips:

•

Log as much as you can, and make it possible to ﬁlter out what you care about. For example,

you may only want to log information related to a speciﬁc connection, or you may only want

to see logs from TCP, and not IP.

•

Debugging TCP can be very diﬃcult, and sometimes your own logging isn’t enough. Therefore,

we suggest using Wireshark, an industrial-strength packet analyzer. It will allow you to collect

packets travelling over your network cards and ﬁlter them by diﬀerent queries. With some

minor conﬁguration, you can tell Wireshark that you are embedding IP packets inside of UDP

packets.

•

Take a look online for guides on proﬁling your language. For a lot of languages you can use

gprof, CallGrind and KCacheGrind (for example, C, Go and OCaml all allow you to use this).

5 Grading

5.1 Milestone I – 5% (Nov 1)

Set up a meeting with a TA for anytime by the milestone due date. You should demonstrate that

your implementation can establish connections, properly following the TCP state diagram under

ideal conditions. Note that connection teardown is not yet required for Milestone I.

It should work with itself and our reference implementation.

Also show that your TCP works even with another node in between the two endpoints. Your IP

and routing should make this trivial. Note that this sounds redundant, but doing this early in the

development of TCP will ensure you ﬁnd any lingering bugs in your IP implementation.

5.2 Milestone II – 20% (Nov 8)

Set up a meeting with a TA for anytime by the milestone due date.

Students should have the send and receive commands working over non-lossy links. That is, send

and receive should each be utilizing the sliding window and ACKing the data received to progress

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

the window. This also means that sequence numbers, circular buﬀers, etc. should be in place and

working.

Retransmission, connection teardown, packet logging and the ability to send and receive at the same

time are not yet required. The ﬁnal implementation, will, however require these functionalities be

implemented correctly.

5.3 Basic Functionality – 55%

As usual, most of your grade depends on how well your implementation adheres to these speciﬁcations.

Some key points:

• Properly follow the state diagram.

• Adhere to the ﬂow control window.

• Re-transmit reasonably. Calculate SRTT and RTO.

•

Send data

reliably

. Files sent across your network should arrive at the other end identical to

how they were sent, even if the links in between the two nodes are lossy.

• Follow the RFC in corner cases.

The idea is that having full basic functionality means that any existing valid TCP implementation

should be able to talk with yours and eventually get data across, regardless of how faulty the link is.

5.4 Performance and Documentation – 20%

Part of this grade will be your TCP’s speed. Your implementation should achieve speeds of at least

8 megabytes/second (that’s 64Mb/s) on two nodes connected directly to each other, both running

on the same computer, with a perfect link. It should also not perform terribly if the link is slightly

faulty.

We want you to understand how your design decisions aﬀect your TCP’s behavior, so another part

of the grade will be a README stating all design decisions you made, and why.

The rest will be a packet trace. You should send a 1 megabyte ﬁle, as speciﬁed in the Driver section,

and have your TCP record all the packets that are sent and received on each end, along with a

nanosecond timestamp of when the packet was sent, the sequence number and size of the data in

the packet, and the ack number of the packet. You should annotate the ﬁrst few hundred of these

packets with key events, saying why particular events occurred. Run your connection through a

faulty node with a 2% drop rate.

You don’t have to write too much about the packets that get to the other end safely. The interesting

things happen when packets get dropped. When this happens, let us know how this aﬀects your

congestion window, how your implementation reacted and retransmitted the dropped packet, etc.

Let us know which of your design decisions caused this behavior.

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

6 Getting Started

6.1 C Support Code

We’ve given some C support code, in

/course/cs168/pub/tcp

. If you are not using C, it is not

important for you to read these ﬁles.

• util/bqueue.c util/bqueue.h

: A blocking queue. See the header and source ﬁles for

instructions on how to use it.

• util/circular_buffer.c util/circular_buffer.h

: A circular buﬀer, which will probably

be useful as you implement the sliding window buﬀer.

• node.c

: Code for a driver that implements all functionality that only uses the TCP API

functions, e.g. connect, sendﬁle, etc. It only has holes for implementation-speciﬁc functions

such as up, down, routes, etc. Feel free to take this code and use it for your driver.

• node_readline.c

: The same thing as

node.c

except that it uses lib readline. This means you

can use up down arrow keys to scroll through your command history and tab to auto-complete

ﬁle path. This will make your experience with your console much better. Compile it with

-lreadline.

We’ve also modiﬁed the debugging macros to prepend messages with a timestamp. These are also

in the util directory.

6.2 TCP Reference Implementation

Available in

/course/cs168/pub/tcp

node

. You can specify a drop rate as the second parameter

at the command line, to simulate lossy links. The drop rate should be a value between 0 and 100,

where 100 means every packet will be dropped by the node.

7 Handing In and Interactive Grading

Once you have completed the project you should run the electronic handin script

/course/cs168/bin/cs168 handin tcp

to deliver us a copy of your code. Your mentor TA will arrange to meet with you for your interactive

grading session to demonstrate the functionality of your program and grade the majority of it. This

meeting will take place at some point shortly after the project deadline. Between the time you’ve

handed in and the demo meeting, you can continue to make minor tweaks and bug ﬁxes (and you

should, since it will be the code base for your next project). However, the version you’ve handed in

should be nearly complete since it could be referenced for portions of the grading.

CS168 Project 3: TCP over IP over UDP 11:59 PM, Nov 25, 2014

8 Final Thoughts

Although we expect compatibility between your TCP implementation and our own, do not get

bogged down in the RFC from the start. It is much more important that you understand how TCP

works on an algorithmic/abstract level and design the interface to your buﬀers from your TCP stack

and from the virtual socket layer.

Don’t tackle the RFC until you’re sure that you have your head wrapped around the assignment. For

any corner cases or small details, the RFC will be your best friend, and our reference implementation

should come in handy. You should read it and consult the TA staﬀ if you have any questions about

what you are required to do, or how to handle corner cases. It is

not OK

to just make assumptions

as to how things will work, because we will be testing your code for interoperability with other

groups in the class.

Please let us know if you ﬁnd any mistakes, inconsistencies, or confusing language in this or any

other CS168 document by ﬁlling out the anonymous feedback form:

http://cs.brown.edu/courses/cs168/f14/feedback.html.