Multi-Path Link Embedding for Survivability in Virtual Networks

Internet applications are deployed on the same network infrastructure, yet they have diverse performance and functional requirements. The Internet was not originally designed to support the diversity of current applications. Network virtualization enables heterogeneous applications and network architectures to coexist without interference on the same infrastructure. Embedding a virtual network (VN) into a physical network is a fundamental problem in network virtualization. A VN embedding that aims to survive physical (e.g., link) failures is known as the survivable VN embedding (SVNE). A key challenge in the SVNE problem is to ensure VN survivability with minimal resource redundancy. To address this challenge, we propose survivability in multi-path link embedding (SiMPLE). By exploiting path diversity in the physical network, SiMPLE provides guaranteed VN survivability against single link failure while incurring minimal resource redundancy. In case of multiple arbitrary link failures, SiMPLE provides maximal survivability to the VNs. We formulate this problem as an integer linear program and implement it using GNU linear programming kit. We propose a greedy proactive approach to solve larger instances of the problem in case of single link failures. In presence of more than one link failures, we propose a greedy reactive algorithm as an extension to the previous one, which opportunistically recovers the lost bandwidth in the VNs. Simulation results show that SiMPLE outperforms full backup and shared backup schemes for SVNE, and produces near-optimal results.