Joint Placement and Allocation of VNF Nodes With Budget and Capacity Constraints
Joint Placement and Allocation of VNF Nodes With Budget and Capacity Constraints
复制标题
DOI：
10.1109/tnet.2021.3058378
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
G. Sallam;Bo Ji
中科院分区：
文献类型：
--
作者：
G. Sallam;Bo Ji
随着网络功能虚拟化（NFV）的出现，传统上在专有专用硬件上运行的网络服务现在可以使用托管在通用商用硬件上的虚拟网络功能（VNF）来实现。这种新的网络范式为互联网服务提供商（ISP）高效运营其网络（收集网络统计数据、执行管理策略等）提供了极大的灵活性。然而，引入NFV需要投资在某些网络节点（称为VNF节点）上部署VNF，这必须考虑到实际的限制因素，如部署预算和VNF节点容量。为此，设计一种联合的VNF节点放置和容量分配算法非常重要，该算法能够在考虑这些实际限制的同时，使由VNF节点完全处理的网络流量总量最大化。与大多数先前的工作往往忽略预算约束或容量约束不同，我们明确考虑了这两个约束。我们证明考虑这些约束带来了几个新的挑战。具体而言，我们证明所研究的问题不仅是NP难的，而且是非次模的。为了应对这些挑战，我们引入了一种新的松弛方法，使得松弛放置子问题的目标函数变为次模的。利用这种有用的次模性质，我们提出了两种算法，对于原始的非松弛问题，它们分别实现了$\frac{1}{2}(1 - 1/e)$和$\frac{1}{3}(1 - 1/e)$的近似比。最后，我们通过基于跟踪驱动的模拟进行广泛评估，证实了所提出算法的有效性。
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.