# A New Approach for Delivering Customized Security Everywhere: Security Service Chain

Authors: Yi Liu; Hong-qi Zhang; Jiang Liu; Ying-jie Yang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Security functions are usually deployed on proprietary hardware, which makes the delivery of security service inflexible and of high cost. Emerging technologies such as software-defined networking and network function virtualization go in the direction of executing functions as software components in virtual machines or containers provisioned in standard hardware resources. They enable network to provide customized security service by deploying Security Service Chain (SSC), which refers to steering flow through multiple security functions in a particular order specified by individual user or application. However, SSC Deployment Problem (SSC-DP) needs to be solved. It is a challenging problem for various reasons, such as the heterogeneity of instances in terms of service capacity and resource demand. In this paper, we propose an SSC-based approach to deliver security service to users without worrying about physical locations of security functions. For SSC-DP, we present a three-phase method to solve it while optimizing network and security resource allocation. The presented method allows network to serve a large number of flows and minimizes the latency seen by flows. Comparative experiments on the fat-tree and Waxman topologies show that our method performs better than other heuristics under a wide range of network conditions.


---

## Body

## 1. Introduction

Today’s security service delivery approach is limited in dynamics, flexibility, scalability, and efficient resource utilization. Firstly, security services are configured in static and inflexible ways, such as deploying hardware firewall and IDS in the key position of network. They are coupled with the underlying physical topology [1], making it difficult to deliver customized security services according to user requirements and network constraints. Secondly, reconfiguring existing security service requires time-intensive manual operations, making the approach often inflexible and hard to cope with changeable requirements. Thirdly, there is a serious waste of security resources. It is inefficient for flows from multiusers or multibusinesses to share hardware-based security devices since their positions are fixed. What is worse, security devices need to work at full capacity so as to serve incoming flows, especially burst flows in time.Recent research efforts on promising network technologies, such as software-defined networking (SDN) [2] and network function virtualization (NFV) [3], promise to revolutionize security service delivery approach. SDN decouples network control from forwarding and makes the former directly programmable [4], realizing the centralized network management. NFV moves network functions off proprietary hardware onto standard servers (e.g., ×86 based systems) in the form of virtual network function (VNF). This way of separating and abstracting functionalities from locations facilitates flexible orchestration of network functions [5]. Moreover, in the state of the art, VNFs can achieve approximate performance of hardware devices [6–8]. Together, SDN and NFV make networks and network devices agile [9].As a consequence, the concept of Security Service Chain (SSC) [10] has been proposed, which refers to an ordered set of security functions composing a logical security service that must be applied to packets or flows. With the help of fine-grained flow management originated from SDN and flexible function orchestration originated from NFV, deploying SSC becomes a promising way to deliver security service. By placing security functions in a topology independent way, it dynamically and flexibly adds or removes functions along the routing path of flow, thereby catering to changeable user demands and network conditions. The key problem is automatically converting abstract SSCs to the specific placement of security function instances or simply instances and routing paths of flows. We refer to this problem as theSSC DeploymentProblem (SSC-DP). Generally, an SSC is derived from the security request of individual user or application. An instance is an operational software or hardware instance capable of delivering the treatment specified by the associated security function to packets or flows [11]. We only consider software instances, namely, virtualized security functions (e.g., virtual firewall, IPS, Web filter, and virus scanner). The server running them is called service node, which not only provides a runtime environment but also comprises facilities for attaching instances to the network.However, several issues should be considered before solving SSC-DP due to limited network resources. First, instances belonging to the same security function may differ in service capacity. For example, the throughput of a single instance may be far less than the volume of flow which generates security request. So instances providing the same functionality should be combined to serve a big flow. However, instances may also differ in resource demand. Thus, in order to minimize resource consumption of service nodes, we need to select the optimal combination of instances and assign more flows to the instance with high service capacity. Second, instances may have different demands for various resources. For example, an instance needs two CPU cores and 4 MB memory while another consumes one CPU core and 6 MB memory. So resources on a server may have different occupancy ratios, which leads to resource fragmentation problem [12]. Specifically, as far as a single service node is concerned, if the occupancy ratio of certain resource reaches the threshold, the node cannot run new instances any more. Third, flows should be routed in such a way to follow the sequence specified by SSC while optimizing the latency of security service, since latency is an important factor in measuring network performance [13–15]. Hence,an optimal solution of SSC-DP is needed to satisfy service demand of security request while minimizing resource consumption of service nodes and reducing resource fragmentation as well as forwarding flow through the best available path with the minimal security service latency.In this paper, we propose an approach that adopts the idea of SSC in the design of a solution for dynamically delivering customized security services. Since the key to effective operation of the proposed approach is to solve SSC-DP, we propose TPSSC, a three-phase method of finding near-optimal solutions of SSC-DP. Our main contributions are summarized as follows:(i)
We design an architecture to realize the idea of SSC by integrating the concepts of SDN and NFV, which facilitates security service delivery and management.(ii)
Taking into account the heterogeneity of service capacity and resource demand of miscellaneous instances, we propose the design operation before deploying SSCs to physical network. It contributes to reducing the total resource consumption of service nodes while allowing us to place instances in service nodes flexibly without worrying about service demands of security requests.(iii)
Based on considering both resource fragmentation and security service latency throughout the node mapping phase and the link mapping phase, we propose heuristic algorithms to select service nodes for instances and establish routing paths for flows. They contribute to optimizing network resource allocation and improving acceptance ratio of security requests.The rest of this paper is organized as follows. We study the related work in Section2. Section 3 describes the architecture of SSC-based security service delivery approach followed by illustrating the integrated ETSI NFV MANO architecture including the proposed architecture. In Section 4, we introduce some important definitions and formally define the SSC Deployment Problem. We present and evaluate the method TPSSC in Sections 5 and 6, respectively. Lastly, we conclude this paper with some future directions in Section 7.


## 2. Related Work

SSC-DP is similar to Virtual Network Embedding (VNE) [16] problem in some aspects, such as placing virtual network nodes (instances in our case) in physical infrastructure and chaining them while optimizing resource utilization or other objectives. However, solutions of VNE cannot be applied to solving SSC-DP directly, since the latter imposes additional constraints such as the service capacity of function specified by user’s request. In other words, VNE directly maps virtual network to physical network, while SSC-DP maps SSC requests of flows to virtual network composed of instances and then maps the latter to physical network. Moreover, VNE only considers routers in physical network while SSC-DP needs to deal with a much wider number of different functions which have strict order.Generally, SSC-DP can be regarded as a combination of VNF placement and traffic routing. A number of researches have been done in this field. Broadly we classify them into two domains as follows.In the case that instances have been running on service nodes, researches focus on the optimal selection of instances and routing of flows. The method proposed by Dwaraki and Wolf [17] transforms the network topology to a layered graph and selects instances and routes for each flow by running the Dijkstra algorithm. But it needs to find the shortest path in large space and the storage of layered graph costs high. Worse still, big flows may be accepted early, preventing network from holding more subsequent flows. To conquer this problem, Cao et al. [18] propose an online routing algorithm which can enable network to accept flows as many as possible over time. But it does not take into account the service capacity of instance. Thus, the work by Xiong et al. [19] selects instances and routes based on the service capacities of instances and the bandwidths of physical links, respectively. But the end-to-end latency of a flow may be large resulting from long distance between two instances belonging to the same flow. In [20], Ghaznavi et al. compare different operations of VNFs or flows. But they assume one VNF-instance type.In the opposite case, researches focus on determining the required number of instances, deploying them to available service nodes and routing flows. Various models have been built using MIQCP [21], MILP [22–24], and ILP [12, 25–27], which optimize different parameters such as end-to-end latency and resource utilization. We analyze them from the aspect of their solving methods. Mehraghdam et al. [21] use Gurobi optimizer, which is slow and cannot reconcile multiple objectives. To speed up the solving process, Mohammadkhan et al. [22] propose limiting the scale of problem through diving flows into groups. But they also use an off-the-shelf solver to solve the problem of each group. Allybokus et al. [27] present a heuristic algorithm based on a linear relaxation. In the case that two objectives are in competition, the method presented by Addis et al. [23] prioritizes them and uses CPLEX to find solutions for only one objective in a phase. However, it needs to limit the execution time of CPLEX in each phase. Improper time setting may affect quality of solutions. Similarly, based on introducing binary search, the method in [25] limits the execution time of CPLEX in each iteration. Bari et al. [12] use Viterbi algorithm to find a near-optimal placement of instances from multistage directed graph. But the graph needs to be updated frequently. Reference [26] compares the effects of different deployment strategies of VNFs on network resource consumption. But it does not illustrate how to solve the developed model. D’Oro et al. [28] propose a distributed solution by exploiting noncooperative game theory. But it assumes that source-destination flow is not split among multiple paths. On the basis of decomposing network functions into more elementary components, Sahhaf et al. [29] propose an algorithm based on backtracking mechanism. Reference [24] also adopts decomposition strategy but decomposes functions to multiple instances based on their performance demands. However, with respect to our work no consideration is made on instance sharing explicitly. Beyond offline problems, Lukovszki and Schmid [30] propose deterministic online algorithms for deploying service chains.From the above analysis, we can draw a conclusion that most researches do not clear up the relationship among flow, function, instance, and service node. Specifically, the function required by multiple flows can probably be mapped to an instance, or in other words those flows share an instance. Multiple instances providing the same functionality may be combined to serve a big flow, or in other words that flow is split among multiple paths. Meanwhile, multiple instances can run on a service node. Thus, in order to reduce the complexity of SSC-DP, it is necessary to determine the required instances for each SSC before placing them in the physical network. In addition, existing researches are insufficient in designing multipath routing of flows and improving solution quality of optimization model.


## 3. Architecture Description

We propose an SSC-based security service delivery approach. As shown in Figure1, its architecture consists of the Security Service Management Platform (SSMP), the Security Function Orchestrating Engine (SFOE), and the Flow Steering Engine (FSE). SSMP is responsible for receiving and analyzing security requests from users or network attack detection tools. It extracts and organizes information about SSC from those requests, such as the required number and types of instances as well as their connections, which will be handed over to SFOE. Then SFOE places instances on suitable service nodes and gives the placement view to FSE. Meanwhile, it sends commands to those nodes, creating and starting the corresponding instances. Additionally, the instances should register with SSMP after being started and SSMP will issue security defense polices to them. Finally, according to SSC information and the placement view, FSE computes routing paths which are used to steer flows through instances in order. And those paths are realized by flow table rules issued by SDN controller. By this approach, instances of security functions can be placed anywhere in the network and dynamically composed to meet specific user or application demands. Once demands or network conditions change, instances can be automatically started or terminated and routing paths of flows can also be adjusted accordingly.Figure 1
Architecture and component interactions.The proposed architecture can be integrated with ETSI NFV Architecture [31]. Figure 2 shows the integrated architecture. The Network Function Virtualization Orchestrator (NFVO) component is in charge of network services lifecycle management, such as instantiating, configuring, updating, and terminating. The Virtual Network Function Manager (VNFM) component is responsible for managing the lifecycle of VNF instances constituting specific network services. The Virtualized Infrastructure Manager (VIM) takes charge of managing NFV Infrastructure resources including computing, storage, and networking resources. The SDN controller component, which is logically placed with the VIM, is used for managing virtual networks through deploying flow table rules to the switches. Our proposed architecture can be regarded as the SSC Orchestrator component. Based on security requests, it constructs the placement view of VNF instances instantiated by the NFVO and creates routing paths of flows. There are two main interfaces exposed by the SSC Orchestrator. One is used by the SFOE to deliver the placement view to NFVO so as to instantiate the related VNFs. Another is used by the FSE to send routing paths of flows to the SDN controller so as to apply the flow table rules needed on the switches.Figure 2
Integrated architecture.


## 4. Definitions and Problem Statement

We first present a mathematical representation of a physical network, security request, and security function instance. Then we formally define the SSC-DP.


### 4.1. Definitions

Physical Network.We represent the physical network as an undirected graph Gs=(N,E), where N and E denote the set of physical nodes and links, respectively. We classify those nodes into three groups as forwarding node ntr⁡, which only forwards packets to other nodes, such as switches; service node nsr⁡, which provides virtualized platform for running instances; end node nend, which is the source or destination of flow. Additionally, let R be the set of available resources on the service node. For each r∈R,c(r) denotes the amount of r. Bandwidth and latency of physical link e∈E are denoted as bwe and late, respectively.Security Request.It is identified by 4-tuple, rq≔(src,dst,ch,run), where src and dst are the source and destination of the flow generating rq, respectively. ch={f1,f2,…,fn} represents the SSC, where fi denotes a security function, 1≤i≤n. If 1≤j=(i+1)≤n, fi is the immediate predecessor of fj, denoted as pre(fj)={fi}. Similarly, fj is the immediate successor of fi, denoted as succ(fi)={fj}. run represents service demand of rq. We define it as the throughput demand for instance and assume that the throughput demand is the same for the whole SSC in this paper. Other indications can also be used, like process rate of instance. It is an important factor for determining the number and types of instances and splitting flows.Security Function Instance.A security function has different types of instances with heterogeneous resource demands, service capacities, and processing delays. Let ins(fi)={iti1,iti2,…,itin} be the instance set of fi, where an instance itij is identified by 5-tuple, itij≔(p_type,type,ins_n,cap,pd). p_type is the type of associated security function, like firewall, IDS. type is used to distinguish instances with the same p_type, like firewalls developed by different companies. ins_n is the set of demands for different resources on service node. For each r∈R,rdijr∈ins_n. cap represents service capacity, which is defined as the throughput of instance in this paper, denoted as cij. pd is processing delay.


### 4.2. Problem Statement

Given a physical networkGs=(N,E) and a set of security requests RQ, instantiate each security function required by rq∈RQ on certain service nodes in Gs and determine the physical routing paths of the flow generating rq. This procedure seeks to minimize resource consumption of service nodes, resource fragmentation, and security service latency. It is subjected to the following constraints:(i)
A security functionfi∈rq can be instantiated on several service nodes in the form of different instance types of fi. Each selected service node has sufficient resources to accommodate the demand of an instance of fi. Additionally, different flows can share a security function instance on a service node.(ii)
A flow can be split. It means that there may be multiple routing paths of the flow between two service nodes where two adjacent security functions run. In addition, the total bandwidth demand on a physical link cannot exceed its available bandwidth.


## 4.1. Definitions

Physical Network.We represent the physical network as an undirected graph Gs=(N,E), where N and E denote the set of physical nodes and links, respectively. We classify those nodes into three groups as forwarding node ntr⁡, which only forwards packets to other nodes, such as switches; service node nsr⁡, which provides virtualized platform for running instances; end node nend, which is the source or destination of flow. Additionally, let R be the set of available resources on the service node. For each r∈R,c(r) denotes the amount of r. Bandwidth and latency of physical link e∈E are denoted as bwe and late, respectively.Security Request.It is identified by 4-tuple, rq≔(src,dst,ch,run), where src and dst are the source and destination of the flow generating rq, respectively. ch={f1,f2,…,fn} represents the SSC, where fi denotes a security function, 1≤i≤n. If 1≤j=(i+1)≤n, fi is the immediate predecessor of fj, denoted as pre(fj)={fi}. Similarly, fj is the immediate successor of fi, denoted as succ(fi)={fj}. run represents service demand of rq. We define it as the throughput demand for instance and assume that the throughput demand is the same for the whole SSC in this paper. Other indications can also be used, like process rate of instance. It is an important factor for determining the number and types of instances and splitting flows.Security Function Instance.A security function has different types of instances with heterogeneous resource demands, service capacities, and processing delays. Let ins(fi)={iti1,iti2,…,itin} be the instance set of fi, where an instance itij is identified by 5-tuple, itij≔(p_type,type,ins_n,cap,pd). p_type is the type of associated security function, like firewall, IDS. type is used to distinguish instances with the same p_type, like firewalls developed by different companies. ins_n is the set of demands for different resources on service node. For each r∈R,rdijr∈ins_n. cap represents service capacity, which is defined as the throughput of instance in this paper, denoted as cij. pd is processing delay.


## 4.2. Problem Statement

Given a physical networkGs=(N,E) and a set of security requests RQ, instantiate each security function required by rq∈RQ on certain service nodes in Gs and determine the physical routing paths of the flow generating rq. This procedure seeks to minimize resource consumption of service nodes, resource fragmentation, and security service latency. It is subjected to the following constraints:(i)
A security functionfi∈rq can be instantiated on several service nodes in the form of different instance types of fi. Each selected service node has sufficient resources to accommodate the demand of an instance of fi. Additionally, different flows can share a security function instance on a service node.(ii)
A flow can be split. It means that there may be multiple routing paths of the flow between two service nodes where two adjacent security functions run. In addition, the total bandwidth demand on a physical link cannot exceed its available bandwidth.


## 5. TPSSC: A Three-Phase Method for Solving SSC-DP

Based on the architecture presented in Section3, we propose TPSSC which finds near-optimal solutions of SSC-DP in three phases: designing, node mapping, and link mapping. The former phase, conducted by SSMP, designs a virtual security service topology according to security requests, which describes the required instances and their relations.However, although the number of instances and the throughput demand for each instance can be obtained from the designing phase, optimally mapping virtual security service topology to physical network is still NP-Hard [24]. We consider two optimization objectives in this paper: reducing resource fragmentation and security service latency. A naive way to perform the mapping is to treat each optimization as an independent subproblem and solve them sequentially, namely, solving first the placement of instances and then the routing of flows. However, this way usually makes it difficult to reduce latency because adjacent instances of the same flow may be placed far away from each other. On the other hand, some studies in the field of VNE have proposed an isomorphic graph search based algorithm to solve those two problems together [32]. But the algorithm is complex, and unlike VNE, end nodes of SSC are fixed physically and the sequence of security functions is often unidirectional. By combining the advantages of those two methods, we propose that a mapping procedure considers both resource fragmentation and security service latency throughout the mapping process. It can be divided into two phases, namely, node mapping and link mapping. The two phases jointly map the virtual security service topology to physical network, namely, determining placement of instances and routing paths of flows, which are conducted by SFOE and FSE, respectively. In each phase, we optimize SSC deployment from different perspectives. For the sake of convenient query, we list the related symbols used in this paper in Abbreviations.


### 5.1. Designing Phase

In this phase, we propose an algorithm to map each SSC to a combination of instances. From the perspective of optimization, the combination of instances satisfying throughput demand of request should consume resources on service node as little as possible. And the flow cannot be too scattered, considering reducing the possibility of transmission interruption caused by link failure(1)I=∑rqm∈RQ∑fi∈rqm.ch∑itij∈insfi∑r∈Rτr·xijm·rdijr,(2)D=∑rqm∈RQ∑fi∈rqm.ch∑itij∈insfixijm.Letxijm be the number of instances itij assigned to the SSC of request rqm. As shown in (1), I is the total resource consumption of service nodes, where τr is weighting factor used to adjust the relative importance of resources, ∑r∈Rτr=1. As shown in (2), D represents the total scatter degree of flows. Given certain SSC, the more the instances a flow needs to traverse, the more the microflows that flow should be split to. The basic procedure of our algorithm is shown in Algorithm 1. It accepts security request set RQ, security function set F, and the maximum number of iterations R as input. Note that each fi in F has an instance set, in which elements are sorted by their throughput (i.e., cij) in descending order. Here, we use a temporary variable tijm to keep track of the candidate value of xijm and use pim to indicate the instance under consideration. Since there may be too many available combinations of instances, the proposed algorithm, based on the idea of greedy, gives priority to instances with high throughput when assigning them to each SSC and limits the maximum number of iterations.Algorithm 1:Mapping SSC.
Input: Security request set RQ, security function set F, maximum number of iterations R
Output: Instance combinations of SSCs
Initializer=0;tijm=0;pim=1
while (r<R)
for all rqm∈RQ and fi∈rqm.ch  do
d
=
r
q
m
.
r
u
n
-
∑
0
≤
q
<
p
i
m
t
i
q
m
⋅
c
i
q
Find the minimum tipimm satisfying tipimm⋅cipim≥d
end for
Compute αI+βD
if  r=1 or αI+βD<δ  then
δ
=
α
I
+
β
D
Assign all tijm to xijm
end if
update(all  tijm)
r
=
r
+
1
end while
return  xijm∣rqm∈RQ,fi∈rqm.ch,itij∈insfi
Functionupdate(all  tijm)
for all rqm∈RQ and fi∈rqm.ch  do
if  pim≥insfi  then
Backtrack set Tim from pim-1th element until
find the first element satisfying tj>0
p
i
m
=
j
end if
t
i
p
i
m
m
=
t
i
p
i
m
m
-
1
p
i
m
=
p
i
m
+
1
end forLet{xijm∣itij∈ins(fi)} represent the instance set of fi which is assigned to rqm. For each itij, thijm denotes the throughput demand of rqm for it. It satisfies thijm≤cij; ∀fi∈rqm.ch, ∑itij∈ins(fi)thijm=rqm.run; the larger cij is, the smaller (cij-thijm) is.Since Algorithm1 does not take into account sharing instances among flows, we can merge the instance combinations of different SSCs, which can further reduce resource consumption. Then virtual security service topology, represented as a directed graph Gv=(V,L), is built. The meanings of symbols are as follows.v
∈
V is a virtual node. If it represents an instance itij, its weight w(v) is defined as the set of throughput demands of requests for this instance. Specifically, if ∑xijm>0thijm≤cij, w(v)={thijm∣xijm>0}. Otherwise, there are a set of nodes {v′} representing itij, and for each v′,∑thijm∈w(v′)thijm≤cij. If v represents the source of flow, denoted as s, w(v) is defined as the set of throughput demands of requests whose flow starts from s; that is, w(v)=rqm.run∣rqm.src=s. The definition of w(v) is similar if v represents the destination.l
∈
L is a virtual link, representing the order between two instances or between the source/destination of flow and an instance. Assume that security functions fi and fj belong to SSCs of rqm and rqn, respectively, and they satisfy pre(fj)=fi. If the instance itip (itiq) of fi (fj) is represented by the virtual node vp (vq), there is a virtual link from vp to vq, denoted as l(vp,vq). Its weight is defined as the set of throughput demands of rqm and rqn; that is, w(l(vp,vq))={db(vp,vq)m,db(vp,vq)n}, where db(vp,vq)m=min⁡thipm,thiqm and db(vp,vq)n=min⁡thipn,thiqn. If an end node of l represents source or destination, relevant definitions are similar. Additionally, we use id(l)={rqm,rqn,…} to record the requests whose SSCs use the edge l.


### 5.2. Node Mapping Phase

In this phase, we aim to select a suitable service node to run the instance represented by each virtual node.


#### 5.2.1. Formulation

(3)
m
i
n
max
n
i
∈
N
sr
⁡
f
r
a
i
,
(4)
u
t
l
i
r
=
∑
v
f
∈
V
i
n
s
x
i
f
·
r
e
s
f
r
c
i
r
,
(5)
u
t
l
i
¯
=
∑
r
∈
R
u
t
l
i
r
R
,
(6)
f
r
a
i
=
∑
r
∈
R
u
t
l
i
r
u
t
l
i
¯
-
1
2
,
(7)
m
i
n
max
s
,
d
∈
Φ
⁡
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
m
,
n
∈
N
x
u
m
·
x
v
n
·
h
o
p
m
,
n
,
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
m
,
n
∈
N
x
u
m
·
x
v
n
·
h
o
p
m
,
n
(8)
s
.
t
.
∀
v
f
∈
V
i
n
s
:
∑
n
i
∈
N
s
r
x
i
f
=
1
,
(9)
∀
n
i
∈
N
s
r
,
∀
r
∈
R
:
∑
v
f
∈
V
i
n
s
x
i
f
·
r
e
s
f
r
≤
c
i
r
(10)
∀
v
s
∈
V
e
n
d
,
∀
n
i
∈
N
e
n
d
-
a
:
x
a
s
=
1
,
x
i
s
=
0
,
(11)
∀
v
d
∈
V
e
n
d
,
∀
n
i
∈
N
e
n
d
-
a
′
:
x
a
′
d
=
1
,
x
i
d
=
0
,
(12)
∀
n
i
∈
N
s
r
,
∀
v
f
∈
V
i
n
s
:
x
i
f
∈
0,1
.As resource fragmentation limits network to accept security requests, we take minimizing the maximum resource fragmentation of service nodes ((3)) as an objective. frai ((6)) measures the resource fragmentation of ni by computing the deviation between utilizations of different resources ((4) and (5)). The smaller the deviation is, the more balanced the utilizations are. Additionally, we consider security service latency by optimizing the length of routing path. For the sake of simplicity, we define the path length between two instances (we regard the source and destination of flow as instances with fixed physical locations in node mapping phase and link mapping phase) as the minimum number of hops of all paths between the service nodes they are placed on. Then for a virtual path, its length is the sum of path lengths between instances along it. As a flow may correspond to several virtual paths constructed by different instances in the virtual security service topology, we define the length of routing path as the maximum length of all virtual paths. So minimizing the maximum length of routing path ((7)) is regarded as another objective.Thus, we provide a constrained multiobjective optimization formulation, denoted as Problem P. It seeks to obtain the optimal selection of service nodes without violating the constraints of capacities of physical nodes and links. Our formulation is as follows.Equation (8) guarantees that an instance must be placed on exactly one service node; (9) constrains the fact that resource demands of all instances placed on a service node should be less than or equal to available resources in that node; (10) and (11) ensure that physical locations of the source and destination of a flow are respected, respectively; (12) constrains decision variables to be 0 or 1. For the sake of clarify, we denote (3) and (7) as f1(X) and f2(X), where X=(xij)|Nsr+Nend|×|Vins+Vend|.


#### 5.2.2. Proposed Algorithm

To obtain the Pareto-optimal solutions of the above problem, inspired by immune memory clonal algorithms [33, 34], we propose a service node selection algorithm based on bidirectional memory. The key idea is to approximate the Pareto-optimal solutions from feasible and infeasible regions. The basic procedure of our algorithm is shown in Algorithm 2. It first establishes the memory unit and the standby unit to reserve the current Pareto-optimal feasible and infeasible solutions, respectively. After implementing clone, mutation, and selection operation, it extracts preponderant antibody population and neighboring antibody population from the whole population. Then the former integrates with the previous Pareto-optimal solutions in memory unit, which ensures that the quality of solutions is not degraded. The latter cooperates with the standby unit to approximate the Pareto-optimal solutions from infeasible region, which maintains diversity of antibody population. Additionally, the newly obtained Pareto-optimal solutions are used as the initial antibody population in next iteration, which accelerates convergence rate of the proposed algorithm. The main data structures and detailed operations are presented as follows.Algorithm 2:Service node selection algorithm based on bidirectional memory.
Input: Maximum number of iterations T, maximum size of antibody population Na, maximum
size of memory unit Nm, size of standby unit Nb, initial mutation probability mp0
Output: Memory unit Mit
Initializeit=0; initializing antibody population Ait, memory unit Mit and standby unit Bit.
Step
1. Generate Cit from Ait by the clone operation Oc:
C
i
t
=
O
c
A
i
t
=
=
c
1
i
t
,
c
2
i
t
,
…
,
c
N
c
i
t, where  Nc=∑i=1Npiit.
Step
2. Update Cit by the mutation operation Om:
D
i
t
=
O
m
C
i
t
=
d
1
i
t
,
d
2
i
t
,
…
,
d
N
c
i
t.
Step
3. Generate preponderant antibody population Pit and neighboring antibody population
Q
i
t from Dit by selection operation Os.
Step
4. If the size of P(it) is larger than Na, sort antibodies by their crowding distances [35] in
descending order and select the top Na antibodies to form new antibody population P′it,
otherwise P′it=Pit:
P
′
i
t
=
O
u
P
i
t
=
p
′
1
i
t
,
p
′
2
i
t
,
…
,
p
′
N
a
i
t.
Step
5. Produce new memory unit M′it by applying study operation Ol on Mit and P′it:
M
′
(
i
t
)
=
O
l
M
i
t
,
P
′
i
t
=
m
′
1
i
t
,
m
′
2
i
t
,
…
,
m
′
R
i
t
+
1
i
t, where  Rit+1≤Nm.
Step
6. Update Qit by the self-repairing operation Or:
Q
′
i
t
=
O
r
Q
i
t
=
q
′
1
i
t
,
q
′
2
i
t
,
…
,
q
′
N
q
i
t.
Step
7. Produce new standby unit B′it by applying replacement operation Oa on Bit and Q′it:
B
′
i
t
=
O
a
B
i
t
,
Q
′
i
t
=
b
′
1
i
t
,
b
′
2
i
t
,
…
,
b
′
N
b
i
t.
Step
8. If it≥T, output M′it and end, otherwise Ait+1=P′it, Mit+1=M′it,
B
(
i
t
+
1
)
=
B
′
i
t, it=it+1, go to Step 1.(
1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.Antibody Population.The algorithm maintains an antibody population A(it)={a1(it),a2(it),…,aNa(it)} at the itth generation, where Na is the size of the population. Antibody ai(it) is the encoding of candidate solution X for the Problem P; that is, ai(it)=e(X)=(ai1(it),ai2(it),…,ain(it)), 1≤i≤Na, where n is the length of the antibody and aif(it)=k means placing the instance represented by vf on the service node nk; namely, xkf=1. In particular, if vf represents the source or destination of flow, aif(it) is a known quantity and will not be changed by the following operations.By this encoding method, the two-dimensional mapping relation between instances and service nodes is transformed to one-dimensional vector, which satisfies (8) and (10)–(12) inherently. So (9) is used to judge the feasibility of ai(it).We introduce a new functiongir(X(i,:))=max{0,∑vf∈Vinsxfi·resfr-ci(r)}, where ni∈Nsr and r∈R. Assume that f3(X)=∑ni∈Nsr∑r∈Rgir(X(i,:)). If f3(e-1(ai(it)))=0, namely, X=e-1(ai(it)) satisfies all constraints of the Problem P, ai(it) is called feasible antibody. Otherwise, ai(it) is called infeasible antibody. Furthermore, f3(e-1(ai(it))) is used to measure the degree of constraint violation of an infeasible antibody. The larger it is, the deeper the degree of constraint violation of ai(it) is.If two feasible antibodies,ai(it) and aj(it), satisfy the condition that (∀k=1,2:fk(e-1(ai(it)))≤fk(e-1(aj(it))))∧(∃g=1,2:fg(e-1(ai(it)))<fg(e-1(aj(it)))), ai(it) is said to Pareto dominate aj(it), denoted as ai(it)≻aj(it). Furthermore, ai(it) is called Pareto-optimal if there does not exist another feasible antibody a∗(it) in A(it) that satisfies a∗(it)≻ai(it).Memory Unit.Memory unit M(it)={m1(it),m2(it),…,mR(it)(it)} is defined as the set of all Pareto-optimal antibodies in A(it), whose size R(it) changes dynamically. In other words, it contains service node selection schemes that are Pareto-optimal. We can implement any one scheme in it. To improve the quality of solutions, we assume that the upper limit of R(it) is Nm.Standby Unit.Standby unit B(it)={b1(it),b2(it),…,bNb(it)}, whose size is Nb, is defined as the set of infeasible antibodies with relatively low degree of constraint violation in A(it).(
2) Operation Description. We describe operations in the proposed algorithm successively.Initializing Operation.To improve the quality of initial solutions, we propose an antibody population initialization algorithm based on preference. The preference of the instance vf for the service node ni is defined as pffi=1/((1/R)∑r∈Rλr2-1/R∑r∈Rλr2+σ), where λr=resfr/ci(r) is the occupancy ratio of resource r in ni occupied by vf and σ is a small positive constant to avoid dividing by zero in computing the preference. Then the preference list of vf, denoted as PL(vf), is built by sorting service nodes by pffi in descending order. Note that preference lists are known before running the algorithm.The key idea of our algorithm is to traverse preference list of each instance until finding the service node satisfying resource constraint and distance constraint so as to achieve optimization objectives initially. The basic procedure is shown in Algorithm3. Here, function Selectfirst(PL(vf)) means traversing PL(vf) in sequence until finding ni which is the first service node satisfying two conditions simultaneously: (i) ∀r∈R, resfr≤ci(r); (ii) ∀vj∈pre(vf),aj=g, hop(ng,ni)≤θ. If all nodes in PL(vf) just satisfy only one condition, it selects the first node satisfying condition (i). If all nodes do not satisfy condition (i), it randomly selects a service node occupied by an instance of pre(vf).Algorithm 3:Antibody population initialization algorithm based on preference.
Input: Gv, preference lists of all instances, the upper limit of hops between two nodes θ
Output: Initial antibody population
for  m=1 to Na  do
T
r
s
=
⌀
while  (Trs≠Vins)
for all vf∈Vins  do
if  idgvf=0  then  //idgvf  is the in-degree of vf
n
i
=
S
e
l
e
c
t
f
i
r
s
t
(
P
L
(
v
f
)
)
a
m
f
=
i
for all r∈R  do
c
i
(
r
)
=
c
i
(
r
)
-
r
e
s
f
r
end for
i
d
g
v
f
=
i
d
g
v
f
-
1
T
r
s
=
T
r
s
⋃
{
v
f
}
for  all vk∈succ(vf)  do
i
d
g
v
k
=
i
d
g
v
k
-
1
end for
end if
end for
end while
m
=
m
+
1
end for
return  A(0)={a1(0),a2(0),…,aNa(0)}Clone Operation.
O
c is defined as Oc(A(it))={Oc(a1(it)),Oc(a2(it)),…,Oc(aNa(it))}, where Oc(ai(it))={a11(it),…,a1pi(it)(it)}, 1≤i≤Na, and pi(it) is the clone scale of ai(it)(13)piit=IntH·ηiit∑j=1Nitηjit·1ψiit.p
i
(
i
t
) is given by (13) and can self-adaptively be adjusted by the antibody-antibody affinity ψi(it) and the antibody-antigen affinity ηi(it). Their detailed definitions are as follows:(i)
Antibody-antibody affinityψi(it): it is measured by the Euclidean distance between ai(it) and other antibodies: ψi(it)=min{exp(-ai(it)-aj(it))}, where i≠j, 1≤j≤Na; · represents Euclidean distance, and it is normalized to [0,1].(ii)
Antibody-antigen affinityηi(it). (14)Rijakit=1fje-1aiit≤fje-1akit,0else,(15)ηijit=∑k=1NaRijakit,(16)ηiit=∑j=13ηijit.To unify the affinity computation of feasible and infeasible antibodies, we regardminf3(X) as an objective of the Problem P. So given a single antigen (i.e., an objective function) fj(X), we can obtain relative affinity between the antibody ai(it) and the antigen fj(X), denoted as ηij(it) ((15)), through comparing the objective value of ai(it) (i.e., fj(e-1(ai(it)))) with objective values of other antibodies ((14)). For the Problem P with multiple objectives, ηi(it) is defined as the sum of relative affinities between ai(it) and each objective ((16)). This method can eliminate the bad influence of a too large or too small objective value on the affinity.H is a given value relating to clone scale (we assume that H=3N) and the function Int() returns the value of a number rounded upwards to the nearest integer. Apparently, the clone scale decreases with the increase of inhibitory effect between antibodies (namely, ψi(it) increases) and the decrease of antigen stimulation (namely, ηi(it) decreases).Mutation Operation.Since every value in antibody indicates a service node, we propose a new mutation strategy to make the mutation operation meaningful. For each antibody in C(it), we select two values in it randomly and exchange them with probability of mp=mp0·(1-it/T), where mp0 is the initial mutation probability, and it and T are the current and the maximum number of iterations, respectively. Apparently, mp decreases with the proposed algorithm running.Selection Operation.First of all, we separate feasible antibodies from infeasible ones. Then, we extract Pareto-optimal antibodies from the former to form the preponderant antibody population P(it). Meanwhile, we choose Nq antibodies with the lowest degree of constraint violation from infeasible antibodies to form the neighboring antibody population Q(it). Adding antibodies of Q(it), which approximate the edge of feasible region, to the next iteration can improve diversity of antibody population.Self-Repairing Operation.Through migrating instances from overloaded service nodes to those with abundant resources, self-repairing operation can reduce the degree of constraint violation of infeasible antibody and make it enter or be more close to feasible region. Let Q(it)={q1(it),q2(it),…,qNq(it)} be the neighboring antibody population. Assume that antibodies in Q(it) are sorted by the degree of constraint violation in descending order. For an antibody qi(it), the resource burden of service node nj is defined as burj=∑r∈Rmax{0,∑k∈{k∣qik=j}reskr-cj(r)}/cj(r). If there exists a node without burden, that is, burj=0, self-repairing operation will be applied to qi(it). Specifically, starting from nj with the heaviest burden, it selects an instance vk randomly and migrates it to the node nj′ with burj′=0, that is, replacing qik=j with qik=j′. If the degree of constraint violation of the new antibody qi′(it) is smaller than that of qi(it), this migration is accepted. Otherwise, it selects another instance and repeats the previous migration until all instances on nj are traversed. Then it tries to do migration in other nodes until there are no nodes without burden. Assuming that self-repairing operation is only applied to m antibodies, the time consumption can be controlled by adjusting m. In other words, m is the depth of self-repairing operation.Replacement Operation.It replaces the antibodies in the standby unit with the antibodies which have lower degree of constraint violation in the neighboring antibody population. It ensures that the standby unit approximates feasible region gradually.Study Operation.Through comparing antibodies in the updated preponderant antibody population with those in the memory unit, study operation updates the memory unit with the newest Pareto-optimal antibodies. If the size of memory unit exceeds Nm, updating operation based on crowding distance will be applied [35].


### 5.3. Link Mapping Phase

This phase is to route flows among the selected service nodes based on the virtual security service topology. We refer to this problem as the service path establishment problem. Since a flow can be split and the capacity of physical link is limited, we treat virtual links as commodities and model the service path establishment problem as the capacitated multicommodity flow problem.


#### 5.3.1. Formulation

(17)
m
i
n
max
s
,
d
∈
Φ
⁡
c
l
t
s
d
,
(18)
c
l
t
s
d
=
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
e
m
,
n
∈
E
s
t
f
y
m
,
n
u
,
v
·
l
a
t
m
,
n
+
∑
v
f
∈
φ
π
i
p
d
f
,
(19)
s
.
t
.
∀
e
m
,
n
∈
E
:
∑
l
u
,
v
∈
L
y
m
,
n
u
,
v
≤
b
w
m
,
n
,
(20)
∀
l
u
,
v
∈
L
,
x
u
b
=
x
v
b
′
=
1
,
∀
n
∈
N
-
b
,
b
′
:
∑
c
∈
N
y
c
,
n
u
,
v
-
∑
c
′
∈
N
y
n
,
c
′
u
,
v
=
0
,
∑
c
∈
N
y
c
,
b
u
,
v
=
∑
c
′
∈
N
y
b
′
,
c
′
u
,
v
=
0
,
∑
c
∈
N
y
b
,
c
u
,
v
=
∑
c
′
∈
N
y
c
′
,
b
′
u
,
v
=
d
b
u
,
v
,
(21)
∀
e
m
,
n
∈
E
,
l
u
,
v
∈
L
:
y
m
,
n
u
,
v
≤
z
m
′
,
n
′
m
,
n
·
x
u
m
′
·
x
v
n
′
·
min
⁡
b
w
m
,
n
,
d
b
u
,
v
,
(22)
∀
e
m
,
n
∈
E
,
l
u
,
v
∈
L
:
y
m
,
n
u
,
v
≥
0
.A security request may correspond to multiple virtual paths constructed by different instances in the virtual security service topology. So the maximum latency of those paths is regarded as the service latency of security request ((18)), where stf() is step function and it is assumed that stf(0)=0; (19) is a constraint on the maximum bandwidth of physical links that can be assigned to different virtual links; (20) is the flow conservation constraint. It ensures that, for every node n in the physical network, if one of its incoming links belongs to the path which a virtual link is mapped to, one of its outgoing links also belongs to that path. Excluded from this rule is the case where the node is one of the nodes to which the two end nodes of virtual link are mapped; (21) constrains the fact that a virtual link must be mapped to the path between the two nodes whose end nodes are mapped to. Note that zm′,n′(m,n), xum′, and xvn′ are not decision variables but introduced to express that constraint; (22) is a constraint on the values of decision variables.


#### 5.3.2. Proposed Algorithm

Since the capacitated multicommodity flow problem is NP-Hard [36], we propose a heuristic named service path establishment algorithm based on hybrid taboo search. Before introducing the algorithm, we describe the main data structures followed by discussing the key aspects of the algorithm: neighborhood search method, evaluation function, and termination condition.(
1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.Initial Solution Set.The initial solution set is defined as S0={s1,s2,…,sn}, where si=ym,nu,vE×L, 1≤i≤n. Take the process of generating an initial solution as an example. Assume that every virtual link has a set of k-shortest physical paths between the two nodes whose start and end node are mapped to. The algorithm randomly selects a node of which the in-degree equals 0 in the virtual security service topology and maps virtual links connected to that node to physical paths. For each virtual link, single path mapping is applied first. Specifically, physical path in its k-shortest path set is traversed in increasing order of their lengths until a path satisfying bandwidth demand is found. If no such single path exists, multipath mapping is applied, which prefers to assign as much bandwidth demand as possible to relatively short physical path. After all virtual links connected to the node have been mapped, the node and virtual links are marked as “traversed" and removed from the virtual topology. Then another node of which the in-degree equals 0 will be chosen to repeat the above operation. An initial solution is generated after all nodes and links in the virtual topology have been traversed.Dominant Solution Set.For S0={s1,s2,…,sn}, solutions are sorted by their objective function values (i.e., max(s,d)∈Φ⁡(cltsd), denoted as h(si)) in ascending order. So the first m solutions are chosen to form the dominant solution set. It is denoted as DS={s1,s2,…,sm}, where h(s1)≤⋯≤h(sm). During the running time, DS will be updated continually to ensure that it always keeps the optimal solutions. Moreover, the depth of local search is adjusted dynamically according to whether DS is updated or not.Tabu List.Assuming that virtual links and physical links are identified by positive integers, the tabu list is defined as TL=({(l,{yab∣1≤a≤E,b=l})∣1≤l≤L},ctl), where l is the identification of virtual link and yab is the bandwidth assigned to the virtual link b by the physical link a. The length of TL is set to be 7 [36].(
2) Key Aspect Description. In what follows, we discuss three key aspects with respect to the proposed algorithm.Neighborhood Search Method.Given the solution si, its neighborhood N(si)=NeborConss,ns={si1,si2,…,sins} can be built as follows. First, a virtual link is selected randomly. Then through adjusting the bandwidth demand assigned to each physical path in its k-shortest path set, a new service path establishment scheme, or in other words a neighboring solution si1 is generated. It is particularly important that the new scheme should satisfy the overall bandwidth demand of the selected virtual link. Similarly, other (ns-1) neighboring solutions can be generated. The size of N(si) is defined as ns=nsmin+nt·(nsmax-nsmin)/NT, where nsmax=L and nsmin=0.5L are the maximum and the minimum size of neighborhood, respectively, and nt and NT are the current and the maximum number of iterations of neighborhood search, respectively. Note that though the generated neighboring solutions satisfy (20) and (21), some of them may violate (19), which should be eliminated.Evaluation Function.It is denoted asEvaluate(). We take the objective function h(s) as the evaluation function. To eliminate infeasible solutions, a highest evaluation value will be assigned to them.Termination Condition.The algorithm will terminate as long as one of the following conditions are satisfied: the number of iterations exceeds T; solutions are not improved; namely, the objective function value remains constant after R successive iterations.The basic procedure of our algorithm is shown in Algorithm4. Here, we use the functions Update(DS,S0) and Update(DS,N(s)) to replace some solutions in DS with better ones in S0 and N(s), respectively. We also use roulette wheel strategy to select the candidate solution set from N(s), denoted as Roulette_wheel(N(s)).Algorithm 4:Service path establishment algorithm based on hybrid taboo search.
Input: NT, T, R
Output: The best solution s∗
Initialize:DS=⌀; TL=⌀; t=0; impro=0
Generate initial solution setS0
UpdateDS,S0
while  (t<T and noimpro<R)
Randomly select s from DS
r
=
h
D
S
1
n
t
=
0
s
b
e
s
t
=
s
while  (nt<NT)
N
(
s
)
=
N
e
b
o
r
C
o
n
s
s
,
n
s
E
v
a
l
u
a
t
e
N
s
i
s
u
p
d
a
t
e
d
=
U
p
d
a
t
e
D
S
,
N
s
if isupdated then  nt=0
else  nt++
end if
C
S
=
R
o
u
l
e
t
t
e
_
w
h
e
e
l
(
N
(
s
)
)
if  isaspiration  then
s
=
S
e
l
e
c
t
B
e
s
t
C
S
s
b
e
s
t
=
s
Update the tabu list TL
else
s
=
S
e
l
e
c
t
B
e
s
t
_
n
o
t
a
b
u
C
S
Update the tabu list TL
end if
end while
t
+
+
if  hDS1<r  then  noimpro=0
else  noimpro++
end if
end while
return  DS1The algorithm generates multiple initial solutions based on greedy strategy and randomly selects one solution as the start point of iteration, which can solve the problem that tabu search relies heavily on initial solution. Additionally, it takes into account both diversification and intensification strategy. On the one hand, the longer the dominant solution set is not updated during neighborhood search, the larger the search space is. It reflects that the algorithm increases diversity of solutions by expanding search space, which benefits finding better solutions. On the other hand, the dominant solution set keeps the firstm excellent solutions so far and every iterative search starts from them. It reflects that the algorithm is exploited in promising space through concentrating on searching the neighborhood of the current excellent solutions.


### 5.4. Time Complexity Analysis

We mainly analyze the time complexity of two algorithms in mapping phase.For the service node selection algorithm based on bidirectional memory, we take the first iteration as an example to analyze its time complexity step by step.Na, Nm, and Nb represent the size of the initial antibody population, memory unit, and standby unit, respectively. Firstly, assuming that the number of service nodes and instances is Nsr and Nins, respectively, the worst time complexity of initializing operation is O(Na·Nins·Nsr). Then, the time complexity of building memory unit and standby unit is O(Na2) and O(Na+NalogNb), respectively. Thirdly, if H is a given value relating to clone scale, the worst time complexity of clone operation is O(NaH). Fourthly, if the size of antibody population after cloning is Nc, the time complexity of mutation operation is O(Nc). Fifthly, selection operation includes computing the degree of constraint violation of antibodies, selecting Pareto-optimal antibodies, and choosing Nq antibodies with the lowest degree of constraint violation. Their time complexities are O(Nc), O(Nc2), and O(NclogNq), respectively. Then, if the size of preponderant antibody population after selection operation is K and there are Na Pareto-optimal antibodies that should be reserved, the time complexity of updating preponderant antibody population is O(NaK2). Next, the time complexity of self-repairing operation is O(m·NsrlogNsr) if its depth is m. Then the worst time complexity of replacement operation is O(Nb·Nq). Finally, the time complexity of study operation is O((Na+Nm)2). Therefore, the worst time complexity of the proposed algorithm during the first iteration is O(Na·Nins·Nsr+Nc2+Na·K2+Na2+Nm2).For the service path establishment algorithm based on hybrid taboo search, we take an iteration as an example to analyze its time complexity. Assume that there areL virtual links. The worst time complexity of generating the initial solution set with n solutions is O(nkL). Subsequently, the time complexity of updating the dominant solution set with m solutions is O(nlogm). The main operation in an iteration is building neighborhood with variable size. Considering the process from nt=0 to nt=NT, the number of generated neighboring solutions is NT·nsmin+0.5·(NT+1)·(nsmax-nsmin). So the time complexity of this process can be regarded as O(NT·nsmax). In conclusion, the time complexity of an iteration of the proposed algorithm is O(nkL+NT·nsmax).


## 5.1. Designing Phase

In this phase, we propose an algorithm to map each SSC to a combination of instances. From the perspective of optimization, the combination of instances satisfying throughput demand of request should consume resources on service node as little as possible. And the flow cannot be too scattered, considering reducing the possibility of transmission interruption caused by link failure(1)I=∑rqm∈RQ∑fi∈rqm.ch∑itij∈insfi∑r∈Rτr·xijm·rdijr,(2)D=∑rqm∈RQ∑fi∈rqm.ch∑itij∈insfixijm.Letxijm be the number of instances itij assigned to the SSC of request rqm. As shown in (1), I is the total resource consumption of service nodes, where τr is weighting factor used to adjust the relative importance of resources, ∑r∈Rτr=1. As shown in (2), D represents the total scatter degree of flows. Given certain SSC, the more the instances a flow needs to traverse, the more the microflows that flow should be split to. The basic procedure of our algorithm is shown in Algorithm 1. It accepts security request set RQ, security function set F, and the maximum number of iterations R as input. Note that each fi in F has an instance set, in which elements are sorted by their throughput (i.e., cij) in descending order. Here, we use a temporary variable tijm to keep track of the candidate value of xijm and use pim to indicate the instance under consideration. Since there may be too many available combinations of instances, the proposed algorithm, based on the idea of greedy, gives priority to instances with high throughput when assigning them to each SSC and limits the maximum number of iterations.Algorithm 1:Mapping SSC.
Input: Security request set RQ, security function set F, maximum number of iterations R
Output: Instance combinations of SSCs
Initializer=0;tijm=0;pim=1
while (r<R)
for all rqm∈RQ and fi∈rqm.ch  do
d
=
r
q
m
.
r
u
n
-
∑
0
≤
q
<
p
i
m
t
i
q
m
⋅
c
i
q
Find the minimum tipimm satisfying tipimm⋅cipim≥d
end for
Compute αI+βD
if  r=1 or αI+βD<δ  then
δ
=
α
I
+
β
D
Assign all tijm to xijm
end if
update(all  tijm)
r
=
r
+
1
end while
return  xijm∣rqm∈RQ,fi∈rqm.ch,itij∈insfi
Functionupdate(all  tijm)
for all rqm∈RQ and fi∈rqm.ch  do
if  pim≥insfi  then
Backtrack set Tim from pim-1th element until
find the first element satisfying tj>0
p
i
m
=
j
end if
t
i
p
i
m
m
=
t
i
p
i
m
m
-
1
p
i
m
=
p
i
m
+
1
end forLet{xijm∣itij∈ins(fi)} represent the instance set of fi which is assigned to rqm. For each itij, thijm denotes the throughput demand of rqm for it. It satisfies thijm≤cij; ∀fi∈rqm.ch, ∑itij∈ins(fi)thijm=rqm.run; the larger cij is, the smaller (cij-thijm) is.Since Algorithm1 does not take into account sharing instances among flows, we can merge the instance combinations of different SSCs, which can further reduce resource consumption. Then virtual security service topology, represented as a directed graph Gv=(V,L), is built. The meanings of symbols are as follows.v
∈
V is a virtual node. If it represents an instance itij, its weight w(v) is defined as the set of throughput demands of requests for this instance. Specifically, if ∑xijm>0thijm≤cij, w(v)={thijm∣xijm>0}. Otherwise, there are a set of nodes {v′} representing itij, and for each v′,∑thijm∈w(v′)thijm≤cij. If v represents the source of flow, denoted as s, w(v) is defined as the set of throughput demands of requests whose flow starts from s; that is, w(v)=rqm.run∣rqm.src=s. The definition of w(v) is similar if v represents the destination.l
∈
L is a virtual link, representing the order between two instances or between the source/destination of flow and an instance. Assume that security functions fi and fj belong to SSCs of rqm and rqn, respectively, and they satisfy pre(fj)=fi. If the instance itip (itiq) of fi (fj) is represented by the virtual node vp (vq), there is a virtual link from vp to vq, denoted as l(vp,vq). Its weight is defined as the set of throughput demands of rqm and rqn; that is, w(l(vp,vq))={db(vp,vq)m,db(vp,vq)n}, where db(vp,vq)m=min⁡thipm,thiqm and db(vp,vq)n=min⁡thipn,thiqn. If an end node of l represents source or destination, relevant definitions are similar. Additionally, we use id(l)={rqm,rqn,…} to record the requests whose SSCs use the edge l.


## 5.2. Node Mapping Phase

In this phase, we aim to select a suitable service node to run the instance represented by each virtual node.


### 5.2.1. Formulation

(3)
m
i
n
max
n
i
∈
N
sr
⁡
f
r
a
i
,
(4)
u
t
l
i
r
=
∑
v
f
∈
V
i
n
s
x
i
f
·
r
e
s
f
r
c
i
r
,
(5)
u
t
l
i
¯
=
∑
r
∈
R
u
t
l
i
r
R
,
(6)
f
r
a
i
=
∑
r
∈
R
u
t
l
i
r
u
t
l
i
¯
-
1
2
,
(7)
m
i
n
max
s
,
d
∈
Φ
⁡
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
m
,
n
∈
N
x
u
m
·
x
v
n
·
h
o
p
m
,
n
,
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
m
,
n
∈
N
x
u
m
·
x
v
n
·
h
o
p
m
,
n
(8)
s
.
t
.
∀
v
f
∈
V
i
n
s
:
∑
n
i
∈
N
s
r
x
i
f
=
1
,
(9)
∀
n
i
∈
N
s
r
,
∀
r
∈
R
:
∑
v
f
∈
V
i
n
s
x
i
f
·
r
e
s
f
r
≤
c
i
r
(10)
∀
v
s
∈
V
e
n
d
,
∀
n
i
∈
N
e
n
d
-
a
:
x
a
s
=
1
,
x
i
s
=
0
,
(11)
∀
v
d
∈
V
e
n
d
,
∀
n
i
∈
N
e
n
d
-
a
′
:
x
a
′
d
=
1
,
x
i
d
=
0
,
(12)
∀
n
i
∈
N
s
r
,
∀
v
f
∈
V
i
n
s
:
x
i
f
∈
0,1
.As resource fragmentation limits network to accept security requests, we take minimizing the maximum resource fragmentation of service nodes ((3)) as an objective. frai ((6)) measures the resource fragmentation of ni by computing the deviation between utilizations of different resources ((4) and (5)). The smaller the deviation is, the more balanced the utilizations are. Additionally, we consider security service latency by optimizing the length of routing path. For the sake of simplicity, we define the path length between two instances (we regard the source and destination of flow as instances with fixed physical locations in node mapping phase and link mapping phase) as the minimum number of hops of all paths between the service nodes they are placed on. Then for a virtual path, its length is the sum of path lengths between instances along it. As a flow may correspond to several virtual paths constructed by different instances in the virtual security service topology, we define the length of routing path as the maximum length of all virtual paths. So minimizing the maximum length of routing path ((7)) is regarded as another objective.Thus, we provide a constrained multiobjective optimization formulation, denoted as Problem P. It seeks to obtain the optimal selection of service nodes without violating the constraints of capacities of physical nodes and links. Our formulation is as follows.Equation (8) guarantees that an instance must be placed on exactly one service node; (9) constrains the fact that resource demands of all instances placed on a service node should be less than or equal to available resources in that node; (10) and (11) ensure that physical locations of the source and destination of a flow are respected, respectively; (12) constrains decision variables to be 0 or 1. For the sake of clarify, we denote (3) and (7) as f1(X) and f2(X), where X=(xij)|Nsr+Nend|×|Vins+Vend|.


### 5.2.2. Proposed Algorithm

To obtain the Pareto-optimal solutions of the above problem, inspired by immune memory clonal algorithms [33, 34], we propose a service node selection algorithm based on bidirectional memory. The key idea is to approximate the Pareto-optimal solutions from feasible and infeasible regions. The basic procedure of our algorithm is shown in Algorithm 2. It first establishes the memory unit and the standby unit to reserve the current Pareto-optimal feasible and infeasible solutions, respectively. After implementing clone, mutation, and selection operation, it extracts preponderant antibody population and neighboring antibody population from the whole population. Then the former integrates with the previous Pareto-optimal solutions in memory unit, which ensures that the quality of solutions is not degraded. The latter cooperates with the standby unit to approximate the Pareto-optimal solutions from infeasible region, which maintains diversity of antibody population. Additionally, the newly obtained Pareto-optimal solutions are used as the initial antibody population in next iteration, which accelerates convergence rate of the proposed algorithm. The main data structures and detailed operations are presented as follows.Algorithm 2:Service node selection algorithm based on bidirectional memory.
Input: Maximum number of iterations T, maximum size of antibody population Na, maximum
size of memory unit Nm, size of standby unit Nb, initial mutation probability mp0
Output: Memory unit Mit
Initializeit=0; initializing antibody population Ait, memory unit Mit and standby unit Bit.
Step
1. Generate Cit from Ait by the clone operation Oc:
C
i
t
=
O
c
A
i
t
=
=
c
1
i
t
,
c
2
i
t
,
…
,
c
N
c
i
t, where  Nc=∑i=1Npiit.
Step
2. Update Cit by the mutation operation Om:
D
i
t
=
O
m
C
i
t
=
d
1
i
t
,
d
2
i
t
,
…
,
d
N
c
i
t.
Step
3. Generate preponderant antibody population Pit and neighboring antibody population
Q
i
t from Dit by selection operation Os.
Step
4. If the size of P(it) is larger than Na, sort antibodies by their crowding distances [35] in
descending order and select the top Na antibodies to form new antibody population P′it,
otherwise P′it=Pit:
P
′
i
t
=
O
u
P
i
t
=
p
′
1
i
t
,
p
′
2
i
t
,
…
,
p
′
N
a
i
t.
Step
5. Produce new memory unit M′it by applying study operation Ol on Mit and P′it:
M
′
(
i
t
)
=
O
l
M
i
t
,
P
′
i
t
=
m
′
1
i
t
,
m
′
2
i
t
,
…
,
m
′
R
i
t
+
1
i
t, where  Rit+1≤Nm.
Step
6. Update Qit by the self-repairing operation Or:
Q
′
i
t
=
O
r
Q
i
t
=
q
′
1
i
t
,
q
′
2
i
t
,
…
,
q
′
N
q
i
t.
Step
7. Produce new standby unit B′it by applying replacement operation Oa on Bit and Q′it:
B
′
i
t
=
O
a
B
i
t
,
Q
′
i
t
=
b
′
1
i
t
,
b
′
2
i
t
,
…
,
b
′
N
b
i
t.
Step
8. If it≥T, output M′it and end, otherwise Ait+1=P′it, Mit+1=M′it,
B
(
i
t
+
1
)
=
B
′
i
t, it=it+1, go to Step 1.(
1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.Antibody Population.The algorithm maintains an antibody population A(it)={a1(it),a2(it),…,aNa(it)} at the itth generation, where Na is the size of the population. Antibody ai(it) is the encoding of candidate solution X for the Problem P; that is, ai(it)=e(X)=(ai1(it),ai2(it),…,ain(it)), 1≤i≤Na, where n is the length of the antibody and aif(it)=k means placing the instance represented by vf on the service node nk; namely, xkf=1. In particular, if vf represents the source or destination of flow, aif(it) is a known quantity and will not be changed by the following operations.By this encoding method, the two-dimensional mapping relation between instances and service nodes is transformed to one-dimensional vector, which satisfies (8) and (10)–(12) inherently. So (9) is used to judge the feasibility of ai(it).We introduce a new functiongir(X(i,:))=max{0,∑vf∈Vinsxfi·resfr-ci(r)}, where ni∈Nsr and r∈R. Assume that f3(X)=∑ni∈Nsr∑r∈Rgir(X(i,:)). If f3(e-1(ai(it)))=0, namely, X=e-1(ai(it)) satisfies all constraints of the Problem P, ai(it) is called feasible antibody. Otherwise, ai(it) is called infeasible antibody. Furthermore, f3(e-1(ai(it))) is used to measure the degree of constraint violation of an infeasible antibody. The larger it is, the deeper the degree of constraint violation of ai(it) is.If two feasible antibodies,ai(it) and aj(it), satisfy the condition that (∀k=1,2:fk(e-1(ai(it)))≤fk(e-1(aj(it))))∧(∃g=1,2:fg(e-1(ai(it)))<fg(e-1(aj(it)))), ai(it) is said to Pareto dominate aj(it), denoted as ai(it)≻aj(it). Furthermore, ai(it) is called Pareto-optimal if there does not exist another feasible antibody a∗(it) in A(it) that satisfies a∗(it)≻ai(it).Memory Unit.Memory unit M(it)={m1(it),m2(it),…,mR(it)(it)} is defined as the set of all Pareto-optimal antibodies in A(it), whose size R(it) changes dynamically. In other words, it contains service node selection schemes that are Pareto-optimal. We can implement any one scheme in it. To improve the quality of solutions, we assume that the upper limit of R(it) is Nm.Standby Unit.Standby unit B(it)={b1(it),b2(it),…,bNb(it)}, whose size is Nb, is defined as the set of infeasible antibodies with relatively low degree of constraint violation in A(it).(
2) Operation Description. We describe operations in the proposed algorithm successively.Initializing Operation.To improve the quality of initial solutions, we propose an antibody population initialization algorithm based on preference. The preference of the instance vf for the service node ni is defined as pffi=1/((1/R)∑r∈Rλr2-1/R∑r∈Rλr2+σ), where λr=resfr/ci(r) is the occupancy ratio of resource r in ni occupied by vf and σ is a small positive constant to avoid dividing by zero in computing the preference. Then the preference list of vf, denoted as PL(vf), is built by sorting service nodes by pffi in descending order. Note that preference lists are known before running the algorithm.The key idea of our algorithm is to traverse preference list of each instance until finding the service node satisfying resource constraint and distance constraint so as to achieve optimization objectives initially. The basic procedure is shown in Algorithm3. Here, function Selectfirst(PL(vf)) means traversing PL(vf) in sequence until finding ni which is the first service node satisfying two conditions simultaneously: (i) ∀r∈R, resfr≤ci(r); (ii) ∀vj∈pre(vf),aj=g, hop(ng,ni)≤θ. If all nodes in PL(vf) just satisfy only one condition, it selects the first node satisfying condition (i). If all nodes do not satisfy condition (i), it randomly selects a service node occupied by an instance of pre(vf).Algorithm 3:Antibody population initialization algorithm based on preference.
Input: Gv, preference lists of all instances, the upper limit of hops between two nodes θ
Output: Initial antibody population
for  m=1 to Na  do
T
r
s
=
⌀
while  (Trs≠Vins)
for all vf∈Vins  do
if  idgvf=0  then  //idgvf  is the in-degree of vf
n
i
=
S
e
l
e
c
t
f
i
r
s
t
(
P
L
(
v
f
)
)
a
m
f
=
i
for all r∈R  do
c
i
(
r
)
=
c
i
(
r
)
-
r
e
s
f
r
end for
i
d
g
v
f
=
i
d
g
v
f
-
1
T
r
s
=
T
r
s
⋃
{
v
f
}
for  all vk∈succ(vf)  do
i
d
g
v
k
=
i
d
g
v
k
-
1
end for
end if
end for
end while
m
=
m
+
1
end for
return  A(0)={a1(0),a2(0),…,aNa(0)}Clone Operation.
O
c is defined as Oc(A(it))={Oc(a1(it)),Oc(a2(it)),…,Oc(aNa(it))}, where Oc(ai(it))={a11(it),…,a1pi(it)(it)}, 1≤i≤Na, and pi(it) is the clone scale of ai(it)(13)piit=IntH·ηiit∑j=1Nitηjit·1ψiit.p
i
(
i
t
) is given by (13) and can self-adaptively be adjusted by the antibody-antibody affinity ψi(it) and the antibody-antigen affinity ηi(it). Their detailed definitions are as follows:(i)
Antibody-antibody affinityψi(it): it is measured by the Euclidean distance between ai(it) and other antibodies: ψi(it)=min{exp(-ai(it)-aj(it))}, where i≠j, 1≤j≤Na; · represents Euclidean distance, and it is normalized to [0,1].(ii)
Antibody-antigen affinityηi(it). (14)Rijakit=1fje-1aiit≤fje-1akit,0else,(15)ηijit=∑k=1NaRijakit,(16)ηiit=∑j=13ηijit.To unify the affinity computation of feasible and infeasible antibodies, we regardminf3(X) as an objective of the Problem P. So given a single antigen (i.e., an objective function) fj(X), we can obtain relative affinity between the antibody ai(it) and the antigen fj(X), denoted as ηij(it) ((15)), through comparing the objective value of ai(it) (i.e., fj(e-1(ai(it)))) with objective values of other antibodies ((14)). For the Problem P with multiple objectives, ηi(it) is defined as the sum of relative affinities between ai(it) and each objective ((16)). This method can eliminate the bad influence of a too large or too small objective value on the affinity.H is a given value relating to clone scale (we assume that H=3N) and the function Int() returns the value of a number rounded upwards to the nearest integer. Apparently, the clone scale decreases with the increase of inhibitory effect between antibodies (namely, ψi(it) increases) and the decrease of antigen stimulation (namely, ηi(it) decreases).Mutation Operation.Since every value in antibody indicates a service node, we propose a new mutation strategy to make the mutation operation meaningful. For each antibody in C(it), we select two values in it randomly and exchange them with probability of mp=mp0·(1-it/T), where mp0 is the initial mutation probability, and it and T are the current and the maximum number of iterations, respectively. Apparently, mp decreases with the proposed algorithm running.Selection Operation.First of all, we separate feasible antibodies from infeasible ones. Then, we extract Pareto-optimal antibodies from the former to form the preponderant antibody population P(it). Meanwhile, we choose Nq antibodies with the lowest degree of constraint violation from infeasible antibodies to form the neighboring antibody population Q(it). Adding antibodies of Q(it), which approximate the edge of feasible region, to the next iteration can improve diversity of antibody population.Self-Repairing Operation.Through migrating instances from overloaded service nodes to those with abundant resources, self-repairing operation can reduce the degree of constraint violation of infeasible antibody and make it enter or be more close to feasible region. Let Q(it)={q1(it),q2(it),…,qNq(it)} be the neighboring antibody population. Assume that antibodies in Q(it) are sorted by the degree of constraint violation in descending order. For an antibody qi(it), the resource burden of service node nj is defined as burj=∑r∈Rmax{0,∑k∈{k∣qik=j}reskr-cj(r)}/cj(r). If there exists a node without burden, that is, burj=0, self-repairing operation will be applied to qi(it). Specifically, starting from nj with the heaviest burden, it selects an instance vk randomly and migrates it to the node nj′ with burj′=0, that is, replacing qik=j with qik=j′. If the degree of constraint violation of the new antibody qi′(it) is smaller than that of qi(it), this migration is accepted. Otherwise, it selects another instance and repeats the previous migration until all instances on nj are traversed. Then it tries to do migration in other nodes until there are no nodes without burden. Assuming that self-repairing operation is only applied to m antibodies, the time consumption can be controlled by adjusting m. In other words, m is the depth of self-repairing operation.Replacement Operation.It replaces the antibodies in the standby unit with the antibodies which have lower degree of constraint violation in the neighboring antibody population. It ensures that the standby unit approximates feasible region gradually.Study Operation.Through comparing antibodies in the updated preponderant antibody population with those in the memory unit, study operation updates the memory unit with the newest Pareto-optimal antibodies. If the size of memory unit exceeds Nm, updating operation based on crowding distance will be applied [35].


## 5.2.1. Formulation

(3)
m
i
n
max
n
i
∈
N
sr
⁡
f
r
a
i
,
(4)
u
t
l
i
r
=
∑
v
f
∈
V
i
n
s
x
i
f
·
r
e
s
f
r
c
i
r
,
(5)
u
t
l
i
¯
=
∑
r
∈
R
u
t
l
i
r
R
,
(6)
f
r
a
i
=
∑
r
∈
R
u
t
l
i
r
u
t
l
i
¯
-
1
2
,
(7)
m
i
n
max
s
,
d
∈
Φ
⁡
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
m
,
n
∈
N
x
u
m
·
x
v
n
·
h
o
p
m
,
n
,
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
m
,
n
∈
N
x
u
m
·
x
v
n
·
h
o
p
m
,
n
(8)
s
.
t
.
∀
v
f
∈
V
i
n
s
:
∑
n
i
∈
N
s
r
x
i
f
=
1
,
(9)
∀
n
i
∈
N
s
r
,
∀
r
∈
R
:
∑
v
f
∈
V
i
n
s
x
i
f
·
r
e
s
f
r
≤
c
i
r
(10)
∀
v
s
∈
V
e
n
d
,
∀
n
i
∈
N
e
n
d
-
a
:
x
a
s
=
1
,
x
i
s
=
0
,
(11)
∀
v
d
∈
V
e
n
d
,
∀
n
i
∈
N
e
n
d
-
a
′
:
x
a
′
d
=
1
,
x
i
d
=
0
,
(12)
∀
n
i
∈
N
s
r
,
∀
v
f
∈
V
i
n
s
:
x
i
f
∈
0,1
.As resource fragmentation limits network to accept security requests, we take minimizing the maximum resource fragmentation of service nodes ((3)) as an objective. frai ((6)) measures the resource fragmentation of ni by computing the deviation between utilizations of different resources ((4) and (5)). The smaller the deviation is, the more balanced the utilizations are. Additionally, we consider security service latency by optimizing the length of routing path. For the sake of simplicity, we define the path length between two instances (we regard the source and destination of flow as instances with fixed physical locations in node mapping phase and link mapping phase) as the minimum number of hops of all paths between the service nodes they are placed on. Then for a virtual path, its length is the sum of path lengths between instances along it. As a flow may correspond to several virtual paths constructed by different instances in the virtual security service topology, we define the length of routing path as the maximum length of all virtual paths. So minimizing the maximum length of routing path ((7)) is regarded as another objective.Thus, we provide a constrained multiobjective optimization formulation, denoted as Problem P. It seeks to obtain the optimal selection of service nodes without violating the constraints of capacities of physical nodes and links. Our formulation is as follows.Equation (8) guarantees that an instance must be placed on exactly one service node; (9) constrains the fact that resource demands of all instances placed on a service node should be less than or equal to available resources in that node; (10) and (11) ensure that physical locations of the source and destination of a flow are respected, respectively; (12) constrains decision variables to be 0 or 1. For the sake of clarify, we denote (3) and (7) as f1(X) and f2(X), where X=(xij)|Nsr+Nend|×|Vins+Vend|.


## 5.2.2. Proposed Algorithm

To obtain the Pareto-optimal solutions of the above problem, inspired by immune memory clonal algorithms [33, 34], we propose a service node selection algorithm based on bidirectional memory. The key idea is to approximate the Pareto-optimal solutions from feasible and infeasible regions. The basic procedure of our algorithm is shown in Algorithm 2. It first establishes the memory unit and the standby unit to reserve the current Pareto-optimal feasible and infeasible solutions, respectively. After implementing clone, mutation, and selection operation, it extracts preponderant antibody population and neighboring antibody population from the whole population. Then the former integrates with the previous Pareto-optimal solutions in memory unit, which ensures that the quality of solutions is not degraded. The latter cooperates with the standby unit to approximate the Pareto-optimal solutions from infeasible region, which maintains diversity of antibody population. Additionally, the newly obtained Pareto-optimal solutions are used as the initial antibody population in next iteration, which accelerates convergence rate of the proposed algorithm. The main data structures and detailed operations are presented as follows.Algorithm 2:Service node selection algorithm based on bidirectional memory.
Input: Maximum number of iterations T, maximum size of antibody population Na, maximum
size of memory unit Nm, size of standby unit Nb, initial mutation probability mp0
Output: Memory unit Mit
Initializeit=0; initializing antibody population Ait, memory unit Mit and standby unit Bit.
Step
1. Generate Cit from Ait by the clone operation Oc:
C
i
t
=
O
c
A
i
t
=
=
c
1
i
t
,
c
2
i
t
,
…
,
c
N
c
i
t, where  Nc=∑i=1Npiit.
Step
2. Update Cit by the mutation operation Om:
D
i
t
=
O
m
C
i
t
=
d
1
i
t
,
d
2
i
t
,
…
,
d
N
c
i
t.
Step
3. Generate preponderant antibody population Pit and neighboring antibody population
Q
i
t from Dit by selection operation Os.
Step
4. If the size of P(it) is larger than Na, sort antibodies by their crowding distances [35] in
descending order and select the top Na antibodies to form new antibody population P′it,
otherwise P′it=Pit:
P
′
i
t
=
O
u
P
i
t
=
p
′
1
i
t
,
p
′
2
i
t
,
…
,
p
′
N
a
i
t.
Step
5. Produce new memory unit M′it by applying study operation Ol on Mit and P′it:
M
′
(
i
t
)
=
O
l
M
i
t
,
P
′
i
t
=
m
′
1
i
t
,
m
′
2
i
t
,
…
,
m
′
R
i
t
+
1
i
t, where  Rit+1≤Nm.
Step
6. Update Qit by the self-repairing operation Or:
Q
′
i
t
=
O
r
Q
i
t
=
q
′
1
i
t
,
q
′
2
i
t
,
…
,
q
′
N
q
i
t.
Step
7. Produce new standby unit B′it by applying replacement operation Oa on Bit and Q′it:
B
′
i
t
=
O
a
B
i
t
,
Q
′
i
t
=
b
′
1
i
t
,
b
′
2
i
t
,
…
,
b
′
N
b
i
t.
Step
8. If it≥T, output M′it and end, otherwise Ait+1=P′it, Mit+1=M′it,
B
(
i
t
+
1
)
=
B
′
i
t, it=it+1, go to Step 1.(
1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.Antibody Population.The algorithm maintains an antibody population A(it)={a1(it),a2(it),…,aNa(it)} at the itth generation, where Na is the size of the population. Antibody ai(it) is the encoding of candidate solution X for the Problem P; that is, ai(it)=e(X)=(ai1(it),ai2(it),…,ain(it)), 1≤i≤Na, where n is the length of the antibody and aif(it)=k means placing the instance represented by vf on the service node nk; namely, xkf=1. In particular, if vf represents the source or destination of flow, aif(it) is a known quantity and will not be changed by the following operations.By this encoding method, the two-dimensional mapping relation between instances and service nodes is transformed to one-dimensional vector, which satisfies (8) and (10)–(12) inherently. So (9) is used to judge the feasibility of ai(it).We introduce a new functiongir(X(i,:))=max{0,∑vf∈Vinsxfi·resfr-ci(r)}, where ni∈Nsr and r∈R. Assume that f3(X)=∑ni∈Nsr∑r∈Rgir(X(i,:)). If f3(e-1(ai(it)))=0, namely, X=e-1(ai(it)) satisfies all constraints of the Problem P, ai(it) is called feasible antibody. Otherwise, ai(it) is called infeasible antibody. Furthermore, f3(e-1(ai(it))) is used to measure the degree of constraint violation of an infeasible antibody. The larger it is, the deeper the degree of constraint violation of ai(it) is.If two feasible antibodies,ai(it) and aj(it), satisfy the condition that (∀k=1,2:fk(e-1(ai(it)))≤fk(e-1(aj(it))))∧(∃g=1,2:fg(e-1(ai(it)))<fg(e-1(aj(it)))), ai(it) is said to Pareto dominate aj(it), denoted as ai(it)≻aj(it). Furthermore, ai(it) is called Pareto-optimal if there does not exist another feasible antibody a∗(it) in A(it) that satisfies a∗(it)≻ai(it).Memory Unit.Memory unit M(it)={m1(it),m2(it),…,mR(it)(it)} is defined as the set of all Pareto-optimal antibodies in A(it), whose size R(it) changes dynamically. In other words, it contains service node selection schemes that are Pareto-optimal. We can implement any one scheme in it. To improve the quality of solutions, we assume that the upper limit of R(it) is Nm.Standby Unit.Standby unit B(it)={b1(it),b2(it),…,bNb(it)}, whose size is Nb, is defined as the set of infeasible antibodies with relatively low degree of constraint violation in A(it).(
2) Operation Description. We describe operations in the proposed algorithm successively.Initializing Operation.To improve the quality of initial solutions, we propose an antibody population initialization algorithm based on preference. The preference of the instance vf for the service node ni is defined as pffi=1/((1/R)∑r∈Rλr2-1/R∑r∈Rλr2+σ), where λr=resfr/ci(r) is the occupancy ratio of resource r in ni occupied by vf and σ is a small positive constant to avoid dividing by zero in computing the preference. Then the preference list of vf, denoted as PL(vf), is built by sorting service nodes by pffi in descending order. Note that preference lists are known before running the algorithm.The key idea of our algorithm is to traverse preference list of each instance until finding the service node satisfying resource constraint and distance constraint so as to achieve optimization objectives initially. The basic procedure is shown in Algorithm3. Here, function Selectfirst(PL(vf)) means traversing PL(vf) in sequence until finding ni which is the first service node satisfying two conditions simultaneously: (i) ∀r∈R, resfr≤ci(r); (ii) ∀vj∈pre(vf),aj=g, hop(ng,ni)≤θ. If all nodes in PL(vf) just satisfy only one condition, it selects the first node satisfying condition (i). If all nodes do not satisfy condition (i), it randomly selects a service node occupied by an instance of pre(vf).Algorithm 3:Antibody population initialization algorithm based on preference.
Input: Gv, preference lists of all instances, the upper limit of hops between two nodes θ
Output: Initial antibody population
for  m=1 to Na  do
T
r
s
=
⌀
while  (Trs≠Vins)
for all vf∈Vins  do
if  idgvf=0  then  //idgvf  is the in-degree of vf
n
i
=
S
e
l
e
c
t
f
i
r
s
t
(
P
L
(
v
f
)
)
a
m
f
=
i
for all r∈R  do
c
i
(
r
)
=
c
i
(
r
)
-
r
e
s
f
r
end for
i
d
g
v
f
=
i
d
g
v
f
-
1
T
r
s
=
T
r
s
⋃
{
v
f
}
for  all vk∈succ(vf)  do
i
d
g
v
k
=
i
d
g
v
k
-
1
end for
end if
end for
end while
m
=
m
+
1
end for
return  A(0)={a1(0),a2(0),…,aNa(0)}Clone Operation.
O
c is defined as Oc(A(it))={Oc(a1(it)),Oc(a2(it)),…,Oc(aNa(it))}, where Oc(ai(it))={a11(it),…,a1pi(it)(it)}, 1≤i≤Na, and pi(it) is the clone scale of ai(it)(13)piit=IntH·ηiit∑j=1Nitηjit·1ψiit.p
i
(
i
t
) is given by (13) and can self-adaptively be adjusted by the antibody-antibody affinity ψi(it) and the antibody-antigen affinity ηi(it). Their detailed definitions are as follows:(i)
Antibody-antibody affinityψi(it): it is measured by the Euclidean distance between ai(it) and other antibodies: ψi(it)=min{exp(-ai(it)-aj(it))}, where i≠j, 1≤j≤Na; · represents Euclidean distance, and it is normalized to [0,1].(ii)
Antibody-antigen affinityηi(it). (14)Rijakit=1fje-1aiit≤fje-1akit,0else,(15)ηijit=∑k=1NaRijakit,(16)ηiit=∑j=13ηijit.To unify the affinity computation of feasible and infeasible antibodies, we regardminf3(X) as an objective of the Problem P. So given a single antigen (i.e., an objective function) fj(X), we can obtain relative affinity between the antibody ai(it) and the antigen fj(X), denoted as ηij(it) ((15)), through comparing the objective value of ai(it) (i.e., fj(e-1(ai(it)))) with objective values of other antibodies ((14)). For the Problem P with multiple objectives, ηi(it) is defined as the sum of relative affinities between ai(it) and each objective ((16)). This method can eliminate the bad influence of a too large or too small objective value on the affinity.H is a given value relating to clone scale (we assume that H=3N) and the function Int() returns the value of a number rounded upwards to the nearest integer. Apparently, the clone scale decreases with the increase of inhibitory effect between antibodies (namely, ψi(it) increases) and the decrease of antigen stimulation (namely, ηi(it) decreases).Mutation Operation.Since every value in antibody indicates a service node, we propose a new mutation strategy to make the mutation operation meaningful. For each antibody in C(it), we select two values in it randomly and exchange them with probability of mp=mp0·(1-it/T), where mp0 is the initial mutation probability, and it and T are the current and the maximum number of iterations, respectively. Apparently, mp decreases with the proposed algorithm running.Selection Operation.First of all, we separate feasible antibodies from infeasible ones. Then, we extract Pareto-optimal antibodies from the former to form the preponderant antibody population P(it). Meanwhile, we choose Nq antibodies with the lowest degree of constraint violation from infeasible antibodies to form the neighboring antibody population Q(it). Adding antibodies of Q(it), which approximate the edge of feasible region, to the next iteration can improve diversity of antibody population.Self-Repairing Operation.Through migrating instances from overloaded service nodes to those with abundant resources, self-repairing operation can reduce the degree of constraint violation of infeasible antibody and make it enter or be more close to feasible region. Let Q(it)={q1(it),q2(it),…,qNq(it)} be the neighboring antibody population. Assume that antibodies in Q(it) are sorted by the degree of constraint violation in descending order. For an antibody qi(it), the resource burden of service node nj is defined as burj=∑r∈Rmax{0,∑k∈{k∣qik=j}reskr-cj(r)}/cj(r). If there exists a node without burden, that is, burj=0, self-repairing operation will be applied to qi(it). Specifically, starting from nj with the heaviest burden, it selects an instance vk randomly and migrates it to the node nj′ with burj′=0, that is, replacing qik=j with qik=j′. If the degree of constraint violation of the new antibody qi′(it) is smaller than that of qi(it), this migration is accepted. Otherwise, it selects another instance and repeats the previous migration until all instances on nj are traversed. Then it tries to do migration in other nodes until there are no nodes without burden. Assuming that self-repairing operation is only applied to m antibodies, the time consumption can be controlled by adjusting m. In other words, m is the depth of self-repairing operation.Replacement Operation.It replaces the antibodies in the standby unit with the antibodies which have lower degree of constraint violation in the neighboring antibody population. It ensures that the standby unit approximates feasible region gradually.Study Operation.Through comparing antibodies in the updated preponderant antibody population with those in the memory unit, study operation updates the memory unit with the newest Pareto-optimal antibodies. If the size of memory unit exceeds Nm, updating operation based on crowding distance will be applied [35].


## 5.3. Link Mapping Phase

This phase is to route flows among the selected service nodes based on the virtual security service topology. We refer to this problem as the service path establishment problem. Since a flow can be split and the capacity of physical link is limited, we treat virtual links as commodities and model the service path establishment problem as the capacitated multicommodity flow problem.


### 5.3.1. Formulation

(17)
m
i
n
max
s
,
d
∈
Φ
⁡
c
l
t
s
d
,
(18)
c
l
t
s
d
=
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
e
m
,
n
∈
E
s
t
f
y
m
,
n
u
,
v
·
l
a
t
m
,
n
+
∑
v
f
∈
φ
π
i
p
d
f
,
(19)
s
.
t
.
∀
e
m
,
n
∈
E
:
∑
l
u
,
v
∈
L
y
m
,
n
u
,
v
≤
b
w
m
,
n
,
(20)
∀
l
u
,
v
∈
L
,
x
u
b
=
x
v
b
′
=
1
,
∀
n
∈
N
-
b
,
b
′
:
∑
c
∈
N
y
c
,
n
u
,
v
-
∑
c
′
∈
N
y
n
,
c
′
u
,
v
=
0
,
∑
c
∈
N
y
c
,
b
u
,
v
=
∑
c
′
∈
N
y
b
′
,
c
′
u
,
v
=
0
,
∑
c
∈
N
y
b
,
c
u
,
v
=
∑
c
′
∈
N
y
c
′
,
b
′
u
,
v
=
d
b
u
,
v
,
(21)
∀
e
m
,
n
∈
E
,
l
u
,
v
∈
L
:
y
m
,
n
u
,
v
≤
z
m
′
,
n
′
m
,
n
·
x
u
m
′
·
x
v
n
′
·
min
⁡
b
w
m
,
n
,
d
b
u
,
v
,
(22)
∀
e
m
,
n
∈
E
,
l
u
,
v
∈
L
:
y
m
,
n
u
,
v
≥
0
.A security request may correspond to multiple virtual paths constructed by different instances in the virtual security service topology. So the maximum latency of those paths is regarded as the service latency of security request ((18)), where stf() is step function and it is assumed that stf(0)=0; (19) is a constraint on the maximum bandwidth of physical links that can be assigned to different virtual links; (20) is the flow conservation constraint. It ensures that, for every node n in the physical network, if one of its incoming links belongs to the path which a virtual link is mapped to, one of its outgoing links also belongs to that path. Excluded from this rule is the case where the node is one of the nodes to which the two end nodes of virtual link are mapped; (21) constrains the fact that a virtual link must be mapped to the path between the two nodes whose end nodes are mapped to. Note that zm′,n′(m,n), xum′, and xvn′ are not decision variables but introduced to express that constraint; (22) is a constraint on the values of decision variables.


### 5.3.2. Proposed Algorithm

Since the capacitated multicommodity flow problem is NP-Hard [36], we propose a heuristic named service path establishment algorithm based on hybrid taboo search. Before introducing the algorithm, we describe the main data structures followed by discussing the key aspects of the algorithm: neighborhood search method, evaluation function, and termination condition.(
1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.Initial Solution Set.The initial solution set is defined as S0={s1,s2,…,sn}, where si=ym,nu,vE×L, 1≤i≤n. Take the process of generating an initial solution as an example. Assume that every virtual link has a set of k-shortest physical paths between the two nodes whose start and end node are mapped to. The algorithm randomly selects a node of which the in-degree equals 0 in the virtual security service topology and maps virtual links connected to that node to physical paths. For each virtual link, single path mapping is applied first. Specifically, physical path in its k-shortest path set is traversed in increasing order of their lengths until a path satisfying bandwidth demand is found. If no such single path exists, multipath mapping is applied, which prefers to assign as much bandwidth demand as possible to relatively short physical path. After all virtual links connected to the node have been mapped, the node and virtual links are marked as “traversed" and removed from the virtual topology. Then another node of which the in-degree equals 0 will be chosen to repeat the above operation. An initial solution is generated after all nodes and links in the virtual topology have been traversed.Dominant Solution Set.For S0={s1,s2,…,sn}, solutions are sorted by their objective function values (i.e., max(s,d)∈Φ⁡(cltsd), denoted as h(si)) in ascending order. So the first m solutions are chosen to form the dominant solution set. It is denoted as DS={s1,s2,…,sm}, where h(s1)≤⋯≤h(sm). During the running time, DS will be updated continually to ensure that it always keeps the optimal solutions. Moreover, the depth of local search is adjusted dynamically according to whether DS is updated or not.Tabu List.Assuming that virtual links and physical links are identified by positive integers, the tabu list is defined as TL=({(l,{yab∣1≤a≤E,b=l})∣1≤l≤L},ctl), where l is the identification of virtual link and yab is the bandwidth assigned to the virtual link b by the physical link a. The length of TL is set to be 7 [36].(
2) Key Aspect Description. In what follows, we discuss three key aspects with respect to the proposed algorithm.Neighborhood Search Method.Given the solution si, its neighborhood N(si)=NeborConss,ns={si1,si2,…,sins} can be built as follows. First, a virtual link is selected randomly. Then through adjusting the bandwidth demand assigned to each physical path in its k-shortest path set, a new service path establishment scheme, or in other words a neighboring solution si1 is generated. It is particularly important that the new scheme should satisfy the overall bandwidth demand of the selected virtual link. Similarly, other (ns-1) neighboring solutions can be generated. The size of N(si) is defined as ns=nsmin+nt·(nsmax-nsmin)/NT, where nsmax=L and nsmin=0.5L are the maximum and the minimum size of neighborhood, respectively, and nt and NT are the current and the maximum number of iterations of neighborhood search, respectively. Note that though the generated neighboring solutions satisfy (20) and (21), some of them may violate (19), which should be eliminated.Evaluation Function.It is denoted asEvaluate(). We take the objective function h(s) as the evaluation function. To eliminate infeasible solutions, a highest evaluation value will be assigned to them.Termination Condition.The algorithm will terminate as long as one of the following conditions are satisfied: the number of iterations exceeds T; solutions are not improved; namely, the objective function value remains constant after R successive iterations.The basic procedure of our algorithm is shown in Algorithm4. Here, we use the functions Update(DS,S0) and Update(DS,N(s)) to replace some solutions in DS with better ones in S0 and N(s), respectively. We also use roulette wheel strategy to select the candidate solution set from N(s), denoted as Roulette_wheel(N(s)).Algorithm 4:Service path establishment algorithm based on hybrid taboo search.
Input: NT, T, R
Output: The best solution s∗
Initialize:DS=⌀; TL=⌀; t=0; impro=0
Generate initial solution setS0
UpdateDS,S0
while  (t<T and noimpro<R)
Randomly select s from DS
r
=
h
D
S
1
n
t
=
0
s
b
e
s
t
=
s
while  (nt<NT)
N
(
s
)
=
N
e
b
o
r
C
o
n
s
s
,
n
s
E
v
a
l
u
a
t
e
N
s
i
s
u
p
d
a
t
e
d
=
U
p
d
a
t
e
D
S
,
N
s
if isupdated then  nt=0
else  nt++
end if
C
S
=
R
o
u
l
e
t
t
e
_
w
h
e
e
l
(
N
(
s
)
)
if  isaspiration  then
s
=
S
e
l
e
c
t
B
e
s
t
C
S
s
b
e
s
t
=
s
Update the tabu list TL
else
s
=
S
e
l
e
c
t
B
e
s
t
_
n
o
t
a
b
u
C
S
Update the tabu list TL
end if
end while
t
+
+
if  hDS1<r  then  noimpro=0
else  noimpro++
end if
end while
return  DS1The algorithm generates multiple initial solutions based on greedy strategy and randomly selects one solution as the start point of iteration, which can solve the problem that tabu search relies heavily on initial solution. Additionally, it takes into account both diversification and intensification strategy. On the one hand, the longer the dominant solution set is not updated during neighborhood search, the larger the search space is. It reflects that the algorithm increases diversity of solutions by expanding search space, which benefits finding better solutions. On the other hand, the dominant solution set keeps the firstm excellent solutions so far and every iterative search starts from them. It reflects that the algorithm is exploited in promising space through concentrating on searching the neighborhood of the current excellent solutions.


## 5.3.1. Formulation

(17)
m
i
n
max
s
,
d
∈
Φ
⁡
c
l
t
s
d
,
(18)
c
l
t
s
d
=
max
π
i
∈
π
s
,
d
⁡
∑
l
u
,
v
∈
π
i
∑
e
m
,
n
∈
E
s
t
f
y
m
,
n
u
,
v
·
l
a
t
m
,
n
+
∑
v
f
∈
φ
π
i
p
d
f
,
(19)
s
.
t
.
∀
e
m
,
n
∈
E
:
∑
l
u
,
v
∈
L
y
m
,
n
u
,
v
≤
b
w
m
,
n
,
(20)
∀
l
u
,
v
∈
L
,
x
u
b
=
x
v
b
′
=
1
,
∀
n
∈
N
-
b
,
b
′
:
∑
c
∈
N
y
c
,
n
u
,
v
-
∑
c
′
∈
N
y
n
,
c
′
u
,
v
=
0
,
∑
c
∈
N
y
c
,
b
u
,
v
=
∑
c
′
∈
N
y
b
′
,
c
′
u
,
v
=
0
,
∑
c
∈
N
y
b
,
c
u
,
v
=
∑
c
′
∈
N
y
c
′
,
b
′
u
,
v
=
d
b
u
,
v
,
(21)
∀
e
m
,
n
∈
E
,
l
u
,
v
∈
L
:
y
m
,
n
u
,
v
≤
z
m
′
,
n
′
m
,
n
·
x
u
m
′
·
x
v
n
′
·
min
⁡
b
w
m
,
n
,
d
b
u
,
v
,
(22)
∀
e
m
,
n
∈
E
,
l
u
,
v
∈
L
:
y
m
,
n
u
,
v
≥
0
.A security request may correspond to multiple virtual paths constructed by different instances in the virtual security service topology. So the maximum latency of those paths is regarded as the service latency of security request ((18)), where stf() is step function and it is assumed that stf(0)=0; (19) is a constraint on the maximum bandwidth of physical links that can be assigned to different virtual links; (20) is the flow conservation constraint. It ensures that, for every node n in the physical network, if one of its incoming links belongs to the path which a virtual link is mapped to, one of its outgoing links also belongs to that path. Excluded from this rule is the case where the node is one of the nodes to which the two end nodes of virtual link are mapped; (21) constrains the fact that a virtual link must be mapped to the path between the two nodes whose end nodes are mapped to. Note that zm′,n′(m,n), xum′, and xvn′ are not decision variables but introduced to express that constraint; (22) is a constraint on the values of decision variables.


## 5.3.2. Proposed Algorithm

Since the capacitated multicommodity flow problem is NP-Hard [36], we propose a heuristic named service path establishment algorithm based on hybrid taboo search. Before introducing the algorithm, we describe the main data structures followed by discussing the key aspects of the algorithm: neighborhood search method, evaluation function, and termination condition.(
1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.Initial Solution Set.The initial solution set is defined as S0={s1,s2,…,sn}, where si=ym,nu,vE×L, 1≤i≤n. Take the process of generating an initial solution as an example. Assume that every virtual link has a set of k-shortest physical paths between the two nodes whose start and end node are mapped to. The algorithm randomly selects a node of which the in-degree equals 0 in the virtual security service topology and maps virtual links connected to that node to physical paths. For each virtual link, single path mapping is applied first. Specifically, physical path in its k-shortest path set is traversed in increasing order of their lengths until a path satisfying bandwidth demand is found. If no such single path exists, multipath mapping is applied, which prefers to assign as much bandwidth demand as possible to relatively short physical path. After all virtual links connected to the node have been mapped, the node and virtual links are marked as “traversed" and removed from the virtual topology. Then another node of which the in-degree equals 0 will be chosen to repeat the above operation. An initial solution is generated after all nodes and links in the virtual topology have been traversed.Dominant Solution Set.For S0={s1,s2,…,sn}, solutions are sorted by their objective function values (i.e., max(s,d)∈Φ⁡(cltsd), denoted as h(si)) in ascending order. So the first m solutions are chosen to form the dominant solution set. It is denoted as DS={s1,s2,…,sm}, where h(s1)≤⋯≤h(sm). During the running time, DS will be updated continually to ensure that it always keeps the optimal solutions. Moreover, the depth of local search is adjusted dynamically according to whether DS is updated or not.Tabu List.Assuming that virtual links and physical links are identified by positive integers, the tabu list is defined as TL=({(l,{yab∣1≤a≤E,b=l})∣1≤l≤L},ctl), where l is the identification of virtual link and yab is the bandwidth assigned to the virtual link b by the physical link a. The length of TL is set to be 7 [36].(
2) Key Aspect Description. In what follows, we discuss three key aspects with respect to the proposed algorithm.Neighborhood Search Method.Given the solution si, its neighborhood N(si)=NeborConss,ns={si1,si2,…,sins} can be built as follows. First, a virtual link is selected randomly. Then through adjusting the bandwidth demand assigned to each physical path in its k-shortest path set, a new service path establishment scheme, or in other words a neighboring solution si1 is generated. It is particularly important that the new scheme should satisfy the overall bandwidth demand of the selected virtual link. Similarly, other (ns-1) neighboring solutions can be generated. The size of N(si) is defined as ns=nsmin+nt·(nsmax-nsmin)/NT, where nsmax=L and nsmin=0.5L are the maximum and the minimum size of neighborhood, respectively, and nt and NT are the current and the maximum number of iterations of neighborhood search, respectively. Note that though the generated neighboring solutions satisfy (20) and (21), some of them may violate (19), which should be eliminated.Evaluation Function.It is denoted asEvaluate(). We take the objective function h(s) as the evaluation function. To eliminate infeasible solutions, a highest evaluation value will be assigned to them.Termination Condition.The algorithm will terminate as long as one of the following conditions are satisfied: the number of iterations exceeds T; solutions are not improved; namely, the objective function value remains constant after R successive iterations.The basic procedure of our algorithm is shown in Algorithm4. Here, we use the functions Update(DS,S0) and Update(DS,N(s)) to replace some solutions in DS with better ones in S0 and N(s), respectively. We also use roulette wheel strategy to select the candidate solution set from N(s), denoted as Roulette_wheel(N(s)).Algorithm 4:Service path establishment algorithm based on hybrid taboo search.
Input: NT, T, R
Output: The best solution s∗
Initialize:DS=⌀; TL=⌀; t=0; impro=0
Generate initial solution setS0
UpdateDS,S0
while  (t<T and noimpro<R)
Randomly select s from DS
r
=
h
D
S
1
n
t
=
0
s
b
e
s
t
=
s
while  (nt<NT)
N
(
s
)
=
N
e
b
o
r
C
o
n
s
s
,
n
s
E
v
a
l
u
a
t
e
N
s
i
s
u
p
d
a
t
e
d
=
U
p
d
a
t
e
D
S
,
N
s
if isupdated then  nt=0
else  nt++
end if
C
S
=
R
o
u
l
e
t
t
e
_
w
h
e
e
l
(
N
(
s
)
)
if  isaspiration  then
s
=
S
e
l
e
c
t
B
e
s
t
C
S
s
b
e
s
t
=
s
Update the tabu list TL
else
s
=
S
e
l
e
c
t
B
e
s
t
_
n
o
t
a
b
u
C
S
Update the tabu list TL
end if
end while
t
+
+
if  hDS1<r  then  noimpro=0
else  noimpro++
end if
end while
return  DS1The algorithm generates multiple initial solutions based on greedy strategy and randomly selects one solution as the start point of iteration, which can solve the problem that tabu search relies heavily on initial solution. Additionally, it takes into account both diversification and intensification strategy. On the one hand, the longer the dominant solution set is not updated during neighborhood search, the larger the search space is. It reflects that the algorithm increases diversity of solutions by expanding search space, which benefits finding better solutions. On the other hand, the dominant solution set keeps the firstm excellent solutions so far and every iterative search starts from them. It reflects that the algorithm is exploited in promising space through concentrating on searching the neighborhood of the current excellent solutions.


## 5.4. Time Complexity Analysis

We mainly analyze the time complexity of two algorithms in mapping phase.For the service node selection algorithm based on bidirectional memory, we take the first iteration as an example to analyze its time complexity step by step.Na, Nm, and Nb represent the size of the initial antibody population, memory unit, and standby unit, respectively. Firstly, assuming that the number of service nodes and instances is Nsr and Nins, respectively, the worst time complexity of initializing operation is O(Na·Nins·Nsr). Then, the time complexity of building memory unit and standby unit is O(Na2) and O(Na+NalogNb), respectively. Thirdly, if H is a given value relating to clone scale, the worst time complexity of clone operation is O(NaH). Fourthly, if the size of antibody population after cloning is Nc, the time complexity of mutation operation is O(Nc). Fifthly, selection operation includes computing the degree of constraint violation of antibodies, selecting Pareto-optimal antibodies, and choosing Nq antibodies with the lowest degree of constraint violation. Their time complexities are O(Nc), O(Nc2), and O(NclogNq), respectively. Then, if the size of preponderant antibody population after selection operation is K and there are Na Pareto-optimal antibodies that should be reserved, the time complexity of updating preponderant antibody population is O(NaK2). Next, the time complexity of self-repairing operation is O(m·NsrlogNsr) if its depth is m. Then the worst time complexity of replacement operation is O(Nb·Nq). Finally, the time complexity of study operation is O((Na+Nm)2). Therefore, the worst time complexity of the proposed algorithm during the first iteration is O(Na·Nins·Nsr+Nc2+Na·K2+Na2+Nm2).For the service path establishment algorithm based on hybrid taboo search, we take an iteration as an example to analyze its time complexity. Assume that there areL virtual links. The worst time complexity of generating the initial solution set with n solutions is O(nkL). Subsequently, the time complexity of updating the dominant solution set with m solutions is O(nlogm). The main operation in an iteration is building neighborhood with variable size. Considering the process from nt=0 to nt=NT, the number of generated neighboring solutions is NT·nsmin+0.5·(NT+1)·(nsmax-nsmin). So the time complexity of this process can be regarded as O(NT·nsmax). In conclusion, the time complexity of an iteration of the proposed algorithm is O(nkL+NT·nsmax).


## 6. Evaluation

### 6.1. Experimental Setup

Our experiments are conducted on the fat-tree and Waxman topologies. The number of different types of nodes in simulated networks is shown in Table1. The CPU and memory of service nodes are random numbers uniformly distributed between 200 and 500. The latency of each physical link is a number with uniform distribution between 1 and 10 time units. The bandwidth of each physical link is set to 5000. Note that the units for the bandwidth of physical link, the throughput demand of security request, and the throughput of instance are the same in the experiments. We omit them for the sake of simplicity. The above setting is the same for all experiments.Table 1
Simulated networks used in evaluation.
Network
FT-6-A
FT-6-B
FT-8
Waxman
Forwarding node
45
45
80
24
End node
38
27
90
403
Service node
16
27
38
173For the service node selection algorithm of TPSSC, we setT=200, Na=300, Nm=Nb=30, and mp0=0.7. For the service path establishment algorithm, we set NT=20, T=200, and R=50. We design a random algorithm and two greedy algorithms with single objective for comparison, which are denoted as RD, GD-1, and GD-2, respectively. RD randomly selects service nodes and establishes service paths. The goal of GD-1 is to reduce resource fragmentation. For a security request, GD-1 traverses its SSC sequentially and selects the “best" service node for running instance of each security function. The “best" service node has the minimum resource fragmentation after the instance is placed on it. With the objective to reduce security service latency, GD-2 defines the “best" service node as the one that the latency from the previous placed instance to it is the minimum. Note that instances can be placed on the same service node.In the evaluation, we first compare TPSSC against the above three algorithms with respect to length of SSC and throughput demand of security request. Experiments are conducted in the FT-6-B network. In each experiment, there are 300 service requests arriving in a Poisson process. Their sources and destinations are uniformly distributed in the simulated network. Their throughput demands are numbers uniformly distributed between 50 and 250. The length of SSC is fixed to one of{2,4,6,8,10}. As the above three algorithms do not consider the case where several instances of the same security function should be combined to serve a flow, we assume that every security function has only one instance. The CPU demand, memory demand, and throughput of an instance are 10, 10, and 300, respectively. We measure the acceptance ratio, the maximum resource fragmentation, the maximum security service latency, and the time overhead of algorithm. Each experiment is iterated 50 times and the arithmetic mean is reported. The results are shown with their 95% confidence intervals. For the convenience of comparative analysis, we take RD’s value as benchmark and the ratio of the value of other three algorithms to RD’s corresponding value is reported. We also conduct some experiments to analyze the performance of TPSSC specifically.


### 6.2. Results

#### 6.2.1. Acceptance Ratio

Figure3 shows the acceptance ratio of GD-1, GD-2, and TPSSC versus RD. When the length of SSC is less than 4, the acceptance ratios are similar to each other. However, TPSSC, GD-1, and GD-2 have better results for longer SSC. Particularly, TPSSC becomes more and more superior as the length increases. The first reason is that TPSSC takes into account reusing instance for several flows in the designing phase. As a result, fewer resources of service nodes are needed. The second reason is that TPSSC optimizes the allocation of network resources based on the full analysis of all security requests over time. So the situation, where “small" security requests are refused because of network resources having been occupied by “big" security requests in advance, can be avoided to a certain extent.Figure 3
Comparison of acceptance ratio.In order to further evaluate the ability of TPSSC to accept security requests, we measure the acceptance ratio of TPSSC by changing some parameters of security request and network environment.(1) Acceptance Ratio under Different Throughput Demands.Experiments are conducted in the FT-6-A network. In each experiment, there are 400 security requests arriving in a Poisson process. The length of SSC is fixed and the throughput demand of each request is set to one of {50,100,150,200,250}. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 10 and 300. Each experiment is iterated 50 times and the arithmetic mean is reported. The results are shown in Figure 4. Security requests with higher throughput demand and longer SSC have the less opportunity to be accepted because of limited network resources. Moreover, the acceptance ratio drops to less than 20% when the length of SSC is 8 and the throughput demand is 250 due to serious lack of network resources.Figure 4
Acceptance ratio of TPSSC in the FT-6-A network.We also conduct the above experiment in the FT-6-B network. The results are shown in Figure5. The acceptance ratio in the FT-6-B network is higher than that in the FT-6-A network. This is because the former has more service nodes for running more instances. Moreover, it allows TPSSC to choose from a wider range of service nodes and routing paths.Figure 5
Acceptance ratio of TPSSC in the FT-6-B network.(2) Acceptance Ratio under Different Network Scales.Experiments are conducted in the FT-6-A, FT-8, and Waxman network, respectively. In each experiment, there are 1000 security requests arriving in a Poisson process. The length of SSC is fixed and the throughput demands are uniformly distributed between 50 and 250. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 10 and 500. Each experiment is iterated 50 times and the arithmetic mean is reported. Figure 6 shows the results.Figure 6
Acceptance ratio of TPSSC in different network scales.As shown in Figure6, the acceptance ratio in the Waxman network is higher than that in the other two networks. The reason is that there are more network resources in the Waxman network. This experiment also indicates that TPSSC has good scalability and large search space, which can perform well in the network with more nodes and links. In addition, when the length of SSC exceeds 6, the acceptance ratio in the FT-6-B network drops rapidly due to insufficient resources.


#### 6.2.2. Resources Fragmentation

Figure7 shows the maximum resource fragmentation of GD-1, GD-2, and TPSSC versus RD. The results of TPSSC and GD-1 are significantly lower than those of RD and GD-2 since the first two try to minimize resource fragmentation when selecting service nodes. In contrast, RD does not optimize the selection of service nodes and GD-2 prefers to place multiple instances in the same service node. Moreover, the resource fragmentation of GD-2 is higher than that of RD as the length of SSC increases. The reason is that GD-2 can accept more security requests than RD, which further increases resource fragmentation. Meanwhile, the advantage of TPSSC is more and more obvious with the increasing length. This is mainly attributed to the service node selection algorithm based on bidirectional memory, which has high capability of global search and can find the near-optimal service node selection scheme to reduce resource fragmentation as far as possible.Figure 7
Comparison of the maximum resource fragmentation.


#### 6.2.3. Security Service Latency

Figure8 shows the maximum security service latency (namely, the maximum end-to-end latency of flow) of GD-1, GD-2, and TPSSC versus RD. The results of GD-2 and TPSSC are better than those of RD and GD-1 since the first two aim at reducing security service latency. Conversely, GD-1 ignores latency when selecting service nodes, which may result in long security service latency since the selected service nodes may be far away from each other. It is worth noting that the maximum security service latency of TPSSC is slightly longer than that of GD-2 when the length of SSC is less than or equal to 6. It is due to the fact that TPSSC does not take into account the bandwidth of the shortest physical path between two service nodes when placing instances. In fact, it may not satisfy throughput demands of flows. So the placement of instances may still affect reducing security service latency. However, as the length of SSC increases further, GD-2 has to place more instances, which leads to higher possibility of placing instances far away from each other. As a result, the maximum security service latency of TPSSC is shorter than GD-2.Figure 8
Comparison of the maximum security service latency.


#### 6.2.4. Time Overhead of Algorithm

Figure9 shows the time overhead of GD-1, GD-2, and TPSSC versus RD. As expected, the time overhead increases with the length of SSC. RD has the least time overhead since it does not consider any optimizations. When the length of SSC is 10, the time overhead of TPSSC is about 18 times higher than that of RD. But we can see from Figures 3, 7, and 8 that TPSSC can accept nearly 2 times security requests than RD and the maximum resource fragmentation is reduced by about 97%. Those data reflects that TPSSC can improve the possibility of network to accept more security requests. Meanwhile, the maximum security service latency of TPSSC is reduced by about 80%, which reflects that user experience improves significantly. From the above analysis, it is apparent that TPSSC is suitable for processing security requests in batch mode.Figure 9
Comparison of the time overhead of algorithm.In order to evaluate the performance of TPSSC further, we conduct experiments with different number of security requests in the FT-8 network and measure the time overhead and the acceptance ratio. In each experiment, security requests arrive in a Poisson process. The lengths of SSCs are approximately uniformly distributed between 1 and 10. Note that the length must be a positive integer. The throughput demands are uniformly distributed between 50 and 500. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 500 and 800. Each experiment is iterated 50 times and the arithmetic mean is reported. Figure10 shows the results.Figure 10
Performance of TPSSC under different number of security requests.With the increasing number of security requests, the time overhead of TPSSC increases and the increasing rate also broadens. Therefore, it is necessary to process several batches of security requests in parallel. In addition, the acceptance ratio decreases. But it is due to the fact that the lifetime of security request is not considered in the experiment. Thus, TPSSC should recycle the released resources before running so as to allow the network to accept more subsequent security requests.


## 6.1. Experimental Setup

Our experiments are conducted on the fat-tree and Waxman topologies. The number of different types of nodes in simulated networks is shown in Table1. The CPU and memory of service nodes are random numbers uniformly distributed between 200 and 500. The latency of each physical link is a number with uniform distribution between 1 and 10 time units. The bandwidth of each physical link is set to 5000. Note that the units for the bandwidth of physical link, the throughput demand of security request, and the throughput of instance are the same in the experiments. We omit them for the sake of simplicity. The above setting is the same for all experiments.Table 1
Simulated networks used in evaluation.
Network
FT-6-A
FT-6-B
FT-8
Waxman
Forwarding node
45
45
80
24
End node
38
27
90
403
Service node
16
27
38
173For the service node selection algorithm of TPSSC, we setT=200, Na=300, Nm=Nb=30, and mp0=0.7. For the service path establishment algorithm, we set NT=20, T=200, and R=50. We design a random algorithm and two greedy algorithms with single objective for comparison, which are denoted as RD, GD-1, and GD-2, respectively. RD randomly selects service nodes and establishes service paths. The goal of GD-1 is to reduce resource fragmentation. For a security request, GD-1 traverses its SSC sequentially and selects the “best" service node for running instance of each security function. The “best" service node has the minimum resource fragmentation after the instance is placed on it. With the objective to reduce security service latency, GD-2 defines the “best" service node as the one that the latency from the previous placed instance to it is the minimum. Note that instances can be placed on the same service node.In the evaluation, we first compare TPSSC against the above three algorithms with respect to length of SSC and throughput demand of security request. Experiments are conducted in the FT-6-B network. In each experiment, there are 300 service requests arriving in a Poisson process. Their sources and destinations are uniformly distributed in the simulated network. Their throughput demands are numbers uniformly distributed between 50 and 250. The length of SSC is fixed to one of{2,4,6,8,10}. As the above three algorithms do not consider the case where several instances of the same security function should be combined to serve a flow, we assume that every security function has only one instance. The CPU demand, memory demand, and throughput of an instance are 10, 10, and 300, respectively. We measure the acceptance ratio, the maximum resource fragmentation, the maximum security service latency, and the time overhead of algorithm. Each experiment is iterated 50 times and the arithmetic mean is reported. The results are shown with their 95% confidence intervals. For the convenience of comparative analysis, we take RD’s value as benchmark and the ratio of the value of other three algorithms to RD’s corresponding value is reported. We also conduct some experiments to analyze the performance of TPSSC specifically.


## 6.2. Results

### 6.2.1. Acceptance Ratio

Figure3 shows the acceptance ratio of GD-1, GD-2, and TPSSC versus RD. When the length of SSC is less than 4, the acceptance ratios are similar to each other. However, TPSSC, GD-1, and GD-2 have better results for longer SSC. Particularly, TPSSC becomes more and more superior as the length increases. The first reason is that TPSSC takes into account reusing instance for several flows in the designing phase. As a result, fewer resources of service nodes are needed. The second reason is that TPSSC optimizes the allocation of network resources based on the full analysis of all security requests over time. So the situation, where “small" security requests are refused because of network resources having been occupied by “big" security requests in advance, can be avoided to a certain extent.Figure 3
Comparison of acceptance ratio.In order to further evaluate the ability of TPSSC to accept security requests, we measure the acceptance ratio of TPSSC by changing some parameters of security request and network environment.(1) Acceptance Ratio under Different Throughput Demands.Experiments are conducted in the FT-6-A network. In each experiment, there are 400 security requests arriving in a Poisson process. The length of SSC is fixed and the throughput demand of each request is set to one of {50,100,150,200,250}. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 10 and 300. Each experiment is iterated 50 times and the arithmetic mean is reported. The results are shown in Figure 4. Security requests with higher throughput demand and longer SSC have the less opportunity to be accepted because of limited network resources. Moreover, the acceptance ratio drops to less than 20% when the length of SSC is 8 and the throughput demand is 250 due to serious lack of network resources.Figure 4
Acceptance ratio of TPSSC in the FT-6-A network.We also conduct the above experiment in the FT-6-B network. The results are shown in Figure5. The acceptance ratio in the FT-6-B network is higher than that in the FT-6-A network. This is because the former has more service nodes for running more instances. Moreover, it allows TPSSC to choose from a wider range of service nodes and routing paths.Figure 5
Acceptance ratio of TPSSC in the FT-6-B network.(2) Acceptance Ratio under Different Network Scales.Experiments are conducted in the FT-6-A, FT-8, and Waxman network, respectively. In each experiment, there are 1000 security requests arriving in a Poisson process. The length of SSC is fixed and the throughput demands are uniformly distributed between 50 and 250. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 10 and 500. Each experiment is iterated 50 times and the arithmetic mean is reported. Figure 6 shows the results.Figure 6
Acceptance ratio of TPSSC in different network scales.As shown in Figure6, the acceptance ratio in the Waxman network is higher than that in the other two networks. The reason is that there are more network resources in the Waxman network. This experiment also indicates that TPSSC has good scalability and large search space, which can perform well in the network with more nodes and links. In addition, when the length of SSC exceeds 6, the acceptance ratio in the FT-6-B network drops rapidly due to insufficient resources.


### 6.2.2. Resources Fragmentation

Figure7 shows the maximum resource fragmentation of GD-1, GD-2, and TPSSC versus RD. The results of TPSSC and GD-1 are significantly lower than those of RD and GD-2 since the first two try to minimize resource fragmentation when selecting service nodes. In contrast, RD does not optimize the selection of service nodes and GD-2 prefers to place multiple instances in the same service node. Moreover, the resource fragmentation of GD-2 is higher than that of RD as the length of SSC increases. The reason is that GD-2 can accept more security requests than RD, which further increases resource fragmentation. Meanwhile, the advantage of TPSSC is more and more obvious with the increasing length. This is mainly attributed to the service node selection algorithm based on bidirectional memory, which has high capability of global search and can find the near-optimal service node selection scheme to reduce resource fragmentation as far as possible.Figure 7
Comparison of the maximum resource fragmentation.


### 6.2.3. Security Service Latency

Figure8 shows the maximum security service latency (namely, the maximum end-to-end latency of flow) of GD-1, GD-2, and TPSSC versus RD. The results of GD-2 and TPSSC are better than those of RD and GD-1 since the first two aim at reducing security service latency. Conversely, GD-1 ignores latency when selecting service nodes, which may result in long security service latency since the selected service nodes may be far away from each other. It is worth noting that the maximum security service latency of TPSSC is slightly longer than that of GD-2 when the length of SSC is less than or equal to 6. It is due to the fact that TPSSC does not take into account the bandwidth of the shortest physical path between two service nodes when placing instances. In fact, it may not satisfy throughput demands of flows. So the placement of instances may still affect reducing security service latency. However, as the length of SSC increases further, GD-2 has to place more instances, which leads to higher possibility of placing instances far away from each other. As a result, the maximum security service latency of TPSSC is shorter than GD-2.Figure 8
Comparison of the maximum security service latency.


### 6.2.4. Time Overhead of Algorithm

Figure9 shows the time overhead of GD-1, GD-2, and TPSSC versus RD. As expected, the time overhead increases with the length of SSC. RD has the least time overhead since it does not consider any optimizations. When the length of SSC is 10, the time overhead of TPSSC is about 18 times higher than that of RD. But we can see from Figures 3, 7, and 8 that TPSSC can accept nearly 2 times security requests than RD and the maximum resource fragmentation is reduced by about 97%. Those data reflects that TPSSC can improve the possibility of network to accept more security requests. Meanwhile, the maximum security service latency of TPSSC is reduced by about 80%, which reflects that user experience improves significantly. From the above analysis, it is apparent that TPSSC is suitable for processing security requests in batch mode.Figure 9
Comparison of the time overhead of algorithm.In order to evaluate the performance of TPSSC further, we conduct experiments with different number of security requests in the FT-8 network and measure the time overhead and the acceptance ratio. In each experiment, security requests arrive in a Poisson process. The lengths of SSCs are approximately uniformly distributed between 1 and 10. Note that the length must be a positive integer. The throughput demands are uniformly distributed between 50 and 500. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 500 and 800. Each experiment is iterated 50 times and the arithmetic mean is reported. Figure10 shows the results.Figure 10
Performance of TPSSC under different number of security requests.With the increasing number of security requests, the time overhead of TPSSC increases and the increasing rate also broadens. Therefore, it is necessary to process several batches of security requests in parallel. In addition, the acceptance ratio decreases. But it is due to the fact that the lifetime of security request is not considered in the experiment. Thus, TPSSC should recycle the released resources before running so as to allow the network to accept more subsequent security requests.


## 6.2.1. Acceptance Ratio

Figure3 shows the acceptance ratio of GD-1, GD-2, and TPSSC versus RD. When the length of SSC is less than 4, the acceptance ratios are similar to each other. However, TPSSC, GD-1, and GD-2 have better results for longer SSC. Particularly, TPSSC becomes more and more superior as the length increases. The first reason is that TPSSC takes into account reusing instance for several flows in the designing phase. As a result, fewer resources of service nodes are needed. The second reason is that TPSSC optimizes the allocation of network resources based on the full analysis of all security requests over time. So the situation, where “small" security requests are refused because of network resources having been occupied by “big" security requests in advance, can be avoided to a certain extent.Figure 3
Comparison of acceptance ratio.In order to further evaluate the ability of TPSSC to accept security requests, we measure the acceptance ratio of TPSSC by changing some parameters of security request and network environment.(1) Acceptance Ratio under Different Throughput Demands.Experiments are conducted in the FT-6-A network. In each experiment, there are 400 security requests arriving in a Poisson process. The length of SSC is fixed and the throughput demand of each request is set to one of {50,100,150,200,250}. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 10 and 300. Each experiment is iterated 50 times and the arithmetic mean is reported. The results are shown in Figure 4. Security requests with higher throughput demand and longer SSC have the less opportunity to be accepted because of limited network resources. Moreover, the acceptance ratio drops to less than 20% when the length of SSC is 8 and the throughput demand is 250 due to serious lack of network resources.Figure 4
Acceptance ratio of TPSSC in the FT-6-A network.We also conduct the above experiment in the FT-6-B network. The results are shown in Figure5. The acceptance ratio in the FT-6-B network is higher than that in the FT-6-A network. This is because the former has more service nodes for running more instances. Moreover, it allows TPSSC to choose from a wider range of service nodes and routing paths.Figure 5
Acceptance ratio of TPSSC in the FT-6-B network.(2) Acceptance Ratio under Different Network Scales.Experiments are conducted in the FT-6-A, FT-8, and Waxman network, respectively. In each experiment, there are 1000 security requests arriving in a Poisson process. The length of SSC is fixed and the throughput demands are uniformly distributed between 50 and 250. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 10 and 500. Each experiment is iterated 50 times and the arithmetic mean is reported. Figure 6 shows the results.Figure 6
Acceptance ratio of TPSSC in different network scales.As shown in Figure6, the acceptance ratio in the Waxman network is higher than that in the other two networks. The reason is that there are more network resources in the Waxman network. This experiment also indicates that TPSSC has good scalability and large search space, which can perform well in the network with more nodes and links. In addition, when the length of SSC exceeds 6, the acceptance ratio in the FT-6-B network drops rapidly due to insufficient resources.


## 6.2.2. Resources Fragmentation

Figure7 shows the maximum resource fragmentation of GD-1, GD-2, and TPSSC versus RD. The results of TPSSC and GD-1 are significantly lower than those of RD and GD-2 since the first two try to minimize resource fragmentation when selecting service nodes. In contrast, RD does not optimize the selection of service nodes and GD-2 prefers to place multiple instances in the same service node. Moreover, the resource fragmentation of GD-2 is higher than that of RD as the length of SSC increases. The reason is that GD-2 can accept more security requests than RD, which further increases resource fragmentation. Meanwhile, the advantage of TPSSC is more and more obvious with the increasing length. This is mainly attributed to the service node selection algorithm based on bidirectional memory, which has high capability of global search and can find the near-optimal service node selection scheme to reduce resource fragmentation as far as possible.Figure 7
Comparison of the maximum resource fragmentation.


## 6.2.3. Security Service Latency

Figure8 shows the maximum security service latency (namely, the maximum end-to-end latency of flow) of GD-1, GD-2, and TPSSC versus RD. The results of GD-2 and TPSSC are better than those of RD and GD-1 since the first two aim at reducing security service latency. Conversely, GD-1 ignores latency when selecting service nodes, which may result in long security service latency since the selected service nodes may be far away from each other. It is worth noting that the maximum security service latency of TPSSC is slightly longer than that of GD-2 when the length of SSC is less than or equal to 6. It is due to the fact that TPSSC does not take into account the bandwidth of the shortest physical path between two service nodes when placing instances. In fact, it may not satisfy throughput demands of flows. So the placement of instances may still affect reducing security service latency. However, as the length of SSC increases further, GD-2 has to place more instances, which leads to higher possibility of placing instances far away from each other. As a result, the maximum security service latency of TPSSC is shorter than GD-2.Figure 8
Comparison of the maximum security service latency.


## 6.2.4. Time Overhead of Algorithm

Figure9 shows the time overhead of GD-1, GD-2, and TPSSC versus RD. As expected, the time overhead increases with the length of SSC. RD has the least time overhead since it does not consider any optimizations. When the length of SSC is 10, the time overhead of TPSSC is about 18 times higher than that of RD. But we can see from Figures 3, 7, and 8 that TPSSC can accept nearly 2 times security requests than RD and the maximum resource fragmentation is reduced by about 97%. Those data reflects that TPSSC can improve the possibility of network to accept more security requests. Meanwhile, the maximum security service latency of TPSSC is reduced by about 80%, which reflects that user experience improves significantly. From the above analysis, it is apparent that TPSSC is suitable for processing security requests in batch mode.Figure 9
Comparison of the time overhead of algorithm.In order to evaluate the performance of TPSSC further, we conduct experiments with different number of security requests in the FT-8 network and measure the time overhead and the acceptance ratio. In each experiment, security requests arrive in a Poisson process. The lengths of SSCs are approximately uniformly distributed between 1 and 10. Note that the length must be a positive integer. The throughput demands are uniformly distributed between 50 and 500. Every security function has 4 instances. The CPU and memory demands of an instance are numbers with uniform distribution between 5 and 30. The throughput of an instance is a number with uniform distribution between 500 and 800. Each experiment is iterated 50 times and the arithmetic mean is reported. Figure10 shows the results.Figure 10
Performance of TPSSC under different number of security requests.With the increasing number of security requests, the time overhead of TPSSC increases and the increasing rate also broadens. Therefore, it is necessary to process several batches of security requests in parallel. In addition, the acceptance ratio decreases. But it is due to the fact that the lifetime of security request is not considered in the experiment. Thus, TPSSC should recycle the released resources before running so as to allow the network to accept more subsequent security requests.


## 7. Conclusions and Future Work

The method of deploying SSC promises to address cost reduction and flexibility in security service delivery. Yet, SSC-DP remains a challenging problem to be tackled. In this paper, we present a novel approach to integrate SSC into delivering security service and propose a three-phase method TPSSC to find near-optimal solutions of SSC-DP. In the case that instances differ in service capacity and resource demand, TPSSC not only determines the combination of instances, placement of instances, and routing of flows, but also seeks to minimize resource consumption of service nodes, resource fragmentation, and security service latency. It facilitates delivering customized security service as well as optimizing utilization of network and security resources. Our evaluations show that although the time overhead of TPSSC is higher than RD, TPSSC has better performance in acceptance ratio, the maximum resource fragmentation, and the maximum security service latency. Moreover, compared with the two greedy algorithms, TPSSC becomes more and more superior as the length of SSC increases. As perspectives for future work, we intend to extend the evaluation of the proposed method by applying it to real network. Moreover, we plan to introduce failure-resilience mechanism into SSC maintenance for guaranteeing the continuity of security service.



---

*Source: 9534754-2017-12-12.xml*