RFC 9550: Deterministic Networking (DetNet): Packet Ordering Function

4.1. Prerequisites and Assumptions

The POF algorithms discussed in this document make some assumptions and trade-offs regarding the characteristics of the sequence of received packets. In particular, the algorithms assume that a PEF is performed on the incoming packets before they are handed to the POF. Hence, the sequence of incoming packets can be out-of-order or incomplete but cannot contain duplicate packets. However, the PREOF run independently without any state exchange required between the PEF and the POF or the PRF and the POF. Error cases in which duplicate packets are presented to the POF can lead to out-of-order delivery of duplicate packets and to increased delays.¶

The algorithms further require that the delay difference between two replicated packets that arrive at the PEF before the POF is bounded and known. Error cases that violate this condition (e.g., a packet that arrives later than this bound) will result in out-of-order packets.¶

The algorithms also make some trade-offs. For simplicity, it is designed to allow for some out-of-order packets directly after initialization. If this is not acceptable, Section 4.5 provides an alternative initialization scheme that prevents out-of-order packets in the initialization phase.¶

4.2. POF Building Blocks

The method described in this document provides a POF for DetNet networks. The configuration parameters of the POF can be derived when engineering the DetNet flow through the network.¶

The POF method is provided via the following:¶

Delay calculator:

Calculates buffering time for out-of-order packets. Buffering time considers (i) the delay difference of paths used for forwarding the replicated packets and (ii) the bounded delay requirement of the given DetNet flow.¶

Conditional delay buffer:

Used for buffering the out-of-order packets of a DetNet flow for a given time.¶

Note: The conditional delay buffer of the POF increases the burstiness of the traffic as it only adds delay for some of the packets.¶

Figure 2 shows the building blocks of a possible POF implementation.¶

               +------------+        +--------------+
               | Delay calc |        | Conditional  |
            +--| for packet >--->>---| Delay Buffer >--+
            |  +------------+        +--------------+  |
            |                                          |
     +------^--------+                                 |
->>--| POF selector  >---------------------------------+-->>----
     | (Flow ident.) |
     +---------------+

->>- packet flow

4.3. The Basic POF Algorithm

The basic POF algorithm delays all out-of-order packets until all previous packets arrive or a given time ("POFMaxDelay") elapses. The basic POF algorithm works as follows:¶

Notes:¶

The state used by the basic POF algorithm (i.e., "POFLastSent") needs initialization and maintenance. This works as follows:¶

The basic POF algorithm has two parameters to engineer:¶

Design of these parameters is out of scope for this document.¶

Note: Multiple network failures can impact the POF (e.g., complete outage of all redundant paths).¶

The basic POF algorithm increases the delay of packets with maximum "POFMaxDelay" time. In-order packets are not delayed. This basic POF method can be applied in all network scenarios where the remaining delay budget of a flow at the POF point is larger than "POFMaxDelay" time.¶

Figure 3 shows the delay budget situation at the POF point.¶

                          Path delay
                          difference
                        /-------------/
<- path with min delay ->             /-- remaining delay budget --/

|-----------------------|-------------|----------------------------|
0                       t1            t2                           T

<-------- path with max delay -------->

/-------------------- delay budget at POF point -------------------/

4.4. The Advanced POF Algorithm

In network scenarios where the remaining delay budget of a flow at the POF point is smaller than "POFMaxDelay" time, the basic method needs extensions.¶

The issue is that packets on the longest path cannot be buffered in order to keep the delay budget of the flow. It must be noted that such a packet (i.e., forwarded over the longest path) needs no buffering as it is the last chance to deliver a packet with a given sequence number. This is because all replicas already arrived via a shorter path(s).¶

The advanced POF algorithm requires extensions of the basic POF algorithm:¶

The advanced POF algorithm identifies the path of a given packet and uses this information to select the predefined time ("POFMaxDelay_i") to apply for the buffered packet. So, in the advanced POF algorithm, "POFMaxDelay" is an array that contains the predefined and path-specific buffering time for each redundant path of a flow. Values in the "POFMaxDelay" array are engineered to fulfill the delay budget requirement.¶

Design of these parameters is out of scope for this document.¶

Note: For the advanced POF algorithm, the path-dependent delays might result in multiple packets triggering the "maximum delay reached" at exactly the same time. The transmission order of these packets should be done in their seq_num order.¶

The method for identifying the packet's path at the POF location depends on the network scenario. It can be implemented via various techniques, for example, using ingress interface information, encoding the path in the packet itself (e.g., replication functions set a different FlowID per member flow at their egress and such a FlowID is used to identify the path of a packet at the POF), or other means. Methods for identifying the packet's path are out of scope for this document.¶

Note: When using the advanced POF algorithm, it might be advantageous to combine PEF and POF locations in the DetNet network, as this can simplify the method used for identifying the packet's path at the POF location.¶

4.5. Further Enhancements of the POF Algorithms

POF algorithms can be further enhanced by distinguishing the case of initialization from normal operation at the price of more states and more sophisticated implementation. Such enhancements could, for example, react better after some failure scenarios (e.g., complete outage of all paths of a DetNet flow) and can be dependent on the PEF implementation.¶

The challenge for POF initialization is that it is not known whether the first received packet is in-order or out-of-order (for example, after a reset). The original initialization (see Section 4.3) considers the first packet as in-order, so out-of-order packet(s) during "POFMaxTime"/"POFMaxTime_path_i" time -- after the first packet is received -- cannot be corrected. The motivation behind such an initialization is simplicity of POF implementation.¶

A possible enhancement of POF initialization works as follows:¶

4.6. Selecting and Using the POF Algorithms

The selection of the POF algorithm depends on the network scenario and the remaining delay budget of a flow. Using the POF algorithms and calculating their parameters require proper design. Knowing the path delay difference is essential for the POF algorithms described here. Failure scenarios breaking the design assumptions can impact the result of the POF (e.g., packet received out of the expected worst-case delay window -- calculated based on the path delay difference -- can result in unwanted out-of-order delivery).¶

In DetNet scenarios, there is always an elimination function before the POF (therefore, duplicates are not considered by the POF). Implementing them together in the same node allows the POF to consider PEF events/states during the reordering. For example, under normal circumstances, the difference between sequence numbers in consecutive packets is bounded due to the history window of the PEF. However, in some scenarios (e.g., reset of sequence number), the difference can be much larger than the size of the history window.¶