Printer Friendly

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

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., x86 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 the SSC Deployment Problem (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 SSCDP, 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 Section 2. 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 SSCDP 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 maybe 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, 2527], 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 non-cooperative 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 Figure 1, 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.

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.

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 [G.sub.s] = (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 [], which only forwards packets to other nodes, such as switches; service node [], which provides virtualized platform for running instances; end node [n.sub.end], which is the source or destination of flow. Additionally, let R be the set of available resources on the service node. For each r [member of] R, c(r) denotes the amount of r. Bandwidth and latency of physical link e [member of] E are denoted as b[w.sub.e] and la[t.sub.e], 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 = {[f.sub.1], [f.sub.2], ..., [f.sub.n]} represents the SSC, where fi denotes a security function, 1 [less than or equal to] i [less than or equal to] n. If 1 [less than or equal to] j = (i + 1) < n, [f.sub.i] is the immediate predecessor of [f.sub.j], denoted as pre([f.sub.j]) = {[f.sub.i]}. Similarly, fj is the immediate successor of [f.sub.i], denoted as succ([f.sub.i]) = {[f.sub.j]}. 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([f.sub.i]) = {[it.sub.i1], [it.sub.i2], []} be the instance set of [f.sub.i], where an instance [it.sub.ij] is identified by 5-tuple, [it.sub.ij] := (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 [member of] R, [rd.sup.r.sub.ij] [member of] ins_n. cap represents service capacity, which is defined as the throughput of instance in this paper, denoted as [c.sub.ij]. pd is processing delay.

4.2. Problem Statement. Given a physical network [G.sub.s] = (N,E) and a set of security requests RQ, instantiate each security function required by rq [member of] RQ on certain service nodes in [G.sub.s] 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 function [f.sub.i] [member of] rq can be instantiated on several service nodes in the form of different instance types of [f.sub.i]. Each selected service node has sufficient resources to accommodate the demand of an instance of [f.sub.i]. 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 Section 3, 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

[mathematical expression not reproducible], (1)

[mathematical expression not reproducible]. (2)

Let [x.sup.m.sub.ij]. be the number of instances [it.sub.ij] assigned to the SSC of request [rq.sub.m]. As shown in (1), I is the total resource consumption of service nodes, where [[tau].sub.r] is weighting factor used to adjust the relative importance of resources, [[summation].sub.r[member of]R] [[tau].sub.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 [f.sub.i] in F has an instance set, in which elements are sorted by their throughput (i.e., [c.sub.ij]) in descending order. Here, we use a temporary variable [] to keep track of the candidate value of [x.sup.m.sub.ij] and use pm 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.


Input: Security request set RQ, security function set F, maximum
  number of iterations R
Output: Instance combinations of SSCs
Initialize r = 0; [t.sup.m.sub.ij] = 0; [p.sup.m.sub.i] = 1
while (r < R)
 for all r[q.sub.m] [member of] RQ and [f.sub.i] [member of]
 r[q.sub.m] ch do
 [mathematical expression not reproducible]
 Find the minimum [mathematical expression not reproducible]
  satisfying [mathematical expression not reproducible]
end for
Compute ([alpha]l + [beta]D)
if r = 1 or ([alpha]l + [beta]D) < [delta] then
 [delta] = ([alpha]I + [beta]D)
 Assign all [t.sup.m.sub.ij] to [x.sup.m.sub.ij]
end if
update(all [t.sup.m.sub.ij])
r = r + 1
end while
return {x.sup.m.sub.ij | r[q.sub.m] [member of] RQ, [f.sub.i] [member
 of] r[q.sub.m] x ch, [it.sub.ij] [member of] ins([f.sub.i])}
Function update(all [t.sup.m.sub.ij])
for all r[q.sub.m] [member of] RQ and [f.sub.i] [member of] r[q.sub.m]
 x ch do
 if [p.sup.m.sub.i] [greater than or equal to] |ins([f.sub.i])l then
 Backtrack set [T.sup.m.sub.i] from [p.sup.m.sub.i] - 1th element
 find the first element satisfying [t.sub.j] > 0
 [p.sup.m.sub.i] = j
 end if
 [mathematical expression not reproducible]
 [p.sup.m.sub.i] = [p.sup.m.sub.i] + 1
 end for

Let [[x.sup.m.sub.ij] [it.sub.ij] [member of] ins([f.sub.i])} represent the instance set of [f.sub.i] which is assigned to r[q.sub.m]. For each [it.sub.ij], [th.sup.m.sub.ij] denotes the throughput demand of r[q.sub.m] for it. It satisfies [mathematical expression not reproducible] the larger [c.sub.ij] is, the smaller ([c.sub.ij] - [th.sup.m.sub.ij]) is.

Since Algorithm 1 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 [G.sub.v] = (V, L), is built. The meanings of symbols are as follows.

v [member of] V is a virtual node. If it represents an instance [it.sub.ij], its weight w(v) is defined as the set of throughput demands of requests for this instance. Specifically, if [mathematical expression not reproducible]. Otherwise, there are a set of nodes {v'} representing [it.sub.ij], and for each v', [mathematical expression not reproducible]. 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) = [r[q.sub.m].run | r[q.sub.m].src = s}. The definition of w(v) is similar if v represents the destination.

l [member of] 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 [f.sub.i] and [f.sub.j] belong to SSCs of r[q.sub.m] and r[q.sub.n], respectively, and they satisfy pre([f.sub.j]) = [f.sub.i]. If the instance [it.sub.ip] ([]) of [f.sub.i] ([f.sub.j]) is represented by the virtual node [v.sub.p] ([v.sub.q]), there is a virtual link from [v.sub.p] to [v.sub.q], denoted as l([v.sub.p], [v.sub.f]). Its weight is defined as the set of throughput demands of r[q.sub.m] and r[q.sub.n]; that is, [mathematical expression not reproducible]. If an end node of l represents source or destination, relevant definitions are similar. Additionally, we use id(l) = [r[q.sub.m], r[q.sub.n], ...} 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

[mathematical expression not reproducible], (3)

[mathematical expression not reproducible], (4)

[mathematical expression not reproducible], (5)

[mathematical expression not reproducible], (6)

[mathematical expression not reproducible], (7)

[mathematical expression not reproducible], (8)

[mathematical expression not reproducible], (9)

[for all][v.sub.s] [member of] [V.sub.end], [for all][n.sub.i] [member of] [N.sub.end] - {a} : [] = 1, [] = 0, (10)

[for all][v.sub.d] [member of] [V.sub.end], [for all][n.sub.i] [member of] [N.sub.end] - {a'} : [x.sub.a'd] = 1, [] = 0, (11)

[for all][n.sub.i] [member of] [], [for all][vsub.f] [member of] [V.sub.ins] : [x.sub.if] [member of] {0,1}. (12)

As resource fragmentation limits network to accept security requests, we take minimizing the maximum resource fragmentation of service nodes ((3)) as an objective. fra; ((6)) measures the resource fragmentation of n; 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 [f.sub.1](X) and [f.sub.2](X), where [mathematical expression not reproducible].

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.

(1) Main Data Structure Description. There are three main data structures used in the proposed algorithm.

Antibody Population. The algorithm maintains an antibody population [mathematical expression not reproducible] at the itth generation, where Na is the size of the population. Antibody [a.sub.i](it) is the encoding of candidate solution X for the Problem P; that is, [mathematical expression not reproducible], where n is the length of the antibody and [a.sup.f.sub.i] (it) - k means placing the instance represented by [v.sub.f] on the service node [n.sub.k]; namely, [x.sub.kf] - 1. In particular, if [v.sub.f] represents the source or destination of flow, at (it) is a known quantity and will not be changed by the following operations.

ALGORITHM 2: Service node selection algorithm based on bidirectional

Input: Maximum number of iterations T, maximum size of antibody
    population [N.sub.a], maximum size of memory unit [N.sub.m],
    size of standby unit [N.sub.b], initial mutation probability
Output: Memory unit M(it)
Initialize it = 0; initializing antibody population A(it), memory unit
    M(it) and standby unit B(it).
Step 1. Generate C(it) from A(it) by the clone operation [O.sub.c]:
    [mathematical expression not reproducible], where [N.sub.c] =
    [[summation].sup.N.sub.i=1][p.sub.i] (it).
Step 2. Update C(it) by the mutation operation [O.sub.m]:
    [mathematical expression not reproducible].
Step 3. Generate preponderant antibody population P(it) and neighboring
    antibody population
    Q(it) from D(it) by selection operation Os.
Step 4. If the size of P(it) is larger than [N.sub.a], sort antibodies
    by their crowding distances [35] in descending order and select
    the top [N.sub.a] antibodies to form new antibody population
    P'(it), otherwise P'(it) = P(it):
    [mathematical expression not reproducible].
Step 5. Produce new memory unit M'(it) by applying study operation
    [O.sub.l] on M(it) and P'(it):
    M'(it) = [O.sub.l](M(it),P'(it)) = {[m'.sub.1](it),[m'.sub.2]
    (it), ..., [m'.sub.R(it+1)](it)},where R(it + 1) [less than or
    equal to] [N.sub.m].
Step 6. Update Q(it) by the self-repairing operation [O.sub.r]:
    [mathematical expression not reproducible].
Step 7. Produce new standby unit B'(it) by applying replacement
    operation [O.sub.a] on B(it) and Q'(it):
    [mathematical expression not reproducible].
Step 8. If it [greater than or equal to] T, output M'(it) and end,
    otherwise A(it + 1) = P'(it), M(it + 1) = M'(it),
    B(it + 1) = B'(it), it = it + 1, go to Step 1.

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 [a.sub.i](it).

We introduce a new function [mathematical expression not reproducible], where [n.sub.i] [member of] [] and r [member of] R. Assume that [mathematical expression not reproducible], namely, X = [e.sup.-1] ([a.sub.i](it)) satisfies all constraints of the Problem P, [a.sup.i](it) is called feasible antibody. Otherwise, [a.sub.i](it) is called infeasible antibody. Furthermore, [f.sub.3]([e.sup.-1] ([a.sub.i](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 [a.sub.i](it) is.

If two feasible antibodies, [a.sub.i](it) and [a.sub.j](it), satisfy the condition that [mathematical expression not reproducible] is said to Pareto dominate [a.sub.j](it), denoted as [a.sub.i](it) > [a.sub.j](it). Furthermore, [a.sub.i](it) is called Pareto-optimal if there does not exist another feasible antibody a* (it) in A(it) that satisfies a* (it) > [a.sub.i](it).

Memory Unit. Memory unit M(it) = {[m.sub.1](it),[m.sub.2](it),..., [mR.sub.(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 [N.sub.m].

Standby Unit. Standby unit [mathematical expression not reproducible], whose size is [N.sub.b], 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 [v.sub.f] for the service node [n.sub.i] is defined as [mathematical expression not reproducible] is the occupancy ratio of resource r in [n.sub.i] occupied by [v.sub.f] and a is a small positive constant to avoid dividing by zero in computing the preference. Then the preference list of [v.sub.f], denoted as PL([v.sub.f]), is built by sorting service nodes by [mathematical expression not reproducible] 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 Algorithm 3. Here, function Selectfirst(PL([v.sub.f])) means traversing PL([v.sub.f]) in sequence until finding [n.sub.i] which is the first service node satisfying two conditions simultaneously: (i) [for all]r [member of] R, [res.sup.r.sub.f] [less than or equal to] [c.sub.i](r); (ii) [for all][v.sub.j] [member of] pre([v.sub.f]), [a.sub.j] = g, hop([n.sub.g], [n.sub.i]) [less than or equal to] [theta]. If all nodes in PL([v.sub.f]) 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([v.sub.f]).

ALGORITHM 3: Antibody population initialization algorithm based on

Input: [G.sub.v], preference lists of all instances, the upper limit
    of hops between two nodes [theta]
Output: Initial antibody population
for m = 1 to [N.sub.a] do
 Trs = 0
while (Trs [not equal to] [V.sub.ins])
 for all [v.sub.f] [member of] [V.sub.ins] do
  if [mathematical expression not reproducible] is the in-degree of
   [n.sub.i] = Selectfirst (PL([v.sub.f]))
   [a.sup.f.sub.m] = i
   for all r [member of] R do
    [c.sub.i](r) = [c.sub.i](r) - [res.sup.r.sub.f]
   end for
   [mathematical expression not reproducible]
   Trs = Trs [universal]{[v.sub.f]}
   for all [v.sub.k] [member of] succ([v.sub.f]) do
    [mathematical expression not reproducible]
   end for
  end if
 end for
end while
m = m + 1
end for
return [mathematical expression not reproducible]

Clone Operation. [O.sub.c] is defined as [mathematical expression not reproducible], and [p.sub.i](it) is the clone scale of [a.sub.i](it)

[P.sub.i](it) = Int (H x [[eta].sub.i](it)/[[summation].sup.N(it).sub.j=1][[eta].sub.j](it) x 1/[[psi].sub.i](it). (13)

[p.sub.i](it) is given by (13) and can self-adaptively be adjusted by the antibody-antibody affinity [[psi].sub.i](it) and the antibody-antigen affinity [[eta].sub.i](it). Their detailed definitions are as follows:

(i) Antibody-antibody affinity [[psi].sub.i](it): it is measured by the Euclidean distance between [a.sub.i](it) and other antibodies: [[psi].sub .i](it) = min{exp(-[paragraph][a.sub.i](it) - [a.sub.j](it)[paragraph])}, where i [not equal to] j, [less than or equal to] j [less than or equal to] [N.sub.a]; [paragraph].[paragraph] represents Euclidean distance, and it is normalized to [0,1].

(ii) Antibody-antigen affinity [[eta].sub.i](it).

[mathematical expression not reproducible], (14)

[mathematical expression not reproducible], (15)

[[eta].sub.i](it) = [3.summation over (j=1)][[eta].sup.j.sub.i](it). (16)

To unify the affinity computation of feasible and infeasible antibodies, we regard min [f.sub.3](X) as an objective of the Problem P. So given a single antigen (i.e., an objective function) [f.sub.j](X), we can obtain relative affinity between the antibody [a.sub.i](it) and the antigen [f.sub.j](X), denoted as [[eta].sup.j.sub.i](it) ((15)), through comparing the objective value of [a.sub.i](it) (i.e., [f.sub.j]([e.sup.-1]([a.sub.i](it)))) with objective values of other antibodies ((14)). For the Problem P with multiple objectives, [[eta].sub.i](it) is defined as the sum of relative affinities between [a.sub.i](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, [[psi].sub.i](it) increases) and the decrease of antigen stimulation (namely, [[eta].sub.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 = m[p.sub.0] x (1 - it/T), where m[p.sub.0] 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 [N.sub.q] 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 [mathematical expression not reproducible] 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 [q.sub.i](it), the resource burden of service node is defined as [mathematical expression not reproducible]. If there exists a node without burden, that is, [bur.sub.j] = 0, self-repairing operation will be applied to [q.sub.i](it). Specifically, starting from [n.sub.j] with the heaviest burden, it selects an instance [v.sub.k] randomly and migrates it to the node [n.sub.j'] with [bur.sub.j'] = 0, that is, replacing [q.sub.ik] = j with [q.sub.ik] = f. If the degree of constraint violation of the new antibody [q'.sub.i](it) is smaller than that of [q.sub.i](it), this migration is accepted. Otherwise, it selects another instance and repeats the previous migration until all instances on [n.sub.j] 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

[mathematical expression not reproducible], (17)

[mathematical expression not reproducible], (18)

[mathematical expression not reproducible], (19)

[mathematical expression not reproducible], (20)

[mathematical expression not reproducible], (21)

[mathematical expression not reproducible]. (22)

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 [z.sup.(m,n).sub.(m',n')] ['], and ['] 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 [S.sub.0] = {[s.sub.1], [s.sub.2], ..., [s.sub.n]}, where [mathematical expression not reproducible]. 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 {[s.sub.1], [s.sub.2], ..., [s.sub.n]}, solutions are sorted by their objective function values (i.e., [mathematical expression not reproducible], denoted as h([s.sub.i])) in ascending order. So the first m solutions are chosen to form the dominant solution set. It is denoted as DS = {[s.sub.1], [s.sub.2], ..., [s.sub.m]}, where h([s.sub.1]) [less than or equal to] ... [less than or equal to] h([s.sub.m]). 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,{[y.sub.ab] | 1 [less than or equal to] a [less than or equal to] [absolute value of E], b = l}) | 1 [less than or equal to] l [less than or equal to] [absolute value of 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 st, its neighborhood N([s.sub.i]) = NeborCons(s,ns) = {[s.sup.1.sub.i],[s.sup.2.sub.i],...,[s.sup.ns.sub.i]} 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 [s.sup.1.sub.i] 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([s.sub.i]) is defined as ns = [ns.sub.min] + nt x ([ns.sub.max] - [ns.sub.min])/NT, where [ns.sub.max] = L and [ns.sub.min] = 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 as Evaluate(). 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 Algorithm 4. Here, we use the functions Update(DS,[S.sub.0]) and Update(DS,N(s)) to replace some solutions in DS with better ones in [S.sub.0] 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)).

The 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 first m 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. [N.sub.a], [N.sub.m], and [N.sub.b] 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 [] and [N.sub.ins], respectively, the worst time complexity of initializing operation is O([N.sub.a] x [N.sub.ins] x []). Then, the time complexity of building memory unit and standby unit is O([N.sub.a.sup.2]) and O([N.sub.a] + [N.sub.a] log [N.sub.b]), respectively. Thirdly, if H is a given value relating to clone scale, the worst time complexity of clone operation is O([N.sub.a]H). Fourthly, if the size of antibody population after cloning is [N.sub.c], the time complexity of mutation operation is O([N.sub.c]). Fifthly, selection operation includes computing the degree of constraint violation of antibodies, selecting Pareto-optimal antibodies, and choosing [N.sub.q] antibodies with the lowest degree of constraint violation. Their time complexities are O([N.sub.c]), O([N.sup.2.sub.c]), and O([N.sub.c] log[N.sub.q]), respectively. Then, if the size of preponderant antibody population after selection operation is K and there are [N.sub.a] Pareto-optimal antibodies that should be reserved, the time complexity of updating preponderant antibody population is O([N.sub.a][K.sup.2]). Next, the time complexity of self-repairing operation is O(m x [] log []) if its depth is m. Then the worst time complexity of replacement operation is O([N.sub.b] x [N.sub.q]). Finally, the time complexity of study operation is O([([N.sub.a] - [N.sub.m]).sup.2]). Therefore, the worst time complexity of the proposed algorithm during the first iteration is O([N.sub.a] x [N.sub.ins] x [] + [N.sup.2.sub.c] + [N.sub.a] x [K.sup.2] + [N.sub.a.sup.2] + [N.sup.2.sub.m]).

ALGORITHM 4: Service path establishment algorithm based on
hybrid taboo search.

Input: NT, T, R
Output: The best solution s'
Initialize: DS = 0; TL = 0; t = 0; impro = 0
Generate initial solution set [S.sub.0]
Update (DS, [S.sub.0])
while (t < T and noimpro < R)
  Randomly select s from DS
  r = h(DS[1])
  nt = 0
  [] = s
  while (nt < NT)
    N(s) = NeborCons(s,ns)
    Evaluate (N(s))
    isupdated = Update (DS,N(s))
    if isupdated then nt = 0
    else nt + +
    end if
    CS = Roulettejwheel(N(s))
    if isaspiration then
      s = SelectBest (CS)
      [] = s
      Update the tabu list TL
      s = SelectBest .notabu (CS)
      Update the tabu list TL
    end if
  end while
  t ++
  if h(DS[1]) < r then noimpro = 0
  else noimpro + +
  end if
end while
return DS [1]

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 are L 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(n log m). 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 x [ns.sub.min] - 0.5 x (NT - 1) x ([ns.sub.max] [ns.sub.min]). So the time complexity of this process can be regarded as O(NT x [ns.sub.max]). In conclusion, the time complexity of an iteration of the proposed algorithm is O(nkL - NT x [ns.sub.max]).

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 Table 1. 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.

For the service node selection algorithm ofTPSSC, we set T = 200, [N.sub.a] = 300, [N.sub.m] = [N.sub.b] = 30, and m[p.sub.0] = 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. Figure 3 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.

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.

We also conduct the above experiment in the FT-6-B network. The results are shown in Figure 5. 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.

(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.

As shown in Figure 6, 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. Figure 7 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.

6.2.3. Security Service Latency. Figure 8 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 maybe 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.

6.2.4. Time Overhead of Algorithm. Figure 9 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.

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. Figure 10 shows the results.

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, SSCDP 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.


[]:                Set of service nodes in physical network
[N.sub.end]:               Set of end nodes in physical network
E:                         Set of physical links
RQ:                        Set of security requests
[V.sub.ins]:               Set of virtual nodes representing instances
[V.sub.end]:               Set of virtual nodes representing sources
                           and destinations of flows
L:                         Set of virtual links
[rd.sup.r.sub.ij]:         Demand of the instance [it.sub.ij] for
                           resource r
[C.sub.ij]:                Throughput of the instance [it.sub.ij]
[th.sup.m.sub.ij]:         Throughput demand of the security
                           request [r.sub.qm] for the instance
[PHI]:                     Set of virtual node pairs representing
                           source-destination pairs of all security
                           requests [PHI] = |([v.sub.s], [v.sub.d]),
                           ... ([v.sub.s'], [v.sub.d'],)}
[pi](s, d):                Set of virtual paths between [v.sub.s] and
                           [v.sub.d] which represent the source and
                           destination of flow, respectively; that is,
                           [pi](s, d) = {[[pi].sub.1], [[pi].sub.2],
                           ..., [[pi].sub.k]}, in which [[pi].sub.i] =
                           {l([v.sub.s], [v.sub.1]), l([v.sub.1],
                           [v.sub.2]), ..., l([v.sub.j], [v.sub.d])}
                           (1 [less than or equal to] i [less than or
                           equal to] k) and [mathematical expression
                           not reproducible]
[phi]([[pi].sub.i):        Set of virtual nodes along the virtual path
PT(m', n'):                Set of k-shortest paths between physical
                           node m and n
[x.sub.if]:                If the instance represented by [v.sub.f] is
                           placed on service node [n.sub.i], [x.sub.if]
                           = 1, or else [x.sub.i]f = 0[
[y.sup.(u,v).sub.(m,n)]:   Bandwidth assigned to virtual linkl(u, v)
                           by physical link e(m, n)
[z.sup.(m,n).sub.(m',n')]: If physical link e(m,n) is a part of
                           physical path p(m', n) and p(m', n) [member
                           of] PT(m', n), [z.sup.(m,n).sub.(m',n')] =
                           1, or else [z.sup.(m,n).sub.(m',n')] = 0
[res.sup.f.sub.r]:         Demand of the instance represented by
                           [v.sub.f] for resource r
[pd.sub.f]:                Processing delay of the instance
                           represented by [v.sub.f]
[C.sub.i](r):              The amount of resource r on service node
[utl.sup.r.sub.i]:         Utilization of resource r on service node
[fra.sub.i]:               Resource fragmentation of service node
[bw.sub.(m,n)]:            Bandwidth of physical link e(m, n)
[lat.sub.(m,n)]:           Latency of physical link e(m,n)
[hop.sub.(m,n)]:           The number of hops of the shortest path
                           between physical nodes m and n
[db.sub.(u,v)]:            Bandwidth demand of virtual link l(u, v).

Conflicts of Interest

The authors declare that they have no conflicts of interest.


This research was supported by National High-Tech Research and Development Project (863) of China (2012AA012704) and Zhengzhou Science and Technology Talents (131PLJRC644).


[1] P. Quinn and T. Nadeau, "Problem Statement for Service Function Chaining," RFC Editor RFC7498, 2015.

[2] N. McKeown, T. Anderson, H. Balakrishnan et al., "OpenFlow: enabling innovation in campus networks," Computer Communication Review, vol. 38, no. 2, pp. 69-74, 2008.

[3] M. Chiosi, D. Clarke, P Willis, and A. Reid, Network functions virtualisation-introductory, White paper, ETSI, 2012.

[4] O. N. Foundation, Software-defined networking: The new norm for networks, White paper, ONF, 2012.

[5] S. Clayman, E. Maini, A. Galis, A. Manzalini, and N. Mazzocca, "The dynamic placement of virtual network functions," in Proceedings of the IEEE Network Operations and Management Symposium (NOMS '14), pp. 1-9, Krakow, Poland, May 2014.

[6] J. Hwang, K. K. Ramakrishnan, and T. Wood, "NetVM: high performance and flexible networking using virtualization on commodity platforms," IEEE Transactions on Network and Service Management, vol. 12, no. 1, pp. 34-47, 2015.

[7] J. Martins, M. Ahmed, C. Raiciu, and F. Huici, "Enabling fast, dynamic network processing with ClickOS," in Proceedings of the 2013 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN 2013, pp. 67-72, China, August 2013.

[8] W. Zhang, G. Liu, W. Zhang et al., "OpenNetVM," in Proceedings of the the 2016 workshop, pp. 26-31, Florianopolis, Brazil, August 2016.

[9] J. Wilson, "Delivering security virtually everywhere with sdn and nfv," Technical Report, 2015.

[10] W. Lee, Y. Choi, and N. Kim, "Study on Virtual Service Chain for Secure Software-Defined Networking," in Proceedings of the The 6th International Conference on Control and Automation, pp. 177-180.

[11] J. Blendin, J. Ruckert, N. Leymann, G. Schyguda, and D. Hausheer, "Position paper: Software-defined network service chaining," in Proceedings of the 3rd European Workshop on Software-Defined Networks, EWSDN 2014, pp. 109-114, Hungary, September 2014.

[12] M. F. Bari, S. R. Chowdhury, R. Ahmed, and R. Boutaba, "On orchestrating virtual network functions," in Proceedings of the 11th International Conference on Network and Service Management, CNSM 2015, pp. 50-56, Spain, November 2015.

[13] D. Bhamare, R. Jain, M. Samaka, and A. Erbad, "A survey on service function chaining," Journal of Network and Computer Applications, vol. 75, pp. 138-155, 2016.

[14] D. Bhamare, R. Jain, M. Samaka, G. Vaszkun, and A. Erbad, "Multi-cloud distribution of virtual functions and dynamic service deployment: OpenADN perspective," in Proceedings of the 2015 IEEE International Conference on Cloud Engineering, IC2E 2015, pp. 299-304, USA, March 2015.

[15] G. Katsikas, Realizing high performance nfv service chains [Master, thesis], KTH School of Information and Communication Technology, 2017,

[16] X.-L. Li, H.-M. Wang, B. Ding, C.-G. Guo, and X.-Y. Li, "Research and development of virtual network mapping problem," Ruan Jian Xue Bao/Journal of Software, vol. 23, no. 11, pp. 3009-3028, 2012.

[17] A. Dwaraki and T. Wolf, "Adaptive Service-Chain Routing for Virtual Network Functions in Software-Defined Networks," in Proceedings of the the 2016 workshop, pp. 32-37, Florianopolis, Brazil, August 2016.

[18] Z. Cao, M. Kodialam, and T. V. Lakshman, "Traffic steering in software defined networks: Planning and online routing," in Proceedings of the ACM SIGCOMM 2014 Workshop on Distributed Cloud Computing, DCC 2014, pp. 65-70, USA, August 2014.

[19] G. Xiong, Y. Hu, J. Lan, and G. Cheng, "A mechanism for configurable network service chaining and its implementation," KSII Transactions on Internet and Information Systems, vol. 10, no. 8, pp. 3701-3727, 2016.

[20] M. Ghaznavi, A. Khan, N. Shahriar, K. Alsubhi, R. Ahmed, and R. Boutaba, "Elastic virtual network function placement," in Proceedings of the 4th IEEE International Conference on Cloud Networking, CloudNet2015, pp. 255-260, Canada, October 2015.

[21] S. Mehraghdam, M. Keller, and H. Karl, "Specifying and placing chains of virtual network functions," in Proceedings of the 2014 3rd IEEE International Conference on Cloud Networking, CloudNet 2014, pp. 7-13, Luxembourg, October 2014.

[22] A. Mohammadkhan, S. Ghapani, G. Liu, W. Zhang, K. K. Ramakrishnan, and T. Wood, "Virtual function placement and traffic steering in flexible and dynamic software defined networks," in Proceedings of the 21st IEEE International Workshop on Local and Metropolitan Area Networks, Lanman 2015, China, April 2015.

[23] B. Addis, D. Belabed, M. Bouet, and S. Secci, "Virtual network functions placement and routing optimization," in Proceedings of the 4th IEEE International Conference on Cloud Networking, CloudNet '15, pp. 171-177, October 2015.

[24] M. Ghaznavi, N. Shahriar, R. Ahmed, and R. Boutaba, Service function chaining simplified, CoRR abs/1601.00751, 2016.

[25] M. C. Luizelli, L. R. Bays, L. S. Buriol, M. P Barcellos, and L. P. Gaspary, "Piecing together the NFV provisioning puzzle: efficient placement and chaining of virtual network functions," in Proceedings of the 14th International Symposium on Integrated Network Management, IM '15, pp. 98-106, IEEE, Toronto, Canada, May 2015.

[26] A. Gupta, M. F. Habib, U. Mandal, P Chowdhury, M. Tornatore, and B. Mukherjee, On service-chaining strategies using virtual network functions in operator networks, CoRR abs/1611.03453, 2016.

[27] Z. Allybokus, N. Perrot, J. Leguay, L. Maggi, and E. Gourdin, "Virtual function placement for service chaining with partial orders and anti-affinity rules," Networks, 2017

[28] S. D'Oro, L. Galluccio, S. Palazzo, and G. Schembra, "Exploiting congestion games to achieve distributed service chaining in NFV networks," IEEE Journal on Selected Areas in Communications, vol. 35, no. 2, pp. 407-420, 2017

[29] S. Sahhaf, W. Tavernier, D. Colle, and M. Pickavet, "Network service chaining with efficient network function mapping based on service decompositions," in Proceedings of the 1st IEEE Conference on Network Softwarization, NETSOFT 2015, UK, April 2015.

[30] T. Lukovszki and S. Schmid, "Online admission control and embedding of service chains," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 9439, pp. 104-118, 2015.

[31] ETSI, Network functions virtualisation (nfv), architectural framework, ETSI GS NFV 002 V1.2.1, ETSI, 2014.

[32] J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in Proceedings of the 1st ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures (VISA '09), pp. 81-88, ACM, New York, NY, USA, 2009.

[33] R.-C. Liu, L.-C. Jiao, and H.-F. Du, "Clonal strategy algorithm based on the immune memory," Journal of Computer Science and Technology, vol. 20, no. 5, pp. 728-734, 2005.

[34] R. Shang and W. Ma, "Immune Clonal MO Algorithm for ZDT Problems," in Advances in Natural Computation, vol. 4222 of Lecture Notes in Computer Science, pp. 100-109, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.

[35] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.

[36] C. Lagos, B. Crawford, E. Cabrera, R. Soto, J.-M. Rubio, and F. Paredes, "Combining Tabu search and genetic algorithms to solve the capacitated multicommodity network flow problem," Studies in Informatics and Control, vol. 23, no. 3, pp. 265-276, 2014.

Yi Liu, Hong-qi Zhang, Jiang Liu, and Ying-jie Yang

Information Science Technology Institute, Zhengzhou, Henan 450000, China

Correspondence should be addressed to Yi Liu;

Received 28 July 2017; Revised 22 October 2017; Accepted 8 November 2017; Published 12 December 2017

Academic Editor: Guangjie Han

Caption: Figure 1: Architecture and component interactions.

Caption: Figure 2: Integrated architecture.

Caption: Figure 3: Comparison of acceptance ratio.

Caption: Figure 4: Acceptance ratio of TPSSC in the FT-6-A network.

Caption: Figure 5: Acceptance ratio of TPSSC in the FT-6-B network.

Caption: Figure 6: Acceptance ratio of TPSSC in different network scales.

Caption: Figure 7: Comparison of the maximum resource fragmentation.

Caption: Figure 8: Comparison of the maximum security service latency.

Caption: Figure 9: Comparison of the time overhead of algorithm.

Caption: Figure 10: Performance of TPSSC under different number of security requests.

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     173
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Liu, Yi; Zhang, Hong-qi; Liu, Jiang; Yang, Ying-jie
Publication:Security and Communication Networks
Article Type:Report
Date:Jan 1, 2017
Previous Article:Practical m-k-Anonymization for Collaborative Data Publishing without Trusted Third Party.
Next Article:F-DDIA: A Framework for Detecting Data Injection Attacks in Nonlinear Cyber-Physical Systems.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters