A unified enhanced particle swarm optimization‐based virtual network embedding algorithm. (27th January 2012)

• Record Type: Journal Article
• Authors: Zhang, Zhongbao; Cheng, Xiang; Su, Sen; Wang, Yiwen; Shuang, Kai; Luo, Yan
• Is Part Of: International journal of communication systems. Volume 26:Number 8(2013:Aug.)
• Page Start: 1054
• Page End: 1073
• Publication Date: 2012-01-27
• Subjects: network virtualization -- virtual network embedding -- integer linear programming -- mixed integer programming -- metaheuristic -- particle swarm optimization; Telecommunication systems -- Periodicals; 621.382
• DOI: 10.1002/dac.1399
• Languages: English
• ISSNs: 1074-5351

Abstract

SUMMARY: Virtual network (VN) embedding is a major challenge in network virtualization. In this paper, we aim to increase the acceptance ratio of VNs and the revenue of infrastructure providers by optimizing VN embedding costs. We first establish two models for VN embedding: an integer linear programming model for a substrate network that does not support path splitting and a mixed integer programming model when path splitting is supported. Then we propose a unified enhanced particle swarm optimization‐based VN embedding algorithm, called VNE‐UEPSO, to solve these two models irrespective of the support for path splitting. In VNE‐UEPSO, the parameters and operations of the particles are well redefined according to the VN embedding context. To reduce the time complexity of the link mapping stage, we use shortest path algorithm for link mapping when path splitting is unsupported and propose greedy k‐shortest paths algorithm for the other case. Furthermore, a large to large and small to small preferred node mapping strategy is proposed to achieve better convergence and load balance of the substrate network. The simulation results show that our algorithm significantly outperforms previous approaches in terms of the VN acceptance ratio and long‐term average revenue. Copyright © 2012 John Wiley & Sons, Ltd. Abstract : In this paper, we first establish an integer linear programming model and a mixed integer programming model for the virtual network (VN) embedding problem when path splitting is unsupported and supported by the substrate network, respectively. To solve these two models, we then propose a unified enhanced particle swarm optimization‐based VN embedding algorithm, called VNE‐UEPSO. The simulation results show that our algorithm significantly outperforms previous approaches in terms of VN embedding cost, VN acceptance ratio and long‐term average revenue.