Sage Journals: Discover world-class research

Abstract

Network Function Virtualization addresses the defect of traditional middleboxes and enables operators to implement new services through a process named Service Function Chain mapping. Service Function Chain is composed by a sequence of Virtual Network Functions (VNFs) which is deployed in shared platforms. Service Function Chain with parallel VNFs is proposed to reduce the delivery latency. In this paper, a multiple instances mapping scheme named MIM is proposed to resolve the performance bottleneck introduced by the imbalance of parallel VNFs. A integer programing model is established to describe the multiple instances mapping problem based on queuing theory, and a double layer Genetic Algorithm is used to allocate parallel VNFs with multiple instances. Simulation results show that the multiple instances mapping scheme can improve the performance of Service Function Chain with parallel VNFs effectively.

Keywords

Network Function Virtualization Virtual Network Function parallelism Service Function Chain mapping Genetic Algorithm

Introduction

Network Function Virtualization (NFV) deploys the network function on general platform through virtualization technology to address the defect of traditional dedicated middleboxes.¹ To provide complex services, the notion of Service Function Chain (SFC) is introduced, which is an ordered set of Virtual Network Functions (VNFs) connected by logical links as shown in Figure 1(a). And traffic can be steered through VNFs for processing as service provider required. Compared with traditional methods, NFV enables operators to implement new services through a process named SFC mapping, which maps the VNFs to High Volume Servers (HVSs).

Figure 1.

Parabox and NFP introduce VNF parallelism to improve the performance of SFC. (a) Traditional sequential SFC and (b) SFC with parallel VNFs.

The benefits of NFV are multifold and range from the operational cost reductions to faster deployment of SFC. However, it also introduces significant processing latency due to extra virtualization overhead. In this context, several efforts^2–6 have been proposed to address this problem. To achieve lower latency, most of the previous works choose to schedule traffic dynamically,² scale VNFs in a horizontal scope (i.e. VNF instances migration^2,3) or a vertical scope (i.e. instantiating more VNF instances^3,4). Moreover, some efforts are devoted to enhance the performance of SFC by accelerating individual VNF (e.g. ClickNP⁵ and NetBricks⁶) or packet delivery acceleration (e.g. DPDK,⁷ ClickOS,⁸ and NetVM⁹). Nevertheless, sequential composition of VNFs limits the performance ceiling of these works and provides additional opportunities for performance optimization. Instead, NFP¹⁰ and Parabox¹¹ break above limitation by enhancing the performance of SFC from a vertical scope. Both of them use dependency analysis module to ensure that VNFs share no dependency work in parallel. To implement the VNF parallelism, they duplicate packets and send replicas to parallel VNFs for processing, respectively. They also propose packet merger for merging replicas after processing. In this way, the processed packets of parallel VNFs are the same as the traditional sequential SFC, and VNF parallelism achieves significant latency reduction for real-world SFC.

However, since each VNF is varied from each other in the processing speed, the maximum throughput of parallel VNFs is determined by the slowest VNF, which is the bottleneck of the parallel VNF. An example of parallel VNFs is shown in Figure 1(b), assuming that the average processing time of network intrusion detection system (NIDS) is 0.2 ms, while that of the traffic shaper is 0.1 ms. In this case, when the traffic shaper completes processing tasks that target the packet replica, another packet replica is still being processed by NIDS. Thus, the total packet processing time is determined by the processing time of NIDS, i.e. 0.2 ms. Thus, the lowest efficiency VNF reduces the throughput of the parallel VNFs. To the best of our knowledge, none of existing SFC mapping algorithms has taken this issue into consideration.

To address this issue, we propose Multiple Instances Mapping scheme (MIM), which allows launching multiple instances for enhancing maximum throughput. As shown in Figure 2(a), instantiating an additional instance of NIDS is in another server for load balancing. Therefore, MIM improves the throughput of parallel VNFs. In order to minimize extra computing and network resources cost caused by launching multiple instances, we introduce queuing theory to evaluate the processing speed of multiple VNF instances, and the mapping decision is made for the best trade-off between high efficiency and resource consumption.

Figure 2.

SFC mapping scheme. (a) Multiple instances mapping of parallel SFC and (b) normal mapping scheme.

In this paper, we have made the following contributions: first, we designed a scheme that focuses on the mapping of SFC with parallel VNFs and solved the efficiency bottleneck caused by the difference of parallel VNFs. Second, we have designed a double layer Genetic Algorithm (GA) for multiple instances mapping that can dynamically add VNF instances based on the theoretical throughput of parallel VNFs and available substrate resources.

The rest of this paper is organized as follows: “Related work” section gives an overview of previous work on SFC mapping and SFC accelerating. In “Problem formulation” section, we formulate the processing latency of multiple instances and SFC mapping problem. Section “Algorithm design” presents our heuristic algorithm of multiple instances mapping problem. We analyze the performance of our mapping algorithm in “Evaluation” section and conclude our work in “Conclusion” section.

Related work

The performance of SFC has been widely studied in the notion of NFV. Li et al. presented a scheme named Quokka that realizes lower latency for end users by placing VNFs and scheduling traffic dynamically.² Huang et al. maximize the network throughput by horizontal scaling and vertical scaling while meeting end-to-end transmission delay requirements.³ Carpio et al. aim at improving load balancing of SFC and designing an algorithm for allocation and replication of VNFs.⁴

There has been considerable work focusing on the issue of SFC mapping. Mehraghdam et al. describe the SFC mapping problem as a mixed integer quadratic programing model. Three objective functions are proposed in the paper to maximize the remaining bandwidth resource, minimize server utilization, and minimize latency,¹² respectively. Cohen et al. describe the SFC mapping problem by integer linear programing and solve the mapping problem with the generalized assignment problem model for minimizing the resource consumption.¹³ Beck and Botero propose an algorithm for performing VNF forwarding graph composition and mapping simultaneously with the goal of maximizing remaining resources.¹⁴ Since SFC mapping is an NP-hard problem, there is a part of the work that applies heuristics to solve this problem. Ma et al. apply the particle swarm optimization algorithm to the mapping of SFC,¹⁵ and the experiment proves that the algorithm has achieved good results on the evaluation indexes such as acceptance rate and long-term resource utilization rate.

Although numerous studies have considered the high throughput SFC deployment, most of the existing approaches are mostly designed for sequential SFC, and rarely studies to resolve efficiency differences between VNFs through multiple instances mapping. Therefore, we propose MIM-GA algorithm to enhance the throughput of parallel VNFs while also considering resource cost of deployment.

Problem formulation

In this section, we introduce the substrate network and the SFC requests, and then formulate the relationship between VNF processing latency and number of instances by queuing theory. At last, we define SFC mapping process as Integer Programing with the objective function that enhances the throughput of parallel VNFs while minimizing the cost of SFC mapping.

VNF processing latency model

An SFC request R arrives and specifies an ordered sequence of VNFs. Suppose that there is a set of σ VNFs required in request, denoted as $N_{v} = {n_{1}^{v}, n_{2}^{v}, \dots, n_{σ}^{v}}$ . Parallel VNFs can be expressed as a set $N_{v}^{'} = {n_{1}^{v'}, n_{2}^{v'}, \dots, n_{τ}^{v'}} (N_{v}^{'} \subset N_{v})$ . Referring to the queuing theory, each $n_{m}^{v'} (m = 1, 2, \dots, τ)$ can be regarded as a M/M/1 queuing system (as shown in Figure 3). Packet arrives at the packet copier, and the replicas are sent to parallel VNFs with an average arrival rate λ. Each $n_{m}^{v'}$ processes the arriving packet in a processing rate μ_m, thus the utilization factor¹⁶ ρ_m is

ρ_{m} = \frac{λ}{μ_{m}}

(1)

Figure 3.

Illustration of the parallel VNF queuing system.

It is reasonable to assume that the average service rate¹⁶ of the queuing system (which is constituted by multiple instances of $n_{m}^{v'}$ ) is proportional to the number of instances of $n_{m}^{v'}$ . That is, the number of instances of $n_{m}^{v'}$ reaches k_m, and the corresponding service rate of the queuing system is increased to k_mμ_m, and ρ_m becomes

ρ_{m} = \frac{λ}{k_{m} μ_{m}}

(2)

The queuing theory model assumes that the input and output of the queuing system obey the “birth” and “death” process in probability theory. In this paper, “birth” means the arrival of a packet entering the $n_{m}^{v'}$ queuing system, and “death” represents the departure of a processed packet. We quote the state equilibrium equation from the queuing theory, and the probability of having η packets in the queuing system can be expressed as P_m_, _η

P_{m, η} {\begin{array}{l} \frac{λ / μ_{m}}{η!} P_{m, η} (0 \leq η \leq k_{m}); \\ \frac{λ / μ_{m}}{k_{m}! k_{m}^{η - k_{m}}} P_{m, η} (k_{m} \geq η); \end{array}

(3)

Among them, P_m_,0 is the probability that there is no packet in the $n_{m}^{v'}$ queuing system. According to the conclusion of previous work,¹⁶ P_m_,0 is expressed as

P_{m, 0} = 1 / (1 + \sum_{η = 1}^{k_{m - 1}} \frac{λ / μ_{m}^{η}}{η!} + \frac{λ / μ_{m}^{k_{m}}}{k_{m}!} \frac{1}{1 - λ / k_{m} μ_{m}})

(4)

Defining the expected value of the packets in the queue (excluding the packet being processed) as Lq_m, which is expressed as

L q_{m} = \sum_{n = 0}^{\infty} (n - k_{m}) P_{m, η}

(5)

According to the little formula,¹⁶ equation (6) represents average queuing latency of each packet. And the average latency of each packet replica in $n_{m}^{v'}$ 's queuing system is expressed as the sum of the packet’s average processing and the queuing latency, which is indicated in equation (7).

W q_{m} = \frac{L q_{m}}{λ}

(6)

W_{m} = W q_{m} + \frac{1}{μ_{m}}

(7)

SFC mapping model

The substrate network and the virtual network (i.e. SFC request) are denoted by G_s = (N_s, L_s) and G_v = (N_v, L_v), respectively. Among them, N_s is the set of substrate (i.e. HVS) nodes, and L_v/L_s represents the virtual/substrate link set. SFC mapping problem is defined by a mapping $M : G_{v} (N_{v}, L_{v}) \to G_{s} (N_{s}^{'}, L_{s}^{'})$ , where $N_{s}^{'} \in N_{s}$ and $L_{s}^{'} \in L_{s}$ . SFC mapping requires that the available resource satisfy the virtual node resource demands and virtual link resource demands; Figure 2(b) shows the mapping process of an SFC. The available computing resource owned by each substrate node $n_{j}^{s} \in N_{s}$ is presented as C_j (i.e. the value in each server in Figure 2(b)). Similarly, computing resource demand of u-th virtual node $n_{u}^{v} \in N_{v}$ is denoted as c_u (i.e. the value on each VNF in Figure 2(b)). Each substrate link $l_{i, j}^{s} \in L_{s} (1 \leq i \leq | N_{s} |, 1 \leq j \leq | N_{s} |, i \neq j)$ associated with bandwidth capacity, which is expressed as $B_{i, j}^{s}$ (i.e. the value on each substrate link in Figure 2(b)), and the bandwidth demand of each virtual link $l_{u, h}^{v} (1 \leq u \leq | N_{v} |, 1 \leq n \leq | N_{v} |, u \neq n)$ presents as $b_{u, h}^{v}$ (i.e. the value on each virtual link in Figure 2(b)). Let $x_{n_{i}^{s}}^{n_{u}^{v}}$ be a 0–1 integer variable, indicating that the VNF node $n_{u}^{v}$ is launched in the substrate node $n_{i}^{s}$ . $f_{n_{i}^{s}, n_{j}^{s}}^{n_{u}^{v}, n_{h}^{v}}$ is also a 0–1 integer variable, which represents the virtual link l_u_, _h is mapped to the substrate link l_i_, _j . And as mentioned before, k_u represents instances number of $n_{u}^{v'}$ .

Constraints

Multiple instances mapping relaxes the constraint of one-to-one mapping between parallel virtual nodes and substrate nodes, constraint (8) represents that the parallel VNF $n_{u}^{v}$ mapped to k_u HVS (i.e. generating k_u instances for $n_{u}^{v}$ ). Constraint (9) limits a non-parallel VNF can only be mapped to a HVS.

\sum_{n_{i}^{s} \in N_{s}} x_{n_{i}^{s}}^{n_{u}^{v}} = k_{u}, \forall n_{u}^{v} \in N_{v}^{'}

(8)

\sum_{n_{i}^{s} \in N_{s}} x_{n_{i}^{s}}^{n_{u}^{v}} = 1, \forall n_{u}^{v} \in N_{v} & n_{u}^{v} \notin N_{v}^{'}

(9)

Meanwhile, there is a computing resource constraint that makes the remaining computing resources of substrate node satisfy the requirement of the virtual node, that is

x_{n_{i}^{s}}^{n_{u}^{v}} . c_{u} \leq C_{j}, \forall n_{u}^{v} \in N_{v}

(10)

Constraint (11) is proposed to ensure that the mapped substrate links of each virtual link cannot be a circle

f_{n_{i}^{s}, n_{j}^{s}}^{n_{u}^{v}, n_{h}^{v}} . f_{n_{j}^{s}, n_{i}^{s}}^{n_{u}^{v}, n_{h}^{v}} \leq 1

(11)

Constraint (12) ensures that the connectivity of the physical links carrying the virtual link is consistent with $l_{u, h}^{v}$ (i.e. there is a path between the substrate nodes that launch $n_{u}^{v}$ and $n_{h}^{v}$ )

\begin{array}{l} \sum_{l_{i, j}^{s} \in L^{s}} f_{n_{i}^{s}, n_{j}^{s}}^{n_{u}^{v}, n_{h}^{v}} - \sum_{l_{j, i}^{s} \in L_{s}} f_{n_{j}^{s}, n_{i}^{s}}^{n_{u}^{v}, n_{h}^{v}} = x_{n_{i}^{s}}^{n_{u}^{v}} - x_{n_{i}^{s}}^{n_{h}^{v}}, \\ \forall n_{i}^{s} \in N_{s}, \forall l_{u, h}^{v} \in L_{v} \end{array}

(12)

Constraint (13) ensures that the sum of the bandwidth resource occupied by the virtual link l_u_, _h do not exceed the remaining bandwidth that the substrate link l_i_, _j can provide

\sum_{l_{u, h} \in L_{v}} f_{n_{i}^{s}, n_{j}^{s}}^{n_{u}^{v}, n_{h}^{v}} . b_{u, h}^{v} \leq B_{i, j}^{s}, \forall l_{i, j}^{s} \in L_{s}

(13)

Objectives

The revenue of accepting an SFC request can be formulated by equation (14)

Rev (G_{v}, t) = \sum_{l_{u, h}^{v} \in L_{v}} b_{u, h}^{v} + \sum_{n_{u}^{v} \in N_{v}} c_{u}

(14)

From service provider’s opinion, an SFC mapping algorithm should maximize the revenue and increase the utilization of the substrate network in a long time run. Therefore, like previous works,¹⁷ we defined a long-term average revenue to evaluate the benefits of accepting SFC

\lim_{Time - > \infty} \frac{\sum_{t = 0}^{Time} R e v (G_{v}, t)}{Time}

(15)

where t represents the time of accepting G_v.

Service provider allocates appropriate resources for accepting an SFC request, which can be defined as the cost of a mapping

\begin{array}{l} C ost (G_{v}, t) = \sum_{l_{i, j} \in L_{s}} \sum_{l_{u, h} \in L_{v}} f_{n_{i}^{s}, n_{j}^{s}}^{n_{u}^{v}, n_{h}^{v}} . b_{u, h}^{v} + \sum_{n_{i}^{s} \in N_{s}} \sum_{n_{u}^{v} \in N_{v}} x_{n_{i}^{s}}^{n_{u}^{v}} . c_{u} \end{array}

(16)

Based on equations (14) and (16), long-term revenue to cost radio is proposed to quantify the resource utilization of substrate network

\lim_{Time - > \infty} \frac{\sum_{t = 0}^{Time} R e v (G_{v}, t)}{\sum_{t = 0}^{Time} C o st (G_{v}, t)}

(17)

In the multi-tenant scenario, the acceptance rate is used to evaluate the proportion of requests successfully accepting

\lim_{Time - > \infty} \frac{\sum_{t = 0}^{Time} N u m (V R_{success})}{\sum_{t = 0}^{Time} N u m (V R_{all})}

(18)

where VR_success is the set of R accepted by substrate network, and VR_all is the set of all requests.

The optimization goal of this model is to minimize the maximum of parallel VNFs processing latency and minimize the substrate resources cost. The other objectives mentioned above will be used as evaluation indicators for the experiment. And the average latency W_m (m is the subscript of virtual node $n_{u}^{v}$ in $N_{v}^{'}$ ) of $n_{m}^{v'}$ ’s queuing system is expressed by equation (19), which can be derived from equation (2) to (7). The objective function is defined as equation (20), which is expressed as the sum of the maximum latency of $n_{m}^{v'}$ and the resource consumption

\begin{array}{l} W_{m} = \frac{\sum_{η = 0}^{\infty} (η - k_{m}) . \frac{{(\frac{λ}{μ_{m}})}^{η}}{k_{m}! k_{m}^{η - k_{m}}}}{(1 + \sum_{η = 1}^{k_{m - 1}} \frac{{(\frac{λ}{μ_{m}})}^{η}}{η!} + \frac{{(\frac{λ}{μ_{m}})}^{k_{m}}}{k_{m}} . \frac{1}{1 - \frac{λ}{k_{m}} . μ_{m}}) λ} + \frac{1}{μ_{m}} \end{array}

(19)

\min α (C (G_{v})) + β (\max {W_{m} | m = 1, 2, \dots, τ})

(20)

Algorithm design

The SFC mapping problem is an NP-hard problem, thus we introduce GA k to solve it. GA is a random search technology that draws on evolutionary ideas and can effectively solve optimization problems under complex constraints. We designed the MIM-GA algorithm to implement multiple instances mapping for parallel chains. The MIM-GA is divided into two phases: (1) optimization of the number of $n^{v'} m' s$ instances and (2) optimization of the mapping scheme.

Genetic algorithm

The basic GA is based on the group search technology, and evolves according to the principle of survival of the fittest, and finally obtains the optimal solution or the quasi-optimal solution. The GA first randomly generates multiple initial solutions for the optimization problem, which is commonly referred to as population, and each chromosome (i.e. individual of population) in the population is a feasible solution to the optimization problem. GA calculates the value of each chromosome fitness function and selects good chromosomes according to the principle of survival of the fittest. The selected elite chromosomes are then encoded into binary string, and the next-generation population is generated by randomly crossing the genes of the chromosome pairs and randomly mutating the genes of certain chromosomes. In this way, the population is evolved from generation to generation until the termination condition is met. The fitness function is usually set to the objective function of the problem.¹⁸

MIM-GA

MIM-GA is a double-layer GA.¹⁹ The first layer GA (Algorithm 2) aims at finding out an optimal number of instances of $n_{m}^{v'}$ (i.e. k_m mentioned before) under a constant upper limit K. And the second layer (Algorithm 3) generates a feasible mapping solution based on the result from first layer. The corresponding steps of MIM-GA are explained as follows.

Population initialization

The chromosome of first-layer GA is expressed as T = (t₁, t₂,…, t_τ), a t_m ∈ T represents the number of instances of $n_{m}^{v'}$ . Second-layer GA’s chromosome $V = (v_{1}, v_{2}, \dots, v_{| {n_{i}^{s} x | n_{i}^{s} \in N_{s} & \notin n^{v^{'}}} | + sum (T)})$ represents the mapping relationship between the virtual nodes and the substrate nodes. Where $| {n_{i}^{s} | n_{i}^{s} \in N_{s} & \notin n^{v^{'}}} | + sum (T)$ is the total number of instances that need to be instantiated in a mapping. It can be seen that the length of V depends on the T. v_r ∈ V indicates the server where the VNF is allocated. The sequence V is indefinite length, and the corresponding mapping relationship between the virtual node and the substrate node is determined according to whether the virtual nodes are parallel nodes. We illustrate the representation of two layer chromosomes in Figure 4. There are three parallel VNFs in the SFC as shown in Figure 4(a), and Figure 4(b) shows a chromosome of first layer MIM-GA (i.e. T), and a chromosome of second layer of MIM-GA is represented as V. As can be seen, length of chromosome V depended on the numbers in T, and V decides the mapping scheme of SFC. The mapping result of chromosome V is shown in Figure 4(c). Algorithm 1 describes the specific steps of initializing V, and the initialization of T is randomly under instance upper limit K as shown in Algorithm 2.

Figure 4.

The representation of the chromosome. (a) SFC; (b) chromosome initialization; and (c) mapping result.

Selection operator

The selection operator selects populations as parent populations by roulette algorithm according to selection probability.

Crossover operator

The crossover operator made two chromosome exchange substrings between two points which generated randomly.

Mutation operator

The mutation operator randomly selects five or fewer elements from the chromosome for mutation. In the process of mutation, a solution beyond the feasible domain may occur. For example, the element of V, which indicates the index of HVS that VNF map to, can be greater than maximum number of HVS or equal to 0. Or the element of T is greater than the instances upper limit K. For this case, the infeasible value produced by the mutation is modified to a random feasible value.

Fitness function

The objective function is used as a fitness function. After the chromosomes are crossover-operated, an infeasible solution which disobeys the constraint may occur. For example, the remaining resources of the substrate node are insufficient to instantiate the corresponding virtual node, or there is no path that satisfies the bandwidth constraint between the substrate nodes where the two VNF instances are located. When the fitness function calculates the fitness of the infeasible solution, it is uniformly taken as +∞ as a penalty function that does not satisfy the constraint. The preferred process uses the roulette wheel selection to select the descendants according to the cumulative probability of the fitness value.

Algorithm 1. Mapping solution initializationalgorithm.

Input: $G_{s} (N_{s}, L_{s}), G_{v} (N_{v}, L_{v}), T, N_{v}^{'}$

Output: V

1: set count = 0, V = $\emptyset$ ;

2: for each $n_{u}^{v} \in N_{v}$ do

3: calculate the candidate node set CN_u for $n_{u}^{v}$ ;

4: sort CN_u by sum of remaining CPU capacity and adjacent links’ bandwidth in descending order;

5: set NM_u = $\emptyset$ , j =1;

6: while j ≤ length(CN_j) do

7: $n_{j}^{s} = C N_{i} (j)$ ;

8: calculate the shortest path Path_u_, _u _–1 between $n_{j}^{s}$ and the node where $n_{u - 1}^{v}$ map to;

9: if Path_u_, _u _–1 exist then

10: add $n_{j}^{s}$ to NM_u;

11: end if

12: if $n_{u}^{v} \in n^{v'}$ then

13: if length(NM_u) ≥ T(u) then

14: mapflag = true;

15: break;

16: end if

17: else

18: if length(NM_u) ≥ 1 then

19: mapflag = true;

20: break;

21: end if

22: end if

23: j = j +1

24: end while

25: if! mapflag then

26: complement NM_i by random node in CN_u;

27: end if

28: add NM_u to V

29: end for

Algorithm 2. First layer of MIM-GA.

Input: $G_{s} (N_{s}, L_{s}), G_{v} (N_{v}, L_{v}), N_{v}^{'}, K$

Output: best mapping scheme

1: Initialization population A to specify numbers of parallel VNFs instances under limit K

2: calculate the fitness of each chromosome of A by second layer of MIM-GA and record best result as pBest, set global best result as gBest = pBest;

3: while count ≤ maximum number of iterations do

4: selection operator for population A to get B;

5: encoding population B to C;

6: crossover operator for population C to get D;

7: mutation operator for population D to get E;

8: decoding for population E and assigned to A;

9: calculate the fitness of population A by second layer of MIM-GA and update pBest;

10: if then fitness(pBest) < fitness(gBest)

11: gBest = pBest;

12: end if

13: count++

14: end while

15: if gBest == + ∞ then 8

16: reject the SFC request

17: else

18: execute gBest’s mapping solution and update G_s(N_s, L_s)

19: end if

Algorithm 3. Second layer of MIM-GA.

Input: $G_{s} (N_{s}, L_{s}), G_{v} (N_{v}, L_{v}), n^{v'}, K$

Output: best mapping scheme under instance limit from first layer MIM-GA

1: Initialization population F to allocate VNF in HVS by Algorithm 1

2: calculate the fitness of each chromosome of population F by equation (20) and record best result as pBest, set global best result as gBest = pBest;

3: while count ≤ maximum number of iterations do

4: selection operator for population F to get G;

5: encoding population G to H;

6: crossover operator for population H to get I;

7: mutation operator for population I to get K;

8: decoding for population K and assigned to F;

9: calculate the fitness of each chromosome of population F second by equation (20) and update pBest;

10: if then fitness(pBest) < fitness(gBest)

11: gBest = pBest;

12: end if

13: count++

14: end while

Evaluation

Simulation workloads

In order to verify the effectiveness of the MIM-GA algorithm, this paper evaluates the throughput of the parallel VNFs, long-term acceptance rate, and the long-term revenue to cost radio of the substrate network.

The substrate network topology is generated by GT-ITM with 100 nodes and approximately 500 links. Substrate nodes computing and network resources are subject to a uniform distribution of 50–100. It is assumed that the arrival of SFC request obeys an average arrival rate of 15 sets per unit time subjecting to poisson distribution, and an average service rate of 5 per unit time, which subject to negative exponential distribution. The number of VNFs per SFC request is subject to a uniform distribution of 2–5. The processing efficiency of the parallel nodes is randomly generated, subject to a uniform distribution of 10,000–15,000 packets per second, and the arrival rate of the packets is subject to a uniform distribution of 5000–80,000. The first layer MIM-GA has a population size of 100 and a maximum number of iterations of 500. The second layer MIM-GA sets the population size to 500 and the maximum number of iterations to 1000. The crossover probability, the selection probability, and the mutation probability are set to 0.7, 0.5, and 0.1, respectively. The simulation time is 10,000 time units, and the experimental data are recorded every 1000 time units.

Simulation results

To evaluate the effectiveness of our proposed algorithm, we compare its performance against the basic Greedy algorithm and Random Fit Algorithm (RFA) for single instance mapping of SFC with parallel VNFs.

Figure 5(a) shows the SFC requests acceptance rate with different SFC mapping strategies. We can see that MIM-GA outperforms other algorithms in acceptance ratio. It should be noted that MIM-GA maps multiple instances for each parallel VNF while other algorithms only map one. The strength of our proposed approach is that the mapping results are optimized over multiple iterations, which makes the utilization of resources more efficient, thus increasing the acceptance rate. Also, MIM-GA looks for mapping candidate nodes from the neighbors of the previous mapping substrate node in a greedy way at initialization stage, so that the fitness value of initial population has reached the level of greedy algorithm.

Figure 5.

Comparison between mapping results of different K. (a) Acceptance rate; (b) average revenue; (c) revenue/cost; and (d) maximum throughput of parallel VNFs.

We note that the revenue curve of MIM-GA displaying in Figure 5(b) is the highest of all. Due to the more SFC requests accepted with MIM-GA, the long-term average revenue is naturally higher than the other two algorithms.

Figure 5(c) shows the long-term revenue to cost ratio (i.e. R/C ratio) of service provider. The R/C ratio of MIM-GA algorithm is about 0.1–0.15 lower than that of the greedy and RFAs. Although we have demonstrated that MIM-GA achieves higher acceptance rates and average revenue in the long-term. However, due to the extra computing resources and bandwidth resources occupied by the multiple instances, the cost of MIM-GA is higher than other single instance mapping algorithm. And this indirectly leads to a drop in the R/C ratio curve.

The maximum throughput of parallel VNFs is shown in Figure 5(d). The multiple instances mapping can effectively improve the throughput of the parallel service chain under simulation and effectively solve the bottleneck problem of the parallel VNFs. In our proposed queuing theory latency model, the MIM-GA can increase throughput by nearly 30% compared to the single instance mapping.

Conclusion

This paper focuses on the performance bottleneck of SFC with parallel VNFs, and proposes a MIM scheme for parallel VNFs. The queuing theory is introduced to describe the relationship between the amount of VNF instances and the processing latency. Based on this, minimizing the resource cost of SFC mapping and the maximum latency of parallel VNFs are taken as the objective function, and an integer programing model is established. MIM-GA algorithm is proposed to perform MIM scheme. The algorithm is implemented by a two-layer GA. The first layer of MIM-GA optimals the number of parallel VNFs, and the second layer implements the mapping operation under resource constraints. Simulation results show that sacrificing some resources for launching multiple instances of parallel VNFs can effectively break through the performance bottleneck of SFCs with parallel VNFs and reduce the latency.

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Cui

Xie

Gao

, et al. Network functions virtualisation (NFV). In: SDN & OpenFlow world congress, Düsseldorf, Germany.

Jiang

Duan

, et al. Quokka: Latency-aware middlebox scheduling with dynamic resource allocation. J Netw Comput Appl 2017; 78: 253–266.

Huang

Liang

, et al. Throughput maximization of delay-sensitive request admissions via virtualized network function placements and migrations. In: 2018 IEEE international conference on communications (ICC), Kansas City, MO, USA, 22-24 May 2018, pp. 1–7. USA: IEEE.

Carpio

Dhahri

Jukan

VNF placement with replication for LOAC balancing in NFV networks. In: 2017 IEEE international conference on Communications (ICC), Paris, France, 21-25 May 2017, pp. 1–6. USA: IEEE.

Tan

Luo

, et al. ClickNP: Highly flexible and high-performance network processing with reconfigurable hardware. In: Conference on ACM SIGCOMM 2016 conference, Florianopolis, Brazil, 22-26 August 2016, pp. 1–14. USA: ACM.

Panda

Jang

, et al. NetBricks: Taking the V out of NFV. In: Usenix conference on operating systems design and implementation, Savannah, GA, USA, 2–4 November 2016, pp. 203–216. USA: USENIX.

Intel. Data plane development kit. http://dpdk.org/, 2014.

Martins

Ahmed

Raiciu

, et al. ClickOS and the art of network function virtualization. In: Usenix conference on networked systems design and implementation, Seattle, WA, USA, 2–4 April 2014, pp. 459–473. USA: USENIX.

Hwang

Ramakrishnan

Wood

NetVM: High performance and flexible networking using virtualization on commodity platforms. IEEE Trans Netw Serv Manage 2015; 12: 34–47.

10.

Sun

Zheng

, et al. NFP: Enabling network function parallelism in NFV. In: Conference of the ACM special interest group on data communication, Los Angeles, CA, USA, 21-25 August 2017, pp. 43–56. USA: ACM.

11.

Zhang

Anwer

Gopalakrishnan

, et al. ParaBox: Exploiting parallelism for virtual network functions in service chaining. In: Symposium on SDN research, Santa Clara, CA, USA, 3–4 April 2017, pp. 143–149. USA: ACM.

12.

Mehraghdam

Keller

Karl

Specifying and placing chains of virtual network functions. In: 2014 IEEE 3rd international conference on Cloud networking (CloudNet), Luxembourg, 8–10 October 2014, pp. 7–13. USA: IEEE.

13.

Cohen

Lewin-Eytan

Naor

, et al. Near optimal placement of virtual network functions. In: 2015 IEEE conference on Computer communications (INFOCOM), Kowloon, Hong Kong, China, 26 April-1 May 2015, pp. 1346–1354. USA: IEEE.

14.

Beck

Botero

JF.

Scalable and coordinated allocation of service function chains. Comput Commun 2016; 102: 78–88.

15.

Zhuang

Lan

Discrete particle swarm optimization algorithm for service chain mapping problem. J Chin Comput Syst 2017; 38: 1811–1817.

16.

Ashcroft

Introduction to operations research. Technometrics 1969; 10: 410–411.

17.

Cheng