Wednesday, April 9, 2014

ADEN (2)


ADEN's project provides a message-based network protocol over UDP/IP (see the first article about ADEN) that provides TCP features but with faster connection/disconnection technique and simpler congestion control mechanism. It is a fast technique for exchanging small messages between two processes and is ideal for applications where communication is request/reply and the largest request (reply) can be fragmented into a few UDP datagrams only.

ADEN Protocol

ADEN protocol  can be described with minimum details as following:  

Sender protocol

step1 - Send N packets.

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

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

step4 - If there is an acknowledged packet then put the next packet (in the sequence) for retransmission otherwise put the Nth packet for retransmission then go to step5.

step5 - If the packet set for retransmission is not retransmitted at least M times then retransmit it and go to step2, otherwise fail.  

the above algorithm describes how a single 'burst' of packets (N packets) are transmitted reliably. An application-level message is transmitted by executing this protocol one or more times. note that details are omitted for demonstration.
The default value of N (burst size) is 1, However, if you modify N remember that it should remain small ( 3 or 4 ).

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.

step2 - If received packet is not the expected packet go to step5 otherwise copy its contents to input_buffer .

step3 - If  reorder_buffer contains a packet that was received out-of-order and this packet is  now the next expected packet copy that packet contents to input_buffer and repeat step3.  Go to step4.

step4- if message is complete put contents of the input_buffer into  message_queue then notify user thread to receive the message. If  packet is a retransmission put a NACK in feedback_buffer otherwise if ACK is required by the received packet put ACK in feedback_buffer, go to step8.

step5 - If sequence is less than expected go to step6 otherwise go to step7.

step6 - If packet is a retransmission packet or ACK is required then put ACK in feedback_buffer , go to step8.

step7 - if sequence is invalid ignore the packet and go to 1  otherwise put the packet in reorder_buffer in its correct order then if  the received packet is a retransmission or ACK is required put a NACK in feedback_buffer.

step8 - if feedback_buffer is not empty send it and go to step 1.

ACK is a feedback packet sent by Receiver to tell Sender about Reciever's current position, the same is true about NACK which is used only when Receiver suspects that a packet might be lost.

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.

No comments:

Post a Comment