  With the advent of Network Function Virtualization (NFV), network services
that traditionally run on proprietary dedicated hardware can now be realized
using Virtual Network Functions (VNFs) that are hosted on general-purpose
commodity hardware. This new network paradigm offers a great flexibility to
Internet service providers (ISPs) for efficiently operating their networks
(collecting network statistics, enforcing management policies, etc.). However,
introducing NFV requires an investment to deploy VNFs at certain network nodes
(called VNF-nodes), which has to account for practical constraints such as the
deployment budget and the VNF-node capacity. To that end, it is important to
design a joint VNF-nodes placement and capacity allocation algorithm that can
maximize the total amount of network flows that are fully processed by the
VNF-nodes while respecting such practical constraints. In contrast to most
prior work that often neglects either the budget constraint or the capacity
constraint, we explicitly consider both of them. We prove that accounting for
these constraints introduces several new challenges. Specifically, we prove
that the studied problem is not only NP-hard but also non-submodular. To
address these challenges, we introduce a novel relaxation method such that the
objective function of the relaxed placement subproblem becomes submodular.
Leveraging this useful submodular property, we propose two algorithms that
achieve an approximation ratio of $\frac{1}{2}(1-1/e)$ and $\frac{1}{3}(1-1/e)$
for the original non-relaxed problem, respectively. Finally, we corroborate the
effectiveness of the proposed algorithms through extensive evaluations using
trace-driven simulations.
