Premium
A unified enhanced particle swarm optimization‐based virtual network embedding algorithm
Author(s) -
Zhang Zhongbao,
Cheng Xiang,
Su Sen,
Wang Yiwen,
Shuang Kai,
Luo Yan
Publication year - 2013
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.1399
Subject(s) - computer science , embedding , shortest path problem , particle swarm optimization , mathematical optimization , node (physics) , network virtualization , integer programming , convergence (economics) , context (archaeology) , algorithm , virtual network , greedy algorithm , path (computing) , linear programming , distributed computing , theoretical computer science , virtualization , mathematics , artificial intelligence , computer network , engineering , cloud computing , graph , paleontology , structural engineering , economics , biology , economic growth , operating system
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.