Encoder Design

The following high-level API outlines the minimum interactions a user should be able to have using the encoder API:

// Configures the encoder to be ready for use
void configure(uint64_t max_packet_bytes, int64_t timeout,
               uint64_t max_stream_size);

// Read payloads into the encoder
void comsume(const uint8_t* payload, uint64_t bytes, int64_t now);

// Access generated packets
auto can_produce() const -> bool;
auto produce_bytes() const -> uint64_t;
auto produce_data() const -> const uint8_t*;
void produce_next();

// Control the repair generation
void set_repair(uint64_t repair_interval, uint64_t repair_target);
void disable_repair();

// Flushing the encoder to ensure that packets do not exceed the specified
// timeout
auto has_upcoming_flush() const -> bool;
auto upcoming_flush(int64_t now) const -> int64_t;
void flush(int64_t now);

This section outlines the design of the class encoder and the documents the decisions made.

This shows the flow of data through the encoder:

+------------------------+
|     Fragmentation      | <-- Payload -- consume(...)
+------------------------+
            |
+-----------v------------+
| Sliding window encoder |
+------------------------+
            |
+-----------v------------+
|      Output queue      | -- Packets --> produce_...()
+------------------------+

1. The user passes Payloads to the encoder via the consume function. The size of the payload must be below Maximum payload bytes.
2. A fragmentation component then splits the Payloads into smaller pieces so they fit in the internal sliding window encoder as Source symbols.
3. The sliding window encoder adds the Source symbols to it’s Stream, and uses them to produce Packets in accordance to the Repair target and Source symbol timeout.
4. Packets are then added added to the output queue which is accessed with the produce_...() functions.

Sliding Window Management

Source symbols added to the encoder will be pushed to its Stream. In addition to maintaining the position of the source symbol in the stream, the encoder also tracks:

1. The timestamp of when the was added to the stream.
2. Whether a source symbol is protected, i.e., whether it has been part of a Repair phase. If repair is disabled source symbols are immediately marked protected.

All new source symbols are immediately written once in Systematic mode. The following rules are used to determine when source symbols are dropped and when repair is scheduled:

1. Each time a source symbol is written the encoder checks if the Repair interval has been reached. If so repair is scheduled.
2. If source symbols which are both unprotected and expired exist, repair is scheduled.
3. If source symbols which are both protected and expired exists, those source symbols are dropped.
4. If the stream grows above its Maximum stream size, source symbols are dropped, and if needed repair is scheduled.

Since the Coding window only moves forward there is no reason to retain source symbols that have left the window. For this reason the encoder’s Stream and coding window always follow each other.

Dropping source symbols

A source symbol can be dropped from the encoder for two reasons.

1. It’s expired.
2. It’s the first in the stream when the stream reaches its maximum size.

In either case, the source symbols must be protected before being dropped! This ensured by the Rely encoder in the following way:

In case 1: When an source symbol expires it is checked if it’s unprotected. If so repair is scheduled immediately.

Since the Coding window covers entire stream this means that all unprotected source symbols in the stream will be marked as protected, including the one(s) about to be dropped.

In case 2: Source symbols dropped to make room for new ones will always be protected. This is the case since the Repair interval is always smaller than or equal to the Maximum stream size. This means a source symbol will always reach the repair interval before reaching the Maximum stream size and thereby be protected.