  In this paper, we consider the network slicing problem which attempts to map
multiple customized virtual network requests (also called services) to a common
shared network infrastructure and allocate network resources to meet diverse
service requirements, and propose an efficient two-stage algorithm for solving
this NP-hard problem. In the first stage, the proposed algorithm uses an
iterative linear programming (LP) rounding procedure to place the virtual
network functions of all services into cloud nodes while taking traffic routing
of all services into consideration; in the second stage, the proposed algorithm
uses an iterative LP refinement procedure to obtain a solution for traffic
routing of all services with their end-to-end delay constraints being
satisfied. Compared with the existing algorithms which either have an
exponential complexity or return a low-quality solution, our proposed algorithm
achieves a better trade-off between solution quality and computational
complexity. In particular, the worst-case complexity of our proposed algorithm
is polynomial, which makes it suitable for solving large-scale problems.
Numerical results demonstrate the effectiveness and efficiency of our proposed
algorithm.
