Skip to main content.

Nachos Phase 4: Protocol Spec

Overview

The Nachos Transport Protocol provides full-duplex, reliable, byte-stream communication with no message size limits. It runs on top of the nachos network abstraction, defined in nachos.machine.NetworkLink . User programs access the transport protocol via the nachos system calls connect(), accept(), read(), write(), and close() which are documented in nachos/test/syscall.h and in the project description.

A connection between two endpoints is uniquely identified by the tuple (local machine address, local port, remote machine address, remote port). A state machine is maintained for each unique conenction. The state transitions are covered in detail later in this document but first we give a brief overview of the life cycle of a connection. This overview omits many details related to handling error conditions -- the details are included in the full transition table below.

To establish a new connection between two endpoints, one endpoint first calls the connect() system call. This endpoint is referred to as the active endpoint. A process at the other endpoint (calledthe passive endpoint) must later call the accept() system call. As these system calls are invoked, the underlying protocol carries out a 2-way handshake. When a user process invokes the connect() system call, the active endpoint send a synchronize packet (SYN). This causes a pending connection to be created. The state for this pending connection must be stored at the receiver until a user process at the passive endpoint invokes the accept() system call. When accept() is invoked, the passive end sends a SYN acknowledgement packet (SYN/ACK) back to the active endpoint and the connection is established.

Once the connection is established both sides may send data packets. Each packet is labeled with a unique 32 bit sequence number. Upon receipt of a data packet, the receiver sends an acknowledgement packet (ACK) back to the sender. Like TCP, the Nachos Transport Protocol uses a sliding window. Unlike TCP, however, the size of the window is always fixed at 16 packets. It is the responsibility of the sender to ensure that it never sends more than 16 unacknowledged packets. To guarantee that all packets are eventually received, the sender must periodically retransmit any packets that have been sent but not yet acknowledged. The frequency of the retransmission process should be once every 20,000 clock ticks.

When an endpoint closes a socket (via the close() system call), it sends a stop packet (STP) to the remote endpoint to indicate it has no more data to send. The sequence number in the STP packet must be one greater than the sequence number of the last data packet sent before the socket was closed. The endpoint that receives the STP packet may continue to receive retransmissions of any lost data packets until it has received all packets up to the last sequence number before the STP packet. However, no data may arrive with a sequence number larger than the STP packet sequence number. An endpoint should also not send any new data after receiving an STP message from the other endpoint.

When the second endpoint closes a connection, the two endpoints execute another handshake to complete the close. The second endpoint sends a FINish packet to which the first endpoint responds with a FINish ACKnowledgement (FIN/ACK) packet. At this point, the connection is finished and any associated state or resources may be deallocated.

Packet Format

Every packet in the nachos hardware has a 4 byte header that includes the link addresses of the sender and destination. The transport protocol adds an additional 8 byte header with the format shown below:

0001020304 0506070809 10111213 14151617 18192021 22232425 26272829 3031
DSTPORT SRCPORT MBZ F
I
N
S
T
P
A
C
K
S
Y
N
3233343536 3738394041 42434445 46474849 50515253 54555657 58596061 6263
SEQNO

The header fields are:

State Machine

A connection can be in one of the following seven states at one time:

The following events may occur to cause state transitions:

The state transitions are summarized in the following diagram and detailed in the following table.

NOTE: There is a small bug in the diagram. The TIMER event in the CLOSING state should result in retransmission of the FIN packet.

State Event Action
CLOSED CONNECT send SYN, goto SYN_SENT, block
RECV dequue data, or fail syscall if none available
SEND fail syscall
SYN goto SYN_RCVD
DATA, ACK, STP protocol error
FIN send FINACK
SYN_SENT TIMER send SYN
SYN protocol deadlock!
SYNACK goto ESTABLISHED, wake thread waiting in connect()
DATA, STP, FIN send SYN
ACK protocol error
SYN_RCVD ACCEPT send SYNACK, goto ESTABLISHED
DATA, ACK, STP, FIN, FINACK protocol error
ESTABLISHED RECV dequeue data
SEND queue data, shift send window
CLOSE if send queue is empty, send FIN, goto CLOSING.
else send STOP, goto STP_SENT
TIMER resend unacknowledged packets
SYN send SYN/ACK
DATA queue data, send ACK
ACK shift send window, send data
STP clear send window, goto STP_RCVD
FIN clear send window, send FIN/ACK, goto CLOSED
FINACK protocol error
STP_SENT TIMER retransmit unacknowledged packet
DATA send STP
ACK shift send window, send data.
if send queue is empty, send FIN and goto CLOSING
STP clear send window, send FIN, goto CLOSING
FIN send FIN/ACK, goto CLOSED
FINACK protocol error
STP_RCVD RECV dequeue data
SEND fail syscall
CLOSE send FIN, goto CLOSING
DATA queue data, send ACK
ACK, FINACK protocol error
FIN send FIN/ACK, goto CLOSED
CLOSING TIMER send FIN
SYN send SYN/ACK
DATA, STP send FIN
FIN send FIN/ACK, goto CLOSED
FINACK goto CLOSED