Overview

Your task in this project is to extend your networking package with 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 missed 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 on top of 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. A correct implementation is sufficient - you don't need to worry too much about performance. For instance, it's fine to build a system that has only one packet in transit at any given time on any given socket (that is, a window size of one). Obviously, this makes the roundtrip time of the network the dominating factor in performance, but it simplifies the implementation greatly.

You should remove the previous project's restriction on the maximum acceptable message size. With minisockets, it should be possible to send a message of any size, instead of one limited by the network's maximum datagram size.

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 send 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 closed.

To open and close a connection and to acknowledge sent packets you need special packets, that we will call control packets, that usually contain no user level data. Also every packet has to contain some extra information (like sequence number). This extra information that cannot be accommodated in the miniports header should be stored in an extra header, that is used only in packets belonging to connection based communication. Since the unreliable, connectionless communication provided by miniport has to coexist with the reliable, connection based communication provided by minisockets, you have to add a "type" field to the miniports headers that specifies the type of communication. Your implementation should use the information in this field when a packet is received to determine if it 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 schedule a timeout when it sends a packet, so that it can detect when an acknowledgement doesn't arrive "fast enough", and resend it (since the ack may have been lost, this is an additional source of duplicates at the receiver).

Sending a message should be a blocking operation, completing when the message is acknowledged, or when the minimsg 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.7 seconds have passed, stop trying to send and return an error (n.b. this means that you should stop after the 7th send times out).
4. If the send is acknowledged, or is aborted because 12.7 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 side within a given timeout period. Note that if the ACK is lost, the receiver may get multiple copies of the data packet. Consequently, the receiver will have to keep track of which date 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.

Removing the maximum message size on send operations means that you now have to fragment large messages into packets, each of which is no bigger than the MAX_NETWORK_PKT_SIZE constant. This introduces a problem: how do you reassemble messages at the receiver's side? There are two possible approaches: (i) a "message-oriented" scheme, or (ii) a "stream-oriented" scheme. In the former, you would preserve message boundaries at the receiver, so that it is possible to reconstruct the lengths of the messages sent by the sender. With the latter, you would ignore message boundaries at the receiver. For this assignment, you will implement a stream abstraction. A stream abstraction simplifies your 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.

You should follow the following guidelines in implementing the stream-oriented protocol:

1. You have to implement the functions in header minisocket.h . You can add functions to this header of minimsg.h but you cannot change the interface of the functions already provided, as that would break our testing code (i.e. existing applications).
2. You have to make sure that sockets are used one-to-one, i.e. only one socket will be sending packets to only one other socket. This simplifies your sequence number management. Any attempt to open a new connection to an already used socket (i.e. socket to which there is a connection already made) should result in an error packet send back. Also, to make debugging easy, if a port number is used by miniports it should not be used by minisockets.
3. You cannot assume that only one thread will use a given port. Multiple threads may try to perform sends or receives on the same port. The semantics are that only one thread performs a given send or receive at any time, while the others wait (i.e. entry to minimsg routines should be protected by a mutex where necessary). This means that the packets sent by multiple threads may be interleaved in any arbitrary order. Similarly, multiple threads performing receives may see the data interleaved in any arbitrary order. The end-to-end argument states that any application that uses ports in a multithreaded style should be smart enough to do the demultiplexing on its own (e.g. such an application may have redundant data in the packets, or all packets may have length descriptors, or they may contain complementary information that goes into a shared data structure regardless of which handler thread receives it).
4. Your code should not have a maximum message size limitation. If a thread performs a large minimsg_send, your minimsg layer should chop it into smaller (around 8K, but in any event less than 64K) blocks.
5. 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. minimsg_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.
6. Opening a connection should be made with the following handshaking protocol: the client machine sends an open connection packet to the server machine, if no thread is waiting for a connection on the specified port (has executed minisocket_server_create on the port the client machine is connecting to) a no server reply should be send to the client; if a thread is waiting a open connection ack should be send back. On the client side, if an open connection ack is received, an ACK message should be send back. From this moment on the both parties consider the connection opened. The same strategy as for the send/receive should be used here to ensure reliable communication (retransmissions).
7. Closing of the connection can be initiated by any of the parties in the communication. A connection close 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 ACK's. Any atempt comming from the applications to send new messages on a closing connection should be replied with a connection closed error message. When the connection is considered closed new connections on the same port can be accepted.

How to Get Started

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 systemwork correctly with really large send operations ? See if the receiver gets all the data the sender sends if it performs minimsg_receive() operations with a buffer which is too small. The test cases for project 3 are not sufficient to test your work: part of the challenge of this project is to develop your own tests, making sure that you've written code which implements the specification correctly.

You should also test your code by randomly dropping packets and seeing if your networking stack continues to deliver messages. If you randomly drop packets with 10% probability (i.e. pick a random number between 0 and 9, drop if you got 1), you would not expect to see any delivery failures unless you send around 10^8 packets (why?). So any 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 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 for any given packet, and that it doubles with every subsequent retry.

Submissions

The project is due at midnight on April 8th.

You should follow the generic submission guidelines to submit this project. Make sure you use the correct project number (4).

For the Adventurous

Add a message window of fixed size (WS). Measure the bandwidth your code achieves with WS set to 1 and WS set to 4.

Dynamically adjust the window size. Increase it by one if you are getting all the packets acked, and divide it by half when a packet is not acked.

Final Word