A Novel Optimal Mapping Algorithm With Less Computational Complexity for Virtual Network Embedding
A Novel Optimal Mapping Algorithm With Less Computational Complexity for Virtual Network Embedding
复制标题
DOI：
10.1109/tnsm.2017.2778106
复制
发表时间：
2018-03-01
影响因子：
5.3
通讯作者：
Yang, Longxiang
中科院分区：
文献类型：
--
作者：
Cao, Haotong;Zhu, Yongxu;Yang, Longxiang
网络虚拟化（NV）被广泛接受为未来网络的一种启用技术，该技术可以使多个虚拟网络（VNS）具有不同的范式和协议，以在共享基板网络（SN）上共存。 NV中的一个主要挑战是VN嵌入（VNE），它将VN映射到共享SN上。由于VNE是NP-HARD，因此现有的努力主要集中于提出试图在合理时间内实现可行的VNE的启发式算法，因此，由此产生的嵌入并不是最佳的。为了解决这个困难，我们提出了一种候选辅助（CAN-A）最佳VNE算法，其计算复杂性较低。 CAN-A算法的关键思想在于构造候选底物节点子集和候选底物路径子集。这大大减少了映射执行时间而没有绩效损失。在以下嵌入中，在CAN-A算法中考虑了四种类型的节点和链接约束，从而使其更适用于现实的网络。模拟结果表明，与纯VNE-MIP算法相比，CAN-A的执行时间大大减少。 CAN-A还优于其他性能指数（例如平均VN请求接受率和平均虚拟链接传播延迟）的典型启发式算法。
Network virtualization (NV) is widely accepted as one enabling technology for future network, which enables multiple virtual networks (VNs) with different paradigms and protocols to coexist on the shared substrate network (SN). One key challenge in NV is VN embedding (VNE), which maps a VN onto the shared SN. Since VNE is NP-hard, existing efforts mainly focus on proposing heuristic algorithms that try to achieve feasible VNE in reasonable time, consequently the resulted embedding is not optimal. To tackle this difficulty, we propose a candidate assisted (CAN-A) optimal VNE algorithm with lower computational complexity. The key idea of the CAN-A algorithm lies in constructing the candidate substrate node subset and the candidate substrate path subset before embedding. This reduces the mapping execution time substantially without performance loss. In the following embedding, four types of node and link constraints are considered in the CAN-A algorithm, making it more applicable to realistic networks. Simulation results show that the execution time of CAN-A is hugely cut down compared with pure VNE-MIP algorithm. CAN-A also outperforms the typical heuristic algorithms in terms of other performance indices, such as the average VN request acceptance ratio and the average virtual link propagation delay.