{'fraction_non_alphanumeric': 0.022638629811768694, 'fraction_numerical': 0.004663388163472952, 'mean_word_length': 5.134980494148245, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Machine Learning for Performance-Aware Virtual Network Function Placement

With the growing demand for data connectivity, network service providers are faced with the task of reducing their capital and operational expenses while simultaneously improving network performance and addressing the increased connectivity demand. Although Network Function Virtualization (NFV) has been identified as a solution, several challenges must be addressed to ensure its feasibility. In this paper, we address the Virtual Network Function (VNF) placement problem by developing a machine learning decision tree model that learns from the effective placement of the various VNF instances forming a Service Function Chain (SFC). The model takes several performance-related features from the network as an input and selects the placement of the various VNF instances on network servers with the objective of minimizing the delay between dependent VNF instances. The benefits of using machine learning are realized by moving away from a complex mathematical modelling of the system and towards a data-based understanding of the system. Using the Evolved Packet Core (EPC) as a use case, we evaluate our model on different data center networks and compare it to the BACON algorithm in terms of the delay between interconnected components and the total delay across the SFC. Furthermore, a time complexity analysis is performed to show the effectiveness of the model in NFV applications.


I. INTRODUCTION
In recent years, the fast-paced increase in the number of data-producing connected devices has put an incredible burden on Network Service Providers (NSPs) worldwide. One of the main challenges currently facing these NSPs is delivering a continuous and quality service while simultaneously addressing the increasing connectivity demand. It is estimated that by the year 2022, the number of connected devices will greatly exceed the global population by a factor of three [1]. Furthermore, the spike in devices will also contribute to a significant increase in the amount of Internet Protocol (IP) traffic worldwide [1].
In order to cope with these challenges and the burden on the system, NSPs need to adapt their networks to enable increased flexibility, scalability and portability. Network Function Virtualization (NFV) has been proposed as a solution to these challenges. The goal of NFV architecture is to isolate the network functions from their underlying hardware and execute them as software-based applications on servers and in data centers [2]. Several potential benefits arise from the implementation of NFV architecture including a reduction in capital and operational expenditures, decreased time to market for new technologies, service testing and implementation efficiencies, network topology optimization, optimized energy consumption, and increased operational efficiencies [3]. However, there are challenges associated with these benefits that must be solved in order to experience the full potential and power of this technology.
NPSs worldwide are held to certain standards when providing a service to a customer. Quality of Service (QoS) requirements take into consideration metrics such as packet loss, jitter, transmission delay, and availability. The QoS guarantee is an NSPs acknowledgement of and adherence to these requirements. When considering the implementation of NFV architecture, QoS guarantees are of paramount importance and consideration. Therefore, violating these requirements jeopardizes the implementation of NFV technology in current networks.
Performance, being a key metric of QoS, plays a major role in the successful implementation of NFV architecture. While the performance of an individual VNF instance is important, the performance of an interconnected and interdependent group of VNF instances known as a Service Function Chain (SFC) is paramount. SFCs are the end goal of NFV enabled networks. In order to provide an end-to-end service, several VNF instances of different types should be accessed in a specific order, thus creating an SFC.
An example of an SFC is the Evolved Packet Core (EPC) which is a network infrastructure that supports the converging on licensed and unlicensed radio access technologies through IP [4]. Virtual EPC (vEPC) is a solution introduced by 3GPP to harness the full potential of radio access technologies [5]. In this technology, there are four main types of VNFs: the Home Subscriber Service (HSS), the Mobility Management Entity (MME), the Serving Gateway (SGW), and the Packet Data Network Gateway (PGW). Fig. 1 outlines the architecture of this technology. EPC was selected as a use case since it is one of the candidate network entities for virtualization.
As with any SFC, vEPC is subject to QoS guarantees including performance, reliability, and availability. When considering a VNF-enable network, the placement of each of the VNF instances forming the SFC directly impacts these requirements. When the initial placement of VNF instances is being conducted, the NFV orchestrator must take into consideration, among other things, the delay requirements of each SFC when placing the VNF instances. Furthermore, an intelligent orchestrator may use machine learning in order to learn from previous placements to predict the placement of future VNF instances such that the delay between interdependent components is reduced.
The work outlined in this paper presents the use of machine learning algorithms in the NFV orchestrator to predict initial VNF instance placement in a network while taking into consideration QoS guarantees. Our work is conducted using the EPC infrastructure as a use case and can generalize to any SFC type. The BACON algorithm is a near-optimal placement algorithm that considers the minimization of the delay between dependent VNF instances and across the overall SFC [6]. This algorithm is used to assess the performance of our model. The results show that the machine learning algorithm can learn from effective previous placements, QoS requirements, network conditions, and other operational constraints and translate them into elements of intelligence to predict placements while minimizing delay.
The remainder of this paper is structured as follows. Section II presents related work in the field of VNF placement and machine learning. Section III outlines the methodology. Section IV describes the implementation and discusses the obtained results. Finally, Section V discusses opportunities for future work and concludes the paper.

II. RELATED WORK
The following outlines some of the work being done in the field related to the use of machine learning in VNF provisioning, allocation, and function placement.
Khezri, et al. [7] propose a dynamic reliability-aware NFV service provisioning solution that incorporates a deep Qlearning network. Zhang et al. [8] propose an intelligent cloud resource management framework that encompasses both deep and reinforcement learning. Xu et al. [9] propose an application-aware VNF deployed on a GPU server that analyzes packets and classifies their application type using a deep neural network. Sun, et al. [10] propose a dynamic SFC deployment strategy using Q-learning. Riera et al. [11] suggest the use of reinforcement learning to solve the service mapping problem.
All of the works presented above aim at solving the problem of VNF resource allocation or placement using machine learning techniques. The objective of each of the aforementioned papers often relates to the constraint of delay, resource, and QoS guarantees or any combination thereof. Our work differs from the works above as it considers the minimization of delay across dependent VNF instances and the entire SFC while simultaneously addressing performance and QoS requirements.
The previous work of Hawilo et al. [6] outlines the use of a heuristic model to calculate the near-optimal placement of VNF instances forming a service chain that minimizes the delay between two dependent VNFs. Building off of their previous work, this paper implements a machine learning model, which learns from the previous placements performed by an adaptation of the aforementioned heuristic in order to minimize the delay between future placements of dependent VNF instances. Considering the delay between dependent components is essential for maintaining service performance.
The major contributions of this work can be summarized as follows: a) The implementation of a machine learning model to identify the best placement of dependent VNF instances forming an SFC. b) The implementation of a machine learning model that learns from previous effective placements when deciding the servers for future placements. c) The implementation of a machine learning model that learns operational constraints when selecting the best server that meets QoS requirements.

III. METHODOLOGY
The following section will discuss the methodology behind our work including the motivation, the generation of the dataset, and the advantages of using a machine learning solution.

A. QoS Requirements
Usually, as a way of creating a more resilient system that is less susceptible to failure, several instances of the same type are located throughout the network. This introduces the concept of computational paths [6] which essentially indicates the number of different routes network traffic can take to traverse an SFC. Fig. 2 illustrates this concept by showing various paths between interdependent VNF instances forming an SFC. For a computational path to be successful, the selected servers hosting the VNF instances should meet their computational needs and ensure the delay tolerance between interdependent VNF instances is not violated. However, the QoS requirements address much more than simply the computational and delay requirements of the SFC. Further consideration must be taken to include the availability and dependency constraints that ensure the SFC is resilient to unexpected changes in the network and traverses the VNFs in the correct order.

B. Dataset Generation
The dataset used to train the machine learning model is generated by using an adaptation of the BACON algorithm presented by Hawilo et al. [6] to place VNF instances. The algorithm is selected for its ability to achieve near-optimal placement with significantly decreased computational complexity compared to the Mixed Integer Linear Programming model. The objective of the optimization model is to minimize the delay between two dependent VNF instances forming an SFC. The dataset contains placements from two network layouts.
The first network represents a small-scale network with 15 servers and 6 VNF instances while the second network represents a medium-scale network with 30 servers and 10 VNF instances to place. The parameters of the network include server-to-server delay, server resources, VNF instance resource requirements, and VNF instance delay tolerances. They are all generated following the structure of a three-tier data center. The instances are then placed using the aforementioned BACON algorithm yielding the near-optimal placement [6]. This is conducted 10,000 times for each network, resulting in the placement of the VNF instances given the respective trial's network conditions. TABLE 1 lists the components of the two network models evaluated.

C. Advantages and Benefits of Machine Learning Based NFV Placement Algorithms
In conventional, model-based networks, mathematical modelling is used to describe the system's behaviour however, this approach is subject to several limitations [12]. Firstly, developing an all-encompassing statistical network model has become challenging as network complexity continually increases. Furthermore, NSPs are often faced with the task of solving NP-Hard problems (ex. NFV Resource Allocation Problem, VNF Placement Problem, etc.). The solution to these problems is computationally expensive and often requires the use of sub-optimal heuristics to achieve a solution in a feasible amount of time. Another concern with model-based networks comes from the notion of problem decomposition whereby a parent problem is split into smaller child problems which are individually solved. Finding an optimal solution to a child problem does not always inherently result in the optimal solution of the parent problem [12]. As a method of mitigating the aforementioned limitations of model-based networks, an alternate data-based framework leveraging the use of machine learning has been suggested as a solution [12]. Data-based networking moves away from rigid mathematical modeling and instead learns a model through the data generated from the network. By learning from the data directly, several benefits arise. Firstly, an exact mathematical model capturing every element of the system is not required to describe the behaviour of the system as this is inherently learned through the direct processing of the generated network data. Additionally, as network complexity increases and changes are made, the new data generated will provide the grounds for the learning of the new system behaviour.
Perhaps the greatest advantage of the use of machine learning in data-based networks is the reduction of the computational complexity of the system. The operation of a machine learning algorithm can be divided into the training and implementation phases; the training phase, containing most of the computationally intense processes of the algorithm, can be completed offline allowing for the implementation phase to be executed during runtime. This is a major improvement over the use of complex optimization models which are computationally intensive as their complexity often scales with network parameters and is often inadequate during runtime [12].
When considering the requirements of the incoming 5G network technology (self-configuration, self-optimization, and self-healing), machine learning is a natural candidate technology [13]. Due to the variety of algorithms available, machine learning can have a wide range of functionalities in future networks (classification, forecasting, clustering, etc.) to solve challenges currently faced by NSPs including resource allocation, performance, security, resilience, energy efficiency, and traffic management [14].

D. Machine Learning Model
The features extracted from the previous dataset generation stage include resource requirements for the VNF instances, resource capacity of the network servers, the delay between servers, delay tolerance between dependent VNF instances, and component dependency. These metrics are used to predict the placement of each of the VNF instances on one of the network's servers. The machine learning model here can be treated as a multi-output, multi-class classification problem as there is a prediction for each of the VNF instances (multioutput) and each prediction selects a server from the set of network servers (multi-class).
Due to the nature of the problem, two approaches are evaluated, neighbour-based algorithms and tree-based algorithms. These two families of algorithms are selected for their ability to address the multi-class, multi-output requirement, something which many learning algorithms are unable to do due to the inherent complexity of the solution [15]. After training the model and performing a 10-fold cross-validation test, it is determined that the tree-based algorithms are the best performing family of algorithms specifically the decision tree algorithm.
The building of the decision tree follows a top-down approach starting with the root node. The goal of the tree is to purify the nodes by increasing the homogeneity of their associated samples. There are two main metrics used to assess the purity of the node, Gini index (1) and entropy (2) where the probability p mk is the proportion of class observations at a given node [15]. The proposed decision tree uses the optimized Classification And Regression Tree (CART) algorithm [15]. This algorithm uses the Gini index by default for evaluating node purity.
When initially constructing the tree, the Gini index of all features with respect to the output label is calculated. The feature with the lowest Gini index has the most purity and therefore is selected as a root node. Once the root node is selected the dataset is split into subsets depending on the feature values using thresholding. The Gini index of each of the features in each respective subset is then calculated and the lowest is selected as a branching attribute. This process is completed until homogenous leaf nodes (pure) are achieved or the maximum depth of the tree is reach. Since decision trees are prone to overfitting when dealing with large quantities of data, the maximum depth of the tree is set, essentially limiting the tree's ability to expand vertically, and 10-fold cross-validation is used to further ensure overfitting does not occur during the training phase.
By using the data generated from the previous placement of VNF instances we create a data-driven network model whereby the algorithm is responsible for determining and extracting the inherent relationships from the data. Using this method, the complex mathematical modelling of the system is bypassed, however, as demonstrated in the results section, the algorithm has learned from the training phase and is able to predict placement that approaches and outperforms the results obtained from the heuristic.

E. Time Complexity
When comparing the computational complexity of the two methods, the Delay Aware Tree (DAT) method exhibits a computational complexity O(n f eatures · n samples · log n samples ) when creating the tree and O(log n samples ) when executing a query [15]. The original algorithm has a computational complexity of O( s 3 −s 2 2 ) where s denotes the number of available servers in the network [6]. Comparing these two complexities, we can see that during runtime, the DAT method would operate at a lower complexity since its initial training phase would have already been completed and it would simply need to execute the query request.

IV. ALGORITHM PERFORMANCE COMPARISON
In order to evaluate the results of the machine learning model, it is compared to the BACON algorithm [6]. The performance is measured by calculating the delays between interconnected VNF instances once the placement is made. Furthermore, the overall delay of each computational path is also calculated.

A. Implementation Setup
The generation of the dataset is executed in Java while the data processing and machine learning models are implemented using Python. Both the generation of the dataset and the model implementation are run on a PC with an Intel © Core™ i7-8700 CPU @ 3.20 GHz CPU, 32 GB RAM, and an NVIDIA GeForce GTX 1050 Ti GPU.

B. Results
The results of the simulations are displayed below. In terms of the small scale 15 server network Fig. 3 displays the delay between the various interdependent VNF instances. Fig. 4 presents the overall SFC delay across the 4 computational paths previously discussed. As seen from these results, it is clear that the Delay Aware Tree (DAT) placement model has learned well from the near-optimal placement of the BACON algorithm. When comparing the delay between the interconnected VNF instances, DAT shows very good performance as the delays observed are very close to the delays observed through BACON's placement. In this case, it can be seen that DAT performs slightly better than BACON for the first two paths and slightly worse for the last two paths. Fig. 5 shows the PDF of the difference between the delay of the computational paths using BACON and DAT. The mean of the distribution suggests that across all computational paths, BACON has on average 34μs less delay compared to DAT. However, the left tail of the distribution greatly skews the mean through outliers. By optimizing the model hyper-parameters the overall performance of a machine learning algorithm improves [16]. By improving the performance of DAT through hyper-parameter optimization, the mean of the distribution will shift further towards the positive side and the tails of the distribution will be suppressed. Fig. 6 displays the delay across the 36 computational paths in the medium 30 server network. As seen in the figure, DAT continues to perform well despite the increase in network size. Assuming a maximum allowable delay is imposed at 2000μs we can see that DAT successfully produces more computational paths that don't violate this threshold thereby increasing the resiliency of the network.

C. Hyper Parameter Optimization
When considering the CART algorithm, there are four main hyperparameters: tree depth, minimum sample split, minimum sample leaf, and the maximum number of features considered. The work of Mantovani et al. [17] deals with the tuning of decision tree hyperparameters across several datasets. Results of their work suggest the min samples split and the min samples leaf parameters are the most impactful on a model's predictive success.
Given the set of hyperparameters h, the set of objectives f , and the importance vector of each objective expressed Fig. 5. Delay Difference between BACON and DAT per Computational Path through the set of weights w, we can consolidate the multiobjective optimization problem into a single objective function O [18]. The evaluation criteria E is an expression of the consolidated objective function, the model trained with the set of hyperparameters h, the training set T s and the validation set V s [17] Assuming E is formulated as a cost function, the optimization problem when implementing a k-fold crossvalidation is the minimization of P (h).
Objective : The hyperparameter optimization of the decision tree model was not considered in this work; it will, however, be considered in future work.

V. CONCLUSION
The work presented in this paper describes the first step towards an implementable, intelligent, and delay-aware VNF placement strategy for the NFV Orchestrator. Future work relates to the improvement of the current model. In terms of model improvement, hyperparameter optimization will occur using the method previously outlined. When performing this optimization, care must be taken to prevent over-fitting, something which plagues large decision trees and hinders predictive accuracy. Furthermore, a model will be built for a large data center network with a significant increase in the number of available servers and VNF instances. Additionally, the computational complexity of building the decision tree is dependent on the number of features, dimensionality reduction techniques will be used to improve the time required to train the model.
In order to deal with the rising costs of operating networks and the new challenges facing NSP due to the rapid increase in connectivity demand in data-dependent devices, NFV has been introduced as a solution. By abstracting the network function from the underlying hardware, we are able to move away from proprietary hardware and move towards a more portable, flexible, and scalable network model. These benefits, however, give rise to new challenges including the implementation of a network model that can adhere to QoS requirements. The work presented in the paper successfully implements and trains a delay-aware decision tree model, DAT, which is able to learn the near-optimal placement of VNF instances forming an SFC. When compared to the original placement algorithm our model exhibits comparable performance and in certain metrics outperforms the initial BACON algorithm.