Achieving High End-to-End Availability in VNF Networks
Achieving High End-to-End Availability in VNF Networks
复制标题
DOI：
10.1109/icccn54977.2022.9868897
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Enrique Rodicio;Deng Pan;Jason Liu;Bin Tang
中科院分区：
文献类型：
--
作者：
Enrique Rodicio;Deng Pan;Jason Liu;Bin Tang
作为软件程序，虚拟网络功能（VNFs）由于其潜在的软件故障给网络可用性带来了新的挑战。关于VNF网络可用性的现有模型没有考虑到所有可能的硬件和软件故障，使它们无法分析路径的端到端可用性。此外，他们没有捕捉路径中重复节点和链接之间的相关性，导致不准确的分析结果。在本文中，我们提出了一个新的分析模型，该模型考虑了所有硬件和软件故障以及重复组件的影响，以有效地分析VNF网络中流路径的端到端可用性。在分析模型的基础上，提出了寻找端到端可用性最高的流路径的最高可用路径（HAP）问题，并通过对节点加权斯坦纳树问题的约简证明了其np -硬度。接下来，我们提出了两种HAP算法：第一种算法基于斯坦纳树近似算法，具有较高的时间复杂度并作为性能基准；第二种是利用动态规划方法在多项式时间内搜索多层图。最后，我们提供了大量的评估数据来证明分层搜索算法的有效性，该算法实现了与基于斯坦纳树的算法相当的性能，并且运行速度提高了四个数量级。
As software programs, Virtual Network Functions (VNFs) introduce new challenges to network availability due to their potential software failures. Existing models on the availability of VNF networks did not consider all the possible hardware and software failures, making them incapable of analyzing the end-to-end availability of a path. Furthermore, they did not capture the correlation between repeating nodes and links in the path, resulting in inaccurate analytical results. In this paper, we propose a new analytical model, which considers all hardware and software failures as well as the effect of repeating components, to effectively analyze the end-to-end availability of a flow path in VNF networks. On top of the analytical model, we formulate the Highest Availability Path (HAP) problem that finds the flow path with the highest end-to-end availability, and prove its NP-hardness by reduction from the Node-Weighted Steiner Tree problem. Next, we propose two algorithms for HAP: the first one based on a Steiner Tree approximation algorithm, having high time complexity and serving as a performance benchmark; the second one using a dynamic programming approach to search a multi-layer graph in polynomial time. Finally, we present extensive evaluation data to demonstrate the effectiveness of the Layered Search algorithm, which achieves comparable performance as that of the Steiner Tree based algorithm and runs faster by four orders of magnitude.