IEEE Trans Cybern. 2018 Feb;48(2):510-521. doi: 10.1109/TCYB.2016.2645123. Epub 2017 Feb 20.
Network virtualization helps overcome shortcomings of the current Internet architecture. The virtualized network architecture enables coexistence of multiple virtual networks (VNs) on an existing physical infrastructure. VN embedding (VNE) problem, which deals with the embedding of VN components onto a physical network, is known to be -hard. In this paper, we propose two VNE algorithms: MaVEn-M and MaVEn-S. MaVEn-M employs the multicommodity flow algorithm for virtual link mapping while MaVEn-S uses the shortest-path algorithm. They formalize the virtual node mapping problem by using the Markov decision process (MDP) framework and devise action policies (node mappings) for the proposed MDP using the Monte Carlo tree search algorithm. Service providers may adjust the execution time of the MaVEn algorithms based on the traffic load of VN requests. The objective of the algorithms is to maximize the profit of infrastructure providers. We develop a discrete event VNE simulator to implement and evaluate performance of MaVEn-M, MaVEn-S, and several recently proposed VNE algorithms. We introduce profitability as a new performance metric that captures both acceptance and revenue to cost ratios. Simulation results show that the proposed algorithms find more profitable solutions than the existing algorithms. Given additional computation time, they further improve embedding solutions.
网络虚拟化有助于克服当前互联网架构的缺点。虚拟化网络架构允许在现有物理基础设施上共存多个虚拟网络（VN）。VN 嵌入（VNE）问题是将 VN 组件嵌入到物理网络中的问题，被认为是 NP 难问题。在本文中，我们提出了两种 VNE 算法：MaVEn-M 和 MaVEn-S。MaVEn-M 采用多商品流算法进行虚拟链路映射，而 MaVEn-S 则使用最短路径算法。它们通过使用马尔可夫决策过程（MDP）框架形式化虚拟节点映射问题，并使用蒙特卡罗树搜索算法为所提出的 MDP 设计动作策略（节点映射）。服务提供商可以根据 VN 请求的流量负载调整 MaVEn 算法的执行时间。算法的目标是最大化基础设施提供商的利润。我们开发了一个离散事件 VNE 模拟器来实现和评估 MaVEn-M、MaVEn-S 以及最近提出的几种 VNE 算法的性能。我们引入了盈利能力作为一个新的性能指标，它同时捕获了接受率和收支比。仿真结果表明，所提出的算法比现有的算法找到更有利可图的解决方案。在增加计算时间的情况下，它们进一步改进了嵌入解决方案。
