Mohamed Rahali

Jean-Michel Sanner

Gerardo Rubino

TOM: a self-trained Tomography solution for Overlay networks Monitoring

Network tomography is a discipline that aims to infer the internal network characteristics from end-to-end correlated measurements performed at the network edge. This work presents a new tomography approach for link metrics inference in an SDN/NFV environment (even if it can be exported outside this field) that we called TOM (Tomography for Overlay networks Monitoring). In such an environment, we are particularly interested in supervising network slicing, a recent tool enabling to create multiple virtual networks for different applications and QoS constraints on a Telco infrastructure. The goal is to infer the underlay resources states from the measurements performed in the overlay structure. We model the inference task as a regression problem that we solve following a Neural Network approach. Since getting labeled data for the training phase can be costly, our procedure generates artificial data for the training phase. By creating a large set of random training examples, the Neural Network learns the relations between the measures done at path and link levels. This approach takes advantage of efficient Machine Learning solutions to solve a classic inference problem. Simulations with a public dataset show very promising results compared to statistical-based methods. We explored mainly additive metrics such as delays or logs of loss rates, but the approach can also be used for non-additive ones such as bandwidth.

I. INTRODUCTION

Software Defined Networking (SDN) [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF] [START_REF] Zhang | A survey on software defined networking with multiple controllers[END_REF] and Network Function Virtualization (NFV) [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF] are new paradigms that enable operators to manage their network resources and handle the increasing demands driven by the new 5G introduction. Operators will therefore have effective tools to better manage their infrastructures and offer scalable and on-demand services to their clients. The NFV concept aims to decouple network functions from the hardware infrastructure by deploying virtualized entities on Custom Off The Shelf servers. This enables creating customized virtual networks to support the varied services. Multiple virtual networks, also called slices [START_REF] Zhou | Network slicing as a service: enabling enterprises' own software-defined cellular networks[END_REF], can be deployed over a common infrastructure. Therefore, network slicing will enable operators to partition their infrastructure to multiple slices to fulfill the customized requirements of the different clients and devices.

In the slicing concept, there are different levels of resource abstraction. Each layer has an abstracted view of the corresponding resources (for example: physical infrastructure, virtual infrastructure, and multi-domain environment). To ease incident diagnosis, the monitoring system must be able to infer the state of the underlying layer from the information collected in the overlay networks.

Network tomography [START_REF] Castro | Network tomography: Recent developments[END_REF] [START_REF] Lawrence | Network tomography: A review and recent developments[END_REF] studies the inference of internal network characteristics from end-to-end measurements. Typical targets are delays, loss rates, or bandwidth. Some approaches allow the discovery of networks topologies [START_REF] Eriksson | Efficient network tomography for internet topology discovery[END_REF]. One of the interesting applications is to reduce the complexity of monitoring and diagnostic tool and protocols spread out all over the infrastructure.

Although these solutions provide accurate estimation and try to minimize the computational complexity, they require a holistic view of the network state. In fact, the monitoring strategy should be dynamically adjusted according to network changes which occurs frequently in virtualized architectures. Network tomography solutions fit well with the SDN and NFV paradigm. Indeed, one of the inherent features of the SDN architecture is the global overview of the network. In addition, the virtualized technologies allow deploying scalable and extensible solutions for storing and processing the collected data.

This work proposes a flexible monitoring solution for the inference of additive metrics (delay or loss rate at logarithmic scale) in the underlying infrastructure from end-to-end measurements performed on the exposed abstracted resources inside an NFV-SDN networking architecture. We cross the collected end-to-end measurements to compute the metrics on the shared resources using a trained Neural Network. Our solution can be easily deployed in an SDN-NFV environment and guarantees the scalability and the flexibility of the monitoring system. The proposed architecture is based on virtual resources for data collection and processing. Thus, the update of the monitoring strategy is flexible and not costly.

The remainder of this paper is organized as follows. Section II summarizes the main related works for the monitoring of overlay networks and on network tomography issues. Section III describes the context of network slicing where our solution can be deployed. Section IV gives an overview about the approach we follow based on Neural Networks. The testing environment and the results analysis are presented in Section V. Finally, Section VI concludes this paper and gives an overview of our future work.

II. BACKGROUND AND RELATED WORKS

Overlay network monitoring [START_REF] Dusia | Recent advances in fault localization in computer networks[END_REF] [START_REF] Steinder | A survey of fault localization techniques in computer networks[END_REF] presents an interesting opportunity for the inference solutions proposed in network tomography. Two main families of approaches can be distinguished: in one of them, exact solutions are the goal,

In CCNC'2020

and the method consists in adding multiple conditions on the traffic collection points and the supervised paths. The related tools are mainly based on algebraic procedures. The other approaches are statistical in nature, and the goal is the estimation of the unknown metrics. This paper can be classified in the second category, even if it is based on Machine Learning instead of statistical techniques.

In [START_REF] Chen | Tomography-based overlay network monitoring[END_REF], the authors propose an algebraic solution to select the necessary paths in an overlay network to fully describe an additive metric on the rest of the available paths. Paper [START_REF] Demirci | Overlay network placement for diagnosability[END_REF] proposes a heuristic algorithm for the placement of overlay networks dedicated to the diagnosis of the underlying network. Other approaches have been published for the inference of additive metrics from end-to-end measurements. These solutions are suitable for the slice monitoring use case. In [START_REF] Gopalan | On identifying additive link metrics using linearly independent cycles and paths[END_REF], the authors proposed an algorithm to identify the minimal number of nodes and their placement in a given topology to collect monitoring traffic and to guarantee the identifiability of all the links. The selected points exchange traffic in order to collect end-to-end measurements that will be used to infer the link metrics. Paper [START_REF] He | Robust and efficient monitor placement for network tomography in dynamic networks[END_REF] deals with the same issue, but the idea is to adapt the monitoring strategy to the network topology changes. These types of solutions usually impose a set of rules for traffic collection points and probing paths. These constraints have to be satisfied in order to ensure proper operations of the monitoring system.

Concerning the methods relying on parametric statistical techniques, the unknown network parameters are considered random variables that follow a specific predefined probabilistic model. The model is then adjusted to fit the collected data. In [START_REF] Liu | Multicast vs. unicast for loss tomography on tree topologies[END_REF], the authors use multicast probing for loss rate inference. The network topology is fully covered with overlapping multicast trees and unicast paths to collect the end-to-end loss measurements. Then, a Maximum Likelihood Estimator is applied to infer the internal loss rates. In [START_REF] Lawrence | Network Delay Tomography Using Flexicast Experiments[END_REF], the authors mix unicast and multicast probing to propose the Flexicast framework for delay inference in a tree topology. The problem is formulated around a likelihood function where the link delay metrics are latent discrete variables. The likelihood is then maximized with the Expectation-Maximization [START_REF] Moon | The Expectation-Maximization algorithm[END_REF] algorithm. Observe that this procedure is characterized by a slow convergence time that is a drawback when dealing with large-scale networks.

In some recent works, Machine Learning solutions have been proposed for network monitoring and troubleshooting. For instance, [START_REF] Srinivasan | Machine learningbased link fault identification and localization in complex networks[END_REF] uses Supervised Learning to identify link failures. They mix classification techniques with a regression model to locate the failed links. The training is done with multiple features like traffic flow information, Round-Trip Times and loss rates. In this work, we also use Supervised Learning but with automatically generated labeled data. That is, we build a self-trained Neural Network as an inference solution tool for additive link metrics. Network slicing allows creating multiple virtual networks on top of a shared infrastructure. Hence, a failed node in the shared resources impacts the slices that share it. The customer who manages the slice makes regular checks on his deployed services in the virtual infrastructure to verify if the slice provider respects the Service Level Agreement (SLA). The monitoring agent in the slice periodically reports about the measurement performed at the virtual layer to a centralized monitoring unit. This entity can detect the SLA violations and transfer this information to the WAN Infrastructure Manager (WIM). The WIM manages the infrastructure where the slices are deployed. It aggregates the information transferred from the different clients and looks for the root causes of the reported incidents thanks to the tomography algorithm.

Fig. 1 illustrates the steps and the call flow between the monitoring units in the different layers to find the potential causes of an observed SLA violation on different slices:

1. A monitoring agent in each slice performs regular observations on the deployed virtual links. 2. Based on the load and performance measurements of data collected from each agent and its resources verification rules, the orchestrator detects the potential shortages of the virtualized resources and reports them to the WAN Infrastructure Manager (WIM). In the example of Fig. 1, the monitoring system notices an SLA violation in slices 1 and 2. 3. The WIM maps the virtual resources with their corresponding representation in the shared infrastructure. Thanks to the tomography algorithm, the WIM infers the possible root causes to the reported incidents and consequently, it performs remediation actions such as relocation of existing paths.

A. Network model and notation

Tab. I summarizes the main notation adopted in this paper. Consider the network topology (graph) G = (V, L) that hosts multiple virtual infrastructures, with the set of nodes V, the set of edges or links L, and denote |V|= V and |L|= L. Each of these virtual infrastructures is composed of virtual machines connected by virtual links. These virtual links represent an abstraction of paths in the underlying network. Let P denote the set of paths selected. A path p is represented by a Boolean vector of size L. If link i belongs to this path, p(i) is equal to 1, and to 0 otherwise. Let A be the Boolean matrix whose rows correspond to the paths vectors. Thus, A(i, j) is equal to 1 if j belongs to path p i , and to 0 otherwise. We denote by Y the vector of size P representing the observed metrics on the virtual paths; Y (i) represents the metric measured or observed on path p i . X denotes the vector of size L representing the unknown link metrics on the shared infrastructure; X(i) represents the metric on link i. Finally, we assume known an upper bound of those link metrics, denoted by B. Using this notation, the end-to-end metrics can be computed by [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF]:

AX = Y. (1)
The objective here is to evaluate X knowing Y and A, that is, to find an appropriate solution to this linear system. The typical situation here is that of an undetermined system (in practice, the number of equations P and the number of unknowns L satisfy, in general, P < L). In this paper we focus on this undetermined situation.

B. Additive metrics inference with Neural Networks

Our proposal is to transform the inference inverse problem described by (1) into a regression problem and to solve it using a Neural Network. For this purpose, since we know the architecture of the network, we can simulate the distribution of traffic through the network in many configurations, and observe many pairs (X, Y ). This can then be used to learn the connection between the two vectors, in the sense Y → X, following a Machine Learning approach. Figure 2 resumes this process.

We will consider a classic Neural Network architecture of the Feed Forward type, and for our tests here, with only one hidden layer. Each of our layers is fully connected to the next one (or to outside for the third layer), that is, both the neurons in the hidden and the output layers receive input from each of the neurons in the previous layer. The dimension of the input traffic τ (1) , . . . , τ (K) simulated network X (1) , . . . , X (K) Y (1) , . . . , Y (K) Fig. 2: We inject K different traffic configurations τ (1) , . . . , τ (K) into a simulated network and we measure both path metrics Y and link metrics X, obtaining K pairs (X (k) , Y (k) ), which constitute our training database. Of course, we can measure only X and deduce Y using [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF]. layer is equal to the number of paths P while L, the number of links, is the number of outcomes from the output layer. The dimension of the hidden layer is a variable parameter that we adjust for optimizing the performance. This happens, as expected, for a number of hidden units much larger than the dimension of the input.

C. Simulated traffic for the training phase

The training of the Neural Network requires a large volume of labeled data. In our problem, the features are the end-toend measurements and the labels are the link metrics. Hence, constructing the dataset requires collecting exhaustive link level metrics in a small time window for each input example. This process should be repeated in different network conditions to avoid the over-fitting of the model. Thus, collecting real data for the training introduces an important overhead in the process. This scenario seems to be unrealistic since the objective of the monitoring operation is to afford useful information about the network state without disturbing the network functioning. To avoid this issue, we train our Machine Learning tool using simulated data.

The Neural Network has to learn how to approximate the link metrics from the path measurements. In other words, it must capture the spatial correlations created by the topology that enable to find relations between the end-to-end measurements and the link metrics. In addition, the Neural Network should not be over-fitted to some specific values and should take into consideration the temporal variability of the link metrics. We propose to generate exhaustive random samples of link metrics denoted X . In fact, with each link metric, we associate a random value between 0 and B to construct one example of X . Its associated simulated end-to-end measurement Y is computed using Y = AX . This procedure is repeated multiple times to construct an important number of couples (X , Y ). The computed end-to-end metrics Y will be the features of the training, while the labels will be the generated link metrics examples X .

D. Training step

The inference of link metrics from path measurements can be considered as a regression problem. The input is the path-level measurements and the expected output is the linklevel metrics estimation. We train the Neural Network using the iterations of forward and backward propagation with the artificially created data. In our experiments, we use the classic Adam optimizer algorithm [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] for backward propagation. It is possible to pass all the training examples multiple times through the forward and backward process. An epoch in the learning process represents one forward and one backward propagation.

E. Testing step

After training the neural network with artificial data, we use it to estimate the link metrics from the path measurements. Observe that if there is a change in the network topology or the used paths, we have to repeat the training step taking into consideration the new updates. Observe also that this is a oneshot step, done only once. Using the trained Neural Network in the operational phase is then a quick procedure.

V. MODEL EVALUATION AND RESULT ANALYSIS

A. Singular Value Decomposition-based reference method

To illustrate the performances reached of our proposal, we compare it with a basic reference solution [START_REF] Chen | Tomography-based overlay network monitoring[END_REF] based on Singular Value Decomposition (SVD) [START_REF] Golub | Singular Value Decomposition and Least Squares Solutions[END_REF]: basically, every matrix A of dimension m × n can be written as A = U SU T where U is an m × m unitary matrix (that is, U U T = I), S is an m × n diagonal matrix whose diagonal is composed of the singular values of A (the square roots of the eigenvalues of matrix A T A) and U is an n × n unitary matrix. The pseudo-inverse of matrix A, denoted A + , is A + = U S + U T , where S + , the pseudo-inverse of matrix S, is the transpose of the matrix obtained by replacing the non zero singular values of A in S by their corresponding inverses. The link metrics can then be computed by multiplying the pseudo-inverse A + by the end-to-end measurement vector Y :

X = A + Y.
(

) 2
We use this method to compare it with our proposal to show the efficiency of Machine Learning solutions to solve a classic statistical problem. Comparing the performances of the different Machine Learning models in this inference task is in the scope of our future work.

B. Simulation environment

-3-1 0-2-1 0-4-1 0-4-2-3-1 0-2-3-1 0-2-4-1
Fig. 3: Topology A In order to evaluate the performances of our procedure TOM, we tested it using two different topologies taken from [START_REF] Mestres | Knowledgedefined networking[END_REF]. For each topology, we selected two nodes to exchange the monitoring traffic and we considered a predefined list of paths. Thus, these points correspond to the data centers where the virtual machines are deployed as described in Fig. 1. The used paths represent the mapping between the virtual links and their corresponding representations in the shared infrastructure. The two topologies are provided with a dataset of multiple samples of delay measurements performed on the different links. The traffic was simulated with the Omnet++4 network emulator. For each topology, we computed the endto-end delay on each path, that is, the sum of the delays on the links composing them, and we estimated the link metrics.

The error is evaluated using (3):

Error (in %) = 100 |V estimated -V real | B , (3)
where V real is the exact value of the metric V we are interested in, V estimated is the estimation, and B is an upper-bound of V . The first topology, shown in Fig. 3, has five nodes and eight edges. The second, depicted in Fig. 4, is composed of nine nodes and twenty-two edges.

-3-7-0-5-1 4-0-2-6-1 4-3-7-2-1 4-0-5-2-1 4-0-2-9-1 4-0-2-7-1 4-0-3-2-1 4-3-9-2-1 4-3-7-2-1 4-0-9-1 4-0-2-5-1 4-0-6-2-1 4-0-7-2-1 4-3-5-1 4-3-0-1 4-0-2-1 4-3-7-1 4-0-6-1 4-3-9-1 4-0-7-1 4-3-2-1 4-0-5-1
Fig. 4: Topology B

We made multiple tests to compare the results of our approach with the method described in Subsection V-A. We also evaluate the accuracy of the estimations and the computing time as a function of different criteria like the number of layers and their sizes, the size of the training data-set, the activation function chosen and the number of epochs in the learning process. After these experiments, we concluded, for instance, that a single hidden layer was enough to obtain a good performance (see V.C.2 below).

C. Results

We evaluate the performances of our solution regarding different parameters. The variation of the activation function and the number of epochs does not have a significant impact on the results. In the next tests, we use the Rectifier Linear Unit (ReLU) activation function and three epochs for the training phase. The errors indicated in the different figures are given in relative terms and in % as described by [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF]. For a fixed number of paths in one test, we select the first ones from the predefined list. We evaluate the performances of our proposal with two topologies and we compare it with the SVD-based solution. Fig. 5 and Fig. 6 illustrate the dispersion of the percentage error of the two solutions with the two studied topologies A and B.

Increasing the number of paths obviously enhances the accuracy of the solutions. The TOM technique has always a better estimation accuracy. The difference is more visible with topology B. In fact, with topology A and 6 paths, the median of the absolute error with our Neural Network is 4.8%, while it is 5.2% with the SVD-based solution. With topology B, when we use for example 19 paths, the median is 5.9% for the TOM method, while it is 22.7% when using the SVD. Using only 6 paths with topology A gives an underdetermined linear equation system. Thus, multiple solutions are possible. However, there are some links that are sufficiently covered by the set of paths so that the link metric can be computed exactly. Both the Neural Network and the SVD solutions compute these metrics with good accuracy. The difference is significant on the other links. In fact, the SVD-based approach gives one possible solution that satisfies the linear equation system, but not necessarily one close to the optimal one. The Neural Network is trained to choose the best solution that minimizes the absolute error. The difference between the two solutions is more evident when using topology B, because of the larger dimensions. The implicit covering of the correlations between the observed path metrics, given the topology of the network and the set of paths selected, done by Machine Learning technology manifests more clearly in these situations, when networks approach more realistic sizes. The main conclusions of this set of experiments are as follows. Firstly, varying the number of the hidden layer does not impact significantly the accuracy of the estimations. That is why we used only one large middle layer in our final evaluations. This doesn't preclude future tests with deeper architectures (see the Conclusions), but our goal here is to illustrate the approach. Secondly, we study the effect of the hidden layer size. Fig. 7 shows the variation of the absolute error regarding the hidden layer size. Increasing the hidden layer size enhances accuracy until reaching about 40 neurons. From this value, the error stagnates. The training time increases more or less linearly with the hidden layer size (see Fig. 8), increasing slightly at the end of the considered range. All these observations fit with the usual behavior of these technologies. In this paper, we propose a Neural Network solution called TOM for the inference of metrics in networks. The described work has been done in the context of SDNs, but it can be exported to other environments. We used additive metrics such as delays or logarithms of loss rates, leading to a linear algebraic context, but the approach can be used for other metrics such as bandwidth. One of the main features of our proposal is the use of simulated data in the training step. In addition, the learning phase can be carried out in a very short time period, which allows to easily manage changes in topologies. We used an emulated network traffic to evaluate the performances of our procedure. The results show that our Machine Learning approach gives better estimations than the pseudo-inverse statistical method.

Many points remain to be explored. Choosing an appropriate set of paths is one of the main open issues in this type of approach. The exploration of the learning tools used was just initiated in our work; a deeper exploration of the techniques available and their possibilities for our problem is one of our possible future tasks.

Fig. 1 :

 1 Fig. 1: Slices monitoring

6 Fig. 5 :

 65 Fig. 5: Topology A: error vs # of paths

Fig. 6 :

 6 Fig. 6: Topology B: error vs # of paths

Fig. 7 :

 7 Fig. 7: Topology B: error vs hidden layer size

Fig. 8 :

 8 Fig. 8: Topology B: training time vs hidden layer size

Fig. 9 :

 9 Fig. 9: Topology B: error vs dataset size The training data size has a similar impact as the hidden layer size. Increasing the number of training examples enhances the accuracy of the estimations until reaching the best performance. Then, adding additional examples for the training does not impact the accuracy as shown in Fig. 9, it increases only the training time (see Fig. 10).

Fig. 10 :

 10 Fig. 10: Topology B: training time vs dataset size

TABLE I :

 I List of main used variables

	variable	description
	G = (V, L)	network graph topology, node set V, link set L
	P	path set, P paths
	Y	end-to-end metrics, vector, size P
	X	link metrics, vector, size L
	IV. NEURAL NETWORK-BASED TOMOGRAPHY


Mohamed Rahali
email: mohamed.rahali@b-com.com

Jean-Michel Sanner
email: jean-michel.sanner@b-com.com

Gerardo Rubino
email: gerardo.rubino@inria.fr

FEAL: A source routing Framework for Efficient Anomaly Localization

Source routing represents a good opportunity to enhance monitoring solutions, particularly probing techniques. This technique allows deploying customized probing schemes to fulfill different monitoring needs like troubleshooting or Service Level Agreement (SLA) supervision. In this context, the use of probing cycles is a promising monitoring method. The deployment of such probing schemes becomes easier thanks to source routing since it allows constraining the traffic to follow specific paths.

, here extended to more general classes of metrics. We prototype and evaluate the FEAL framework with a P4 implementation of source routing over a Mininet emulator. The results show that our framework detects and localizes efficiently the failure points in the network.

I. INTRODUCTION

Internet networks are continuously evolving to satisfy the increasing clients' demands on connectivity offers. The emergent new services usually have high SLA requirements that must be respected (e.g. high-quality video streaming, augmented and virtual reality, connected cars). Operators and service providers should respect these requirements and must have suitable and efficient tools to detect SLA violations and make the needed remediation actions. Thus, the network monitoring tools should follow the network and services evolution to fulfill these new demands.

Classic monitoring procedures, based for instance on SNMP or traceroute, rely on the direct metrics measurement on network devices. These methods introduce an important overhead and do not help in the design of customized monitoring solutions. Probing techniques, where monitoring traffic is exchanged between specific nodes, i.e. monitors, are not well adapted to large backbone networks. For example, to check the operation of a specific router or link, it is very difficult to constrain the monitoring traffic to follow a specific path or to pass through the required network nodes due to mechanisms like multi-path routing, aggregated links and backup links [START_REF] Pelsser | From paris to tokyo: on the suitability of ping to measure latency[END_REF].

Recently, more attention has been accorded to apply source routing [START_REF] Filsfils | The segment routing architecture[END_REF] in network monitoring [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF] [START_REF] Li | ILP formulation for monitoring-cycle construction using segment routing[END_REF]. The main idea is that the traffic source encodes the forwarding path, or some parts of the path, in the packet header. Segment Routing (SR) [START_REF] Abdullah | Segment routing in software defined networks: A survey[END_REF] is an efficient and flexible method of applying source routing in MPLS networks [START_REF] Bashandy | Segment Routing with MPLS data plane[END_REF]. In SR, the path is encoded in the packet header as a list of segment ID (SID). Then, the packet is forwarded according to the instructions corresponding to the stacked SIDs.

Source routing has been well explored from a traffic engineering point of view [START_REF] Moreno | Traffic engineering in segment routing networks[END_REF]. It provides fast and efficient tools to deploy traffic forwarding strategies along arbitrary paths without any additional protocol or signaling procedure. It enables to constrain the traffic to pass throw particular places and thus, to build specific probing schemes. Some works focus on a specific approach of source routing for probing where only cycles are used [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF]. The probing cycle schemes have a significant advantage compared to regular paths. When the same node sends and receives the monitoring packets (the probes), it is not necessary to synchronize with the other nodes. This reduces synchronization issues between source and destination nodes. But in spite of the flexibility offered by source routing in monitoring, the technology presents multiple challenging issues. For example, most of the commercial switches support only a limited number of SIDs in the packet headers. This adds a constraint on the length of the probed cycles.

In this paper, we propose a monitoring framework called FEAL (Framework for Efficient Anomaly Localization). Our solution is composed of two main components, the "Cycle Probing" and the "Anomaly Detection" modules. For the first one, we consider minimizing the number of monitors as the main objective for the monitors' placement strategy. Meanwhile, we compare two conditions to be satisfied: covering the network topology, as in most previous works, and adding more conditions on the probed cycles to enhance the anomaly localization, following an algebraic modeling of the problem. The "Anomaly Detection" module is based essentially on a statistical approach for additive metrics inference that we proposed in [START_REF] Rahali | Unicast inference of additive metrics in general network topologies[END_REF], here adapted to a more general case.

The remainder of the paper is organized as follows. Section II overviews the work on network monitoring based on end-to-end measurement, especially the use of probing cycles. Sections III and IV present respectively the problem formulation and the framework components. Section V gives a description of the implemented proof of concept and the in ICC'20 performance results. Finally, Section VI concludes the work and outlines some perspectives for future developments.

II. BACKGROUND AND RELATED WORKS

In [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF], the authors propose a Segment Routing monitoring solution. A single monitor is deployed in a graph centroid and the probes are forwarded through the probing cycles starting and ending at that point. The paper proposes a set of algorithms to minimize the probing cycles covering the topology and to encode them efficiently. Using only one monitor reduces the monitoring operation cost and discards the synchronization problems. However, this requires very long cycles to cover the network topology which can introduce additional bias in the measurements. Authors in [START_REF] Li | Designing network monitoring schemes based on segment routing[END_REF] propose a method similar as in [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF] since they use only one monitor for the probing. They focus on minimizing the cycle cover length, which is the total length of all the probed cycles, to reduce the consumed bandwidth. An Integer Linear Programming (ILP) formulation of the same problem is proposed in [START_REF] Li | ILP formulation for monitoring-cycle construction using segment routing[END_REF]. Other works studied the monitors' placement problem while enabling the deployment of regular paths between different nodes. Similarly, the same optimization methods are still applicable. A well detailed classification of these different approaches has been presented in [START_REF] Dusia | Recent advances in fault localization in computer networks[END_REF] and [START_REF] Steinder | A survey of fault localization techniques in computer networks[END_REF].

In [START_REF] Gopalan | On identifying additive link metrics using linearly independent cycles and paths[END_REF], the authors give necessary and sufficient conditions to identify an additive metric on all the network links for a given topology. The proposed solution identifies the minimum number of monitors to exchange probes with regular paths or cycles. However, no constraint on the length of the paths is considered. In [START_REF] He | Robust and efficient monitor placement for network tomography in dynamic networks[END_REF] the authors propose a solution to find the optimal monitors placement for the inference of additive metrics from end-to-end measurements made on regular paths between different nodes. They give an algebraic formulation of the problem. The proposed algorithms are based on the graph decomposition into strongly connected components and find an efficient placement to guarantee the identifiability of all the links. [START_REF] Dong | Optimal monitor assignment for preferential link tomography in communication networks[END_REF] studied the same problem. Meanwhile, only a subset of links is privileged to guarantee their identifiability. This leads to the objective of finding the minimal number of monitors and their right placement in order to identify an additive metric on all the considered links. In [START_REF] Ma | Link identifiability in communication networks with two monitors[END_REF], the authors focus on the dual problem where the number of monitors is fixed first, and the objective is to find their effective placement to identify the highest number of links.

III. GENERAL CONTEXT AND PROBLEM DESCRIPTION

A. General context

A network monitoring operation usually has two main steps. First, the monitoring data is collected from the network via specific tools and protocols. Second, the collected information is examined and interpreted to detect and localize the existence of malfunctioning, in order to take the needed remediation actions. Thus, the FEAL framework is composed of two main components. The first one, the "Cycle Probing", is responsible for deploying the probing strategy and collecting the monitoring data. The second one, the "Anomaly Detection" module, is mainly based on a statistical algorithm that enables the localization of the most likely failure points from the collected end-to-end monitoring measures. As shown in Fig. 1, the FEAL framework can be deployed, for instance, as an SDN application over a network controller since it needs a global view of the network to deploy the probing strategy and adapt it according to the network updates.

B. Network model and notation

The network topology is modeled by a graph G = (V, L), with set of vertices V = {1, 2, . . . , V } and set of links L = {1, 2, . . . , L}. Let us denote by C = {1, 2, . . . , C} the set of given probed cycles. A is a C × L Boolean matrix whose rows code the probed cycles vectors: A(c, ) is equal to 1 iff cycle c includes link . The monitors send and receive the probes through these cycles and measure the end-to-end performances. Y denotes the metrics vector of the selected probed cycles. Hence, its size is C and the cth element Y (c) represents the metric on cycle c. X denotes the vector of the unknown link metrics. Thus, its size is L and its th element X( ) is the metric value corresponding to link .

C. Introducing two placement strategies

Consider the case of additive metrics, such as the delay, or the probabilities of not loosing a packet. Using the notation described above, the process of producing the end-to-end measurement linear operation

Y = AX. (1)
Assume that the objective of collecting end-to-end performances is to supervise the general network state and localize the failure points. Problems are simply defined by the fact that the considered metric value on a path/link (think, for instance, of delays or losses) are higher than some beforehand specified threshold. See that the metric whose value is 1 on path/link z iff there is an anomaly on z, is not anymore additive.

Covering all the network's links by the probing cycles allows the detection of any anomaly. From this observation, the first strategy for the monitors' placement, called LinkCovering, has simply the goal of covering the maximum number of links without any additional constraint. However, if a breakdown is detected, it is difficult to localize exactly the failed link. This requires computing the link metrics vector X. Now, to solve (1) for X, matrix A should be square and non singular. This adds new constraints to the probing cycles: we need L different cycles for which their vector representations are linearly independent. This constraint can be hard or impossible to satisfy in realistic conditions. A possible strategy is then to search the maximum of linearly independent equations to compute a good approximation of X. This leads to our second strategy for the monitors' placement, called MaxRank, whose goal is to choose the cycles such as the rank of A is maximized.

IV. FEAL FRAMEWORK Before searching the best monitors placement, the "Cycle Probing" module starts by exploring the possible cycles that can be generated from each feasible node v. Thus, we propose a resolution algorithm that explores the graph network to find all the possible cycles formed by less than k links, for a given k. In this way, the monitors' placement task can be seen as a set covering problem. For the LinkCovering strategy, the objective is to cover the set of links L. For the MaxRank strategy, the objective is to cover the network topology with cycles that give the maximum possible rank of matrix A to enhance the anomaly localization.

A. Additional notation

Let C k denote the set of probing cycles formed by less than k links. The subset that includes vertex v is denoted by C v k . Let us denote by B v k a basis of linearly independent vectors in C v k , with dimension dim(B v k ). For each vertex v, the set of links covered by C v k is denoted by R v k . The selected nodes of G for the monitors' placement are denoted by M.

B. Probing cycles encoding

Each probe stacks the forwarding path in the packet header as a list of SIDs. Most network equipment have a limitation on the number of SIDs which limits the probing cycle length. network s a b Fig. 2: To reach a link between nodes a and b starting from s, it is possible to forward the probe to node a with a node SID, then to b with an adjacency SID and finally to s with a node SID.

There are two types of segments: adjacency segments, when the router forward the probe to an intermediate link before achieving the final destination, or node segments, when the router sends the probe to an intermediate node.

It is possible to reach any point in the network with long paths encoded with node SIDs as proposed in [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF]. However, this can affect the measurement accuracy by introducing multiple sources of bias. If we consider the example illustrated in Fig. 2, to forward the probes from s to a or from b to s, the routers use the shortest paths as the regular traffic. However, it is difficult to know exactly the taken paths due to the dynamic mechanisms deployed for traffic load balancing. In our proposal, the cycles are encoded with only adjacency SIDs. The complete path is described in the packet header, so all the crossed links and nodes are well known beforehand. It is possible to make a trade-off by combining node and adjacency SIDs to extend the coverage of each monitor. However, the use of node SIDs should be well controlled to avoid uncertainty and bias in the collected end-to-end measurements.

In Algorithm 1 we describe a simple recursive method to generate the possible probing cycles starting and ending at a given vertex v.

Algorithm 1 Cycles construction

INPUT: Topology G, length k, vertex v. OUTPUT: C v k . 1: startN ode ← v 2: C v k ← ∅ 3: function FINDCYCLES(vertex, visited) 4:
if |visited| > k then C. LinkCovering algorithms 1) Optimal algorithm: We consider the monitors' placement task as a set covering problem. Thus, the objective is to minimize the number of selected monitors in M to cover L using the branch and bound technique. Finding the optimal solution for the set covering problem is NP-complete [START_REF] Caprara | Algorithms for the set covering problem[END_REF]. The branch and bound technique is an efficient method to deal with this complexity level.

Before exploring a branch of a solution space, the algorithm approximates the largest set of links that can be covered. The first step of the algorithm is the computation of the associated bounds of the methodology. If we consider the ordered set of vertices V = {1, 2, ..., V }, boundLinks v returns the largest set of links that can be covered by any subset of vertices included in {v, v + 1, ..., V }.

The MLC algorithm (Maximum Links Covering) is implemented with a recursive function as described in Algorithm 2. At each node v, the algorithm tests if all the non covered links are included in boundLinks v . Then, there are two possible recursive calls: either node v is selected or not. When the algorithm reaches the final step and all the links are covered, the set of selected nodes corresponds to a possible solution.

Algorithm 2 Maximum Links Covering algorithm (MLC)

INPUT: Topology G, R k . OUTPUT: Monitors placement M. 1: boundLinks V +1 = ∅ 2: for v ∈ V do 3: boundLinks V -v+1 ← boundLinks V -v+2 ∪R V -v+1

MLC(coveredLinks, usedN odes, vertex + 1)

Then, it is compared to the last saved solution to choose the best between them.

2) Greedy algorithm: The branch and bound method can reach a high accuracy, but its computational complexity is still very high, becoming useless in case of large topologies. Thus, we propose an alternative greedy approach described by Algorithm 3. The GMLC algorithm (Greedy Maximum Link Covering) makes multiple iterations. At each one, the network nodes are browsed to select the probing node that covers the maximum of new links. This process is repeated until the maximum possible number of covered links is reached.

3) Complexity analysis: The worst case complexity of the optimal algorithm is O(2 V L), when all the solution space branches are explored. There are 2 V possible combinations of monitors' placements. The complexity verification of the optimality of each one is O(L). The worst case complexity of the greedy algorithm is O(V 2 L). At each iteration, all the nodes are browsed to find the one that covers the maximum number of links which can be done in O(V L) steps. These iterations are repeated until covering all the links.

Algorithm 3 Greedy Maximum Link Covering (GMLC)

INPUT: Topology G, R k . OUTPUT: Monitors placement M.

1: maxLinks ← |BoundLinks 1 | 2: M ← ∅ 3: links ← ∅ 4: while |links| < maxLinks do 5: s ← s ∈ V|∀v ∈ V, |R v k \ links| ≤ |R s k \ links| & s / ∈ M 6: links ← links ∪ R s k 7:
M.add(s)

D. MaxRank algorithms

In this section, we focus on the second strategy for monitors placement whose goal is to maximize the rank of matrix A.

If we consider the global set of cycles C k , their associated vectors can be represented in a basis denoted by B k with dimension D. Therefore, the objective is to find D probing cycles, whose representative vectors are linearly independent to form the basis B k . Using the notation described before, the objective is to cover the basis B k with the minimal set of basis B v k which maximizes the rank of the obtained matrix A.

1) Optimal algorithm:

The Maximum Rank algorithm (MR) applies the same approach as the optimal algorithm for LinkCovering. Meanwhile, the condition becomes maximizing the rank of the matrix A.

Algorithm 4 Maximum Rank algorithm (MR)

INPUT: Topology G, Probing cycles C k . OUTPUT: Monitors placement M.

1: boundDim V +1 = ∅ 2: for v ∈ V do 3: boundDim V -v+1 ← bounDim V -v+2 ∪ B V -v+1 k 4: M ← ∅ 5: D ← dim(boundDim 1 ) 6: function MR(basis, usedN odes, vertex) 7: if vertex = V then 8:
if dim(basis) = D then:

MR(basis, usedN odes, vertex + 1)

The algorithm starts by computing the bounds used for the branch and bound technique. The objective is to cover the basis of linearly independent vectors B k . The bound for a subset of monitors is a basis of vectors representing the probing cycles of these nodes. boundDim v represents the basis of maximum dimension that can be formed with any subset of monitors included in {v, v + 1, ..., V }. The remainder of the algorithm is very similar to the LinkCovering strategy as described in Algorithm 4.

2) Greedy algorithm: The greedy approach of the MaxRank procedure uses the same concept as the LinkCovering strategy. The GMR algorithm (Greedy Maximum Rank) browses the graph nodes and chooses the best placement to maximize the rank of A. It makes similar iterations until covering the global basis B k . This process is described in Algorithm 5.

3) Complexity analysis: The worst case complexity of the optimal algorithm can be written O(2 V L 3 ). In fact, there are 2 V of monitors' placement combinations. Then, the verifica-

s ← s ∈ V|∀v ∈ V, dim(basis ∪ B v k ) ≤ dim(basis ∪ B s k ) & s / ∈ M 6:
basis ← basis ∪ B s k 7:

M.add(s)

tion of the optimality of each one requires to compute the rank of a L × L matrix (generally with smaller dimensions) with a complexity O(L 3 ).

The worst case complexity of the greedy algorithm is O(V 2 L 3 ). At each iteration, all the nodes are browsed to find the best one that maximizes the rank of A with a complexity O(V L 3 ). These iterations are repeated until maximizing the rank of A.

E. Anomaly Detection module

The "Anomaly Detection" module aggregates the end-to-end performances from the monitors to make a deeper analysis of the collected data. The FEAL framework integrates our previously proposed algorithm for the inference of additive metrics called ESA (Evolutionary Sampling Algorithm) [START_REF] Rahali | Unicast inference of additive metrics in general network topologies[END_REF]. The ESA algorithm computes the probability distribution for each link metric. Then, an alarm can be activated if the failure probability on a link exceeds a fixed threshold, let's say if Pr(X > V fail ) > p * . More details are available in [START_REF] Rahali | Unicast inference of additive metrics in general network topologies[END_REF].

V. EVALUATION

A. Proof of Concept and testing environment

To evaluate the performance of our solution, we implement a test-bed over the Mininet emulator. We experiment with topologies taken from [START_REF] Knight | The internet topology zoo[END_REF] and [START_REF] Orlowski | Sndlib 1.0—survivable network design library[END_REF]. We use a P4 [START_REF] Bosshart | P4: Programming protocol-independent packet processors[END_REF] software switch named "behavioral model" (bmv2) [START_REF]Behavioral-model[END_REF] with a source routing implementation from [START_REF]Source routing implementation[END_REF] to build the topologies. The monitors are implemented as Python scripts that are running over hosts connected to the switches.

Each host constructs the probes using the Scapy Python library [START_REF]Scapy python library[END_REF]. The forwarding path is stacked is the packet header. Before sending each probe, the host saves the sending timestamp with the associated packet identifier. When the probe comes back to its starting node, the host saves the returning timestamp to compute the end-to-end delay.

B. Results

1) Monitors placement evaluation: Firstly, we compare the performances of the optimal and the greedy approaches of the monitors' placement with different topologies with characteristics described in Table I. For each studied topology, we compute the minimal number of monitors to cover it, or to maximize the path matrix rank A. We vary the maximal number of labels k for path encoding. For small and medium topologies like A, B and C, the optimal and the greedy solution usually give the same results except for a few infrequent cases like topology C with k equal to 4. With larger topologies like D and E, the optimal algorithm cannot give results in reasonable computing time.

Comparing the two strategies for the monitors' placement, maximizing the rank of A usually requires more monitors than only covering the topologies, an obvious result.

Fig. 5 and Fig. 6 illustrate the computing time for the different experiences. The computing time increases exponentially according to the number of links only with the optimal algorithm as shown with topology C compared to A and B. Remark: the computing time of the second algorithm is too small compared to that of the first; this makes often hard to represent both in the same graphics.

2) Anomaly detection evaluation: We choose an anomaly detection use case to test the efficiency of the FEAL framework with its two probing strategies. For each experience, we choose randomly a link to generate an anomaly and the framework tries to localize it. Since we are focusing on additive metrics, the chosen scenario is to increase the delay on the selected link. We use the testbed described in Section V-A to make multiple tests on the two topologies A and B. Note that we cannot test with larger topologies since the used network emulator needs much more resources (CPU and memory) to emulate the needed scenarios in good conditions. However, the proposed algorithms are well adapted for larger ones. We make 30 different experiences for each topology. In each one, the "Anomaly Detection" module computes the probability of failure on each link. Then, the alarm can be activated if this probability exceeds a fixed threshold denoted p * . As a result, this task can be considered as a binary one, and the results for each fixed threshold can be summarized by four metrics that are described in Table II. There is an important feature in our case that must be taken into consideration. The two classes that we are considering, normal and failed links, are heavily imbalanced as shown in Fig. 7. The precision and recall metrics are well adapted to evaluate a binary classification model with imbalanced data [START_REF] Saito | The precision-recall plot is more informative than the roc plot when evaluating binary classifiers on imbalanced datasets[END_REF]. These metrics focus more on the positive class and is not affected by the large number of TN as described in [START_REF] Pelsser | From paris to tokyo: on the suitability of ping to measure latency[END_REF]. These values are used to plot the precision-recall curve presented in Fig. 8 for topology A. We use the AUC score (Area Under the precision-recall Curve) as a global indicator to evaluate the performances: the higher the area, the better the model accuracy. We make similar tests with the two strategies of probing. The MaxRank probing strategy outperforms the LinkCovering since its curve is always on the top. Besides, the AUC for MaxRank is 0.8, while it is 0.67 for LinkCovering. Fig. 9 represents the same tests made with topology B. The MaxRank gives always better results as in the first example. For this topology, the MaxRank probing requires 3 hosts to achieve the maximum rank, while the LinkCovering requires only one host. However, with topology A, both of the two probing strategies requires two monitors, but with different placements. This case shows that even with identical resources (number of monitors), the right placement can make a significant difference. VI. CONCLUSION In this paper, we study the use of source routing, particularly probing cycles, in network monitoring, from different points of view. We explore two different approaches for monitors placement, called LinkCovering and MaxRank, both modeled as a set covering problem, and we propose two alternatives each of them: an optimal branch and bound solution and a much faster greedy algorithm. The entire solution is implemented and tested over the Mininet emulator to evaluate its performances.

The paper compares the two approaches, because most of existing solutions consist of following the same ideas as in LinkCovering. The result is that MaxRank outperforms LinkCovering and enhances the anomaly localization performances. The proof of concept with P4 switches and a source routing implementation shows that the proposed ideas can be applied in realistic conditions. One constraint that can limit their applicability is the maximum of labels in the packet header. In this work, we consider a simple strategy for path encoding. An enhanced strategy of path encoding is possible to extend the coverage of each monitor which can reduce the cost of the probing operation and the efficiency of the anomaly detection.

The applicability to real networks of this approach relies essentially on the flexibility and the programmability offered by SDN networks. Problem sizes don't appear as a serious limitation.

Fig. 1 :

 1 Fig. 1: Framework components

  visited ∪ {v})

k 4 : 7 : 9 :

 479 M ← ∅ 5: maxLinks ← |boundLinks 1 | 6: function MLC(coveredLinks, usedN odes, vertex) if vertex = V then 8: if |coveredLinks| = maxLinks then: if |usedN odes| < |M| then:

9 :

 9 if |usedN odes| < |M| then: newBound ← dim(basis ∪ boundDim vertex )

Algorithm 5

 5 Greedy Maximum Rank (GMR) INPUT: Topology G, Probing cycles C k . OUTPUT: Monitors placement M. 1: D ← dim(boundDim 1 ) 2: M ← ∅ 3: basis ← ∅ 4: while dim(basis) < D do 5:

Fig. 3 :Fig. 4 :

 34 Fig.3: k vs number of monitors for LinkCovering strategy.

Fig. 3 and

 3 Fig.3and Fig.4illustrate the number of needed monitors for different value of k respectively for LinkCovering and MaxRank strategies.For small and medium topologies like A, B and C, the optimal and the greedy solution usually give the same results except for a few infrequent cases like topology C with k equal to 4. With larger topologies like D and E, the optimal algorithm cannot give results in reasonable computing time.Comparing the two strategies for the monitors' placement, maximizing the rank of A usually requires more monitors than only covering the topologies, an obvious result.Fig.5and Fig.6illustrate the computing time for the different experiences. The computing time increases exponentially according to the number of links only with the optimal algorithm as shown with topology C compared to A and B. Remark: the computing time of the second algorithm is too small compared to that of the first; this makes often hard to represent both in the same graphics.2) Anomaly detection evaluation: We choose an anomaly detection use case to test the efficiency of the FEAL framework with its two probing strategies. For each experience, we choose randomly a link to generate an anomaly and the framework tries to localize it. Since we are focusing on additive metrics, the chosen scenario is to increase the delay on the selected link. We use the testbed described in Section V-A to make multiple tests on the two topologies A

Fig. 5 :Fig. 6 :

 56 Fig. 5: k vs computing time for LinkCovering strategy.

Fig. 7

 7 Fig.7 shows the probabilities dispersion of 30 tests made with topology A. The prediction-recall curve is a model to evaluate the binary classification model. It is obtained by computing multiple pairs of precision and recall for different thresholds p * (represented by the dotted red line).

Fig. 7 :

 7 Fig. 7: Class distribution probabilities for 30 tests made with topology A. The MaxRank probing strategy is used with k equal to 4. The threshold p * is 0.5.

Fig. 8 :

 8 Fig. 8: Precision-Recall curve for 30 tests made with topology A. The two probing strategies are tested with k equal to 4.

Fig. 9 :

 9 Fig. 9: Precision-Recall curve for 30 tests made with topology B. The two probing strategies are tested with k equal to 6.

TABLE I :

 I Network topologies

	Toplogy A-GridNet B-Polska C-NewYork D-India E-Pioro
	Vertices	9	12	16	35	40
	Edges	20	20	51	80	89

TABLE II :

 II Binary classification parameters

	Variable	Description
	True Positives (TP)	Successfully detected link failure
	False Positives (FP)	False warning
	True Negatives (TN) Good prediction of normal links
	False Negatives (FN)	Not detected link failure