  With the advent of Network Function Virtualization (NFV), Physical Network
Functions (PNFs) are gradually being replaced by Virtual Network Functions
(VNFs) that are hosted on general purpose servers. Depending on the call flows
for specific services, the packets need to pass through an ordered set of
network functions (physical or virtual) called Service Function Chains (SFC)
before reaching the destination. Conceivably for the next few years during this
transition, these networks would have a mix of PNFs and VNFs, which brings an
interesting mix of network problems that are studied in this paper: (1) How to
find an SFC-constrained shortest path between any pair of nodes? (2) What is
the achievable SFC-constrained maximum flow? (3) How to place the VNFs such
that the cost (the number of nodes to be virtualized) is minimized, while the
maximum flow of the original network can still be achieved even under the SFC
constraint? In this work, we will try to address such emerging questions.
First, for the SFC-constrained shortest path problem, we propose a
transformation of the network graph to minimize the computational complexity of
subsequent applications of any shortest path algorithm. Second, we formulate
the SFC-constrained maximum flow problem as a fractional multicommodity flow
problem, and develop a combinatorial algorithm for a special case of practical
interest. Third, we prove that the VNFs placement problem is NP-hard and
present an alternative Integer Linear Programming (ILP) formulation. Finally,
we conduct simulations to elucidate our theoretical results.
