Anouar Rkhami

Gerardo Rubino

On the use of machine learning and network tomography for network slices monitoring

Keywords: 5G, Deep Learning, Transfer Learning, Network slicing, Overlay Network monitoring, Network Tomography

Network Slicing (NS) is a key technology that enables network operators to accommodate different types of services with varying needs on a single physical infrastructure. Despite the advantages it brings, NS raises some technical challenges, mainly ensuring the Service Level Agreements (SLA) for each slice. Hence, monitoring the state of these slices will be a priority for ISPs. However, due to the high measurements overhead, it is generally forbidden to directly measure the performance of all of these slices. To overcome this limitation, network tomography is a promising solution, consisting of a set of methods of inferring unmeasured network metrics using end-to-end measurements between monitors. In this work, we focus on inferring the additive metrics of slices such as delays or logarithms of loss rates. We model the inference task as a regression problem that we solve using neural networks. In our approach, we train the model on an artificial dataset. This not only avoids the costly process of collecting a large set of labeled data but has also a nice covering property useful for the procedure's accuracy. Moreover, to handle a change on the topology or the slices we monitor, we propose a solution based on transfer learning in order to find a trade-off between the quality of the solution and the cost to get it. Simulation results with both, emulated and simulated traffic show the efficiency of our method compared to existing ones in terms of both accuracy and computation time.

I. Introduction

Network Slicing (NS) [START_REF] Afolabi | Network slicing and softwarization: A survey on principles, enabling technologies, and solutions[END_REF] is a key technology that allows network operators to place dynamically different types of services with different types of requirements on top of a single physical infrastructure. Accordingly, NS opens up new business opportunities for network operators by allowing them to automatically lease customized network slices to third parties.

To achieve such an objective, NS leverages the last advents of Network Function Virtualization (NFV) [START_REF] Li | Software-defined network function virtualization: A survey[END_REF] and Software-Defined Networking (SDN) [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF]. NFV enables flexible deployment of services, while SDN offers a finer control of resources, including service isolation.

Despite the advantages it brings, NS raises some technical challenges. In fact, once the slices are leased, operators have to ensure that the Service Level Agreements (SLA) for each slice is guaranteed. Hence, monitoring the state of these slices will be a priority for both, operators and slices' tenants. Nonetheless, due to the high measurements overhead associated with the monitoring traffic, and sometimes the lack of cooperation of internal elements of the network, it is generally forbidden to directly measure the performance of all these slices. To overcome these limitations, Network Tomography is considered as a promising solution [START_REF] Lawrence | Network tomography: A review and recent developments[END_REF].

Network Tomography (NT) is defined as a set of methods that aim to infer unmeasured network metrics using an end-to-end measurement between monitors. Hence, it reduces the complexity of the monitoring and the network diagnostic process. Another motivation for using NT approaches for the slices monitoring is their perfect fit with the SDN and NFV paradigms. Indeed, NT methods require a holistic view of the state of the network, which is guaranteed through SDN technologies.

Most existing works in Network Tomography had put the accent on inferring all links metrics [START_REF] Ma | Inferring link metrics from end-to-end path measurements: Identifiability and monitor placement[END_REF] or a subset of links in a network [START_REF] Dong | Optimal monitor assignment for preferential link tomography in communication networks[END_REF] from end-to-end measurements. In this work and as [START_REF] Yang | On the optimal monitor placement for inferring additive metrics of interested paths[END_REF], we focus on inferring metrics for a set of paths of interest (i.e., slices). In fact, to infer the slices metrics, we don't necessarily need to monitor all the links involved in the slices, moreover, we may need to monitor links that don't belong to these slices. Hence, inferring, directly, the slices' metrics, is more efficient and uses less monitoring resources than the approaches that focus on links metrics inferring.

In this work, we focus on identifying additive metrics. Therefore, inferring the slices' metrics is equivalent to solving a system of linear equations, where the unknown variables are the slice metrics and the known constants are the end-to-end path measures. However, in practice, this system of linear equations is non-invertible [START_REF] Gurewitz | Estimating one-way delays from cyclic-path delay measurements[END_REF], [START_REF] Chen | An algebraic approach to practical and scalable overlay network monitoring[END_REF]. In other words, in most cases slices metrics cannot be uniquely identified.

To deal with these drawbacks, we formulate the task of solving the linear system of equations into a regression problem, which we solve using neural networks. By doing so, our approach can also be used in the case where the system of equations can be uniquely solved. Indeed, we can determine the values in an efficient way. We avoid the matrix inversion process that takes too much time in large networks.

Unfortunately, formulating the problem as a regression problem and the use of neural networks to infer slices metrics, raise two main challenges. First, the training process requires a large and diverse amount of real labeled data to avoid over-fitting. Hence, a real large labeled dataset of metrics must be collected in a small window of time, this will introduce an important overhead. The second issue is that with a learning based approach, if a change occurs in the network topology or the slices we monitor, the training of the neural network architecture must start from scratch to take into consideration the new changes. Repetitive training will then also introduce an important overhead. As response to the first concern, we train our neural network using simulated data. While for the second one, we unveil the potential of transfer learning techniques. [START_REF] Zhuang | A comprehensive survey on transfer learning[END_REF] Overall the main contributions of our paper can be summarized as follows:

• We propose a one-step solution to infer the slices' metrics using end-to-end measurements. We formulate it as a regression problem, which we solve using a neural architecture.

• Since neural network based methods require a huge and diverse amount of data, and to avoid generation an overhead in the collection process, we propose a self-training approach to solve the regression problem mentioned above.

• We avoid frequent retraining from scratch when a change occurs in the network topology, or in the monitored slices by using transfer learning techniques. We retrain only a part of the neural network architecture instead of updating all the weights. Hence we reduce the complexity of the approach.

• We conduct extensive simulations and we compare our approach against benchmark solutions. The results show the superiority of our approach in terms of error approximation of slices' metrics as well as the computational complexity. The remainder of this paper is organized as follows. Sec. II presents the main related work on network tomography. In Sec. III, we provide an overview of the context of our work and the notations we have used. Then, in Sec. IV, we delve into the details of our proposed method. Later, in Sec. V, we describe both the simulation setup and the results analysis. Finally, in Sec VI, we conclude and give an overview of our future work.

II. Related Work

Network tomography (NT) was introduced by Vardi [START_REF] Vardi | Network tomography: Estimating source-destination traffic intensities from link data[END_REF] in 1996. Since then, NT has been extensively studied [START_REF] Chen | Network tomography: Identifiability and fourier domain estimation[END_REF], [START_REF] Ma | Efficient identification of additive link metrics via network tomography[END_REF], [START_REF] Mahajan | Inferring link weights using end-to-end measurements[END_REF], [START_REF] Gao | Scalpel: Scalable preferential link tomography based on graph trimming[END_REF].

In NT, we distinguish between two main categories of approaches: algebraic and statistical procedures. In the algebraic approaches, the aim is to find exact solutions, link metrics are modeled as unknown constants metrics and they are inferred using linear algebra techniques. Regarding the statistical approaches, the objective is to approximate the link metrics. In this category, link metrics are modeled as a random variable with unknown probability distribution, then the link metrics are inferred using statistical techniques. Our work can be classified in the statistical category even if it is based on machine learning techniques instead of statistical approaches (e.g., Expectation Maximization (EM)).

Network slices monitoring can be defined as a particular case of overlay network monitoring [START_REF] Chen | Tomography-based overlay network monitoring[END_REF]. Several works focused on the use of network tomography techniques to monitor overlay networks. For example, in [START_REF] Chen | Tomography-based overlay network monitoring[END_REF], authors proposed 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. Moreover, M. Demirci et al. focused on the placement of overlay networks for diagnosability of the underlay network [START_REF] Demirci | Overlay network placement for diagnosability[END_REF]. Compared to these works, our work has a different scope, we aim to identify the state of the slices and not use the slices to diagnose the underlay network.

When the target is the additive metrics, the approaches suggested in the literature to infer link metrics can be used to infer the metrics of the slices. In fact, to infer the slice metrics from end-to-end measurements, we can infer the metric related to each link in the slice or all links in the underlay networks and then sum them up.

In [START_REF] Gopalan | On identifying additive link metrics using linearly independent cycles and paths[END_REF], A. Gopalan and al proposed an algorithm to determine the minimal number of monitors as well as their placement in a given network to collect end-toend measurements, that will be used to infer the links' metrics. These approaches are feasible, but, they fail to find the optimal number of monitors to be used to infer the slices' metrics. Hence, in [START_REF] Yang | On the optimal monitor placement for inferring additive metrics of interested paths[END_REF], the authors demonstrated that to infer the metrics of a slice, it is not necessary to know the metric of each link on the path. Based on that, they proposed an algorithm to find the minimum number of monitors and their placements to directly identify the slices measurements. What distinguishes our work from this work is that here we do not focus on monitor placement, but on inferring slices' metrics.

Regarding the statistical methods, the focus was on inferring links' metrics. In [START_REF] Liu | Multicast vs. unicast for loss tomography on tree topologies[END_REF], the authors presented a solution based on multicast probing and the expectationmaximization algorithm (EM) to estimate loss rate on links. Moreover, in [START_REF] Lawrence | Network delay tomography using flexicast experiments[END_REF], authors proposed Flexicast, a method based on a mix of unicast and multicast probing to infer links' delays in a tree topology. They formulate the problem as a likelihood maximization problem, which was solved using the EM algorithm. This kind of approach is characterized by its slow convergence time. In [START_REF] Rahali | Unicast inference of additive metrics in general network topologies[END_REF] there is a statistical algorithm called ESA merging the EM technique with an evolutionary approach, that outperforms previous mentioned proposals.

More recently, machine learning based solutions have been introduced for network monitoring. Sirnivasan and al used supervised learning, in particular a mix of classification and regression to locate the failed links [START_REF] Srinivasan | Machine learning-based link fault identification and localization in complex networks[END_REF]. Compared to our work, we also use supervised learning but we train a model using an automatically generated dataset. In [START_REF] Rahali | TOM: a self-trained tomography solution for overlay networks monitoring[END_REF], M.Rahali and al, used machine learning algorithms and more particularly neural networks. They trained them using a simulated training dataset. However, their focus was on the inference of underlying metrics using information collected in the overlay networks. If a change occurs in the underlay topology or the overlay networks, their approach has to repeat the training from the beginning, which will introduce an important overhead in the monitoring process.

III. Context and problem formulation

A. Context

As mentioned earlier, in this work we aim to monitor a set of network slices placed on a physical network using NT and machine learning techniques.

In general, the construction of an NT solution is done in three main steps: the selection of nodes for traffic data collection (i.e., monitors), the deployment of a probing strategy, and the inference of metrics.

In this work, we focus on the inference part. It is a key part because it is the one that quantifies the quality of the first and the second steps. Hence, we consider that the placement of monitors and the list of probed paths as known. Then, we collect the monitoring data and feed it to our model to estimate the slices' metrics.

B. Model and problem formulation

The notations used in this subsection are summarized in Table I. We assume that the topology of the physical network is known and we model it as an undirected graph G = (V, L) where V and L represent the sets of physical nodes and of the physical links, respectively. Let P denote the set of the probed paths and S the set of slices we want to monitor and which are deployed on top of the physical network G. The cardinals of the sets V, L, P and S are respectively, m = |V|, n = |L|, p = |P| and s = |S|. Let X denote the vector of the unknown links metrics, hence with size n. Similarly we denote by Y s the vector of the unknown slices metrics, size s. Finally, we define Y p as the vector of the measured or observed probed paths metrics, whose size is p.

Notation Description G = (V,
To model the relation between the physical links and the slices being monitored, as well as the relationship between the physical links and the measured paths, we define two matrices A s and A p . These are Boolean matrices and their shapes are respectively equal to (s, n) and (p, n). For A s the entry A s (i, j) is equal to 1 if the jth physical link belongs to the ith slice, and to 0 otherwise. Likewise, the A p (k, l) equals 1 if the lth link is on the kth path, 0 otherwise. Finally, we assume that the links' metrics have a known upper bound B.

Using the notation stated before we derive two main equations :

A s X = Y s , ( 1
)
A p X = Y p . ( 2
)
The objective here is to infer the Y s vector knowing A s , A p and Y p . To solve this problem, one may start by determining X solving Equation ( 2) and then, a simple multiplication with A s will give Y s . However, in practice, the linear system depicted in Equation ( 2) is undetermined (that is, p < m). Moreover, even in determined cases we have another issue here. Solving Equation (2) involves inverting matrix A p . This takes O(n 3 ) time, which can be too much for large graphs.

IV. Proposed Method

In this section, we detail our approach and explain how we model the inferred slices' metrics as a regression problem.

A. Inferring slices' metrics using neural networks

To solve the problems discussed in previous section, we model the metrics' inference as a multi-output regression problem, where the features are represented by Y p and the targets by Y s . Thus, solving the equation is equivalent to learning the f function defined by

Y s = f (Y p ). (3)
To learn f , we use neural networks (NNs). NNs can approximate any function as long as the hidden layers contain sufficient numbers of hidden neurons. By doing so, our solution can approximate the slices metrics in the case of an undermined system. Moreover, the direct learning of the relation between Y s and Y p makes the task independent of the size of the physical network, hence it can scale easily.

The neural architecture we used is a Multi Layer Perceptron (MLP) [START_REF] Ramchoun | Multilayer perceptron: Architecture optimization and training[END_REF]. It consists of one input layer with p neurons, one output layer with s neurons and h hidden layers. The number of neurons in each hidden layer is a hyperparameter that we fine-tune to reach an optimal performance.

To train this neural architecture, a set of pairs (Y s , Y p ) must be collected. Since we know the topology of the physical network, we can simulate the distribution of traffic in the network in many configurations and observe the pairs (Y s , Y p ).

B. Self training

Neural networks are efficient and autonomous once trained, however, as the case for any data-driven approach, it requires a huge and diverse pool of sample and therefore a large amount of labeled data. Moreover, to avoid the over-fitting problem [START_REF] Ying | An overview of overfitting and its solutions[END_REF], this process must be done under diverse network conditions Unfortunately, the latter process, will generate an overhead and may disturb the network functioning. To solve such a challenge, we propose to train our neural network using a simulated data. We propose to generate a large amount of random pairs

(Y ′ p , Y ′ s ).
The dataset is generated as follows: we generate a large amount of random samples of links metrics denoted as X ′ . We associate with each link metric a random value between 0 and an upper bound B to generate one sample of X ′ . Then, given A s and A p and based on Equations ( 1) and ( 2), we generate one pair

(Y ′ p , Y ′ s ).
After collecting the simulated dataset, we feed it to the neural network and train the latter using the backpropagation algorithm in order to minimize the mean square error (MSE) between the predicted and the target values [START_REF] Sammut | Mean Squared Error[END_REF].

Once the training of the neural network finished, we use it to estimate the slice metrics from path measurements.

C. Transfer learning

In real scenarios, the number of slices to monitor may vary with time. In addition, the path measurements can also change, either due to a failure on the physical network, or to an update of the monitors in charge of launching the probes. When these changes occur, and in order to take them into consideration, we have to update the neural network architecture and start the training process from scratch. However, changing the neural network architecture and restart training from scratch each time a new slice is added to the set of slices to monitor may be inefficient and may introduce an important overhead in the monitoring process. To deal with this challenge, we unveil the potential of transfer learning.

Transfer learning is a machine learning technique that allows to transfer what a model learned in one task to another one. Thus, when a change occurs, instead of building a new neural network (NN) and start the training process from the beginning, we take the last version of our model and we modify only the input or the output layer. If the update concerns the slices we monitor, it is the output layer that will be changed. While it will be the input layer which will be changed if the update occurs in the measurements' paths. Moreover, once we make this slight update, we train efficiently the new version of the model. We only update the weights of the new layer and freeze the other ones. This way, the model transfers what it learned before and then starts to learn how to adapt to the new changes.

V. Performance Evaluation

In this section, we evaluate the performance of our monitoring approach. To evaluate its effectiveness, we compare it to two main solutions. In what follows, we present a description of the simulation setup, then we define the approaches against which we compare our solution. Finally, we present and discuss the results.

A. Simulation Setup

In order to test the performance of our method, we tested it using two different topologies. The first one was taken from [START_REF] Mestres | Knowledge-defined networking[END_REF] and the second one from [START_REF] Knight | The internet topology zoo. Selected Areas in Communications[END_REF]. They are depicted, respectively, in Fig. 1 and Fig. 2. The First topology contains 9 nodes and 22 links, while the second one contains 54 nodes and 68 links.

For each network, two nodes are selected to start probes and exchange the monitoring traffic. Besides, we considered a predefined list of measurement paths, as well as the slices to monitor. The first topology is provided with a dataset of multiple samples of delay measurements preformed on its different links. To get this dataset, the traffic was simulated with the Omnet++4 network emulator [START_REF] Varga | Discrete event simulation system[END_REF]. Regarding the second topology, we generate a random dataset of link delays.

Based on these datasets, we computed the end-to-end delay on each path and on each monitored slice according to the equations ( 1) and [START_REF] Chen | Network tomography: Identifiability and fourier domain estimation[END_REF]. For the first topology we monitor 3 slices while for the second topology we monitor 20 slices. The main parameters of our simulation setup are summarized in Table II.

In order to assess the quality of the estimates,we define, in the following, the error formula:

Error = 100 × |Y estimated s -Y real s |. ( 4
)
In this equation, Y estimated s represents the estimated delay on the slices, while Y real s is the exact value we computed.

B. Baseline methods

In order to benchmark the performance of our proposed method, we compare it against two well-known state of the art solutions. They both aim to estimate the links' metrics and then use it to estimate the slices metrics.

They can be described as follows:

• Singular Value Decomposition-based method: This method relies on the singular value decomposition method (SVD) [START_REF] Golub | Singular value decomposition and least squares solutions[END_REF] to compute the pseudo-inverse of the matrix A p , denoted A + p . Then, the slices metrics are obtained by the following equation:

Y estimated s = A s A + p Y p ( 5
)
• Link level metric prediction: In this method, we apply the learning method we propose but to estimate the link metrics. Therefore, in this case, we define a neural network whose input is the path metrics and the output is the estimate of the link metrics. Once the training is complete, we replace the estimation of the link metrics in Equation ( 1) to get Y estimated s .

C. Simulation results

To compare the performance of our method with the above described approaches, we consider a neural network with only one hidden layer. In each case, we generate a simulated training set with 5 × 10 5 samples. The hidden layer contains 50 hidden units. These parameters were fixed after several tests when we saw that after increasing the number of hidden units we only increase the computation time while the performance is quasi the same. Moreover the training lasts for 5 epochs.

1) Estimation error vs number of paths used: With each topology, and based on the monitor placement, we fix a list of measurements' paths. For the first topology we fixed 20 paths, while we considered 60 paths for the second one.

To test the relation between the number of measurements paths used and the accuracy of the estimation, we made multiple tests. In each test, we select k paths from the predefined list and we compare the performance of our approach to the SVD and link-based estimations as a function of the number of paths used.

For example, for the first topology, first we use only 15 paths among the 20, then 16, and so on, in order to analyze the effect of the number of paths on the estimation error.

Figures 3 and4 illustrate the dispersion of the percentage error of the three methods with both topologies.

Increasing the number of measurements paths reduces the percentage error of the solutions. Our method has always a better estimation accuracy. With the first topology and while using 20 paths, the median of the absolute error is 3.45% with our method, while it was 3.71% for the link based method, and 10.76% for the SVD based method. With the second topology, when we use for example 20 paths, the median error is 4.34% for our approach, while it is 7.13% for the link based method and 12.07% for SVD.

Overall, we find that learning-based solutions have taken the lead from the SVD method. In addition, direct estimation of slice metrics is more precise and efficient. In fact, by dividing the task into link estimation and then using that estimation to obtain slice metrics, the error of the first step is propagated, and therefore the performance is lower than the direct method. With our approach, the neural network focuses directly on learning the solution that minimizes the error.

Finally, when using the first topology, we observe that the difference between our method and the one that learns to estimate link metrics is narrow. However, in terms of temporal complexity our solution is more efficient, since we only predict for 3 slices, while the other approach focuses on 22 links.

2) Transfer learning evaluation : In this section we study the performance of the transfer learning methodology we used. For space constraint, and without loss of generality, in these tests, we highlight results related to the second topology. We start with a case where we monitor only 10 slices. Once the training is done, we suppose that new slices are added to be monitored. we added 5, 10 and 15 new slices to the existing 10 slices.

For each case, we used the model trained to monitor the first 10 slices. Then we freeze all its layers except the last one, we change it with a new layer with 15 slices for example for the first case. Then, we compare the performance of this models with the ones that are retrained from scratch and do not use any weights from the original model, which was in charge of monitoring the first 10 slices.

In Figures 5 and6 illustrate the comparison in term of the median error of estimation and the time to finish one epoch of training after a change occurs. We observe that pre-trained models are less accurate than the whole trained ones. However this difference is tight, besides, when it comes to the training time to get these model, we observe that pre-trained models are three times faster than the other models.

To summarize, the use of transfer learning allows us to find a trade-off between the quality and the complexity of the monitoring solution. It transfers the knowledge acquired during past experiences to get a fast adaptation to the new changes.

VI. Conclusions and Future Work

In this work, we unveiled the potential of machine learning methods and network tomography techniques for network slices monitoring. We focused on additive metrics inference but the approach can be used for the nonadditive metrics as well. Unlike existing work, we focused on estimating the slices metrics and not the metrics of the physical links. Hence, we modeled the inference problem as a regression problem and we solved it by training neural networks. To deal with the challenges associated with the training of neural networks, we used a simulated data in the training step. Finally, we proposed a transfer learning technique in order to handle changes in the physical topology as well as the slices subject of monitoring. We evaluated the performance of our approach using an emulated and simulated network traffic. The results show that our approach outperforms the methods with which we compared in terms of both, accuracy and computational complexity. For future work, we plan to extend this work, by incorporating the first and second stages of network tomography monitoring. Namely, an intelligent selection of measurements' paths as well as an intelligent monitor placement for slices' monitoring. Furthermore, we plan to use neural architectures suitable for graph structured data.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Topology 1.

Fig. 3 .

 3 Fig. 3. Topology 1 error vs # of measurements paths

Fig. 4 .

 4 Fig. 4. Topology 2: Error VS # of measurements paths

Fig. 5 .Fig. 6 .

 56 Fig. 5. Topology 2. Error: Pre training vs Retraining from scratch


Anouar Rkhami

Learn to improve: A novel deep reinforcement learning approach for beyond 5G network slicing

Keywords: 5G, Virtual Network Embedding, Deep Reinforcement Learning, Relational Graph Convolutional Neural Networks, Resource Allocation

Network slicing remains one of the key technologies in 5G and beyond 5G networks (B5G). By leveraging SDN and NVF techniques, it enables the coexistence of several heterogeneous virtual networks (VNs) on top of the same physical infrastructure. Despite the advantages it brings to network operators, network slicing raises a major challenge: Resource allocation of VNs, also known as the virtual network embedding problem (VNEP). VNEP is known to be an NP-Hard problem. Several heuristics, meta-heuristics and Deep Reinforcement Learning (DRL) based solutions were proposed in the literature to solve it. Regarding the first two categories, they can provide a solution for large scale problems within a reasonable time, but the solution is usually suboptimal, which leads to an inefficient utilization of the resources and increases the cost of the allocation process. For DRL-based approaches and due to the explorationexploitation dilemma, the solution can be infeasible. To overcome these issues, we combine, in this work, deep reinforcement learning and relational graph convolutional neural networks in order to automatically learn how to improve the quality of VNEP heuristics. Simulation results show the effectiveness of our approach. Starting with an initial solution given by the heuristics our approach can find an amelioration, with an improvement in the order of 35%.

I. INTRODUCTION

5G networks are expected to handle multiple services with different types of requirements within a single physical infrastructure. In order to achieve such an objective, the Network Slicing (NS) [START_REF] Afolabi | Network slicing and softwarization: A survey on principles, enabling technologies, and solutions[END_REF] is certainly one of the most important building blocks.

NS leverages the last advents of Network Function Virtualization [START_REF] Li | Software-defined network function virtualization: A survey[END_REF](NFV) and Software Defined Networking [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF] (SDN) to enable the coexistence of heterogeneous Virtual Network Requests (VNRs) on top of the same Substrate Network (SN). In addition, NS provides network infrastructure providers (InPs) with new opportunities to increase their revenues. In fact, they will be more involved in the resourceprovisioning process by leasing their infrastructure to third parties.

Despite the benefits it brings, NS raises a plethora of challenges. The allocation of resources for network slices is considered to be one of the most important issues, which is known in the literature as the Virtual Network Embedding Problem [START_REF] Cao | A survey of embedding algorithm for virtual network embedding[END_REF] (VNEP). VNEP is known to be an NP-Hard problem [START_REF] Gupta | A Scalable Approach for Service Chain Mapping With Multiple SC Instances in a Wide-Area Network[END_REF] and several families of solutions have been proposed to solve it: Exact, heuristics, metaheuristics and finally deep reinforcement-based approaches [START_REF] Quang | A deep reinforcement learning approach for vnf forwarding graph embedding[END_REF].

While exact solutions ensure optimality, they are applicable only to small network instances [START_REF] Jang | Joint optimization of service function placement and flow distribution for service function chaining[END_REF]. For large networks, heuristics may find a solution within a reasonable time-frame, but they are sub-optimal [START_REF] Gong | Toward profit-seeking virtual network embedding algorithm via global resource capacity[END_REF]. To avoid this issue, meta-heuristics were proposed, they bring more flexibility and more efficiency in the exploration process [START_REF] Pham | Virtual network function-forwarding graph embedding: A genetic algorithm approach[END_REF], but they lack efficiency in the solution computation process. Indeed, they don't accumulate knowledge, for every new instance a new search process must be started from scratch. More recently, some works unveiled the potential of deep reinforcement learning to solve the VNEP [START_REF] Rkhami | On the use of graph neural networks for virtual network embedding[END_REF]. This category of approaches is more promising since with reinforcement learning we can overcome the issues stated before and learn from past experiences and with deep learning techniques we can extract the most relevant features automatically. However, due to the exploration-exploitation dilemma, the learning may lead to choose infeasible solution which may cause the rejection of critical network services as well as a decrease in revenues for InPs.

In this paper, we propose a new way of using DRL to solve the VNEP. Instead of learning a solution from scratch, which may result in an unsafe learning, we propose to train an agent to reduce the optimality gap of VNEP heuristics. This will lead to reliable solutions based on the DRL. Also, this will ensure that the worst-case result is equal to the one obtained with the heuristic.

To achieve this objective, we model the process of improving the quality of the heuristics as a reinforcement learning problem, where we train an agent to find the best strategy (policy). In each iteration of the training, the RL agent tries to improve sequentially the quality of the placement of the slices given by a heuristic.

The main contributions of this paper can be summarized as follows :

• We propose a safe DRL-based solution to the problem of resources allocation for network slices by learning how to reduce the optimality gap of heuristic-based solutions, • We formalize the task as a Markov Decision Process (MDP), • We represent the states of the system in a novel way using heterogeneous graphs, • In order to automate the features extraction process and let the agent benefit from the structural information, we model its policy using a Relational Graph Convolutional Neural-based architecture, • We design a specific reward function in order to guide the agent to improve the quality of the solutions. The remaining of this paper is structured as follows. The formulation of the VNEP problem is presented in section III. Then, the MDP formulation of the problem is presented in section IV. The neural network architecture and the training procedure is depicted in section V. The simulation setup and the performance evaluation are presented in section VI and the conclusions of the work are provided in section VII.

II. BACKGROUND

A. Heterogeneous Graphs

A heterogeneous graph and heterograph for short [START_REF] Shi | A survey of heterogeneous information network analysis[END_REF], is defined as a directed graph H = (V, E, T n , T l ) associated with two functions φ n and φ l . V, E, T n , T l represent, respectively, the set of nodes, the set of edges, the set of types of nodes and the set of types of links of the heterograph. φ n : V → T n maps each node v ∈ V to a single node type φ n (v), while φ l : E → T l maps each link e ∈ E to a link type φ l (e).

Besides, T n and T l satisfy the following condition:

|T n | + |T l | > 2 (1)

B. Relational Graph Convolutional Neural Networks (RGCN)

Graph Convolutional neural Networks(GCN) [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] were proposed as a generalization of the convolution operation on arbitrary graph-structured data. The aim of GCN is to extract features automatically from graphs. However, GCN can deal only with homogeneous graphs where we have only one type of edges between nodes (i.e |T l | = 1 ). Hence, RGCN [START_REF] Schlichtkrull | Modeling relational data with graph convolutional networks[END_REF] were defined as an extension of GCN to extract features from heterographs.

The key idea behind RGCN is that the encoding of a node is based on the encoding of its neighbors under all types of links.

Let H=(V,E,T n ,T l ) be a heterograph. We assume that each node v ∈ V has an input vector in v . Each layer of an RGCN network takes as input the feature vector in v and outputs a new vector out v according to the following equation :

out v = σ( r∈T l j∈N r v 1 c v,r W r in v ) (2)
where N r v represents the neighbors of node v under the link type r, c v,r = |N r v | represents a normalization constant and finally W r denotes the trainable weight matrix associated with the link type r.

III. PROBLEM FORMULATION

In this section, we describe the model of the SN, the VNR and their resources. Then, we define formally the VNE problem and the metrics to optimize, and by which we quantify the quality of the placement. The notations used in this section are summarized in Table I.

A. Networks and resources models

The susbtrate network is defined by an undirected graph G s = (N s , L s ), where N s represents the set of substrate nodes and L s the set of substrate links. The number of the substrate nodes and substrate links are |N s | and |L s |, respectively. Each substrate node n s has a computing capacity c n s and each substrate link l s has a bandwidth capacity b l s . Similarly, the VNR is represented by a directed graph

G v = (N v , L v ),
l v . Notation Description G s , G v
The substrate network and VNR graphs

N s , N v Set of

B. VNE Problem

The VNE problem can be divided into two stages: the virtual node mapping VNM and the virtual link mapping VLM. The former is defined as a function f VNM : N v → N s that maps a virtual node to a substrate node. It must be injective, that is, two VNFs of the same VNR cannot be hosted by the same substrate network.

f VNM (v i ) = f VNM (v j ) ⇒ v i = v j ∀v i , v j ∈ N v (3)
On the other hand, VLM can be modeled as a function f VLM : L v → P s that maps a virtual link to a physical path (set of physical links).

At the node mapping level, a virtual node is successfully deployed if the substrate node that hosts it has sufficient CPU resources,

c n v ≤ c fVNM(n v ) , ∀n v ∈ N v . (4)
At the link mapping stage, a VL is successfully deployed if its virtual nodes are deployed and if each physical link belonging to the physical path on which it is mapped has sufficient bandwidth,

b l v ≤ min l s ∈f vlm(l v ) b f VLM(l v )) , ∀l v ∈ L v . (5)

C. Optimization objective

In this work, the aim is to find a placement strategy of VNRs that uses efficiently the substrate network resources and maximize the InPs revenue. To quantify the quality of the embedding, several works used the revenue generated by embedding a request R as well as its cost C [START_REF] Fischer | An evaluation methodology for virtual network embedding[END_REF] and the cost of embedding a VNR G v are defined respectively as follows :

R(G v ) = n v ∈N v c n v + l v ∈L v b l v (6) C(G v ) = n v ∈N v c n v + l v ∈L v b l v × |P s l v | (7)
where |P s l v | represents the length of the physical path that hosts the virtual link l v . Since we want both: reducing the cost and increasing the revenue, we consider a new metric called Revenue to Cost (R2C), which is defined as follows :

R2C(G v ) = R(G v ) C(G v ) , if G v is accepted 0 otherwise
A VNR is accepted if, and only if, all its nodes and links mapping satisfy, respectively, the constraints (4) and [START_REF] Gong | Toward profit-seeking virtual network embedding algorithm via global resource capacity[END_REF].

IV. MDP FORMULATION

Instead of using DRL to find a solution for the VNEP, we will adopt it in order to optimize the quality of a solution given by a heuristic. In this section we give an overview of DRL and Markov Decision Process (MDP). Then we define the problem of Improving the Quality of VNEP Heuristics (IQH) within this framework.

A. Deep Reinforcement learning overview

In reinforcement learning [START_REF] Russell | Artificial intelligence: a modern approach[END_REF], we have two main entities, an environment and an agent. The learning process is done through the interaction between them so that the agent can optimize a total amount of return. At every time step t the agent gets a state representation s t from the environment and chooses an action a t based on the state representation. Then, the agent applies this action on the environment. As result the environment moves into a new state s t+1 and the agent receives a reward r t corresponding to this transition as well as the representation of the new state. This interaction can be modeled as an MDP M = (S, A, P, R) with a state space S, an action space A, transition dynamics P and a reward function R. The behavior of the agent is defined by a policy function π : S → A that maps the state to a distribution over the actions. The aim of RL is to find the optimal policy π * that maximizes the expected cumulative return. To achieve this, traditional RL methods used tabular representations for π. However, these approaches reached their limits when the state and action spaces are high. To deal with this, Deep Neural Networks (DNNs) were used instead of tabular methods to approximate the policy function. Moreover, DNNs help the agent to extract the most relevant features from the state representation.

B. Improving the Quality of VNEP Heuristics (IQH) as MDP

Given a VNE problem and an heuristic to solve it, the process of improving the quality of heuristics consists in starting with this initial solution and then modify it in order to increase its R2C score. Instead of modifying the solution in a one shot basis, we do it node by node. We define IQH as a sequential MDP where the states, actions and rewards are defined as follows:

• States: In RL, the state represents the raw information the agent gets from the environment and based on which it chooses an action. In this work we define the state as a hetero-graph that illustrates the solution of the heuristic. The hetero-graph is composed of 2 types of nodes and 3 types of edges : 'v connected', 'hosted by' and 'ph connected'. The two categories of nodes represent the virtual and substrate nodes, while the categories of edges represent the type of possible relation between these nodes. Each virtual node is connected to another virtual node under the relation v connected and each substrate node is connected to another substrate node under the relation s connected, and to represent the solution given by the heuristic , each VNF may be connected to a substrate node via hosted by type relation Each node has 3 initial features. For the virtual nodes:

(1) the CPU required by the VNF c n v , (2) the sum of requested bandwidth defined as the total bandwidth requested by the virtual links to which belongs the node; and (3) a flag indicating if the VNF is the current VNF to process. On the other hand each substrate node has the following features : (1) the remaining amount of CPU c n s , (2) the sum of bandwidth defined as the total remaining bandwidth of links to which belongs the substrate node; and (3) the number of its neighbors. Initially, a random VNF (virtual node) is selected as the current node. • Actions: At each time step t, the agent has to select either to keep the same placement of the current VNF or to modify it into another substrate that does not host any other VNF from the same request. Hence the action space at time step t is defined as follows :

A t = N s \S t ( 8
)
where S t represents the set of substrate nodes that host a VNF of the current slice at time step t excepting the current node. For example, as depicted in Figure ?? at step 0, A 0 = {1, 7, 6, 4, 5}.

Once the action for the current node is computed, we check its feasibility (i.e., chosen node has enough resources) and then we try updating the link mapping of edges, where the current VNF is head or tail. We run the shortest path algorithm between the new chosen substrate node and the placement of its neighbors under the relation 'connected v'. If the link mapping is feasible the agent will receive a new state representation, where the 'hosted by' link of the current VNF is updated according to the new computed node and a new virtual node is marked as the current node. If a failure occurs either on the node or on the link mapping stages, the action is not applied and the agent gets a new state representation, where only the current VNF is changed. Besides, after each step the agent gets a reward related to the action it made. • Rewards: The reward is the signal by which a RL agent can measure the correctness of the action it made. It can be positive in the successful cases or negative if the action leads to an undesirable behavior. The process to compute the reward obtained at each time step t is presented in Algorithm ??. The objective is to improve the R2C score of the solution given by the heuristic by updating the placement of virtual nodes sequentially, hence at each time step t if the action a t leads to an unfeasible solution the agent gets a negative reward of -100 and we keep the last feasible placement. Otherwise, the reward obtained is r t = rc tbp t , where rc t is the new R2C score after updating the placement of the t th node and bp t is the best R2C score found before the time step t. Initially bp 0 is the R2C score of the placement of the heuristic.

V. AGENT'S DESIGN

In this section we present the neural network-based architecture of the policy as well as its training process. reward ← (r2cbp) return reward, bp 12: end function

A. Agent Architecture

To choose actions, the policy of the agent is parametrized using deep neural networks and trained using the policy gradient descent algorithm.

The architecture of the agent is depicted in the Figure 2. The policy is a function that maps each state representation to a probability distribution over the actions. At each time step t given the state representation, the policy network outputs a distribution probability over the actions. However, since the state is represented by a heterograph, the first part of the policy network is in charge of encoding this information. This step generates a vector representation of all nodes in the heterograph using an RGCN network, then the vector of the current virtual node is selected and fed to a Multi-Layer Perceptron (MLP)

B. Training

To optimize the neural network architecture of the policy network and update its trainable parameters, we adopt the RE-INFORCE [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF] algorithm. REINFORCE is a policy-gradient algorithm, in other words it updates the policy network parameters to optimize an objective function using gradient descent. The objective is to maximize the cumulative discounted return:

R t = E[ t γ t r t ], γ ∈ [0, 1]. ( 9
)
where γ is the discount factor, by which we ensure the convergence of the cumulative return in the infinite horizon setups. The gradient of this objective is defined by :

∇R t = E[log(π θ (a t |s t ))Q π θ (a t , s t )] (10)
where Q π θ (a t , s t ) represents the expected cumulative reward by choosing a t in s t and following π θ . θ represents the set of trainable parameters of π With Reinforce, this gradient is estimated using a MONTE-CARLO approach. During each episode a rollout (s t , a t , r t ) is performed using the current policy π θ . At the end of each episode a gradient ascent step is performed and θ are updated as follows : T k=t r k -b k . This way, the trainable parameters are updated such that the probability of actions leading to a cumulative rewards higher than the average rewards is increased.

θ ← θ + T t=0 α log(π θ (a t |s t ))( T k=t r k -b k ) (11)

VI. PERFORMANCE EVALUATION

In this section, we present the simulation setup and an analysis of the obtained results.

A. Simulation setup

To assess the performance of our approach we consider the following simulation setup.

For the substrate network, we consider a random topology generated following the Waxman random graph model [START_REF] Waxman | Routing of multipoint connections[END_REF] , using the parameters α = 0.5 and β = 0.2; this methodology for topology generation has been commonly used in previous works [START_REF] Fischer | An evaluation methodology for virtual network embedding[END_REF]. Given this configuration, the generated substrate network will contain 100 nodes and 500 edges. The CPU and bandwidth of the substrate nodes and links are drawn uniformly from the interval [50,100].

To generate the virtual requests topology, we adopt the Erdős-Rényi model [START_REF] Erdős | On the evolution of random graphs[END_REF]. The generated topology is defined by the numbers of nodes n and the probability p for the edges creation. With p = 2 ln(n) n , the generated graphs are in general connected. The CPU and bandwidth requested by the VNR are drawn uniformly from the interval [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF]20]. The number of VNFs in each VNR is randomly chosen from the interval [START_REF] Kingma | A method for stochastic optimization[END_REF][START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF].

For the DRL agent, the policy architecture is set up with the parameters depicted in Table II. The RGCN part is represented by a 2-layer RGCN network. The first layer contains 16 hidden units and the second one 32 hidden units. The fully connected layer that maps the vector encoding the current node to the actions contains 100 units. We adopt a LeakyReLu activation for all layers except for the last one where we used softmax activation so as to get probabilities.

Each time a VNR arrives, the heuristic finds first the initial placement, and then an episode of quality improvement starts. There are 30000 episodes. We execute 10 runs with different seeds.

The model architecture , is written in Python using the Pytorch1 and the DGL2 libraries.

B. Heuristics

We evaluated our method in learning to improve the following heuristics :

• First-Fit: An heuristic that maps a virtual node into the first substrate node with sufficient CPU. • Best-Fit: Heuristic that maps a virtual node to the substrate node with the smallest sufficient CPU.

Fig. 3: Improvement rate while using First Fit.

Fig. 4: Improvement rate while using Best Fit.

Figures 3 and4 show, respectively, the improvement rates reached by the agent, for First-Fit and Best-Fit. For the First-Fit, we see that the agent could reach an improvement rate of 35%. Moreover, the performance of the agent gets better with time. On the other hand, with the Best-Fit strategy, the task was harder for the agent in the beginning, but with the negative rewards it got, the agent learned to avoid bad decisions and converges to an improvement rate of 20%. Note that when the agent fails to improve the heuristic solution (the worst case) we don't apply its decision but it learns from it.

To assess the robustness of the proposed approach we modify the interval from which the number of VNFs per VNR is drawn from [START_REF] Kingma | A method for stochastic optimization[END_REF][START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF] to [START_REF] Pham | Virtual network function-forwarding graph embedding: A genetic algorithm approach[END_REF][START_REF] Rkhami | On the use of graph neural networks for virtual network embedding[END_REF]. Figures 6 and5 show the results using the First-Fit and the Best-Fit strategies under this setting. Even the task becomes harder, the agent learns and finds a way to improve both heuristics under this new setting. For First-Fit the agent reached an average improvement rate of 16%, while for Best-Fit the improvement rate was of 13%.

VII. CONCLUSIONS

Virtual network embedding in 5G and beyond 5G networks is known to be an NP-hard problem (when properly converted to a decision problem). In this work we unveiled the potential of deep reinforcement learning in a novel way. Instead of learning a solution from scratch using DRL we trained a reinforcement learning agent to reduce the optimality gap of heuristics dedicated to solve this problem. We modeled the task as a sequential Markov decision process, where the states are represented using heterogeneous graphs. To exploit the graph information we exploited RGCN to parameterize the policy network and in order to guide the agent to the desired behavior we defined a reward function that gives the agent a positive reward each time it could improve the quality of the heuristic. To validate our approach we learned to improve two heuristics: First-Fit and Best-Fit. the simulation results showed that we can reach an improvement rate of 35% for First-Fit and 20% for Best-Fit.

In the future, we are planning to learn to improve other heuristics and under different settings.

  where N v represents the set of VNFs and L v represents the set of virtual links. The numbers of VNFs and VLs are |N v | and |L v |, respectively. Each VNF n v has a computing demand denoted as c n v , and each VL l v has a bandwidth demand b

Fig. 1 :

 1 Fig.1: Illustration of the sequential process of Improvement of quality of VNE heuristics. The state is represented using an heterograph whit two types of nodes and three types of links. At each step either the placement of a virtual node is modified or kept.

Algorithm 1 reward 1 :

 11 Compute function getReward(bp, r2c)

Fig. 5 :

 5 Fig. 5: Improvement rate while using Best Fit .

Fig. 6 :

 6 Fig.6: Improvement rate while using First Fit.

  substrate nodes and VNFs L s , L v Set of substrate links and VLs P s Set of substrate paths cns Available CPU at substrate node n s b l s Available bandwidth of substrate link ls cnv CPU request of VNF n v b l v Bandwidth request of VL lv

TABLE I :

 I Notations

TABLE II :

 II DRL agent Hyperparameters b t represents a baseline for reducing the variance of the estimate and it is equal to the average of the cumulative reward starting from time step t, b t =

https://pytorch.org/

https://www.dgl.ai/