ADEN (2)

PREFACE

ADEN project provides a reliable, message-based transfer protocol over UDP/IP designed as a high-performance alternative to TCP for low data-volume applications and bulk transfer over a LAN (see first article about ADEN).

ADEN Protocol (summarized) 

Communication is initiated by a two way handshake to exchange a pair of unique identifiers. The peer that initiated the handshake -which represents the client of the client-server model- can then send messages to the other peer -which represents the server of the client-server model. After receiving the first message, the server can also send messages to the client. 
To send a message, the sender protocol associates the identifier received earlier from the receiver with each packet it sends. A sequence number is also associated with each packet to allow ordered delivery. If the user message can not be enclosed in a single UDP datatram, the sender protocol fragments it into a number of segments each is transmitted in a single UDP datagram. The payload size of a UDP datagram is predefined by user (default is 512). 
The sender may send up to n packets continuously, then stops and waits for the receiver to acknowledge the last transmitted packet, as an indication of successful reception of all the transmitted packets. As long as the last packet is not yet received, the receiver continues to receive packets silently, performing any necessary reorder. If the last packet is received, the receiver reports its state to the sender. If the receiver's reply indicates that a packet were missing, the sender retransmits the missing packet then continues to wait for the next reply. If no valid reply is received before a specific time the sender retransmits the last packet. The sender fails after if a number of consecutive timeouts. The value of n is predefined by user.
Communication is normally terminated by the client sending a zero-bytes message to server. After that resources associated with the connection can be disposed on each side. Server can also be made to dispose connections without prior agreement when no messages are received for long time.
 

ADEN Protocol (detailed)

ADEN protocol  can be described with minimum details as following:  

 Sender protocol

step1 -  If there are no more packets halt, otherwise send N packets then go to step2.

step2 - Wait until a reply is received or RTO seconds has passed, whichever happens first, then go to step3

step3 - If there is a reply go to step4 otherwise go to step5.

step4 -If the reply is an ACK recalculate RTO then go to step1, otherwise if the reply is a negative acknowledgment (NACK) indicating a missing packet, and that packet is not retransmitted since the last timeout, then retransmit that packet then go to step2, otherwise go back to step2 and continue waiting.

step5 - If the maximum number of timeouts is not yet reached then retransmit the Nth packet, set RTO = 2 * RTO then go to step2, otherwise fail.

 

The packet blocking concept

User message is fragmented into a number of segments (depends on the message size and the configured payload size of UDP datagrams). Each segment is enclosed in a single UDP datagram. These packets are transmitted in a number of cycles. On each cycle, the Sender sends N packets (except maybe in the last cycle) or a single block, then waits for Receiver's acknowledgment of the transferred block. Receiver must send a reply that indicates correct reception of the last packet of the block in order to to confirm successful reception of the entire block (such reply we call ACK). If the Receiver receives the last packet of the block while a number of packets are not yet received, the Receiver's reply must indicate the last packet received orderly, making the sender retransmits the next packet (such reply we call NACK). If the Sender did not receive any valid reply before a specific time, it retransmits the last packet of the block. Retransmissions timeout or RTO is calculated using RoundTripTimer class borrowed from Esmond Pitt's book Fundamental Networking in Java (see class com.aden .util.RoundTripTimer).

Receiver Protocol

step1 - Wait until a packet is received then go to 2.

step2 -  If the received packet incloses a new segment go to step3 otherwise go to step4.

step3- Put the segment into new_message_buffer in its correct position, if all segments are successfully received put the complete message in the message queue, clear new_message_buffer and notify user thread. Go to step4.

step4- If the packet asks for ACK then if there is no missing segment - i.e. no non-adjacent segments in  new_message_buffer - put ACK in out-buffer otherwise put NACK in out-buffer. Go to step5.

step5- If out-buffer is not empty then send its content. Go to step1. 

The Sender uses the last packet of the block and retransmitted packets to tell the Receiver that he must report his state to the Sender. Normally, a special flag in packet's header is used to distinguish between such packets and other packets that should be received silently by the Receiver. Note that both ACK and NACK indicates the last packet received orderly by the Receiver.

Congestion Control & the choice of appropriate value for N

After sending N packets, the transmission suspends until all packets are received. If packets were dropped by network due to congestion, the suspension will increase proportionally. That should give a chance to a temporarily congested network to clear congestion and prevents worsening it. However, this technique is less efficient if N itself is too large that many packets are almost always dropped (you can use ADEN's logger to see how many packets are retransmitted per cycle). 

If you are using ADEN on internet, N should be 1. The packet blocking technique is not appropriate for the internet because it does not control the send rate of UDP datagrams. When running on a LAN, you can increase N (or blocksize) to increase throughput. Normally, you should set N to the maximum effective value, i.e. the size of the largest application message - in packets.
 
Given the message size in bytes, you can calculate message size in packets as follows:

messageSize_inPackets = Math.ceil((messageSize - datagramLen - 21) / (datagramLen - 17));

Where datagramLen is the configured payload size of UDP datagrams in the ADEN instance. 21 and 17 are the sizes of ADEN's header in the first packet of an outgoing message and the subsequent packets respectively.

However, you may have to set N to a lesser value; especially on a heavily loaded LAN or when the message is extremely large. Therefore, it might be necessary to test ADEN on the given LAN with different values of N to determine an appropriate value (see performance test results).

The packet structure

The protocol data unit is called 'packet' which is transferred in a single UDP datagram. A packet may enclose application data (a user message or a segment of a user message) or a reply (ACK or NACK). For the former case we will use the term data packet or just packet to refer to the packet. For the later case we will use the term feedback packet or just feedback.

datagramLen is the maximum payload size of a UDP datagram, and is predefined by user. Default is 512 bytes.

blocksize is the maximum number of UDP datagrams in a single block (see sender protocol above), and is also user-defined. Default value is 1.

ADEN's header in both packets and feedbacks is 17 bytes, except in the packet that encloses the first segment of the user message; where additional four bytes are used to hold the message size. So given datargamlen equals 512, the maximum payload of a packet is 491 bytes if it is the first packet of a message and 495 bytes if it is not. Note that at application level, a message is the smallest transmittable/receivable data unit not a packet. In other words, a message can not be partially sent or partially received.

The protocol header is composed of three fields which are - by order:

-8-bit control flag 

Used for various purposes. For example, to indicate the type of the data in the UDP datagram payload, i.e. a packet or a feedback. Also used to  indicate a packet that incloses a connection message and the corresponding feedback.

-64-bit connection_id
A unique identifier of the connection to which the packet/feedback belongs, and is obtained during connection setup (explained later).

-64-bit sequence_number

Indicates the sequence number of the enclosed segment or the sequence number the expected segment (if this is a feedback).

The header of the packet that contains the first segment of a message has additional four bytes used to hold the length of that message in bytes.

Note about the sequence_number field:

This field is incremented by the payload length of the transmitted/received packet rather than by one. This way the protocol can cope with platforms where partial datagram reception is possible (Java is one example - the reason is probably to prevent running out of memory when available memory for JVM is low).

  

Connection establishment

connection setup can be explained using Server-Client analogy, as follows:

When Client sends a message to Server for the first time, ADEN generates a unique 64-bit id and use it as connection_id in the header of the outgoing packet. When the Server receives that packet, likewise it generates a unique 64-bit id and put it in the feedback body.
After this exchange each end has two connection_ids for this connection, one generated locally or local_id and one obtained from the remote end or remote_id. Note that the uniqueness of connection_ids has to be maintained within the local host only.

The general criteria of the Client's first message or connection message is that it should not be used to invoke a non-idempotent computation on the Server or be larger than one packet. Other than that it is an ordinary message. 

The Server must receive at least one more message from the client after receiving the connection message, otherwise the Server must not send messages on that connection, and must consider the connection invalid and drop it if no messages is received before an application-specific time.

Passing data in both directions

The Sender uses the id it obtained from the Receiver (i.e remote_id) as the connection_id in packet's header. Except the packet that encloses the connection message, where the Sender (it is the client in this case) uses its local_id as connection_id. On the other hand the Receiver uses its local_id as the connection_id in feedback's header. Except the feedback corresponding to a connection message, where the Reciever (it is the server in this case) uses the the remote_id as connection_id while the local_id is put in the feedback body (Note that except this one, feedbacks have no body).

For the Sender, the sequence_number of the next packet must equal the sequence_number of the previous packet plus its payload (or zero if no packets are sent yet). For the Receiver,  the sequence_number of the expected packet equals the sequence_number of the last packet received orderly plus its payload (or zero if no packets are yet received). Note that this means the sequence_number of the connection message is zero, likewise the first packet from the server to client (no -if you ask - first packet from server to client cannot be confused as a connection message).

Connection termination

Synchronizing connection termination is handled entirely at application domain, at the end of communication a special message (EOF) should be passed in one direction. After passing this message both ends can dispose the connection object. Who should send EOF and who should wait for it is application-specific, a common practice found in TCP-based applications that the client starts the termination sequence; except that in ADEN it is a two-way not a four-way handshake.

Note that EOF message should not contain application data, sender should normally tolerate unsuccessful send of this message and continue normally.

Note that it cannot be guaranteed that the connection is always terminated in this clean way. Using 'read' timeout -at both ends of an ADEN connection- is the only way to prevent blocking indefinitely on a dead connection.

 ADEN source code & binaries.