  Network Function Virtualization (NFV) aims to abstract the functionality of
traditional proprietary hardware into software as Virtual Network Functions
(VNFs), which can run on commercial off the shelf (COTS) servers. Besides
reducing dependency on proprietary support, NFV helps network operators to
deploy multiple services in a agile fashion. Service deployment involves
placement and in sequence routing through VNFs comprising a Service Chain (SC).
Our study is the first to focus on the computationally complex problem of
multiple VNF SC placement and routing while considering VNF service chaining
explicitly. We propose a novel column generation model for placing multiple VNF
SCs and routing, which reduces the computational complexity of the problem
significantly. Our aim here is to determine the ideal NFV Infrastructure (NFVI)
for minimizing network resource consumption. Our results indicate that a
Network enabled Cloud (NeC) results in lower networkresource consumption than a
centralized NFVI (e.g., Data Center) while avoiding infeasibility with a
distributed NFVI.
