Arij Elmajed
email: arij.elmajed@nokia.com

Armen Aghasaryan
email: armen.aghasaryan@nokia.com

Eric Fabre
email: eric.fabre@inria.fr

Machine Learning Approaches to Early Fault Detection and Identification in NFV Architectures

Keywords: NFV, virtualization, network management, root cause analysis, fault identification and localization, Machine Learning, Max-Likelihood, fault injection, interventional learning

Virtualization technologies become pervasive in networking, as a way to better exploit hardware capabilities and to quickly deploy tailored networking solutions for customers. But these new programmability abilities of networks also come with new management challenges: it is critical to quickly detect performance degradation, before they impact Quality of Service (QoS) or produce outages and alarms, as this takes part in the closed loop that adapts resources to services. This paper addresses the early detection, localization and identification of faults, before alarms are produced. We rely on the abundance of metrics available on virtualized networks, and explore various data preprocessing and classification techniques. As all Machine Learning approaches must be fed with large datasets, we turn to our advantage the softwarization of networks: one can easily deploy in a cloud the very same software that is used in production, and analyze its behaviour under stress, by fault injection.

I. INTRODUCTION

By virtualizing the network functions and decoupling them from hardware appliances and physical locations, the Network Function Virtualization (NFV) paradigm is a tremendous opportunity for enhancing networks operation. The possibility of developing Virtual Network Functions (VNF) using general-purpose programming languages and running them on commodity hardware provides a high level of flexibility and agility, as well as a faster time to market for new services and upgrades. It enables telecom operators to simplify, rationalize and develop a sustainable deployment of technical solutions.

In spite of its benefits, NFV also comes with an increase of complexity at different levels, and raises new challenges, especially for Network Management, where operators spend a tremendous amount of their time to ensure the reliability of the services offered to their customers.

One of the hardest challenges relates to fault and performance management. The identification of the cause, the location, and/or the type of network malfunctions that result in a degraded Quality of Service (QoS) becomes more complex in these new virtualized environments. For legacy networks, malfunctions are typically identified by metrics crossing a threshold configured by some field expert. This generates alarms which are supposed to pinpoint overload bottlenecks, faults, and failures. In reality, a malfunction generally results in cascades of correlated alarms, arising from different network layers, which renders the identification of the root cause problematic. Root cause analysis (RCA) and alarm correlation have been an active research topic for at least two decades. Virtualized networks make the problem even more difficult as more resources and additional layers are involved in the delivery of a service. But they also raise qualitatively new difficulties. The first one comes from the intrinsic dynamic architecture of such systems, which are designed to be constantly reconfigured. This is clearly an obstacle to both model-based and data-driven (learning-based) approaches to RCA. The second difficulty relates to the necessity to quickly identify a malfunction or a service degradation, possibly before metrics are severely impacted, as a quick detection and isolation is the key to adaptive resource allocation. Minimizing the human intervention and reducing the time to recovery are crucial within the paradigm of dynamic and adaptive networks realized through network virtualization. While several fault detection and localization solutions are available when the service performance and service-level agreement (SLA) are already jeopardized, here we will focus on early fault detection before an apparent QoS degradation takes place.

In this paper, we address two central challenges related to fault management in virtualized networks. One is the early detection of service degradation, before some metrics are severely impacted and trigger alarms. Our idea is that the combination of metrics, and in particular the way they jointly evolve, can be an early signature of a QoS degradation. The performance degradation sources we cover are related to typical resource shortages in virtualized environments, such as CPU overloads in virtual machines (VM), latency in messages exchanges, or overloads in disk access. The second challenge relates to the unavailability of models of the managed systems, although the (dynamic) topology might be accessible and usable. In fact, some of the RCA techniques rely on a system model and develop sophisticated diagnosis algorithms that exploit the model to infer the hidden fault states from observable variables. In dynamic virtualized networks such models are hard to obtain. In contrast, another family of techniques try to characterize fault situations by adopting a black-box approach, through a data intensive learning process. These so-called Machine Learning (ML) approaches require however labeled data which are also in general unavailable in sufficient volumes. ML requires labeled data as a starting point, which is generally a scarce resource as this means experts need to annotate logs of failure scenarios. Virtualized networks open a way around this bottleneck, as the true production software can be deployed in a controlled environment, where realistic perturbations can be injected. As we are not interested in severe failures but in yet "invisible" degradations, one can also imagine injecting such smooth perturbations in running/production services, which opens the way to reinforcement learning approaches that would adapt failure signatures to dynamic changes of architectures.

The contributions of this paper are as follows. We first propose a methodology based on the deployment of an experimental platform for virtualized network services enabled with the automated execution of resource perturbation schemes.

As an example, we deployed ClearWater, a virtualized IP Multimedia Subsystem (IMS) services over OpenStack, fed with a traffic generator (SIPp), and executed series of resource perturbations (CPU, network latency, etc.) at different application nodes. Perturbation levels on the platform are carefully calibrated so that services are not yet impacted, and users do not yet start disconnecting. We then select the relevant metrics to collect on this platform, and generate datasets labelled with the injected perturbations. Raw data are not directly usable as they exhibit dynamics specific to the current execution, e.g. they can depend on the current load of the service (the specific number and activity level of users). We thus examine several data preprocessing techniques that avoid the model over-fitting while preserving the signatures of service degradation. Finally, we compare a family of classical ML approaches, including a statistical Max-Likelihood estimation, for the detection and characterization of the injected faults.

The paper is organized as follows. Section II presents the related work. Section III introduces the experimental setting, the stress injection approach and the data collection methodology. Section IV presents our pipeline for data preprocessing and feature selection. Section V presents the Maximum Likelihood approach and other ML approaches. Section VI evaluates the effectiveness of the proposed solutions; we compare our work to related research using data from different samples and with different traffic patterns.

II. RELATED WORK

There exist many RCA techniques for fault diagnosis which can be classified according to different aspects such as problem requirements, availability of data (size, form, velocity, etc.), or availability of a formal system representation (model).

Model-based diagnosis approaches take into account the system behavior and topology to construct an abstraction of the system in terms of a model on which the fault behaviours can be explained. Some contributions rely on building fault propagation models, in [START_REF] Aghasaryan | Modeling Fault Propagation in Telecommunications Networks for Diagnosis Purposes[END_REF] authors build a behaviour model reproduced in different fault scenarios using the tile structure derived from Viterbi-based diagnosis algorithm. Sanchez et al. [START_REF] Sanchez Vilchez | Self-Modeling based Diagnosis of Services over Programmable Networks[END_REF] use a self-modelling and multi-layered approach that captures dependencies between network services in Software Defined Network (SDN) and NFV context and propose a RCA module using network topology. Authors in [START_REF] Zhu | Automatic Fault Diagnosis in Cloud Infrastructure[END_REF] propose an approach based on Edge-Rank to find the key events that contribute to a fault and construct a dependency graph with the correlations among events and metrics, and a detection graph, to find a path of events that represents a fault. And in [START_REF] Bahl | Towards Highly Reliable Enterprise Network Services Via Inference of Multi-level Dependencies[END_REF], they present a multi-level probabilistic inference model that captures the dependencies between different services in enterprise networks and describe an algorithm that uses this inference graph and service response times measurements for root cause localization.

Pham et al. [START_REF] Pham | Failure Diagnosis for Distributed Systems using Targeted Fault Injection[END_REF] use a failure injection approach to construct a database with failure profiles, then with a Top-K Nearest Faults query algorithm they recognise a specific fault pattern and pinpoint the root cause. Authors of [START_REF] Cotroneo | A Fault Correlation Approach To Detect Performance Anomalies in Virtual Network Function Chains[END_REF] use a statistical fault diagnosis, with Pearson correlation computed pairwise between neighboring nodes to detect anomalies. It is based on the fact that the Virtualized Network Functions (VNF) chain can be seen as a pipeline, where the input of the next network function of the chain is the output of the one before. These two works, only provide detection solutions without fault type identification and localization. One of the non-statistical data driven approaches uses fault injection techniques to generate data and applies a Random Forest (RF) algorithm [START_REF] Sauvanaud | Towards Black-Box Anomaly Detection in Virtual Network Functions[END_REF] to detect malfunctions and localize the root cause (one task at a time) in the context of NFV. Although these two approaches [START_REF] Cotroneo | A Fault Correlation Approach To Detect Performance Anomalies in Virtual Network Function Chains[END_REF] [7] achieve good level of accuracy, they do not provide any complexity analysis while using a high number of metrics. And, they do not address the model parameter optimization and do not check the robustness of the solution in presence of different load patterns.

For a joint data-driven diagnosis, authors in [START_REF] Mariani | Localizing Faults in Cloud Systems[END_REF] combine ML with Granger causality for temporal correlations between anomalous values of Key performance indicators (KPIs) in order to construct a causality graph and localize anomalies based on a set of graph centrality indices. The authors show a high detection accuracy and low False Positives rate, but do not address the tasks of the localization and identification simultaneously. Authors in [START_REF] Sharma | CloudPD: Problem Determination and Diagnosis in Shared Dynamic Clouds[END_REF] propose a fault management framework for clouds, where they use Hidden Markov Models (HMM) and two ML clustering algorithms (K-Nearest Neighbor KNN and K-means) to construct a correlationbased performance models to detect and recognise anomalies. Authors in [START_REF] Niwa | Anomaly Detection for OpenStack Services with Process-Related Topological Analysis[END_REF] propose an anomaly detection framework for OpenStack services. This work characterizes nominal operating modes of each process through clusters of K-means, and define a process anomaly as a significant deviations from the centroids of these clusters. The dependency graph of processes is then used to connect possibly faulty processes. In our work, we do not make use of the topology in the first place. Rather, we focus on the joint management of all processes metrics to detect and localize a malfunction before alarms are produced.

All these state-of-the-art techniques have proposed solutions for detection and localization separately and without fault type identification and when the system has already been affected by faults. Some of these works use data from a specific network gathered over a long period of time and others used fault injection approach to generate their data. In our work, we target a fault injection based approach for early fault detection (binary classification), localization and identification.

III. EXPERIMENTAL PLATFORM FOR MODEL LEARNING

A. Stimulus-based approach

Faults are rare events which makes difficult to comprehensively learn their impact unless we are provided with rigorous specification of the system's faulty behavior. While such models are not available in cloud-based networks, obtaining sufficient volumes of labeled data through passive network monitoring is not realistic neither; this would imply observing the system for a long time to encounter all types of these rare events. For these reasons, we choose an interventional approach which consists in provoking the faulty situations of interest and "shortening" the waiting time to their natural occurrence. More specifically, we apply the stimulus-based approach [START_REF] Aghasaryan | Stimulus-based Sandbox for Learning Resource Dependencies in Virtualized Distributed Applications[END_REF] which consists in methodically applying a series of elementary resource perturbations in each node of a distributed virtualized application with the purpose of elucidating causal dependencies between local and remote states. Here, we aim at discovering other types of models (statistical and ML models), different from [START_REF] Aghasaryan | Stimulus-based Sandbox for Learning Resource Dependencies in Virtualized Distributed Applications[END_REF], however we will use the same stimulus-based approach for a controlled data acquisition.

The solution is to set up an NFV based application in a private managed cloud environment and to learn its behaviour through resource perturbations without interfering with other applications; this environment is called "Sandbox"; in the present case it is an NFV-based Sandbox. The application nodes are taken as communicating black-boxes each one relying on a limited set of computing resources: CPU, memory, disk Input/Output (I/O), network I/O, etc. Given an input load, the behavior of an application is then essentially determined by the quantity of computing and communication resources consumed by the nodes. We consider therefore any types of faults that impact the computing and communication resources.

We can see the stimulus as a button that we trigger to have a system fault each time. In our case, due to the limited access to the underlying hardware layer, we consider only three perturbations categories (CPU, Disk I/O, or Network I/O). The considered faults categories are:

1) CPU stress that means increasing the CPU usage in the VM using the stress-ng tool1 ; 2) Disk stress, where the disk usage increases by using the stress-ng tool; 3) Network stress, in which the network delay increases using the open source tool tc2 .

B. Test-bed architecture

To generate faults for our solution, we used a test-bed platform. First we present the telco application which is installed in an open cloud software, OpenStack 3 , where the application nodes are IMS components from ClearWater4 open source project depicted in Fig. 1. The ClearWater IMS is an implementation of the IMS core standard [START_REF]3rd Generation Partnership Project; Technical Specification Group Services and System Aspects[END_REF]. IMS functions • Bono: it is the first point of entry in the IMS core network.

It is responsible for routing incoming SIP transactions to the IMS registrar server (the Proxy CSCF); • Sprout: it is a combined SIP registrar and authoritative routing proxy; • Dime: it provides two functions:

1) Homestead: provides web interfaces to Sprout for retrieving authentication credentials and user profile information; 2) Ralf: provides an HTTP API that both Bono and Sprout can use to report billable events.

• Vellum: it is used basically to store authentication credentials and profile information; • Homer: it is a standard XML Document Management Server (XDMS) used to store multimedia telephony service settings documents for each user of the system; • Ellis: it is a web provisioning portal to create subscribers; • SIPp5 : it is a Load generation tool; creates multiple SIPp instances each of which emulates a pair of users. It performs actions in control-plane only. At first we have ramp-up period of 10 minutes to set-up subscribers load. Each couple of the created subscribers will try to register or update the registration every 5 minutes. Then it will attempt to send an INVITE with a default probability of 16%, and RE-REGISTER with a probability of 16%. Our platform depicted in Fig. 2 is composed of several functional blocks:

• Fault catalog: which is the list of perturbations that we can emulate on the platform; • Ansible6 orchestrator: which enables us to manage and execute remotely the perturbations in our platform. The tests that are executed are organized in a playbook, that are called "perturbations"; 1) InfluxDB 7 is a time series based database for storing the metrics collected; 2) Telegraf 8 is the SNMP agent used for collecting the metrics in our VMs; 3) Grafana is our dashboard that we configure to display the graphs for the metrics that we are collecting.

• Event storage: is a MongoDB 9 database used to store the stimulus start and stop, such a stimulus or a perturbation is considered as an event with metadata indicating stimulus name, stimulated metric, and resource type.

C. Fault injection calibration

In contrast with [START_REF] Aghasaryan | Stimulus-based Sandbox for Learning Resource Dependencies in Virtualized Distributed Applications[END_REF], we are interested in early fault detection, and therefore the perturbations need to be calibrated in a way to not push the system into an outage mode. The calibration of the injected perturbations is crucial, and we performed numerous tests to select the appropriate levels. Our observation is that too severe perturbations lead to a collapse of the system: clients start being disconnected and never manage to reconnect again, so that the metric "connected users" goes to zero or stabilizes at a low value. By contrast, too small perturbations could have a non-significant influence on metrics. We thus selected a single perturbation intensity for each experiment, slightly below the collapse level, and guaranteeing at the same time that all collected metrics had stationary behaviors. 7 https://www.influxdata.com/time-series-technical-paper-2/ 8 https://www.influxdata.com/time-series-platform/telegraf/ 9 https://www.mongodb.com

We have generated perturbations with three different traffic patterns: the first one is regular traffic pattern (e.g. day traffic) with 50k subscribers, the second one represents peak periods with a 100k subscribers, and the third one with more INVITE transactions 85% and REGISTER rate of 15%. We have six different datasets: four datasets are generated with the regular traffic pattern, one with the high peak, and another one with more INVITE transactions.

D. Collected metrics

In Machine Leanring, data collection is the most critical step for building the desired knowledge, about the faulty behaviour in our context. We collected two types of metrics, some in the virtualization plane, in the form of resource-related metrics (CPU, Disk, memory, network, processes), and other in the application layer, mostly QoS metrics (latency, number of incoming INVITE/REGISTER). As the application provides numerous QoS metrics, we had to choose the most appropriate ones the learning purposes. Stationarity is an important criterion for metric selection, as the statistical properties should not change over different periods of time in a given perturbation scenario. Often, metrics come in a cumulative form (e.g. number of packets sent), then one has to replace them by their derivatives to collect instantaneous information and ensure independence of samples. Several metrics "duplicate" others, or are highly correlated. We took a single version of them. Finally, we observed periodic behaviors in data due to the scenarios executed by the traffic generation software (see Fig. 3). We rejected this nuisance by sampling our data along the different phases of these scenarios, at the expense of augmenting variance.

We end up with around 63K rows of data with 35 features 10 . Each line is thus a pair (x, y) where the feature part x = (x 0 , x 1 , ..., x 34 ) gathers our metrics, and the fault class y can take 13 possible values: either the no fault or a pair <fault-type, fault-location>:

y ∈ {N ormal, CP U Bono , CP U Dime , CP U Sprout , CP U V ellum , DISK Bono , DISK Dime , DISK Sprout , DISK V ellum , N etwork Bono , N etwork Dime , N etwork Sprout , N etwork V ellum } IV. DATA PREPROCESSING
The early detection of performance degradation in metric vectors requires a careful analysis of the available data, to select the right metrics, accommodate nuisances like transient behaviors, outliers, or the effect of exogenous system load. It also requires a rigorous experimental methodology, to avoid biases that could impact detection and classification performances.

A. Necessity of stationary data

Our fault injection approach consists in perturbing one resource on a virtual machine, at an appropriate level of severity, and in collecting metrics over a rather long period of time. We assume the collected data are stationary, in order to collect a large number of hopefully independent signatures of a given perturbation, which then enables a statistical analysis or ML methods. Too severe perturbations will produce severe service degradation, resulting in metrics either drastically increasing or decreasing. For example, the number of connected users may go to zero, with all traffic metrics. Conversely, too weak perturbations will be non-detectable. Fig. 3 illustrates samples of some collected metrics, related to numbers of requests, bytes received, bytes sent (per second), and CPU load. One can observe that several metrics approximately follow a Gaussian distribution, as witnessed by Fig. 4. Nevertheless, their dynamic ranges are extremely different, which requires a re-normalization of data if we want to handle them jointly. Not all metrics have such nice behaviors. First, some of them come in cumulative form (e.g. total number of bytes received), so they need to be handled under their derivative form (see also the discussion about experimental biases). Then, there are numerous outliers, so in our experiments we have discarded data that were beyond 3 times the standard deviation above/below the mean value. Other metrics, like the CPU load measurements (bottom right in Fig. 33), are quantified at the precision of 1%, and exhibit little fluctuations around their mean, hence the Gaussian approximation for them is far from perfect. We have also observed metrics with spiky behaviors (typically, variations of buffer loads) for which the Gaussian approximation would clearly be inappropriate. Despite the almost Gaussian behavior of most metrics we have selected, some of them exhibit periodic pattern. This is quite visible on the Dime and Vellum metrics (bottom left in Fig. 3). This is due to a 30' periodic behavior of the SIPp load generator that plays registration and call scenarios over its database of users. Our data range over 2 hours, hence 4 periods observed in the data. We have chosen to ignore this artificial alternation of high and low activity levels, and considered averaged behaviors over the 2 hours, at the expense of a larger variance estimate on these data. Similarly, we have also noticed a sub-period of 5' in several metrics, still due to the SIPp activity, that we have also chosen to average out.

Finally, in some experiments, some metrics are either unmeasured or almost constant. We have chosen to ignore them when this is the case. For example, too strong perturbations on the CPU of VMs can result in almost saturated metrics slightly below 100%. We consider that this can be easily detected by a direct observation of the metric. We are rather interested in weaker perturbations that would not trigger an alarm, and for which a joint analysis of several metrics would be necessary to detect the fault. As another example, we have also observed that latency perturbations in VM communications could result in a drastic modifications in the statistics of some single metrics such as the size of cached data in memory. Again, this is then easily detectable, so we have chosen to ignore such metrics for the detection of latency perturbations.

B. Data normalization

The collected metrics have extremely different dynamic ranges, both due to the nature of the measured quantities (bits/s, requests/s, CPU load), and due to the current load of the system. We want to study how metrics jointly evolve in case of a silent perturbation, without favoring one or another. We also aim to be insensitive to the "nuisance parameter" represented by the number of users present in the system. Therefore, in order to get comparable dynamics, insensitive to system load, we examine two techniques of normalization of the selected metrics.

The first normalization technique assumes the data follow a Gaussian distribution; we center and normalize them in variance. In doing so, the average activity level is set to zero (so all information lying in the metric averages is ignored), and only the correlation between metrics will be analyzed. This is equivalent to considering the so-called Z-score of data. Formally, let µ and σ 2 be the mean and variance of some collected metric over 2 hours, we replace each value x by (x -µ)/σ.

The second normalization technique is slightly less brutal. It simply consists in resizing the data so that the minimal (resp. maximal) value of each metric is set to 0 (resp. 1). Formally, let x min and x max be the observed minimal and maximal values of x over our 2 hours experiment, we replace each x by (x -x min )/(x max -x min ). By contrast with the previous one, this normalization may preserve information about the mean and variance of the metric.

C. Metric selection

Which metrics to consider, and how many of them should we use for early fault detection? Several criteria come into play. First of all, we select the metrics directly related to the activity level of both the application (ClearWater) and the virtualization layer (OpenStack), such as the bytes received and sent by software components, the numbers of requests, the CPU load of a VM, etc. We keep also, the metrics reflecting the health state of the entire system (latency measurements, numbers of request failures, etc.). As mentioned above, it is important that these metrics exhibit stationary behaviors. Another sanity check is that they react to the injected failures. Fig. 5 illustrates the correlation patterns of the 21 selected metrics (from 35 gathered in the beginning), for two different perturbations. One can observe that the joint behavior of these metrics is a signature of the injected fault, and that this information is preserved by the normalization of data. We have performed experiments on the classification of 12 faults (3 fault types over 4 components), using the Extreme Trees Classifier, fed with z-score data. Fig. 6 sorts selected metrics according to their influence in the classification decision. When some of them (the top 17) are simultaneously used, the classification accuracy is almost perfect.

D. Risks of experimental biases

Some metrics exhibit non-stationary behaviors and their successive samples are not independent (e.g., see Fig. 7, left). We have chosen not to model this memory effect, and assume independence of samples. Our experimental data thus collect samples over a 2 hours period for each injected perturbation. The data for training and testing belong to different samples generated in different period of time. If metrics with memory are used, they can reproduce some kind of timing information, that would sign the moment at which data were collected. This information remains even if data are normalized. We have performed experiments with fake metrics, corresponding to samples of a Brownian motion, centered and re-normalized in variance (see Fig. 7, right). As the number of such fake metrics augments, the fault classification performance increases, and is almost perfect with simply 10 Brownian motion samples. Our interpretation is that these synthetic metrics with memory jointly form a time vector that uniquely identifies the moment at which experimental data were collected. It is therefore crucial to reject non-stationary metrics, that exhibit a memory effect.

V. APPROACHES FOR EARLY FAULT LOCALIZATION AND

IDENTIFICATION

We choose four different approaches. We first handpick Random Forest (RF) because several previous contributions reported a good accuracy in detecting and identifying service degradations. We want to check whether RF still performs well for soft degradations, where one only collects preliminary symptoms. The second selected approach is Extreme Gradient Boost (XGBOOST) as one of the most popular recent classification techniques. It solved many complex problems, and many Kaggle competitions were won using this algorithm. The third one is a classical statistical approach, Max-Likelihood algorithm, assuming metrics follow a Gaussian (multi-valued) distribution. Max-Likelihood exploit the correlation patterns between features/metrics which supposedly form different signatures for our fault classes. It provides the minimal error classifier, if the collected samples are independent and follow a Gaussian law. Finally, the fourth method, K-Nearest Neighbors, it is chosen because it is suitable for our data velocity and was proven to achieve a good accuracy in similar problems. For the implementation, we use Python scikit-learn library for RF, KNN and XGBOOST, and Matlab for Max-Likelihood.

A. First approach: Random Forest

The general idea is to rely on an ensemble of decision models to improve accuracy. RF [START_REF] Breiman | Random Forests[END_REF] is a supervised learning algorithm that generates and merges several decision trees into one forest, which enhance the accuracy of the model. For each decision tree in the forest a random sample of data is chosen and at each split a subset of features are randomly chosen to avoid over-fitting and minimize multicollinearity. We find the best split point and split it to daughter node using a method for best split (Gini index or entropy) until we reach the nodes that are too small to be split called leaves. Then when we get all the trees, we classify using the highest voted class among all the estimators.

For the RF approach, we need to tune the best hyperparameters (The parameters which can be defined by the user before starting training the model), in particular the number of estimators (trees) and the maximum depth for a tree ; because more trees imply more computational costs, and the improvement is minimal after a certain number of trees, so we need to find the optimal number. We compare between two algorithms as shown in Fig. 8 : Grid search algorithm and Random search [START_REF] Bergstra | Random Search for Hyper-Parameter Optimization[END_REF].The first method tries every single combination of hyper-parameters from a range of values and the latter simply tries random combinations of hyper-parameters from a range of values to find an optimal solution for a model through Cross Validation (CV), avoiding over-fitting. We choose K-fold the most popular CV method with k=3 (k: the number of groups to which the data will be split). For the implementation, we set 20 iterations, each one trying a new combination of hyper-parameters: We choose to use the Random search algorithm because it has a better accuracy and a faster convergence. The optimal values obtained are 29 for the maximum depth of a tree and 872 for the number of estimators in the forest. It should be noted that RF preprocessing is not a necessary step, as this algorithm is less sensitive to data scaling then other approaches.

B. Second approach: Extreme Gradient Boost

The Extreme Gradient Boosting (XGBOOST) [START_REF] Chen | XGBoost: A Scalable Tree Boosting System[END_REF] is also a supervised ML algorithm, but instead of training models separately like RF, it trains sequentially, it has a more regularized formalism to avoid over-fitting; The first weak tree based classifier uses all the observations, it computes the residuals (the difference between the predictions and the actual values) and updates weights for incorrectly predicted observations. Then, for the second decision tree the observation with the maximum weights will be selected to construct the model. We will apply the same procedure by modifying weights for wrongly classified samples. So, we will iterate sequentially until constructing the n-th decision. Finally, all of these weak learners are combined to get a strong weighted prediction.

C. Third approach: Max-Likelihood classification

The Max-Likelihood classification is a classical statistical approach with sound mathematical foundations for its decision rule. We assume that all the features are normally distributed and we estimate the probability that a given observation belongs to a specific class; the class y i with the highest computed likelihood is assigned to the observation X. Each sample will be associated with a class (a concatenation between type and localization). We implement Logarithmic Max-Likelihood ( ) : a supervised classification by calculating the following function for each observation vector in the dataset :

Log-likelihood = (X -µ i ) T Σ -1 i (X -µ i ) + log(det(Σ i )) + N i log(2π) where µ i is the mean and Σ i the correlation matrix of random vector X in class i (recall that data are normalized, so the covariance is actually a correlation), and N i the dimension of the data in class i.

The proposed approach was initiated by the visualization of the correlation matrices of each class y i . It is observed as expected that the correlations between features change depending on the classes. We take the example of features dependencies difference between two classes : CPU_Bono, Network_Dime. The blocks of features are highly correlated in the data Network in Dime perturbation around one value and for the CPU Bono the blocks correlation are around 0.5 as depicted in Fig. 5.

D. Fourth approach: K-Nearest Neighbors (KNN)

KNN [START_REF] Cunningham | k-Nearest Neighbour Classifiers[END_REF] is a supervised non-parametric ML algorithm used for pattern recognition and intrusion detection systems; it is based on feature similarity measure. Given N training vectors, it identifies K nearest neighbors for vectors, then using a voting system it finds the class to which a given vector will be associated. We choose to use this approach since our dataset is not so voluminous after the removal of noisy features. One crucial step when using KNN is to choose parameter K, if K is too low, it will bias the results and if it is too high it will increase complexity. So we tuned the hyper-parameter to find the optimal K value using Randomized search and we found that best value is 15 nearest neighbors.

VI. RESULTS AND COMPARISON OF APPROACHES

We show some experimental results to demonstrate the effectiveness of our approaches. We first tried to train models with 70% for train and 30% test, but it seems to be not realistic and not very robust methodology for that reason we choose to train our models on a mixture of datasets from different traffic patterns execution with regular traffic pattern (50k subscribers), pattern with higher ratio of INVITE (85% ratio of Invite/Register) and high traffic pattern (100k subscribers). And then the test was carried out on the dataset obtained from a distinct execution with a regular traffic pattern.

A. Fault detection

We detect here whether a fault has occurred or not by recognising preliminary symptoms; it is a binary classification. As shown in Table I, we compare between the four described approaches using three performance indicators: Precision, Recall and AUC score (Area Under Curve) can be understood as a measure of the probability that the model will classify a random positive example over a random negative example: All approaches have a very good Precision and Recall around 90%, and away from traditional ML algorithms, Max-Likelihood classifier performs also as good as the other approaches. Although, it is important to assess the binary classification using AUC score, since it tests the efficiency of a binary classifier on average across a range of possible decision thresholds. The results obtained with RF, XGBOOST and KNN with an AUC score above 90% that means that the three algorithms are able to distinguish between normal and faulty classes, Max-Likelihood AUC score is 84% less than the top three classifiers have also a good discrimination capacity to distinguish between classes with faults and normal. So it is an easy task for the ML algorithms to recognise faulty patterns and normal behaviour especially if the preprocessing part is done correctly.

B. Identification and localization of faults

For the fault localization and identification task, we will evaluate the classification performance between the described approaches using Precision, Recall and F1-score since it is a harmonic mean of Precision and Recall and it is useful to evaluate if we have imbalanced classes (our samples per class are not even). As illustrated in table II, the two highest performance values belong to RF and XGBOOST with 82% and 81% of Precision and Recall. Then, we have KNN with a Precision, Recall of 73% and a F1-score of 72%, it has a performance which can be enhanced, since KNN is an algorithm that can suffer from a phenomenon called "dimensionality curse": data dimensions can affect badly algorithm performance. Max-Likelihood classifier have the worst performance, that can be explained by the data size. There is a huge gap between results obtained for detection using Max-Likelihood classifier and results for fault identification and localization. It is interpreted by the fact that some fault patterns are quite similar and this can lead to prediction errors. For the four approaches, Precision and Recall are equal, meaning that an equal amount of users has been classified as False Positives and as False Negatives. For the learning time, the RF took 59 second since we are using 872 trees, 24 second for XGBOOST, 3 second for KNN and the longest one was Max-Likelihood with 1 minute and 40 seconds.

We take a closer look to the classification accuracy for each class using confusion matrix.

Fig. 9 depicts the confusion matrix of the RF classifier. Lines represent injected faults, columns stand for detected faults. We first have CPU faults (top left), then Disk faults (center), and Network faults (bottom right), and within each block of 4, locations range over components Bono, Dime, Sprout and Vellum. On the diagnonal, and below percentages, quantities A/B stand for the number of cases correctly recognized over the total number of cases. Off the diagonal, the single number A stands for the number of wrong classification (for the same B, constant on a line).

RF classifies well almost all the classes except the latency in Vellum and Dime; this is explained by the fact that the two perturbations have a close pattern and a similar impact Fig. 9. Confusion matrix for RF on our NFV platform, since Dime and Vellum are two highly correlated VNFs in the platform. The RF is the best classifier for this task since number of trees was tuned to find the optimal value, but with a large computational cost during runtime as a drawback.

XGBOOST and RF has almost the same accuracy for each class and the same misclassified classes, which can be explained by the fact that the two approaches are tree based algorithms.

VII. CONCLUSION AND FUTURE WORK

This work demonstrates that the joint use of performance metrics enables the early detection, identification and location of faults in virtualized networks, before QoS is impacted. One can train classifiers to recognize these fault signatures by injecting gentle perturbations in the network, at levels that do impact too much services and nevertheless enable the learning techniques to grab sufficient information.

We have trained our ML models on a mixture of datasets obtained with different load levels and protocol usage patterns, in order to increase robustness to nuisance parameters. The evaluation was performed on a distinct dataset with a fixed load level. RF and XGBOOST were best to recognize different types of fault injections such as CPU exhaustion, excessive disk I/O, and network latency. They show excellent scores and resist well to different traffic patterns. This suggests that such approaches combining gentle fault injection and learning could be deployed online, in production services.

Despite these early promising results, we need to further investigate the robustness properties and the generalization of the proposed methods. For example, the selection of metrics, the necessary preprocessings (e.g. ouliers removal) and normalization of data, the calibration of injected faults, the resistance to traffic loads or to user profiles are important to get good classification levels, and still need further investigation. We also assumed that all collected samples were independent, while Markov models could possibly better account for memory phenomena in such systems. Nevertheless, the present work underlines that the joint behavior of multiple continuous metrics is already quite informative, as opposed to a more traditional per-metric alarm generation approach.

We plan to extend our work by building another statistical model to express the correlation between VNFs and resources, by exploiting the topological structure of the relationships between the VNF components. We also plan to use this stimulus-based approach on a Docker based platform and test our model.

Fig. 1 .

 1 Fig. 1. ClearWater open source project components are implemented in VMs and are taking full advantage of cloud computing technology.

Fig. 2 .

 2 Fig. 2. Test-bed architecture

Fig. 3 .

 3 Fig. 3. Samples of available metrics.

Fig. 4 .

 4 Fig. 4. Left: probability distribution for measured latencies at Bono and Sprout. Right: normalized probability distributions of bytes received per second, by Bono and by Sprout.

Fig. 5 .

 5 Fig. 5. Correlation matrices of 21 metrics for two injected perturbations: a CPU load on Bono (left), and a latency in communications on Dime (right).

Fig. 6 .

 6 Fig. 6. Gini influence of metrics for the XTC classifier.

Fig. 7 .

 7 Fig. 7. Left: a metric with memory (buffered memory on Dime). Right: a forged fake metric, as a Brownian motion sample.

Fig. 8 .

 8 Fig. 8. Comparison between two hyper-parameter tuning approaches

  F N where TP : True Positive, FP: False Positive, and FN: False Negative.

https://manpages.ubuntu.com/manpages/artful/man1/stress-ng.1.html

https://wiki.debian.org/TrafficControl

https://docs.openstack.org/ocata/fr/install-guide-ubuntu/index.html

https://www.projectclearwater.org/

http://sipp.sourceforge.net/

https://www.ansible.com


Tomas Lagos Jenschke
email: tomas.lagos-jenschke@imt-atlantique.fr

Remous-Aris Koutsiamanis
email: remous-aris.koutsiamanis@imt-atlantique.fr

Georgios Z Papadopoulos
email: georgios.papadopoulos@imt-atlantique.fr

Nicolas Montavont
email: nicolas.montavont@imt-atlantique.fr

ODeSe: On-Demand Selection for Multi-path RPL Networks

Keywords:

The Internet of Things (IoT) has become ubiquitous due to its flexibility, ease-of-use, and reduced cost. As a consequence, the industry is adopting these systems in its transformation into Industry 4.0. However, the strict Quality of Service (QoS) requirements of the industry are not met with the default best-effort provisions of the IoT. Most industrial applications require strict guarantees in terms of end-to-end network reliability and latency. For instance, consecutive packet losses can lead to communication disruptions in supply chain systems. Therefore, adaptations are being made to fulfill these requirements with the IEEE Std 802.15.4-2015 Time slotted Channel Hopping (TSCH) link-layer standard and the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) standard at the Internet Engineering Task Force (IETF). However, even by employing such industrial protocols, it is still difficult to achieve the expected QoS levels. Considering that RPL constructs and maintains a single-path from a source to a destination if there are potential issues on this path (e.g., queue overflow, variable wireless link quality) packets may suffer unexpected delays and even drops. If we consider a multi-path implementation where each node can replicate a packet into several paths, the transmission reliability improves since each packet copy is used to forward the packet information. However, uncontrolled replication can lead to network flooding, resulting in excessive power consumption. In this article, we present On-Demand Selection (ODeSe), a novel multi-path routing algorithm, which improves our previous work, the Common Ancestor (CA) algorithms, by selecting the most suitable upward forwarders. Moreover, we use the Packet Automatic Repeat reQuest, Replication and Elimination, and Overhearing (PAREO) functions in order to improve network reliability and availability. In order to control the number of relay nodes during a transmission, ODeSe forces each node of the same relay level to select the same Preferred Parent (PP) and the same Alternative Parent (AP). Thus, we address the trade-off between the total number of traversed nodes in the network and high reliability. Using the Cooja network simulator running the Contiki OS, we compare ODeSe against single-path RPL and multi-path RPL with different alternative parent selection algorithms. The results demonstrate that ODeSe outperforms single-path RPL in terms of reliability, and multi-path RPL in terms of energy consumption while maintaining a 99.14% packet delivery ratio.

Introduction

The importance of wireless technologies and the use of the pervasive Internet of Things (IoT) has dramatically risen in the last decade. The industry has started adopting these technologies in plants for different purposes, including monitoring and controlling production chains. The IoT is considered as one of the main pillars of what is called the Industry 4.0, the new industrial revolution guided by digitalization. The advantages of the IoT are its easy deployment, low energy consumption and great adaptability to different environments. One remaining issue though lies in wireless technology behavior and the industrial requirements, since IoT devices usually provide best-effort networking while Quality of Service (QoS) is required in industry applications.

The community has published several standards to handle these requirements. At the physical and link layers, the IEEE 802.15.4-2015 [START_REF]IEEE Standard for Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF] standard is based on Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA) designed for Low Power and Lossy Network (LLN) devices. As a part of IEEE 802.15.4-2015, the Time slotted Channel Hopping (TSCH) protocol allocates specific slots for transmission and reception per device while using frequency hopping for multi-path fading avoidance. At the network layer, a commonly used protocol for the IoT systems is the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF], standardized by the Internet Engineering Task Force (IETF). RPL configures one or more routes to transmit a message to a sink through the construction of a Destination Oriented Directed Acyclic Graph (DODAG). These protocols, however, do not provide a high level of quality of service since they depend on the variability of the link quality and the availability of the selected forwarders.

Multi-path routing protocols have been popular over the past years for different reasons, including to enhance reliability. They enable multiple paths using different nodes from a source to a destination to achieve different purposes, such as mitigating traffic load or improving transmission reliability. Depending on the use case, these multiple paths can be used alternatively or simultaneously.

In our previous work [START_REF] Papadopoulos | Leapfrog Collaboration: Toward Determinism and Predictability in Industrial-IoT applications[END_REF], we proposed the use of a braided pattern by simultaneously sending multiple copies of a packet to both a primary and a secondary route. This pattern allows receivers to overhear a transmission intended for another forwarder in order to increase the probability of receiving the transmitted packet. Here the problem lies in the selection of these Alternative Parents (APs) since this algorithm does not maintain a stable braided pattern [START_REF] Minet | Increasing reliability of a TSCH network for the industry 4.0[END_REF], producing unnecessary routing changes within the DODAG.

In this work, we propose the On-Demand Selection (ODeSe) algorithm, which aims to perform multi-path parent selection based on the dynamic conditions at the packet-forwarding time. The aim is to keep a more stable braided pattern in the routing topology and prevent the forwarded packet from spreading to a larger part of the topology. This work also implements and uses the Packet Automatic Repeat reQuest, Replication and Elimination, and Overhearing (PAREO) [START_REF] Koutsiamanis | Meet the PAREO Functions: Towards Reliable and Available Wireless Networks[END_REF] functions, to improve reliability and increase energy efficiency. Finally, in this work we use a centralized TSCH schedule for simplicity but the proposed algorithms are more general since RPL is agnostic of the Medium Access Control (MAC) layer.

The document is organized as follows: in Section 2 the TSCH and RPL protocols are explained. In Section 3 we introduce multi-path routing and the PAREO functions. Next, we provide a detailed description of the method used for implementing the braided routing pattern in Section 4. In Section 5 we present the proposed algorithms for parent selection. In Section 6 we describe the simulation setup used for our experimental evaluation and in Section 7 we analyze and present the experimental results. After having presented our contributions, we present other related works and how they compare to this work in Section 8. Finally, in Section 9 we conclude our work. [START_REF] Watteyne | [END_REF] is a wireless MAC protocol that provides predictable medium access and mitigates potential multi-path fading. TSCH allows nodes in the network to coordinate through a communication scheduler which uses TDMA for the time dimension and FDMA for the frequency dimension.

Background

More specifically, time is divided into timeslots and the available frequency range into multiple non-overlapping physical radio channels. We call cell a (timeslot, channel offset) pair, which is the representation of a communication opportunity at a specific point in time and frequency. Frequency Hopping Spread Spectrum (FHSS) is employed to mitigate multi-path fading and for this reason the cells in the schedule do not use the physical radio channel values directly but a channel offset, which is mapped at each timeslot to a different but deterministically computed physical channel. Finally, a set of timeslots are organized into a slotframe of length equal to the repetition period (in timeslots). IEEE Std 802.15.4-2015 describes how TSCH should operate, but the definition of the schedule is left to specific implementations based on the needs of the application domain.

Cell types

As shown in Figure 1, it is possible to classify cells into two types.

• Shared cells: these are the contention-based cells, i.e., Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), and they are used for control plane traffic.

• Dedicated cells: these are the contention-free cells.

Only a specific pair of nodes can communicate concurrently so collisions are avoided within a given TSCH network. These cells are commonly used for application traffic.

Channel offset mapping

To support FHSS, a channel offset is mapped to a physical channel using the following Equation (1):

= [(ASN + ChannelOffset) mod CH ] ( 1
)
where CH is the number of existing physical channels, Absolute Slot Number (ASN) is the timeslot counter for the lifetime of the network, and is a lookup table that maps the results from the equation to the radio channel .

Scheduling

Regarding the scheduling, we use the scheme provided by TSCH to define the general structure and operation of the schedule. However, cell assignment, creation, and distribution of the schedule among the nodes are left to the implementation. These latter processes [START_REF] Rugamba | Implementation of a Centralized Scheduling Algorithm for IEEE 802.15.4e TSCH[END_REF] can be classified into two broad categories:

• Centralized scheduling: a schedule is computed in a single central entity, taking into account the needs of all the nodes of the network, and is distributed to the nodes afterwards.

• Decentralized scheduling: nodes negotiate and create their schedule with the other nodes in their neighborhood. Thus, different parts of the whole network use different local schedules.

In this work, we assume that there is previous knowledge of the network topology. Therefore, we use a centralized scheduling method and distribute it to the nodes. We should note that this schedule has been created manually, but it is possible to generate one automatically using a controller, as can be seen in [START_REF] Koutsiamanis | A Centralized Controller for Reliable and Available Wireless Schedules in Industrial Networks[END_REF].

RPL

RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF] is a proactive distance-vector routing protocol for LLNs which maintains connectivity while minimizing energy consumption by limiting network traffic overhead. The nodes running the RPL routing protocol construct a DODAG, and the traffic is routed from these nodes to a border router, called the DODAG Root, that provides external connectivity. To achieve this, RPL initiates a routing instance to incorporate several nodes into one or many DODAGs. Then, depending on the instance's requirements, the nodes choose the best route for forwarding packets upwards (leaf to root). RPL supports two modes for performing downwards (root to leaves) routing: • Storing mode: where intermediate nodes maintain state representing the routing information towards all their ancestors (direct children, children of children, etc.). This results in additional memory requirements for the nodes maintaining this information but higher network performance, especially for inter-DODAG traffic.

• Non-storing mode: where only the DODAG root maintains state representing the routing information towards the whole DODAG. This results in high memory requirements only on the root, but adds network overhead due to the use of source routing and less efficient intra-DODAG routing because all the traffic needs to go through the root.

RPL uses three types of control packets to build and maintain the DODAG.

• DODAG Information Object (DIO): Contains all the necessary information regarding a RPL instance, allowing a receiving node to connect. Given its nature, it is commonly transmitted as multicast and aims to grant the current DODAG information to a node so that it can make a parent selection.

• Destination Advertisement Object (DAO): Propagates reverse routing information and is transmitted every time a new preferred parent is selected. It is sent as unicast and delivered to the new parent node or the DODAG root, depending on the established RPL storing method (storing mode / non-storing mode).

• DODAG Informational Solicitation (DIS): Interrogates other nodes about the status of the network, soliciting DIO messages as a response. To avoid loops in the DODAG, RPL performs distancevector routing based on a rank hierarchy given by an Objective Function (OF). Out of a set of candidate parent nodes, the node with the lowest rank value is selected as the Preferred Parent (PP) and used for upwards routing. To calculate a rank, the OF can use different metrics [START_REF] Vasseur | Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks[END_REF], usually one of the two following:

• Hop Counting (HC): number of hops a packet must perform to reach its destination.

• Expected Transmission Count (ETX): Statistics aggregation that reveals a point-to-point link's quality. This metric reveals a route with the highest success probability.

Multi-path with the PAREO functions

The default implementation of RPL forwards packets from one node to another via a single-path. If one of the transmissions fails, the only option is to retry the transmission. Furthermore, transmission failure may occur not only because of low link quality but also when one node in the path is unreachable. With the default single-path RPL, such node can be routed around, given time, with a local or global DODAG repair process [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF]. However, in the time taken to detect this problem and repair the DODAG, packets will be delayed, and if the queues fill up, lost.

Multi-path routing addresses both cases thanks to the functions of PAREO [START_REF] Koutsiamanis | Meet the PAREO Functions: Towards Reliable and Available Wireless Networks[END_REF], which are used to improve network reliability and energy efficiency. Additionally, they can work almost independently from each other. The individual functions that make up PAREO are described in the next sections.

Automatic Repeat reQuest (ARQ)

This function attempts to detect failed packet transmissions and performs a retransmission when that happens. In order for ARQ to function, some mechanism for detecting failed transmissions is needed. In this work we use the support provided by the MAC layer, TSCH. In TSCH, each unicast transmission is by default configured to require an acknowledgement, thus the lack of its reception can be interpreted as a failed transmission.

Using ARQ, given a link with a one-shot Packet Delivery Ratio (PDR) of and up to ARQ transmission attempts, the PDR with ARQ is 1 -(1 -) .

The disadvantage is that each attempt requires an additional cell, entailing an increase in delay, jitter, and energy consumption.

Packet Replication and Elimination (PRE)

Multi-path assumes using several routes to forward packet copies, i.e. Replication. As shown in [START_REF] Papadopoulos | Exploiting Packet Replication and Elimination in Complex Tracks in LLNs[END_REF], this increases the number of opportunities to successfully deliver the data packet to the destination. The primary parent used to forward data is called the PP while the rest of the used parents are the APs. In this work, all the multi-path algorithms use a single AP (i.e., two forwarders).

Additionally, it is possible that via different paths a node receives multiple copies of the same packet. If the node treats the copies as independent packets and also replicates each copy independently, then flooding can occur. To control this, PRE discards duplicated packets, i.e., Elimination. This is done by tagging each sent packet with a unique identifier at the source and keeping a recently seen identifier list on each node. If a received packet's unique identifier is in the list on a forwarding node, it is not forwarded but dropped.

Overhearing

In the context of using multiple parents, a device can also take advantage of the broadcast nature of the wireless medium and listen for transmissions intended for nodes different than itself. Indeed, by employing Overhearing [START_REF] Huh | Reliable data transfer using overhearing for implicit ACK[END_REF], packet replication is performed more efficiently. To do so, we configure the nodes with an overhearing reception cell in their schedule. This allows keeping the nodes in listening mode when one of their neighbors is scheduled to receive a packet transmission. Note that the overhearing nodes do not send an acknowledgement when receiving a data packet. Only the unicast target destination node acknowledges the transmitter to avoid acknowledgment (ACK) collisions. The overhearing function is performed for both PP and AP, i.e., when the transmission is intended for the PP, the AP overhears, and when the transmission is intended for the AP, then the PP overhears.

Common Ancestor (CA) Algorithms

In this section, we present parent selection algorithms for multi-path routing based on a braided pattern with two routing paths. In the main path, nodes forward packets via the PP while in the alternative path nodes use another node called the AP. The way the AP nodes are selected greatly impacts the number of nodes that will be part of the forwarding path, and thus the energy consumption (the more the nodes involved, the higher the energy consumption). So it is important to define rules that allow constraining a transmission within a restricted number of nodes along a narrow path in the network. The CA approach [START_REF] Jenschke | Alternative Parent Selection for Multi-Path RPL Networks[END_REF] selects an AP if there is at least one potential parent in common between the parent sets of the PP and the AP. The objective behind this principle is to select an AP that is related to the PP in order to avoid (or reduce) the potential flooding and concentrate the transmission efforts towards a single direction. However, employing strict rules to select an AP may also reduce the probability of finding one, thus also impacting reliability. Given this trade-off between reliability and power consumption, three algorithms were defined, which vary in their flexibility when choosing an AP.

Overview

To be able to perform both a theoretical and an experimental analysis of the CA algorithm, we established a regular grid-like topology of × , as shown in Figure 3, where is the number of nodes per layer, the number of layers between the source node (node S) and the DODAG root (node R), and L( ) is the set of nodes in the ℎ layer. More specifically, L(0) = { }, L( + 1) = { }, and for the rest of the layers ∈ {1, 2, ⋯ , }, |L( )| = . Each node in each layer will have as its Parent Set (PS) the nodes located in the lower layer, i.e., > 0 and ∀ ∈ L( ).

( ) = L( -1). Finally, the nodes report a subset of their parent set in the PS extension of the Node State and Attribute (NSA) object in the Metric Container (MC) of DIO messages (referred to as the parent set from here on). This extension contains a fixed number of addresses , with 1 ≤ ≤ . The probability of being able to find an AP depends on the AP selection algorithm used and the values of and . We will now investigate this probability since it significantly impacts the ability to implement braided multi-path routing.

Probability of obtaining an AP

The probability of obtaining an AP is given in Equation [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF].

(∃ ) = 1 -(1 -(∃ )) -1 (2)
where (∃ ) is the probability of having at least one AP and (∃ ) is the probability of having at least one CA. Pa re nt se t si ze 1 2 3 4 5 6 7 8 9 Different (∃ ) are produced depending on the selection algorithm, and as a result also different (∃ ).

CA Algorithms

Three different AP selection algorithms are presented in [START_REF] Jenschke | Alternative Parent Selection for Multi-Path RPL Networks[END_REF], with different trade-offs between the probability of selecting an AP and the level of flooding mitigation. In Figure 5, the probability of selecting an AP is shown for each of these algorithms, depending on the values of and .

Strict CA

Strict CA selects a candidate parent node as an AP if the candidate node's PP is the same as the PP of the PP (the preferred grandparent) of the current node , i.e., ( ( )) = ( ). The probability of finding a CA is given in Equation [START_REF] Papadopoulos | Leapfrog Collaboration: Toward Determinism and Predictability in Industrial-IoT applications[END_REF].

(∃ ) = 1 (3)
Given this, the probability of finding an AP is calculated in Equation ( 4).

(∃ ) = 1 - -1 -1 (4)
It is represented in Figure 4a with nodes A, D, E, and S. Since D and E have the same PP, which is A, then E is a candidate node to be selected as AP. Given the above and since E belongs to the PS of S, then E is selected as AP of S.

Medium CA

Medium CA selects a candidate parent node as an AP if the candidate node's PS contains the PP of the PP (the preferred grandparent) of the current node , i.e., ( ( )) ∈ ( ). The probability of finding a CA is given by Equation [START_REF] Koutsiamanis | Meet the PAREO Functions: Towards Reliable and Available Wireless Networks[END_REF].

(∃ ) = (5)
Using Equation (2), we then obtain the probability to get an AP, shown in Equation [START_REF] Watteyne | [END_REF].

(∃ ) = 1 - - -1 (6)
The representation of its selection can be found in Fig- ure 4b , where none of the nodes have a common PP except for those connecting to the root. However, since E has A, B, and C within its PS and D has A as PP, E is selected as AP.

Soft CA

Soft CA selects a candidate parent node as an AP if the candidate node's PS has any common node with the PS of the PP (the preferred grandparent set) of the current node , i.e., ( ( )) ∩ ( ) ≠ ∅. In Equation [START_REF] Rugamba | Implementation of a Centralized Scheduling Algorithm for IEEE 802.15.4e TSCH[END_REF] the probability (∃ ) of obtaining a CA depends on the probability of having a common node in the two parent sets via the PP and via the candidate AP.

(∄ ) = ⋅ - ⋅ = - ⇒ (∃ ) = 1 - - (7)
Finally, using Equation ( 2), the probability of finding an AP is shown in Equation ( 8).

(∃ ) = 1 - - -1 (8)
Its selection methodology is represented in Figure 4c, where E is selected as AP of S since its PP D has B as a common node with E. In case that multiple nodes are possible candidates to be selected as AP, then the one with the lowest RANK will be selected.

Common Ancestor Trade-offs

As it can be seen in Figure 4, in each algorithm, the PS of the PP of a node directly affects which nodes are eligible as APs. Even with Soft CA, the least restrictive selection algorithm, at least one node from the PS of the candidate AP has to belong to the PS of the PP of the node.

Indeed, if we analyze the three CA algorithms, the Strict CA selection performance, in terms of reliability, should be lower than the other two CA algorithms, since the probability of obtaining an AP is subject to share a common PP. As the probability is lower, fewer nodes are selected, and thus lower reliability is achieved, but less energy consumption as well.

A Soft CA selection, on the other hand, improves reliability since its AP selection works by matching any node between the PS of the PP with the PS of a possible AP. Therefore, the number of nodes employed for a transmission increases (and can easily lead to flooding), which in turn leads to higher energy consumption.

Using the notation defined in Section 4.1, let us consider a 3-layer topology between the source and the sink, where each layer is composed of 3 nodes, i.e., = 3 and = 3. If we make a transmission by making a Strict CA selection, we expect to get at most 6 relay nodes, i.e., the PP and AP in each layer. However, as seen in Figure 6, we can observe more selected forwarders since an AP does not necessarily have the same AP as the PP.

The Strict CA algorithm considers a node as a possible AP if both this node and the PP share the same PP. It is clearly possible that several nodes may fulfill this criteria, so another criterion might be used to select the AP, such as the candidate with the best link quality. However the choice is made, the selected node may select a different AP than the PP's AP, which will break the braided pattern and extend the number of nodes selected in each layer.

Figure 6 demonstrates this behavior where it can be observed that all the selected parents belong to the algorithm condition, but at the same time, the selection is dispersed throughout the DODAG. It should be mentioned that each node does not necessarily have the same knowledge of its neighbors since a desynchronization may occur, e.g., the loss of a DIO packet. Also, since the parent selection depends on the parent's rank, there is a possibility of not obtaining an AP. Therefore, the packet will replicate uncontrollably, increasing the network overhead.

Implementation Aspects

The CA algorithms are implemented as custom RPL OFs, which extend The Minimum Rank with Hysteresis Objective Function (MRHOF) [START_REF] Gnawali | The Minimum Rank with Hysteresis Objective Function[END_REF]. The same behavior as MRHOF is used as far as rank calculation and PP selection are concerned, but additional filtering of the candidate parents in a node's PS is performed for the AP.

As we show in [START_REF] Koutsiamanis | RPL DAG Metric Container Node State and Attribute object type extension[END_REF], we have added the information required for this filtering, called the , within DIO control packets. More specifically, the is an additional field in the NSA object, which in turn is nested in the MC option of DIO control packets, as shown in Figure 2. The field is stored as a list of IPv6 addresses, one for each potential parent in the PS, ordered by rank from most to least preferred (lowest to highest rank). Since IPv6 addresses require 16 bytes of storage, there is a limit to how many can be efficiently stored (thus ≠ ) and compression is generally required to send more than 2 addresses within the 127 byte frame limit of IEEE 802.15.4-2015. In our implementation, we only send the lower-order byte of this IPv6 address, following a compression method similar to the one used for the Source Routing Header (SRH) in the 6LoWPAN Routing Header (6LoRH) [START_REF] Thubert | IPv6 over Low-Power Wireless Personal Area Network (6LoWPAN) Routing Header[END_REF].

ODeSe

While the Strict, Medium, and Soft CA algorithms perform well, the highest transmission reliability is achieved with Soft CA but at the cost of higher energy consumption due to higher flooding. In this section, we present ODeSe that aims to maintain the same level of network reliability while maintaining minimal transmission propagation between its parts. The main difference between the CA algorithms and the ODeSe is that in ODeSe each node decides not only its own forwarding parents (PP and AP) but also the PP and AP to be used in the next hop towards the destination. In other words, each node has a two-hop forwarding control. As it is shown in the performance evaluation, this results in tighter control of flooding that can be translated into lower energy consumption.

Given the above, ODeSe maintains as a selection policy the assignment of the same relay parents to the nodes that are at the same distance. However, ODeSe requires that these nodes point to the same PP. Otherwise, it loses the multi-path route direction.

Let us consider three different use cases. The first, illustrated in Figure 7a , represents the ideal ODeSe case. Here we can see that both E and F point to B as PP, allowing them Output: Returns the parent set used for the next data packet forwarding (PP, AP). where PP( ) and AP( ) correspondingly return the PP and AP of node .

to choose C as AP. When this situation does not occur, ODeSe has mechanisms that manipulate parent sets to adapt them to its requirements without affecting RPL. This is shown in Figure 7b, where an auxiliary link is generated to point to a suitable parent. More precisely, since E has A as PP, and F has B as PP, E must temporarily change its PP to B since it satisfies the requirements of the algorithm. This is because B is the PP of F, and F is the PP of S.

Finally, if a given scenario cannot be adapted to ODeSe, it will choose to make a selection using Soft CA (see Figure 7c).

Selection method

For every hop, a node selects its PP and AP using the Strict CA algorithm. Additionally, in the forwarded replicas, the node stores the addresses of the PP and the AP of its PP, i.e., HbH = PP(PP( )), HbH = AP(PP( )). More specifically, these two addresses are stored within the Hopby-Hop option header of the data packet, to be delivered to the next-hop node, see Figure 8.

As is shown in Algorithm 1, once received at the next hop node(s) ′ ∈ { ( ), ( )} (i.e., both the PP and AP of ), the following checks are made. The next-hop node ′ checks if the transported PP address HbH is indeed a valid PP for it, and if yes, it then uses HbH as the new PP for this specific packet, see Figure 7a and Figure 7b. The original PP is restored after finishing the forwarding operation for this packet. The validity check is required because information at node might be "stale" due to not receiving up-to-date parent set information from ′ via a DIO packet. If the HbH is not a valid PP, then the default PP of node ′ is used, see Figure 7c.

For the AP, node ′ checks if the stored within the Hopby-Hop option field HbH node is also a valid AP using Strict CA. If it is, then ′ uses HbH as the AP (see Figure 7a). If it is not, then ′ will try to obtain a new AP using first Strict CA, and if that fails, falls back to Medium CA and then Soft CA.

When ′ has selected the AP and PP for the next hop, it does what node at the previous hop did before it. It stores and replaces the addresses of the PP and the AP of its PP, i.e., HbH = PP(PP( ′ )), HbH = AP(PP( ′ )) in the forwarded replicas. Therefore, the entire process repeats until the data packet is delivered to the target node.

Multi-path algorithms behavior

To evaluate ODeSe against the three CA selection algorithms, we used the Monte Carlo method [START_REF] Hastings | Monte carlo sampling methods using markov chains and their applications[END_REF] using the grid topology explained in Section 4.1. This methodology consisted in modeling a DODAG construction using multipath, where each node has a PP and a possible AP. The goal is to evaluate the average number of nodes used per hop "layer" during transmission between the source and the root node. To do so, we use different scenarios with hop distances L between 0 and 50 hops, and node sets per layer of size N between 0 and 50 nodes. The process of selecting a PP consists of choosing a random node from the upper routing layer , based on the "distance" of a given node. Here, each node selected as a PP is provided with a probabilistic weight to increase the possibility of being selected again by other nodes.

Regarding the AP selection process, the principles of the CA and ODeSe algorithms are employed. Here, the selection method takes into consideration only a random half set of nodes contained in the upper hop layer , based on the distance of a given node.

The results of this model are shown in Figure 9, where the x-axis indicates the distance between the source and the root, the z-axis indicates the number of present nodes per hop, and the y-axis indicates the average number of relay nodes per stage × .

Figure 9a shows that the Strict CA algorithm increases the average number of relay nodes per layer until it normalizes in approximately three nodes.

Figure 9b and Figure 9c, on the other hand, have a linear upward increase. Due to the topology used, the differentiation between these two algorithms is quite small, being Medium CA a bit smaller than Soft CA in terms of the average number of relay nodes. Finally, ODeSe (Figure 9d), shows a horizontal linear average that does not exceed two nodes per layer yet with values close to those.

Simulation Setup

Simulation Parameters and Topology

We have employed the Contiki 3.01 operating system [START_REF] Dunkels | Contiki -a lightweight and flexible operating system for tiny networked sensors[END_REF] and the COOJA simulator to implement the CA and ODeSe algorithms with a directed graph radio medium. Contiki comes with the default RPL protocol implemented, which is what is used for evaluating the single-path routing.

The network topology used for the evaluation is the one shown in Figure 3 with = 5 and = 6. The radio links in this topology come with 50% link quality on average, and every node (except the root and its direct children) has 6 potential parents to forward data. This link quality value has been chosen following the Dust Networks2 definition of a healthy network where each device should have at least a 50% link quality with its neighbors and at least 3 potential parents. Therefore, we evaluate three different cases with increasing average link quality and in all cases using a uniform random distribution for selecting the link quality values. Furthermore, the size of the has been set to 3 to correspond to a more realistic case where finding a potential alternative parent even by employing Soft CA is not guaranteed.

At the MAC layer, we use TSCH with a timeslot length of 10 and a total slotframe size of 297 timeslots, i.e., 2970 . The purpose of this is to provide the appropriate number of slots to locate 1 Retransmission (RTX) for each individual transmission and to locate all overhearing events as well.

A centralized TSCH scheduling was used as described in Section 2.1.3, where the slotframe takes its form based on Figure 1. For application traffic, in each simulation we send 250 UDP packets from a unique source node S to the root node R, with no fragmentation. The packets are sent once every 15 seconds so that at any one point in time there is only one packet being forwarded through the network.

For the routing algorithms, we have evaluated ODeSe against the three CA multi-path variants as well as against the default RPL single-path algorithm with different RTX count limits.

More specifically, the routing algorithms evaluated are: For each of the above routing algorithms, we executed 20 simulation repetitions with 20 different Pseudo-Random Number Generator (PRNG) seeds, to increase the statistical reliability of our results. In total, therefore, 5000 data packets have been sent for each routing algorithm, and a total of 480 simulations have been executed.

In Table 1, the detailed simulation parameters are listed.

IEEE Std 802.15.4-2015 TSCH Schedule

This work evaluates routing algorithms within RPL, which is MAC agnostic. For the MAC layer, we have chosen to use TSCH for its scheduled nature in order to reliably evaluate energy consumption, delay, and jitter.

For UDP data transmissions, the experimental scenario that we investigate cannot have transmission collisions. Thus, only 1 TSCH channel is used for simplicity. Furthermore, we wanted to allow the routing protocols to select at each node any of the nodes in the higher layer as a PP or an AP. Therefore, we created a schedule which for each node has transmission cells to all the possible parents. Additionally, for each possible parent, there are two available cells to support 1 RTX within the same slotframe. Finally, overhearing is not supported in TSCH, so it has been implemented as an extension in Contiki. When any node is transmitting to one of the parents, overhearing cells are placed in the rest of the potential parents. They take the form of shared receive cells (i.e., listening for packets from any source) with the normal MAC filtering disabled (i.e., unicast packets received are not checked if the receiver is the intended destination). An example showing a simplified version of the schedule is shown in Figure 1.

Performance evaluation 7.1. Packet Delivery Ratio (PDR)

During single-path transmission, the probability of success will depend on the link quality and the number of retransmissions per packet lost. As already mentioned in this investigation, only four attempts (SP-3RTX) are required to transmit a single-hop transmission with PDR Single Hop = 93.75% using a 50% link quality on average (i.e., as in the U(40%, 60%) case). Since each hop transmission is independent, the PDR between the source to the sink is given by the multiplication of the probability of each hop, i.e., PDR = PDR Single Hop . Assuming that the total number of hops is six, then PDR = 68.82% (U(40%, 60%), SP-3RTX) as shown in the approximate value of Figure 10a. Multi-path, on the contrary, uses two parents per hop transmission. The probability that both receive the packet with also four opportunities is 87.89%. Therefore, if two nodes transmit to the same parent (CA and ODeSe), the probability of a hop success is 99.60%, since eight attempts are used (four attempts per child). Consequently, reliability improves. In evaluating different link quality ranges, it can be seen in Figure 10a that as the average link quality increases ( = {50%, 60%, 70%}) also the PDR increases for all algorithms, with ODeSe achieving a PDR between 99.1% and 99.96%. In all cases ODeSe outperforms SP-RTX7 and is placed consistently between Medium CA-RTX1 and Soft CA-RTX1.

Delay

Due to the employed centralized scheduling, the slotframe size of the schedule severely impacts delay performance. This requires to obtain all possible transmission cases between the source and the DODAG root. Considering the topology, see Figure 3 with = 5 and = 6, the total number of nodes between the source and the sink is 30. If we consider that each node within the topology has 6 possible parents, excluding the DODAG root and its direct children, then the total number of upward links is 156. More specifically, if T is the total number of links Finally, if we consider that there is one retransmission per slotframe (i.e., two transmissions) and that each timeslot lasts 10 , then the maximum delay per sloframe is 3120 , i.e., if we consider MD as maximum delay per sloframe, then MD = TL × 2 × 10 .

Figure 10b shows this analysis, with single-path algorithms which perform more than one retransmission (RTX > 1) affected since they require more slotframes to transmit. In contrast, all the multi-path algorithms, i.e., ODeSe and Strict, Medium, and Soft CA, only use one slotframe per end-to-end transmission.

Energy Consumption & Traversed Nodes

The simulator used, COOJA, can provide energy consumption information in terms of duty cycle for each radio state and for each node. We have used that duty cycle information to extrapolate the average power consumption per node. To do so, we used the radio power consumption values of the Zolertia Z1 mote with the CC2420 radio transceiver module. The values taken from its specification sheet ( = 52.2 @3 , = 56.4 @3 ) are used as factors for each radio state's duty cycle.

As it can be observed from Figure 10c, single-path comes with better performance than the multi-path algorithms, with single-path reducing the energy consumption as the links become more reliable and as a result fewer retransmissions being used. The multi-path algorithms in general do not rely as much on retransmissions, and therefore have less room for energy consumption improvement due to this factor. This is mainly due to the number of nodes used to forward a single data packet and due to the overhearing operation that requires an extra timeslot. Among the multi-path algorithms, Soft CA comes with the highest energy consumption due it's production of flooding, while ODeSe consumes the least energy, since it concentrates its routes without dispersing them over the DODAG, see Figure 10d.

Note that the energy consumption calculation comprises the cost sending both data and control packets.

Number of Copies per Single Packet

The total number of copies per data packet consists of the number of times a data packet was forwarded at the relay nodes or at the source node. As we have seen in Section 4.3, CA algorithms do not regulate the selected APs if they can satisfy the selection policies of each algorithm. However, since ODeSe aims for all nodes of the same hop distance to forward their links to the same PP and AP, this algorithm is expected to have a restricted number of relay nodes, with 2 parents per node, as well as a limited number of copies of a packet.

As can be seen in Figure 10e, the total number of copies per original data packet in ODeSe decreases by 19.794% compared to the average of CA algorithms, demonstrating that ODeSe's selection policy minimizes the traffic load in multi-path routing.

Discussion

As can be seen in the results of Figure 10, in general, the use of multiple routes increases the reliability of transmission with low delay but also consumes a greater amount of energy, since a greater number of nodes are used to send a packet. On the other hand, the concentration of the alternative paths closer to the main path is necessary for higher energy efficiency.

To demonstrate this behavior, we made several evaluations using the Pareto principle. These graphs illustrate the contribution of each algorithm in terms of nodes used and power spent per transmission.

Figure 11a shows that ODeSe uses a lower number of copies to achieve a PDR comparable to other algorithms, reaching values close to 100%.

Figure 11b, on the other hand, shows that additionally, ODeSe consumes less energy than the CA algorithms.

In both cases, comparing the performance of ODeSe against the other CA algorithms, the CA algorithms use more nodes per transmission and, more energy. Additionally, not all CA algorithms have the same transmission reliability, e.g., Strict CA and Medium CA have worse performance than ODeSe. The highlighted Pareto frontier can help in choosing an appropriate algorithm depending on the required levels of power consumption and reliability.

Related work

The authors in [START_REF] Minet | Increasing reliability of a TSCH network for the industry 4.0[END_REF] compared three types of multi-path algorithms that guarantee a network reliability improvement. First, they defined a Disjoint pattern, which aims to propagate different alternative routes isolated from each other, that is, without a common node between them. The routes are generated from the source node and merged at the sink. Then, they established a triangular pattern, which allows the nodes of the main path to have APs based on a common ancestor. This pattern does not allow alternate nodes to select an AP. Finally, they established a braided pattern, whose goal is to select an AP if there is a common ancestor. Unlike the triangular pattern, this pattern allows the alternative nodes to also select an AP. The authors specify that algorithms with common ancestors improve the reliability of the network at the cost of overhead since there are more routes where the packets can go. The existing problem with the braided pattern is that it can spread across the topology since several common ancestors can exist, therefore, a controlled braided pattern is required.

In [START_REF] Mozaffari | Multipath aware scheduling for high reliability and fault tolerance in low power industrial networks[END_REF], the authors propose the use of multiple routes by selecting an AP using the braided pattern. This proposal aims to use the AP if the PP cannot be reached. Furthermore, they propose the use of a centralized TSCH scheduler that is constructed in such a way that the nodes can perform an end-to-end transmission from the source to the sink in a single slotframe. To take advantage of the isolation that exists between the PP and AP nodes, the authors propose to assign the RX of the nodes of the same layer in a shared cell and the TX of the nodes that will transmit them in dedicated cells. In this way, if there is a common receiver, the transmission from a PP or an AP will use the same timeslot. What is not taken into account is the existence of desynchronization in the reception of the packet. If we consider the transmission of a received data packet to be successful, an ACK is expected to verify its delivery. Since these packets can get lost, this can result in the AP being used for transmitting as well, thus generating collisions.

The authors in [START_REF] Lodhi | Multiple path RPL for low power lossy networks[END_REF], [START_REF] Iova | Using multiparent routing in RPL to increase the stability and the lifetime of the network[END_REF] and [START_REF] Le | RPL-based multipath Routing Protocols for Internet of Things on Wireless Sensor Networks[END_REF] propose the use of multiple routes to reduce upstream traffic congestion in an RPL network. Lodhi et al. [START_REF] Lodhi | Multiple path RPL for low power lossy networks[END_REF] propose the use of the M-RPL extension which has the purpose of detecting the traffic of the forwarding nodes by using the PDR based on a series of expected packets. As soon as a node's PDR exceeds the congestion threshold, it alerts its children to select an alternate parent and thus distribute traffic over two transmission routes instead of one (PP and AP). Iova et al. [START_REF] Iova | Using multiparent routing in RPL to increase the stability and the lifetime of the network[END_REF], on the other hand, defined an Expected Lifetime metric which represents the amount of traffic that the nodes is handling. Depending on the values provided by this metric, the nodes balance the amount of traffic to their neighbors so that each node in the network has similar traffic. Le et al. [START_REF] Le | RPL-based multipath Routing Protocols for Internet of Things on Wireless Sensor Networks[END_REF] propose three types of algorithms to select an AP in RPL: Energy Load Balancing (ELB), Fast Local Repair (FLR), and ELB and FLR together. ELB has an OF that uses hop-counting and residual energy metrics to select nodes with the highest energy levels. In this way, the neighbor with the lowest rank will be selected as PP, while the set of APs will be considered as a backup. FLR, on the other hand, attempts to reduce the number of local repairs. This is achieved by searching for neighbors with the same rank as the rank of the PP, with the objective of using them as PP if the actual PP requires a local repair. Finally, the combination of the two algorithms results in a reduction in overhead and delay while a wellbalanced network is maintained. In all three of these works, although the authors balance traffic to multiple parents, this does not guarantee that the network is reliable. This is due to the fact that the transmission opportunities are scattered throughout the topology, which can cause disjoint paths that in turn depend on re-transmissions due to their isolation.

LeapFrog Collaboration (LFC) is a RPL-based multipath routing algorithm that maintains reliability by taking advantage of the properties of the wireless environment, and packet replication and elimination functions. It uses a braided pattern based on common ancestor strategy, where the preferred and the alternative parents of a node should have at least one common parent. Furthermore, to offer more receiving opportunities, LFC uses the overhearing function to keep the alternative node in reception mode in order to capture the transmitted packets when a node transmits to its preferred parent. These methods result in an algorithm which maintains high reliability at the expense of energy consumption [START_REF] Koutsiamanis | From Best-Effort to Deterministic Packet Delivery for Wireless Industrial IoT Networks[END_REF] [START_REF] Papadopoulos | Leapfrog Collaboration: Toward Determinism and Predictability in Industrial-IoT applications[END_REF]. In contrast, the CA algorithms and ODeSe have been designed with the intent of more flexible parent selection to control flooding. As a result, Strict CA and ODeSe are more energy efficient.

Conclusion

In this work, we addressed the trade-off between reliability and energy consumption in the industrial IoT context, and more specifically when using IEEE Std 802.15.4-2015 TSCH as the MAC protocol and RPL as the routing protocol. Previous works on multi-path with CA achieve high reliability using multi-path techniques but at the cost of high energy consumption. We propose here the ODeSe algorithm which achieves very high reliability with lower energy consumption, thus providing better options in the reliability -energy consumption trade-off. More specifically, the results show that it is possible to attain the high reliability offered by the highest energy consuming CA algorithm (Soft CA) with energy consumption lower than the least energy consuming CA algorithm (Strict CA). Additionally, ODeSe offers a better trade-off than the highest reliability single-path algorithm evaluated (Single-path RPL with 7 RTX). Therefore, ODeSe offers a novel solution for high-reliability industrial wireless networks.

It may be possible to further improve performance, and in the next steps we will investigate the possibility of reducing the energy consumption of nodes by more intelligently choosing when nodes enable their radios to listen, by taking advantage of the information in the ODeSe control packets.

2. 1 .

 1 IEEE Std 802.15.4-2015 TSCH IEEE Std 802.15.4-2015 Time slotted Channel Hopping (TSCH)

Figure 1 :Figure 2 :

 12 Figure 1: TSCH schedule example.

Figure 3 :

 3 Figure 3: Grid-like network topology. Node S is the source node and node R is the DODAG root / destination node. The intermediate layers each contain nodes. Each node in each layer is connected to all the nodes in the layer preceding it ( -1).

Figure 4 :

 4 Figure 4: Algorithms for selecting an AP by using a Common Ancestor.

Figure 5 :

 5 Figure 5: Probability of finding an AP through common ancestors parametrized over the PS set size and the set size .

Figure 6 :

 6 Figure 6: Strict CA problem statement.

  scenario. (b) Parent change transition scenario.(c) Unsuited scenario.

Figure 7 :Figure 8 :

 78 Figure 7: ODeSe functions for parent selection.

Algorithm 1 :

 1 ODeSe. Input: HbH : The stored Preferred Parent within the Hop-by-Hop IPv6 extension header, HbH : The stored Alternative Parent within the Hop-by-Hop IPv6 extension header, : The current node.

Figure 9 :

 9 Figure 9:

1 .

 1 Single-path (SP) with: (a) 0 RTX, which means no retransmission when an ACK is not received. (b) maximum 1 RTX upon failure. (c) maximum 3 RTX upon failure. (d) maximum 7 RTX upon failure. 2. Multi-path Strict CA with 1 RTX maximum. 3. Multi-path Medium CA with 1 RTX maximum. 4. Multi-path Soft CA with 1 RTX maximum. 5. Multi-path On Demand Selection CA with 1 RTX maximum.

Figure 10 :

 10 Figure 10: Performance evaluation

  +1 = (source layer) ⋯2 = 2 (each intermediate layer) 1 = (layer of direct children of the root) = +1 + ( -1) ⋯2 + 1 = ( -1) 2 + 2

Figure 11 :

 11 Figure 11: Relationship between (a) the average copies per packet transmitted and the end-to-end PER per algorithm, (b) the average power consumption per node and the end-to-end PER per algorithm. The line represents the Pareto frontier.

15 end if 16 end if 17 end if 18 PP

1 Function ODeSe(HbH PP , HbH AP , ) 2 PP old ← PP( ) ; // Save current PP 3 if IS_VALID_PP( , HbH PP ) then 4 PP( ) ← HbH PP ; // Replace current PP 5 end if 6 if IS_VALID_AP_STRICT( , HbH AP ) then 7 AP( ) ← HbH AP ; // Use HbH AP as AP 8 else 9 AP( ) ← NULL ; // Clear the AP before CA call 10 AP( ) ← CA( , IS_VALID_AP_STRICT) ; // AP Strict 11 if AP( ) = NULL then 12 AP( ) ← CA( , IS_VALID_AP_MEDIUM) 13 if AP( ) = NULL then 14 AP( ) ← CA( , IS_VALID_AP_SOFT) aux ← PP( ) ; // Save the PP to use for this packet 19 PP( ) ← PP old ; // Restore old PP for other packets 20 return (PP aux , AP( )) 21 end

Table 1

 1 Simulation parameters.

	Simulation
	Replications/PRNG seeds	20
	Duration	until 250 pkts sent
	Data traffic		1 ∕15
	Routing		RPL
	Parent set size ( )		6
	size ( )		3
	UDP payload size		16 bytes
	TSCH	Single-path	Multi-path
	Scheduling	Centralized	Centralized
	EB period	4 sec	4 sec
	Timeslot length	10 ms	10 ms
	Slotframe length	297 Timeslots	297 Timeslots
	N o of channels	1	1
	N o of RTX	0 RTX, 1 RTX	1 RTX
		3 RTX, 7 RTX
	Topology
	Topology		Multi-hop
	N o of nodes		32
	N o of layers ( )		5
	N o of sources		1
	Link quality	Uniform distribution (U(a, b)):
		U(40%, 60%), = 50%
		U(50%, 70%), = 60%
		U(50%, 90%), = 70%

https://github.com/ariskou/contiki/tree/draft-ietf-roll-nsa-extension

SmartMesh IP Application Notes, Linear Technology Corp. 2012-2016.

Acknowledgment

The Cooja simulations presented in this research were performed on the Grid'5000 supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https:// www.grid5000.fr). Additionally, this work was partially performed and supported under the TPI ANR-17-CE10-0007-01 project of the French National Research Agency (ANR).