Virtual Network Function Deployment in Tree-Structured Networks
Virtual Network Function Deployment in Tree-Structured Networks
复制标题
DOI：
10.1109/icnp.2018.00023
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Yang Chen;Jie Wu;Bo Ji
中科院分区：
文献类型：
--
作者：
Yang Chen;Jie Wu;Bo Ji
网络功能虚拟化（NFV）将网络功能的实现从昂贵的硬件发展到软件中间盒。这些软件中间盒也称为虚拟网络功能（VNF），在交换机连接的服务器上执行。有效地部署这样的VNF是具有挑战性的，因为VNF必须在它们到达它们的目的地之前以它们的流量速率完全处理所有流，而VNF位置受到顶点容量的约束。此外，每个网络功能提供具有不同处理量和成本配置的异构VNF类型。本文的重点是最大限度地减少部署VNF实例的总成本，为树结构网络中的所有流提供特定的网络功能。首先，我们证明了在树拓扑异构VNF部署的NP-困难，并提出了一个基于动态规划的解决方案与伪多项式的时间复杂度。然后，我们缩小到三个简化的情况下，专注于同质VNF或线性线拓扑结构。具体地，介绍了三种算法：用于在树拓扑中部署同构VNF的改进的基于动态规划的算法，用于在线性线拓扑中部署异构VNF的性能保证算法，以及用于在线性线拓扑中部署同构VNF的最优贪婪算法。大量的模拟进行评估我们的算法的性能。
Network Function Virtualization (NFV) evolves the implementation of network functions from expensive hardwares to software middleboxes. These software middleboxes, also called Virtual Network Functions (VNFs), are executed on switch-connected servers. Efficiently deploying such VNFs is challenging, because VNFs must fully process all flows with their traffic rates before they reach their destinations while VNF locations are restricted by the constraint of vertex capacity. In addition, each network function offers heterogeneous VNF types with different configurations of processing volumes and costs. This paper focuses on minimizing the total cost of deploying VNF instances for providing a specific network function to all flows in tree-structured networks. First we prove the NP-hardness of heterogeneous VNF deployment in a tree topology and propose a dynamic programming based solution with a pseudo-polynomial time complexity. Then we narrow down to three simplified cases by focusing on homogeneous VNFs or the linear line topology. Specifically, three algorithms are introduced: an improved dynamic programming based algorithm for deploying homogeneous VNFs in a tree topology, a performance-guaranteed algorithm for deploying heterogeneous VNFs in a linear line topology, and an optimal greedy algorithm for deploying homogeneous VNFs in a linear line topology. Extensive simulations are conducted to evaluate the performance of our algorithms.