Virtual network embedding algorithm for one-to-one site protection

Network redundancy and protection have become an even more serious issue after the last tsunami in Japan. Future networks need to be planned and operated keeping such unprecedented failures in mind. In this regard, we consider Virtual Network Embedding (VNE) techniques as an useful tool to realize an optimization between redundancy and resource consumption. However, conventional VNEs mostly concentrate on single network embedding. As VNE is a computationally intractable problem, relaxation methods are often used to offer a workable polynomial time solution. Some of such relaxation methods like flow-splitting do not fit well in real network operation. In this paper, we propose a heuristic VNE algorithm for network site protection without flow splitting. We also provide a solution with joint site and link embedding to achieve better bandwidth consumption. Evaluation results show that our VNE algorithm performs close to theoretical thresholds and consumes less link resources in delivering a VNE solution in polynomial time compared to the conventional algorithm.