Overview

Your task in this project is to extend your networking package to provide reliable delivery.

The previous assignment developed an unreliable networking layer, with ports as endpoints. Data sent from one host to another could be lost in the network. The applications would not know if their data made it across, or whether it got lost. Needless to say, this is not a good programming model for most applications. In practice, best-effort delivery is often an insufficient guarantee for application writers; only a few applications such as streaming video are able to adapt to lost packets at the receiver side, without requiring retransmissions. Adding the notion of connection also helps user level programming since the communication between the applications can be viewed as a stream.

While it would be possible to require every application designer to write a reliable network protocol along side our UDP-like protocol, there are powerful reasons to provide a standard reliable protocol. First, it is unquestionably more convenient: writing an efficient protocol is nontrivial. Second, there is an important incentive in standardizing the one reliable transport protocol, since these protocols must incorporate mechanisms for flow control and congestion avoidance. The more protocols which are in use, the harder it is to predict how they will contribute to the overall behavior of the network. One of the reasons why TCP has been so successful is that its behavior under adverse conditions is well understood.

For this project, you need to implement minisockets, a connection-based reliable communication channel abstraction which is a simplification of TCP.

Your implementation will overcome restrictions that the previous project imposed on the message length. With minisockets, it should be possible to send a message of any size, instead of one limited by the network's maximum datagram size. To accomplish this, your implementation will fragment and reassemble the packets such that the receiver is provided with the illusion of a continuous stream of data.

The Details

For this project you have to deal with connection based communication. What this means is that you need the notion of connection, i.e. binding between ports on two machines. Before actual communication starts a connection has to be made (both parties have to agree that packets sent from particular ports belong to the connection), communication is made on the connection (the user program has to specify on what connection the communication is made, i.e. the minisocket_t, not the source and destination ports as in the previous assignment) and the connection is eventually closed when either endpoint decides to terminate the communication session.

To manage a connection and to acknowledge sent packets you need special packets, that we will call control packets (the various message types can be found in miniheader.h), that usually contain no user level data. Also every packet has to contain some extra information about the sequence number and acknowledgement number. This extra information will be stored in the mini_header_reliable structure, which is an extension of the header format you saw in project 3. Your implementation should use the information in the protocol field to determine if a packet should be handled by your previous code (miniports) or by the new code (minisockets).

To ensure reliable delivery, you will have to cope with packet losses and duplicates. This means that the receiver has to acknowledge each packet which arrives and maintain information about the packets it has already seen, to detect duplicates. The sender has to set a timeout when it sends a packet, so that it can detect when an acknowledgement doesn't arrive "fast enough", and resend the packet (since the ack may have been lost, this is an additional source of duplicates at the receiver).

Opening a connection

Opening a connection should be made with the following handshaking protocol: the client machine sends a MSG_SYN packet to the server machine. If no thread is waiting for a connection on the specified port, the server should not respond. After 7 retries without getting a response, the client can conclude that the server does not have the port open and return SOCKET_NOSERVER to the user.

On the other hand, if a server thread is waiting on the specified port (ie, has executed minisocket_server_create() on the port the client machine is connecting to), the server should send an MSG_SYNACK to the client. The client, upon receipt of this message, should acknowledge the server by sending MSG_ACK. At this point, the connection is open and ready for data transfer.

Note that MSG_SYNACK is subject to retransmission until either the server receives a MSG_ACK or times out (in which case the server should reset the port and go back into listening mode).

You have to make sure that sockets are used one-to-one, i.e. one socket will be sending packets to only one other socket. Any attempt to open a new connection to an already used socket (i.e. socket to which there is another connection already made) should result in an MSG_FIN packet sent back to the client. The client should report this as a SOCKET_BUSY error.

Sending and retransmissions

Data is sent by setting the message type to MSG_ACK and appending the data to the reliable header. In other words, a MSG_ACK can be used both as a control packet and as a packet that contains data.

Sending a message should be a blocking operation, completing when the message is acknowledged, or when the minisocket layer "gives up" and returns a partial result or an error. Obviously, introducing reliable sends adds the problem that a sender may block indefinitely, retransmitting a message to a receiver which does not exist or is not responding. To avoid indefinite blocking, you should use the following scheme for timeouts and retransmissions:

1. Set the initial timeout to occur 100 ms after the first send.
2. Each time the timeout expires, resend the message and double the timeout interval.
3. After 12.8 seconds have passed, stop trying to send and return an error (this means that you should stop after the 7th send times out).
4. If the send is acknowledged, or is aborted because 12.8 seconds have elapsed, reset the timeout value to 100 ms.

For reliable delivery in the face of lost packets, you will have to retransmit data packets if you don't get an acknowledgement from the remote end within a given timeout period. Note that if the ACK is lost, the receiver may get multiple copies of the data packet as the sender retransmits in an effort to get an ACK from the receiver. Consequently, the receiver will have to keep track of which data packets it has seen, and suppress duplicates. Also note that the sender might get duplicate ACKs, especially if some ACKs get delayed in the network.

Retransmissions may also be necessary if one end indicates that it did not receive a message that was earlier sent from the another endpoint. This condition is detected through discrepancies between the sender's sequence number and the receiver's acknowledgement number. Refer to the slides for more information about sequence numbers and acknowledgement numbers.

Receiving and acknowledgements

Since the MSG_ACK message type serve a dual purpose, we distinguish them into two classes: user data packets and acknowledgement (control) messages.

All user data packets (ie. MSG_ACK packets that have data after the reliable header) need to be acknowledged. An acknowledgement message is simply a MSG_ACK that does not contain any data after the reliable header. Acknowledgement messages should not be further acknowledged.

You can assume that only one thread will send to a given port. However, multiple threads may try to perform receives on the same port. The semantics are such that only one thread advances through the receive function at any time, while others wait. Multiple threads performing receives may see the data interleaved in any arbitrary order. It is up to the user to handle such interleaved reads and to merge them back into something sensible, so you do not have to worry about these details.

If a thread performs a partial receive, e.g. the packet has 2000 bytes but the receiver thread reads only 500 bytes out of it, the rest of the data in the packet must not be discarded. minisocket_send should return the number of bytes successfully delivered to the remote side. If someone attempts a 20M send and gets only 800K across when a packet times out, send ought to return 800K.

Fragmentation

Your code should not have a maximum message size limitation. If a thread performs a large minisocket_send, your minisocket layer should fragment it into smaller blocks. The total size of each block (inclusive of the header) can be arbitrary but this must not be bigger than the maximum transmission unit of the underlying network layer (which is defined to be MAX_NETWORK_PKT_SIZE, or 8192 bytes). The size you select for each block can be arbitrary because minisockets does not depend on message sizes for correctness. However, to minimize overhead (ie. the ratio of bandwidth spent on sending headers vs. the actual data), usually the largest possible fragment size is selected.

Together with fragmentation, you will also implement a stream abstraction. A stream abstraction simplifies your recieve implementation in many ways, and parallels TCP's behavior. For instance, if you chop a large send into multiple small packets, you don't need to wait for all of the pieces to arrive on the receiving side before you wake up the receiving thread.

Closing a socket

Closing of the connection can be initiated by any of the parties in the communication. A MSG_FIN message is sent to the other machine and an ACK is expected back. The retransmission strategy from send/receive shuld be used. The initiator of the closing considers the connection closed when the ACK is received or when the 7 retransmission fail. The other machine considers the connection closed after 15s from the moment it got the closing request and it sent the first acknowledge. If multiple closing requests come all should be replied with ACKs. Any attempt by applications to send new data on a closing connection should be replied with a SOCKET_SENDERROR error message. When the connection is closed new connections can be made on the same port.

How to Get Started

Make a backup copy of your code from the previous project, download the code from CMS, and merge.

You have to implement the functions defined in minisocket.h. You can add functions to minimsg.h or minisocket.h but you cannot change the interface of the functions already provided, as that would break our testing code (ie. existing applications).

How to Test Your Code

It's crucial that systems code be correct and robust. You must test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly. At a minimum, you should test sending large numbers of messages and check if they're all received. Does your system work correctly with really large send operations?

Verify that the receiver can get all data from a sender if it performs minisocket_receive() operations with a small buffer. The provided test cases are not sufficient to comprehensively test your work: part of the challenge of this project is to develop your own tests and to make sure that you've written code that implements the specification correctly.

You should also test your code by randomly dropping packets and seeing if your networking stack continues to deliver messages. For convenience, we have included two variables, loss_rate and duplication_rate that you can modify in network.c to test the robustness of your code. Make sure to set synthetic_network to 1 before you adjust these variables. If you randomly drop packets with 10% probability, you would on average expect to see a catastrophic delivery failure after 10^8 packets (why?). So, any frequent delivery failures when you have low packet loss indicate a problem.

A common error is to wait for a timeout before waking up a sending thread, even though an ACK may already have arrived. Make sure you build your network layer so that the sending thread is awakened immediately if the ACK arrives, and that it is awakened eventually by the timeout mechanism if the ack does not arrive.

Another common error is to mismanage the timeout periods. Make sure that the initial timeout period is 100 ms for the first try of any given packet, and that it doubles with every subsequent retry.

Submissions

Use CMS to submit your project. You should include a README file with your name, your partner's name, and anything you think we should know. This includes documenting any broken functionality.

Final Words

Although the TAs will not be physically present in school this week, should you need assistance with any part of the assignment, we are here to help.