标题：A modified ant colony optimization algorithm for virtual network embedding
作者：Zhu, Fangjin ;Wang, Hua
作者机构：[Zhu, Fangjin ;Wang, Hua ] School of Computer Science and Technology, Shandong University, Jinan, China
来源：Journal of Chemical and Pharmaceutical Research
关键词：Ant colony optimization; Greedy algorithm; Multi-choice knapsack problem; Network virtualization; Virtual network embedding
摘要：Traditional Internet architecture is far too rigid for use with large numbers of network applications with different quality of service requirements. One new and promising approach to overcome the rigidity is network virtualization (NV), which allows multiple heterogeneous virtual networks to coexist on a shared substrate network (SN). However, one of the key problems for NV is the virtual network embedding (VNE) problem, which concerns the efficient mapping of virtual nodes and links to SN nodes and paths. The VNE problem has proven to be nondeterministic polynomial-time hard and approximation algorithms are needed to address it. In this paper, we define the VNE problem based on the multiple-choice knapsack model and propose a modified ant colony optimization algorithm to solve the problem. The combination of revenue and acceptance ratio of an SN is used as an important component when designing the fitness function to evaluate iterative solutions obtained by ants, and pheromone update rules are designed based on the fitness function. The cost of a candidate network is defined as the selection heuristic information. Simulation results show that this algorithm performs well with various numbers of VN requests. The algorithm also provides better optimization performance than existing algorithms. © 2014, Journal of Chemical and Pharmaceutical Research. All rights reserved.