Service Chain Placement in SDNs

Gilad Kutiel1,2(B) and Dror Rawitz1,2

1
Department of Computer Science, Technion, 32000 Haifa, Israel
gkutiel@[Link]
2
Faculty of Engineering, Bar Ilan University, 52900 Ramat-Gan, Israel
[Link]@[Link]

Abstract. We study the allocation problem of a compound request for

a service chain in a software defined network that supports network func-
tion virtualization. Given a network that contains servers with limited
processing power and of links with limited bandwidth, a service chain
is a sequence of virtual network functions (VNFs) that service a certain
flow request in the network. The allocation of a service chain consists
of routing and VNF placement, namely each VNF from the sequence is
placed in a server along a path. It is feasible if each server can handle
the VNFs that are assigned to it, and if each link on the path can carry
the flow that is assigned to it. A request for service is composed of a
source and a destination in the network, an upper bound on the total
latency, and a specification in the form of a directed acyclic graph (DAG)
of VNFs that provides all service chains that are considered valid for this
request. In addition, each pair of server and VNF is associated with a
cost for placing the VNF in the server. Given a request, the goal is to
find a valid service chain of minimum total cost that respects the latency
constraint or to identify that such a service chain does not exist.
We show that even the feasibility problem is NP-hard in general
graphs. Hence we focus on DAGs. We show that the problem is still
NP-hard in DAGs even for a very simple network, and even if the VNF
specification consists of only one option (i.e., the virtual DAG is a path).
On the other hand, we present an FPTAS for the case where the network
is a DAG. In addition, based on our FPTAS, we provide algorithms for
instances in which the service chain passes through a bounded number
of vertices whose degree is larger than two.

1 Introduction
Computer communication networks are in constant need of expansion to cope
with the ever growing traffic. As networks grow, management and maintenance
become more and more complicated. Current developments that aim to improve
the utilization of network resources include the detachment of network applica-
tions from network infrastructure and the transition from network planning to
network programming.
Research supported in part by Network Programming (Neptune) Consortium, Israel.
D. Rawitz—Partially supported by the Israel Science Foundation (grant no. 497/14).
c Springer International Publishing AG, part of Springer Nature 2018
D. Alistarh et al. (Eds.): ALGOCLOUD 2017, LNCS 10739, pp. 27–40, 2018.
[Link]
28 G. Kutiel and D. Rawitz

One aspect of network programming is to manage resources from a central

point of view, namely to make decisions based on availability, network status,
required quality of service, and the identity of the client. Hence, a focal issue is a
central agent that is able to received reports from network components and client
requests, and as a result can alter the allocation of resources in the networks.
This approach is called Software Defined Networking (SDN), where there is a
separation between routing and management (control plane) and the underlying
routers and switches that forward traffic (data plane) (see Kreutz et al. [11]).
A complementary approach is Network Function Virtualization (NFV) [3].
Instead of relying on special purpose machines, network applications become
virtual network functions (VNF) that are executed on generic machines and
can be placed in various locations in the network. Virtualization increases the
flexibility of resource allocation and thus the utilization of the network resources.
Internet Service Providers (ISPs) that provide services to clients benefit from
NFV, since it helps to better utilize their physical network. In addition, when
network services are virtualized, an ISP may support service chaining [1], namely
a compound service that consists of a sequence of VNFs. Furthermore, one may
offer a compound service a service that may be obtained using one of several
sequences of VNFs.

1.1 Related Work

In this paper we consider an SDN network that employs NVF [4]. Such networks
attracted a lot of attention in the networking community, especially from a sys-
tems point of view (see, e.g., [9,10]). Several papers also consider the algorithmic
aspects of such networks but mainly present heuristics (see, e.g., [15]). For more
details see [6] and references therein.
Cohen et al. [2] considered VNF placement. In their model the input is
an undirected graph with a metric distance function on the edges. Clients are
located in various nodes, and each client is interested in a subset of VNFs. For
each node v and VNF α, there is a setup cost associated with placing a copy
of α at v (multiple copies are allowed), and there is a load that is induced on
v for placing a copy of α. Furthermore, each node has a limited capacity, and
each copy of a VNF can handle a limited amount of clients. A solution is the
assignment of each client to a subset of nodes, each corresponding to one of its
required VNFs. The cost of a solution is the total setup costs plus the sum of
distances between the clients and the node from which they get service. Cohen
et al. [2] gave bi-criteria approximation algorithms for various versions of the
problem, namely algorithms that compute constant factor approximations that
violate the load constraints by a constant factor. It is important to note that in
this problem routing is not considered and it is assumed that VNF subsets can
be executed in any order.
Lukovszki and Schmid [12] studied the problem of admission control and
placement of service chains, where each chain is associated with a source-
destination pair and is supposed to be routed via an ordered sequence of 
VNFs. The VNFs may have multiple instantiations, but each node has a limited
 Service Chain Placement in SDNs 29

capacity that bounds the number of requests it may service. They presented
an O(log )-competitive algorithm for the problem of maximizing the number of
serviced chains, assuming that capacities are Ω(log ). It is also shown that this
ratio is asymptotically optimal even for randomized online algorithms. APX-
hardness results for the offline version of the problem were also presented. Rost
and Schmid [13] considered variant of this problem, where each node can host a
subset of the VNFs. In addition, each VNF has a demand and each VNF-node
pair has a capacity, and in a feasible solution the total demand for each pair
is bounded by the capacity. They considered two goals: maximum profit and
minimum resource cost and gave bicriteria approximation algorithms which are
based on LP-rounding for several special cases.
Even et al. [5] studied online path computation and VNF placement. They
considered compound requests that arrive in an online manner. Each request is a
flow with a specification of routing and VNF requirements which is represented
by a directed acyclic graph (DAG) whose vertices are VNFs. Each VNF can
be performed by a specified subset of servers in the system. Upon arrival of a
request, the algorithm either rejects the request or accepts it with a specific rout-
ing and VNF assignment, under given server capacity constraints. Each request
has a benefit that is gained if it is accepted, and the goal is to maximize the
total benefit gained by accepted requests. Even et al. [5] proposed an algorithm
that copes with requests with unknown duration without preemption by using
a third response, which is refer to as “stand by”, whose competitive ratio is
O(log(knbmax )), where n is the number of nodes, bmax is an upper bound on a
request benefit per time unit, and k is the maximum number of VNFs of any ser-
vice chain. This performance guarantee holds for the case where the processing
of any request in any possible service chain is never more than O(1/(k log(nk)))
fraction of the capacity of any network component. Even et al. [6] presented
a randomized approximation algorithm for the same problem that computes
(1 − ε)-approximate placements if the demand of any processing request in any
possible service chain is never more than an O(ε2 / log n) fraction of the capacity
of any network component.

1.2 Our Results

We study the allocation problem of a compound flow request for a service chain
in a software-defined network that supports NFV, where the goal is to find an
optimal placement with respect to the current available resources from the point
of view of the network (i.e., the ISP). More specifically, we consider the case
where the network already contains previous resource allocations. Therefore,
we are given a (physical) network that contains servers with limited (residual)
processing power and of links with limited (residual) bandwidth. A request for
service is composed of a source and a destination in the network, an upper bound
on the total latency, and a specification of all service chains that are considered
valid for this request. As in [5], the specification is represented by a DAG whose
vertices are VNFs. The allocation of a service chain consists of routing and VNF
placement. That is, each VNF from the sequence is placed in a server along a
30 G. Kutiel and D. Rawitz

path, and it is feasible if each server can handle the VNFs that are assigned to
it, and if each link on the path can carry the flow that is assigned to it. Moreover
each link causes a delay, and the service chain placement should also comply with
a global bound on the total latency. Each pair of server and VNF is associated
with a cost for placing the network function in the server. This cost measures
compatibility of a VNF to a server (e.g., infinite costs means “incompatible”).
Given a request, the goal is to find a feasible service chain of minimum total cost
or to identify that a valid service chain does not exist.
We show that even feasibility is NP-hard in general networks using a reduc-
tion from Hamiltonian Path. We show that the problem is still NP-hard if the
network is a DAG even for a very simple network, and even if the specification
consists of a single option. Both reductions are from Partition.
On the positive side, we present an FPTAS for the case where the network is
a DAG which is based on a non-trivial dynamic programming algorithm. Based
on our FPTAS, we provide a randomized algorithm for general networks in which
there is an optimal placement whose physical path consists of at most k vertices
whose degree is larger than 2. For example, this can be assumed if all simple
paths from s to t contain at most k such vertices. The algorithm computes a
(1 + ε)-approximate placement with high probability using k! log n invocations
of the FPTAS. We also present a (deterministic) parameterized algorithm that
computes a (1 + ε)-approximate placement in time O(k! · poly(n)), where k is
the number of vertices in the network whose degree is larger than 2.

2 Preliminaries
Model. An instance of the Service Chain Placement (SCP) problem is com-
posed of three components, a physical network, a virtual specification, and place-
ment costs:
Physical network: The physical network is a graph G = (V, E). Each node
v ∈ V has a non-negative processing capacity p(v), and each directed edge
e ∈ E has a non-negative bandwidth capacity b(e). Without loss of generality,
we assume that p(s) = p(t) = 0.
Virtual specification: The description of a request for a service chain consists
of a physical source s ∈ V , a physical destination t ∈ V , and a directed
acyclic graph (DAG) G = (V, E). The DAG G has a source node σ ∈ V and a
destination τ ∈ V. Each node α ∈ V represent a VNF that has a processing
demand p(α). Without loss of generality, we assume that p(σ) = p(τ ) = 0.
Each edge ε ∈ E has a bandwidth demand b(ε).
Placement costs: There is a non-negative cost c(α, v) for placing the VNF α
in v. We assume that c(σ, s) = 0 and c(σ, v) = ∞, for every v = s. Similarly,
we assume that c(τ, t) = 0 and c(τ, v) = ∞, for every v = t.
A solution consists of the following:
Virtual path: A path from σ to τ in G, namely a sequence of vertices α0 , . . . , αq ,
where α0 = σ, αq = τ , and (αj , αj+1 ) ∈ E, for every j ∈ {0, . . . , q − 1}.
 Service Chain Placement in SDNs 31

Physical path: A simple path from s to t in G, namely a sequence of

nodes v0 , . . . , vk , where v0 = s, vk = t, and (vi , vi+1 ) ∈ E, for every
i ∈ {0, . . . , k − 1}.
Placement: A function f that maps a virtual path to a simple physical path.
Formally, a placement is a function f : {α0 , . . . , αq } → {v0 , . . . , vk } where
1. vi = vi if i = i .
2. If f (αj ) = vi and f (αj+1 ) = vi , then i ≤ i .
3. b(αj , αj+1 ) ≤ b(vi , vi+1 ), for every (vi , vi+1 ) ∈ f¯(αj , αj+1 ), where
f¯(αj , αj+1 ) to be the set of physical edges that correspond to it, i.e.,

f¯(αj , αj+1 ) = {(vi , vi+1 ) : i ≤ i < i } ,



where f (αj ) = vi and f (αj+1 ) = vi .

 −1 
4. α∈f −1 (v) p(α) ≤ p(v), where f (v) = {α : f (α) = v}.

An example of an SCP instance and a solution is given in Fig. 1.

2 σ s
4
2 8
4
2

6 2
7
5

1 6 3
4

7 3 3
2
3

τ 1 3 8
6
2

2 8 19
6
5 2
2

2 1
3
8

5
7 4
2 4
8
6
4

4
t

Fig. 1. An example of an SCP instance and a solution.

The cost of a placement f is defined as:



c(f ) = c(αj , f (αj )) .
j

In SCP the goal is to find a feasible placement of a virtual path into the physical
DAG that minimizes the cost.
32 G. Kutiel and D. Rawitz

We also consider an extended version of SCP in which each physical link

causes a delay and there is an upper bound L on the total delay. More formally,
each pair of a virtual edge ε and physical edge e is associated with a latency
(ε, e). Given a placement f : {α0 , . . . , αq } → {v0 , . . . , vk }, the total latency of
the solution is given by
q−1
 
L(f ) = ((αj , αj+1 ), e) .
j=0 e∈f¯((αj ,αj+1 ))

In this case there is an additional constraint that L(f ) ≤ L.

Notation. Given a virtual DAG G, we assume the existence of a topological

sorting of the vertices and write α ≺ β if α precedes β in this ordering. If the
physical network is a DAG, then we make a similar assumption and write v ≺ u
if v precedes u in this ordering.

3 Hardness Results
In this section we present three hardness results. First, we show that even the fea-
sibility question of SCP is NP-hard, and therefore no approximation algorithm
exists for SCP. In addition, we show that SCP is NP-hard even if |V \ {s, t}| = 1.
We also show that SCP is NP-hard even if both the physical network and the
virtual DAG are simple paths.
We start by showing that even finding a feasible solution is NP-hard.

Theorem 1. Feasibility of SCP is NP-hard

Proof. We use a reduction from Hamiltonian Path that is known to be NP-

hard [8]. Given an instance H of Hamiltonian Path we construct an instance
of SCP. For the physical network we have that G, where V (G) = V (H) ∪ {s, t},
and E(G) = E(H) ∪ {(s, v), (v, t) : v ∈ V (H)}. In addition, p(v) = 1, for every
v, and b(e) = 1, for every e. The virtual DAG G is a path containing n + 2
virtual functions, σ = α0 , α1 , . . . , αn , αn+1 = τ , where p(αi ) = 1, for every
i ∈ {1, . . . , n}. Also, b(αi , αi+1 ) = 1, for every i.
The construction can clearly be computed in polynomial time. An Hamilto-
nian Path in G, induces a SCP solution that follows the path, i.e., αi is placed
in the ith vertex along the path. On the other hand, since all demands and
capacities are 1, no two VNFs can share a physical node. Hence a SCP solution
induces an Hamiltonian path.

Next, we show that SCP is NP-hard even if the physical network is very
simple.

Theorem 2. SCP is NP-hard, even if |V \ {s, t}| = 1.

 Service Chain Placement in SDNs 33

Proof. We prove the theorem using a reduction from Partition. Given a

Partition instance {a1 , . . . , an }, we construct an SCP instance as follows. The
physical network G contains three nodes: s, v,and t, and there are two edges
(s, v) and (v, t). The capacity of v is p(v) = 12 i ai . Edge bandwidth are zero.
The virtual DAG is composed of 2n + 2 vertices, namely

V = {σ, τ } ∪ {α1 , . . . , αn } ∪ {β1 , . . . , βn } .

Also,

E= {{αi , βi } × {αi+1 , βi+1 }} ∪ {(σ, α1 ), (σ, β1 ), (αn , t), (βn , t)} .
i

The DAG is shown in Fig. 2. The demands are p(αi ) = ai and p(βi ) = 0, for
every i. Also, b(ε) = 0, for every ε ∈ E. The costs are: c(αi , v) = 0 and c(βi , v) =
ai , for every i.
The SCP instance can be computed in polynomial time. Also, it is not hard
to verify that {a 1 , . . . , an } ∈ Partition if and only if there exists a solution
whose cost is 12 i ai .

α1 α2 ... αn

σ τ

β1 β2 ... βn

Fig. 2. The specification defined in the proof of Theorem 2.

Next, we show that SCP is NP-hard even if both the physical network and
the VNF specification are paths.
Theorem 3. SCP is NP-hard, even if both the physical network and the virtual
DAG are paths.
Proof. We prove the theorem using a reduction from Partition. Given a Par-
tition instance {a1 , . . . , an }, we construct a virtual path σ, α1 , . . . , αn , τ and a
physical path s, v1− , v1+ , . . . , vn− , vn+ , t. We set p(v) = 1, for every node v = s, t,
and p(αi ) = 1, for every i. In addition, we set b(e) = 1, for every edge e ∈ E,
and b(ε) = 1, for every edge ε ∈ E. As for the costs, we define c(αi , vi− ) = 0,
c(αi , vi+ ) = ai , and for any v ∈ / {vi− , vi+ } we set c(αi , v) = ∞. We also define
− +
((αi , αi+1 ), (vi , vi )) = ai , and set (ε, e) = 0, otherwise. Finally, we set
n
L = 12 i ai . Figure 3 depicts the above reduction. One can verify that ai is
either counted in the latency of in the cost. Hence, n {a1 , . . . , an } ∈ Partition if
and only if there is a placement with cost 12 i ai .
34 G. Kutiel and D. Rawitz

σ α1 α2 ··· αn τ

0
v1− v2− ··· vn− t

an
a1

a2
0

a1

an
a2
0

0
0
0

0
s v1+ v2+ ··· vn+

Fig. 3. A reduction from a partition instance a1 , . . . , an . The cost function enforces

each αi to be placed either in vi− or in vi+ . In the former case this placement incure no
cost but additional latency of ai , in the later case there will be additional ai cost with
zero latency.

4 Algorithms for Physical Directed Acyclic Graphs

In this section we present an FPTAS for SCP in DAGs which is based on a
dynamic programming algorithm. The algorithm is described in a top down man-
ner. We first assume that costs are polynomially bounded and design a dynamic
programming algorithm that computes a minimum cost placement of a virtual
path within a single physical node. Next, we provide a dynamic programming
algorithm for SCP without the latency constraint. Then, we give an algorithm
that copes with a global latency constraint. At the end of the section we drop
our assumption on the costs and use standard scaling techniques to obtain an
FPTAS for SCP in DAGs.

4.1 Placing a Sub-chain in a Physical Node

Assume that we want to place a minimum cost virtual path from a VNF α to a
VNF β within a physical node v. A sequence of VNFs  α = α0 , α2 , . . . , αq = β is
a candidate path if (αi , αi+1 ) ∈ E, for every i, and i p(αi ) ≤ p(v). We would
like to find such a path with minimum cost, and we denote the cost of such a
path by costv (α  β).
We use dynamic programming in order to compute such a path. Let
prcv (α  β, c) be the minimum amount of processing required to place a vir-
tual path form α to β into v among paths whose cost is at most c. The value of
prcv (α  β, c) can be computed recursively as follow:
⎧
⎪
⎪ ∞ c(α, v) > c,
⎪
⎪
⎨ c(α, v) ≤ c,
prcv (α  β, c) = p(α) β = α,
⎪
⎪
⎪
⎪
⎩ min {prcv (α  γ, c − c(β, v)) + p(β)} otherwise.
(γ,β)∈E

Observe that if c(α, v) > c, then a placement is not possible with a budget c.
Otherwise, if α = β, then the best path is the one containing only α. If α = β,
 Service Chain Placement in SDNs 35

then an optimal path ends with an edge (γ, β) ∈ E, which means that the
processing placed at v consists of p(β) plus the minimum amount of processing
of a path from α to γ, whose cost is at most c − c(β, v).
To complete our argument observe that the following holds:

costv (α  β) = min {c : prcv (α  β, c) ≤ p(v)} .

Since the costs are assumed to be polynomially bounded, there is a polyno-

mial number of states to be computed, and the computation of each of them
can be done in linear time. Hence, the total running time is polynomial. Finally,
we note that the above algorithm computes the minimum amount of processing,
but may also be used to compute the actual placement that achieves this value
using standard techniques.

4.2 Placing a Service Chain

In this section we describe a dynamic programming algorithm for placing a

service chain without a global latency bound.
Consider an optimal solution of SCP, i.e., a service chain from σ to τ which
is placed along a path from s to t in the physical DAG. Suppose v is a node along
the path from s to t. Also, let α be the last VNF in the service chain which is
placed in the path from s to v. It must be that the placement of the VNFs from
σ to α in the path from s to v is the best one among all placements of a virtual
path from σ to α in a path from s to v. In other words, any partial placement of
an optimal placement is also optimal. Our algorithm is based on this property.
We define a state for each pair of VNF α and physical node v. Let cost(α, v)
stand for the minimum cost placement of a virtual path from σ to α in a path
from s to v, where α is the last VNF which is placed along the physical path.
In addition, we write (u, v) ⇒ (γ, β) if v is reachable from u using only edges
with bandwidth at least b(γ, β), namely if there is a path from u to v such that
the bandwidth of all edges in the path is at least b(γ, β). cost(α, v) can be
computed recursively, as follows:
⎧
⎪
⎪ 0 α = σ, v = s,
⎨
cost(α, v) = β≺α,(γ,β)∈E,
min {cost(γ, u) + costv (β  α)} otherwise.
⎪
⎪
⎩ u≺v,
(u,v)⇒(γ,β)

The desired value is cost(τ, t). Consider an optimal placement of a virtual path
ending at α within a path ending at v. Let γ be the first VNF along the virtual
path that is not placed in v. Also, let u be the node in which γ is placed. Hence,
the optimal placement is composed of three segments: an optimal placement of
a virtual path that ends in γ in a physical path ending at u, a virtual edge (γ, β)
is placed in the path from u to v, and a minimum cost placement of a virtual
path from β to α in v, that does not violate the capacity of v. Thus, we check all
pairs (γ, u), where γ ≺ α and u ≺ v, and for each pair we consider any neighbor
36 G. Kutiel and D. Rawitz

Virtual Graph

b(αβ)
σ α β γ

s v w

Physical Graph

Fig. 4. The optimal placement of a path to α into a path to v can be efficiently

computed by breaking the problem into the problem of placing a path to γ-path into
a path to u (blue, dashed rectangles) and the problem of embedding a path from β to
α into v (orange, dotted). The path from u to v must carry at least b(γ, β) bandwidth.
(Color figure online)

(γ, β) ∈ E and β ≺ α such that (u, v) ⇒ (γ, β). The recursive computation is
illustrated in Fig. 4.
As for the running time, observe that checking whether (u, v) ⇒ (γ, β) can be
done using DFS in linear time. Since the number of state is polynomial, and each
state can be computed in polynomial time, the total running time is polynomial.
Finally, we note that the above algorithm computes the minimum amount of
cost, but may also be used to compute the actual placement that achieves this
value using standard techniques.

4.3 Placing a Service Chain with a Latency Bound

We now consider the SCP problem with latency. Recall that in this variant of
the problem we are also given a latency function  : E × E → R+ , and a latency
upper bound L. The goal is to find a minimum cost placement that also respect
the latency constraint.
Let lat(α, v, c) be the minimum latency created by a placement of a virtual
path from σ to α in a path from s to v whose cost is at most c. Also, let
lat(γ, β, w  v) be the minimum possible latency of path from w to v such
that the bandwidth of all edges in the path is at least b(γ, β). That is,

lat(γ, β, w  v) = min ((γ, β), e) .
f :b(γ,β)≤mine∈f¯(γ,β) b(e)
e∈f¯(γ,β)

Observe that lat(γ, β, w  v) can be computed using a Shortest Path algo-

rithm, were we consider only edges whose bandwidth cap is at least b(γ, β). Now
we are ready for the computation of lat(α, v, c):
 Service Chain Placement in SDNs 37
⎧
⎪
⎪∞ c < 0,
⎪
⎪
⎪
⎪ α = σ, v = s,
⎪
⎪0
⎨ and c ≥ 0,
lat(α, v, c) =
⎪
⎪ lat(γ, β, w  v)+
⎪
⎪ min otherwise.
⎪
⎪ β≺α,(γ,β)∈E, lat(γ, u, c − costv (β  α))
⎪
⎪
⎩w≺v,(u,w)∈E,
(u,v)⇒(γ,β)

The minimum latency of a placement of a path to α in a path to v whose cost is

at most c can be divided into two values: the latency caused by the placement of
a path to γ, where (γ, β) ∈ E, and β ≺ α, with cost c − costv (β  α), and the
latency caused by placing a virtual edge (γ, β) on a physical path from w to v,
where w ≺ v and (u, w) ∈ E. The optimal value is min {c : lat(τ, t, c) ≤ L}.
Since the computation of lat(γ, β, w  v) can be done efficiently, the com-
putation for a triple (α, v, c) can be done in polynomial time. Hence, the total
running time is polynomial. Finally, as in the previous algorithms, one may use
the algorithm to compute a corresponding placement using standard techniques.

4.4 FPTAS for General Costs

In this section we present an FPTAS for SCP in DAGs for general costs, namely
without the assumption that costs are polynomially bounded. Our algorithm is
similar to the FPTAS for the Minimum Knapsack problem.
Let f be an optimal placement, and let cmax be the maximum cost of a VNF
placement by f , i.e., cmax = maxf (α)=u c(α, v). Given a constant ε > 0, we define

c(α,v) n
· c(α, v) ≤ cmax ,
c (α, v) =
 cmax ε
∞ c(α, v) > cmax .

Let f  be an optimal placement with respect to c .

Lemma 1. c(f  ) ≤ (1 + ε)c(f ).

Proof. We have that

 εcmax 
c(f  ) = c(α, f  (α)) ≤ · c (α, f  (α))
α
n α
εcmax 
≤ · c (α, f (α))
n α
εcmax  εcmax 
≤ · c(α, f (α)) · +1
n α
n
= c(f ) + εcmax
≤ (1 + ε)c(f ) ,

where the second inequality is due to the optimality of f  with respect to c .

38 G. Kutiel and D. Rawitz

This leads to the following result:

Theorem 4. There exists an FPTAS for SCP in DAGs.

Proof. Given ε > 0, run the dynamic programming algorithm from Sect. 4.3 |V| ·
|V | times, once for each possible value of cmax , and choose the best placement.
According to Lemma 1 the best placement is (1 + ε)-approximate. The running
time is polynomial in the input size and in 1/ε.

5 General Networks
In this section we consider SCP when the physical network is an undirected
graph. Recall that even the feasibility version of SCP is NP-hard in general
networks, and therefore we focus on a special case. A vertex v ∈ V is called
neighborly if it has more than two neighbors. First, we assume that there exists
an optimal placement whose physical path consists of at most k neighborly
vertices. For example, this can be assumed if all simple paths from s to t contain
at most k neighborly vertices. In this case we present a randomized algorithm
that computes an (1 + ε)-approximate placement with high probability whose
running time is O(k! · poly(n)). Our second algorithm works under the stronger
assumption that there are k neighborly vertices in the network. In this case, we
present a deterministic algorithm whose running time is O(k! · poly(n)).
Our randomized algorithm consists of k! iterations of the following two
phases: an orientation phase that applies a random orientation to the physi-
cal network, and an execution of the FPTAS for DAGs given in Theorem 4. The
algorithm finds a (1 − ε)-approximate placement with probability (1 − 1/e), and
the running time of the algorithm is O((n + t(n))k!), where t(n) is the time it
takes to compute a placement when the physical network is a DAG. As usual,
one may amplify the probability of success using repetition.
The orientation phase is done as follows: let N be the set of neighborly
vertices, and let π : N → {1, . . . , |N |} be a random permutation. We direct the
edges according to π. Observe that each edge e ∈ E is found on a simple path
between two neighborly nodes ve and ve , in which all internal vertices are in
V \ N . The edge e is directed towards ve , if π(ve ) > π(ve ), and otherwise it is
directed towards ve . Observe that when this process terminates we get a DAG,
denoted by Gπ , where there is a topological order than is consistent which π.
Figure 5 depicts the orientation stage. A naı̈ve implementation of this phase
would run in O(|V ||E|) time.
Upon completing the orientation, we use our previous algorithm to find a
placement. We repeat this process k! times, each time with a new independent
random permutation, and keep the best embedding so far.

Theorem 5. There exists an algorithm, that given an SCP instance with an

optimal solution that contains at most k neighborly vertices, finds a (1 + ε)-
approximate placement with high probability, whose running time is O(k! ·
poly(n)).
 Service Chain Placement in SDNs 39

1 1

2 3 2 3

6 6

5 5

4 4

Fig. 5. Orientation phase: on the left is the physical network, where only the heavy
nodes are drawn. The numbers represent the permutation and the dashed path repre-
sents a path of an optimal placement. The orientated physical network is on the right.
It is enough that the internal ordering of the nodes on the dashed path is “correct” to
ensure that the survival of the optimal placement.

Proof. Consider an optimal placement with at most k neighborly vertices, and

let π  be the permutation it induces on the neighborly vertices in the physical
path. If the random permutation π orders the neighborly vertices correctly, i.e.,
if π(v) = π  (v), for every v ∈ N , then the optimal placement is feasible with
respect to Gπ . Hence, the FPTAS will find a (1 + ε)-approximate placement
in Gπ . This placement is feasible, and therefore (1 + ε)-approximate placement,
with respect to G. The permutation π agrees with π  with probability 1/k!, and
the probability that π agrees with π  in k! iterations is 1 − (1 − 1/k!)k! ≥ 1 − e−1 .
One may amplify the success probability to 1 − n1 using log n repetitions.
In the case where |N | = k we can simply examine the k! permutations of
the neighborly vertices. For each possible permutation the algorithm applies the
graph orientation procedure as described above, and then executes the FPTAS
for DAGs given in Sect. 4.4. Thus the running time of the algorithm is O(k! ·
poly(n)). We note that permutation enumeration for k numbers takes O(k!) time
(see e.g., [7,14]).
Theorem 6. There exists an O(k!·poly(n))-time algorithm, that given an SCP
instance with k neighborly vertices, finds a (1 + ε)-approximate placement.

Acknowledgement. We thank Reuven Bar-Yehuda for helpful discussions.

References
1. Brown, G.: Service Chaining in Carrier Networks. Heavy Reading (2015)
2. Cohen, R., Lewin-Eytan, L., Naor, J., Raz, D.: Near optimal placement of virtual
network functions. In: 34th IEEE Conference on Computer Communications, pp.
1346–1354 (2015)
40 G. Kutiel and D. Rawitz

3. ETSI: Network Functions Virtualisation: An Introduction, Benefits, Enablers,

Challenges & Call for Action, October 2012
4. ETSI: Network Functions Virtualisation (NFV); Ecosystem; Report on SDN Usage
in NFV Architectual Framework, December 2015
5. Even, G., Medina, M., Patt-Shamir, B.: On-line path computation and function
placement in SDNs. In: Bonakdarpour, B., Petit, F. (eds.) SSS 2016. LNCS, vol.
10083, pp. 131–147. Springer, Cham (2016). [Link]
49259-9 11
6. Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation
and function placement in SDNs. In: Suomela, J. (ed.) SIROCCO 2016. LNCS,
vol. 9988, pp. 374–390. Springer, Cham (2016). [Link]
48314-6 24
7. Even, S.: Algorithmic Combinatorics. Macmillan Inc., New York (1973)
8. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory
of NP-Completeness. W.H. Freeman and Company, San Francisco (1979)
9. Gember-Jacobson, A., Viswanathan, R., Prakash, C., Grandl, R., Khalid, J., Das,
S., Akella, A.: OpenNF: enabling innovation in network function control. In: ACM
SIGCOMM, pp. 163–174 (2014)
10. Hartert, R., Vissicchio, S., Schaus, P., Bonaventure, O., Filsfils, C., Telkamp, T.,
François, P.: A declarative and expressive approach to control forwarding paths in
carrier-grade networks. In: ACM SIGCOMM, pp. 15–28 (2015)
11. Kreutz, D., Ramos, F.M.V., Verı́ssimo, P.J.E., Rothenberg, C.E., Azodolmolky,
S., Uhlig, S.: Software-defined networking: a comprehensive survey. Proc. IEEE
103(1), 14–76 (2015)
12. Lukovszki, T., Schmid, S.: Online admission control and embedding of service
chains. In: Scheideler, C. (ed.) Structural Information and Communication Com-
plexity. LNCS, vol. 9439, pp. 104–118. Springer, Cham (2015). [Link]
1007/978-3-319-25258-2 8
13. Rost, M., Schmid, S.: Service chain and virtual network embeddings: Approxima-
tions using randomized rounding. Technical report abs/1604.02180, CoRR (2016)
14. Sedgewick, R.: Permutation generation methods. ACM Comput. Surv. 9(2), 137–
164 (1977)
15. Soulé, R., Basu, S., Marandi, P.J., Pedone, F., Kleinberg, R.D., Sirer, E.G., Foster,
N.: Merlin: a language for provisioning network resources. In: 10th ACM Interna-
tional on Conference on emerging Networking Experiments and Technologies, pp.
213–226 (2014)