next up previous contents
Next: Prospero Conventions Up: The Prospero Protocol Previous: Replication


Asynchronous Reliable Delivery Protocol

This appendix describes the asynchronous reliable delivery protocol (ARDP) used by Prospero. As used by Prospero, this protocol is layered on top of the Internet User Datagram Protocol.

Prospero implements its own ARDP because at the time of initial development we were unable to find any that were suitable for general use. Most systems that use any sort of reliably delivered message protocol implement their own around the specific needs of their application. Like these other systems, early versions of the Prospero protocol defined the mechanisms needed for retries and packet sequencing. As these mechanisms were refined, the functionality was moved to a separate protocol layer (and is implemented as a separate library) to improve modularity, and in hope that this general and simple ARDP can be used for other purposes.

The ARDP protocol is designed for a request/response style of interaction, where a client sends a request message to a server in one fell swoop and receives a reply message from the server. The server can send the packets composing the reply message slowly, as data becomes available, while it is still processing the rest of a reply. In the current implementation, each request message sent by a machine from a particular port has its own connection id.

ARDP was designed so that in the common case, the additional overhead of guaranteeing reliability is as small as possible. Unless special processing is required, the header is kept small, and unless a packet is lost, no additional packets are sent. If a field is not specified, the default value is used in its place. All fields up to and including the last field specified must be filled in, but the header may be truncated at any point, after which all remaining fields take on their default values. The ARDP header contains the following fields:

Octet 0
Version and header length: High order two bits are ARDP version number mod 4 (this is version 0). Low order six bits are the header length including octet 0.gif

Octets 1-2
Connection ID: Defaults to zero. It must be specified in the response to any request that specified a non-zero connection ID.

Octets 3-4
Packet number: Defaults to 1 if not specified. A specified value of 0 indicates an unsequenced control packet which should not be passed to the application. Note that unsequenced control packets cannot request acknowledgements, nor is there any way for the sender of such a packet to be sure that they have arrived.

Octets 5-6
Total number of packets in this message: Defaults to 0 if not known, or retains current value if it was provided in any earlier messages. If the packet number was also not specified, then it defaults to 1. A specified value of 0 means use the default.

Octets 7-8
Received through: Sequence number through which all packets have been received by the sender of this packet. Defaults to current value if specified in previous message. Defaults to 0 otherwise. The recipient's count of packets received through is normally monotonically increasing; this keeps the count from being set backwards in case an out-of-order packet is received. However, if the ``reset received through'' option (option 2) is specified in octet 12, then it means reset to 0 (i.e. it forgot or lost the earlier messages). More generally, specifying any explicit value for this field along with the ``reset received through'' option resets the peer's count, possibly backwards. The recipient should not set its internal value of this field backwards unless the ``reset received through'' option is set.

Octets 9-10
Wait (expected time till response): Defaults to current value. Specified value of 0 means revert to client-specified backoff algorithm. Specifying a non-zero value lets the client know that a request might not be processed for some time and that the client should not retry the request until the specified time. The client may retry sooner if it believes messages are available which have been missed (e.g., gaps in the list of received packets). This is an unsigned quantity, measured in seconds, in network octet order (i.e., octet 9 is more significant than octet 10). A specified value of 65,535 (; all bits turned on) means greater than or equal to 65,535 seconds until the next packet. (We do not expect that this value will ever be used, but it is defined for the sake of completeness.)

The client, in its messages, always sets this field to zero.

Octet 11
Flags: Octet 11 is a bit vector specifying option flags. The flags may themselves require additional fields specific to the flag. These fields appear at the end of the header in the order they are needed when reading flags from the low order bit to the high order bit, followed by any extra fields needed by the flag specified by the 12th octet.

Octet 12
More Options: Octet 12 specifies exactly one (1) of up to 256 other options. The options may themselves require additional fields specific to the options. (See discussion at Octet 11).

Octets 13 and above
Fields specific to particular flags and options.

First, additional data fields specific to the flags in octet 11 should be specified.

Next Octets
Additional Address Information (if Additional Address Information flag specified): The first octet specifies the type of additional address information. The next octet specifies the length of the address information, from 0 to 255 octets.gif Its length does not include the two octets that specify type and length. The following octets contain the address information itself, and its format is dependent upon the type of address information.

Next 2 octets
Priority (if Priority flag specified): These octets are a signed integer representing the priority of the request. Not all implementations understand this message, and many that do will not honor requests for expedited handling. Negative numbers indicate expedited handling while higher numbers indicate greater delays. A priority of 0 is normal. Implementation detail: the priority is currently tagged onto all packets sent; this isn't necessary, but it's easy.

Next 2 octets
Protocol ID (if Protocol ID flag specified): These octets identify the interpretation of the data carried in the packet. The default, or an explicitly specified value of 0, mean that it is not specified, but has been agreed upon externally (i.e. the applications will know).

Next octets
Any data specific to the option set by octet 12 should be specified. This is the data specified in the ``additional fields'' column of the table ``Value of flags for octet 12.''

next up previous contents
Next: Prospero Conventions Up: The Prospero Protocol Previous: Replication

Padma Indraganti
Thu Jun 20 13:02:20 PDT 1996