论文标题
在线联合放置和分配虚拟网络功能与异质服务器
Online Joint Placement and Allocation of Virtual Network Functions with Heterogeneous Servers
论文作者
论文摘要
网络功能虚拟化（NFV）是一种有希望的虚拟化技术，有可能显着降低支出并改善服务敏捷性。 NFV使Internet服务提供商（ISP）有可能在不安装新设备的情况下使用各种虚拟网络功能（VNF）。 NFV技术中最有吸引力的方法之一是虚拟网络功能（JPA-VNF）的所谓联合放置和分配，该功能（JPA-VNF）考虑了VNF投资与服务质量（QoS）之间的平衡。我们引入了一种新型的功能功能，以测量提出的OJPA-HS模型中每个服务器的VNF实例的潜力。该模型允许网络中的服务器是异质的，同时结合了许多经典的JPA-VNF模型。尽管它具有NP硬度，但我们提出了一种基于动态编程（DP）的可证明的最佳确定性在线算法。为了征服DP的高复杂性，我们提出了另外两种随机启发式方法，即拉斯维加斯（LV）和蒙特卡洛（MC）随机算法，它们的性能与DP的性能较小，复杂性较小。此外，MC在实践中是一个有前途的启发式方法，因为它具有处理大数据环境的优势。为论文中提出的算法构建了广泛的数值实验。
Network Function Virtualization (NFV) is a promising virtualization technology that has the potential to significantly reduce the expenses and improve the service agility. NFV makes it possible for Internet Service Providers (ISPs) to employ various Virtual Network Functions (VNFs) without installing new equipments. One of the most attractive approaches in NFV technology is a so-called Joint Placement and Allocation of Virtual Network Functions (JPA-VNF) which considers the balance between VNF investment with Quality of Services (QoS). We introduce a novel capability function to measure the potential of locating VNF instances for each server in the proposed OJPA-HS model. This model allows the servers in the network to be heterogeneous, at the same time combines and generalizes many classical JPA-VNF models. Despite its NP-hardness, we present a provable best-possible deterministic online algorithm based on dynamic programming (DP). To conquer the high complexity of DP, we propose two additional randomized heuristics, the Las Vegas (LV) and Monte Carlo (MC) randomized algorithms, which performs even as good as DP with much smaller complexity. Besides, MC is a promising heuristic in practice as it has the advantage to deal with big data environment. Extensive numerical experiments are constructed for the proposed algorithms in the paper.
