A modified ACO algorithm for virtual network embedding based on graph decomposition

Network virtualization is a promising scheme to solve Internet ossification. A challenging problem in this scheme is virtual network embedding (VNE), which involves efficiently embedding multiple heterogeneous virtual networks into one or more physical networks. The VNE problem is known to be NP-hard and thus requires an approximate algorithm as a solution. This study models the VNE problem based on virtual network topology invariance and analyzes the shortcomings of a general embedding algorithm under different network topologies. A modified ant colony optimization algorithm is proposed based on network topology decomposition. A pre-computation algorithm is first proposed based on ant random walking to accelerate the recognition of the ring characteristics of a network topology. Pre-computation results are used to guide the decomposition of virtual networks and the embedding process of ring structures. The topology of a virtual network is decomposed into a combination of ring structures and tree structures, which have different characteristics. Different embedding algorithms are then designed for these structures. Point-disjoint paths are searched for any two virtual links to ensure the reliability of the network topology in the embedding process. The proposed algorithm shows an enhanced optimization performance, which is better than those of the ViNE-LB and GN-SP algorithms.