  Software Defined Networking and Network Function Virtualization are two
paradigms that offer flexible software-based network management. Service
providers are instantiating Virtualized Network Functions - e.g., firewalls,
DPIs, gateways - to highly facilitate the deployment and reconfiguration of
network services with reduced time-to-value. They employ Service Function
Chaining technologies to dynamically reconfigure network paths traversing
physical and virtual network functions. Providing a cost-efficient virtual
function deployment over the network for a set of service chains is a key
technical challenge for service providers, and this problem has recently caught
much attention from both Industry and Academia. In this paper, we propose a
formulation of this problem as an Integer Linear Program that allows one to
find the best feasible paths and virtual function placement for a set of
services with respect to a total financial cost, while taking into account the
(total or partial) order constraints for Service Function Chains of each
service and other constraints such as end-to-end latency, anti-affinity rules
between network functions on the same physical node and resource limitations in
terms of network and processing capacities. Furthermore, we propose a heuristic
algorithm based on a linear relaxation of the problem that performs close to
optimum for large scale instances.
