Reliable topics

[pavel-kirienko]

There are two main strategies: positive and negative acknowledgements. Negative acknowledgements work well with streamed data but do not appear to be a good choice for ad-hoc exchanges, since the failure will not be discovered until the next successful delivery. Positive acknowledgements, on the other hand, cause undue network loading in high-fanout topics.

One issue with naive multicast positive acks is the uncertainty of how many nodes have actually received the transfer if we assume it delivered based on a single ack. We can assume that for positive acks, the links are either point-to-point (single subscriber), OR the application only cares about one acknowledgement (anycast), OR the application assumes that if one copy was delivered successfully, then the other copy has probably succeeded as well (depends on the required reliability guarantees).

It seems clear that paks/naks should be produced at the transport library level because any higher level lacks the necessary context. If we take paks as an example, the transport library will need to emit one when a transfer is successfully received, OR when a transport frame with a transfer-ID from the past is received; the higher layers are not even notified when the latter occurs. If we take naks, the transport library also has access to the required state to notice that a transfer-ID was skipped; similarly, it will also notice when a transfer could not be reassembled due to a CRC error, which also warrants a nak.

Contrary to pak/nak production, retransmission can be handled at the Cy level, and it is more convenient also since this is a highly stateful process.

Depending on the reliability mode, the transport can notify the sender when:

• A transfer is successfully received (pak).

• A transfer-ID from the past is observed on a transport frame (pak). This case occurs if an earlier pak was lost while in transit to the sender and the sender attempts to retransmit; the received does not need to bother receiving that transfer, simply acknowledging it speculatively.

• A transfer-ID from the future is observed on a transport frame (nak). Should the sender still attempt to receive the out-of-order transfer? If it does, the transfer will need to be stashed away somewhere until the earlier transfer-ID is received, since transfer-ID monotonicity is a fairly fundamental property. This gets convoluted quickly.

• A transfer could not be reassembled due to CRC error (nak).

[pavel-kirienko]

Streamed reliable delivery is less relevant for us at the moment; plus we also have a very rudimentary FEC support that simply emits a transfer twice with the same transfer-ID, which is deduplicated at the receiver transparently for the application, which at least partially addresses the need for reliable multicasts.

We will focus on PAK for now, with the following requirements and assumptions:

• This form of reliable delivery will be mostly used with topics with a single subscriber.
• The protocol guarantees either:
  • Delivery to a single subscriber.
  • Detection of delivery failure to any subscriber.
• If a topic has more than one subscriber, delivery is guaranteed only to a single, randomly chosen subscriber. The other subscribers will receive the transfer on a best-effort basis.
• The reliable transmission window spans one transfer. Only one transfer can be in the process of delivery at any time on a given session. This means that a node having published transfer X cannot initiate transfer X+1 until X is either successfully confirmed or timed out. This limitation does not affect transfers originating from different publishers, of course.
• The only means of congestion control is exponential backoff when retransmitting.

There are many ways to extend the algorithm, e.g., to discover the number of live subscribers and get a confirmation from each of them, but for now we are intentionally sticking to the most basic case of peer-to-peer exchanges.

One notable difference from Zenoh/DDS is that we do not attempt to filter topic matches on reliability. A subscriber will receive data from both reliable and best-effort publishers. The reliability of a topic is fully defined by its publishers; as such, the same topic can operate both in a reliable and best-effort mode depending on who is publishing on it.

The most basic algorithm is:

On the transmitting side:

1. When sending a transfer, set a flag indicating that this is a reliable transfer. Save the payload into the local retransmission buffer.
2. If an attempt is made to send another transfer while the previous one is still not confirmed/timed-out, enqueue the new transfer.
3. Wait for the retransmission delay R. While waiting:

• If a confirmation is received (matched by topic hash and the transfer ID), complete the transfer and exit.
• If no confirmation is received by the expiration of R, and the total transfer timeout is not yet exceeded, double R and go to step 3.

4. Otherwise, report delivery failure.

On the receiving side, if the reliable flag is set on a received frame, the protocol is mostly stateless. Implementations will need to hold a very short list of recently received valid transfer-IDs (a ring buffer of 32 transfer-ID values per session). Rules:

1. If the transfer-ID of a frame is in the received list, discard the frame and send a PAK with the received transfer-ID back to the sender. This case covers the problem of lost PAKs.
2. If a new transfer is successfully reassembled, send a PAK. On CRC error we could send a NAK, but this is explicitly out of the scope -- thus, on reassembly error we just do nothing and wait for the sender to time out and retransmit. This is one of many possibilities for future enhancements.
3. If the received transfer-ID is in the future, we accept it normally. This, again, is something that could be improved in the future. Sending a NAK notifying the sender about the missing transfers is one possibility.

There is value in duplicating every PAK to reduce the likelihood of their loss, since lost PAKs are indeed expensive both in the network throughput sense (losing a small PAK will cause the sender to retransmit the whole transfer) and in the application-layer delay sense (the sender will remain in the unconfirmed state, preventing the application from making progress). Perhaps if redundant interfaces are used, PAK duplication is not necessary.

[pavel-kirienko]

Upon some experimentation I established that the reliable delivery logic cannot be sensibly separated from the transport libraries (lib*ards). I drafted a seemingly solid solution in libudpard and am going to experiment with it now: https://github.com/OpenCyphal/libudpard/tree/experimental