# Server Resource Dimensioning and Routing of Service Function Chain in NFV Network Architectures

Authors: V. Eramo; A. Tosti; E. Miucci
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

The Network Function Virtualization (NFV) technology aims at virtualizing the network service with the execution of the single service components in Virtual Machines activated on Commercial-off-the-shelf (COTS) servers. Any service is represented by the Service Function Chain (SFC) that is a set of VNFs to be executed according to a given order. The running of VNFs needs the instantiation of VNF instances (VNFI) that in general are software components executed on Virtual Machines. In this paper we cope with the routing and resource dimensioning problem in NFV architectures. We formulate the optimization problem and due to its NP-hard complexity, heuristics are proposed for both cases of offline and online traffic demand. We show how the heuristics works correctly by guaranteeing a uniform occupancy of the server processing capacity and the network link bandwidth. A consolidation algorithm for the power consumption minimization is also proposed. The application of the consolidation algorithm allows for a high power consumption saving that however is to be paid with an increase in SFC blocking probability.


---

## Body

## 1. Introduction

Today’s networks are overly complex, partly due to an increasing variety of proprietary, fixed-function appliances that are unable to deliver the agility and economics needed to address constantly changing market requirements [1]. This is because network elements have traditionally been optimized for high packet throughput at the expense of flexibility, thus hampering the deployment of new services [2]. Network Function Virtualization (NFV) can provide the infrastructure flexibility and agility needed to successfully compete in today’s evolving communications landscape [3]. NFV implements network functions in software running on a pool of shared commodity servers instead of using dedicated proprietary hardware. This virtualized approach decouples the network hardware from the network function and results in increased infrastructure flexibility and reduced hardware costs. Because the infrastructure is simplified and streamlined, new and expended services can be created quickly and with less expense. Implementation of the paradigm has also been proposed [4] and the performance has been investigated [5]. To support the NVF technology both ETSI [6, 7] and IETF [8, 9] are defining novel network architectures able to allocate resources for Virtualized Network Function (VNF) as well as manage and orchestrate NFV to support services. In particular the service is represented by a Service Function Chain (SFC) [8] that is a set of VNFs that have to be executed according to a given order. Any VNF is run on a VNF instance (VNFI) implemented with one Virtual Machine (VM) whose resources (Vcores, RAM memory, etc.) are allocated to [10]. Some solutions have been proposed in the literature to solve the problem of choosing the servers where to instantiate VNF and to determine the network paths interconnecting the VNFs [1]. A formulation of the optimization problem is illustrated in [11]. Three greedy algorithms and a tabu search-based heuristic are proposed in [12]. The extension of the problem in the case in which virtual routers are also considered is proposed in [13].The innovative contribution of our paper is that differently from [12] we follow an approach that allows for both the resource dimensioning and the SFC routing. We formulate the optimization problem whose objective is the minimization of the number of dropped SFC requests with the constraint that the SFCs are routed so as to respect both the server processing capacity and network link bandwidth. With the problem being NP-hard we introduce a heuristic that allows for (i) the dimensioning of the Virtual Machines in terms of number of Vcores assigned and (ii) the SFC routing through the VNF instance implemented by the Virtual Machines. The heuristic performs simultaneously the dimensioning and routing operations. Furthermore we propose a consolidation algorithm based on Virtual Machine migrations and able to achieve power consumption savings. The proposed algorithms are evaluated in scenarios characterized by offline and online traffic demands.The paper is organized as follows. The related work is discussed in Section2. Section 3 is devoted to illustrating the optimization problem and the proposed heuristic for the offline traffic demand case. In Section 4 we describe an SFC planner in which the proposed heuristic is applied in the case of online traffic demand. The planner also implements a consolidation algorithm whose application allows for power consumption savings. Some numerical results are shown in Section 5 to prove the effectiveness of the proposed heuristics. Finally the main conclusions and future research items are mentioned in Section 6.


## 2. Related Work

The Internet Engineering Task Force (IETF) has formed the SFC Working Group [8, 9] to define Service Function Chaining related problems and to standardize the architecture and protocols. A Service Function Chain (SFC) is defined as a set of abstract service functions [15] and ordering constraints that must be applied to packets selected as a result of the classification. When virtual service functions are considered, the SFC is referred to as Virtual Network Function Forwarding Graph (VNFFG) within the ETSI [6]. To support the SFCs, Virtual Network Function instances (VNFIs) are activated and executed in COTS servers. To achieve the economics of scale expected from NFV, network link and server resources should be used efficiently. For this reason efficient algorithms have to be introduced to determine where to instantiate the VNFI and to route the SFCs by choosing the network paths and the VNFI involved. The algorithms have to take into account the limited resources of the network links and the servers and pursued objectives of load balancing, energy saving, recovery from failure, and so on [1]. The task of placing SFC is closely related to virtual network embeddings [16] and virtual data network embedding [17] and may therefore be formulated as an optimization problem, with a particular objective. The approach has been followed by [11, 18–21]. For instance, Moens and Turck [11] formulate the SFC placement problem as a linear optimization problem that has the objective of minimizing the number of active servers. Other objectives are pursued in [19] (latency, remaining data rate, number of used network nodes, etc.) and the SFC placing is formulated as a mixed integer quadratically constrained program.It has been proved that the SFC placing problem is NP-hard. For this reason efficient heuristics have been proposed and evaluated [10, 13, 22, 23]. For example, Xia et al. [22] formulate the placement and chaining problem as binary integer programming and propose a greedy heuristic in which the SFCs are first sorted according to their resource demands and the SFCs with the highest resource demands are given priority for placement and routing.In order to achieve energy consumption saving, the NFV architecture should allow for migrations of VNFI, that is, the migration of the Virtual Machine implementing the VNFI. Though VNFI migrations allow for energy consumption saving, they may impact the QoS performance received by the users related to the migrated VNFs. A model has been proposed in [24] to derive some performance indicators, such as the whole service down time and the total migration time so as to make function migrations decisions.The contribution of this paper is twofold: (i) to propose and to evaluate the performance of an algorithm that performs simultaneously resource dimensioning and SFC routing and (ii) to investigate the advantages from the point of view of the power consumption saving that the application of server consolidation techniques allow us to achieve.


## 3. Offline Algorithms for SFC Routing in NFV Network Architectures

We consider the case in which SFC requests are known in advance. We formulate the optimization problem whose objective is the minimization of the number of dropped SFC requests with the constraint that the SFCs are routed so as to respect both the server processing capacity and network link bandwidth. With the problem being NP-hard we introduce a heuristic that allows for (i) the dimensioning of the Virtual Machines in terms of the number of Vcores assigned and (ii) the SFC routing through the VNF instances implemented by the Virtual Machines. The heuristic performs simultaneously the dimensioning and routing operations.The section is organized as follows. The network and traffic model is introduced in Section3.1. Sections 3.2 and 3.3 are devoted to illustrating the optimization problem and the proposed heuristic, respectively.


### 3.1. Network and Traffic Model

Next we introduce the main terminology used to represent the physical network, VNF, and the SFC traffic request [25]. We represent the physical network PN as a directed graph GPN=(VPN,EPN), where VPN and EPN are the sets of physical nodes and links, respectively. The set VPN of nodes is given by the union of the three node sets VAPN, VRPN, and VSPN that are the sets of access, switching, and server nodes, respectively. The server nodes and links are characterized by the following:(i)
NcorePN(w): processing capacity of the server node w∈VSPN in terms of the number of cores available;(ii)
CPN(d): bandwidth of the physical link d∈EPN.We assume that F types of VNFs can be provisioned as firewall, IDS, proxy, load balancers, and so on. We denote by F=f1,f2,…,fF the set of VNFs, with fi being the ith VNF type. The packet processing time of the VNF fi is denoted by tiproc (i=1,…,F).We also assume that the network operator is receivingT Service Function Chain (SFC) requests known in advance. The ith SFC request is characterized by the graph GiSFC=(ViSFC,EiSFC), where ViSFC represents the set of access and VNF nodes and EiSFC (i=1,…,T) denotes the links between them. In particular the set ViSFC is given by the union of Vi,ASFC and Vi,FSFC denoting the set of access nodes and VNFs, respectively. The graph is characterized by the following parameters:(i)
αvw: assuming the value 1 if the access node v∈⋃i=1TVi,ASFC characterizes an SFC request starting/terminating from/to the physical access nodes w∈VAPN; otherwise its value is 0;(ii)
βvk: assuming the value 1 if the VNF node v∈⋃i=1TVi,FSFC needs the application of the VNF fk (k∈[1,…,F]); otherwise its value is 0;(iii)
BSFC(v): the processing capacity requested by the VNF node v∈⋃i=1TVi,FSFC; the parameter value depends on both the packet length and the bandwidth of the packet flow incoming to the VNF node;(iv)
CSFC(e): bandwidth requested by the link e∈⋃i=1TEiSFC.An example of SFC request is represented in Figure 1 where the traffic emitted by the ingress access node u has to be handled by the VNF nodes v1 and v2 and it is terminating to the egress access node t. The access and VNF nodes are interconnected by the links e1, e2, and e3. If the flow bandwidth is 1 Mbps and the packet length is 1500 bytes we obtain the processing capacities BSFC(v1)=BSFC(v2)=83.33 while the bandwidths CSFC(e1), CSFC(e2), and CSFC(e3) of all links equal 1.Figure 1
An example of graph representing an SFC request for a flow characterized by the bandwidth of 1 Mbps and packet length of 1500 bytes.


### 3.2. Optimization Problem for the SFC Routing and VNF Instance Dimensioning

The objective of the SFC Routing and VNF Instance Dimensioning (SRVID) problem is to maximize the number of accepted SFC requests. The output of the problem is characterized by the following: (i) the servers in which the VNF nodes are executed and (ii) the network paths in which the virtual links of the SFC are routed. This arrangement has to be accomplished without violating both the server processing and the physical link capacities. We assume that all of the servers create a VNF instance for each type of VNF that will be shared by the SFCs using that server and requesting that type of VNF. For this reason each server will activateF VNF instances, one for each type, and another output of the problem is to determine the number of Vcores to be assigned to each VNF instance.We assume that one virtual link of the SFC graphs can be routed through single physical network path. We introduce the following notations:(i)
P: set of paths in GPN,(ii)
δdp: the binary function assuming value 1 or 0 if the network link d belongs or does not to the path p∈P, respectively,(iii)
aPN(p) and bPN(p): origin and destination nodes of the path p∈P,(iv)
aSFC(d) and bSFC(d): origin and destination nodes of the virtual link e∈⋃i=1TEiSFC.Next we formulate the optimal SRVID problem characterized by the following optimization variables: (i)
xh: binary variable assuming the value 1 if the hth SFC request is accepted; otherwise its value is zero;(ii)
ywk: integer variable characterizing the number of Vcores allocated to the VNF instance of type k in the server w∈VSPN;(iii)
zvwk: binary variable assuming the value 1 if the VNF node v∈⋃i=1TVi,FSFC is served by the VNF instance of type k in the server w∈VSPN;(iv)
udp: binary variable assuming the value 1 if the virtual link e∈⋃i=1TEiSFC is embedded in the physical network path p∈P; otherwise its value is zero.Next we report the constraints for the optimization variables:(1)∑k=1Fywk≤NcorePNw,w∈VSPN,(2)∑k=1F∑w∈VSPNzvwk≤1,v∈⋃i=1TVi,FSFC,(3)zvwk≤βvk,k∈1,…,F,v∈⋃i=1TVi,FSFC,w∈VSPN,(4)∑v∈⋃i=1TVi,FSFCzvwkBSFCvtkproc≤ywk,k∈1,…,F,w∈VSPN,(5)udp≤zaSFCdaPNpk,aSFCd∈⋃i=1TVi,FSFC,k∈1,…,F,p∈P,(6)udp≤zbSFCdbPNpk,bSFCd∈⋃i=1TVi,FSFC,k∈1,…,F,p∈P,(7)udp≤αaSFCdaPNpk,aSFCd∈⋃i=1TVi,ASFC,k∈1,…,F,p∈P,(8)udp≤αbSFCdbPNpk,bSFCd∈⋃i=1TVi,ASFC,k∈1,…,F,p∈P,(9)∑p∈Pudp≤1,d∈⋃i=1TEiSFC,(10)∑d∈⋃i=1TEiSFCCSFCd∑p∈Pδepudp≤CPNe,(11)xh≤∑k=1F∑w∈VSPNzvwk,h∈1,…,T,v∈Vh,FSFC,(12)xh≤∑p∈Pudp,h∈1,…,T,d∈EhSFC.Constraint (1) establishes the fact that at most a number of Vcores equal to the available ones are used for each server node w∈VSPN. Constraint (2) expresses the condition that a VNF can be served by one only VNF instance. To guarantee that a node v∈Vh,FSFC needing the application of a VNF type is mapped to a correct VNF instance we introduce constraint (3). Constraint (4) limits the number of VNF nodes assigned to one VNF instance by taking into account both the number of Vcores assigned to the VNF instance and the required VNF node processing capacities. Constraints (5)–(8) establish the fact that when the virtual link d is supported by the physical network path p then aPN(p) and bPN(p) must be the physical network nodes that the nodes aSFC(d) and bSFC(d) of the virtual graph are assigned to. The choice of mapping of any virtual link on a single physical network path is represented by constraint (9). Constraint (10) avoids any overloading on any physical network link. Finally constraints (11) and (12) establish the fact that an SFC request can be accepted when the nodes and the links of the SFC graph are assigned to VNF instances and physical network paths.The problem objective is to maximize the number of SFCs accepted given by(13)max⁡∑h=1Txh.The introduced optimization problem is intractable because it requires solving a NP-hard bin packing problem [26]. Due to its high complexity, it is not possible to solve the problem directly in a timely manner given the large number of servers and network nodes. For this reason we propose an efficient heuristic in Section 3.3.


### 3.3. Maximizing the Accepted SFC Requests Number (MASRN) Heuristic

The Maximizing the Accepted SFC Requests Number (MASRN) heuristic is based on the embedding algorithm proposed in [14] and has the objective of maximizing the number of accepted SFC requests. The MASRN algorithm tries routing the SFCs one by one by using the least loaded link and server resources so as to balance their use. Algorithm 1 illustrates the operation mode of the MASRN algorithm. The routing of a target SFC, the ktarth, is illustrated. The main inputs of the algorithm are (i) the set Tpre containing the indexes of the SFC requests routed successfully before the ktarth SFC request; (ii) the ktarth SFC request graph GktarSFC=(VktarSFC,EktarSFC); (iii) the values of the parameters αvw for the ktarth SFC request; (iv) the values of the variables zvwk and udp for the SFC requests successfully routed before the ktarth SFC request and defined in Section 3.2.Algorithm 1:MASRN algorithm.
(1)Input: Physical Network Graph GPN=(VPN,EPN); ktarth SFC request; ktarth SFC request Graph
GktarSFC=(VktarSFC,EktarSFC); Tpre;
αvw,v∈Vktar,ASFCw∈VAPN;
zvwk,k∈[1,…,F]v∈⋃i∈TpreVi,FSFCw∈VSPN;
udp,d∈⋃i∈TpreEiSFCp∈P;
(2)Variables: Ak(w),k∈[1,…,F]w∈VSPN;
SN(w),w∈VSPN;
SL(e),e∈EPN;
ywk,k∈[1,…,F]w∈VSPN;
/∗Evaluation of the candidate mapping of   GktarSFC=(VktarSFC,EktarSFC)in  GPN=(VPN,EPN)∗/
(3)assign the node v∈Vktar,ASFC to the physical network node w∈VSPN according to the value of the parameter αvw;
(4)select the nodes w∈VSPN and the physical network paths p∈P to be assigned to the server nodes v∈Vktar,FSFC and virtual links
d∈Ektar,SSFC by applying the algorithm proposed in [14] and based on the values of the node and link stresses SN(w) and SL(e);
determine the variable values:
zvwk,k∈[1,…,F]v∈Vktar,FSFCw∈VSPN;
udp,d∈EktarSFCp∈P;
/∗Server Resource Availability Check Phase∗/
(5)for  v∈Vktar,FSFC, w∈VSPN, k∈[1,…,F]  do
(6)if  ∑s=1(s≠k)Fyws+Ak(w)+zvwkBSFC(v)tkproc≤NcorePNw  then
(7)Ak(w)=Ak(w)+zvwkBSFC(v)tkproc;
(8)SN(w)=SN(w)+zvwkBSFC(v)tkproc;
(9)ywk=Ak(w)+zvwkBSFC(v)tkproc;
(10)else
(11)REJECT  the ktarth SFC request
(12)end if
(13)end for
/∗Link Resource Availability Check Phase∗/
(14)for  e∈EPN  do
(15)if  SL(e)+∑d∈EktarSFC‍CSFC(d)∑p∈P‍δepudp≤CPN(e)  then
(16)SL(e)=SL(e)+∑d∈EktarSFC‍CSFC(d)∑p∈P‍δepudp;
(17)else
(18)REJECT the ktarth SFC request
(19)end if
(20)end for
(21)Output:  zvwk,k∈[1,…,F]v∈Vktar,FSFCw∈VSPN;
udp,d∈EktarSFCp∈PThe operation mode of the heuristic is based on the following variables:(i)
Ak(w): the load of the cores allocated for the VNF instance of type k∈[1,…,F] in the server w∈VSPN; the value of Ak(w) is initialized by taking into account the core resource amount used by the SFCs successfully routed before the ktarth SFC request; hence its initial value is(14)Akw=∑v∈⋃i∈TktarVi,FSFCzvwkBSFCvtkproc.(ii)
SN(w): defined as the stress of the node w∈VSPN [14] and characterizing the server load; its value is initialized to(15)SNw=∑k=1FAkw.(iii)
SL(e): defined as the stress of the physical network link e∈EPN [14] and characterizing the link load; its value is initialized to(16)SLe=∑d∈⋃i∈TktarEiSFCCSFCd∑p∈Pδepudp.The candidate physical network links and nodes in which to embed the target SFC are evaluated. First of all the access nodes are evaluated (line 3) according to the values of the parametersαvw, v∈Vktar,ASFC, w∈VAPN. Next the MASRN algorithm selects a cluster of server nodes (line 4) that are not lightly loaded but also likely to result in low substrate link stresses when they are connected. Details on the procedure are reported in [14].In the next phases the resource availability in the selected cluster is checked. The resource availability in the server nodes and physical network links is verified in the Server (lines 5–13) and Link (lines 14–20) Resource Availability Check Phases, respectively. If resources are not available in either links or nodes, the target SFC request is rejected. In particular, in the Server Resource Availability Check Phase, the algorithm verifies whether the allocation of new Vcores is needed and in this case their availability is checked (line 6). The variableywk is also updated in this phase (line 9).Finally the outputs (line 21) of the MASRN algorithm are the selected values for the variableszvwk,k∈1,…,Fv∈Vktar,FSFCw∈VSPN and udp,d∈EktarSFCp∈P.The computational complexity of the MASRN algorithm depends on the procedure for the evaluation of the potential nodes [14]. Let Ns be the total number of servers. The complexity of the phase in which the potential nodes are evaluated can be carried out according to the following remarks: (i) as many servers as the number of the VNFs of the SFC are determined and (ii) the hth server is selected by evaluating the (Ns-h) shortest paths and by performing a minimum operation of a list with (Ns-h) elements. According to these remarks the computational complexity is given by O(VV+NsNllog⁡(Ns+Nn)), where V is the maximum number of VNFs in an SFC and Nl and Nn are the numbers of nodes and links of the network.


## 3.1. Network and Traffic Model

Next we introduce the main terminology used to represent the physical network, VNF, and the SFC traffic request [25]. We represent the physical network PN as a directed graph GPN=(VPN,EPN), where VPN and EPN are the sets of physical nodes and links, respectively. The set VPN of nodes is given by the union of the three node sets VAPN, VRPN, and VSPN that are the sets of access, switching, and server nodes, respectively. The server nodes and links are characterized by the following:(i)
NcorePN(w): processing capacity of the server node w∈VSPN in terms of the number of cores available;(ii)
CPN(d): bandwidth of the physical link d∈EPN.We assume that F types of VNFs can be provisioned as firewall, IDS, proxy, load balancers, and so on. We denote by F=f1,f2,…,fF the set of VNFs, with fi being the ith VNF type. The packet processing time of the VNF fi is denoted by tiproc (i=1,…,F).We also assume that the network operator is receivingT Service Function Chain (SFC) requests known in advance. The ith SFC request is characterized by the graph GiSFC=(ViSFC,EiSFC), where ViSFC represents the set of access and VNF nodes and EiSFC (i=1,…,T) denotes the links between them. In particular the set ViSFC is given by the union of Vi,ASFC and Vi,FSFC denoting the set of access nodes and VNFs, respectively. The graph is characterized by the following parameters:(i)
αvw: assuming the value 1 if the access node v∈⋃i=1TVi,ASFC characterizes an SFC request starting/terminating from/to the physical access nodes w∈VAPN; otherwise its value is 0;(ii)
βvk: assuming the value 1 if the VNF node v∈⋃i=1TVi,FSFC needs the application of the VNF fk (k∈[1,…,F]); otherwise its value is 0;(iii)
BSFC(v): the processing capacity requested by the VNF node v∈⋃i=1TVi,FSFC; the parameter value depends on both the packet length and the bandwidth of the packet flow incoming to the VNF node;(iv)
CSFC(e): bandwidth requested by the link e∈⋃i=1TEiSFC.An example of SFC request is represented in Figure 1 where the traffic emitted by the ingress access node u has to be handled by the VNF nodes v1 and v2 and it is terminating to the egress access node t. The access and VNF nodes are interconnected by the links e1, e2, and e3. If the flow bandwidth is 1 Mbps and the packet length is 1500 bytes we obtain the processing capacities BSFC(v1)=BSFC(v2)=83.33 while the bandwidths CSFC(e1), CSFC(e2), and CSFC(e3) of all links equal 1.Figure 1
An example of graph representing an SFC request for a flow characterized by the bandwidth of 1 Mbps and packet length of 1500 bytes.


## 3.2. Optimization Problem for the SFC Routing and VNF Instance Dimensioning

The objective of the SFC Routing and VNF Instance Dimensioning (SRVID) problem is to maximize the number of accepted SFC requests. The output of the problem is characterized by the following: (i) the servers in which the VNF nodes are executed and (ii) the network paths in which the virtual links of the SFC are routed. This arrangement has to be accomplished without violating both the server processing and the physical link capacities. We assume that all of the servers create a VNF instance for each type of VNF that will be shared by the SFCs using that server and requesting that type of VNF. For this reason each server will activateF VNF instances, one for each type, and another output of the problem is to determine the number of Vcores to be assigned to each VNF instance.We assume that one virtual link of the SFC graphs can be routed through single physical network path. We introduce the following notations:(i)
P: set of paths in GPN,(ii)
δdp: the binary function assuming value 1 or 0 if the network link d belongs or does not to the path p∈P, respectively,(iii)
aPN(p) and bPN(p): origin and destination nodes of the path p∈P,(iv)
aSFC(d) and bSFC(d): origin and destination nodes of the virtual link e∈⋃i=1TEiSFC.Next we formulate the optimal SRVID problem characterized by the following optimization variables: (i)
xh: binary variable assuming the value 1 if the hth SFC request is accepted; otherwise its value is zero;(ii)
ywk: integer variable characterizing the number of Vcores allocated to the VNF instance of type k in the server w∈VSPN;(iii)
zvwk: binary variable assuming the value 1 if the VNF node v∈⋃i=1TVi,FSFC is served by the VNF instance of type k in the server w∈VSPN;(iv)
udp: binary variable assuming the value 1 if the virtual link e∈⋃i=1TEiSFC is embedded in the physical network path p∈P; otherwise its value is zero.Next we report the constraints for the optimization variables:(1)∑k=1Fywk≤NcorePNw,w∈VSPN,(2)∑k=1F∑w∈VSPNzvwk≤1,v∈⋃i=1TVi,FSFC,(3)zvwk≤βvk,k∈1,…,F,v∈⋃i=1TVi,FSFC,w∈VSPN,(4)∑v∈⋃i=1TVi,FSFCzvwkBSFCvtkproc≤ywk,k∈1,…,F,w∈VSPN,(5)udp≤zaSFCdaPNpk,aSFCd∈⋃i=1TVi,FSFC,k∈1,…,F,p∈P,(6)udp≤zbSFCdbPNpk,bSFCd∈⋃i=1TVi,FSFC,k∈1,…,F,p∈P,(7)udp≤αaSFCdaPNpk,aSFCd∈⋃i=1TVi,ASFC,k∈1,…,F,p∈P,(8)udp≤αbSFCdbPNpk,bSFCd∈⋃i=1TVi,ASFC,k∈1,…,F,p∈P,(9)∑p∈Pudp≤1,d∈⋃i=1TEiSFC,(10)∑d∈⋃i=1TEiSFCCSFCd∑p∈Pδepudp≤CPNe,(11)xh≤∑k=1F∑w∈VSPNzvwk,h∈1,…,T,v∈Vh,FSFC,(12)xh≤∑p∈Pudp,h∈1,…,T,d∈EhSFC.Constraint (1) establishes the fact that at most a number of Vcores equal to the available ones are used for each server node w∈VSPN. Constraint (2) expresses the condition that a VNF can be served by one only VNF instance. To guarantee that a node v∈Vh,FSFC needing the application of a VNF type is mapped to a correct VNF instance we introduce constraint (3). Constraint (4) limits the number of VNF nodes assigned to one VNF instance by taking into account both the number of Vcores assigned to the VNF instance and the required VNF node processing capacities. Constraints (5)–(8) establish the fact that when the virtual link d is supported by the physical network path p then aPN(p) and bPN(p) must be the physical network nodes that the nodes aSFC(d) and bSFC(d) of the virtual graph are assigned to. The choice of mapping of any virtual link on a single physical network path is represented by constraint (9). Constraint (10) avoids any overloading on any physical network link. Finally constraints (11) and (12) establish the fact that an SFC request can be accepted when the nodes and the links of the SFC graph are assigned to VNF instances and physical network paths.The problem objective is to maximize the number of SFCs accepted given by(13)max⁡∑h=1Txh.The introduced optimization problem is intractable because it requires solving a NP-hard bin packing problem [26]. Due to its high complexity, it is not possible to solve the problem directly in a timely manner given the large number of servers and network nodes. For this reason we propose an efficient heuristic in Section 3.3.


## 3.3. Maximizing the Accepted SFC Requests Number (MASRN) Heuristic

The Maximizing the Accepted SFC Requests Number (MASRN) heuristic is based on the embedding algorithm proposed in [14] and has the objective of maximizing the number of accepted SFC requests. The MASRN algorithm tries routing the SFCs one by one by using the least loaded link and server resources so as to balance their use. Algorithm 1 illustrates the operation mode of the MASRN algorithm. The routing of a target SFC, the ktarth, is illustrated. The main inputs of the algorithm are (i) the set Tpre containing the indexes of the SFC requests routed successfully before the ktarth SFC request; (ii) the ktarth SFC request graph GktarSFC=(VktarSFC,EktarSFC); (iii) the values of the parameters αvw for the ktarth SFC request; (iv) the values of the variables zvwk and udp for the SFC requests successfully routed before the ktarth SFC request and defined in Section 3.2.Algorithm 1:MASRN algorithm.
(1)Input: Physical Network Graph GPN=(VPN,EPN); ktarth SFC request; ktarth SFC request Graph
GktarSFC=(VktarSFC,EktarSFC); Tpre;
αvw,v∈Vktar,ASFCw∈VAPN;
zvwk,k∈[1,…,F]v∈⋃i∈TpreVi,FSFCw∈VSPN;
udp,d∈⋃i∈TpreEiSFCp∈P;
(2)Variables: Ak(w),k∈[1,…,F]w∈VSPN;
SN(w),w∈VSPN;
SL(e),e∈EPN;
ywk,k∈[1,…,F]w∈VSPN;
/∗Evaluation of the candidate mapping of   GktarSFC=(VktarSFC,EktarSFC)in  GPN=(VPN,EPN)∗/
(3)assign the node v∈Vktar,ASFC to the physical network node w∈VSPN according to the value of the parameter αvw;
(4)select the nodes w∈VSPN and the physical network paths p∈P to be assigned to the server nodes v∈Vktar,FSFC and virtual links
d∈Ektar,SSFC by applying the algorithm proposed in [14] and based on the values of the node and link stresses SN(w) and SL(e);
determine the variable values:
zvwk,k∈[1,…,F]v∈Vktar,FSFCw∈VSPN;
udp,d∈EktarSFCp∈P;
/∗Server Resource Availability Check Phase∗/
(5)for  v∈Vktar,FSFC, w∈VSPN, k∈[1,…,F]  do
(6)if  ∑s=1(s≠k)Fyws+Ak(w)+zvwkBSFC(v)tkproc≤NcorePNw  then
(7)Ak(w)=Ak(w)+zvwkBSFC(v)tkproc;
(8)SN(w)=SN(w)+zvwkBSFC(v)tkproc;
(9)ywk=Ak(w)+zvwkBSFC(v)tkproc;
(10)else
(11)REJECT  the ktarth SFC request
(12)end if
(13)end for
/∗Link Resource Availability Check Phase∗/
(14)for  e∈EPN  do
(15)if  SL(e)+∑d∈EktarSFC‍CSFC(d)∑p∈P‍δepudp≤CPN(e)  then
(16)SL(e)=SL(e)+∑d∈EktarSFC‍CSFC(d)∑p∈P‍δepudp;
(17)else
(18)REJECT the ktarth SFC request
(19)end if
(20)end for
(21)Output:  zvwk,k∈[1,…,F]v∈Vktar,FSFCw∈VSPN;
udp,d∈EktarSFCp∈PThe operation mode of the heuristic is based on the following variables:(i)
Ak(w): the load of the cores allocated for the VNF instance of type k∈[1,…,F] in the server w∈VSPN; the value of Ak(w) is initialized by taking into account the core resource amount used by the SFCs successfully routed before the ktarth SFC request; hence its initial value is(14)Akw=∑v∈⋃i∈TktarVi,FSFCzvwkBSFCvtkproc.(ii)
SN(w): defined as the stress of the node w∈VSPN [14] and characterizing the server load; its value is initialized to(15)SNw=∑k=1FAkw.(iii)
SL(e): defined as the stress of the physical network link e∈EPN [14] and characterizing the link load; its value is initialized to(16)SLe=∑d∈⋃i∈TktarEiSFCCSFCd∑p∈Pδepudp.The candidate physical network links and nodes in which to embed the target SFC are evaluated. First of all the access nodes are evaluated (line 3) according to the values of the parametersαvw, v∈Vktar,ASFC, w∈VAPN. Next the MASRN algorithm selects a cluster of server nodes (line 4) that are not lightly loaded but also likely to result in low substrate link stresses when they are connected. Details on the procedure are reported in [14].In the next phases the resource availability in the selected cluster is checked. The resource availability in the server nodes and physical network links is verified in the Server (lines 5–13) and Link (lines 14–20) Resource Availability Check Phases, respectively. If resources are not available in either links or nodes, the target SFC request is rejected. In particular, in the Server Resource Availability Check Phase, the algorithm verifies whether the allocation of new Vcores is needed and in this case their availability is checked (line 6). The variableywk is also updated in this phase (line 9).Finally the outputs (line 21) of the MASRN algorithm are the selected values for the variableszvwk,k∈1,…,Fv∈Vktar,FSFCw∈VSPN and udp,d∈EktarSFCp∈P.The computational complexity of the MASRN algorithm depends on the procedure for the evaluation of the potential nodes [14]. Let Ns be the total number of servers. The complexity of the phase in which the potential nodes are evaluated can be carried out according to the following remarks: (i) as many servers as the number of the VNFs of the SFC are determined and (ii) the hth server is selected by evaluating the (Ns-h) shortest paths and by performing a minimum operation of a list with (Ns-h) elements. According to these remarks the computational complexity is given by O(VV+NsNllog⁡(Ns+Nn)), where V is the maximum number of VNFs in an SFC and Nl and Nn are the numbers of nodes and links of the network.


## 4. Online Algorithms for SFC Routing in NFV Network Architectures

In the online approach the SFC requests arrive at the system over the time and each of them is characterized by a certain duration. In order to reduce the complexity of the online SFC resource allocation algorithm we designed an SFC planner whose general architecture is described in Section4.1. The operation mode of the SFC planner is based on some algorithms that we describe in Section 4.2.


### 4.1. SFC Planner Architecture

The architecture of the SFC planner is shown in Figure2. It could make up the main component of an orchestrator in the NFV architecture [6]. It is composed of three components: theSFC Scheduler, theResource Monitor, and theConsolidation Module.Figure 2
SFC planner architecture.Once the SFC Scheduler receives an SFC request, it executes an algorithm to verify if resources are available and to decide which resources to use.The physical resource, as well as the Virtual Machines running on the servers, is monitored by theResource Monitor. If a failure of any physical/virtual node or link occurs it notifies the event to the SFC Scheduler.The Consolidation Module allows for the server resource consolidation in low traffic periods. When the consolidation technique is applied, VMs are migrated to as fewer servers as possible; the remaining ones are turned off and power consumption saving can be achieved.


### 4.2. SFC Scheduling and Consolidation Algorithms

In this section we describe the algorithms executed by the SFC Scheduler and the Consolidation Module.Whenever a new SFC request arrives at the SFC planner, the SFC scheduling algorithm is executed in order to find the best embedding in the system, maintaining a uniform usage of the network resource. The main steps of this procedure are reported in the flow chart in Figure3 and are based on MASRN heuristic described in Section 3.3. The algorithm starts selecting the set of servers on which the VNFs requested by the SFC will be executed. In the second step the physical paths on which the virtual links will be mapped are selected. If there are not enough available resources in the first or in the second step the request is dropped.Figure 3
Flow chart of the SFC scheduling algorithm.The flow chart of the consolidation algorithm is reported in Figure4. Each server s∈VSPN is characterized by a parameter ηs defined as the ratio of the total amount of incoming/outgoing traffic Λs that it is handling to the power Ps it is consuming; that is, ηs=Λs/Ps. The power consumption model assumes a constant power contribution and a variable one that linearly increases versus the handled traffic. The server power consumption is expressed by(17)Ps=Pidle+Pmax-PidleLsCs,∀s∈VSPN,where Pidle is the power consumed by the server when no traffic is handled, Pmax is the maximum server power consumption, Ls is the total load handled by the server s, and Cs is its maximum capacity. The maximum power that the server can consume is expressed as Pmax=Pidle/a, where a is a parameter characterizing how much the power consumption is depending on the handled traffic. The power consumption is as much more rate adaptive as a is lower. For a=1 the rate adaptive power consumption is absent and the consumed power is constant.Figure 4
Flow chart of the SFC consolidation algorithm.The proposed algorithm tries switching off the server with minimum power consumption per bit carried. For this reason when the consolidation algorithm is executed it starts selecting the serversmin with the minimum value of ηs as the one to turn off. A set of possible destination servers able to host the VMs executed on smin is then evaluated and sorted in descending order based again on the value of ηs. The algorithm proceeds selecting the first element of the ordered set and evaluating if there are enough resources in the site to reroute all the flows generated from or terminated to smin. If it succeeds the migration is performed and the server smin is turned off. If it fails the destination server is removed and the next server of the list is considered. When the ordered set of possible destinations becomes empty another server to turn off is selected.The SFC Consolidation Module also manages the resource deconsolidation procedure when the reactivation of physical servers/links is needed. Basically the deconsolidation algorithm selects the most loaded VMs already migrated to a new server and moves them to their original servers. The flows handled by these VMs are accordingly rerouted.


## 4.1. SFC Planner Architecture

The architecture of the SFC planner is shown in Figure2. It could make up the main component of an orchestrator in the NFV architecture [6]. It is composed of three components: theSFC Scheduler, theResource Monitor, and theConsolidation Module.Figure 2
SFC planner architecture.Once the SFC Scheduler receives an SFC request, it executes an algorithm to verify if resources are available and to decide which resources to use.The physical resource, as well as the Virtual Machines running on the servers, is monitored by theResource Monitor. If a failure of any physical/virtual node or link occurs it notifies the event to the SFC Scheduler.The Consolidation Module allows for the server resource consolidation in low traffic periods. When the consolidation technique is applied, VMs are migrated to as fewer servers as possible; the remaining ones are turned off and power consumption saving can be achieved.


## 4.2. SFC Scheduling and Consolidation Algorithms

In this section we describe the algorithms executed by the SFC Scheduler and the Consolidation Module.Whenever a new SFC request arrives at the SFC planner, the SFC scheduling algorithm is executed in order to find the best embedding in the system, maintaining a uniform usage of the network resource. The main steps of this procedure are reported in the flow chart in Figure3 and are based on MASRN heuristic described in Section 3.3. The algorithm starts selecting the set of servers on which the VNFs requested by the SFC will be executed. In the second step the physical paths on which the virtual links will be mapped are selected. If there are not enough available resources in the first or in the second step the request is dropped.Figure 3
Flow chart of the SFC scheduling algorithm.The flow chart of the consolidation algorithm is reported in Figure4. Each server s∈VSPN is characterized by a parameter ηs defined as the ratio of the total amount of incoming/outgoing traffic Λs that it is handling to the power Ps it is consuming; that is, ηs=Λs/Ps. The power consumption model assumes a constant power contribution and a variable one that linearly increases versus the handled traffic. The server power consumption is expressed by(17)Ps=Pidle+Pmax-PidleLsCs,∀s∈VSPN,where Pidle is the power consumed by the server when no traffic is handled, Pmax is the maximum server power consumption, Ls is the total load handled by the server s, and Cs is its maximum capacity. The maximum power that the server can consume is expressed as Pmax=Pidle/a, where a is a parameter characterizing how much the power consumption is depending on the handled traffic. The power consumption is as much more rate adaptive as a is lower. For a=1 the rate adaptive power consumption is absent and the consumed power is constant.Figure 4
Flow chart of the SFC consolidation algorithm.The proposed algorithm tries switching off the server with minimum power consumption per bit carried. For this reason when the consolidation algorithm is executed it starts selecting the serversmin with the minimum value of ηs as the one to turn off. A set of possible destination servers able to host the VMs executed on smin is then evaluated and sorted in descending order based again on the value of ηs. The algorithm proceeds selecting the first element of the ordered set and evaluating if there are enough resources in the site to reroute all the flows generated from or terminated to smin. If it succeeds the migration is performed and the server smin is turned off. If it fails the destination server is removed and the next server of the list is considered. When the ordered set of possible destinations becomes empty another server to turn off is selected.The SFC Consolidation Module also manages the resource deconsolidation procedure when the reactivation of physical servers/links is needed. Basically the deconsolidation algorithm selects the most loaded VMs already migrated to a new server and moves them to their original servers. The flows handled by these VMs are accordingly rerouted.


## 5. Numerical Results

We evaluate the effectiveness of the proposed algorithms in the case of the network scenario reported in Figure5. The network is composed of five core nodes, five edge nodes, and six access nodes in which the SFC requests are randomly generated and terminated. A Network Function Virtualization (NFV) site is connected to edge nodes 3 and 4 through two access routers 1 and 2. The NFV site is also composed of two switches and eight servers. In the basic configuration, 40 Gbps links are considered except the links connecting the server to the switches in the NFV sites whose rate is equal to 10 Gbps. The sixteen servers are equipped with 48 Vcores each.Figure 5
The network topology is composed of six access nodes, five edge nodes, and five core nodes. The NFV site is composed of two routers, two switches, and sixteen servers.Each SFC request is composed of three Virtual Network Functions (VNFs), that is, a firewall, a load balancer, and VPN encryption whose packet processing times are assumed to be equal to 7,08μs, 0,65 μs, and 1,64 μs [27], respectively. We also assume that the load balancer splits the input traffic towards a number of output links chosen uniformly from 1 to 3.An example of graph for a generated SFC is reported in Figure6 in which ut is an ingress access node and vt1, vt2, and vt3 are egress access nodes. The first and second VNFs are a firewall and VPN encryption; the third VNF is a load balancer splitting the traffic towards three output links. In the considered case study we also assume that the SFC handles traffic flows of packet length equal to 1500 bytes and required bandwidth uniformly distributed from 500 Mbps to 1 Gbps.Figure 6
An example of SFC composed of one firewall VNF, one VPN encryption VNF, and one load balancer VNF that splits the input traffic towards three output logical links.ut denotes the ingress access node while vt1, vt2, and vt3 denote the egress access nodes.


### 5.1. Offline SFC Scheduling

In the offline case we assume that a given numberT of SFC requests are a priori known. For the case study previously described we apply the MASRN heuristic proposed in Section 3.3. We report the percentage of the dropped SFCs in Figure 7 as a function of the offered number of SFCs. We report the curve for the basic scenario and the ones in which the link capacities are doubled, quadrupled, and increased per ten times, respectively. From Figure 7 we can see how, in order to have a dropped SFC percentage lower than 10%, the number of SFCs requests has to be smaller than 60 in the case of basic scenario. This remarkable blocking is due to the shortage of network capacity. In fact we can notice from Figure 7 how the dropped SFC percentage significantly decreases when the link bandwidth increases. For instance, when the capacity is quadrupled, the network infrastructure is able to accommodate up to 180 SFCs without any loss.Figure 7
Dropped SFC percentage as a function of the number of SFCs offered. The four curves are reported for the basic scenario case and the ones in which the link capacities are doubled, quadrupled, and increased by 10 times.This is confirmed in Figure8 where we report the number of Vcores occupied in the servers in the case of T=360. Each of the servers is represented on the x-axis with the identification (ID) of Figure 5. We also show in Figure 8 the number of Vcores allocated to each firewall, load balancer, and VPN encryption VNF with the blue, green, and red colors, respectively. The basic scenario case and the ones in which the link capacity is doubled, quadrupled, and increased by 10 times are reported in Figures 8(a), 8(b), 8(c), and 8(d), respectively. From Figure 8 we can notice how the MASRN heuristic works correctly by guaranteeing a uniform occupancy of the servers in terms of total number of Vcores used. We can also notice how the firewall VNF is the one needing the higher number of Vcores allocated. That is a consequence of the higher processing time that the firewall VNF requires with respect to the load balancer and VPN encryption VNFs.Figure 8
Number of allocated Vcores in each server. The number of Vcores for firewall, load balancer, and encryption VPN VNFs are represented with blue, green, and red colors.
(a)
(b)
(c)
(d)


### 5.2. Online SFC Scheduling

The numerical results are achieved in the following traffic scenario. The traffic pattern we consider is supposed to be sinusoidal with a peak value during daytime and minimum value during nighttime. We also assume that SFC requests follow a Poisson process and the SFC duration time is distributed according to an exponential distribution. The following parameters define the SFC requests in the Peak Hour Interval (PHI):(i)
λ is the arrival rate of SFC requests;(ii)
μ is the termination rate of an embedded SFC;(iii)
[βmin,βmax] is the range in which the bandwidth request for an SFC is randomly selected.We consider K time intervals in a day and each of them is characterized by a scaling factor αh with h=0,…,K-1. In order to capture the sinusoidal shape of the traffic in a day, αh is evaluated with the following expression:(18)
α
h
=
1
,
if
h
=
0
,
1
-
2
h
K
1
-
α
m
i
n
,
h
=
1
,
…
,
K
2
,
1
-
2
K
-
h
K
1
-
α
m
i
n
,
h
=
K
2
+
1
,
…
,
K
-
1
,where α0 and αmin refer to the peak traffic and the minimum traffic scenario, respectively.The parameterαh affects the SFC arrival rate and the bandwidth requested. In particular we have the following expression for the SFC request rate λh and the minimum and the maximum requested bandwidths βhmin and βhmax, respectively, in the interval h (h=0,…,K-1):(19)λh=αhλ,βhmin=αhβmin,βhmax=αhβmax.Next we evaluate the performance of SFC planner proposed in Section 4 in dynamic traffic scenario and for parameter values βmin=500Mbps, βmax=1 Gbps, λ=1 rich/min, and μ=1/15 min−1. We also assume K=24 with traffic change and consequently application of the consolidation algorithm every hour.Finally we consider servers whose power consumption is characterized by the expression (17) with parameters Pmax=1000 W and Cs=10 Gbps.We report the SFC blocking probability as a function of the average number of offered SFC requests during the PHI (λ/μ) in Figure 9. We show the results in the case of basic link capacity scenario and in the ones obtained considering a capacity of the links that is twice and four times higher than the basic one. We consider the case of server with no rate adaptive power consumption (a=1). As we can observe, when the offered traffic is low, the degradation in terms of SFC blocking probability introduced by the consolidation technique increases. In fact in this low traffic scenario, more resource consolidation is possible with the consequence of higher SFC blocking probabilities. When the offered traffic increases the blocking probability with or without applying the consolidation technique does not change much because the network is heavily loaded and only few servers can be turned off. Furthermore, as we can expect, the blocking probability decreases when the links capacity increases. The performance loss due to the application of the consolidation technique is what we have to pay in order to obtain benefits in terms of power saved by turning off servers. The curves in Figure 10 compare the power consumption percentage savings that we can achieve in the cases a=0.1 and a=1. The results show that when the offered traffic decreases and the link capacity increases, higher power consumption saving can be achieved. The reason is that we have more resources on the links and less loaded VMs that allow for a higher number of VM migrations and resource consolidation. The other result to notice is that the use of rate adaptive servers reduces the power consumption saving when we perform resource consolidation. This is due to the lower value Pidle of the constant power consumption of the server that leads to lower power consumption saving when a server is switched off.Figure 9
SFC blocking probability as a function of the average number of SFCs offered in the PHI for the cases in which the consolidation technique is applied and it is not. The server power consumption is constant (a=1).Figure 10
The power consumption percentage saving achieved with the application of the consolidation technique versus the average number of SFCs offered in the PHI. The casesa=1 and a=0.1 are considered.


## 5.1. Offline SFC Scheduling

In the offline case we assume that a given numberT of SFC requests are a priori known. For the case study previously described we apply the MASRN heuristic proposed in Section 3.3. We report the percentage of the dropped SFCs in Figure 7 as a function of the offered number of SFCs. We report the curve for the basic scenario and the ones in which the link capacities are doubled, quadrupled, and increased per ten times, respectively. From Figure 7 we can see how, in order to have a dropped SFC percentage lower than 10%, the number of SFCs requests has to be smaller than 60 in the case of basic scenario. This remarkable blocking is due to the shortage of network capacity. In fact we can notice from Figure 7 how the dropped SFC percentage significantly decreases when the link bandwidth increases. For instance, when the capacity is quadrupled, the network infrastructure is able to accommodate up to 180 SFCs without any loss.Figure 7
Dropped SFC percentage as a function of the number of SFCs offered. The four curves are reported for the basic scenario case and the ones in which the link capacities are doubled, quadrupled, and increased by 10 times.This is confirmed in Figure8 where we report the number of Vcores occupied in the servers in the case of T=360. Each of the servers is represented on the x-axis with the identification (ID) of Figure 5. We also show in Figure 8 the number of Vcores allocated to each firewall, load balancer, and VPN encryption VNF with the blue, green, and red colors, respectively. The basic scenario case and the ones in which the link capacity is doubled, quadrupled, and increased by 10 times are reported in Figures 8(a), 8(b), 8(c), and 8(d), respectively. From Figure 8 we can notice how the MASRN heuristic works correctly by guaranteeing a uniform occupancy of the servers in terms of total number of Vcores used. We can also notice how the firewall VNF is the one needing the higher number of Vcores allocated. That is a consequence of the higher processing time that the firewall VNF requires with respect to the load balancer and VPN encryption VNFs.Figure 8
Number of allocated Vcores in each server. The number of Vcores for firewall, load balancer, and encryption VPN VNFs are represented with blue, green, and red colors.
(a)
(b)
(c)
(d)


## 5.2. Online SFC Scheduling

The numerical results are achieved in the following traffic scenario. The traffic pattern we consider is supposed to be sinusoidal with a peak value during daytime and minimum value during nighttime. We also assume that SFC requests follow a Poisson process and the SFC duration time is distributed according to an exponential distribution. The following parameters define the SFC requests in the Peak Hour Interval (PHI):(i)
λ is the arrival rate of SFC requests;(ii)
μ is the termination rate of an embedded SFC;(iii)
[βmin,βmax] is the range in which the bandwidth request for an SFC is randomly selected.We consider K time intervals in a day and each of them is characterized by a scaling factor αh with h=0,…,K-1. In order to capture the sinusoidal shape of the traffic in a day, αh is evaluated with the following expression:(18)
α
h
=
1
,
if
h
=
0
,
1
-
2
h
K
1
-
α
m
i
n
,
h
=
1
,
…
,
K
2
,
1
-
2
K
-
h
K
1
-
α
m
i
n
,
h
=
K
2
+
1
,
…
,
K
-
1
,where α0 and αmin refer to the peak traffic and the minimum traffic scenario, respectively.The parameterαh affects the SFC arrival rate and the bandwidth requested. In particular we have the following expression for the SFC request rate λh and the minimum and the maximum requested bandwidths βhmin and βhmax, respectively, in the interval h (h=0,…,K-1):(19)λh=αhλ,βhmin=αhβmin,βhmax=αhβmax.Next we evaluate the performance of SFC planner proposed in Section 4 in dynamic traffic scenario and for parameter values βmin=500Mbps, βmax=1 Gbps, λ=1 rich/min, and μ=1/15 min−1. We also assume K=24 with traffic change and consequently application of the consolidation algorithm every hour.Finally we consider servers whose power consumption is characterized by the expression (17) with parameters Pmax=1000 W and Cs=10 Gbps.We report the SFC blocking probability as a function of the average number of offered SFC requests during the PHI (λ/μ) in Figure 9. We show the results in the case of basic link capacity scenario and in the ones obtained considering a capacity of the links that is twice and four times higher than the basic one. We consider the case of server with no rate adaptive power consumption (a=1). As we can observe, when the offered traffic is low, the degradation in terms of SFC blocking probability introduced by the consolidation technique increases. In fact in this low traffic scenario, more resource consolidation is possible with the consequence of higher SFC blocking probabilities. When the offered traffic increases the blocking probability with or without applying the consolidation technique does not change much because the network is heavily loaded and only few servers can be turned off. Furthermore, as we can expect, the blocking probability decreases when the links capacity increases. The performance loss due to the application of the consolidation technique is what we have to pay in order to obtain benefits in terms of power saved by turning off servers. The curves in Figure 10 compare the power consumption percentage savings that we can achieve in the cases a=0.1 and a=1. The results show that when the offered traffic decreases and the link capacity increases, higher power consumption saving can be achieved. The reason is that we have more resources on the links and less loaded VMs that allow for a higher number of VM migrations and resource consolidation. The other result to notice is that the use of rate adaptive servers reduces the power consumption saving when we perform resource consolidation. This is due to the lower value Pidle of the constant power consumption of the server that leads to lower power consumption saving when a server is switched off.Figure 9
SFC blocking probability as a function of the average number of SFCs offered in the PHI for the cases in which the consolidation technique is applied and it is not. The server power consumption is constant (a=1).Figure 10
The power consumption percentage saving achieved with the application of the consolidation technique versus the average number of SFCs offered in the PHI. The casesa=1 and a=0.1 are considered.


## 6. Conclusions

The aim of this paper has been to propose heuristics for the resource dimensioning and the routing of Service Function Chain in network architectures employing the Network Function Virtualization technology. We have introduced the optimization problem that has the objective of minimizing the number of SFCs offered and the compliance of server processing and link bandwidth capacity. With the problem being NP-hard, we have proposed the Maximizing the Accepted SFC Requests Number (MASRN) heuristic that is based on the uniform occupancy of the server and link resources. The heuristic is also able to dimension the Vcores of the servers by evaluating the number of Vcores to be allocated to each VNF instance.An SFC planner has been already proposed for the dynamic traffic scenario. The planner is based on a consolidation algorithm that allows for the switching off of servers during the low traffic periods. A case study has been analyzed in which we have shown that the heuristics works correctly by uniformly allocating the server resources and reserving a higher number of Vcores for the VNFs characterized by higher packet processing time. Furthermore the proposed SFC planner allows for a power consumption saving dependent on the offered traffic and varying from 10% to 70%. Such a saving is to be paid with an increase in SFC blocking probability. As future research we will propose and investigate Virtual Machine migration policies allowing for the achievement of a right trade-off between power consumption saving and SFC blocking probability degradation.



---

*Source: 7139852-2016-04-24.xml*