A heuristic survivable virtual network mapping algorithm

Network virtualization is a promising solution to attack Internet ossification. Virtual network mapping (or embedding) problem is the core of it and is proved to be NP-hard. In this paper, virtual network mapping problem with survivability is formulated and solved with a heuristic algorithm. Firstly, network link resources are divided into primary flow resources and secondary flow resources. The former are used under normal network operation, whereas the latter are used as backup resources once the networks fail. Secondly, we introduce a novel metric named global resource capacity (GRC) which is recently proposed for measuring node mapping capacity to improve network load balance. At last, a heuristic survivable virtual network embedding algorithm (GRC-SVNE) is proposed. In node mapping phase, we calculate the mapping capacity of all nodes and then some nodes are selected as candidate nodes for virtual network embedding and the goal is to improve mapping successful ratio. After that, link mapping is performed with Dijkstra algorithm. Simulation results show that GRC-SVNE outperforms the traditional greedy algorithm (GREEDY), randomized algorithm (R-ViNE) as well as deterministic algorithm (D-ViNE) and demonstrates desirable results in terms of acceptance ratio, network load balance and network revenue.