Two-stage metaheuristic for reliable and balanced network function virtualization-enabled networks

Abstract

Network function virtualization (NFV) is a contemporary network architecture concept that integrates complex network functions into software-based virtual network functions (VNFs) instead of specialized hardware. Resource allocation for multiple service function chain requests (SFC) in NFV-enabled networks is a fundamental challenge for network providers. Several research studies have focused on this problem in detail. Specifically, SFC routing attempts to satisfy each request by assigning a path across data centers that places the ordered set of required VNFs. This paper formulates this problem as an SFC provisioning problem (SFCRP) with the two objectives of maximizing the number of accepted requests and balancing the utilization of network resources. To address this problem, a two-stage routing algorithm (2PRT) that integrates Yen’s algorithm and a genetic algorithm is proposed. The simulation results based on 12 scenarios that use three real-world networks and randomly generated requests indicate that the batch mode significantly enhances the acceptance rate compared to the existing methods.

Introduction

Traditional networks require dedicated hardware for the deployment of network devices such as intrusion detection system (IDS), network address translation (NAT), load balancer (LB), and firewall (FW). The main disadvantage of hardware-based deployment is related to network complexity. Due to the number of Service Function Chain (SFC) increase each day rapidly. A service function chain (SFC) is defined as a set of requested network services that can be represented as an ordered sequence. A promising technical network called network function virtualization (NFV) was proposed in 2012 to address the issues of the traditional network approach. NFV refers to the softwarization of network functions traditionally performed by specialized hardware appliances. Typically, a network function is deployed in the NFV environment, termed virtual network function (VNF). Because of resource limitations at network servers/links, one of the main challenges in NFV is to find the appropriate servers in the network for placing VNF and constructing optimal paths for SFC. This is the VNF placement and routing problem. Currently, most studies focus on the first problem, commonly referred to as the VNF placement. Given a network with limited resources (CPU, memory, and network bandwidth), a VNF placement solution needs to locate VNF on server nodes efficiently. In this study, we concentrate on the second issue, VNF scheduling, which finds an execution scheme for VNFs depending on their SFC.

Research gap and motivations

There have been numerous studies addressing the routing problem for services in virtualized networks. In their study (Kuo et al. 2018), the authors investigate the combined challenge of optimizing the placement of virtual network functions (VNFs) and the selection of network paths to enhance network utilization. They emphasize the critical role played by the relationship between link and server usage. To address this issue, they introduce a systematic approach for dynamically adjusting the appropriate usage of network links and servers for each network demand, taking into account network conditions and demand characteristics. This approach involves determining an optimal routing path length and deciding whether to allocate additional server resources or make use of existing server resources for each VNF in a service chain. The authors in Lukovszki et al. (2016) discuss a method for deploying middleboxes in a network in a way that is both near-optimal and incremental. They present an approach that aims to find an efficient and effective way to deploy these middleboxes while considering network optimization. However, these studies have some limitations as follows. First, most of the optimization models use a single physical machine to place VNFs of the same function (Kuo et al. 2018; Lukovszki et al. 2016) or even place all VNF of a chain (Moens and De Turck 2014). Second, most of the works only consider either the number of accepted requests or the end-to-end delay of each request.

Unlike exact methods, which aim to find optimal solutions through exhaustive searches, metaheuristics focus on efficiently exploring large solution spaces to discover near-optimal solutions. These algorithms are particularly valuable when dealing with problems for which finding the absolute best solution is computationally infeasible or highly time-consuming. Metaheuristics are characterized by their ability to balance exploration and exploitation of the solution space, allowing them to escape local optima and discover globally superior solutions. Several innovative metaheuristic algorithms which have been introduced in recent years draw inspiration from natural or social phenomena across diverse fields. Gharehchopogh (2023) present Harris hawks optimization, an improved algorithm inspired by the predatory behavior of hawks that enhances solution exploration. Slime mould algorithm (SMA) Gharehchopogh et al. (2023) exhibits adaptability, mirroring the foraging behavior of slime molds, allowing it to navigate complex and dynamic search spaces effectively. The authors in Shen et al. (2023) introduce the whale optimization algorithm, which draws its inspiration from the coordinated hunting behavior of whales and has been further improved for efficiency. Rime optimization algorithm is introduced in Su et al. (2023), which leverages the natural processes of frost formation to guide its optimization process. Colony predation algorithm (Tu et al. 2021) simulates the collective hunting strategies of predator colonies, enabling efficient exploration of solution spaces. Weighted mean of vectors (INFO) (Ahmadianfar et al. 2022) employs weighted vector manipulation to optimize solutions across diverse problem domains. Hunger games search (Yang et al. 2021) takes inspiration from the competitive dynamics of the hunger games to offer an innovative approach to optimization.

Metaheuristic algorithms have demonstrated their remarkable effectiveness in tackling practical real-world challenges. For instance, they have been successfully applied to tasks such as breast cancer prediction through a hybrid method combining the butterfly optimization algorithm and the ant lion optimizer (Thawkar et al. 2021), medical data feature selection utilizing a modified multi-objective Harris hawk optimizer (Piri and Mohapatra 2021), feature selection and COVID-19 image segmentation with the aid of boosting whale optimizer (Xing et al. 2023), addressing imbalanced data via the optimized SqueezeNet using the bald eagle search optimization approach (Sayed et al. 2021), and numerous other applications.

The mentioned algorithms are well suited for problems that involve real-number encoded solutions. Genetic algorithms (Reeves 2010), despite their long history, remain a suitable choice for addressing diverse combinatorial optimization problems with various encoding methods. Their strength lies in their ability to efficiently explore vast solution spaces, making them suitable for tasks involving multiple variables and constraints. Their ability to balance exploration and exploitation makes them a valuable tool for addressing a wide range of real-world optimization challenges, including machine learning, scheduling, and parameter tuning, demonstrating their effectiveness in finding near-optimal solutions.

Our contributions

This study addresses the following key problem in service function chaining routing: Given multiple SFCs, how can we design their routing from ingress to egress to maximize the number of accepted SFCs while maintaining the system’s operation.

Our contributions in this paper are summarized as follows:

• First, we formulated service function chain provisioning problem (SFCRP) in the case of multi-service chains as a multi-objective optimization problem. The first objective is maximizing the accepted SFC. The second one is to balance the links and node utilization. Our work differs from the above studies in combining the VNF scheduling with bandwidth optimization between multiple service chains. We solve a scheduling problem and network service assignment to network functions. Our work, however, can leverage the above works in guaranteeing bandwidth on the virtual links along the chain, interconnecting the virtual machines hosting the virtual functions.

• Second, we introduce a mixed integer linear programming (MILP) approach to systematically address the SFCRP and confirm its NP-hardness. MILP serves as a dependable benchmark for assessing the efficiency of our metaheuristic algorithms. Leveraging MILP’s capability to guarantee optimal or near-optimal solutions, it establishes a standard by which we can validate the results of our algorithms. Additionally, we highlight the inefficiency of MILP when applied to large-scale networks.

• Third, we introduce a two-level algorithm called Two-Phase Routing Algorithm (2PRA). In the first level, it identifies a set of k valid paths for each service chain. These paths may include cycles and must traverse server nodes containing the ordered virtual network functions. To construct a valid path, we create a multi-layer graph and employ Yen’s algorithm to find k shortest paths. In the second level, a genetic algorithm is employed to select a single path for each service chain and combine them into a single solution for the problem.

• Lastly, we conduct extensive simulations to validate the performances of the proposed algorithm on three real-world network topologies with various distributions. The results prove the effectiveness of 2PRA in solving SFCRP for practical physical networks.

Outline of the article

The rest of this paper is organized as follows. The formulation of the problem is presented in Sect. 3. In Sect. 2, a thorough discussion of related studies is provided. Our main contributions are shown in Sect. 5. In Sect. 6, we compare the proposed algorithm and other approaches. Finally, our future works will be discussed in Sect. 7.

Related works

Routing SFC issue has become one of the current hot problems. Some studies have used integer linear programming (ILP) (Tajiki et al. 2018; Wang et al. 2019; Kang et al. 2020; Varasteh et al. 2021), mixed integer linear programming (MILP) (Ghaznavi et al. 2017), and binary integer linear (BIL) models (Pei et al. 2018; Pei et al. 2018) for modeling. These models provide exact optimal solutions for this problem. However, the SFC routing problem is a typical NP-hard problem; these resolutions work only for small network instances. The authors used them in the experiments to further evaluate the proposed algorithms. Recently, researchers have begun to study approximate algorithms for designing effective routing. Although it is difficult to find the optimal solution, the approximate algorithm finds a near-optimal solution within an acceptable time. This study investigates the approximate algorithms for routing the SFC problem.

Heuristic and nature inspired algorithms

Several studies have considered heuristic-based approaches. In Pei et al. (2018), the authors proposed an efficient method to achieve load balancing and differentiated routing for SFC requests. Their algorithm consisted of two steps: They constructed a logical function graph (LFG) according to the relative costs in the first step, and the second step was to run a modified k-shortest path algorithm on the LFG to find the path with minimum resource consumption costs. Ghaznavi in Ghaznavi et al. (2017) solved the optimization of the number of VNF instances, placing these instances, and routing the traffic through the placed cases. They developed a local heuristic that routes traffic layer by layer. The problems of flow rerouting and server energy consumption in the SFC were considered in Tajiki et al. (2018). They presented a suboptimal heuristic called HNR to find a near-optimal solution for real-world networks

Wang et al. (2019) used a heuristic called segment routing for SFC steering based on backtracking and dynamic programming. Kang et al. (2020) proposed a VNF allocation model to improve the continuous available time of SFC by assuming the existence of known availability schedules. A heuristic algorithm is developed to address the VNF allocation problem. They also indicated that the proposed model, together with a consideration of routing, reduces the path length of requests. In Varasteh et al. (2021), the authors studied power-aware and delay-constrained joint VNF placement and routing problems. An online heuristic framework was proposed to tackle this problem by dividing it into two subproblems: VNF placement and routing. Wang et al. in Wang et al. (2021) presented the VNF mapping and scheduling problem, where both VNF remapping and VNF rescheduling are allowed, and the additional delays and migration costs incurred by VNF live migration and instantiation are considered. Two Tabu search-based heuristic algorithms were proposed to obtain suboptimal solutions. In Hamann and Fischer (2019), the authors addressed the selection, placement, and traffic routing of link-based approaches. They applied the k-shortest paths as a heuristic to find paths to reduce the input of the optimization problem.

Metaheuristics are among the best choices for solving NP-hard problems in different areas. When a metaheuristic algorithm is designed, exploration and exploitation should be considered. Recently, efforts have been devoted to developing metaheuristic approaches for routing SFC. For instance, in Pei et al. (2018), the authors formulated the VNF selection and chaining problem as a binary integer programming problem to minimize the end-to-end delay. They also proposed a novel deep learning-based strategy to solve this problem using intelligent routing learning and prediction. In Xing et al. (2019), an integer encoding gray wolf optimizer is proposed to solve virtual network function placement. However, they only considered one SFC request. In Shokouhifar (2021), fuzzy heuristic-based ant colony optimization (FH-ACO) was introduced to solve the VNF placement and routing problem. The high responsiveness of heuristics and the height solution quality of metaheuristics are combined in FH-ACO. The authors investigated the issue of online VNF-SF provisioning, in which requests are fulfilled one at a time without the knowledge of upcoming requests, in Khatiri et al. (2022). They used a concerted approach to solving the issue. A resource-balancing heuristic approach is suggested for minimizing the overall course and lowering the bottleneck. The authors described a mathematical model for placing and routing online virtual network service requests in Zahedi et al. (2022) (VNF-PRO). A VNF placement and routing evolutionary-based tunable fuzzy inference system (mcFIS) that responds to online queries quickly. The automatic rule tweaking of the mcFIS is then presented using a multi-objective evolutionary algorithm based on GA to maximize server load balancing, reduce overall power consumption, and increase the SFC acceptance rate.

Other intelligence-based algorithms

A deep reinforcement learning (DRL)-based algorithm was proposed in Fu et al. (2019) as a solution to deal with dynamic and complex SFC embedding scenarios in the IoT. In Quang et al. (2019), the authors addressed the allocation of a virtual network function-forwarding graph (VNF-FG) for realizing network services. They proposed a DRL framework based on a deep deterministic policy gradient to enhance the performance of DRL agents. In Pei et al. (2018), the authors studied the SFC routing with dynamic VNF placement in a geo-distributed cloud system. They aim to reduce redundant VNF instances and reduce total VNF running time. Their algorithm is a method commonly used by researchers and finds the deployment path with the fewest hops. However, all SFC chose their shortest path which can lead to a bottleneck in several links.

Game theory provides a natural mechanism to study the SFC routing problem owing to the non-cooperative behavior of users in NFV networks. In Le et al. (2021), the authors addressed SFC routing in NFV networks with coupled constraints in the Nash equilibrium (NE). An algorithm is formulated to determine the NE that minimizes user costs in the proposed game. The problems of resource allocation in NFV-enabled mobile edge cloud (MEC) networks, routing among access points (APs), and MEC servers were studied in Wu et al. (2019). A path-switching rule with proportionally shared operational costs is proposed to bring efficient costs. They presented a resource allocation algorithm by analyzing the behavior of APs using game theory. In Pham et al. (2017), the authors considered the VNF scheduling problem. To address this problem, they proposed an approach where the assignment of VNFs to resource nodes at each time slot can be considered an outcome of the one-to-one matching game.

Online routing algorithms for route flows with SFC requests were studied by Cao et al. (2014); Wang et al. (2016, 2017). The authors of Cao et al. (2014) proposed a novel competitive online algorithm for traffic steering (COAT). Using a layered graph, they updated the costs of the links and routed flows with SFC requests. Two deep reinforcement learning-based online algorithms were proposed in Ding et al. (2019) to reduce congestion probability and shorten transmission paths. In Zhou et al. (2019), a novel multitask deep learning (MTDL)-based architecture was proposed, which improves generalization by sharing related information for tasks. An MTDL-based routing algorithm was shown to compute routing paths with a minimum end-to-end delay for requests for SFC. The authors (Wang et al. 2016) study the dynamic provisioning of enterprise network services. They designed efficient online algorithms without requiring traffic rates to determine the number of instances of each type of VNF for provision.

When the servers in the network are overloaded, increasing the number of executed VNF instances is better for maintaining a network with high performance. In contrast, when the network is light, it is helpful to reduce the number of executed VNFs to decrease the cost. Unlike the studies mentioned above, we focus on selecting VNF instances to optimize two objectives: i) the number of accepted SFC requests and ii) guarantee load balancing in the network.

Problem statement

We consider a set of network services, each service with a chain of functions to traverse, and network resource constraints such as virtual network function (VNF) capacity of each node and transmission bandwidth of each link. The objective of the problem is to determine the path for each service to maximize the number of accepted services, balance links, and node utilization.

Input

• A network is represented as a graph G(V, E), where V is a set of n nodes and E stands for a set of links, respectively. Each node is either a server or PNF node. We assume that a VNF is only placed on the servers. Because the computational resource of a server node is finite, we denote $ca{p}_j$ as the memory resource of $v_j$, and $cp{u}_j$ as the CPU resource of $v_j$. Each link between nodes $v_j$ and $v_{j^{\prime }}$ is associated with transmission bandwidth $w_{j{j}^{\prime }}$.

• Let $F=\{f_1,f_2,\dots ,f_{|F|}\}$ be the set of VNFs as FW, IDS, proxy, LB, NAT, etc. Each service chain is defined as an ordered sequence VNF with some functions possibly repeated. All servers have both routing ability and processing capacities for operating multiple VNFs of different types.

• We define R as the set of m service chains/requests. Requests from users should always traverse a set of VNF instances in predefined orders to satisfy their demands. In this paper, a 6-tuple, $\{s^r,t^r,{\alpha }^r,r{m}^r,r{c}^r,F^r\}$ is used to represent SFC request r: (1) Source and destination substrate node for r, represented by $s^r$ and $t^r$; (2) The bandwidth demand is denoted as ${\alpha }_r$; (3) $r{m}^r$ is the memory cost to transfer data of r through a node; (4) $r{c}^r$ stands for the CPU resource consumed to run a required VNF; (5) The set of VNFs with dependency $F^r=\{f_1^r,f_2^r,\dots ,f_{k_r}^r\}$, $f_k^r\in F$. It is worth noting that VNF instances are only allowed to be deployed on servers, and PNF nodes do not need to process SFC requests; therefore, we ignore the CPU consumption on PNF nodes.

• In this paper, we assume functions are already placed on servers and focused on finding routing paths to meet certain quality of service. For simplicity, $c{n}_{\mathit{ij}}$ is a decision variable in which $c{n}_{\mathit{ij}}=1$ denotes that VNF $f_i$ is installed on node $v_j$, $c{n}_{\mathit{ij}}=0$ otherwise.

Output

• The path to route the user traffic for each request $p^r$. Because a path $p^r$ must passes some server nodes that contain required VNF instances, $p^r$ is split into multiple segments by these nodes. Then, $p^r$ can be defined as $p^r=\{{\mathbf{s}}^{\mathbf{r}}\}+\{p_1^{r,0},p_2^{r,1},\dots ,p_{l_{r,0}}^{r,0}\}+\{{\mathbf{p}}_{\ast }^{\mathbf{r},\mathbf{1}}\}+\{p_1^{r,1},\dots ,p_{l_{r,1}}^{r,1}\}+\cdots +\{{\mathbf{p}}_{\ast }^{\mathbf{r},{\mathbf{k}}_{\mathbf{r}}}\}+\{p_1^{r,k_r},\dots ,p_{l_{r,1}}^{r,k_r}\}+\{{\mathbf{t}}^{\mathbf{r}}\}$, where ${\mathbf{p}}_{\ast }^{\mathbf{r},\mathbf{k}}$ is the server that contains $f_k^r$.

• $CP=\{c{p}_j^{r,k}\}$ is a set of decision variables, where $c{p}_j^{r,k}=1$, iff VNF $f_k^r$ is executed on node $v_j$ for the request r, or ${\mathbf{p}}_{\ast }^{\mathbf{r},\mathbf{k}}=v_j$. $c{p}_i^{r,k}=0$ otherwise.

• $X=\{x_r\}$ is a set of decision variables, where $x_r=1$, if the rth SFC request is accepted, otherwise its value is zero.

• $Z=\{z_{j{j}^{\prime }}^{r,k}\}$ is a set of decision variable, where $z_{j{j}^{\prime }}^{r,k}=1$ if the kth segment of $p^r$ traverses link $(v_j,v_{j^{\prime }})$. Note that the kth segment is the sub-path between two servers contain $f_k^r$ and $f_{k+1}^r$, respectively. The 0th segment starts at $s^r$ and the $k^r$-th segment ends at $t^r$.

• $Y=\{y_j^{r,k}\}$ is a set of decision variable, where $y_j^{r,k}=1$ if the kth segment of $p^r$ traverses node $v_j$.

Constraints

• Each SFC request r must start from node $s^r$ and end at node $t^r$: $p_1^{r,0}=s^r$, $p_{l_{k_r}}^{r,k_r}=t^r$.

• The path $p^r$ traverses the servers that contain VNFs in the set $F^r$ in that order. With $p^r$ defined above, each intermediate node ${\mathbf{p}}_{\ast }^{\mathbf{r},\mathbf{k}}$ must have the corresponding VNF $f_k^r$ installed. In other words, if $f_k^r=f_i$ and ${\mathbf{p}}_{\ast }^{\mathbf{r},\mathbf{k}}=v_j$ then $c{n}_{\mathit{ij}}=1$.

  1

  $$\begin{array}{cc}& (f_k^r=f_i)\wedge ({\mathbf{p}}_{\ast }^{\mathbf{r},\mathbf{k}}=v_j)\Rightarrow c{n}_{\mathit{ij}}=1.\hfill \end{array}$$

• The link capacity constraint given in Eq. (2) enforces the capacity limits for all links. It ensures that the sum of the bandwidth from all requests routed on a path traversing link $(v_j,v_{j^{\prime }})$ cannot exceed the bandwidth on this link.

  2

  $$\begin{array}{c}\hfill \sum _{r=1}^m{x}_r{\alpha }_r\sum _{k=1}^{k_r+1}{z}_{j{j}^{\prime }}^{r,k}\le w_{j{j}^{\prime }}\forall j,j^{\prime }\in \{1,\dots ,n\}.\end{array}$$

• Equations (3) and (4) define the node resource constraints. It sums up the resource demands of all VNFs placed on a node and ensures that these do not exceed the resource capacities of this node.

  3

  $$\begin{array}{cc}& \sum _{r=1}^m{x}_{r}r{c}_r\sum _{k=1}^{k_r}c{p}_j^{r,k}\le cp{u}_j\forall j\in \{1,\dots ,n\},\hfill \end{array}$$

  4

  $$\begin{array}{cc}& \sum _{r=1}^m{x}_{r}r{m}_r\sum _{k=1}^{k_r}{y}_j^{r,k}\le ca{p}_j\forall j\in \{1,\dots ,n\}.\hfill \end{array}$$

Objectives

• Maximize the number of accepted SFCs

  5

  $$\begin{array}{c}\hfill \sum _{r=1}^m{x}^r⟶max.\end{array}$$

• Balance the links and nodes utilization

  6

  $$\begin{array}{c}\hfill max(U_1,U_2,U_3)⟶min,\end{array}$$ where

  7

  $$\begin{array}{c}\hfill U_1=max\left(\frac{{\sum }_{r=1}^m{x}_r{\alpha }_r{\sum }_{k=1}^{k_r+1}{z}_{j{j}^{\prime }}^{r,k}}{w_{j{j}^{\prime }}}\right),\end{array}$$

  8

  $$\begin{array}{c}\hfill U_2=max\left(\frac{{\sum }_{r=1}^m{x}_{r}r{c}_r{\sum }_{k=1}^{k_r}c{p}_j^{r,k}}{cp{u}_j}\right),\end{array}$$

  9

  $$\begin{array}{c}\hfill U_3=max\left(\frac{{\sum }_{r=1}^m{x}_{r}r{m}_r{\sum }_{k=1}^{k_r}{y}_j^{r,k}}{ca{p}_j}\right).\end{array}$$ In Eq. (7), the numerator denotes the consumed bandwidth, and the denominator represents the bandwidth on link $v_j{v}_{j^{\prime }}$. Equations (8) and (9) are calculated similarly as Eq. (7), and their value ranges are uniform between (0,1). It is obvious that Eq. (7) represents the resource utilization rates on each link, and Eqs. (8) and (9) show the resource utilization rates on nodes. Three values $U_1$, $U_2$, and $U_3$ can indicate the network’s resource bottlenecks. The objective is Eq. (6) to guarantee the load balancing between nodes and links using sufficient resources.

This paper’s list of important notations is provided in Table 1.

Table 1. Key notations

Symbol	Description
Physical network
$G=(V,E)$	V is a set of server or PNF
	E is a set of links
$w_{j{j}^{\prime }}$	the bandwidth of link $v_j{v}_{j^{\prime }}$
$ca{p}_j$	the memory resource of $v_j$
$cp{u}_j$	the CPU resource of $v_j$
F	the set of VNFs, $F=\{f_1,f_2,\dots ,f_{|F|}\}$
Service function chain
R	The set of SFC, $|R|=m$
$s^r$, $t^r$	ingress node and egress node of the request r
${\alpha }^r$	the bandwidth demand of the request r
$r{m}^r$	the required bandwidth of request r
$r{c}^r$	the required memory cost of request r
$F^r$	the ordered set of required VNFs of the request r
Binary variables
$x_r$	whether request r is accepted
$c{n}_{\mathit{ij}}$	whether VNF type $f_i$ is installed on server $v_j$
$c{p}_j^{r,k}$	whether VNF $f_k^r$ is executed on server $v_j$ for request r
$z_{j{j}^{\prime }}^{r,k}$	whether the kth segment of the path $p^r$ traverses link $(v_j,v_{j^{\prime }})$
$y_j^r$	whether the kth segment of the path $p^r$ traverses node $v_j$

An example of SFC is shown in Fig. 2. The network has five PNFs and three server nodes with four types of VNFs placed on them. Each type of VNF comprises multiple instances deployed in various network locations. $f_2$ and $f_3$ have two instances, and $f_1$ and $f_4$ have one instance. $f_1$ and $f_3$ are placed on $v_2$ node, $f_2$ and $f_4$ are placed on $v_7$ node, $f_2$ and $f_3$ are placed on $v_6$ node. Some examples of typical SFC are as follows: SFC1: $\{v_1,v_8,1,\{f_1,f_2\}\}$ and SFC2: $\{v_3,v_5,1,\{f_3\}\}$. For simplicity, we skip two fields, $r{m}^r$ and $r{c}^r$, along with all information related to node resources in these examples. For SFC1, any conventional shortest path algorithm returns a path $\{v_1,v_3,v_6,v_8\}$ that does not satisfy the SFC constraint; that is, the flow needs to be processed by $f_1$ just before it is processed by $f_2$. In Fig. 1, many paths satisfy the predefined order of SFC constraints. The solution $\{v_1,v_2,v_4,v_7,v_8\}$ will give the path a cost of 13, not the path with the minimum cost. However, we can see that $\{v_1,v_2,v_4,v_7,v_8\}$ satisfies the SFC constraint.

Fig. 1 [Images not available. See PDF.]

An example of SFC request

Fig. 2 [Images not available. See PDF.]

An example on SFC deployment

Integer linear programming formulation

In this section, we formulate an ILP model to exactly solve the SFC routing problem. In the ILP formulation, Eqs. (11), (12) and (13) are flow balance constraints for nodes of $p^r$ paths (with the information from cp variables to determine whether a node is an endpoint of a segment). Equations (14) and (15) ensure only servers that have the suitable VNF type in $F^r$ can serve request r, and only accepted requests need to be served. Equation (16) helps determining y from z. The resource utilizations of each node are evaluated in Eqs. (17), (18), and (19). As a result, Eqs. (20), (21) and (22) are resource capacity constraints. Equations (23)–(28) are used to calculate the utilization objective. Finally, the total objective is the aggregation of the two objectives by the weight parameter $\rho$.

The ILP formulation allows ILP solvers to provide exact optimal solutions to the problem. However, these solvers have exponential complexity and do not scale well to large instances. In our experiments, we use this method to calculate the optimal values for the test data and further evaluate our proposed algorithms. More detail is provided in Sect. 6.

Theorem 4.1

The optimization described by the aforementioned ILP model for service function chain provisioning problem (SFCRP) is NP-hard.

Proof

First, we apply the restrictions that $\rho =1$, which means that the resources bandwidth of links, CPU, and memory of nodes can be ignored in the optimization. Second, we apply the restriction that both numbers of supported VNF types in the network and the number of VNFs in the SFC are 1. Then, the problem is transformed into the capacitated facility location problem, which is known to be NP-hard (Nauss 1978). Hence, as the restricted case of the optimization is the general case of a known NP-hard problem, we prove that SFCRP is NP-hard as well.

10

$$\begin{array}{c}\hfill \rho \times \frac{{\sum }_{r=1}^m{x}^r}{m}+(1-\rho )\times (1-U)⟶max,\end{array}$$Subject to:

11

$$\begin{array}{cc}& c{p}_{s_r}^{r,0}=x_r\forall r\in R,\hfill \end{array}$$

12

$$\begin{array}{cc}& c{p}_{t_r}^{r,k_r+1}=x_r\forall r\in R,\hfill \end{array}$$

13

$$\begin{array}{cc}& \sum _{j=1}^n{z}_{\mathit{ij}}^{r,k}-\sum _{j^{\prime }=1}^n{z}_{j^{\prime }i}^{r,k}\hfill \\ \hfill & =c{p}_i^{r,k-1}-c{p}_i^{r,k}\forall v_i\in V,r\in R,k=\overline{1,k_r+1},\hfill \end{array}$$

14

$$\begin{array}{cc}& c{p}_i^{r,k}=0\forall r\in R,k=\overline{1,k_r},v_i\in V|c{n}_i^{f_k^r}=0,\hfill \end{array}$$

15

$$\begin{array}{cc}& \sum _{i=1}^{n}c{p}_i^{r,k}=x_r\forall r\in R,k=\overline{1,k_r},\hfill \end{array}$$

16

$$\begin{array}{cc}& y_j^{r,k}=\sum _{k=1}^{k_r+1}\sum _{j^{\prime }=1}^n{z}_{j^{\prime }j}^{r,k}\forall v_j\in V,\hfill \end{array}$$

17

$$\begin{array}{cc}& use{d}_{j{j}^{\prime }}^{\mathit{bw}}=\sum _{r\in R}{\alpha }_r\times \sum _{k=1}^{k_r+1}{z}_{j{j}^{\prime }}^{r,k}\forall (v_j,v_{j^{\prime }})\in E,\hfill \end{array}$$

18

$$\begin{array}{cc}& use{d}_j^{\mathit{mem}}=\sum _{r\in R}r{m}_r\times \sum _{k=1}^{k_r}{y}_j^{r,k}\forall v_j\in V,\hfill \end{array}$$

19

$$\begin{array}{cc}& use{d}_j^{\mathit{cpu}}=\sum _{r\in R}r{c}_r\times \sum _{k=1}^{k_r}c{p}_j^{r,k}\forall v_j\in V,\hfill \end{array}$$

20

$$\begin{array}{cc}& use{d}_{j{j}^{\prime }}^{\mathit{bw}}\le {\omega }_{j{j}^{\prime }}\forall (v_j,v_{j^{\prime }})\in E,\hfill \end{array}$$

21

$$\begin{array}{cc}& use{d}_j^{\mathit{mem}}\le ca{p}_j\forall v_j\in V,\hfill \end{array}$$

22

$$\begin{array}{cc}& use{d}_j^{\mathit{cpu}}\le cp{u}_j\forall v_j\in V,\hfill \end{array}$$

23

$$\begin{array}{cc}& U_1\ge \frac{use{d}_{j{j}^{\prime }}^{\mathit{bw}}}{{\omega }_{j{j}^{\prime }}}\forall (v_j,v_{j^{\prime }})\in E,\hfill \end{array}$$

24

$$\begin{array}{cc}& U_2\ge \frac{use{d}_j^{\mathit{mem}}}{ca{p}_j}\forall v_j\in V,\hfill \end{array}$$

25

$$\begin{array}{cc}& U_3\ge \frac{use{d}_j^{\mathit{cpu}}}{cp{u}_j}\forall v_j\in V,\hfill \end{array}$$

26

$$\begin{array}{cc}& U\ge U_1,\hfill \end{array}$$

27

$$\begin{array}{cc}& U\ge U_2,\hfill \end{array}$$

28

$$\begin{array}{cc}& U\ge U_3,\hfill \end{array}$$

29

$$\begin{array}{cc}& x_r\in \{0,1\},y_j^{r,k}\in \{0,1\},c{p}_j^{r,k}\in \{0,1\},z_{j{j}^{\prime }}^{r,k}\in \{0,1\}.\hfill \end{array}$$

Two-phase SFC routing algorithm

Due to the computational complexity of the proposed MILP model (NP-hard) and given the available computing processing power, the optimization model imposes a limitation on scaling to a large-scale data center network. Therefore, we divide the problem into two phases. The first phase aims to construct potential SFC paths for each request, then the second phase decides on accepted requests and selects corresponding paths among the candidates. The proposed method is called two-phase routing algorithm (2PRA) and is detailed in Algorithm 1.

First phase: candidate path construction

The best path for each request may not be the most suitable when combined with the SFC path of other requests. Thus, the first phase aims to find k potential paths for each SFC request.

Single SFC routing on multi-layer graph

A valid path for SFC request r may contain cycles and must cross server nodes that contain $f_1^r,f_2^r,\dots ,f_{k_r}^r$ in that particular order. Therefore, traditional path-finding algorithms such as Dijkstra cannot be applied directly to find a valid path. One popular approach to solve a single SFC routing problem is to convert the original network into a multi-layer graph. To find the route for SFC1: $\{v_1,v_4,1,\{f_1,f_2\}\}$, the network provided in Fig. 2 can be transformed into a multi-layer graph illustrated in Fig. 3.

Fig. 3 [Images not available. See PDF.]

Corresponding multi-layer graph for a SFC request

Because there are two requested VNFs, the path to find can be split into three segments: the first one goes from $v_1$ to a server node containing $f_1$, the second goes from that node to a server node containing $f_2$, then the last segment begins at the end of the second one and ends at $v_4$. Each segment is represented as one layer, a complete clone of the original graph. A good route from the first node to the last node of a segment is usually a loopless path inside the corresponding layer. The connection points between segments are chosen server nodes that contain the corresponding VNF type. The transfer between consecutive layers in the graph is limited by directed edges connecting two clones of the same server node with the required VNF type. For example, as the required VNF between the first and second segment is $f_1$, and only $v_6$ contains $f_1$, there is only one edge between the first and second layer, which runs from $v_6$ in the first layer to $v_6$ in the second layer.

Fig. 4 [Images not available. See PDF.]

GA encoding for SFCRP

We call $v_i^k$ the clone of $v_i$ in the kth layer of the multi-layer graph. If there exists a path that starts at $v_1^1$ ($v_1$ clone of the first layer) and ends at $v_4^3$ ($v_4$ clone of the final layer), it is guaranteed to be a suitable path to serve SFC1. For example, a valid path is: $\{v_1^1,v_3^1,v_6^1,v_6^2,v_8^2,v_7^2,v_7^3,v_4^3\}$, which travels through both $v_6$ (which has $f_1$) and $v_7$ (which has $f_2$). Additionally, each path on the multi-layer graph can easily be converted back to a network path: $\{v_1,v_3,v_6,v_8,v_7,v_4\}$.

Yen’s algorithm in a multi-layer graph

After the physical network has been converted to a multi-layer edge corresponding to a request r, the complex constrained SFC routing problem has been transformed into a simple path-finding problem between two endpoints. If we define a weight for edges to evaluate their influence toward the SFC routing problem, shortest path algorithms can be used to find the best SFC path for request r.

Since the most challenging factors in SFCRP are the resource allocation constraints, the considered weights directly reflect the resource capabilities of each node and each edge:

• Node weight is also considered in the shortest path algorithm. The inverted remaining memory capacity is set as the weight of $v_j$:

  30

  $$\begin{array}{c}\hfill \frac{ca{p}_j}{ca{p}_j-{\sum }_{r=1}^m{x}_{r}r{m}_r{\sum }_{k=1}^{k_r}{y}_j^{r,k}}.\end{array}$$

• Intra edges of each layer are clones of links on the physical network. The weight value of each edge $(v_j,v_{j^{\prime }})$ is set as its inverted remaining bandwidth:

  31

  $$\begin{array}{c}\hfill \frac{w_{j{j}^{\prime }}}{w_{j{j}^{\prime }}-{\sum }_{r=1}^m{x}_r{\alpha }_r{\sum }_{k=1}^{k_r+1}{z}_{j{j}^{\prime }}^{r,k}}.\end{array}$$

• Inter edges between layers actually represent server nodes chosen to run the required VNFs. An appropriate metric is inverted remaining CPU resource of corresponding node $v_j$:

  32

  $$\begin{array}{c}\hfill \frac{cp{u}_j}{cp{u}_j-{\sum }_{r=1}^m{x}_{r}r{c}_r{\sum }_{k=1}^{k_r}c{p}_j^{r,k}}.\end{array}$$

As the inverted forms of remaining resources are applied, the proposed weights effectively help the shortest path algorithm prioritize nodes and links with more remaining resources.

After the weights have been defined, the multi-layer graph becomes a weighted directed graph without negative weight, which allows the Dijkstra algorithm to find the shortest path. However, as stated earlier, the shortest path may not be the best to combine with other SFC requests’ paths. To increase the number of potential paths, we replace the Dijkstra algorithm with Yen’s algorithm (Yen 1970). The extended shortest path algorithm finds k loopless shortest paths instead of one. Paths with cycles are not considered since the cycles only make the path cost more resources than paths without cycles. The final output of this step is k SFC paths for each request.

Second phase: SFC selection

The first phase’s results are k potential paths for each of m SFC requests, which means a total of $m\times k$ paths are provided. The last problem is to decide which request will be accepted and which path among k ones will be used for that request. Since the network resources are lacking compared to all requests’ demands, some requests may be rejected.

In the second phase, these problems are solved by a genetic algorithm (GA) (Reeves 2010). It is a popular nature-based metaheuristic algorithm that can find good solutions for complex optimization problems in an acceptable time. To select both accepted requests and corresponding chosen paths consecutively, an integer encoding scheme is introduced in Fig. 4.

Assuming that the considered SFCRP must have servers 4 SFC requests, the number of paths for each request is $k=4$. In Fig. 4, each dashed border rectangle box contains four candidate paths for each request. The encoded individual is an integer vector $\mathbf{x}$ of length 4 (which equals the number of requests). Each element stores an index of the path chosen for the corresponding request. For example, $x_2=4$ means request $r_2$ is served by its 4th candidate path. Moreover, rejected requests’ corresponding position in vector $\mathbf{x}$ have a negative value of $-1$. In the example, request $r_1$ chooses its first path, $r_2$ chooses its fourth path, $r_3$ is rejected, and $r_4$ chooses its second path. To complete GA’s setup, the crossover operator is the uniform crossover, the mutation type is a 1-point mutation, and the selection strategy is elitism. Besides, to ensure all produced individuals provide possible solutions (which satisfy all resource constraints), a fix function is applied for each new individual to remove previously accepted requests until no constraint is violated randomly.

Table 2. Experimental setting parameters

Parameter	Value
	10-request	20-request	30-request
Computer specs	Xeon E-2124 G 3.40 GHz (16GB RAM)
Environment	Python on Ubuntu 16.04
Resource per node	[30–50]
Request required resource	[5–10]	[3–5]	[1–3]
Bandwidth per link	[80–100]
Request required bandwidth	[10–20]	[5–10]	[3–5]

Fig. 5 [Images not available. See PDF.]

Visualization of three real-world topologies

Experimental results

Experimental settings

All experiments are performed in a single Intel Xeon(R) E-2124 G 3.40 GHz CPU with 16 GB RAM running on Ubuntu Linux 16.04. No extra parallelization apart from the default NumPy acceleration is used. For an arbitrary server node v, both its available compute and storage resources are randomly generated in the range [30–50] units. For SFC requests, the required computational resource is generated in the range [5–10] units for 10-request instances, [3–5] for 20-request instances and [1–3] for 30-request instances. For an arbitrary link, the bandwidth is randomly generated in the range [80–100] Mb/s. The required bandwidth of SFC requests is in the range [10–20], [5–10] and [3–5] for 10,20, and 30-request instances, respectively. These parameters are summarized in Table 2.

Datasets

In the simulation, we use three real-world verified network topologies of varying sizes: NSF (Hei et al. 2004), CORONET continental United States (CONUS) (Velinska et al. 2018), and Cogent Communications (COGENT) (Zhang et al. 2020) topology. Some details of the topologies are shown in Fig. 5 and Table 3.

Table 3. Details of network topologies

Topology	Nodes	Edges
NSF	14	21
CONUS	75	99
COGENT	104	116

To evaluate the performance of the proposed 2PRA algorithm on networks with different VNF distributions, four types of instances are created with distinctive server nodes and VNF distributions:

• Uniform: 30% of the network nodes are randomly picked as server nodes. VNFs are also distributed randomly on server nodes. Each server has 2–3 VNFs.

• Rural: In this distribution, VNFs are assumed to stay mostly on nodes in the rural and suburban areas. That means server nodes are 70% lowest-degree nodes in the topology. VNFs also distribute sparingly on these nodes (each node only has one VNF).

• Urban: In contrast with the rural distribution, this script selects 30% highest-degree nodes as server nodes.

• Centers: The final distribution assumes the physical network follows a central topology: Only a few big data centers handle all services in the network. Consequently, only 10% highest-degree nodes are chosen as data centers, and all other nodes are PNF nodes.

Different SFCRP instances are generated for each network instance with 10, 20, or 30 requests. For each request set size, five problem instances are generated. Each SFC request demands 1–3 VNF types. Since we have three topologies, four server node distributions, three different request set sizes, and five instances for each type, the total number of instances is $3\times 4\times 3\times 5=180$.

We denote $x\_y\_z$ as the instance’s name with topology network x, distribution y, and z SFC requests. For example, $nsf\_ur\_30$ refers to the instance with NSF topology, urban distribution, and 30 SFC requests.

Evaluation criteria

To enhance the persuasiveness of the experiments, we compare 2PRA with five different solutions for the SFCRP problem:

• Greedy algorithm (GRE) is the objective value obtained by the heuristic on a multi-layer graph in Pei et al. (2018).

• Genetic programming (GP) is the objective value obtained genetic programming algorithm in Tam et al. (2023).

• MILP is a result using our MILP solver with a time limit of 2 h.

• Slime mould algorithm (SMA) (Gharehchopogh et al. 2023) is a representative of swarm algorithms introduced in section 1.

• Weighted Mean of vectors (INFO) (Ahmadianfar et al. 2022) is a new, flexible, and efficient method from the evolutionary algorithm group, also mentioned in section 1.

In the case of SMA and INFO, we essentially still use the 2PRA method, but the role of GA in phase 2 is replaced by SMA and INFO, respectively. On the other hand, since both algorithms operate on continuous encoding while the problem requires categorical variables, the encoding strategy using the probability distribution in Strasser et al. (2016) is applied.

The output result of a solution in this section refers to the number of accepted SFC requests and the links and nodes utilization. We also denote U as the second objective value (see the second part of Eq. 10).

Experiment results

In this study, we evaluated the performance of 2PRA in solving SFCRP using different experiments.

• We first assess the effectiveness of parameter k in the first phase on the overall performance of 2PRA.

• We further conduct an extensive analysis to evaluate the effectiveness of our proposed algorithm compared to the sequential approach using a multi-layer graph (GRE (Pei et al. 2018)), GP (Tam et al. 2023), SMA (Gharehchopogh et al. 2023), INFO (Ahmadianfar et al. 2022), and the optimal solution found by solving the ILP model.

Evaluate the influence of parameter k

In the second phase, all the parameters of GA were observed, chosen experimentally, and reported in Table 4. This experiment focused only on the number of candidates for each request k in the first phase. The results are aggregated in Table 5.

Table 4. Parameters of GA, SMA, and INFO in the second phase of 2PRA

Parameter	Algorithm
	GA	SMA	INFO	GP
Population size	50	50	50	50
Number of generations	100	100	100	100
Crossover probability	0.8	–	–	0.8
Mutation probability	0.05	–	–	0.05
z parameter	–	0.03	–	–
c parameter	–	–	2	–
d parameter	–	–	4	–
Maximum depth of tree	–	–	–	8

Table 5 shows the objective value with different k, where the bold values indicate the best results for each instance. The average number of accepted SFC requests is also shown in Fig. 6. The results show that the number of requests and the objective values have little to no effect on the performance for different k values. However, the most suitable k value depends heavily on the scale of the network topology. In the small-scale physical network (NSF topology), the results show little difference with different numbers of k-shortest paths. $k=5$ is sufficient to achieve the best results for several instances. However, the number of accepted SFC requests declines rapidly for large-scale physical network topologies (CONUS and COGENT) with $k=1$. This is far worse than for all other k, equal to $k=1$, and unsuitable. The number of accepted SFC requests was better achieved with $k=5,k=10$, $k=20$, $k=30$, and $k=40$, but they were significantly lower than the number of SFC requests. Small values for k lead to poor solution quality, independent of graph size. However, our results indicate a linear increase in the computation time with an increase of k.

Table 5. The performance results of 2PRA with different k for the number of accepted requests objective

Topology	Distribution	No. of requests	k (number of candidates)
			1	5	10	20	30	40
NSF	Centers	10	0.29	0.29	0.29	0.29	0.29	0.29
		20	0.28	0.28	0.28	0.28	0.28	0.28
		30	0.31	0.31	0.31	0.31	0.31	0.31
	Rural	10	0.34	0.35	0.35	0.35	0.34	0.35
		20	0.35	0.38	0.38	0.37	0.37	0.37
		30	0.38	0.40	0.40	0.40	0.39	0.39
	Uniform	10	0.35	0.37	0.37	0.37	0.37	0.36
		20	0.35	0.37	0.37	0.36	0.36	0.36
		30	0.40	0.41	0.41	0.41	0.41	0.41
	Urban	10	0.33	0.35	0.35	0.35	0.35	0.35
		20	0.35	0.38	0.38	0.37	0.37	0.37
		30	0.37	0.41	0.41	0.40	0.40	0.40
CONUS	Centers	10	0.36	0.43	0.46	0.45	0.46	0.47
		20	0.39	0.48	0.51	0.52	0.52	0.53
		30	0.45	0.53	0.55	0.56	0.57	0.58
	Rural	10	0.40	0.43	0.47	0.48	0.49	0.49
		20	0.45	0.49	0.50	0.51	0.52	0.52
		30	0.43	0.48	0.51	0.52	0.53	0.52
	Uniform	10	0.44	0.48	0.51	0.53	0.55	0.55
		20	0.48	0.54	0.56	0.57	0.58	0.58
		30	0.44	0.51	0.51	0.53	0.54	0.54
	Urban	10	0.39	0.48	0.49	0.52	0.53	0.53
		20	0.46	0.52	0.55	0.58	0.59	0.60
		30	0.44	0.50	0.51	0.54	0.54	0.55
COGENT	Centers	10	0.41	0.46	0.49	0.48	0.48	0.49
		20	0.46	0.53	0.54	0.55	0.55	0.55
		30	0.46	0.52	0.53	0.53	0.53	0.53
	Rural	10	0.33	0.33	0.33	0.33	0.33	0.33
		20	0.34	0.36	0.36	0.37	0.37	0.37
		30	0.36	0.37	0.38	0.38	0.38	0.38
	Uniform	10	0.37	0.39	0.41	0.41	0.41	0.41
		20	0.39	0.42	0.42	0.43	0.43	0.44
		30	0.42	0.45	0.46	0.46	0.46	0.46
	Urban	10	0.39	0.43	0.43	0.42	0.42	0.42
		20	0.42	0.46	0.46	0.47	0.47	0.47
		30	0.46	0.47	0.47	0.47	0.47	0.47

Fig. 6 [Images not available. See PDF.]

Acceptance rate of 2PRA with different k values

Comparison with the existing approach

In this experiment, we conduct a comprehensive comparison to prove the superior overall performance of our proposed algorithm 2PRA to the traditional sequential method—GRE in Pei et al. (2018), genetic programming—GP (Tam et al. 2023), slime mould algorithm (SMA) (Gharehchopogh et al. 2023), weighted mean of vectors (INFO) (Ahmadianfar et al. 2022), and MILP about the obtained the number of SFC requests, bandwidth, computational, and memory resources. We investigate 2PRA using $k=5$ for the small-scale network topology and $k=40$ for other network topologies. It is difficult to determine the appropriate weight coefficients ($\rho$) to be used when enough information about the problem is unavailable (this is a significant concern, particularly in real-world applications). Also, properly scaling the objectives requires considerable extra knowledge about the problem. Therefore, in our problem, we evaluate our proposed algorithm with the different coefficients $\rho =0.01$ and $\rho =0.5$. The coefficient is close to zero; it would say we only focus on the number of accepted SFC requests. In Tables 6 and 7, we report the output results from each of the above methods, where the bold values indicate the best results for each instance type. In most of these types of instances, the results from our algorithm perform well and closely approaches lower bound values regardless of distributions and the network’s topologies. With the coefficient $\rho =0.01$, our algorithm achieves better results on 32/36, 21/36, 34/36 and 35/36 instance types compared to GRE, GP, SMA, and INFO algorithms, respectively. These figures are respective 32/36, 30/36, 32/36, and 32/36 with the coefficient $\rho =0.5$. There are, however, some instances on 2PRA which do not achieve the best result, particularly from instances with CONUS topology. This is in line with our projection that this topology is more challenging for this approach, as the distribution’s nodes are so sparse. In addition, we can see that the efficiency of 2PRA becomes more pronounced when working with a large network (COGENT topology). Also notable is that the three variants of 2PRA (GA, SMA, and INFO) produce better results than two baseline algorithms (GRE and GP) in all types of instances in the COGENT topology. It proves 2PRA’s superior performance compared to the existing approaches. On the other hand, the proposed 2PRA version using GA performs better than SMA and INFO, even achieving optimal or near-optimal values on several instance types.

Table 6. Results of 2PRA for optimizing both objectives with ($\rho =0.5$) compared to the optimal values and other algorithms. $k=5$ for NSF instances and $k=40$ for others. The bold values indicate best results between our proposed 2PRA and others’ except the optimal

Topology	Distribution	No. of requests	Algorithm (with $\rho =0.5$)
			2PRA	GP	GRE	SMA	INFO	MILP
NSF	Centers	10	0.29	0.15	0.15	0.29	0.29	_
		20	0.28	0.16	0.16	0.26	0.26	_
		30	0.30	0.18	0.18	0.27	0.27	0.51
	Rural	10	0.35	0.28	0.28	0.35	0.34	_
		20	0.38	0.32	0.31	0.34	0.35	_
		30	0.40	0.32	0.32	0.35	0.36	0.54
	Uniform	10	0.37	0.29	0.28	0.37	0.37	_
		20	0.37	0.30	0.30	0.35	0.35	_
		30	0.41	0.33	0.33	0.37	0.38	0.54
	Urban	10	0.35	0.28	0.30	0.35	0.35	_
		20	0.38	0.28	0.28	0.35	0.36	_
		30	0.41	0.32	0.32	0.36	0.37	0.54
CONUS	Centers	10	0.47	0.49	0.44	0.43	0.43	_
		20	0.53	0.54	0.52	0.46	0.47	_
		30	0.58	0.58	0.57	0.51	0.52	_
	Rural	10	0.49	0.44	0.40	0.44	0.45	_
		20	0.52	0.48	0.46	0.46	0.47	_
		30	0.52	0.50	0.47	0.45	0.47	_
	Uniform	10	0.55	0.53	0.46	0.49	0.48	_
		20	0.58	0.56	0.52	0.51	0.52	_
		30	0.54	0.52	0.50	0.45	0.47	_
	Urban	10	0.53	0.53	0.48	0.47	0.48	_
		20	0.60	0.57	0.55	0.50	0.51	_
		30	0.55	0.55	0.54	0.46	0.48	_
COGENT	Centers	10	0.49	0.44	0.43	0.47	0.47	0.56
		20	0.55	0.48	0.48	0.50	0.51	_
		30	0.53	0.47	0.47	0.49	0.51	_
	Rural	10	0.33	0.28	0.25	0.32	0.34	_
		20	0.37	0.29	0.27	0.35	0.35	_
		30	0.38	0.30	0.29	0.33	0.34	0.54
	Uniform	10	0.41	0.36	0.30	0.38	0.39	_
		20	0.44	0.35	0.32	0.39	0.41	_
		30	0.46	0.38	0.40	0.40	0.41	_
	Urban	10	0.42	0.37	0.35	0.41	0.41	_
		20	0.47	0.42	0.38	0.44	0.44	0.58
		30	0.47	0.43	0.41	0.45	0.45	0.79

Table 7. Results of 2PRA for optimizing both objectives with ($\rho =0.01$) compared to the optimal values and other algorithms. $k=5$ for NSF instances and $k=40$ for others. The bold values indicate best results between our proposed 2PRA and others’ except the optimal

Topology	Distribution	No. of requests	Algorithm (with $\rho =0.01$)
			2PRA	GP	GRE	SMA	INFO	MILP
NSF	Centers	10	0.44	0.26	0.26	0.44	0.43	0.44
		20	0.46	0.30	0.30	0.45	0.44	0.46
		30	0.54	0.36	0.36	0.48	0.49	0.54
	Rural	10	0.62	0.50	0.44	0.59	0.58	0.65
		20	0.68	0.60	0.54	0.62	0.64	0.70
		30	0.75	0.63	0.59	0.65	0.67	0.77
	Uniform	10	0.65	0.53	0.54	0.61	0.61	0.65
		20	0.68	0.55	0.55	0.64	0.65	0.70
		30	0.78	0.65	0.59	0.70	0.72	0.79
	Urban	10	0.58	0.53	0.50	0.58	0.58	0.61
		20	0.69	0.53	0.48	0.64	0.65	0.71
		30	0.76	0.61	0.55	0.67	0.69	0.78
CONUS	Centers	10	0.80	0.93	0.56	0.75	0.75	_
		20	0.94	0.99	0.68	0.86	0.88	_
		30	0.98	0.99	0.80	0.95	0.97	_
	Rural	10	0.85	0.83	0.61	0.81	0.80	_
		20	0.92	0.91	0.75	0.86	0.87	_
		30	0.95	0.96	0.71	0.86	0.89	_
	Uniform	10	0.97	0.97	0.71	0.90	0.89	_
		20	0.96	0.99	0.80	0.92	0.92	_
		30	0.96	0.98	0.73	0.85	0.88	_
	Urban	10	0.92	0.99	0.65	0.84	0.84	_
		20	0.99	0.99	0.71	0.94	0.95	_
		30	0.96	0.99	0.73	0.87	0.89	_
COGENT	Centers	10	0.87	0.85	0.63	0.85	0.84	0.93
		20	0.95	0.92	0.80	0.93	0.93	_
		30	0.96	0.94	0.81	0.94	0.94	_
	Rural	10	0.56	0.50	0.38	0.53	0.54	0.61
		20	0.66	0.53	0.48	0.61	0.63	0.7
		30	0.71	0.57	0.51	0.61	0.63	0.74
	Uniform	10	0.69	0.63	0.54	0.66	0.65	0.71
		20	0.79	0.64	0.57	0.72	0.74	_
		30	0.87	0.75	0.65	0.75	0.79	_
	Urban	10	0.77	0.67	0.59	0.73	0.73	0.79
		20	0.85	0.81	0.68	0.82	0.82	0.87
		30	0.88	0.84	0.76	0.84	0.85	0.89

The comparative analysis presented in Figs. 7, 8, and  9 provides valuable insights into the performance of our proposed algorithm (2PRA) in relation to established algorithms (GP, SMA, INFO, and GRE). The focus lies on both the number of accepted SFC requests and the obtained second objective value.

Specifically, when examining the enhancement in the number of accepted SFC requests in Figs. 7a, 8a, and 9a, 2PRA give the best results. Its performance surpasses that of other algorithms, showcasing its effectiveness in optimizing the acceptance of SFC requests. Across all instances, 2PRA achieves improvements, enhancing the number of accepted SFC requests by approximately 24.52, 12.85, 7.64, and 6.21% over GRE, GP, SMA, and INFO, respectively. This notable improvement is particularly emphasized in the NSF and COGENT topologies, suggesting that 2PRA is especially well suited for these network structures.

The results presented in Fig. 7b, 8b, and 9b underscore the superiority of 2PRA in achieving the highest values for the performance metric U across a majority of the tested instances. Note that the larger the value of $1-U$, the better the algorithm performs. Notably, GP shows comparatively poorer performance, indicating a potential limitation of its effectiveness in these scenarios. Interestingly, GRE performs at a level similar to GP, but with a slight advantage. A particularly noteworthy observation is that, even in scenarios characterized by sparse distribution nodes, 2PRA continues to outperform other algorithms. This suggests that the algorithm is adept at adapting to varying network conditions and resource availability, making it a versatile choice in practical deployment scenarios. For instances from these topologies, the average $1-U$ values further emphasize 2PRA’s dominance, with an average of 0.096. In comparison, GRE, GP, SMA, and INFO exhibit lower averages at 0.028, 0.043, 0.068, and 0.074, respectively. This substantial performance gap further emphasizes the efficacy of 2PRA in achieving superior results across diverse scenarios.

Tables 8 and 9 indicate that our 2PRA is strictly better than GP, GRE, SMA and INFO. Since we perform four consecutive comparisons, the Bonferroni correction is applied to the threshold: $0.05/4\approx 0.0125$. The p-values obtained by the Wilcoxon tests in all cases are less than 0.0125. As a result, the null hypothesis is rejected and the superior performance of 2PRA is confirmed.

Fig. 7 [Images not available. See PDF.]

Comparison of the improvement percentage about the number of accepted SFC requests and the obtained second objective value on the NSF topology

Fig. 8 [Images not available. See PDF.]

Comparison of the improvement percentage about the number of accepted SFC requests and the obtained second objective value on the CONUS topology’s instances

Fig. 9 [Images not available. See PDF.]

Comparison of the improvement percentage about the number of accepted SFC requests and the obtained second objective value on the COGENT topology’s instances

Table 8. Wilcoxon tests for comparisons between 2PRA, GRE and GP with $\rho =0.5$

Scenario	Ranks			Statistics
	Type	Direction	Instances
GRE - 2PRA	Negative	<	170	Z	$-$11.392
	Positive	>	10	(based on)	(positive ranks)
	Tie	=	0	p-value (2-tailed)	0.000
GP - 2PRA	Negative	<	158	Z	$-$10.499
	Positive	>	21	(based on)	(positive ranks)
	Tie	=	1	p-value (2-tailed)	0.000
SMA - 2PRA	Negative	<	14	Z	$-$10.981
	Positive	>	159	(based on)	(positive ranks)
	Tie	=	7	p-value (2-tailed)	0.000
INFO - 2PRA	Negative	<	8	Z	$-$11.041
	Positive	>	168	(based on)	(positive ranks)
	Tie	=	4	p-value (2-tailed)	0.000

Table 9. Wilcoxon tests for comparisons between 2PRA, GRE, and GP with $\rho =0.01$

Scenario	Ranks			Statistics
	Type	Direction	Instances
GRE - 2PRA	Negative	<	180	Z	$-$11.635
	Positive	>	0	(based on)	(positive ranks)
	Tie	=	0	p-value (2-tailed)	0.000
GP - 2PRA	Negative	<	134	Z	$-$7.419
	Positive	>	44	(based on)	(positive ranks)
	Tie	=	2	p-value (2-tailed)	0.000
SMA - 2PRA	Negative	<	5	Z	$-$11.228
	Positive	>	166	(based on)	(positive ranks)
	Tie	=	9	p-value (2-tailed)	0.000
INFO - 2PRA	Negative	<	0	Z	$-$11.374
	Positive	>	172	(based on)	(positive ranks)
	Tie	=	8	p-value (2-tailed)	0.000

Conclusions and future works

In this paper, we formulated service function chain provisioning problem(SFCRP) in the case of multi-service chains as a multi-objective optimization problem: maximizing the number of accepted SFC and balancing the links and node utilization. Since the popular sequential approach in the single service chain is inefficient to SFCRP, we present a two-phase algorithm called two-phase routing algorithm (2PRA). The first phase is to find k near-optimal solution for each service chain, and the second level combines each of k solutions for one solution of the problem. Extensive simulations have been conducted to validate the performances of the proposed algorithm on three real-world network topologies with various distributions. The results prove the effectiveness of 2PRA in solving SFCRP for practical physical networks.

While our study successfully formulates the SFCRP for multi-service chains as a multi-objective optimization problem and presents the efficient 2PRA algorithm, it is essential to acknowledge certain limitations. Our model is designed for static networks where all requests are known and consistent. This limitation restricts its applicability to dynamic networks characterized by varying and unpredictable requests.

In light of these limitations, our future research will focus on addressing the challenges posed by dynamic networks. A faster and more flexible algorithm tailored to dynamic environments will be developed, enabling our model to adapt to real-time changes in network conditions.

Furthermore, we recognize the potential for improvement in congestion avoidance strategies. Future work will explore leveraging combined information from multiple requests at the shortest path step to enhance traffic congestion avoidance mechanisms. This approach aims to optimize network performance and responsiveness to dynamic traffic patterns.

Funding

This research has been done under the research project QG.23.05 of Vietnam National University, Hanoi. Nguyen Thi Tam was funded by the Postdoctoral Scholarship Programme of Vingroup Innovation Foundation (VINIF), code VINIF.2023.STS.56. This work was sponsored by the Office of Naval Research (ONR) Global (ONRG) and the U.S. Army Combat Capabilities Development Command Indo-Pacific (DEVCOM Indo-Pacific), under grant number N62909-23-1-2018 for Huynh Thi Thanh Binh and Tran Huy Hung. The views and conclusions contained herein are those of the authors only and should not be interpreted as representing those of the U.S. Government. Tran Huy Hung was funded by Vingroup JSC and supported by the Master, PhD Scholarship Programme of Vingroup Innovation Foundation (VINIF), Institute of Big Data, code VINIF.2022.ThS.BK.04.

Data Availability

Source codes and datasets of this paper can be retrieved from the link: https://gitlab.com/tranhuyhung1998/nfv-static; https://drive.google.com/drive/folders/1fSw2_tTVrhJJoL8lRcBo0GQoHT2RH-x4?usp=drive_link.

Declarations

Conflict of interest

The authors have not disclosed any competing interests.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

Ahmadianfar, I; Heidari, AA; Noshadian, S; Chen, H; Gandomi, AH. Info: an efficient optimization algorithm based on weighted mean of vectors. Expert Syst Appl; 2022; 195, [DOI: https://dx.doi.org/10.1016/j.eswa.2022.116516]

Cao Z, Kodialam M, Lakshman T (2014) Traffic steering in software defined networks: Planning and online routing. In: Proceedings of the 2014 ACM SIGCOMM Workshop on Distributed Cloud Computing, pp. 65–70

Ding, R; Xu, Y; Gao, F; Shen, X; Wu, W. Deep reinforcement learning for router selection in network with heavy traffic. IEEE Access; 2019; 7, pp. 37109-37120. [DOI: https://dx.doi.org/10.1109/ACCESS.2019.2904539]

Fu, X; Yu, FR; Wang, J; Qi, Q; Liao, J. Dynamic service function chain embedding for nfv-enabled iot: a deep reinforcement learning approach. IEEE Trans Wirel Commun; 2019; 19, 1 pp. 507-519. [DOI: https://dx.doi.org/10.1109/TWC.2019.2946797]

Gharehchopogh, FS. An improved Harris hawks optimization algorithm with multi-strategy for community detection in social network. J Bionic Eng; 2023; 20, 3 pp. 1175-1197. [DOI: https://dx.doi.org/10.1007/s42235-022-00303-z]

Gharehchopogh, FS; Ucan, A; Ibrikci, T; Arasteh, B; Isik, G. Slime mould algorithm: a comprehensive survey of its variants and applications. Arch Comput Methods Eng; 2023; 30, 4 pp. 2683-2723. [DOI: https://dx.doi.org/10.1007/s11831-023-09883-3]

Ghaznavi, M; Shahriar, N; Kamali, S; Ahmed, R; Boutaba, R. Distributed service function chaining. IEEE J Sel Areas Commun; 2017; 35, 11 pp. 2479-2489. [DOI: https://dx.doi.org/10.1109/JSAC.2017.2760178]

Hamann M, Fischer M (2019) Path-based optimization of nfv-resource allocation in sdn networks. In: ICC 2019-2019 IEEE International Conference on Communications (ICC), pp. 1–6. IEEE

Hei, X; Zhang, J; Bensaou, B; Cheung, C-C. Wavelength converter placement in least-load-routing-based optical networks using genetic algorithms. J Opt Netw; 2004; 3, 5 pp. 363-378. [DOI: https://dx.doi.org/10.1364/JON.3.000363]

Holland, JH. Genetic algorithms. Sci Am; 1992; 267, 1 pp. 66-73. [DOI: https://dx.doi.org/10.1038/scientificamerican0792-66]

Kang, R; He, F; Sato, T; Oki, E. Virtual network function allocation to maximize continuous available time of service function chains with availability schedule. IEEE Trans Netw Serv Manag; 2020; 18, 2 pp. 1556-1570. [DOI: https://dx.doi.org/10.1109/TNSM.2020.3007712]

Khatiri, A; Mirjalily, G; Luo, Z-Q. Balanced resource allocation for vnf service chain provisioning in inter-datacenter elastic optical networks. Comput Netw; 2022; 203, [DOI: https://dx.doi.org/10.1016/j.comnet.2021.108717]

Kuo, T-W; Liou, B-H; Lin, KC-J; Tsai, M-J. Deploying chains of virtual network functions: on the relation between link and server usage. IEEE/ACM Trans Netw; 2018; 26, 4 pp. 1562-1576. [DOI: https://dx.doi.org/10.1109/TNET.2018.2842798]

Le, S; Wu, Y; Guo, Y; Del Vecchio, C. Game theoretic approach for a service function chain routing in nfv with coupled constraints. IEEE Trans Circuits Syst II Express Briefs; 2021; 68, 12 pp. 3557-3561.

Lukovszki, T; Rost, M; Schmid, S. It’s a match! near-optimal and incremental middlebox deployment. ACM SIGCOMM Comput Commun Rev; 2016; 46, 1 pp. 30-36. [DOI: https://dx.doi.org/10.1145/2875951.2875956]

Moens H, De Turck F (2014) Vnf-p: A model for efficient placement of virtualized network functions. In: 10th International Conference on Network and Service Management (CNSM) and Workshop, pp. 418–423. IEEE

Nauss, RM. An improved algorithm for the capacitated facility location problem. J Oper Res Soc; 1978; 29, 12 pp. 1195-1201. [DOI: https://dx.doi.org/10.1057/jors.1978.263]

Pei, J; Hong, P; Xue, K; Li, D. Resource aware routing for service function chains in sdn and nfv-enabled network. IEEE Trans Serv Comput; 2018; 14, 4 pp. 985-997. [DOI: https://dx.doi.org/10.1109/TSC.2018.2849712]

Pei, J; Hong, P; Xue, K; Li, D. Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system. IEEE Trans Parallel Distrib Syst; 2018; 30, 10 pp. 2179-2192. [DOI: https://dx.doi.org/10.1109/TPDS.2018.2880992]

Pei J, Hong P, Li D (2018) Virtual network function selection and chaining based on deep learning in sdn and nfv-enabled networks. In: 2018 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 1–6. IEEE

Pham, C; Tran, NH; Hong, CS. Virtual network function scheduling: a matching game approach. IEEE Commun Lett; 2017; 22, 1 pp. 69-72. [DOI: https://dx.doi.org/10.1109/LCOMM.2017.2747509]

Piri, J; Mohapatra, P. An analytical study of modified multi-objective Harris hawk optimizer towards medical data feature selection. Comput Biol Med; 2021; 135, [DOI: https://dx.doi.org/10.1016/j.compbiomed.2021.104558]

Quang, PTA; Hadjadj-Aoul, Y; Outtagarts, A. A deep reinforcement learning approach for vnf forwarding graph embedding. IEEE Trans Netw Serv Manag; 2019; 16, 4 pp. 1318-1331. [DOI: https://dx.doi.org/10.1109/TNSM.2019.2947905]

Reeves, CR. Genetic algorithms; 2010; Boston, Handbook of metaheuristics. Springer: pp. 109-139.

Sayed, GI; Soliman, MM; Hassanien, AE. A novel melanoma prediction model for imbalanced data using optimized squeezenet by bald eagle search optimization. Comput Biol Med; 2021; 136, [DOI: https://dx.doi.org/10.1016/j.compbiomed.2021.104712]

Shen, Y; Zhang, C; Gharehchopogh, FS; Mirjalili, S. An improved whale optimization algorithm based on multi-population evolution for global optimization and engineering design problems. Expert Syst Appl; 2023; 215, [DOI: https://dx.doi.org/10.1016/j.eswa.2022.119269]

Shokouhifar, M. Fh-aco: Fuzzy heuristic-based ant colony optimization for joint virtual network function placement and routing. Appl Soft Comput; 2021; 107, [DOI: https://dx.doi.org/10.1016/j.asoc.2021.107401]

Strasser, S; Goodman, R; Sheppard, J; Butcher, S. A new discrete particle swarm optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference; 2016; 2016, pp. 53-60.

Su, H; Zhao, D; Heidari, AA; Liu, L; Zhang, X; Mafarja, M; Chen, H. Rime: a physics-based optimization. Neurocomputing; 2023; 532, pp. 183-214. [DOI: https://dx.doi.org/10.1016/j.neucom.2023.02.010]

Tajiki MM, Salsano S, Shojafar M, Chiaraviglio L, Akbari B (2018) Energy-efficient path allocation heuristic for service function chaining. In: 2018 21st Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN), pp. 1–8. IEEE

Tam NT, Hung TH, Van Hanh P, Binh HTT (2023) Genetic programming for resource allocation in network function virtualization. In: 2023 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE

Thawkar, S; Sharma, S; Khanna, M; Kumar Singh, L. Breast cancer prediction using a hybrid method based on butterfly optimization algorithm and ant lion optimizer. Comput Biol Med; 2021; 139, [DOI: https://dx.doi.org/10.1016/j.compbiomed.2021.104968]

Tu, J; Chen, H; Wang, M; Gandomi, AH. The colony predation algorithm. J Bionic Eng; 2021; 18, pp. 674-710. [DOI: https://dx.doi.org/10.1007/s42235-021-0050-y]

Varasteh, A; Madiwalar, B; Van Bemten, A; Kellerer, W; Mas-Machuca, C. Holu: power-aware and delay-constrained vnf placement and chaining. IEEE Trans Netw Serv Manag; 2021; 18, 2 pp. 1524-1539. [DOI: https://dx.doi.org/10.1109/TNSM.2021.3055693]

Velinska J, Mishkovski I, Mirchev M (2018) Routing, modulation and spectrum allocation in elastic optical networks. In: 2018 26th Telecommunications Forum (TELFOR), pp. 1–4. IEEE

Wang, L; Mao, W; Zhao, J; Xu, Y. Ddqp: a double deep q-learning approach to online fault-tolerant sfc placement. IEEE Trans Netw Serv Manag; 2021; 18, 1 pp. 118-132. [DOI: https://dx.doi.org/10.1109/TNSM.2021.3049298]

Wang X, Wu C, Le F, Lau FC (2017) Online learning-assisted vnf service chain scaling with network uncertainties. In: 2017 IEEE 10th International Conference on Cloud Computing (CLOUD), pp. 205–213. IEEE

Wang X, Wu C, Le F, Liu A, Li Z, Lau F (2016) Online vnf scaling in datacenters. In: 2016 IEEE 9th International Conference on Cloud Computing (CLOUD), pp. 140–147. IEEE

Wang Y, Zhang X, Fan L, Yu S, Lin R (2019) Segment routing optimization for vnf chaining. In: ICC 2019-2019 IEEE International Conference on Communications (ICC), pp. 1–7. IEEE

Wu B, Zeng J, Ge L, Shao S, Tang Y, Su X (2019) Resource allocation optimization in the nfv-enabled mec network based on game theory. In: ICC 2019–2019 IEEE International Conference on Communications (ICC), pp. 1–7. IEEE

Xing, H; Zhou, X; Wang, X; Luo, S; Dai, P; Li, K; Yang, H. An integer encoding grey wolf optimizer for virtual network function placement. Appl Soft Comput; 2019; 76, pp. 575-594. [DOI: https://dx.doi.org/10.1016/j.asoc.2018.12.037]

Xing, J; Zhao, H; Chen, H; Deng, R; Xiao, L. Boosting whale optimizer with quasi-oppositional learning and Gaussian barebone for feature selection and covid-19 image segmentation. J Bionic Eng; 2023; 20, 2 pp. 797-818. [DOI: https://dx.doi.org/10.1007/s42235-022-00297-8]

Yang, Y; Chen, H; Heidari, AA; Gandomi, AH. Hunger games search: visions, conception, implementation, deep analysis, perspectives, and towards performance shifts. Expert Syst Appl; 2021; 177, [DOI: https://dx.doi.org/10.1016/j.eswa.2021.114864]

Yen, JY. An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Q Appl Math; 1970; 27, 4 pp. 526-530.MathSciNet ID: 253822[DOI: https://dx.doi.org/10.1090/qam/253822]

Zahedi, SR; Jamali, S; Bayat, P. Emcfis: evolutionary multi-criteria fuzzy inference system for virtual network function placement and routing. Appl Soft Comput; 2022; 117, [DOI: https://dx.doi.org/10.1016/j.asoc.2022.108427]

Zhang, S; Wang, X; Qian, X; Huang, M. An intelligent sdn-enabled ccn routing mechanism with community division. Trans Emerg Telecommun Technol; 2020; 31, 2 3698. [DOI: https://dx.doi.org/10.1002/ett.3698]

Zhou J, Hong P, Pei J, Li D (2019) Multi-task deep learning based dynamic service function chains routing in sdn/nfv-enabled networks. In: ICC 2019–2019 IEEE International Conference on Communications (ICC), pp. 1–6. IEEE