Flow and Retransmission Control Protocol

 This page is under construction  

The Flow and Retransmission Control Protocol is, together with Ouroboros Data Transfer Protocol and Flow Allocator Protocol one of the three core protocols in Ouroboros.

Header

Packet switched networks use end-to-end protocols to deal with lost or corrupted packets. The Ouroboros End-to-End protocol (called the Flow and Retransmission Control Protocol, FRCP) has 4 fields:

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |            Flags              |            Window             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                        Sequence Number                        |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                    Acknowledgment Number                      |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Flags

There are 7 flags defined for FRCP.

1. DRF : Data Run Flag, indicates that there are no unacknowledged packets in flight for this connection.
2. DATA: Indicates that the packet is carrying data (this allows for 0 length data).
3. ACK : Indicates that this packet carries an acknowledgment.
4. FC : Indicates that this packet updates the flow control window.
5. RDVZ: Rendez-vous, this is used to break a zero-window deadlock that can arise when an update to the flow control window gets lost. RDVZ packets must be ACK’d.
6. FFGM: First Fragment, this packet contains the first fragment of a fragmented payload.
7. MFGM: More Fragments, this packet is not the last fragment of a fragmented payload.

Window

This updates the flow control window.

Sequence Number

A monotonically increasing sequence number used to (re)order the packets at the receiver

Acknowledgment Number

Set by the receiver to indicate the highest sequence number that has been received in order.

Operation

The operation of FRCP is based on the Delta-t protocol<ref>[https://www.osti.gov/biblio/5542785 Delta-t protocol specification: working draft<ref>, which is a timer-based protocol that is simpler in operation than the equivalent ARQ and flow control functionalities in TCP. Watson’s paper is highly recommended reading; it is truly a thing of beauty.

Before we proceed, a small note on what is meant by reliability in this discussion. We’re going to use the following definition: if a piece of a communication is received, all previous pieces of this communication will be received. This means data can only be delivered reliably if it is delivered in-order.

FRCP is only enabled when needed (based on the requested application QoS). So for a UDP-like operation where packets don’t need to be delivered in order (or at all), Ouroboros doesn’t add an FRCP header. If FRCP is enabled, Ouroboros will track sequence numbers and deliver packets in-order.

Unreliable delivery: The sender considers all packets as ACK’d. Since there are no unacknowledged packets, the Data Run Flag is set for all packets. The receiver tracks the highest received sequence number and drops all packets that have a lower sequence number. The receiver never really sends ACKs.

Reliable delivery: The Ouroboros receiver will keep track of a window of acceptable sequence numbers, indicated by the Left and Right Window Edges (LWE and RWE). The LWE is thus one greater than the highest received sequence number, and the receiver always acknowledges with LWE sequence number. An ACK for a sequence number thus means “I have received all previous sequence numbers”. Received packets with sequence numbers outside of the window are dropped. If a received packet has sequence number LWE, both window edges will be incremented until the LWE reaches a sequence number that has not been received yet. All the packets that are in the reordering buffer with a sequence number lower than the new LWE are delivered to the application. If a received packet has a greater sequence number than LWE but is within the window, it is stored for reordering.

The reliable delivery has to deal with lost packets, duplicates,etc. Automated-repeat request handles this: if a packet is not acknowledged within a certain time-frame, it is retransmitted by the sender.

For reliable transmission in the presence of lost packets to work, three timers need to be bounded. These timers define a “data run”. The state is uni-directional, so for bi-directional communication, each side has a sender record and a receiver record.

1. MPL: The maximum packet lifetime. This is bound by the network below, using the TTL mechanism. It is approximate with the probability of a packet still arriving after MPL close to zero.
2. R: The time after which a packet with a given sequence number may not be retransmitted anymore.
3. A: The maximum time a receiver will wait before acknowledging a given sequence number for the first time.