# Deterministic Networking (DetNet): Performance evaluation of the Packet Ordering Functions

Juan-Cruz Piñero, Alberto Blanc, José Ignacio Alvarez-Hamelin, Georgios Papadopoulos

## ► To cite this version:

Juan-Cruz Piñero, Alberto Blanc, José Ignacio Alvarez-Hamelin, Georgios Papadopoulos. Deterministic Networking (DetNet): Performance evaluation of the Packet Ordering Functions. Computer Communications, 2025, 239, pp.108171. 10.1016/j.comcom.2025.108171. hal-05480450

HAL Id: hal-05480450

https://hal.science/hal-05480450v1

Submitted on 11 Feb 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Deterministic Networking (DetNet): Performance evaluation of the Packet Ordering Functions

Juan-Cruz Piñero<sup>a,b</sup>, Alberto Blanc<sup>a,b,*</sup>, José Ignacio Alvarez-Hamelin<sup>b</sup>, Georgios Z. Papadopoulos<sup>a</sup>

<figure><img src="image_2.png" /></figure>

## ARTICLE INFO

**Keywords:**

Wireless networks

Internet of Things

Deterministic networks

## ABSTRACT

Industrial Internet of Things applications need strict Quality of Service guarantees, including when they use wireless networks. While existing standardization efforts, such as Deterministic Networks (IETF) and Time-Sensitive Networking (TSN), have focused mainly on wired networks, more recent activities address wireless networks, like the Reliable and Available Wireless (RAW) Working Group of the IETF. Duplicating packets over multiple paths can improve availability and reliability, but this can potentially result in more out-of-order packets. Existing reordering algorithms, including two recently standardized by the IETF, are not always well suited to wireless networks. As a result, guaranteeing a bounded end-to-end latency and/or maximum consecutive packet losses is still particularly challenging. We propose a novel packet reordering algorithm for deterministic networking that includes wireless segments to achieve lower end-to-end latency while providing high end-to-end reliability. We simulate a 6TiSCH wireless network to compare its performance with the existing ones. Furthermore, we also extend existing Network Calculus bounds on the reordering timer to obtain path-dependent values that can reduce the average latency. We also introduce a probabilistic model to compute the reordering ratio when there are no retransmissions that fits the simulation results.

## 1. Introduction

The wireless shared medium [1] poses unique challenges in achieving properties comparable to those of wired deterministic networks due to uncontrolled interferences. Thus, the packet transmissions over a wireless medium cannot be guaranteed to be fully deterministic. At the same time, a number of use cases such as industrial applications, professional audio and video, wireless gaming, aeronautical communications, amusement parks, require a wireless technology. These applications require strict Quality of Service (QoS) guarantees, in particular end-to-end network reliability (no packet losses), low jitter, and in-order packet delivery [2]. For instance, consecutive packet losses are especially harmful in industrial automation applications as they can halt production lines.

Wired networks are best placed to deliver such guarantees, but at a significantly higher cost, especially when using redundant paths to increase network reliability, hence the need for technical solutions to allow wireless networks to offer these guarantees. Within the Internet Engineering Task Force (IETF), the goal of the Reliable and Available Wireless (RAW) Working Group (WG) is to extend the results

of the Deterministic Networking (DetNet) group to wireless networks. The latter has defined Packet Replication Function (PRF) and Packet Elimination Function (PEF) [3] to achieve low packet loss by sending multiple copies of the same packet over different paths. The downside of such a solution is the possibility of out-of-order packet delivery, which may not be acceptable for some applications, as highlighted in the DetNet network architecture document [3], where the in-order delivery is a crucial QoS metric. The document also defines a Packet Ordering Function (POF) without any implementation details.

More recently, DetNet published RFC 9550 [4] that contains possible implementations of a POF in a deterministic network. While in traditional IP networks, the transport or application layer at the receiving host handles out-of-order packets, not Layers 2 or 3, the draft outlines a few packet reordering algorithms for the IP layer. Several packet reordering algorithms have been proposed without focusing on wireless networks or considering the memory needed to buffer packets while reordering them. Memory can be limited in resource-constrained scenarios like wireless networks with battery-powered nodes. As a result,

<footnote><sup>a</sup> IMT Atlantique, IRISA, UMR CNRS, 6074, Rennes, France</footnote>

<footnote><sup>b</sup> Universidad de Buenos Aires, Buenos Aires, Argentina</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: jpinero@fi.uba.ar (J.-C. Piñero), alberto.blanc@imt-atlantique.fr (A. Blanc), ihameli@cnet.fi.uba.ar (J.I. Alvarez-Hamelin), georgios.papadopoulos@imt-atlantique.fr (G.Z. Papadopoulos).</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 1. 6TiSCH Protocol Stack [5].</figcaption></figure>

ensuring bounded end-to-end latency and/or minimizing consecutive packet losses remains a significant challenge.

In this article, we present a novel packet reordering algorithm, called Path and Buffer Aware Advanced Packet Ordering Function (PBAAPOF), for deterministic networking that includes wireless segments to achieve lower end-to-end network latency while providing high reliability and requires less memory compared to the existing solutions. Moreover, we extend existing Network Calculus results to obtain a tighter per-path timeout bound. We evaluate the performance of our proposed algorithm and compare it against existing reordering approaches in a simulated IPv6 over TSCH mode of IEEE Std 802.15.4e (6TiSCH) network [5], focusing on their memory usage. This work is based on our previous conference paper [6]. In this extended version, we introduce a probabilistic model to compute the reordering ratio when there are no retransmissions. Furthermore, we extend the performance evaluation by employing additional simulation setups (e.g., network topologies, number of nodes, number of parallel paths, schedule).

The remainder of this paper is organized as follows. The system description, along with the necessary technical background, is presented in Section 2. Section 3 overviews the related work on packet reordering functions. Section 4 describes reordering algorithms standardized by the IETF and presents our proposed algorithm, which is better suited for wireless networks. Section 5 introduces the reordering metrics that are applicable to DetNet systems, while in Section 6, the upper bounds for the reordering metrics are calculated based on Network Calculus. In Section 7, the packet reordering ratio is computed when there are no retransmissions. Section 8 describes the simulation setup, while Section 9 presents the performance evaluation of our proposed solution when compared to state-of-the-art approaches. Finally, Section 10 concludes the paper and presents potential future works.

## 2. System description

This paper focuses on the IPv6 over the TSCH mode of IEEE 802.15.4e (6TiSCH) technology [5]. The 6TiSCH architecture proposes a protocol stack rooted in the TSCH mode of the IEEE Std 802.15.4-2015 standard [7], supports multi-hop topologies with the RPL routing protocol [8], and is IPv6-ready through IPv6 over Low power Wireless Personal Area Networks (6LoWPAN) [9]. 6TiSCH has defined the missing control plane protocols to match link-layer resources to the routing topology and application communication needs: the 6TiSCH Operation Sublayer (6top) and the 6top Protocol (6P) [10]. All these protocols form the 6TiSCH protocol stack, shown in Fig. 1. Note that the Institute of Electrical and Electronics Engineers (IEEE) standardizes the lower layers, while the IETF standardizes the upper layers.

### 2.1. IEEE std 802.15.4-2015 TSCH

Under TSCH, communications among the nodes are orchestrated by a schedule; see Fig. 2. TSCH enables nodes in the network to coordinate through a communication scheduler, which uses Time Division Multiple Access (TDMA) for the time dimension and Frequency Division Multiple Access (FDMA) for the frequency dimension. More specifically, time is divided into discrete *timeslots* of equal length (e.g., 10 ms), sufficient for a node to transmit a frame and to receive an acknowledgment. The available frequency is divided into 16 non-overlapping physical *radio channels* operating at 2.4 GHz, where each radio channel has a bandwidth of 2 MHz and a channel separation of 5 MHz.

A group of consecutive timeslots forms a slotframe that repeats perpetually, and, according to the standard, it consists of 101 timeslots, but this value is configurable. The timeslots are identified by an Absolute Sequence Number (ASN) counter that increments as time elapses, i.e., the ASN counts the number of timeslots since the establishment of the network. Thanks to the periodic transmission of the Enhanced Beacon (EB) frames from the nodes in the TSCH network, all nodes are aware of the current ASN value, and they continuously re-synchronize with their neighbors. An EBs frame contains time and channel frequency information and information about the slotframe for new nodes to join the network.

To build a TSCH schedule, a collection of timeslots and channel offsets is assigned to each node, called “cells”. The cells are classified into two types, the Carrier Sense Multiple Access (CSMA) contention-based cells or the *shared cells*, and the contention-free cells or the *dedicated cells*, see Fig. 2. The employed schedule indicates, for each timeslot, whether a node has to turn its radio ON to transmit or receive a frame or turn its radio OFF to save energy.

### 2.2. 6TiSCH operation sublayer (6top)

To enable an IPv6-based low-power wireless mesh architecture based on TSCH mode of the IEEE Std 802.15.4-2015 standard [5], IETF 6TiSCH WG specified a new sublayer, called 6top, to fill the gap between the 6LoWPAN and the IEEE Std 802.15.4-2015 TSCH layers, see Fig. 1. 6top sublayer is composed of the 6top Protocol (6P) [10] and one or more Scheduling Functions (SFs) [11].

#### 2.2.1. 6Top protocol (6P)

6P enables distributed scheduling in 6TiSCH-based networks by facilitating the negotiation of cells between two neighboring nodes, i.e., between a child and a parent node. In particular, 6P defines the transaction (control) messages to “add”, “delete”, or “relocate” cells within the slotframe, i.e., node schedules. Note that when and how many cells to add, delete, or relocate is left to a SF.
<figure><img src="image_4.png" /><figcaption>Fig. 2. A RPL DODAG topology (left) and TSCH schedule example (right).</figcaption></figure>

### 2.2.2. Scheduling function (SF)

As previously stated, 6P only provides the necessary transaction messages. In contrast, a 6TiSCH SF decides when to add, delete, or relocate a cell according to the application requirements, routing changes, or schedule collisions. Consequently, it triggers the 6P transaction messages.

SFs can be classified into two broad categories. The *distributed* where the nodes build their own schedule solely based on the information exchanged locally with their direct neighbors, and the *centralized* where the schedule is computed and distributed by a single central entity. We use the *centralized scheduling* approach in this paper.

### 2.3. 6LoWPAN adaptation layer

IEEE Std 802.15.4 frames have a Maximum Transmission Unit (MTU) of 127 bytes when operating at 2.4 GHz. Considering that the IPv6 and User Datagram Protocol (UDP) headers have 40 and eight bytes, respectively, and the IEEE Std 802.15.4 MAC header can be up to 23 bytes while its footer consists of 2 bytes, there are 54 bytes left for the payload.

The 6LoWPAN Working Group (WG) was established in 2005 to address this issue. The WG defined mechanisms for enabling efficient IPv6 communication over IEEE Std 802.15.4 networks [12]. As part of its efforts, the 6LoWPAN WG introduced an intermediate adaptation layer between layers two and three [13]. This 6LoWPAN adaptation layer handles tasks such as header compression, fragmentation, reassembly, and forwarding of IPv6 packets that exceed the 127-byte MTU. The header compression mechanism is essential for reducing the 40-byte IPv6 header and the eight-byte UDP header down to a few bytes when link-local IPv6 destination and source addresses are employed.

### 2.4. The RPL routing protocol

Industrial applications require low-power (wireless) mesh networks that consist of hundreds and thousands of nodes [2]. Therefore, to extend the industrial network beyond the radio coverage of one node, mesh technology enables some nodes to act as relays for others. However, beyond one hop, it requires a routing protocol.

RPL is one of the most adopted routing protocols for low-power (wireless) mesh networking. RPL is a proactive link-layer agnostic distance vector routing protocol, and thus it can operate over wireless or Power Line Communication (PLC) networks [8]. In the low-power and lossy networks we target, the topology is not predefined; thus, RPL discovers and selects nodes to construct optimal routes.

The RPL routing protocol nodes construct a DODAG based on a distance-vector technique. DODAG is a directed acyclic graph. Moreover, a single node is considered the DODAG Root, which serves as the gateway to other non-RPL networks. Based on a common Objective Function (OF) each node selects one or more parent(s), acting as a relay

towards the DODAG Root. In such an acyclic network, the traffic from DODAG Root towards non-Root nodes is called the downstream traffic, while the reverse is called the upstream traffic. Fig. 2 shows a DODAG topology that consists of 7 nodes with one DODAG Root.

### 2.5. DetNet, RAW, and PREOF functions

In 2023, at the IETF, the DetNet and RAW WGs were merged, and thus, DetNet WG was chartered to include wireless technologies. Indeed, the DetNet WG will also work on defining how DetNet solutions operate over networks that include wired and wireless network technologies. This work focuses on Layer 3 to support applications requiring DetNet high reliability and availability and can operate over a wide range of scheduled-based wireless media, such as IEEE Std 802.15.4-2015 TSCH, 3GPP 5G Ultra-Reliable Low Latency Communications (URLLC), and IEEE 802.11ax/be.

One of the fundamental pieces of achieving reliable and available wireless networking is the Packet Replication Elimination and Ordering Functions (PREOF) functions [3,14]. PREOF consists of the following individual functions:

* **Packet Replication Function (PRF):** this function duplicates each data packet, and each copy is forwarded over a different parent node over multiple paths in the network.

* **Packet Elimination Function (PEF):** packet replication function introduces multiple copies of the same packet that traverse the multi-hop multi-path network independently. To prevent each received copy from generating additional independent data packet copies and causing network flooding, the elimination function is employed to remove unnecessary duplicates.

* **Packet Ordering Function (POF):** when RAW/DetNet flow packets are received out of order at the relay or at the final destination node, this function reorders packets.

RAW augments DetNet's PREOF functions by enabling potential interaction with lower-layer one-hop reliability mechanisms, which are more common in wireless-based technologies than in wired ones. These include:

* **Automatic Repeat reQuest (ARQ):** if a failed packet transmission is detected, ARQ function retransmits a packet up to a predefined maximum count.

* **Promiscuous Overhearing:** considering that a wireless transmission is broadcast by nature, any neighbor within propagation range of a transmitter may "overhear" the transmission.

In the literature, most of these functions have been evaluated [15, 16]. However, to the best of our knowledge, the POF has not been studied in low-power wireless mesh networks. In this paper, we aim to exploit the advantages of the Ordering Function over the 6TiSCH technology.
## 3. Related work

The reordering problem has been studied in different environments, along with its causes, impact on performance, and possible solutions in different domains, such as broadband digital television [17], reliable transport protocols [18], video traffic over UDP [19].

As modern user devices have multiple wireless interfaces, it is possible to use them in parallel to connect to the Internet. Given the different bandwidth and latency of each wireless network, packet reordering is a major problem. Kaspar et al. [20] address reordering when user devices (e.g., smartphones) use multiple wireless network interfaces in parallel to connect to the Internet. They propose a sender-side solution to reduce the buffer requirements by dropping the most delayed packet, i.e., the one with the lowest sequence number, whenever the buffer is full. Evensen et al. [21] address the same problem and propose a network layer proxy on the sender side, achieving transport protocol transparency. In this use case, packets are not duplicated, and there are no latency guarantees, contrary to DetNet and Time-Sensitive Networking (TSN).

Narasiodeyar et al. [22] propose the Lowest-First Re-Sequencing Algorithm (LFRA) to reorder packets, with the resequencing buffer memory as the limiting resource (see Section 4.3 for a detailed description of the algorithm). They evaluate the algorithm with simulations using prerecorded traces with out-of-order packets but do not derive delay bounds.

The IETF DetNet working group has standardized a POF [4], including a basic reordering algorithm and two advanced versions. The basic version uses an unbounded buffer to store out-of-order packets and a timeout mechanism to forward them when the missing packet can no longer be received. The advanced version uses a timeout value that depends on the path to reduce the average latency (see Section 4.1 for a detailed description of the algorithms).

Koutsiamanis et al. [23] propose a multipath routing algorithm that exploits the properties of the shared wireless medium to provide redundancy in an Internet of Things (IoT) environment. The algorithm outperforms the single-path retransmission-based approach of RPL plus TSCH and the LinkPeek solution when considering resource allocation, overhead, jitter, delay, and Packet Delivery Ratio (PDR). The authors did not address packet reordering, even though the proposed algorithm uses multiple paths in parallel.

When reordering packets in a lossy network, one has to decide how long to wait for out-of-order packets. The Network Calculus framework [24] is ideally suited to model TSN systems and to derive performance bounds, including lower bounds on the timeout values when reordering packets [25], as well as arrival curves for the output of packet reordering functions [26].

Existing Network Calculus bounds do not take into account the path taken by each packet. We derive tighter bounds by exploiting this information, assuming each path is FIFO. The timeout-based algorithms proposed by the IETF assume an unlimited buffer, an unreasonable assumption for Industrial Internet of Things (IIoT) devices. On the contrary, the LFRA algorithm uses a bounded buffer, but it stores out-of-order packets until the buffer is full (or the missing packets arrive), increasing the latency. We combine these two approaches, using the tighter delay bounds based on the path taken by each packet.

## 4. Reordering algorithms

We briefly describe existing reordering algorithms and present a new algorithm better suited for wireless networks. RFC 9550 [4] propose a basic and an advanced version of the algorithm meant to address some limitations of the basic algorithm at the cost of higher complexity, while Narasiodeyar et al. [22] proposes only one.

To simplify the comparison between the different algorithms, we use a uniform notation and variable names (where applicable) for all the algorithms, different from those used by the authors of each

algorithm. We assume that each packet has a sequence number that is incremented by one for each successive packet sent by the source. When a packet is replicated, each replica has the same sequence number as the original packet. For the sake of simplicity, we assume monotonically increasing sequence numbers (i.e., we do not consider wrap-around).

### 4.1. Basic POF algorithm

Let $n$ (POFLastSent) be the sequence number of the last packet forwarded, $i$ (seq_num) be the sequence number of the $i$th packet, and $T$ (POFMaxDelay) be the time after which a packet stored in the buffer is sent even if it is out-of-order. In parenthesis, the names of the variables in the original document [4].

The pseudocode in Algorithm 1 is equivalent to the basic algorithm [4]. The conn_state variable keeps track of the state of each connection, including the sequence number of the last forwarded packet (conn_state.n). Packets whose sequence number is less than $n + 1$ are forwarded immediately (line 2 in PROCESS-PACKET). If the sequence number is equal to $n + 1$ (line 3), $n$ is incremented, and the RELEASE-PCKTS checks if any buffered packet can now be forwarded. The call to Get-Packet(conn_staten, buffer) (line 2) returns the packet with sequence number conn_staten from the buffer, if such a packet is stored in the buffer, and NONE otherwise.

If the sequence number is greater than $n$, packets are buffered (line 7), and a timer is started. When the timer expires after $T$ units of time, it calls TIMER-EXPIRED with parameters pktseq_num, conn_state, buffer.

**Algorithm 1** The basic POF algorithm.

RELEASE-PCKTS pkt, conn_state, buffer)

1 repeat

2 pkt' = Get-Packet(conn_staten, buffer)

3 if pkt' ≠ NONE

4 Forward-Packet pkt)

5 Stop-Timer(conn_state.n)

6 conn_staten = conn_staten + 1

7 until pkt' == NONE

TIMER-EXPIRED pkt, conn_state, buffer)

1 Forward-Packet pkt)

2 conn_staten = pktseq_num

3 RELEASE-PCKTS pkt, conn_state, buffer)

PROCESS-PACKET pkt, conn_state, buffer)

1 if pktseq_num ≤ (conn_staten) + 1

2 Forward-Packet pkt)

3 if pktseq_num == (conn_staten) + 1

4 conn_staten = conn_staten + 1

5 RELEASE-PCKTS pkt, conn_state, buffer)

6 else

7 bufferstore pkt)

8 START-TIMER pktseq_num, T,
       TIMER-EXPIRED pkt, conn_state,
       buffer)

### 4.2. Advanced POF algorithm

The basic algorithm uses a single timeout value $T$, which does not depend on the path taken by each packet. This is sub-optimal: if different paths have different (maximum) delays, as is often the case, one must always use the timeout value for the slowest path. The
advanced algorithm replaces a single timeout value with an array of
timeouts $T_p$ one for each path $p$, reducing the average latency. (Except
in corner cases where all the packet losses are on the faster paths,
forcing the algorithm always to use the largest $T_p$ anyway.)

This version requires the reordering node to know the path taken by
each packet. This can be achieved, for example, by setting an ID value
in the packet header at the replication point [4].

Another enhancement is to handle explicitly the first packets in each
connection. We do not consider this further optimized version, as, for
the sake of simplicity, we focus on long-lived connections.

4.3. LFRA Algorithm

The basic and advanced POF algorithms above assume that there
is always space in the buffer storing the out-of-order packets. On the
contrary, the LFRA [22] algorithm assumes a bounded buffer (see
Algorithm 2). As long as the buffer is not full, the algorithm stores out-
of-order packets until they can be sent in order (lines 2–9); if the buffer
is full, it sends the packet with the smallest sequence number among
all the packets in the buffer and the last received packet (lines 11–18).
The call to Get–Min–Packet(buffer) (line 14) returns the packet with
the smallest sequence number currently stored in the buffer.

**Algorithm 2** The LFRA algorithm.

PROCESS-PACKET(pkt, conn_state, buffer)
1   if pktseq_num == (conn_staten) + 1
2     Forward-Packet(pkt)
3     conn_state.n = conn_staten + 1
4   repeat
5     pkt' = Get-Packet(conn_staten)buffer)
6     if pkt' ≠ NONE
7       Forward-Packet(pkt')
8       conn_staten = conn_staten + 1
9     until pkt' == NONE
10  else
11  if bufferfull == FALSE
12  bufferstore(pkt)
13  else
14  pkt' = Get–Min–Packet(buffer)
15  if pkt'seq_num < pkt.seq_num
16    Forward-Packet(pkt')
17  else
18  Forward-Packet(pkt)

4.4. PBAAPOF Algorithm

Given that nodes in IoT networks often have limited memory, we
propose a new algorithm that combines ideas from the algorithms
presented above (see Algorithm 3), called Path and Buffer Aware
Advanced Packet Ordering Function (PBAAPOF). As the POF algorithm,
it immediately forwards packets whose sequence number is less than
$n + 1$ (line 2). If the sequence number is $n + 1$, it forwards the packet,
increments the $n$ (line 4), and then calls the same RELEASE-PKTS function
(see Algorithm 1).

Unlike the POF algorithm, if the sequence number of the packet is
greater than $n+1$, it checks if the buffer is full, like the LFRA algorithm
(line 7). If it is not full, it calls the STORE-PKT function to store the packet
in the buffer, computes the timeout value based on the path of the
packet, and starts a time that will call the TIME-EXPIRED function (see
Algorithm 1). If the buffer is full, it finds the packet with the smallest
sequence number among all the packets in the buffer and the current
packet (line 10, and it forwards it (stopping the timer if needed).

**Algorithm 3** The PBAAPOF algorithm.

STORE-PKT(pkt, conn_state, buffer)
1   bufferstore(pkt)
2   T = Compute–Timer–Value(pkt)
3   START–TIMER(pkt.seq_num, T,
               TIMER–EXPIRED(pkt, conn_state,
                               buffer))

PROCESS-PACKET(pkt, conn_state, buffer)
1   if pktseq_num ≤ conn_state.n + 1
2     Forward–Packet(pkt)
3     if pktseq_num == conn_staten + 1
4       conn_staten = conn_staten + 1
5     RELEASE–PCKTS(pkt, conn_state, buffer)
6   else
7     if bufferfull == FALSE
8       STORE–PKT(pkt, conn_state, buffer)
9     else
10    pkt' = Get–Min–Packet(buffer)
11    if pkt'seq_num < pktseq_num
12      Forward–Packet(pkt')
13      Stop–Timer(pkt'seq_num)
14      STORE–PKT(pkt, conn_state, buffer)
15    else
16    Forward–Packet(pkt)

5. Reordering metrics

RFC 4737 [27] defines several metrics applicable to DetNet systems. Among these, RTO and RBO are relevant for the reordering algorithms as they can determine the timeout values and buffer size, respectively. The Reordered packet Ratio is a useful metric when comparing different simulations, as it quantifies the amount of packet reordering.

5.1. Reordered packet ratio

Let $k$ be the next expected sequence number and $s$ the sequence number of the incoming packet. The packet is considered in order if $s \ge k$, in which case $k \leftarrow s + 1$. Otherwise (i.e., if $s < k$), the packet is considered reordered, and $k$ is not incremented.

Let $L$ be the number of unique sequence numbers observed (i.e., excluding duplicated packets). Then the Reordered Packet Ratio is:

$$
R = \frac{r}{L}
$$

where $r$ is the total number of reordered packets. When receiving a
packet multiple times, only the first copy is considered when computing
$r$ (Section 4.1.3 of RFC 4737 [27]).

5.2. Reordering late-time offset

Let $E_i$ be the time packet $i$ arrives at the reordering function or, more generally, at any given observation point. For duplicated packets, $E_i$ is the earliest arrival time for one of the copies. Given that packets can be out of order, it is possible for packet $j$, with $j > i$, to arrive before packet $i$, i.e., $E_j < E_i$. The Reordering late-time offset (RTO) $\lambda_i$ of packet $i$ is the largest amount of time by which a packet $j$ (with $j > i$) has to wait for packet $i$:

$$
\lambda_i = E_i - \min_{j \mid j \ge i} E_j
$$
For a connection, the RTO is $max_i \lambda_i$, where the maximum is taken over all received packets, ignoring lost packets, for which $E_j$ is $\infty$. For a given connection, the RTO is the maximum time any packet has to wait in the reordering buffer before it can be released in order.

### 5.3. Reordering Byte Offset

Similarly to the RTO, the RBO for packet $i$ is the sum of all the bytes in the packets that have arrived before packet $i$ ($E_j < E_i$) and whose sequence number greater than $i$:

$$ \pi_i = \sum_{j | j > n, E_j < E_i} l_j $$

where $l_j$ is the length of packet $j$. For a connection, the RBO is $max_i \lambda_i$, where the maximum is taken over all received packets, ignoring lost packets, for which $\pi_i$ is not defined. RBO indicates how many bytes are needed in the reordering buffer to store out-of-order packets.

## 6. Network calculus bounds

The definitions of RTO and RBO presented in the previous section can be used only when one knows the arrival times of all the packets of a connection. It is, therefore, preferable to obtain upper bounds, ideally achievable, for these quantities. Mohammadpour and Le Boudec [25] use the Network Calculus framework to derive tight bounds on the RTO and RBO under the assumption that the delay in the network is bounded and the input flow satisfies an envelope.

After an overview of the existing results, we conclude the section with a new bound for the RTO for path-aware reordering algorithms, such as the advanced version of the POF algorithm and the PBAAPOF algorithm.

### 6.1. RTO and RBO bounds for the POF algorithm

Let $d_i$ be the delay of the $i$th packet and a given observation point (the reordering function in our case). Considering only the packets that are not lost of a connection, one can define the delay jitter $V$ as:

$$ V = \max_i \{d_i\} - \min_j \{d_j\}. \qquad (1) $$

Theorem 5 of [25] states that, if the arrival flow has input envelope $\alpha$, then:

$$ [V - \alpha^{\perp}(2l, 0)]^{+} \qquad (2) $$

is an upper bound for the RTO, where $[a]^{+} = \max[a, 0]$, $\alpha$ is the input envelope, $l$ is the minimum packet length of the flow, and $\alpha^{\perp}$ is the lower pseudoinverse of the envelope, defined as $F^{\perp}(x) = \inf\{s \ge 0 | F(s) \ge x\}$ [28].

Theorem 6 of [25] gives the following upper bound for the RBO, assuming, again, that the arrival flow has input envelope $\alpha$: $\max(\alpha(V) - l, 0)$.

### 6.2. RTO bound for the advanced POF and PBAAPOF algorithms

As explained in Section 4, the advanced POF and PBAAPOF algorithms use a per-path timeout. Therefore, while still valid, the bound provided above is not the best one for all the paths. Given that, in most cases, each path has a different maximum and minimum delay, we can define $D^{(p)}$ and $d^{(p)}$ as the maximum and minimum delay, respectively, on path $p$.

**Proposition 1.** If all the paths are First In First Out (FIFO), and if a flow has input envelope $\alpha$, with minimum packet size $l$, then for packets received on path $p$:

$$ E_{n-1} - E_n \le \left[ \max_{q \ne p} \{D^{(q)}\} - d^{(p)} - \alpha^{\perp}(2l) \right]^{+}. \qquad (3) $$

$$ \begin{array}{l} k = 0 \qquad \begin{array}{cccc} a_1 & a_2 & a_3 & x \\ b_1 & x & b_3 & b_4 \end{array} \\ \hline k = 1 \qquad \begin{array}{cccc} a_1 & x & a_3 & a_4 \\ b_1 & \textcircled{2} & b_3 \end{array} \\ \hline k = 2 \qquad \begin{array}{cccc} a_1 & x & x & a_4 & a_5 & a_6 \\ b_1 & \textcircled{2} & \textcircled{3} & b_4 \end{array} \end{array} $$

<caption>**Fig. 3.** A few reordering examples. Lost packets are represented by an “x”. Circled packets are reordered.</caption>

**Proof.** Let $A_n$ be the time when the source sends packet $n$. If the arrival process has envelope $\alpha$, it follows that [25]:

$$ A_n - A_{n-1} \ge \alpha^{\perp} (l_n + l_{n-1}). \qquad (4) $$

Given that $\alpha$ is wide sense increasing and $l$ is the minimum packet size; (4) implies that:

$$ A_{n-1} \le A_n - \alpha^{\perp}(2l). \qquad (5) $$

If packet $n$ has arrived on path $p$, we have that:

$$ E_{n-1} \le A_{n-1} + \max_{q \ne p} D^{(p)} \qquad (6) $$

$$ \le A_n - \alpha^{\perp}(2l) + \max_{q \ne p} D^{(p)} \qquad (7) $$

$$ \le E_n - d^{(p)} - \alpha^{\perp}(2l) + \max_{q \ne p} D^{(p)} \qquad (8) $$

where (6) follows from the definition of $A_n$, $E_n$, $D^{(p)}$ and the fact that, as each path is FIFO, if packet $n$ has arrived on path $p$, and any packet $m \le n - 1$ is missing, it suffices to wait for packet $n - 1$, which, if it arrives, it will arrive on a different path. Eq. (5) implies (7), and (8) follows from the fact that packet $n$ was received at time $E_n$ on path $p$, hence $A_n \le E_n - d^{(p)}$. The claim follows immediately by rearranging the terms. $\square$

## 7. Reordering ratio computation with no retransmissions

When there are no retransmissions, the reordering ratio can be computed as the probability that a packet is reordered. Suppose there are two disjoint paths between the node implementing the packet replication function and the node where the two paths merge, and that packet inter-arrival times are constant multiples of the slot frame duration. Then, for any given schedule, whenever both copies of a packet arrive at the merge node, the time difference between the two arrival times is constant. The difference between the sequence numbers of two consecutive packets received at the merge node is also constant.

Let $a_i$ and $b_i$ be the copies of each packet (with sequence number $i$) sent on the two different paths. Without loss of generality, assume that path $a$ is faster. If the delay difference between the two paths is less than a slotframe, then packet $a_i$ is followed by packet $b_i$, which is followed by packet $a_{i+1}$, and so on, again assuming that these packets are not lost. In this case, we say that the “sequence number offset” $k$ between the two paths is 0.

Similarly, if the delay difference between the two paths is more than a slotframe but less than two, packet $a_i$ is followed by packet $b_{i-1}$, which is followed by packet $a_{i+1}$ (again assuming that all three packets arrive successfully). In this case, $k = 1$.

Fig. 3 shows one example for three values of $k$ (an “x” represents a lost packet). If $k = 0$, reordering is not possible. No matter which packets are lost, none of the correctly received packets can be considered as reordered. Recall that the definition of reordered packets considers only the first copy of the received packet. If $k = 1$ or $k = 2$, reordering is possible, as shown in the example with packet $b_2$ ($k = 1$) and packets $b_2$ and $b_3$ ($k = 2$).
<figure><img src="image_5.png" /><figcaption>Fig. 4. The reordering probability ($p_r$) as a function of the success probability on path a ($p_a$) for $p_b = 0.8$, see Eq. (9).</figcaption></figure>

If packet losses are independent and identically distributed random variables, and $p_a$ and $p_b$ are the probability that a packet arrives successfully at the merge node on path a and b, respectively, then the probability that packet i is reordered is

$$p_r = [1 - (1 - p_a)^k] (1 - p_a)p_b. \quad (9)$$

Packet i is reordered if it is lost on path a (probability $1-p_a$), and if it is successfully delivered on path b (probability $p_b$), and if at least one packet between packets i-k and i is successfully delivered on path a (probability $1-(1-p_a)^k$). As expected, $p_r = 0$ if $k = 0$, or if $p_a = 1$ (recall that packets arrive first on path a), or if $p_a = 0$; and larger values of k correspond to larger values of $p_r$.

The reordering probability is monotonically increasing with $p_b$, which is again consistent with the assumption that packets arrive first on path a: a packet lost on both paths is not reordered; therefore, the higher $p_b$ is, the more likely it is that a packet lost on path a will arrive on path b resulting in a reordered packet (provided at least one packet arrived on path a as well). Given that the derivative with respect to $p_a$ of (9) is

$$p_b [(k+1)(1-x)^k - 1]$$

which has a root at

$$p_a^* = 1 - \sqrt[k]{\frac{1}{k+1}},$$

$p_r$ is maximized when $p_a = p_a^*$.

Fig. 4 shows three plots of $p_r$ as a function of $p_a$, with $p_b = 0.8$. For a given $p_b$, if $p_a$ is small, $p_r$ is also small, given that most packets are lost on path a, reducing the number of reordered packets. Similarly, if $p_a$ is close to 1, most packets cannot be reordered as they arrive on path a, resulting in a small $p_r$. If $k = 1$, $p_a^* = 1/2$ and $p_r = p_b/4$. If $k = 2$, $p_a^* = 1 - \sqrt{1/3}$ and $p_r = \sqrt{1/3}(2/3)2p_b$.

## 8. Simulation configuration

We have used the 6TiSCH simulator [29]<fnref n="1" /> to compare the performance of the algorithms discussed in Section 4 in a 6TiSCH network [30]. We added support for multipath to the simulator, as the original version does not include this feature.

We have simulated two network topologies: one with seven nodes and two paths between the source and the merge node, and another with ten nodes and three paths. The simulations use the RPL routing

<figure><img src="image_6.png" /><figcaption>Fig. 5. The network topology used for the simulations with two paths.</figcaption></figure>

protocol, with the objective function OF0, which ranks the neighbors based on the expected number of transmissions needed to successfully transmit a packet (known as the ETX metric).

Fig. 5 shows the simulated topology: node 6 is the source and node 0 is the destination. There are two paths from the source to the destination: path 1 (nodes 6, 3, 1, 0) and path 2 (nodes 6, 5, 4, 2, 1, 0). The first path is shorter but has two links with higher packet loss probability (low quality in the figure), while all the links in the longer path have a lower packet loss probability.

Fig. 6 shows the topology with three paths: node 9 is the source, and node 0 is the destination. The three paths are: path 1 (nodes 9, 4, 3, 2, 1, 0), path 2 (nodes 9, 3, 1, 0), path 3 (nodes 9, 8, 7, 6, 1, 0); with high, low, and medium link qualities, respectively.

In both cases, the source sends a copy of every packet on each path. Node 1 runs the elimination function and the reordering algorithm.

The transmission schedule is the same throughout each simulation and is negotiated by the 6top layer in the setup phase of each simulation. We reduced the standard slotframe size from 101 cells to nine in the simulations with two paths and 13 in the simulations with three paths so that each link in the network has precisely one dedicated cell in each slotframe, as each slotframe has two dedicated timeslots. Fig. 7 shows a sample schedule with nine timeslots.

To guarantee a bounded delay, we consider either no retransmissions or one at most if a packet is lost on any of the links. As both the schedule and the retransmission strategy are fixed for each simulation, it is possible to combine these two elements to easily compute the minimum and maximum delay for a packet between the source and the merge node.

For example, for the schedule in Fig. 7, the minimum delay is four timeslots for path 1 and 20 for path 2 when the source (Node 6) has a packet to send right before the beginning of timeslot 1 on path 1 and timeslot 5 on path 2. If there are no retransmissions, the worst case is 13 cells on path 1 and 29 on path 2, when the source has a packet to send right after the beginning of timeslot 1 on path 1 and timeslot 5 on path 2. In the case of one retransmission, the worst case is $T(N+1)$ where T is the number of timeslots in a cycle (9), and N is the number of hops: two for path 1 and four for path 2.

The input traffic has envelope $\alpha(t) = \sigma + \rho t$, with $\sigma$ set to one or five packets, and $\rho$ to one packet every slotframe in the simulations with no retransmissions and one packet every two slotframes in the simulations with one retransmission. Note that the average packet rate (in packets per second) varies because the number of timeslots in each slotframe depends on the number of paths. In all the simulations, the timeslot duration is 10 ms, and the queue size at all the nodes, except the merge node, is 15 packets.

Table 1 summarizes the simulation parameters.

As explained in Section 6, we can derive an upper bound on the RTO by using Eq. (2) (Theorem 5 of [25]). In our case, the lower pseudo-inverse of the input envelope is [25] $\alpha(x)^{\downarrow} = [(x - \sigma)/\rho]^+$. Hence, equation (2) becomes:

$$[V - \left[ \frac{2l - \sigma}{\rho} \right]^+]^+ \quad (10)$$

where l is the (minimum) packet size, which is constant in our case.

<footnote n="1">¹ https://bitbucket.org/6tisch/simulator/src</footnote>
<figure><img src="image_7.png" /><figcaption>Fig. 6. The network topology used for the simulations with three paths.</figcaption></figure>

<table><caption>Fig. 7. A schedule example.</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><th>Ch. 1</th><td>Shared</td><td>6 → 3</td><td></td><td>5 → 4</td><td>3 → 1</td><td>6 → 5</td><td>2 → 1</td><td>1 → 0</td><td>AutoRx</td></tr><tr><th>Ch. 2</th><td>Shared</td><td></td><td>4 → 2</td><td></td><td></td><td></td><td></td><td></td><td>AutoRx</td></tr></tbody></table>

**Table 1**

Summary of simulation parameters, where $τ_s$ is the timeslot duration, $N_f$ is the number of timeslots in a slotframe, RTX is the maximum number of retransmissions, and $l$ is the packet size. The first four lines refer to the simulations in Section 9.1 (Reordered Packet Ratio) and the last two to the algorithm comparison in Section 9.2.

<table><thead><tr><th></th><th>Nodes</th><th>τ<sub>s</sub> (ms)</th><th>N<sub>f</sub></th><th>RTX</th><th>l (B)</th><th>σ (B)</th><th>ρ (B/s)</th></tr></thead><tbody><tr><td>RPR (1 path)</td><td>7</td><td>10</td><td>9</td><td>0</td><td>90</td><td>450</td><td>10000</td></tr><tr><td>RPR (1 path)</td><td>7</td><td>10</td><td>9</td><td>1</td><td>90</td><td>459</td><td>5000</td></tr><tr><td>RPR (2 paths)</td><td>10</td><td>10</td><td>13</td><td>0</td><td>90</td><td>450</td><td>6923</td></tr><tr><td>RPR (2 paths)</td><td>10</td><td>10</td><td>13</td><td>1</td><td>90</td><td>450</td><td>3462</td></tr><tr><td>Alg. comparison (1 path)</td><td>7</td><td>10</td><td>9</td><td>0</td><td>90</td><td>90</td><td>10000</td></tr><tr><td>Alg. comparison (2 paths)</td><td>10</td><td>10</td><td>13</td><td>0</td><td>90</td><td>90</td><td>6923</td></tr></tbody></table>

Similarly, the RTO bound for the advanced POF and PBAAPOF algorithms, based on Eq. (3) becomes:

$$ \left[ \max_{q \neq p} \{D^{(q)}\} - d^{(p)} - \left[ \frac{2l - \sigma}{\rho} \right]^{+} \right]^{+} \quad (11) $$

As discussed in Section 2.3, the IEEE Std 802.15.4 frames have a maximum payload of 127 bytes. Therefore, as long as the payload is less than 127 bytes, it will be transmitted in a single timeslot and within a single Layer 2 frame. In this study, we assume that the Layer 2 payload (i.e., IPv6 and UDP headers, and the application data) is less than 102 bytes, i.e., 127 bytes (Layer 2 MTU) minus 23 bytes (Layer 2 Header) and minus 2 bytes (Layer 2 Footer). Therefore, packets will not be fragmented by the 6LoWPAN adaptation layer. Otherwise, the 6LoWPAN fragments the application payload. Such a scenario introduces several challenges that we do not address in this work. For instance, if a fragment is lost, all the other fragments are useless, and there is no point in reordering them.

As shown in Table 1, we used a packet size of 90 B (including all the headers) for the simulations. The 6TiSCH simulator [29] takes into account the total packet length to determine whether a packet needs to be fragmented, and does not explicitly build the different protocol headers. Metadata associated with the packet carries the Layer 2 and 3 addresses and all other information needed in the simulations. Without header compression a packet size of 90 B implies an application payload of 17 B (25 B for Layer 2, and 48 B for IPv6 and UDP). With header compression the IPv6 and UDP headers can be reduced for example to 5 B to 10 B, leaving 55 B to 60 B.

## 9. Simulation results

For each topology presented in Section 8, we ran two sets of simulations: one to quantify the amount of packet reordering in the

**Table 2**

Reordering Probability values for different PDR combinations.

<table><thead><tr><th>PDR low</th><th>PDR high</th><th>p<sub>a</sub></th><th>p<sub>b</sub></th><th>p<sub>r</sub> (k = 1)</th><th>p<sub>r</sub> (k = 2)</th></tr></thead><tbody><tr><td>0.68</td><td>0.86</td><td>0.471</td><td>0.548</td><td>0.136</td><td>0.209</td></tr><tr><td>0.75</td><td>0.95</td><td>0.562</td><td>0.815</td><td>0.200</td><td>0.289</td></tr></tbody></table>

network and another to compare the performance of different reordering algorithms. In each simulation, the source (Node 6 or Node 9) sends 5000 packets to the destination (Node 0).

### 9.1. Packet reordering ratio

As discussed in Section 7, the reordering ratio depends on the PDRs of each link and on the transmission schedule, as the latter determines the difference of the sequence numbers of consecutive packets at the merge node. For different combinations of PDRs, we pick a random schedule at the beginning of each simulation to ensure that the results do not depend on the specific TSCH schedule.

#### 9.1.1. Two paths

For the topology with two paths, the PDR of the high-quality and low-quality links are either (0.86, 0.68) respectively, or (0.95, 0.75); and the retransmissions (RTX) are either zero or one. We ran 200 simulations for each of the four possible combinations of these parameters.

Fig. 8 shows the Cumulative Distribution Function (CDF) of the reordering ratio and the box plot of the end-to-end delay (latency). Each CDF of the reordering ratio is concentrated around three values, with a bigger jump around 0, i.e., no packet reordering at all. This is consistent with the model presented in Section 7: these jumps correspond to a sequence number offset $k$ of 0, 1, or 2, respectively.

Table 2 shows the values of the success probability on the path with low-quality links ($p_a$), the success probability on the other path ($p_b$), and the reordering probability ($p_r$) for the PDRs used in the simulations of Fig. 8. The jumps of the CDF for the simulations without retransmissions correspond to the values given in Table 2. The fact that both CDFs have a jump close to 20% is a coincidence. As each simulation uses a different random schedule, it is not surprising that the smaller jumps correspond to $k = 1$ and $k = 2$, as fewer schedules can produce such a delay difference between the two paths.

In the case of retransmissions, $k$ is not a constant that depends only on the schedule, as it can change from one packet to another. In this case, more packets are correctly delivered, reducing the reordering. As expected, the latency is higher with retransmissions, as shown in Fig. 8(b).
<figure><img src="image_8.png" /><figcaption>**Fig. 8.** Reordering Packet Ratio levels measured at the merge node (a), and average end-to-end latencies (b) for different link quality and retransmission configurations. Each setup was run 200 times. In each run, the source sends 5000 packets replicated on the two paths in Fig. 5.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Fig. 9.** Reordering Packet Ratio levels measured at the merge node (a), and average end-to-end latencies (b) for different link quality and retransmission configurations. Each setup was run 200 times. In each run, the source sends 5000 packets replicated on the three paths in Fig. 6.</figcaption></figure>

### 9.1.2. Three paths

The topology with three paths has three PDR values, resulting in a larger number of possible combinations. Among these, we selected the following three: (0.68, 0.75, 0.86), (0.68, 0.75, 0.95), (0.75, 0.86, 0.95), where the first value is the PDR of the low-quality links, the second one of the medium-quality links, and the third one of the high-quality links. As we did for the topology with two paths, we ran 200 simulations, each with a different random schedule.

Fig. 9 shows the CDF of the reordering ratio at the merge node (left) and the box plot of the average latency (right) for the three path topology. There are no clear jumps, as in the CDF for the two-path topology. This can be explained by the fact that, as there are three paths, even without retransmissions, the difference in the sequence number of consecutive packets received by the merge node depends on the delay difference between paths 1 and 2, and paths 2 and 3. Unsurprisingly, the reordering ratio is lower when packets are retransmitted in case of loss, as in the two-path topology. Once more, retransmissions result in a higher average delay, as the box plots show, but a lower reordering ratio.

## 9.2. Reordering algorithms comparison

Reordering is more prevalent when there are no retransmissions. This setting has the advantage of having a lower and constant delay (for the delivered packets), which is especially relevant in a deterministic network setting.

We assess the performance of the algorithms presented in Section 4 in a second set of simulations, with the same topologies (see Fig. 5, and Fig. 6).

<figure><img src="image_10.png" /><figcaption>**Fig. 10.** The empirical CDF of the end-to-end latency (in seconds) with different reordering algorithms, with a buffer size of 3 packets (top) and 2 packets (bottom).</figcaption></figure>

### 9.2.1. Two paths

We simulated a network with no retransmissions and with a high-quality and low-quality link PDR of 0.95 and 0.75, respectively. The schedule is the one in Fig. 7, resulting in a Reordering Packet Ratio of
<figure><img src="image_11.png" /><figcaption>Fig. 11. The buffer occupancy with a buffer size of 3 packets (left) and 2 packets (right). The frequencies of an empty buffer are not shown.</figcaption></figure>

<table><caption>**Table 3**

Fraction of packets successfully delivered in the simulations with two paths.</caption><thead><tr><td>Algorithm</td><td>Buffer Size 3</td><td>Buffer Size 2</td></tr></thead><tbody><tr><td>Basic POF</td><td>0.8788</td><td>0.8788</td></tr><tr><td>LFRA</td><td>0.8772</td><td>0.8772</td></tr><tr><td>Advanced POF</td><td>0.8756</td><td>0.8756</td></tr><tr><td>PBAAPOF</td><td>0.8804</td><td>0.8804</td></tr></tbody></table>

29%. We use the same schedule for all the simulations in this set. The reordering algorithm runs on node 1, i.e., where the two paths merge, which is the best location for lossy networks [25].

Each simulation consists of 5000 packets and uses the same random seed so that exactly the same packets are lost for all the algorithms. The interval between the packets the source sends is nine or ten timeslots (with equal probability). Therefore, the input envelope is a $(\sigma, \rho)$ envelope with bursts $(\sigma)$ of one packet and a rate $(\rho)$ of one packet every nine timeslots. With these values, the RBO bound is three packets (see Section 6).

Fig. 10 shows the empirical CDF of the end-to-end latency for different algorithms for the packets successfully delivered to the destination. The PBAAPOF and Advanced POF algorithms have the same latency distribution, which dominates the distribution of the basic POF and LFRA algorithms.

While the network calculus RBO bound is achievable, it is a conservative value: only a few packets can achieve it. Hence, evaluating what happens with a smaller buffer is interesting, as shown in the bottom part of Fig. 10. In this case, the latency of the LFRA algorithm is lower than when the buffer size is three. The latency of the other algorithms is similar.

This can be explained by the buffer occupancy, shown in Fig. 11 for two different values (2 and 3) for the buffer size of the LFRA and PBAAPOF algorithms. As the basic and Advanced POF algorithms assume an unbounded buffer, we used a larger buffer in the simulations for these two algorithms. We omitted the bar for zero packets, i.e., empty buffer, to highlight the differences between the algorithms. Hence, the sum of the frequencies is not one.

Given that the LFRA algorithm does not use a timer, it has the highest buffer occupancy frequency for two and three packets because it stores out-of-order packets for a needlessly long time. This explains why its latency is highest when the buffer size is three and lowest when it is two.

Table 3 shows the fraction of successfully delivered packets, which are higher than the probability of successfully receiving a packet on the high-quality path (0.774). Recall that the Basic and Advanced POF algorithms use a larger buffer size, hence the fraction of packets delivered is the same, regardless of the buffer size used for the LFRA and PBAAPOF algorithms. It so happens that, in this configuration, the fraction of delivered packets is also the same for the other two algorithms, regardless of the buffer size.

<figure><img src="image_12.png" /><figcaption>Fig. 12. The empirical CDF of the end-to-end latency (in seconds) with different reordering algorithms, with a buffer size of 3 packets (top) and 2 packets (bottom) for the topology with three paths.</figcaption></figure>

### 9.2.2. Three paths

As we did for the topology with two paths, we simulated sending 5000 packets with the three-path topology: the PDRs of the low, medium, and high-quality links are 0.68, 0.75, and 0.86, respectively. The schedule is 3 → 2, 4 → 3, 9 → 5, 7 → 6, 5 → 1, 6 → 1, 9 → 8, 2 → 1, 8 → 7, 1 → 0, 9 → 4.

The source sends a packet every 13 or 14 timeslots with equal probability, resulting in a $(\sigma, \rho)$ envelope with a burst size of one packet and an average rate of one packet every 13 timeslots. We used the same random seeds for all the simulations so that the same packets would be lost each time.

Fig. 12 shows the CDF of the end-to-end latency with the four algorithms. When the buffer size is 3, LFRA has the highest latency, and the Advanced POF and PBAAPOF algorithms have the same latency. When the buffer size is 2, the Basic POF algorithm has the highest latency, and PBAAPOF has the lowest latency. In this case, there is a difference between the Advanced POF and PBAAPOF algorithms.

This is consistent with the buffer occupancy shown in Fig. 13. When the buffer size is 3, LFRA has three packets in the buffer almost 20% of the time and two packets roughly 15%, while the other algorithms have much lower values. The same pattern holds for two packets in the buffer. When the buffer size is 2, LFRA has three packets in the buffer more often than the Advanced POF and PBAAPOF algorithms. Finally, as the Advanced POF algorithm has a larger buffer, it keeps three packets in the buffer once in a while, resulting in a higher latency than the PBAAPOF algorithm.
<figure><img src="image_13.png" /><figcaption>Fig. 13. The buffer occupancy with a buffer size of 3 packets (left) and 2 packets (right) for the topology with three paths. The frequencies of an empty buffer are not shown.</figcaption></figure>

<table><caption>**Table 4**

Fraction of packets successfully delivered in the simulations with three paths.</caption><thead><tr><td>Algorithm</td><td>Buffer Size 3</td><td>Buffer Size 2</td></tr></thead><tbody><tr><td>Basic POF</td><td>0.6990</td><td>0.6990</td></tr><tr><td>LFRA</td><td>0.6926</td><td>0.6992</td></tr><tr><td>Advanced POF</td><td>0.6944</td><td>0.6944</td></tr><tr><td>PBAAPOF</td><td>0.6896</td><td>0.6970</td></tr></tbody></table>

Table 4 gives the fraction of packets successfully delivered for the simulations with three paths. Recall that the Basic and Advanced POF algorithms use a buffer with a larger and fixed size, so the corresponding values are the same in each column. The LFRA algorithm performs slightly better than the PBAAPOF one. Note that all the values in the table are larger than 0.47, which is the probability of successfully delivering a packet on the high-quality path.

## 10. Conclusions

Exploiting path diversity in a 6TiSCH network can increase the reliability even without retransmissions, but at the cost of packet reordering, which can reach 30%. We presented a simple model to compute the reordering probability on any topology with two paths without packet retransmissions. The reordering probability is a function of the PDR of each link and of the transmission schedule, which could be adapted to reduce the amount of packet reordering.

Retransmissions increase reliability and decrease packet reordering but, unsurprisingly, result in higher latency, a drawback in delay-sensitive networks, such as those in Industrial IoT. Reordering algorithms implemented at the node(s) where multiple paths join can alleviate the packet reordering problem.

Existing reordering algorithms use different mechanisms, such as timers with an unbounded buffer or smart handling of bounded buffers. We proposed a new algorithm (PBAAPOF) that combines both approaches, resulting in lower latency and lower buffer occupancy, which are desirable properties in resource-constrained networks. We extended existing Network Calculus results to obtain potentially smaller timeout values, which can be applied in the Advanced POF and PBAAPOF algorithms.

The downside of PBAAPOF, shared by the Advanced POF algorithm, is the need to know the path taken by each packet. This can be avoided by combining the buffer-size-aware part of the algorithm, taken from the LFRA algorithm, with the basic version of the POF algorithm. Further studies will focus on this solution and on more complex topologies with multiple paths merging at different nodes.

### CRediT authorship contribution statement

Juan-Cruz Piñero: Writing – review & editing, Writing – original draft, Visualization, Software, Investigation, Formal analysis, Conceptualization. Alberto Blanc: Writing – review & editing, Writing – original draft, Visualization, Supervision, Software, Methodology, Investigation, Formal analysis, Data curation. José Ignacio Alvarez-Hamelin: Writing – original draft, Supervision, Conceptualization. Georgios Z. Papadopoulos: Writing – review & editing, Writing – original draft, Visualization, Supervision, Project administration, Methodology, Investigation, Formal analysis, Conceptualization.

### Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

### Data availability

Data will be made available on request.

### References

[1] P. Thubert, D. Cavalcanti, X. Vilajosana, C. Schmitt, J. Farkas, Reliable and available wireless (RAW) technologies, 2025.

[2] C.J. Bernardos, G.Z. Papadopoulos, P. Thubert, F. Theoleyre, Reliable and available wireless (RAW) use cases, 2023, RFC 9450.

[3] N. Finn, P. Thubert, B. Varga, J. Farkas, Deterministic networking architecture, 2019, http://dx.doi.org/10.17487/RFC8655, IETF RFC 8655.

[4] B. Varga, J. Farkas, S. Kehrer, T. Heer, Deterministic networking (DetNet): Packet ordering function, 2024, http://dx.doi.org/10.17487/RFC9550, RFC 9550. URL: https://www.rfc-editor.org/info/rfc9550.

[5] P. Thubert, An architecture for IPv6 over the time-slotted channel hopping mode of IEEE 802.15.4 (6TiSCH), 2021, RFC 9030, IETF.

[6] J.-C. Piñero, A. Blanc, J.I. Alcareaz Hamelin, G.Z. Papadopoulos, Packet ordering functions in low-power wireless deterministic networks, in: Proceedings of the 23rd IFIP Networking Conference (IFIP Networking), 2024, pp. 177–185, http://dx.doi.org/10.23919/IFIPNetworking62109.2024.10619804.

[7] IEEE standard for low-rate Wireless Personal Area networks (LR-WPANs), 2016, IEEE Std 802.15.4-2015 (Revision of IEEE Std 802.15.4-2011).

[8] T. Winter, et al., RPL: IPv6 routing protocol for low-power and lossy networks, 2012, RFC 6550, IETF.

[9] J. Hui, P. Thubert, Compression format for IPv6 datagrams over IEEE 802.15.4-based networks, 2011, IETF, RFC 6282.

[10] Q. Wang, X. Vilajosana, T. Watteyne, 6TiSCH operation sublayer (6top) protocol (6P), 2018, RFC 8480, IETF.

[11] T. Chang, et al., 6TiSCH minimal scheduling function (MSF), 2021, RFC 9033, IETF.

[12] N. Kushalnagar, G. Montenegro, C. Schumacher, IPv6 over low-power Wireless Personal Area networks (6LoWPANs): Overview, assumptions, problem statement, and goals, 2007, IETF RFC 4919.

[13] G. Montenegro, N. Kushalnagar, D. Culler, Transmission of IPv6 packets over IEEE 802.15.4 networks, 2007.

[14] P. Thubert, Reliable and available wireless architecture, 2025, draft-ietf-raw-architecture-24, IETF.

[15] R.-A. Koutsiamanis, G.Z. Papadopoulos, T.L. Jenschke, P. Thubert, N. Montavont, Meet the PAREO functions: Towards reliable and available wireless networks, in: ICC 2020 - 2020 IEEE International Conference on Communications, ICC, 2020, pp. 1–7, http://dx.doi.org/10.1109/ICC40277.2020.9149206.

[16] T.L. Jenschke, et al., Odese: On-demand selection for multi-path RPL networks, Elsevier Ad Hoc Netw. 114 (2021) 102431.
[17] S. Spirou, Packet reordering effects on the subjective quality of broadband digital television, in: IEEE ISCE, 2006, pp. 1–6, http://dx.doi.org/10.1109/ISCE.2006.1689474.

[18] E. Blanton, M. Allman, On making TCP more robust to packet reordering, ACM SIGCOMM Comput. Commun. Rev. 32 (2002) http://dx.doi.org/10.1145/510726.510728.

[19] C. Arthur, et al., The effects of packet reordering in a wireless multimedia environment, in: Proceedings of the 1st ISWCS, 2004, pp. 453–457, http://dx.doi.org/10.1109/ISWCS.2004.1407288.

[20] D. Kaspar, K. Evensen, A.F. Hansen, P. Engelstad, P. Halvorsen, C. Griwodz, An analysis of the heterogeneity and IP packet reordering over multiple wireless networks, in: Proceedings of the 14th IEEE ISCC, 2009, pp. 637–642, http://dx.doi.org/10.1109/ISCC.2009.5202249.

[21] K. Evensen, et al., A network-layer proxy for bandwidth aggregation and reduction of IP packet reordering, in: Proc. of the 34th IEEE LCN, 2009, pp. 585–592, http://dx.doi.org/10.1109/LCN.2009.5355198.

[22] R.M. Narasiodeyar, et al., Improvement in packet-reordering with limited re-sequencing buffers: An analysis, in: Proc. of the 38th IEEE LCN, 2013, pp. 416–424, http://dx.doi.org/10.1109/LCN.2013.6761274.

[23] R.-A. Koutsiamanis, et al., From best effort to deterministic packet delivery for wireless industrial IoT networks, IEEE Trans. Ind. Inform. 14 (10) (2018) 4468–4480, http://dx.doi.org/10.1109/TII.2018.2856884.

[24] J.-Y.L. Boudec, P. Thiran, Network calculus: A theory of deterministic queuing systems for the internet, in: Lecture Notes in Computer Science, Springer, 2001.

[25] E. Mohammadpour, J.-Y. Le Boudec, On packet reordering in time-sensitive networks, IEEE/ACM Trans. Netw. 30 (3) (2022) 1045–1057, http://dx.doi.org/10.1109/TNET.2021.3129590.

[26] L. Thomas, A. Mifdaoui, J.-Y. Le Boudec, Worst-case delay bounds in time-sensitive networks with packet replication and elimination, IEEE/ACM Trans. Netw. 30 (6) (2022) 2701–2715, http://dx.doi.org/10.1109/TNET.2022.3180763.

[27] A. Morton, G. Ramachandran, S. Shalunov, L. Ciavattone, J. Perser, Packet reordering metrics, 2006, http://dx.doi.org/10.17487/RFC4737, RFC 4737.

[28] J. Liebeherr, Duality of the max-plus and min-plus network calculus, Found. Trends Netw. 11 (3–4) (2017) 139–282, http://dx.doi.org/10.1561/1300000059.

[29] E. Municio, G. Daneels, M. Vučinić, S. Latré, J. Famaey, Y. Tanaka, K. Brun, K. Muraoka, X. Vilajosana, T. Watteyne, Simulating 6TiSCH networks, Trans. Emerg. Telecommun. Technol. 30 (3) (2019) http://dx.doi.org/10.1002/ett.3494.

[30] D. Hauweele, R.-A. Koutsiamanis, B. Quoitin, G.Z. Papadopoulos, Thorough performance evaluation & analysis of the 6TiSCH minimal scheduling function (MSF), J. Signal Process. Syst. (2021) Springer.