CSE logo University of Washington Computer Science & Engineering
 CSE 461: Computer Communication and Networks (Winter 2007)
  CSE Home   About Us    Search    Contact Info 

Course home
 Using course email
 Email archive
 Lectures and readings
 Section and tutorials
 Midterms and exams
Lab information
 Getting lab accounts
 Unix tutorials

Project 3: Reliable Transport and Congestion Control

Your assignment is to design and implement a protocol for reliable transport, that is, a simplified version of TCP. Your code will complement and make use of the code you wrote for previous assignments to do naming, flooding, and routing.

Reliable Transport

Your job is to design and implement a transport protocol with the following features. For transport packets, use the TRANSPORT_PKT protocol. The packet payload should be a packed object of class Transport.

Connection setup/teardown: A connection is identified by a four-tuple, the combination of a source and destination fishnet address plus a source and destination port value. Our connection state machine is considerably simpler than the one described in Peterson for TCP. Specifically:

  • First, connections are one-way byte streams, not two-way as in TCP. (Of course, you can easily build two-way byte streams on top of two one-way byte streams.)
  • Second, we assume a simpler hand-shake mechanism. As with TCP, each connection should be established before data is transferred and torn down after all data has been transferred. The sender initially sends a connection request to the receiver, by picking an initial sequence number and setting the SYN flag. The receiver then replies with an acknowledgment packet (with the ACK flag set). The transfer can then proceed.
  • Teardown is also simple -- either side closes the connection by sending a packet with the FIN flag set. FIN should also be used to indicate "connection refused" when there is no application awaiting connections on the destination port.
  • Unlike in TCP, packets with the SYN, ACK, or FIN flag never carry payload data.

You must support multiple, concurrent connections. We suggest that you define your own transport connection structure, with your node having an array of such structures, one per connection in use. The structure will encode all state associated with a connection, including sequence numbers, buffered data (both sent awaiting acknowledgment and possible retransmission, and received awaiting processing by the application), and connection state (such as established, the SYN has been sent but not acknowledged, etc.).

Reliability and Sliding Window: Each payload packet should be transmitted reliably by using sequence/acknowledgment number field and timeouts and retransmissions.

  • The sequence number advances in terms of bytes of data that are sent.
  • The acknowledgement number operates as in TCP to give the next expected in-order sequence number, and an acknowledgement should be sent every time that a data packet is received. That is, the acknowledgement number does not increase when a packet has been lost until that packet has been retransmitted and received. (Note that since an ACK never carries data, we put the acknowledgment number in the Transport header sequence number field.)
  • Note that packets carry both a sequence number in the packet header (which is unique among all packets sent by this node), and a sequence number in every transport header (which is the place within the byte stream for this data or ACK packet). These two roles for sequence number are semantically distinct, and in fact, the IP header has its own unique identifier field separate from the sequence number in TCP's header.
  • We recommend that you first implement a "stop and wait" style scheme, where only a single packet can be outstanding at a time. Once that is working, implement a fixed-size sliding window.

Flow control: Your protocol should use the advertised window field along with the sequence and acknowledgement numbers to implement flow control so that a fast sender will not overwhelm a slow receiver. The advertised window field tells the other end how much buffer space is available to hold data that has not yet been consumed by the application. 


As usual, you should strive to come up with a design that will interoperate with other students' nodes. As you do, take the following steps:
  1. Build a "transfer" command into your node that, on the sender side, sets up a connection to another node and sends a well-known test pattern to the other side, and tears down the connection. On the receiver side, your node should check that the test pattern is expected and provide feedback about the success or failure of the overall transfer. This command is purely an expedient way to test your transport protocol. For the transfer pattern you should use a configurable number of fixed sized packets, 512 bytes by default, whose contents are all bytes with values of N for the Nth packet, e.g., all 1s for the first packet, 2s for the second, etc., and using a specific port, 1, for both source and destination.

  2. At the sender and receiver, print the following single letter codes, without a newline, when a packet of the appropriate type is sent or received:

    • "S" for a SYN packet
    • "F" for a FIN packet
    • "." for a regular data packet
    • "!" for a retransmission at the sender or duplicate at the receiver
    • ":" for an acknowledgement packet that advances the acknowledgement field
    • "?" for an acknowledgement packet that does not advance the field

    These codes will give you visual feedback to help you gauge the progress of a transfer and give us a trace for your turnin. If you print the codes as specified above, a successful connection will appear as a sequence of mostly dot characters marching across your screen.

  3. Run your Fishnet with a relatively high level of packet loss (5%, say) to check that lost data is successfully retransmitted. Packet loss on a given link can be specified in the topology file provided to the simulator or trawler (for example: edge 0 1 lossRate 0.05 delay 5 bw 10) to establish a link between node 0 and 1, with a 5% loss rate, 10KB/s bandwidth, and 5 millisecond propagation delay. You can also generate sample topologies using topogen's "-l" flag.

Discussion Questions

  1. Your transport protocol implementation picks an initial sequence number when establishing a new connection. This might be 1, or it could be a random value. Which is better, and why?
  2. Your transport protocol implementation picks the size of a buffer for received data that is used as part of flow control. How large should this buffer be, and why?
  3. Our connection setup protocol is vulnerable to the following attack. The attacker sends a large number of connection request (SYN) packets to a particular node, but never sends any data. (This is called a SYN flood.) What happens to your implementation if it were attacked in this way? How might you have designed the initial handshake protocol (or the protocol implementation) differently to be more robust to this attack?
  4. What happens in your implementation when a sender transfers data but never closes a connection? (This is called a FIN attack.) How might we design the protocol differently to better handle this case?

Turn In

Turn in electronic material as follows.
  1. Run a two-node fishnet emulation. Perform a reliable transfer of at least 100 packets. Capture the output (from both the sending node and the receiving node) and mark it up to tell us what is going on. (It's fine if the output includes only your commands and the "SF.!:?" characters as described above.)

  2. Use the turnin program to electronically submit one or more Java files containing the source code of your solution.

  3. Your turnin should also include (in addition to both partner's names):
    • A brief design document.
    • Short answers to the discussion questions.

Grading guidelines

Each part of the project is graded on a 5 point (0-4) scale, multiplied by the weight of the part. The weighted grades from all parts of the project are added together to produce the final grade. There is an extra credit component to this project.

The five point scale is based on how well you show your understanding of the problem, and in case of code how well your implementation works:

0 - nothing turned in
1 - show minimal understanding of the problem / most things don't work
2 - show some understanding of the problem / some things work
3 - show a pretty good understanding of the problem / most things work
4 - show excellent understanding of the problem / everything works

The weights for the parts of project 3 are:

Transport layer implementation: 1/2 of total grade
Write-up of your design decisions: 1/4 of total grade
Answers to discussion questions: 1/8 of total grade
Print-out of captured output: 1/8 of total grade

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX