Omar Houidi
email: omar.houidi@telecom-sudparis.eu

Oussama Soualah
email: oussama.soualah@telecom-sudparis.eu

Wajdi Louati
email: wajdi.louati@redcad.org

Marouen Mechtri
email: marouane.mechteri@orange.com

Farouk Kamoun
email: frk.kamoun@planet.tn

An Efficient Algorithm for Virtual Network Function Scaling

Keywords: Network Functions Virtualization, VNF Scaling, Migration

Network Functions Virtualization (NFV) has been revolutionizing and improving the way networking services are deployed but also requires the dynamic scaling of resources during the lifecycle management of Virtual Network Functions (VNFs) with increasing service demand. We propose an Integer Linear Programming (ILP) approach and a Greedy heuristic to address this NP-Hard scaling problem. Both horizontal (scale out/in) and vertical (scale up/down) scaling are considered and the scalability of the ILP is addressed by reducing the number of candidate hosts in the search space. Extensive simulations evaluate the performance of the algorithms in successful scalings and VNF migrations and highlight the importance of using the algorithms to tidy up the infrastructure to accept more users. The results show that the ILP can outperform the Greedy heuristic if appropriate actions are selected.

I. INTRODUCTION

Network Functions Virtualization (NFV) has emerged as an innovative concept to reduce cost, improve flexibility and accelerate service deployment for network providers by decoupling functions (such as NATs, firewalls, load balancers, DNS...) from dedicated hardware and moving them to virtual servers. The SNS Telecom report [START_REF]SNS Telecom, The SDN, NFV & Network Virtualization Ecosystem: 2016 -2030 -Opportunities, Challenges, Strategies & Forecasts[END_REF] estimates that service provider SDN and NFV investments will grow at a Compound Annual Growth Rate (CAGR) of 46% between 2016 and 2020. As service providers seek to reduce costs and virtualize their networks, these investments will eventually account for over $18 Billion in revenue by the end of 2020.

In NFV based environment, one of the most important challenges for providers is to efficiently allocate hosting resources to dynamic virtualized network services demands while increasing revenue. Elastic mechanisms and scaling algorithms are essential to improve adaptation and deployment of Virtual Network Functions (VNFs) in NFV infrastructures to support increasing traffic load and customer demands.

As introduced in [START_REF]Network Functions Virtualisation (NFV); Predeployment Testing; Report on Validation of NFV Environments and Services[END_REF] and [START_REF] Ghaznavi | Elastic virtual network function placement[END_REF], Virtual Network Function scaling is triggered by new client requirements and/or rising traffic load due, for example, to an increase in the user plane traffic or the need of allocating more resources to a VNF to avoid service interruption.

To enhance initial VNF placement with dynamic adaptation, three scaling mechanisms are defined in [START_REF] Ghaznavi | Elastic virtual network function placement[END_REF] and [START_REF] Galante | A survey on cloud computing elasticity[END_REF]: i) Horizontal scaling (scale out/in): Add/remove virtualized resources (e.g., VNF Components (VNFCs)), ii) Vertical scaling (scale up/down): Reconfigure the capacity/size of existing virtualized resources and iii) VNF migration.

To address this NP-Hard elasticity problem [START_REF] Xia | Optimized virtual network functions migration for NFV[END_REF], we propose an exact algorithm and a Greedy heuristic. An Integer Linear Programming (ILP) formulation with a search space reduction is adopted to improve scalability. A Greedy algorithm searching for a scaling solution in the neighborhood of initial placement is also presented. Comparisons between the two approaches show that an adequately tuned and devised ILP can outperform Greedy solutions in terms of proportion of successful scalings.

Section II of this paper presents the related work. The system model is described in Section III. The proposals are introduced in Section IV. Section V reports the performance evaluation results.

II. RELATED WORK

We review the VNF scaling problem with emphasis on the dynamic expansion and adaptation of Virtualized Network Function-Forwarding Graphs (VNF-FGs). A VNF-FG corresponds to a set of networked VNFs providing chained network services with specified traffic steering and flow paths. The review covers consequently the related work on VNF-FG placement and related work on VNF adaptation and configuration through scaling and migration. Prior work on Virtual Network Embedding (VNE) adaptation using migration and scaling is also included in the presentation for completeness.

VNF-FG placement and chaining was formulated and solved as a Integer Linear Programming in [START_REF] Bari | On orchestrating virtual network functions in NFV[END_REF], [START_REF] Gember | Stratos: A networkaware orchestration layer for middleboxes in the cloud[END_REF], [START_REF] Moens | VNF-P: A model for efficient placement of virtualized network functions[END_REF], and [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF]. These methods are efficient in finding exact solutions but are subject to combinatorial explosion and do not scale with problem size. Heuristic algorithms are typically proposed to scale better with problem size. A baseline Greedy algorithm [START_REF] Mechtri | Vnf placement and chaining in distributed cloud[END_REF], using a bipartite graph construction and matching techniques, for VNF-FG placement and chaining, solves the problem in two steps: first mapping VNFs on physical hosts and second steering inter-VNF traffic across the hosts. In all these previous works, VNF scaling and migration are not considered to address increasing requirements and load on network functions and hosting resources.

Migration has been used in the VNE context. Several dynamic algorithms using reconfiguration optimize substrate resources for virtual networks. Authors of [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] propose a path migration algorithm for reconfiguring and rerouting virtual links, unfortunately do not consider adaptation of the virtual nodes and thus find suboptimal solutions. An iterative algorithm, called Virtual Network Reconfiguration (VNRe), is presented in [START_REF] Fajjari | VNR Algorithm: A Greedy Approach For Virtual Networks Reconfigurations[END_REF] to ensure load balancing among substrate nodes and reduce the rejection rate caused by congested substrate links. In [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], the authors propose an adaptive optimization algorithm which selects only critical VN requests for reconfigurations. Despite this selection of most critical VN requests, computational cost and service disruptions remain important at large scale. The more important body of work on scaling and migrating services in VNE is not directly applicable to the VNF-FG placement problem. VNE and VNF graph placement are distinct and have different characteristics [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF], [START_REF] Moens | VNF-P: A model for efficient placement of virtualized network functions[END_REF], [START_REF] Guerzoni | A novel approach to virtual networks embedding for SDN management and orchestration[END_REF]. VNE requests are modeled by simple undirected graphs while VNF chains are more complex and contain both the VNFs to place and the traffic flows to steer between the VNF-FG end points.

Few works address virtual network function scaling and migration to ensure dynamic VNF chain placement for rising demand and traffic load. Authors of [START_REF] Ghaznavi | Elastic virtual network function placement[END_REF] propose a consolidation algorithm called Simple Lazy Facility Location (SLFL) that optimizes the placement of the VNF instances in response to on-demand workload. SLFL chooses the VNF instances to be migrated on the basis of the instantaneous reconfiguration but does not assess the impact (induced benefits or penalties) of these decisions on future instants.

Bandwidth guaranteed VNF placement and scaling in Datacenter is considered in [START_REF] Wang | Bandwidth guaranteed virtual network function placement and scaling in datacenter networks[END_REF]. Leveraging the tree-like topology of Datacenter networks, this work proposes an on-line heuristic algorithm that achieves a near optimal allocation. Note that these two cited approaches do not take into account migration cost. In [START_REF] Xia | Optimized virtual network functions migration for NFV[END_REF], authors proposed an Integer Linear Programming (ILP) model to solve the network function migration problem. In the rest of the paper, we denote this competitor algorithm by (ILP C) that proposes a migration cost model and a heuristic algorithm to decrease the migration cost. Note that these algorithms do not consider scaling and elasticity to optimize resource utilization.

We address in this paper, through an ILP solution, the tradeoff between cost and performance when using VNF instances scaling and migration to adapt virtualized network functions graphs to increasing demand and workload.

III. PROBLEM FORMULATION

This section models the VNFs and the VNF-FG scaling problem and derives an ILP solution that ensures placement and scaling for increasing demands with minimal cost and service interruptions.

A. Substrate and virtual networks models

The physical network (commonly known as substrate and physical infrastructure and use interchangeably), as defined by the ETSI NFV Infrastructure (NFV-I) [START_REF]Network Functions Virtualisation (NFV); Use Cases[END_REF], is modeled as an undirected weighted graph, denoted by 𝐺 𝑝 =( 𝑁 𝑝 ,𝐸 𝑝 ) where 𝐸 𝑝 is the set of physical links and 𝑁 𝑝 is the set of physical nodes. Each substrate node, 𝑘 ∈ 𝑁 𝑝 , is characterized by its i) available processing power (i.e., CPU) denoted by 𝐶𝑃𝑈 𝑘 , and ii) type 𝑇 𝑘 : switch, server or Physical Network Function (PNF) [START_REF] Etsi Gs | Network Functions Virtualisation (NFV); Terminology for Main Concepts in NFV[END_REF], where PNFs are the traditional physical middleboxes offering network functions. A PNF is a dedicated hardware that implements a network function. Each virtual link (i.e., 𝑒 ∈ 𝐸 𝑝 ) is characterized by its available bandwidth 𝐵𝑊 𝑒 .

A client request (i.e., requested service function chain) is modeled as a directed graph 𝐺 𝑣 =(𝑁 𝑣 ,𝐸 𝑣 ) where 𝑁 𝑣 is the set of virtual nodes and 𝐸 𝑣 is the set virtual links in the graph. Each virtual node, 𝑖 ∈ 𝑁 𝑣 , is characterized by its i) required processing power 𝑐𝑝𝑢 𝑖 and ii) its type 𝑡 𝑖 : VNF or switch (i.e., ingress or egress). Each virtual link (𝑖𝑗) ∈ 𝐸 𝑣 is described by its required bandwidth 𝑏𝑤 𝑖𝑗 . Note that the VNFs can be hosted only into server or PNFs having the same type. The ingress and egress nodes can be hosted only into switches. Before the expiration of a tenant or user VNF-FG lifetime, the resources requirements of the VNFs in the forwarding graph can increase with rising demand. This will entail the spawning of new VNF instances, the allocation of additional hosting resources and possible the migration of the VNFs to other more capable physical hosts. For example, a firewall may need to install more filtering and control rules or handle more applications and users. Figure 1 depicts examples some of these scaling actions to respond to rising requirements and demand. ETSI [START_REF]Network Functions Virtualisation (NFV); Predeployment Testing; Report on Validation of NFV Environments and Services[END_REF] defines the type of scalings as follows:

B. Scaling Problem

1) When a VNF is scaled out, new VNF components (VNFCs) are instantiated and added to the VNF. Under such circumstances, the VNF may need a mechanism to distribute the load or traffic among the VNFCs (newly instantiated and existing VNFCs). This distribution can be accomplished through the use of load balancers (see figure 1(a)). 2) When a VNF is scaled in, one or more VNFCs of a VNF are terminated. 3) When a VNF is scaled up, it is assigned additional NFVI resources such as compute cores, memory, storage, or network resources (see figure 1(b)). 4) When a VNF is scaled down, NFVI resources that have been previously allocated to the VNF are de-allocated. From the point of view of physical resource consumption, scaling out and scaling up can be treated the same way (i.e., increasing VNF scale is accomplished by scaling out or scaling up [START_REF]Network Functions Virtualisation (NFV); Predeployment Testing; Report on Validation of NFV Environments and Services[END_REF]) despite technical deployment differences. Both actions require additional resources and result in increased physical resources consumption. Scaling out and up are taken into account in our proposed model and optimization algorithms.

IV. PROPOSALS

We propose an Integer Linear Programming solution and a Greedy algorithm to address the VNF scaling problem. We assume that the scaling concerns the 𝑖 𝑡ℎ VNF in the VNF-FG. Hence, 𝑖 is fixed (i.e., not variable) for each scaling request.

A. ILP Solution

We now formulate the ILP model for virtual network function scaling. Table I summarizes the parameters and the used variables. The model includes integrity constraints associated to the objective function used to achieve optimal scaling.

Node re-mapping constraint: Each scaled VNF 𝑖 is remapped to exactly one physical candidate node 𝑘. A VNF (i.e., its components (VNFCs)) can not be split into (distributed across) many physical nodes. This is expressed by:

∑ 𝑘∈𝒞 𝑥 𝑖𝑘 =1 (IV.1)
where:

𝑥 𝑖𝑘 = { 1, if the VNF 𝑖 is re-mapped to physical node 𝑘; 0, otherwise. (IV.
2) Capacity constraint: This constraint ensures that the residual capacity in a physical node 𝑘 satisfies the required capacity by VNF 𝑖. This leads to the following inequality:

𝑐𝑝𝑢 𝑖 × 𝑥 𝑖𝑘 ≤ 𝐶𝑃𝑈 𝑘 , ∀𝑘 ∈𝒞 (IV.3)
Link re-mapping constraint: Each virtual link (𝑖𝑗) will be re-mapped to exactly one physical path 𝑃 𝑘,𝑚(𝑗) where 𝑘 is a physical candidate for the 𝑖 𝑡ℎ VNF and 𝑚(𝑗) is the initial mapping location of the 𝑗 𝑡ℎ VNF. Note that 𝑖 and 𝑗 are neighbors in the VNF-FG request.

∑ 𝑘∈𝒞 𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) =1, ∀(𝑖𝑗) ∈ 𝐸 𝑁 (𝑖) (IV.4)
where:

𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) = ⎧  ⎨  ⎩
1, if the virtual link (𝑖𝑗) is re-mapped to physical path 𝑃 𝑘,𝑚(𝑗) ; 0, otherwise.

(IV.5) Bandwidth constraint: Obviously the residual bandwidth in a physical path 𝑃 𝑘,𝑚(𝑗) has to satisfy the bandwidth requirement of virtual link (𝑖𝑗). We should not violate the remaining bandwidth of each physical link 𝑒 ∈ 𝐸 𝑝 on the physical path 𝑃 𝑘,𝑚(𝑗) . This condition can be formally expressed as:

∑ (𝑖𝑗)∈𝐸𝑁 (𝑖) 𝑏𝑤 𝑖𝑗 × 𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) × 𝛿 𝑒𝑝 ≤ 𝐵𝑊 𝑒 , ∀𝑒 ∈ 𝑃 𝑘,𝑚(𝑗) , ∀𝑃 𝑘,𝑚(𝑗) ∈𝒫 (IV.6)
Node and link re-mapping constraint: When a VNF 𝑖 is re-mapped to a physical candidate node 𝑘, each virtual link (𝑖𝑗), starting from VNF i, has to be re-mapped to a physical path 𝑃 𝑘,𝑚(𝑗) having 𝑘 as one of its endpoint or extremity. The other endpoint is 𝑚(𝑗) (i.e., where 𝑗 is a neighbor of 𝑖 in VNF-FG). Objective function: We are interested in minimizing the service interruption time caused by scaling and favor for this reason new physical hosts with the most available resources. This should also maximize the revenue of the providers that can maintain services and tidy up their infrastructures to accept more users.

𝑥 𝑖𝑘 = 𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) , ∀(𝑖𝑗) ∈ 𝐸 𝑁 (𝑖), ∀𝑘 ∈𝒞 (IV.7)
𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 Where:

𝑍 =(Δ 𝑡𝑟 × 𝑐𝑝𝑢 𝑖 × 𝑅𝑒𝑣 𝑢 ) × ∑ 𝑘∈𝒞 𝐶𝑃𝑈 𝑘 𝑚𝑖𝑛𝐶𝑃𝑈 × 𝑥 𝑖𝑘 -(𝛿 𝑡 × 𝑐𝑝𝑢 𝑖 × 𝑃𝑒𝑛 𝑢 ) × ∑ 𝑘∈𝒞∖{𝑚(𝑖)} 𝑥 𝑖𝑘 (IV.8)
The addressed VNF scaling problem is summarized by lumping the objective function and the constraints: maximize 𝑍 subject to:

∑ 𝑘∈𝒞 𝑥 𝑖𝑘 =1 𝑐𝑝𝑢 𝑖 × 𝑥 𝑖𝑘 ≤ 𝐶𝑃𝑈 𝑘 , ∀𝑘 ∈𝒞 ∑ 𝑘∈𝒞 𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) =1, ∀(𝑖𝑗) ∈ 𝐸 𝑁 (𝑖) ∑ (𝑖𝑗)∈𝐸𝑁 (𝑖) 𝑏𝑤 𝑖𝑗 × 𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) × 𝛿 𝑒𝑝 ≤ 𝐵𝑊 𝑒 , ∀𝑒 ∈ 𝑃 𝑘,𝑚(𝑗) , ∀𝑃 𝑘,𝑚(𝑗) ∈𝒫 𝑥 𝑖𝑘 = 𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗) , ∀(𝑖𝑗) ∈ 𝐸 𝑁 (𝑖), ∀𝑘 ∈𝒞

B. Heuristic Algorithm

We also propose a Greedy algorithm for VNF scaling and re-mapping to compare with our ILP and gain some insight on achievable performance, benefits and strengths of the exact modeling approach. The proposed Greedy algorithm operates using the following 5 steps:

V. P ERFORMANCE EVA L UAT I O N

The performance of our proposed ILP based is assessed through extensive simulations. Simulator settings and performance evaluation metrics used for evaluation and comparison purposes are presented. The ILP is compared to the Greedy heuristic. The evaluation focuses on the gains reconfiguration (just to tidy up the network) and scaling (during rising demands) provide to the stakeholders by analyzing the proportion of rejected (failed) adaptation attempts.

A. Simulation Environment

Our simulations are based on a realistic topology as well as extensive simulations for which it is possible to evaluate in depth the scalability of the algorithms using larger infrastructures and request sizes. A 2.50 GHz Quad Core server with 6 GBytes of available RAM is used for the performance evaluation and comparison of the proposed algorithms.

For the realistic topology and the extensive simulations, the VNF-FG requests are generated using a Poisson process with an average arrival rate of 5 requests per 100 time units. The lifetime of each request follows an exponential distribution with a mean of 1000 time units.

The Germany50 network topology [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF] is used for the first assessment since it corresponds to the largest publicly available network topology (with 50 nodes). This topology is defined by the German National Research and Education Network (DFN). The capacity of physical nodes and links capacities are generated randomly in the [50, 100] intreval. The size of the VNF-FG requests is set to 5 nodes. The GT-ITM [START_REF] Zegura | How to model an internetwork[END_REF] tool is used to generate the requested VNF-FG topologies. The initial VNF-FG computing and bandwidth requirements are set to 10. Scaling in CPU is fixed to 20 with one scaling request at a time per VNF-FG.

To assess the scalability of our proposed algorithms, we generate using the GT-ITM tool a network topology with 100 nodes and a connectivity of 0.2 (or 20%). The physical resources capacities (i.e., CPU and bandwidth) are also drawn randomly in the [50, 100] interval. The VNF-FG requests size varies between 3 and 15 nodes. The required CPU for each VNF in the VNF-FG is set to 10 units. The required bandwidth between two VNFs, to ensure communication between them, is set also to 10 units. The connectivity between nodes in the VNF-FG is set to 0.3.

The ILP algorithm is evaluated for three values of the migration penalty 𝑃𝑒𝑛 𝑢 from 10 to 1000 units in order to tune the penalty according to needs and provider priority as well as measure its effect on performance. The migration penalty (𝑃𝑒𝑛 𝑢 in the second term of the objective function in equation VI.8) is used to control the re-mapping process and to especially trade-off "in node scaling" with "migration to other hosts". The migration penalties in the performance evaluation correspond to the reported ILP10, ILP100 and ILP1000 results. The performance of the ILP for these penalty values (10, 100 and 1000) are also compared to the Greedy algorithm, to assess the effectiveness and usability of this migration. For the realistic topology and the simulation, 1000 VNF-FG requests are generated and a scaling request is triggered for each and every generated request. Since, we are focussing on scaling and adaptation of already embedded VNF-FGs, we used the heuristic approach of [START_REF] Mechtri | Vnf placement and chaining in distributed cloud[END_REF] to generate the initial VNF-FG mapping and initialize the assessment runs.

B. Performance Metrics

The metrics used for the performance evaluation are described in this section that reports also the results obtained using both the realistic topology and the extensive simulations for the extended performance assessment.

1) Successful scalings: represents the number of VNF scaling requests that have been accomplished. Indeed, due to physical resources limitation the algorithm may reject some scaling requests. From the provider point of view, this number should be maximized in order to improve the global revenue.

2) Scaling ratio: is the ratio of successful scalings defined by the ratio of successful scalings to the accepted VNF-FG requests. The number of accepted VNF-FG requests depends on the initial provisioning and on how the scaling algorithm deals with scaling requests. Since we use as initial mapping the same basis for all algorithms, the scaling ratio reflects their relative efficiency and enables their comparison.

3) Number of migrated VNFs: is the number of the scaled VNFs through migration. Migration involves a temporary service interruption until the concerned VNF is activated in the new physical host.

4) The ratio of migrated VNFs: is the ratio of the number of migrated VNFs to the number of successful scalings. This metric measures the proportion of adaptations accomplished through migration that providers prefer to minimize to avoid or limit the service interruptions due to migrations. Minimizing this measure reduces disruptions to applications.

5) Execution time: is a decisive measure in order to assess the scalability of the algorithms. Service providers prefer efficient and rapid algorithms in order to quickly serve clients. Figure 3(a) depicts the number of the migrated VNFs. The ILP with a migration penalty of 10 performs more than ILP1000 for which a higher migration penalty forces the scaling to occur within the nodes in priority. At the first glance, one could conclude that the Greedy algorithm and ILP C use less migrations than the ILP1000 but figure 3(b) shows that the migration ratio of the Greedy strategy (about 90%) is higher than ILP1000 (roughly 87%) and ILP C( 84, 3%).

C. Simulation Results

If we analyze only the three ILP configurations, we observe as expected that ILP10 migrates almost all VNFs (more than 98%) to find more hosting resources while ILP100 migrates about 94% of the requests. shows that the migration ratio of the Greedy strategy (varies between 90% and 95%) is higher than ILP1000 and ILP C (between 80% and 90%). Clearly the ILP can be tuned to outperform other algorithms as well as tradeoff migrations with in node scaling to fulfill the provider preferences and business interests and policies.

3) Importance of reconfiguration: In this subsection we focus on the gain that the reconfiguration process may provide. The provider can perform re-mapping of some VNFs re-mapping to tidy-up their physical networks and prevent bottlenecks and degradations in the NFV-I and in addition can host more client requests. Figure 6 depicts the rejection the Greedy heuristic and the baseline solution (i.e., dealing with only the initial mapping). In this scenario there is no extra CPU demand but only the concerned VNF will be reconfigured. The baseline algorithm (i.e., without reconfiguration) rejects more requests (about 14%) compared to the Greedy heuristic and ILP C( 9%) and the ILP solution (7%). This result can be explained by the dynamics in the requests arrivals and departures that are exploited more efficiently and especially when departures occur and resources are released. The reconfiguration opportunistically tidies up the network and make room for new requests that would be otherwise rejected because of suboptimal use of the infrastructure. In order, to evaluate this metric, the substrate graph size is fixed at 100 nodes. We generate 1000 VNF-FG requests and vary the set of potential candidates size from 5 to 20. These results indicate that the Greedy algorithm has significantly better execution time when compared to our ILP algorithm and ILP C execution times. However, the faster execution times of the Greedy algorithms are accomplished at the expense of the number of accepted scaling requests. Indeed, the ILP achieves 918 scalings and ILP C 909 while the Greedy accepts only 815. The extra time taken by the ILP is due to the ability of the ILP to find more solutions and hence accept more scaling requests.

VI. CONCLUSION

Our work addresses the problem of virtual network function reconfiguration with the main objective of reducing the rejection of VNF scaling requests when faced with rising demand and traffic load. We proposed an ILP solution and a new Greedy reconfiguration algorithm for the purpose and show that the solutions can efficiently scale virtualized network functions and forwarding graphs with good execution time and scaling requests acceptation performance over distributed and dynamically varying cloud environments.

Fig. 1 :

 1 Fig.1: VNF scaling[START_REF]Network Functions Virtualisation (NFV); Predeployment Testing; Report on Validation of NFV Environments and Services[END_REF]

Problem 1 :

 1 VNF scaling optimization summary

Fig. 2 :

 2 Fig. 2: Germany50 topology results: Scalings

  (a) VNF migration (b) Migration ratio

Fig. 3 :

 3 Fig. 3: Germany50 topology results: Migration 2) Scenario 2: To analyze the behavior of the algorithms and their scalability with problem size, we use larger NFV-Is (with 100 nodes) and initial VNF-FG request sizes with a number of VNFs in the [3, 15] interval. Figure 4(a) reports the number of successful scalings. The ILP algorithm outperforms

Figure 4 (

 4 b) confirms this with scaling ratios exceeding 97% for the ILP variants and ILP C. The Greedy strategy achieves ratios only between 84% and 94%.

Fig. 4 :

 4 Fig. 4: Large scale scenarios: Scalings Figure 5(a) illustrates the number of the migrated VNFs.ILP10 performs more migration than the ILP1000. ILP10 and ILP100 perform more migrations than the Greedy and ILP C. ILP10 roughly migrates the totality (exactly 100% if VNF-FG sizes exceed 10) of the scaled VNFs compared to ILP100 that migrates 98, 4%. Figure5(b)shows that the migration ratio of the Greedy strategy (varies between 90% and 95%) is higher than ILP1000 and ILP C (between 80% and 90%). Clearly the ILP can be tuned to outperform other algorithms as well as tradeoff migrations with in node scaling to fulfill the provider preferences and business interests and policies.3) Importance of reconfiguration: In this subsection we focus on the gain that the reconfiguration process may provide. The provider can perform re-mapping of some VNFs re-mapping to tidy-up their physical networks and prevent bottlenecks and degradations in the NFV-I and in addition can host more client requests. Figure6depicts the rejection

Figure 5 (

 5 Figure 5(a) illustrates the number of the migrated VNFs.ILP10 performs more migration than the ILP1000. ILP10 and ILP100 perform more migrations than the Greedy and ILP C. ILP10 roughly migrates the totality (exactly 100% if VNF-FG sizes exceed 10) of the scaled VNFs compared to ILP100 that migrates 98, 4%. Figure5(b)shows that the migration ratio of the Greedy strategy (varies between 90% and 95%) is higher than ILP1000 and ILP C (between 80% and 90%). Clearly the ILP can be tuned to outperform other algorithms as well as tradeoff migrations with in node scaling to fulfill the provider preferences and business interests and policies.3) Importance of reconfiguration: In this subsection we focus on the gain that the reconfiguration process may provide. The provider can perform re-mapping of some VNFs re-mapping to tidy-up their physical networks and prevent bottlenecks and degradations in the NFV-I and in addition can host more client requests. Figure6depicts the rejection

Fig. 5 :

 5 Fig.5: Large scale scenarios: Migration ratio, based on the initial embedding, of the ILP algorithm, the Greedy heuristic and the baseline solution (i.e., dealing with only the initial mapping). In this scenario there is no extra CPU demand but only the concerned VNF will be reconfigured. The baseline algorithm (i.e., without reconfiguration) rejects more requests (about 14%) compared to the Greedy heuristic and ILP C( 9%) and the ILP solution (7%). This result can be explained by the dynamics in the requests arrivals and departures that are exploited more efficiently and especially when departures occur and resources are released. The reconfiguration opportunistically tidies up the network and make room for new requests that would be otherwise rejected because of suboptimal use of the infrastructure.

Fig. 6 :

 6 Fig.6: Rejection Ratio insight on their scalability and complexity with problem size. In order, to evaluate this metric, the substrate graph size is fixed at 100 nodes. We generate 1000 VNF-FG requests and vary the set of potential candidates size from 5 to 20. These results indicate that the Greedy algorithm has significantly better execution time when compared to our ILP algorithm and ILP C execution times. However, the faster execution times of the Greedy algorithms are accomplished at the expense of the number of accepted scaling requests. Indeed, the ILP achieves 918 scalings and ILP C 909 while the Greedy accepts only 815. The extra time taken by the ILP is due to the ability of the ILP to find more solutions and hence accept more scaling requests.

TABLE I :

 I Main notations 𝐸𝑝 belongs to path 𝑃 𝑘,𝑚(𝑗) ∈𝒫: 𝛿𝑒𝑝 =1⇔ 𝑒 ∈ 𝑃 𝑘,𝑚(𝑗)

	Notation	Description
	𝐶𝑃𝑈 𝑘	Residual capacity in a physical node 𝑘
	𝑚(𝑗)	Initial mapping location of VNF 𝑗
	𝑃 𝑘,𝑚(𝑗)	Physical path interconnecting physical nodes 𝑘
		and 𝑚(𝑗)
	𝐵𝑊 𝑃 𝑘,𝑚(𝑗)	Residual bandwidth in a physical path 𝑃 𝑘,𝑚(𝑗)
	𝒞	Set of physical node candidate
	𝒫	Set of physical path candidate
	𝑚𝑖𝑛 𝐶𝑃𝑈	The minimum capacity in 𝒞
	𝐵𝑊𝑒	Residual bandwidth in one physical link 𝑒
	𝛿𝑒𝑝	A binary coefficient determining whether physical
	link 𝑒 ∈ 𝐸 𝑁 (𝑖) Set of virtual links (𝑖𝑗) where 𝑗 is a virtual neighbor
		of 𝑖
	𝑐𝑝𝑢 𝑖	Required capacity by virtual node 𝑖
	𝑏𝑤 𝑖𝑗	Required bandwidth between virtual nodes 𝑖 and 𝑗
	𝑥 𝑖𝑘	A boolean variable indicating whether VNF 𝑖
		is re-mapped to physical node 𝑘
	𝑦 𝑖𝑗,𝑃 𝑘,𝑚(𝑗)	A boolean variable indicating whether virtual link
		(𝑖𝑗) is re-mapped to physical path 𝑃 𝑘,𝑚(𝑗)
	Δ𝑡 𝑟	Remaining time of request before departure
	𝛿𝑡	Required time to migrate one capacity unit
	𝑅𝑒𝑣𝑢	Revenue unit
	𝑃𝑒𝑛𝑢	Penalty unit

  Our Greedy algorithm has a complexity of 𝑂(|𝒞| × |𝑁 𝑝 | 2 × |𝐸 𝑁 (𝑖)|). The algorithm requires in step 9 |𝒞| iterations in the worst case and a complexity |𝑁 𝑝 | 2 in step 12 since the Dijkstra's algorithm is used to compute the shortest path needed to map a virtual link (𝑖𝑗) crossing the scaled VNF 𝑖. The Dijkstra algorithm is called |𝐸 𝑁 (𝑖)| times and this leads to the 𝑂(|𝒞| × |𝑁 𝑝 | 2 ×|𝐸 𝑁 (𝑖)|) overall complexity.

	Else, use migration
	to scale;
	2) find a set of neighboring physical candidate nodes 𝒞
	related to m(i);
	3) check candidate node re-mapping: if node 𝑘 capacity
	and type constraints are met, move to links capacities
	checking;
	4) compute the shortest path between candidate 𝑘 and all
	physical nodes 𝑚(𝑗) (where 𝑗 is a virtual neighbor of 𝑖)
	using Dijkstra's algorithm based on available bandwidth.
	In fact, this corresponds to computing the best paths
	that maximize the minimum bandwidth along their route
	between 𝑘 and 𝑚(𝑗);
	5) check link re-mapping: if links capacities are respected,
	confirm candidate 𝑘 as re-mapping solution.
	Algorithm 1: Scaling Greedy pseudo-code

1) check initial mapping 𝑚(𝑖) capacity: if the remaining resource in node 𝑚(𝑖) can satisfy the new required capacity by VNF 𝑖, scaling occurs in the same physical node 𝑚(𝑖) (i.e., without migration). 1 Inputs: 𝐺 𝑝 , VNF 𝑖, 𝑐𝑝𝑢 𝑖 2 Output: VNF 𝑖 scaled 3 𝑚(𝑖) ← GetInitialMapping(VNF 𝑖) 4 if 𝐶𝑃𝑈 𝑚(𝑖) ≥ 𝑐𝑝𝑢 𝑖 then 5 return Mapping(VNF 𝑖, 𝑐𝑝𝑢 𝑖 , 𝑚(𝑖))

6 else 7 𝒞←ComputeNeighborCandidate(𝑚(𝑖), 𝑐𝑝𝑢 𝑖 ) 8 𝑠𝑡𝑎𝑐𝑘 ← Sort(𝒞) 9 while stack ∕ = ∅ and 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 =F a l s edo 10 𝑘 ← Top(𝑠𝑡𝑎𝑐𝑘) 11 if 𝐶𝑃𝑈 𝑘 ≥ 𝑐𝑝𝑢 𝑖 and 12 ComputeLinkMapping(𝑘, 𝑚(𝑗))=T r u ethen 13 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 ← True 14 return Mapping(VNF 𝑖, 𝑐𝑝𝑢 𝑖 , 𝑘)

TABLE II :

 II Execution time (𝑚𝑠)

		|𝒞|=5	|𝒞|=10	|𝒞|=15	|𝒞|=20
	𝐺𝑟𝑒𝑒𝑑𝑦	11, 65	12, 07	14, 64	15, 43
	𝐼𝐿𝑃	23, 04	38, 21	43, 74	44, 62
	𝐼𝐿𝑃 𝐶	26, 81	41, 87	45, 62	46, 12

4) Average time resolution (Execution time):

Table II reports the execution time performance of the algorithms to gain