Wednesday, April 9, 2014

ADEN (2)


ADEN's project provides a reliable connection-oriented protocol implemented on top of UDP/IP (see the first article about ADEN) .

ADEN Protocol (summarized) 

In ADEN protocol communication is initiated via a two way handshake, that is done by the client sending an application-specific control message to the server, after that the server is ready to receive data from client . Client sends one message a time, after receiving the first data message server can also send messages to client. A message can be of any length and is broken into a number of segments, each segment is transmitted in a single UDP datagram. Datagram's max payload is 512 bytes (max. segment length equals 512 minus ADEN's header). The datagram that contains the first segment also contains the message size. Sender sends a segment then waits for acknowledgement before sending the next segment.Communication is terminated by client sending a special message that tells the server to dispose the connection, also server can be made to dispose the connection 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 no more packets are left halt, otherwise send the next packet in the message.

step2 - Wait until the packet is acknowledged or RTO sec. has passed then go to step 3.

step3 - If the packet is acknowledged then go to step 1 otherwise go to step 4.

step4 - If the packet is retransmitted at least M times then fail, otherwise retransmit the packet and go to step2.  

The above algorithm describes how an application-level message that is fragmented into a number of packets is transmitted reliably. note that details are omitted for demonstration.
Congestion Control

-Roughly speaking, Congestion is controlled by varying the time between subsequent retransmissions. Note that Retransmission scheduling is TCP-inspired (Look in ADEN's source-code for class RoundTripTimer, which was borrowed from Esmond Pitt's book Fundimintal Networking in Java. Although the technique explained in the book is totally different, it helped a lot in designing the technique used in ADEN).

Receiver Protocol

step1 - wait until a packet is received or closed.

step2 - If closed halt, otherwise If received packet is the next expected packet copy its contents to input_buffer and go to step3, otherwise if its the last packet received in-order go to step 4 otherwise go to step1.

step3- if message is complete put contents of the input_buffer into  message_queue then notify user thread to receive the message and go to step 4.

step4- send acknowledgement for the last packet received in-order then go to step 1.

The packet structure

The protocol data unit is called 'packet' which is enclosed in a single UDP datagram.
A packet can be a data packet (we refer to it as packet) or a feedback packet(we refer to it as feedback).
A packet may hold one complete or one fragment of an application-level message.
N (see sender protocol) is user-defined, the default is 1(recommended). The protocol can be made to send 'bursts' of packets instead of one packet a time by setting N>1 (not recommended).
packet payload size is predefined by user (default is 467 - which is 512 minus IP, UDP & ADEN headers  ) .
The packet (and feedback) header 17 bytes, however, when ADEN transfers a message the first transmitted packet contains the message size therefore this packet payload is less by 4 bytes than the configured payload length.
 Note that a single transmittable/receivable data unit by the application is called a 'message' not a packet. i.e. although message transmission consists of exchanging a number of datagrams over an unreliable service, a message can not be partially sent or partially received.
The protocol header is composed of three fields which are - by order:
-an 8-bit control flag used for various purposes (for example referring to the content type of the datagram payload: packet or a feedback).
-64-bit connection id which is a unique identifier for the connection over which the message is passed and is obtained during connection setup (explained later).
-64-bit sequence_number .
A packet sequence_number refers to the sequence of the chunk of bytes in the packet payload.
a feedback always holds the sequence of the next expected chunk.

The packet that contains the first fragment of a message  holds-besides the three fields mentioned above- an extra four bytes field in its header used to hold the total length of that message.

Note about sequence field of the packet/feedback:

Sequence  is incremented by the payload length of the transmitted/received packet instead of incrementing by one, this way the sender can always retransmit bytes that were discarded by receiver's platform from a packet payload (that is possible in Java -the reason is probably to prevent running out of memory when available memory for JVM is low).

The connection id in the header of an outgoing packet is obtained from the other end during connection setup while in feedback header it is the connection id found in the header of the received packet that triggered this feedback. 
connection setup can be explained in Server-Client terms:
Client generates a unique 64-bit id and send it in a special message (connection message) to the server. server likewise generates unique 64-bit id and send it to the client in a special feedback. After this exchange each end has two connection ids for this connection, one generated locally (local id) and one obtained from the remote end (remote id).
Note that the uniqueness of the generated connection id has to be maintained within the local host only.

The general criteria for 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. After receiving the connection message and before sending anything to the client the server should receive at least one message from the client otherwise the server must consider the connection invalid.

Passing data in both directions

The sending end uses the id it obtained from the remote end (i.e remote id) as the connection id in the packet header, except in the connection message where it uses its local id. On the other hand the receiver uses its local id as the connection id in the feedback header, except for the feedback sent in response to a connection message where the remote id is used in the feedback header while the generated id (i.e local id) is put in the feedback body (note that except this one, feedbacks have no body).

Note that the sequence value of the connection message is zero, likewise the first message from the server to client (no -if you ask - first message 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.

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.