Scalable Reliable Datagram Protocol

In a lot of situations involving communications between a number of participants, we need a protocol that allows messages to be sent from peer to peer or between client and server without the overhead of opening a TCP session . In many of these cases, UDP works fine, however UDP does not guarrantee delivery.

SRDP is designed to give the application the ability to decide how much reliability it wants. The reliability is achieved by sending the message a selectable number of times until an acknowledgement is received.

A number of design criteria govern some of the choices here.

1. SRDP must scale to many thousands of simultaneous connections.
2. SRDP must be capable of being implemented simply, but also allow for future optimisation
3. SRDP should not require ANY changes to underlying TCP stacks.
4. SRDP should be able to work through proxy servers on firewalls.
5. SRDP should generate minimal network overhead
6. SRDP should smoothly degrade from networks with 100% delivery to 0% delivery.
7. SRDP should be easily retrofitted to existing network applications.

SRDP details

where:

sockaddr_in DestnAddr

The destination IP address and port, as built by traditional techniques using gethostbyname for UDP or TCP

Uint16 size

Number of bytes to send (max 548 set by limits on UDP packets)

char * bytes

The bytes to send in the packet

sockaddr_in SourceAddr

The source IP address and port

Uint8 Repeats

The number of times to send the packet - 0 means until received, but beware of endless repeats on dead destinations.

time_t timeout

The time to wait between retries, 0 means let the library decide

Unit8 flags

A bit field of service requests, see flags

SRDP takes the following actions, best expressed through pseudo-code:

    Construct a srdp_packet data structure (see srdp_packet
        Note the PacketId is the next increment of packetId
    Call UDP to Send the packet to the destination (see data_on_wire
    if timeout != 0
        RetryTime=time_now+timeout
    else
        RetryTime calculated by heuristics  (see optimisation
    Add srdp_packet to srdp_sent_queue in order of retry time.
    Adjust timer to RetryTime of first packet on queue.

    Parse the UDP data into a srdp_packet
    If the top bit of the PacketId is set, its a acknowledgement
    Construct an acknowledgement packet 
    set  the PacketId to that of the received packet, with the top bit set.
    Send that packet back to the SourceAddr
    Pass the received packet up to the receiver.
        There is a little hand-waiving here,
        but it should be no different from handling UDP

    Extract the PacketId
    if the top bit is clear, its not an acknowledgement, its a received packet
    Locate the PacketId in the srdp_sent_queue, 
        typically it will be near the beginning, 
        so there is probably no need for a binary tree etc
    Unqueue that packet from the srdp_sent_queue 
    Delete the packet and free up any memory used for it
    Delete the acknowledgement and free up any memory used for it
    If the packet was the first in the queue, 
    then readjust timer to RetryTime of first packet in queue
    If the SRDP application is clever, 
        it can adjust its heuristics based on the time the packet was 
        sent, and the time the ACK was received.

    While (the first packet in the queue has a RetryTime before time_now)
        Resend packet to the DestnAddr
        Adjust RetryTime based on Delta_Time and time_now
        Requeue packet based on RetryTime
    Set timer based on RetryTime of first packet in queue

Data structures or classes

srdp_packet

Note this would typically be implemented as a string, with appropriate methods to access the elements, in order to avoid copying data. This data structure is not mandated by the specification, but is a usefull way to think about the functionality described here.

Uint16 PacketId

The sequence number of the packet

sockaddr_in SourceAddr

Host and port of source

sockaddr_in DestnAddr

Host and port of destn

time_t Time

On the sending end this is the time to retry the message

On the receiving end, this is the time the message was retrieved

time_t Delta_Time

On the sending side, this is the time to wait between retries

On the receiving side it currently has no meaning.

char* Bytes

The bytes received, this MAY contain NULLs terminated by end of packet

UInt16 Size

The length of the bytes following

Packet

CommandType[1]

A one byte fixed value TBD so that SRDP can co-exist with our other protocols on the same port.

Packet Id[2]

The id of the packet as allocated by the sender

Flags[1]

Flags including SRDP_DONTDUPLICATE and SRDP_ORDER

Bytes[Size]

"Size" bytes of data (which may contain nulls) terminated by end of packet

CommandType[1]

A one byte value TBD indicating an SRDP acknowledgement

Packet Id[2]

The id of the packet being responded to, top-bit set

SRDP_DONTDUPLICATE

Don't allow duplicate packets to be received, this can occur if the resent packet, and the acknowledgement cross in the network. This is tricky, because it relies on the receiver keeping a queue of received packets which could get large, this may never be implemented. The second packet is sent with the same ID, there are three possible ways of dealing with this.

1. Keep a list of recently received IDs, and discard duplicates
2. Don't use SRDP for protocols which are really worried by packets arriving twice
3. Tackle it at a higher level, i.e. something in the data prevents duplicates

SRDP_ORDER

This requires that packets are received in the order sent. Packets can be mis-ordered if an early packet is lost and resent AFTER a later packet. The receiver will get, and pass on, the packets in the wrong order, there are three ways around this.

1. The sender only allows a maximum of one packet in the srdp_sent_queue per receiver, keeping a seperate queue of packets that are waiting.
2. Dont use SRDP for protocols which are really worried about misordering.
3. Tackle it at a higher level

Proxies

UDP

TCP

SOCKS

Packet size limitation

576

Min IP datagramsize

- 20

IP header size

- 8

UDP header size

- 16

header fields from SRDP

= 532

Acknowledgements