{'fraction_non_alphanumeric': 0.02949763847144697, 'fraction_numerical': 0.0072992700729927005, 'mean_word_length': 4.520502488741408, '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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving Reliability of Service Function Chains with Combined VNF Migrations and Replications

The Network Function Virtualization (NFV) paradigm is enabling flexibility, programmability and implementation of traditional network functions into generic hardware, in form of Virtual Network Functions (VNFs). To provide services, the VNFs are commonly concatenated in a certain ordered sequence, known as Service Function Chains (SFCs). SFCs are usually required to meeting a certain level of reliability. This creates the need to place the VNFs while optimizing reliability jointly with other objectives, such as network and server load balancing. Traditional migration and replication mechanisms, commonly used for Virtual Machines (VM) in data centers, can be used to improve SFC reliability. We study how to improve service reliability using jointly replications and migrations, considering the chaining problem inherent in NFV. While replications provide reliability, performing migrations to more reliable servers decreases the resource overhead. A Linear Programming (LP) model is presented to study the impact of active-active configurations on the network and server resources. Additionally, to provide a fast recovery from server failures, we consider N-to-N configurations in NFV networks and study its impact on server resources. The results show that replications do not only improve reliability, but can also be used to achieving a better server and network load balancing, and when used jointly with migrations can improve resource utilization without degrading reliability.


I. INTRODUCTION
Network Function Virtualization (NFV) is a new paradigm that virtualizes the traditional network functions and places them into generic hardware inside the network or in data centers, as opposed to the traditional designated hardware. Since a single Virtual Network Functions (VNF) cannot provide a full service, multiple VNFs are commonly linked in a sequence order, known as Service Function Chains (SFCs), and placed into the network which introduces the so-called VNF placement problem. The placement of the VNFs can happen either in data centers (DC) or by deploying standard Physical Machines (PMs) (e.g., commodity servers) inside the network. Those SFCs provide services that using quality metrics require to meet certain key performance indicators for reliability, latency, service outage downtime, etc.
In NFV-based networks, the provision of service reliability is critical because the failure of a single VNF breaks the continuity of the SFC. Replication mechanisms have already been proposed to target the required service reliability based on VNF redundancy, which allow configurations in Active-StandBy or Active-Active modes. The Active-StandBy con-figurations instantiate VNF replicas in the network without providing service, just waiting for some failure on the main VNF to start working. These configurations do not require any load distribution function, since the replicas are not performing any task during the normal operation mode. On the other hand, Active-Active configurations instantiate VNF replicas which are fully functional VNFs, even in the normal operation mode. In this mode, when a VNF fail the affected traffic is redirected to the remaining operational VNFs. To achieve that, a load distribution function is required as well as a coordination function to maintain the internal state among the replicas.
This paper studies the impact of active-active configurations on the network and server utilization. The main objective is to improve reliability of the service chains by a combined allocation of replicas and usage of migrations of VNFs from lower to higher reliable servers. Since active-active configurations in NFV standards do not consider the reservation of resources to minimize the reconfiguration time in case of failures, some solutions propose traffic replication to avoid reconfiguration delays. In contrast, we propose to study the impact on the server resources when N-to-N configurations are used in NFV. Those schemes consider the reservation of resources before failures to minimize the reconfiguration times, but without the need of replicating traffic. To this end, we propose an LP model to optimally perform placement, replications and migrations of VNFs while maximizing the service reliability and minimizing required network and server resources.
The rest of the paper is organized as follows. Section II presents related work. Section III describes the proposed solution. Section IV formulates the optimization model. Section V analyzes the performance and Section VI concludes the paper.

II. RELATED WORK
Different methods to provide end-to-end reliability in NFV environments has already been discussed by ETSI [1]. The proposed schemes for VNF protection can be classified in two main groups: Active-Standby and Active-Active methods. Active-Standby is a straightforward solution where it is not required to have load distributions functions, but a mechanism to redirect traffic towards standby nodes in case of failure. This solution requires to reserve dedicated resources that are not performing any task. In contrary, active-active schemes are not standby entities, but all nodes are providing service. This solution not only requires redirection of traffic in case of failure, but also an additional load balancing function before the pool of replicated entities to decide how to distribute the traffic. The complexity of active-active solutions is in maintenance and coordination of the internal state replication among replicas to ensure the stateful sessions.
Previously proposed redundancy methods have considered the physical hardware reliability, while ignoring the global information of the VNF Forwarding Graph (VNF-FG) and leading to inaccurate estimation for the services. This has led to an inefficient utilization of networking resources, as shown in [2]. Therefore, the service reliability became rather important in NFV networks. For instance, in [3], the authors evaluate the reliability criterion within a probabilistic model and propose an LP model to address the joint optimization of the chain composition (CC) and the FGE problem. The same problem is solved with heuristics by [4] and [5]. This body of work concluded that an optimum mapping of VNFs is required to optimize reliability regardless the necessity to instantiate additional VNF replicas. Similarly, [6] showed that to guarantee resiliency against single-node failures, it was required the duplicate the amount of resources even in case of failure of a single VNF in service chains.
In the meantime, data centers are being the first environment where to deploy VNFs due to the high flexibility provided by cloud operators. In [7], the authors model different SFC backup strategies and provide heuristic algorithms for resilient embedding in different data center topologies analyzing which one provides a better throughput for a certain resilience. To improve reliability, one solution is to place VNFs backups on the routing path that the SFC is using, however this increases the end-to-end delays due to the extension of the path. To solve that problem, [8] proposed multipath backup schemes to increase reliability while, at the same time, minimizing end-to-end delays. The proposed LP model also replicates the traffic between two end-points in order to support immediate recovery after a failure. While applying this solution does not imply disruption on the service, redundant network and server resources are necessarily to make this solution work.
We showed in our previous work [9] that VNF placement with replications can load balance network, and in this paper we add reliability and server usage optimization in the same type of system. Replicas generally utilize additional resources, we combine replicas with migrations, from lower reliability to higher reliability servers. Additionally, since resource reservation method is required in NFV networks to provide fast recovering after server failures, we also provide a study of the impact of N-to-N configurations have on the server utilization.

III. RELIABILITY SOLUTIONS IN NFV NETWORKS
In this section, we discuss the existing methods to provide reliability with migrations and replications, and introduce our proposed solution that combines the two to provide even better reliability of service function chains. Let S be the set of service chains and V s the set of VNFs from a specific service chain Then, according to [1], the reliability of a certain service chain is calculated as: , where R v is the reliability of a VNF v. Following the example shown in Fig. 1a, where 4 concatenated VNFs are allocated in P M 1 , P M 2 , P M 5 and P M 7 , respectively, the reliability of the service chain is: R s = 0.96 · 0.92 · 0.89 · 0.95 = 0.747.
In case the reliability does not meet the requirements, one solution is to migrate the VNFs to another P M s with higher reliabilities, as shown in Fig. 1b, where V N F 2 and V N F 3 are migrate to P M 3 and P M 6 , respectively. In this case, the achieved reliability is: If the reliability is still lower than the minimum requirements, the solution goes through instantiating VNF replicas in order to improve the robustness. Then, the reliability is defined as: , where V s v is the original VNF v plus the set of replicas of the same function. An example is shown in Fig. 1c, where the V N F 2 and V N F 3 are replicated into P M 3 and P M 6 , respectively. In this case, the achieved reliability is: The more replicas are instantiated, the higher becomes the reliability of the service chain. This solution, known as active-active [1], allocates multiple instances of the same VNF running in active-mode. This scheme requires a load balancing function in front of the pool of replicas to load balance the traffic. In case of failure of one of the replicas, the service chain is not interrupted at all. Only the traffic is redirected from the failed instance to the remaining operational ones.
The main inconvenience with active-active schemes is that higher the reliability achieved, larger the amount of the required resources. For that reason, it is important to consider the optimum allocation of VNFs, from a global point of view, as a requirement for resilient NFV networks. In order to minimize the number of required replicas, while maintaining a similar level of reliability, we propose to use migrations jointly with replications of VNFs. An example is shown in Fig. 1d. Here, only the V N F 2 is replicated into the P M 3 while the traffic is also splitted. Then, in case of failure of P M 2 , the f 1 would be redirected towards P M 3 without service interruption, only the delay associated to the redirection of the traffic. Differently from the previous example, here the V N F 3 is migrated into the P M 4 , instead of being replicated, allowing the increment of reliability without using extra resources. The achieved service reliability in this case is R s = 0.96 · [1 − (1 − 0.92)(1 − 0.97)] · 0.98 · 0.95 = 0.892, which is slightly lower than in the previous case, but requiring one VNF less.
However, the lack of reservation of resources to accommodate the extra redirected traffic from the failed nodes, makes the remaining operational nodes to require more time to accommodate the redirected traffic. To solve that problem, Nto-N configurations, which are a combination between activeactive and N+M configurations, reserve extra resources for fast recovering in each one of the active nodes, without the necessity to have dedicated nodes in a standby mode. This scheme is shown in Fig. 2. Here, the V N F 2a , V N F 2b and V N F 2c , which are replicas of the same function, are processing three different traffic flows, f 1 , f 2 and f 3 , respectively. Because f 3 is twice the size of f 1 and f 2 , the used resources in P M 3 are also twice than those used in P M 1 and P M 2 . In order to support the redirected traffic in case of one of the PMs fails, each V N F requires to reserve extra capacity. Assuming C as the capacity of a PM and f the maximum traffic processed by one PM, for instance, the reserved capacity in V N F 2a and V N F 2b could be C/4 in order to support half of the redirected flow f 3 , in case of failure. While in the V N F 2c could be only C/8 to support half of the redirected flows f 1 or f 2 . With this configuration there are many possibilities, for instance, in case of failure of P M 2 , the flow f 2 can be completely redirected towards the P M 1 or can be split and redirected to both P M 1 and P M 3 . Which one of these solution is chosen will depend whether the objective is to load balance the servers, the network, or both.
In this paper, we propose to deploy both replications and migrations of VNFs to increase the reliability of services, but minimizing the impact on the required network and server resources. Additionally, we also propose to study the impact that N-to-N configurations have on the server utilization.

IV. PROBLEM FORMULATION
We now present the LP model with all the notation specified in Table I. The objective function considers the minimization of four different costs: reliability, server utilization, migration costs and link utilization i.e., the first three terms, i.e., reliability, server and migration costs, are weighted by the α parameter to enable the desired tradeoff between the reliability of the services or the server load balancing and the number of migrations. While the link costs are in all cases taken into consideration, the small β factor decreases its weight in comparison to others. It should be noted that all terms are normalized by the total number of services |S|, servers |X|, functions |V | and links |L|, respectively. The reliability cost is defined by the resulting values from the piecewise linear cost functions z i (u) = 1 − (a i u − b i ), corresponding to an inverse exponential cost, while the rest of costs follow y i (u) = a i u − b i , that correspond to an exponential cost. Both linear cost functions are shown in Fig.  3. It should be noted that the cost of a replica is implicitly included in the cost of the server where the replica is. This is because the cost to place a replica increases the server utilization due the overhead incurred by the creation of a new   VNF. Therefore, the model will only do replication in case the benefit on either the server load balancing, or on reliability, compensates for the cost of creating new VNF replica.
Even though the reliability is considered as a parameter for this model, we are trying to optimize the placement of VNFs maximizing the achieved service reliability. For this reason, the previous equation (2) should be rewritten as: , where the variable f w,s x indicates if the function w from service chain s is allocated in server x. Note that, we assume the reliability of function w is the same than the reliability of the physical server x where the VNF is allocated. Because this solution is not linear, we propose to use reliability costs simulating an inverse penalty function based on the reliability of the server where the VNF is placed: , where R x is the reliability of the server x. Similarly, the server, migration and link costs are respectively defined by: , but using the penalty costs that simulate the exponential function. The server utilization (u x ) is calculated by adding the utilization of every VNF, the overhead introduced by the creation of the VNF and the reserved capacity, in case of applying the N-to-N scheme. Therefore, ∀x ∈ X: x,λ specifies if a certain traffic demand λ is using the VNF v in server x. If true, then using the corresponding load ratio L v for the specific function v, the bandwidth from λ is added. To calculate the overhead, the first term adds the percentage that increases with the utilization of the VNF, and is pondered by the parameter E r . The second term is also pondered by E r and adds a fixed minimum percentage that any VNF has due to its existence. The calculation of the reserved capacity in server x for N-to-N is defined as: , when x = z. Therefore, the variable d v,s x determines which is the replica with highest load and reserves a proportion in relation with the number of replicas. On the other hand, the link utilization is defined as: , where the variable t λ,s p specifies when a specific traffic demand λ is using the path p. If true, then the condition T p checks if path p is traversing the link , in order to sum the bandwidth λ to the equation.
Before optimizing the migration or replication, the model generally first optimizes the placement for each sourcedestination pair of nodes, with a specific ordered set of functions V s that belong to the service chain s ∈ S. In this case, the objective is only to load balance the server and link utilization and no replicas are allowed. In other words, the placement of VNFs determines the initial allocation of VNFs (i.e. F v,s x ) that will be taken as input parameters for the replication and migration later. Taking this into account, the migration costs are defined by: , where the parameter F v,s x specifies if the function v was placed on server x during the initial placement. If so, the variable f v,s x determines if the function remains on the same server, which sets the cost to be zero, or the function has migrated, which sets the cost to be E m . When the model is not able to improve reliability by migrating functions, then it will try place replicas of VNFs. Then, the number of active paths for each service chain is related to the possible allocation of VNFs in the servers and, therefore, is constrained by the number of replicas (i.e. F M AX ≥ 1). Therefore, How many times a VNF can be replicated is determined by the parameter F v and constrained by: If the function can be replicated, then the function can be placed in many servers as active paths the variable t s p determines. The following routing constraint defines that each traffic demand λ from each service chain s can only use one path p: ∀s ∈ S, ∀λ ∈ Λ s : Then, when some traffic demand λ is using the path p, this is activated for the service chain s: Then, the next constraint allocates all VNFs from the service chain s in the activated path using the variable f v,s x,λ : ∀s ∈ S, ∀p ∈ P s , ∀λ ∈ Λ s , ∀v ∈ V s : t λ,s p ≤ n∈Np f v,s x,λ (16) , where N p is an ordered set of servers traversed by path p. The rest of constraints assure the proper activation of VNFs in the correct order for each traffic demand. First, the next constraint specifies that each traffic demand λ has to traverse an specific function v in only one server: Then, the next constraint allocates the function v on server x when at least one traffic demand is using it: Finally, since each service chain is composed by a certain ordered set of VNFs, each traffic demand has to traverse them in the correct order, i.e., ∀s ∈ S, ∀λ ∈ Λ s , ∀p ∈ P s , ∀v ∈ V s , ∀n ∈ N p , ∀x ∈ X n : n m=0 y∈Xm , where for every traffic demand λ, the function v is allocated at server x, only if the previous function v − 1 of the same service chain s is already allocated in any of the previous available servers y from the activated path p. Note that N p is an ordered set of nodes traversed by the path p and X n is the set of servers running on node n.

V. PERFORMANCE EVALUATION
This section shows the results from the LP model implemented with Gurobi Optimizer [10]. The analyzed topology is janos-us with 26 nodes and 84 links taken from SNDLib [11]. Each node has one PM with 2000 units of capacity to allocate VNFs, and the capacity of each link is 1 Gbps. Each source-destination pair of nodes allocate one service chain and randomly generates between 1 and 6 connections with a random bandwidth between 1 and 10 Mbps. Each service chain is composed by 3 VNFs (1950 VNFs in total) and the maximum number of replicas per service chain is 5. Each PM has a random reliability between 0.9 and 0.99. Without protection, α does not affect the results because neither replicas nor migrations are allowed. When the model only optimizes reliability (i.e. α = 1), only placing 470 replicas (see Table II) increases the reliability, but even more evident is this gain when 1198 migrations and 1165 replications are combined. For the rest of α values, doing replications only have benefit when α = 0.9. Contrary, when replications and migrations are combined, the benefit on the achieved reliability is more relevant. Note that, when the model is able to optimally reallocate VNFs, there are more released resources from critical nodes and, therefore, more chances to allocate replicas. The results also show how the increment on the number of replicas to provide protection improves the reliability, but when this is combined whit an optimum reallocation of VNFs the benefit is clearly higher.

B. Server and link utilization
To analyze the servers load balancing, the Fig. 5 show the utilization of all servers in the network for different α values and protection schemes. When α = 1, allowing replication jointly with migrations (i.e. protect. migr.) implies a higher server utilization due to the higher number of replicas compared to the case where no migrations are allowed (i.e. protect.). To be noted, that in both cases there are servers completely overloaded. By relaxing α to 0.9, clearly avoid to have overloaded servers, and all schemes are able to load balance all servers utilization. In this case, having migrations increases the average utilization compared to the case where only replication is allowed. For the rest of α values the behavior is comparable but decreasing the average utilization even more. To be noted that N-to-N schemes increase the average server utilization, but taking into account their benefits on fast recovering, this increment could be justified. Fig. 6 shows the link utilization, one more time, for different α values and compares the case when only replicas are allowed (i.e. rep) and when replicas and migration are allowed (i.e. rep migr.). Here, only performing replications increases the average link utilization in all cases. If re-allocations are allowed by doing migrations, then, the average is also increased in all cases, specially critical when α is close to 1 creating bottlenecks in some links. These results show how a good balance between reliability and load balancing (i.e. α = 0.5) is important to maintain the network load balanced.

VI. CONCLUSIONS
To provide high reliability in service function chains, a high number of VNF replicas is required. While this increment becomes necessary to meet the reliability requirements, the utilization of server and network resources is affected. We proposed to use migrations of VNFs jointly with activeactive configurations to reduce the number of replicas while maintaining an acceptable level of reliability. We also showed the impact on the server utilization of N-to-N configurations, that is comparable higher than active-active but benefiting from fast recovery.
ACKNOWLEDGMENT This work has been performed in the framework of SENDATE-PLANETS (Project ID C2015/3-1), and it is partly funded by the German BMBF (Project ID 16KIS0470).