Hamza Ben-Ammar
email: hamza.ben-ammar@irisa.fr

Yassine Hadjadj-Aoul
email: yassine.hadjadj-aoul@irisa.fr

Soraya Ait-Chellouche
email: soraya.ait-chellouche@irisa.fr

Efficiently allocating distributed caching resources in future smart networks

Keywords: Multi-cache systems, Cache allocation, Multiobjective optimization, GRASP, VNF placement

During the last decade, Internet Service Providers (ISPs) infrastructure has undergone a major metamorphosis driven by new networking paradigms, namely: Software Defined Networks (SDN) and Network Function Virtualization (NFV). The upcoming advent of 5G will certainly represent an important achievement of this evolution. In this context, static (planning) or dynamic (on-demand) caching resources placement remains an open issue. In this paper, we propose a new technique to achieve the best trade-off between the centralization of resources and their distribution, through an efficient placement of caching resources. To do so, we model the cache resources allocation problem as a multi-objective optimization problem, which is solved using Greedy Randomized Adaptive Search Procedures (GRASP). The obtained results confirm the quality of the outcomes compared to an exhaustive search method and show how a cache allocation solution depends on the network's parameters and on the performance metrics that we want to optimize.

I. INTRODUCTION

The endless race of content providers towards even more content and more quality is increasing data consumption as never before. This growth is such that it is undermining the infrastructure of Internet Service Providers (ISPs). The latter organize themselves by developing caching capabilities, increasingly close to end-users in order to relieve the load on their networks [START_REF] Bertin | Next-Generation PoP with Functional Convergence Redistributions[END_REF]. These recent developments allow them to share their infrastructure by offering these caching capabilities to third parties, which makes it possible to multiply sources of revenues. The virtualization of network functions (NFV), especially caching, as well as the dynamic orchestration of resources bring much more flexibility to the infrastructure and their management. These features will be, therefore, major drivers that will certainly accelerate these developments and make them available to content providers [START_REF] Parvez | A survey on low latency towards 5g: Ran, core network and caching solutions[END_REF]. These building blocks represent, indeed, the main foundation of the future core of the mobile network, namely 5G.

Setting up an optimal caching system within a network infrastructure, up to the edge of the latter at the Multi-access Edge Computing (MEC) level, is very complex and remains an open issue in the literature [START_REF] Reddy | Effects of storage heterogeneity in distributed cache systems[END_REF]. In fact, if we want to optimize the use of caches, we will tend to put everything in the same place at the exit of the network (at Point of Presence (PoP) level), where users requests will be aggregated. This allows to maximize the hit rate, but has the drawback of overloading the network. However, if one wants to maximize user satisfaction while at the same time reducing network load, the ideal would be to put everything on the edge. The problem here is that there will be more redundancy at the edge because of the multitude of access networks and the origin server will be more solicited.

We investigate, in this paper, the optimal placement of caching resources. The proposed approach solves the trade-off between minimizing the hit rate in the origin server (with the risk of degrading the quality of experience) and minimizing the distance between clients and the requested contents (with the risk of ineffective caching). For this purpose, we propose a model considering, at the same time, the different objectives mentioned below, namely: (i) latency (or distance), in order to bring the content closer to the users, and (ii) the cache hit in the ISP, in order to request the origin server the least. We model the cache allocation problem as a multi-objective integer nonlinear program. Since it is an NP-hard problem, we propose the use of the Greedy Randomized Adaptive Search Procedures (GRASP) [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF], which has shown its effectiveness in solving combinatorial optimization problems.

The reminder of this paper is organized as follows. In section II, we present the related work. Section III provides the detailed description of the cache placement problem and the proposed solution. Then, the evaluation of our proposal is displayed in section IV. Finally, section V summarizes the achievements in this paper and introduces our future work.

II. RELATED WORK

Many studies have investigated the problem of cache resource allocation and placement in the context of multi-cache networks (e.g., CDN, ICN, etc.). Krishnan et al. in [START_REF] Krishnan | The cache location problem[END_REF] studied the cache location problem in the case of transparent inroute caches in the context of web caching. The problem was modeled as a k-median problem, where the objective is to minimize the network traffic flow, and solutions were proposed based on dynamic programming and greedy heuristics. The study in [START_REF] Rossi | On sizing ccn content stores by exploiting topological information[END_REF] was probably the first attempt to investigate the cache allocation problem in CCN. They used in their study different metrics to measure the centrality of routers like degree, closeness and betweeness in order to decide where the cache should be distributed along the network's nodes. They suggest that deploying more cache resources at the core nodes of the network is better than at the edge. In later works [START_REF] Psaras | In-network cache management and resource allocation for information-centric networks[END_REF] [8], the authors have concluded the opposite, suggesting that placing larger caches at the edge is more effective. Wang et al., in their work [START_REF] Wang | Design and evaluation of the optimal cache allocation for content-centric networking[END_REF], have studied the impact of content popularity distribution on caching performance in CCN. They show that placing caches into the network core is better suited for content requests with uniform distribution and that in case of highly skewed popularity demands patterns, pushing cache resources to the edge yields better performance.

Considering a single metric clearly reduces the complexity of the problem, but has led many studies to find contradictory results. There are many aspects in our proposal that makes it different from the existing works. We propose a versatile tool that takes into account more than one performance metric to solve the cache allocation problem and it can be tuned in order to seek some specific results. In addition, the solutions are built by measuring the contribution of all the nodes by the means of an analytic model capable of estimating the network performance, which will allow to take into account the impact of a node's performance on the others.

III. MULTI-OBJECTIVE CACHE PLACEMENT STRATEGY

A. Problem description

In previous works that addressed the cache allocation problem, only one performance metric is generally considered to generate a solution. In this work, we use jointly the following two performance metrics to evaluate the cache gain: content provider load and average distance ratio. The first metric represents the amount of contents that were served by the origin server over all the requests sent in the network. The second one depicts the average distance travelled to get contents in the network over the obtained distance without caching. We chose these two metrics for their importance in representing the cost and gain obtained from in-network caching. A high content provider load means most of the requested contents are not served by the intermediate caches. Accessing the main source of contents is expensive for network operators, this is why it is important for them to keep the content provider load as low as possible. On the other hand, a low average distance to get contents means a better Quality of Experience for users. Hence, a good cache allocation strategy should find the best trade-off between these two metrics.

B. System assumptions

Let G = (V, E) be the graph representing a network of caches, where V = {v 1 , ..., v M } depicts the nodes of the network and E ⊂ V × V is the set of links connecting the nodes. Each node is equipped with a caching module used to store contents locally. Let C = {c 1 , ..., c R } be the set of the catalog's contents available for the users. We assume that all the accessible contents in the system have an identical size and are divided into small packets or chunks, which are in turn of the same size. The cache capacity is then expressed in terms of the number of contents or chunks that can be stored. All the available contents are stored permanently at one or more servers attached to some nodes within the network.

Clients, which are attached to the network nodes, send requests into the network looking for contents. The pattern of these requests is characterized by the Independent Reference Model (IRM) [START_REF] Fricker | Impact of traffic mix on caching performance in a content-centric network[END_REF]. Suiting the IRM model, users generate an independent and identically distributed sequence of requests from the catalog C of R objects. Specifically, the probability p r to request an item c r from the set of available contents in the network is constant and follows a popularity law, where the contents are ranked decreasingly according to their popularity from one to R. As already argued in many previous studies, the latter fits the Zipf law [START_REF] Fricker | Impact of traffic mix on caching performance in a content-centric network[END_REF]: the probability to request the content of rank r is:

p r = r -α / ∑ R i=1 i -α
, where α, the skew of the distribution, depends on the type of the accessible objects. In the present work, the LRU algorithm is used to manage the node's content store and the Leave Copy Everywhere (LCE) scheme is employed as a caching policy. LCE is the default caching scheme used in multi-cache networks, where the objects received by each node is always cached. Note that the proposed solution may work similarly with other caching strategies.

C. Problem formulation

A cache allocation solution (typically taken by an NFV orchestrator), can be defined by a vector X = (x 1 , . . . , x M ), where x i represents the amount of storage capacity placed in node v i . To compute the content provider load or the average distance ratio of a configuration of caches X, we use our model MACS (Markov chain-based Approximation of Caching Systems), which we presented in previous works [START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF] [START_REF] Ben-Ammar | A versatile markov chain model for the performance analysis of CCN caching systems[END_REF]. MACS is an analytic tool that allows us to estimate the cache hit ratio of an interconnection of caches, which can be used to compute other performance metrics like the content provider load and the average distance ratio. By using MACS and for each cache allocation configuration X, we can evaluate the performance of the whole system in its steady-state and not just during a transient phase.

Since in this work the caching capacity of a Virtual Network Function (VNF) or a physical cache is expressed in terms of the number of contents that can be stored, then we have x i ∈ N. As we measure the caching gain through evaluating the content provider load and the average distance ratio in the network, our objective is to find a cache distribution solution such that the evaluation metrics that we have chosen are optimized (i.e. minimized). The cache placement is then formulated as a multi-objective optimization problem as follows:

minimize f 1 (X), f 2 (X) subject to ∑ i x i ≤ Tc, i = 1, . . . , M, x i ≥ 0, i = 1, . . . , M, x i ∈ N. (1)
The value of T c represents the total cache resources available in the network. The expressions f 1 (X) and f 2 (X) are expressed as a percentage and represent, respectively, the content provider load and the average distance ratio of a cache placement configuration X. Using MACS, we can calculate the cache hit and cache miss ratios of the network's nodes. Then, we can compute f 1 (X) and f 2 (X) as follows:

f 1 (X) = ( s ∏ i=1 P miss (i) ) × 100, f 2 (X) = ∑ s i=1 ( ( ∏ i-1 j=1 P miss (j) ) × P hit (i) × Dist(i) ) Dist(s) × 100. (2)
The values P miss (i) and P hit (i) represent, respectively, the cache hit and cache miss of a network's node v i . The expression Dist(i) is the distance from where the clients requests were generated to the node v i . The index s represents the nearest node v s to the clients to which a content provider is attached (i.e. where a permanent copy of the contents is available). In the definition of f 1 (X) and f 2 (X) and for sake of clarity, we supposed that the network is formed by a line of s nodes numbered from i to s where the clients are attached to node v 1 and the content repository is located just after node v s . It has to be noted that of course, we can compute these metrics or other ones in any type of network topology. Since here we are dealing with a multi-objective optimization problem, in which we want to minimize f 1 (X) and f 2 (X), the solutions will be a set of efficient points usually called the Pareto frontier. Pareto efficiency or optimality implies that a solution to a multi-objective problem is such that no single objective can be improved without deteriorating another one. In our case, a solution X * is said to be efficient if there is no other solution X such that f 1 (X) < f 1 (X * ) and

f 2 (X) ≤ f 2 (X * ) or f 2 (X) < f 2 (X * ) and f 1 (X) ≤ f 1 (X * ).
Given that integer nonlinear programming is an NP-hard problem, solving the cache allocation problem as we modeled below will come at a very high computational cost. Therefore, we propose the use of the meta-heuristic GRASP to solve it.

D. Solving cache allocation problem using GRASP

The Greedy Randomized Adaptive Search Procedures or GRASP [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF] is an iterative process, where each iteration consists basically of two steps: construction and local search. The construction phase seeks to build a feasible solution using a greedy randomized approach, whose neighborhood will be investigated during the local search in order to find a local optimum. The best overall solution is, then, kept as the final result. During the construction phase, the candidate set CS will be the list of cache placement configurations X i where a partial resource that we denote P c , is taken from the total available cache T c and allocated to one of the network's nodes. If we have for example a network with three nodes, T c = 100 and P c = 10, the initial candidate set will then be: CS = {(10, 0, 0), (0, 10, 0), (0, 0, 10)}.

Each candidate is then evaluated with a greedy function in order to build a restricted candidate list RCL, which will contain some of the candidate set who have the best evaluation values (e.g., RCL = {(10, 0, 0), (0, 10, 0)}). The limitation criteria of the list cardinality can be either based on the number of elements or based on their quality. The elements added to the RCL list will then be those having an evaluation value inferior to the threshold (i.e., f (X) ∈ [f min , f min + β(f max -f min )]). The value of β will control the insertion condition of candidate elements to RCL. The case β = 1 is equivalent to a random construction, while β = 0 corresponds to a pure greedy algorithm. Once RCL is built, an element from it is randomly selected and added to the partial solution. The candidate list CS and the evaluation function are then updated and the construction is repeated until the total use of the cache budget T c . If we consider for example that the second element from RCL has been chosen, the current partial solution will then be S = (0, 10, 0) and the new candidate list will contain: CS = {(10, 10, 0), (0, 20, 0), (0, 10, 10)}.

Once the cache budget T c is distributed, the local search will seek to improve the generated solution (e.g., S = (20, 40, 40)) by evaluating its neighborhood. We used for the neighborhood search the following procedure: starting from the solution generated by the greedy randomized construction, we transfer an amount of cache P c from one node to another looking for a configuration whose cost function value is lower than the current one. If a better neighbor is found, we keep it and repeat the search in order to find a better solution (e.g., Neighbor(S) = (10, 50, 40), (30, 30, 40), etc.). The best overall solution S is then returned as the output of GRASP.

When dealing with multi-objective GRASP [START_REF] Martí | Multiobjective grasp with path relinking[END_REF], the candidate elements will be evaluated with more than one function (in our case, we have f 1 (X) and f 2 (X)) and there are many methods that can be used to compute the outcome of each configuration in the construction and local search phases (see [START_REF] Martí | Multiobjective grasp with path relinking[END_REF] for more details). For example, and in our case, one can use f 1 (X) in the construction phase and f 2 (X) during the local search and vice versa, or choose randomly between the objective functions during each GRASP iteration. We can also consider a weighted combined method (f (X) = w 1 f 1 (X)+w 2 f 2 (X)). The choice of which method to be used to evaluate a candidate solution can depend on some desired results that should be achieved or some constraints that should be respected. In our work, we considered many methods to generate the solutions based on the defined objective functions f 1 (X) and f 2 (X) but due to the lack of space, only the results of one approach will be presented. It consists on using in each iteration one objective function (f 1 (X) or f 2 (X)) during the construction phase. The other one is then used during the local search. Then, we alternate between the selected functions for each phase in the next iteration. This approach will allow us to produce diversified solutions of good quality.

IV. PERFORMANCE EVALUATION

A. Model configuration

The different tests were conducted on a typical three-level network that contains 21 nodes forming a perfect 4-ary tree topology where the distance and the latency between each two adjacent nodes are the same. We considered in our experiments a catalog of contents containing 20, 000 1-chunk sized objects whose popularity distribution follows the Zipf's law. Permanent copies of the available contents are hosted on one repository attached to the root node of the network and the users are attached to the network's leaves (i.e. level 1 of the network). We tested different values of the Zipf law's skew parameter α going from 0.8 to 1.2. The parameter β that controls the amounts of greediness and randomness in GRASP was set to 0.5 and the total cache T c is expressed as a ratio of the catalog size. For sake of simplicity, the cache resources are allocated in a way that the nodes located on the same level of the network have the same cache size. Since there are 16 nodes on the first level of the network, P c should be a multiple of 16 and in our case, it was set to 16. Thus, a cache resource placement can be described as X = (x 1 , x 2 , x 3 ), where x i represents the total cache allocated at level i of the network.

B. Model results and analysis

In figure 1, we compare the network's performance metrics of the different cache distribution solutions generated by GRASP (20 iterations) with the Pareto front. We can see from the plots how the solutions produced by GRASP are very close to the set of dominant points in the different tested scenarios, which reflects the good quality of the metaheuristic outcomes.

In Table I, we display the cache allocation solutions generated by GRASP in different configurations (only the results of three iterations of GRASP are shown) using a separate evaluation functions approach. Depending on the Zipf law's parameter α and the total cache resources available T c , different solutions will be generated by GRASP. The choice of the final solutions between the different proposed ones can be based on some constraints that should be respected. For example, if α = 1.2 and T c = 20% and if the priority is to minimize the content provider load (f 1 (X)), then the allocation X = (1952, 1040, 1104) is the best one.

We can see from the exposed different results that there is no absolute solution for the cache allocation problem and it is not a question about whether to cache at the edge or in the core. Depending on the network's configuration and the objectives that one wants to achieve, multiple solutions can be adopted. Other metrics can be used as evaluation functions during the building of the solutions instead of those that we used in this work like for example the financial cost of cache resources deployment. The aim of our proposal is to give a tool capable of efficiently allocating distributed caching resources and versatile enough to adapt to specific desired network performance and constraints.

V. CONCLUSION

We address in this paper the problem of allocating efficiently cache resources in multi-cache networks. We first model it as a multi-objective optimization problem where our analytic tool MACS is used to evaluate the objective functions. Our formulation of the problem turned out to be an NP-hard problem and thus, we propose an adaptation of the GRASP metaheuristic to solve it. The experimental results have showed how the outcomes of our algorithm are very close to the optimal ones. The versatility of our proposal allows it to be applied to any network topology and it can be used with metrics different from the ones used in this paper. We intend in the future to conduct more experiments on the cache allocation problem using our proposal by considering more network performance metrics and testing other caching schemes.

Figure 1 :

 1 Figure 1: Comparison between the Pareto front and GRASP solutions

Table I :

 I Cache allocation solutions using GRASP with a separate evaluation functions approach (Tc = 20%)

	α	X	f 1 (X)	f 2 (X)
		(320,1696,2080)	53.47%	81.78%
	0.8	(768,1376,1952)	54.80%	81.15%
		(736,1280,2080)	53.84%	81.14%
		(1536,1168,1392)	34.39%	62.92%
	1.0	(944,880,2272)	28.57%	63.65%
		(1136,864,2096)	29.54%	63.38%
		(1952,1040,1104)	15.62%	44.00%
	1.2	(1760,2176,160)	19.88%	44.00%
		(1456,720,1920)	12.02%	44.67%


Imad Alawe

Yassine Hadjadj-Aoul

Adlen Ksentini
email: adlen.ksentini@eurecom.fr

Philippe Bertin

Cesar Viho
email: cesar.viho@irisa.fr

Davy Darche
email: §davy.darche@tdf.fr

An efficient and lightweight load forecasting for proactive scaling in 5G mobile networks

Keywords: 5G, Scaling, Mobile Core Network, Prediction, Neural Network, Training

The number of connected devices is increasing with the emergence of new services and trends. This phenomenon is leading to a traffic growth over both the control and the data planes of the mobile core network. It is expected that the traffic will increase more and more with the installation of the new generation of mobile networking (5G) as it offers more services that are intended to be connected over the same network in addition to the legacy ones. Therefore the 3GPP group has rethought the architecture of the New Generation Core (NGC) by defining its components as Virtualized Network Functions (VNF). However, scalability techniques should be envisioned in order to answer the needs, in term of resource provisioning, without degrading the Quality Of Service (QoS) already offered by hardware based core networks. Neural networks, and in particular deep learning, having shown their effectiveness in predicting time series, could be good candidates for predicting traffic evolution. In this paper, we proposed a novel solution to generalize neural networks while accelerating the learning process by using K-mean clustering, and a Monte-Carlo method. We benchmarked multiple types of deep neural networks using real operator's data in order to compare their efficiency in predicting the upcoming network load for dynamic and proactive resource provisioning. The proposed solution allow obtaining very good predictions of the traffic evolution while reducing by 50% the time needed for the learning phase.

I. INTRODUCTION

Mobile networks are facing a traffic load increase over both the data and the control planes due to the explosion of the number of connected devices and the emergence of new trends as the Internet of Things (IoT), and e-Health . . . etc. In fact, the number of devices connected to 5G is expected to reach 28 billions by 2021, in front of 9 billions in 2016 [START_REF] Nordrum | Popular internet of things forecast of 50 billion devices by 2020 is outdated[END_REF].

In the new 5G architecture, the Access and Mobility Function (AMF), the new generation component of the Mobility Management Entity (MME), is likely to be congested since it is the single point of access for the control plane in the core network. Indeed, as shown in [START_REF] Alawe | On evaluating different trends for virtualized and sdn-ready mobile network[END_REF], the overhead causes an increase in latency for the Network Access Stratum (NAS) procedures, up to some requests' rejects when certain load thresholds are exceeded.

Therefore, the 3GPPP group [START_REF]3rd generation partnership project (3GPP)[END_REF] has rethought the architecture of the New Generation Mobile Core Network (NGC) [START_REF]3rd Generation Partnership Project (3GPP)[END_REF], to tackle the issue listed above, by introducing more modular Network Functions (NF) to compose the control plane service, which could also relies on network virtualization via Network Function Virtualization (NFV). Even though, this new architecture offers more flexibility and elasticity, the 3GPP group didn't tackle yet the strategies or the techniques to be used in order to dynamically provision the needed resources while protecting the traffic from any Quality of Service (QoS) degradation.

Resource scaling, when required, is effective when accompanied by a traffic evolution prediction function to avoid not only wasted resources but also quality degradation. Neural networks, and in particular deep learning, having shown their effectiveness in predicting time series, could be good candidates for predicting traffic evolution. Indeed, as neural networks are able to predict the upcoming load, combined with an orchestrator, it will offer dynamic and proactive resources provisioning. However, we still need to determine what kind of neural networks best fit the prediction of Mobile Networking load evolution and how historical data should be formatted in order to give the most accurate results.

In this paper, we analyze the most effective techniques for predicting the traffic evolution of a mobile network. We are particularly interested in the possibility of generalizing prediction techniques to allow them to effectively predict traffic evolution even when the scale of traffic changes. To that purpose, we introduce a novel technique allowing to generalize the neural network while accelerating significantly the training phase using K-mean clustering and a Monte-Carlo method. We apply our technique to three types of neural networks: Recurrent Neural Network (RNN) with Long Short Term Memory (LSTM) cell; Convolutional Neural Network (CNN); and CNN combined with LSTM Neural Network. Finally a benchmark listing the effects of parameters variation (i.e. Number of Clusters, epochs, Number of boosting, etc.) on the prediction efficiency for each of the neural network types listed above. Simulation using TensorFlow library [START_REF] Tensorflow | An open-source machine learning framework for everyone[END_REF] are used to provide the benchmark.

The remainder of this paper is organized as follows. Section II lists and analyses related work on scalability solutions for VNFs and more precisely for mobile core network components. Section III presents the different types of considered neural networks. Section IV describes the proposed solution process from data management to neural network testing. Model evaluation and results analysis are presented in Section V. Finally Section VI concludes this paper and introduces our future work.

II. RELATED WORK

The introduction of the NGC by the 3GPP group provides the flexibility to scale up infrastructure much more easily to respond to increasing traffic loads or even to free up resources in the event of a drop in needs. However, new strategies and techniques should be envisioned for the dynamic scaling of the core network in order to adapt dynamically the infrastructure to the needs.

The most commonly used techniques in the literature are based on fixed thresholds. The idea behind this technique is simple: a scale in process is launched whenever the actual load goes below a fixed "scale in" threshold and a scale up process is launched when the actual load bypass a fixed "scale up" threshold. In [START_REF] Alawe | On the scalability of 5g core network: the amf case[END_REF], we proposed such a solution to manage the congestion that the AMF may undergo with the massive access of IoT devices. Besides, these kind of techniques are widely deployed in many commercial solutions and open-source cloud solutions [7][8].

This type of techniques is rather effective and very simple to implement but can present stability problems. The latter can be a source of degradation of the quality of service making it not suitable for mobile networks. Indeed, deploying, for example, a new VNF may take up to a dozen of minutes depending on the data-center configuration. Thus, the delay between a reactive decision and the scaling process will lead to an increase of the UE attach duration and some requests rejection.

In order to solve the threshold configuration problem, the authors, in [START_REF] Arteaga | An adaptive scaling mechanism for managing performance variations in network functions virtualization: A case study in an nfv-based epc[END_REF], proposed a Reinforcement Learning (RL)based strategy to adapt to dynamic environments and to improve the scaling policy before taking any action following a reward and a penalty process. The authors showed that it behaves better than threshold-based techniques. However as it is a reactive solution, it inherits the drawbacks listed above. In addition, RL may need a considerable time before converging and taking adequate scaling decisions. This is not acceptable in 5G networks due to time constraint of certain type of applications and low latency requirement fixed by the standards.

The authors, in [START_REF] Bilal | Dynamic cloud resource scheduling in virtualized 5g mobile systems[END_REF], proposed a proactive strategy, which consists in forecasting the CPU load of the system based on a historical dataset. Even though this solution is is proactive, it is not adapted for the mobile context as it considers only system level information, like CPU or memory usage. In addition to system level information, service level information should also be taken into consideration while taking scaling decisions as it reflects better the global load of the core network.

In this paper, we propose to forecast the evolution of traffic based on neural networks. The potential variability of telecom network traffic has led us to propose a method to further generalize neural networks so that they can respond correctly to a pattern change. The relearning, in case of a significant deviation in the prediction, also led us to propose a process accelerating the learning. The authors, in [START_REF] Faraoun | Neural networks learning improvement using the k-means clustering algorithm to detect network intrusions[END_REF], worked on accelerating neural networks training using clustering. The main objective of the paper was to use k-mean clustering to reduce data size for the training phase while keeping almost the same accuracy with a shallow neural network. However, the analysis of the results did not go far enough to show the amount of samples needed to converge the classification problem under consideration. Indeed, no clear results was presented on how much the technique can accelerate the training process or even its efficiency. Moreover, in high dimensionality, k-means is not that efficient and the determination of the number of samples remain an open issue. On the other hand, reducing the number of samples results in a loss of information that could severely affect the quality of learning. This is one of the key points that we are improving in this paper by resorting to a Monte-Carlo method.

III. ARCHITECTURE

As mentioned above, the 3GPP group introduced the New Generation Core Network (NGC) in order to answer the requirements of 5G. In what follows, we consider this NGC, in which prediction techniques will have to be introduced to better manage the scaling of resources.

Figure 1 depicts the architecture of the NGC. The 3GPP group decided to introduce the components of the core network as modular functions allowing to benefit from Network Function Virtualization (NFV) to scale in/out depending on the needs as it is now a matter of software deployment.

Even if the technique we are proposing can be applied to different components of the NGC, our proposal, for the moment, targets especially the Access and Mobility function (AMF) as it is the single point of access of the core network. In fact, the control traffic in 5G is expected to increase significantly as the number of connected devices is increasing [START_REF] Alawe | On evaluating different trends for virtualized and sdn-ready mobile network[END_REF].

Thanks to NFV, dynamic scaling issue can be addressed by using machine learning in order to forecast the upcoming load of the core network and, thus, scale in/out resources in Fig. 1: Architecture proposal for 5G a proactive manner to avoid congestion while meeting the 5G requirements in terms of latencies. In addition to NFV, dynamic scaling is now possible as the 3GPP group has split the Mobility and Management Entity (MME), AMF version in 4G, into AMF and Unified Data Management (UDM) entities. Therefore, the AMF function is now stateless as all the User Equipments (UE) contexts and session contexts are hosted in the UDM, adding more flexibility and elasticity to the mobile core network [START_REF]3rd Generation Partnership Project (3GPP)[END_REF]. Indeed, in that case, any user procedure can be handled by any AMF worker.

When a request is received by an AMF instance, the AMF brings the user context from the UDM, using the reference interfaces noted Nx and represented in Figure 1. The AMF processes the request and stores the information and status of the new user context in the UDM.

Based on ETSI's NFV reference architecture, the scalability of a VNF is a decision made by the NFV Orchestrator (NFVO), using information provided by both the Virtual Infrastructure Manager (VIM) and the VNF Manager (VNFM). Therefore, for the sake of simplicity, we have added only one service orchestrator (SO) to the NGC architecture, in this work. As already mentioned, our approach aims to balance the burden between AMF instances and and to scale in/out the AMF functions as required. So the intelligence needed to apply this strategy is located in the SO.

IV. NEURAL NETWORKS TRAFFIC LOAD ESTIMATION FOR RESOURCES' SCALING IN 5G

The prediction of the evolution of a time series, whether periodic or not, has been an active research topic for several years [START_REF] Basterrech | Sensitivity analysis of echo state networks for forecasting pseudo-periodic time series[END_REF]. Several studies, in this sense, have shown the potential of neural networks, and especially LSTM, to identify traffic patterns [START_REF] Gers | Applying lstm to time series predictable through time-window approaches[END_REF].

In this section, we analyze different types of neural networks for predicting load evolution in a network. We use traditional neural networks, CNN and LSTM, but we also suggest a combined architecture of the latter, which not only reduces learning time but also makes it more effective. In addition, we introduce a novel technique, based on the Monte-Carlo method, allowing to generalize the neural network to allow them to effectively predict traffic evolution even when the scale of traffic changes. The proposed technique also has the advantage of making learning much faster thanks to the use of K-mean clustering technique on the data.

A. A combined CNN-LSTM Neural Networks

Before going deeper into the selected neural network architecture, let's start with a brief look at its different components.

1) Convolutional Neural Networks (CNN): A CNN, depicted in Figure 2 (CNN), comprises three main layers. The convolution layer is used to extract features from the input data, while preserving its spatial relationship. Then the nonlinear operation Rectified Linear Unit (ReLu) is applied. Following the ReLU function, spatial pooling (sub-sampling) is applied in order to reduce the dimensionality of each feature map while keeping the most important information. Finally before the output a final fully connected layer is used. This final step will allow to classify the output and to learn nonlinear combinations of the features (refer to [START_REF] Lecun | Convolutional networks for images, speech, and time series[END_REF] for more details).

2) Long Short Term Memory (LSTM): The second neural network used is RNN and more precisely an LSTM cell, which is another type of neural network. Compared to a conventional neural network, an LSTM cell can keep state memory of the last passed activation events in the network as temporal contextual information [START_REF] Hochreiter | Long short-term memory[END_REF][16] (cf. Figure 2(LSTM)). Hence, the advantage of the LSTM cell is to allow data patterns to be stored without degradation over time.

For more details on RNN and LSTM structures and functions, interested readers may refer to [START_REF] Goodfellow | Deep learning[END_REF].

3) A combined CNN-LSTM architecture: In addition to the two types of neural networks explained above, we added another one by combining both types used before. This third type will allow getting improved results by benefiting from the strengths of both the LSTM and the CNN. Indeed, as a an entry we use the CNN in order to extract features (i.e. traffic pattern) and simplify them by using the pooling, which will allow retaining the main part of the pattern. Hence, beside using a fully connected layer as an output layer, we use the LSTM cell in order to forecast the upcoming traffic load. The generalization of neural networks during learning is an important characteristic, since it makes it possible to avoid the phenomenon of over-fitting, which leads to poor performance with new data.

Various techniques have been introduced in the literature to avoid the over-fitting problem. In this paper, we propose a novel approach that has the advantage of significantly accelerating the speed of learning. This technique is particularly effective when predicting time series due to redundancy in the data. The main idea consists first in grouping the data using the K-mean clustering technique.

In the proposed approach, we deal with windows of traffic loads, making the Euclidean distance, which is generally used as a distance metric for the clustering, not very efficient. To that purpose, we propose in this paper using the Dynamic Time Warping (DTW) algorithm [START_REF] Keogh | Scaling up dynamic time warping for datamining applications[END_REF], which is more suitable for time series comparison.

Existing approaches proposed to reduce the size of the initial data after the clustering phase. This speeds up learning but reduces the accuracy of prediction, as only a sub-set of the initial data is used for the training. In contrast with these approaches, we propose to exploit all this data using a Monte-Carlo method.

The proposed solution consists in getting randomly, from each cluster, an element for the training phase, using the function "getRandom()". This process is repeated at each epoch, which allows covering the whole dataset and thus not loosing any precision and accuracy while accelerating significantly the training. Train the neural network with trainset Note that the obtained performance is directly related to the number of clusters nClusters. Indeed, this number must be related to the percentage of data to be considered in each period. The more similarities we have in the input data, the smallest is the number nClusters.

A boost process, in which all the dataset in injected, can also be considered for a number of epochs at the end of the training phase. This phase is efficient only when the number of clusters is too small.

V. MODELS EVALUATION AND RESULTS ANALYSIS A. Dataset

The dataset used in our work contains real mobile data collected by Telecom Italia Big Data Challenge [START_REF] Italia | Telecom italia big data challenge[END_REF] and Fig. 3: Testing data used to test the Neural Networks hosted on Harvard Dataverse [START_REF]A multi-source dataset of urban life in the city of milan and the province of trentino dataverse[END_REF]. This dataset is rich of information. It contains two months of data collected on different Cells of the mobile core network of Mobile Italia in Milano, with a period of 10 minutes. First, the data is sorted following the timestamps and not the cell ids. In other words, for each period of time (10 minutes), we regrouped together the data of all the cells in Milano city. Then, we split the obtained dataset into two datasets: training dataset; and testing dataset. The training dataset will be constituted of 60% of the data and the testing dataset will be filled with the 40%left.

Finally, we decided to add for the testing dataset, a copy of the 40% but doubled, and then also another copy of the 40%. Therefore the testing dataset, illustrated in figure 3, is split into 3 phases: Normal control traffic; an increased (doubled) control traffic; and return to a normal control traffic. By this, in the simulation section we will be testing the precision of the prediction of the neural networks on arrivals where the neural network is not trained for and hence testing it adaptation to traffic load pattern change.

B. Scenario and simulations

In this section we explain the procedure and the simulation launched in order to verify our acceleration proposal as to compare the precision of the neural network predictions. We built the three types of neural networks listed above using the Tensorflow library [START_REF] Tensorflow | An open-source machine learning framework for everyone[END_REF].

In our simulations we decide to test the effects of the number of epochs, the number of clusters, fixed to accelerate the training phase, as the effects of what we will be calling the boost metric. While using our acceleration technique in the training phase, boost technique consists on adding some number of epochs at the end of the training phase where we inject the whole training dataset and not only the clustered data. This test will allow to show if the k means clustering is enough to get the same precision as if we inject the whole data or still a complete re-injection of the training data is still needed.

Thus, for each neural network 3 different types of simulations are launched where in each one we will be varying on metric to see its effect on the prediction precision of the The simulations parameters are listed as following:

• Each entry of the neural network is filled with the last 20 past data in order to predict the 21st one. • The number of clusters is fixed to 30% of the size of training dataset • The number of epochs is fixed to 100 epochs by training phase.

• The number of boost epochs is fixed to 10. Finally, those metrics will be fixed in each simulation type where only the concerned metric of the simulation will be varying in order to understand its effect on the training phase and hence the precision of the prediction as also the training phase duration evolution.

C. Results and Analysis

From Figure 4 (a), we can see the effects of the number of epochs in the training phase for the different types of neural networks as with k means clustering or not and with boost session or not. For all the simulations and the neural networks, it is evident that 25 epochs is not enough to get precise prediction. On the other hand we can see that with clustering technique the precision for each neural network is kind of similar as if there was not data clustering. Thus it shows that applying K means clustering with randomly injection at each epochs allows to get same precision. Also from Figure 4 (b), we can notice that the training time with k means clustering is divide by two comparing to the normal injection of the whole dataset. Therefore K means clustering allows to divide by the the training duration and to keep the same precision as if we inject the whole training dataset. It worth mentioning also that the boost at the end of an accelerated training phase is not so efficient as it does not add any precision to the output. So k means clustering alone is a very interesting solution in order to accelerate the training phase of the neural network.

In the same spirit Figure 5 Also Figure 6 (a), shows the effect of adding some boost epochs at the end of a accelerated training session. We can notice that the boost does not add precision on the neural network precisions. Some time even adds some confusion to the neural network as the distances goes beyond or beneath zero. In the same aspect boost epochs adds some latency to the duration of a training phase as it adds more epochs to the training. Thus boost epochs are not efficient in those use case and using K means clustering alone is better as it gives the desired accuracy while decreasing the training phase duration.

On the other hand from the Figures 4 (a), 5 (a) and 6 (a), we notice that the proposed model including CNN and LSTM is behaving very well and even better than the version of CNN standalone and the LSTM standalone. This is explained by the fact that the CNN is very good in extracting features from the input data and the LSTM is behaving so good in classifying the output.

VI. CONCLUSION

In this paper, we suggested combining a CNN and an LSTM neural networks to predict network loads' evolution. We proposed a novel solution to generalize neural network based on K-mean clustering and Monte-Carlo method. We used real Operator's data in order to evaluate the efficiency of the proposed technique in predicting the upcoming network load for dynamic and proactive resource provisioning. The simulations showed that our solution allows reducing by 50% the duration of the training phase of a Neural Network. In addition, the proposed combined neural network showed clearly its efficiency in predicting the evolution of the considered time series as it performs better than a standalone CNN or a standalone LSTM.

Fig. 2 :

 2 Fig. 2: CNN-LSTM Architecture

Algorithm 1 5 :

 15 Monte Carlo-based training procedure 1: Inputs: epochs, dataset, nClusters 2: Clusters[] = K-mean( nClusters,dataset) 3: for ep in epochs do 4: trainset = [] for clst in Clusters do 6: trainset.add(getRandom(Clusters[clst])) 7:

Fig. 4 :

 4 Fig. 4: Evolution of prediction distance (a) and training phase duration (b) vs number of epochs in training phase

Fig. 5 :Fig. 6 :

 56 Fig. 5: Evolution of prediction distance (a) and training phase duration (b) vs number of clusters in training phase


Pham Tran

Anh Quang

Jean-Michel Sanner
email: jeanmichel.sanner@orange.com

Cédric Morin
email: cedric.morin@b-com.com

Yassine Hadjadj-Aoul

Multi-objective multi-constrained QoS Routing in large-scale networks: A genetic algorithm approach

The growing need for a simplified management of network infrastructures has recently led to the emergence of software-defined networking (SDN), which enables a centralized path calculation. The diversification of services, as well as the need of rapid path deployment, raises, however, challenges in routing algorithms. Moreover, Quality of Service (QoS) requirements and conflicts between them pile up the complexity of the problem. An intuitive method is formulating the problem as an Integer Linear Programming and solving it by an approximation algorithm. This method tends to have a specific design and usually suffers from unacceptable computational delays to provide a sub-optimal solution. Genetic algorithms (GAs) are deemed as a promising solution to cope with highly complex optimization problems. However, the convergence speed and the quality of solutions should be addressed in order to fit into practical implementations. In this paper, we propose a genetic algorithm-based mechanism to address the multi-constrained multi-objective routing problem. Using a repairer to reduce the search space to feasible solutions, results confirm that the proposed mechanism is able to find the Pareto-optimal solutions within a short run-time.

I. INTRODUCTION

In recent decades, we have been witnessing an incredibly fast development of the Internet in both its coverage and traffic load. It unveils dramatic challenges in optimizing and guaranteeing QoS for large-scale networks. One of major components that contributes significantly to the performance of large-scale networks is routing. Routing algorithm is in the core of routing protocol and is responsible for determining the optimal or sub-optimal paths between a source and a destination. A QoS routing algorithm takes QoS and network constraints into account in order to find the optimal path in terms of predefined objectives.

QoS routing plays an important role in QoS provisioning in networks. Depending on the QoS requirements, different QoS routing problems can be defined. Generally, they could be classified into the following five types:

• Shortest path (SP): The route minimizes a unique endto-end metric • Constrained Shortest Path (CSP): The route minimizes an end-to-end metric while maintaining another metric below a given bound. • Multi-constrained shortest path (MCSP): CSP proble m with several end-to-end metrics constrained by prescribed bounds.

• Multi-constrained path (MCP): MCSP problem without end-to-end metric optimization.

• Multi-constrained Multi-objective path (MCMOP): MCP problem with multiple end-to-end metrics to optimize. Both MCP and MCSP are NP-complete if the metrics are mutually independent [START_REF] Kuipers | Bi-directional Search in QoS Routing[END_REF]. MCSP is considered as a modified version of MCP problem and it is more difficult than MCP problem. The solution of MCSP problem is also a solution to the MCP problem, but not vice versa [START_REF] Kuipers | An overview of constraint-based path selection algorithms for QoS routing[END_REF]. MCSP is a special case of MCMOP when there is only one objective, thus MCMOP is also an NP-complete problem. Artificial Intelligent (AI) techniques, e.g. Genetic algorithms (GAs) [START_REF] Lorenzo | Optimal routing and traffic scheduling for multihop cellular networks using genetic algorithm[END_REF], are able to deal with high complexity of routing problems. However, existing genetic algorithms have typically fairly high execution time, thus not well suited for on-line routing decisions [START_REF] Guck | Unicast QoS Routing Algorithms for SDN: A Comprehensive Survey and Performance Evaluation[END_REF].

In this paper, we propose a genetic algorithm that can cope with the high complexity of MCMOP routing problems even in large-scale networks. The rest of this paper is structured as follows. Existing works related to this paper is discussed in Sec. II. A system overview is provided in Sec. III. Sec. IV describes a network model. The proposed genetic algorithm to address MCMOP is presented in Sec. V. Sec. VI provides the performance assessment of the proposed scheme. Finally, conclusions and future research are presented in Sec. VII.

II. RELATED WORKS A. QoS Routing

Several approaches have been proposed in the literature to solve the problem of QoS routing. They could be classified into two main groups: (i) heuristic and (ii) exact algorithm. The authors in [START_REF] Neve | TAMCRA: a tunable accuracy multiple constraints routing algorithm[END_REF] have proposed a tunable accuracy multiple constraints routing algorithm (TAMCRA). It is built upon three fundamental concepts: a non-linear measure of the path length, the k-shortest path approach, and the principle of nondominated paths. The non-linear measure of path length tends to perform well when the path weights are not correlated [START_REF] Kuipers | An overview of constraint-based path selection algorithms for QoS routing[END_REF]. TAMCRA keeps track of up to k-non dominated path for each intermediate node i on the path from a source to a destination. Self-Adaptive Multiple Constraints Routing Algorithm (SAMCRA) [START_REF] Mieghem | Hop-by-hop quality of service routing[END_REF] is an exact variant of TAMCRA. It differs from TAMCRA at the point that it could adapt the number of stored paths at each node. As an exact algorithm, SAMCRA assures that a feasible path is found if one exists.

B. Multi-objective Optimization Genetic Algorithm

Evolutionary algorithms have been exploited to cope with multi-objective optimization problem in [START_REF] Horn | A niched pareto genetic algorithm for multiobjective optimization[END_REF], [START_REF] Srinivasan | Multi-objective function optimisation using non-dominated sorting genetic algorithm[END_REF]. Although they Fig. 1: Proposed GA-based path computation element have proved their abilities in finding multiple non-dominated solutions on many test problems, it is necessary to introduce evolutionary algorithms that have better convergence speed. Elitism is a process that copies the fittest individuals to the next generation. By doing that, the solution quality will not degrade in the next generation and it helps in achieving better convergence [START_REF] Zitzler | Comparison of Multiobjective Evolutionary Algorithms: Empirical Results[END_REF]. The most well-known elitist multi-objective evolutionary algorithm (MOEAs) is Non-dominated Sorting Genetic Algorithm II (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] which outperforms other elitist MOEAs (Pareto Archived Evolution Strategy (PAES) and Strength Pareto Evolutionary Algorithm (SPEA)). However, a number of MOEAs is unable to find well-converged and diversified non-dominated solutions because of the loss of selection pressure in fitness evaluation [START_REF] He | Many-objective evolutionary algorithm: Objective space reduction and diversity improvement[END_REF] in problems with many objectives (more than 3 objectives). Unlike NSGA-II, NSGA-III selects the new population based on supplied reference points. NSGA-III have been demonstrated to work well for many-objective problems [START_REF] Deb | An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints[END_REF].

III. SYSTEM OVERVIEW

The Path Computation Element (PCE) is the module which implements the route computation algorithm. It is a well documented element [START_REF] Farrel | A path computation element (PCE)based architecture[END_REF], that is already used in Multi Protocol Label Switching (MPLS) networks, for example. PCE communicates with its client through the Path Computation Element Protocol (PCEP) [START_REF] Le Roux | Path computation element (PCE) communication protocol (PCEP)[END_REF]. We chose to implement it out of the SDN controller in order to enforce simplicity, encapsulation, security and maintainability. It can implement any kind of routing algorithm, such as Dijkstra or, in our case, a genetic algorithm. We based our implementation on a modified version of the Netphony PCE [15]. Upon receiving a path computation request, the algorithm uses the network image provided by the Traffic Engineering Database (TED) to compute a result. Once this result is found, the PCE modifies the availability of the resources of the TED accordingly. For example, if a path that requests a bandwidth of 1 Mbps is sent through a link A with 3 Mbps available, then the link A will only propose 2 Mbps for the following computations. This strategy allows us to avoid allocating resources multiple time, which may lead to QoS violations. PCE's implementation details are presented in Fig. 1.

IV. NETWORK MODEL

We model a network as a directed graph G = (V, E), where V is the set of nodes and E is the set of directed links. We introduce the binary variable Φ e to index the usage of a directed link e. QoS measures of a link are presented by a vector {w i,e , i = 1, ..., M }, where M is the number of QoS measures. End-to-end QoS measure i of a path is limited by an upper-bound W i . QoS measures can be classified into three different classes: additive, multiplicative, and min-max QoS. Multiplicative measures are able to convert to additive measures by taking the logarithm [START_REF] Mieghem | Concepts of exact qos routing algorithms[END_REF]. For min-max QoS measures, the length of a path is the minimum or maximum of the QoS measures of links forming that path. A filter could be adopted to prune the network by removing the unqualified link. For instance, a video streaming requests a bandwidth of 5M bps, thus a filter will remove all links with capacity less than 5M bps. Meanwhile, path computation with additive routing is more difficult to cope with and it is proved to be NP-complete [START_REF] Wang | Quality-of-service routing for supporting multimedia applications[END_REF]. Consequently, in this paper we consider the cases where the length of a path is composed of additive QoS measures. We have The cost of a path l(P) is a M -dimension vector defined as follow l(P) = [l 1 (P), l 2 (P), . . . , l M (P)] , where l i (P) = e Φ e w i,e . The objective is to find the set of non-dominated solutions (i.e. Pareto optimal).

The aforementioned mathematic model could be solved by the solvers that support multi-objective optimization such as Gurobi [18]. However, the high computational complexity of the problem, especially of large scale networks, causes a high runtime. In the next section, we re-encode this problem in order to solve it using genetic algorithms.

V. GENETIC ALGORITHM

In this paper, extra processes are added into the genetic algorithm in order to guarantee the feasibility of the population and shorten calculation time. Fig. 2 presents the proposed genetic algorithm flowchart. A repairer and a new crossover are added into the genetic algorithm. The set of candidate solutions is called as population. Each candidate solution (individual) is a sequence of bits representing Φ e . In each iteration (generation), the quality of the population could be improved by executing crossover process and/or mutation process. Then, selected parents create the new offspring for the next generation. The following subsections describe the key components of the proposed scheme in details.

A. Initialization

To generate the initial population, links will be selected randomly among all available links. Consequently, they may not be feasible solutions. We decide to work on a search space composed of only feasible solutions, thus it is necessary to correct initial population. A repairer process presented in the next subsection addresses this need.

B. Repairer

This section discusses the proposed repairer, which is able to convert an unfeasible individual to a feasible individual. The repairing process aims to find non-dominated solutions.

Due to multiple QoS measures, a cost of a path is a vector composed of elements corresponding to QoS measures. The Dijkstra shortest path from n to d regarding QoS measure i is Proof. Assume that there is a non-dominated path P * comprising link nn and c n ,d i,i + c n,n i > u n,d i , ∀i. Intuitively, it exists a path from n to d, P 0 , such that c P0 i ≤ u n,d i , ∀i (e.g. any shortest path from n to d). All paths to d consisting of link nn have the QoS measure i greater than or equal to c n ,d i,i +c n,n i since c n ,d i,i is the shortest length in QoS measure i. Consequently, all paths traversing through nn are dominated by P 0 . Therefore, P * could not be a non-dominated path.

Lemma 2. With additive QoS measures, all Pareto-optimal paths are simple paths Proof. A simple path is a path in a graph which does not have repeating vertices. Assume that there is a Pareto-optimal path P * that is not a simple path with a vertex M 0 visited twice. s and d are the source and the destination, respectively. Let us denote the links originated from M 0 in first and second visits as (M 0 , M 1 ) and (M 0 , M 2 ), respectively. Due to additive metrics, we have the cost of P * , c P * , can be determined as the sum of sub-paths (all are simple paths), i.e. c P * = c P s→M 0 + c P M 0 →M 0 + c P M 0 →d , where P s→M0 and P M0→d are the sub-paths from s to M 0 and from M 0 to d (traversing through M 2 ). P M0→M0 is the cost of the loop that traversing through M 0 , M 1 , ..., M 0 . P * is dominated by the simple path P that has the same sub-paths from s to M 0 and from M 0 to d since the total cost of P is c P s→M 0 + c P M 0 →d which is less than c P * . Thus, P dominates P * . It contradicts the assumption, thus all Pareto-optimal paths are simple paths.

Alg. 1 describes the proposed repairer. The input of the repairer could be unfeasible. All active entries in the inputs are stored in the set Ẽ (line 3) and have higher priority to be selected through repairing procedure. For each QoS measure, the repairer finds the shortest path using Dijkstra algorithm (line 4), which is exploited to predict the cost of paths and eliminate dominated paths in later steps. The main loop of repairing process, from line 6 to line 22, in which all relaying nodes from the source to the destination are determined respectively. For each outgoing link from node n, the repairer checks if the remaining bandwidth of the link, b e , is sufficient (i.e. b e ≥ B req ) (line 9). Then, the destination n is checked if it has been visited or belongs to blacklist B (line 11) since the Pareto-optimal path are simple paths as shown in Lemma 2 and there is no feasible path from nodes in the blacklist. The process presented from line 12 to line 15 is to verify if the current link could belong to a non-dominated path following Lemma 1. When the set of candidate links E * is empty, the algorithm backs to the last selected vertex (line 16 and 17). Otherwise, repairing procedure selects a link arbitrarily among common entries of Ẽ and E * to enhance randomness in searching solutions (line 20 to line 21).

C. Non-dominated crossover

Crossover is the process of combining the bits of one parent with those of another, in order to create an offspring that inherits characteristics of both parents. In this section, we present a proposed crossover scheme so as to create offspring that are not dominated by their parents.

We define a crossover point (CP) n i,j of a pair of paths (i, j) as a common vertex of both paths (excluding the source and the destination). A cross over point n i,j divides a path i to two sub-paths P ia n i,j , from source to n i,j (inclusive), and P ib n i,j , form n i,j (exclusive) to d. A non-isolated CP, n i,j , is a CP of paths P i and P j such as P ia (n i,j ) ∩ P jb (n i,j ) = ∅. Meanwhile, an isolated CP of a pair of parents, m i,j , is a CP of paths P i and P j such as P ia (m i,j ) ∩ P jb (m i,j ) = ∅. Note that a non-isolated (isolated) CP n i,j might be not a non-isolated (isolated) CP of (j, i) since it could happen that P ja (n i,j ) ∩ P ib (n i,j ) = ∅ (P ja (n i,j ) ∩ P ib (n i,j ) = ∅). Lemma 3. Given an offspring A formed by a non-isolated CP n i,j , there exists an offspring formed by an isolated CP that dominates A.

Proof. Since n i,j is a non-isolated CP, it means that P ia (n i,j ) ∩ P jb (n i,j ) = ∅. Let us denote C = P ia (n i,j ) ∩ P jb (n i,j ) as the common vertices of P ia (n i,j ) and P jb (n i,j ). Obviously, it exists an isolated CP m i,j ∈ C, and forms two new sub-paths P ia (m i,j ) and P jb (m i,j ). Due to P ia (m i,j ) ∩ P jb (m i,j ) = ∅ and additive QoS measures, c Pia(m i,j ) ≤ c Pia(n i,j ) and c P jb (m i,j ) ≤ c P jb (n i,j ) . Consequently, the offspring formed by (P ia (m i,j ), P jb (m i,j )) dominates the offspring (P ia (n i,j ), P jb (n i,j )).

Alg. 2 presents the proposed non-dominated crossover. The first step is to find common nodes from parents (line 3). Then, the crossover process checks each node in the set of common nodes to see if swapping at a common node can create the offspring that are not dominated by their parents (line 6 to line 13). For each node in the set of common nodes, the crossover algorithm checks whether this node is an isolated CP (line 10 to line 11) since the non-isolated CPs are dominated as shown in Lemma 3. Then, each offspring is compared with two parents (line 12 to line 13). All isolated crossover that forms non-dominated offspring are stored in S 1 and S 2 corresponding to the first and second offspring. Finally, the algorithm returns random offspring among candidates (line 14 to line 15).

The computational complexity of finding common nodes in parents is O(|V| log |V|). The worst case complexity of the process from line 10 to line 11 is O(|V| log |V|). The comparison between offspring and parents has the complexity of O(M ). Consequently, the loop from line 6 to line 13 has the complexity of O(|V| (|V| log |V| + M )). The Algorithm 2: Non-dominated Crossover 1 Input: Linked list of vertices of parents P 1 , P 2 2 Output: non-dominated offspring 3 Find common vertices → V c ; 4 List of swap nodes S 1 , S 2 ; 5 if V c = ∅ then return P 1 , P 2 ;

6 foreach n ∈ V c do 7 P i (n) ← ∅, i = 1, 2 8 P ia (n) ← P i .sublist (s, n) , i = 1, 2; 9 P ib (n) ← P i .sublist (n.next(), d) , i = 1, 2; 10 if P 1a (n) ∩ P 2b (n) = ∅ then P 1 (n) = P 1a (n) ∪ P 2b (n) ; 11 if P 2a (n) ∩ P 1b (n) = ∅ then P 2 (n) = P 2a (n) ∪ P 1b (n) ; 12 if P 1 (n) = ∅ and not dominated then S 1 ← n ; 13 if P 2 (n) = ∅

VI. NUMERICAL RESULTS

In this section, the performance of proposed schemes under different combinations of non-dominated crossover, singlepoint crossover, and mutation will be presented in order to determine appropriate configurations for different scenarios. In single-point crossover, both parents are swapped at a random CP. The new offspring is created by concatenating the first part of one parent with the second part of the other. NSGA-II is the GA algorithm as default. Simulation parameters are presented in Tab. I

We consider different scales of networks: from one to over seven hundreds of nodes. The sizes of networks and shortest distance in number of hops between source and destination are described in Table II. These topologies are referred to the dataset provided by topology-zoo [START_REF]The internet topology zoo[END_REF] with real latency so as to keep the assessments practical. For GAs, we consider different combinations of proposed modules: Non-dominated crossover and mutation (NDC-M), Single-point crossover and mutation (SP-M), Non-dominated crossover only (NDC), and Mutation only (M). For NDC, it is unnecessary to execute repairing process after crossover since the offspring is a feasible solution, therefore reducing computational complexity. The conventional SAMCRA (SCR) defines the length as the maximum of ratios of metrics and their upper-bounds. Consequently, the output of SCR is not a Pareto-optimal solution. To derive Pareto-optimal solutions, we define the length as a vector of ratios instead of a linear or non-linear function. This modified SCR with Look-ahead feature, denoted as SAMCRA-LA-MO (SCRM), is used as reference since its output is the Pareto optimal solution. The hypervolume (HV) of a set of solutions S is the volume of objective space dominated by the set, limited by a given reference point. In other words, the greater HV means the better solutions. The normalized HV is defined as follows NHV = HV GA HV SCRM , where HV SCRM is the HV of SCRM which is the optimal solutions and HV GA is the HV of GA-based solutions. The normalized HV (NHV) expresses how good the GA-based solutions are. We evaluates the performance of the proposed GA scheme by NHV, QoS-metrics, and calculation time.

Comparisons of four configurations in terms of NHV and calculation time are shown in Fig. 3 and Fig. 4. Even though the population size and the number of generations are small (20 and 120, respectively), the normalized HVs are over 80% in all cases. It means that the GA-based solutions are near to the optimal solutions. The performances of all configurations in most cases (except Kdl) are similar to each other. There are noticeable gaps between NDC and other configurations in Kdl scenario. It is because the missing of mutation and small population limits the capability of finding a Pareto optimal solution of NDC, especially in large network such as Kdl. However, the calculation time of NDC is shortest due to its simplicity. The gap in calculation time is proportional to the networks' complexity, since the repairing processes of high complex networks requires more calculation time. By deploying mutation, the combination NDC-M has the better performance. Nevertheless, the performance of NDC-M is similar to SP-M and M while it requires noticeable extra run-time. The solutions of Kdl-NDC-M is near to the optimal solutions; however, they do not cover all Pareto Front. That explains the lower normalized HV in Fig. 3. Fig. 6 presents the calculation time of the proposed mechanism, and SCRM. The calculation time of SCRM is similar to SP-M when the sizes of networks is small or moderate. However, the calculation time of SCRM is much greater than the proposed mechanism in a large-scale network scenario, e.g. Kdl. As a result, the implementation of SCRM in large-scale networks could be impractical. The proposed mechanism can offer similar normalized HV as shown in Fig. 3

VII. CONCLUSIONS

Multi-objective QoS routing is one of major challenges in networking. We proposed an efficient GA-based routing to cope with Multi-objective QoS routing by introducing the repairer concept and the non-dominated crossover operator. We confirmed the gain of the proposed mechanism through intensive simulations. A comprehensive study on how to control parameters so as to balance between calculation time and the quality of solution will be considered in future. Furthermore, we intend to extend this approach to a broader category of problems where path computation takes part, like VNF chains placement problem. For reducing computation time, multi-objective evolutionary algorithms that enable fully parallelization will be considered in future.

eΦ

  e w i,e ≤ W i , ∀i. The objectives are to minimize all QoS measures min e Φ e w i,e , for i = 1 . . . M .

Fig. 2 :

 2 Fig. 2: Proposed Genetic Algorithm Flowchart

Algorithm 1 :; 5 V 7 E * ← ∅; 8 foreach e originated from n do 9 if 12 foreach QoS measure i do 13 uE * ← e and break; 16 if E * = ∅ then 17 B 21 else

 157891213161721 Repairer 1 Input: An unfeasible path from S to D 2 Output: A feasible path from S to D 3 foreach active bit of the input do Ẽ ← e ; 4 foreach QoS measure i do Run Dijkstra for QoS measure i → c n,d i * ← s, n ← s, and B ← ∅; 6 while n = d do b e < B req then continue ; 10 n ← Dest(e); 11 if n ∈ V * ∪ B then continue ; ← B ∪ {n}, n ← last entry in V * ; 18 if n = s then continue; 19 else break;; 20 if E * ∩ Ẽ = ∅ then Select e from E * ∩ Ẽ randomly ; Select e among entries in E * randomly ; 22 n ← Dest(e) and V * ← V * ∪ {n}; 23 return V * ; The worst case complexity of the code in line 11 is O(log |V|) and it is O(M ) for the code from line 12 to line 15. Consequently, the overall worst case complexity of the main loop of repairing procedure (line 6 to line 20) is O(|V| 3 (M + log |V|)). The complexity of Dijkstra algorithm (line 4) is O(M |E| log |V|). Note that this loop can run once and reused for all individuals. Meanwhile, the main loop has to be executed for each individual.

Fig. 3 :

 3 Fig. 3: Normalized Hypervolume with 2 QoS metrics

Fig. 4 :Fig. 5 :

 45 Fig. 4: Calculation time when there are 2 QoS metrics

Fig. 6 :Fig. 7 :Fig. 8 :

 678 Fig. 6: Calculation Time of SCRM vs GAs with 2 QoS metrics

  and not dominated then S 2 ← n ; 14 Select node n * 1 in S 1 randomly → OffSpring1 = P 1 (n 1 ); 15 Select node n * 2 in S 2 randomly → OffSpring2 = P 2 (n 1 ); 16 return OffSpring1 and OffSpring2;

	Parameters	Value
	Population size	20
	Number of generations	120
	QoS metrisc	Loss rate and Latency
	Loss rate	0.01% -0.1% [19]
	Number of runs per scenario	30
	Confidence interval	95%
	Simulation Environment	Intel Core i5-6300U, 8GB RAM
	Genetic algorithm framework	jMetal [20]

TABLE I :

 I

Simulation parameters overall complexity of non-dominated crossover procedure is O(|V| (|V| log |V| + M )).

TABLE II :

 II Topology parameters

	Kdl	Colt	GtsCe UsCarrier Deltacom

  within 1s. Above simulations confirm the performance of proposed

	10 3
	10 2
	Kdl	Colt	GtsCe UsCarrier Deltacom