|
|
|
|
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.
Requirements
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:
- 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.
- 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.
- 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
- 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?
- 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?
- 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?
- 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.
- 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.)
- Use the turnin program to electronically submit one or
more Java files containing the source code of your solution.
- 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
|