Reliable UDP (RUDP) Author: Andrew Keating <andrewzkeating@gmail.com> May 31, 2011 This project implements a reliability layer on top of UDP in C. Reliability is achieved using sliding window flow control, ARQ-based retransmissions and detection of out-of-order packets. Usage notes: To compile, simply run make. This will compile the RUDP library and two applications which use RUDP. The sample applications are vs_send and vs_recv, a file sending application and a file receiving application. Run the receiver: ./vs_recv [-d] port Run the sender: ./vs_send [-d] host1:port1 [host2:port2] ... file1 [file2]... Note that vs_send supports sending multiple files simultaneously to multiple hosts, but both of these are optional - it is perfectly okay to send a single file to a single host. If executing both the client and server locally, be sure to do so in different directories. Note that vs_send and vs_recv are only sample applications. Other applications can be written using RUDP. The event callback system in RUDP was developed by Olof Hagsand and Peter Sjödin Author's note: The RUDP receiver code contains some rather complex nested logic. While it may benefit from refactoring, it is mostly a necessary evil due to RUDP's numerous protocol states and transitions. Technical notes: For state/session management, we maintain a list of RUDP sockets. Each RUDP socket has a list of sessions associated with the socket, in addition to function pointers for event handler functions which can be registered by applications. Each RUDP session is uniquely identified by the IP address and port of the peer with whom the session is established. We logically separate sender and receiver sessions, although a single session may contain both a sender session and receiver session if both parties exchange data. Within a sender session, we maintain a sliding window of transmitted but unacknowledged packets, a queue of packets which have not yet been transmitted, and the sequence number of the last packet transmitted. Within a receiver session, we maintain the sequence number of the last packet received. We utilize two types of events in RUDP – one which is triggered when data is received on a RUDP socket, and another which is triggered when we detect packet loss (via a timeout event). Applications can register two types of events using the RUDP API: one which is used to pass received data from the RUDP socket to the application, and another which handles other events. We support two other events: RUDP_EVENT_TIMEOUT, which indicates that a packet has been retransmitted more than RUDP_MAXRETRANS times, and RUDP_EVENT_CLOSE which indicates that an RUDP socket has been closed. RUDP heavily relies upon sequence numbers to provide reliability. An RUDP sequence number is an unsigned 32-bit integer, which is transmitted as a field in the RUDP header. When we send a SYN to initiate an RUDP session, a random sequence number is generated for the SYN packet. Subsequent packets are sent with incremented sequence numbers. ACK packets have a sequence number which is 1 greater than the sequence number of the packet they acknowledge. When comparing sequence numbers, we use macros which handle the multiple cases caused by potential integer overflow. As previously noted, RUDP sender sessions maintain a sliding window of transmitted but unacknowledged packets. The size of the sliding window is defined by RUDP_WINDOW. When the application provides RUDP with data to be sent, we determine whether any slots in the sliding window are open. If so, the packet can immediately be added to the window and transmitted. If not, we must queue the packet to be delivered once it can acquire a slot in the window. Upon receiving an ACK packet, we inspect the first item in the sliding window. If the ACK packet is intended to acknowledge the first window item, we remove this item from the sliding window and shift any subsequent window items to the left, creating space in the window for new packets to be sent. As long as RUDP_WINDOW is greater than 1, this scheme provides better efficiency than stop-and-wait flow control by allowing up to RUDP_WINDOW outstanding unacknowledged packets to be sent. When a non-ACK packet is sent in RUDP, a timer event is registered to occur after RUDP_TIMEOUT milliseconds. If the timeout event fires, the packet associated with it will be retransmitted, unless the packet has already been retransmitted RUDP_MAXRETRANS times, in which case we will trigger a RUDP_EVENT_TIMEOUT event. When we receive an ACK, the timeout event for the packet being acknowledged is canceled. In RUDP, timeout events represent the detection of packet loss. Since we do not utilize negative acknowledgments, we instead detect packet loss implicitly when an ACK is not received. When an application calls rudp_close on an RUDP socket, we attempt to terminate all RUDP sessions which exist on the socket. For each active sender session on the socket, we wait until all queued data has been successfully transmitted, after which we send a FIN message. When a corresponding ACK has been received for the FIN message, we consider the sender session to be complete. Similarly, we consider a receiver session to be complete after it has received and acknowledged a FIN. Once all sessions on the socket are complete, we close the underlying UDP socket, and if the application has registered an RUDP event handler, we fire a RUDP_EVENT_CLOSE event. Tested on Ubuntu 10.04 LTS. Verified memory leak-free by Valgrind.