基于线性规划松弛的虚拟网络映射算法

"虞红芳和高秀娇在2012年的电子科技大学学报上发表了一篇关于网络虚拟化的文章，题目为‘点边联合协调的高效虚拟网络映射’，该研究提出了一种利用线性规划松弛的点边联合协调虚拟网络映射算法，旨在提高网络虚拟化的效率。通过添加约束条件强化线性松弛模型STRICT_LP，并采用渐进启发式算法求解映射问题。仿真结果表明，该算法在成功率、网络开销、收益以及网络收益开销比值等方面优于现有的D-ViNE和R-ViNE算法。" 这篇文章探讨的核心知识点是虚拟网络映射，这是网络虚拟化中的关键技术。网络虚拟化允许多个虚拟网络在共享的物理基础设施上独立运行，提高了网络资源的利用率和灵活性。传统的虚拟网络映射问题通常被建模为混合整数线性规划（MILP）问题，这是一个复杂的优化问题，因为它涉及到离散和连续变量的组合。 文章提出的新方法是基于线性规划松弛的策略，首先对原始的MILP模型进行松弛，这样可以简化问题，使其更易于求解。为了保持问题的有效性和精确性，他们在松弛模型中添加了额外的约束条件，形成STRICT_LP模型。这种方法有助于在保持计算效率的同时，更好地捕捉实际问题的特性。 接下来，他们应用了一种渐进启发式算法来解决这个强化后的模型。启发式算法是一种实用的优化策略，它可能无法找到全局最优解，但在实际应用中能够快速获得接近最优的解决方案。这种算法在处理大规模问题时特别有用，因为它可以在有限的时间内找到可行的映射解。 实验结果证明了该算法在虚拟网络映射方面的优越性。它在四个方面显著优于D-ViNE和R-ViNE算法：成功率更高，意味着更多的虚拟网络请求能够成功映射；网络开销更低，意味着资源使用更加经济；收益更大，表示服务提供者能够获取更高的利润；网络收益开销比值更高，这意味着在投入的成本和产生的收益之间有更好的平衡。 这篇论文为网络虚拟化提供了一种有效且高效的映射策略，通过点边联合协调和线性规划松弛的结合，提高了映射质量和资源利用率，对于网络虚拟化领域的研究和实践具有重要的参考价值。