Virtual infrastructure design for surviving physical link failures

With the increasingly popular virtualization of both computing and networking resources in a distributed system (called a physical substrate), multiple virtual infrastructures (VIs) can share the physical resources of the underlying substrate, and accordingly even a single failure in the substrate can affect a large number of VIs and the services they offer. Thus, the problem of efficiently mapping a VI to a substrate while guaranteeing the VI's survivability in the event of failures in the substrate becomes important. In this paper, we study the survivable VI mapping problem to protect against link failures in the substrate. We first propose a solution based on traditional shared protection (survivable virtual infrastructure mapping algorithm, P-SVIMA), and then propose a novel VI node migration protection-based algorithm (MP-SVIMA) to minimize the computing and communication resource costs. The MP-SVIMA scheme takes advantage of the flexibility in where VI nodes are mapped in the substrate by migrating a VI node from the originally mapped physical location to a different location after a physical link fails in order to recover from link failures. We compare the efficiency of our solutions using simulations under various performance metrics.