Survivable virtual infrastructure mapping in a federated computing and networking system under single regional failures

As virtualization becomes more and more popular, how to guarantee survivability of a virtual infrastructure (VI) over a wide-area optical network is increasingly important. In this paper, we approach the problem of survivable VI mapping (SVIM) from a few unique perspectives. One of the most distinguishing perspectives is that a large-scale regional failure could destroy one or more facility nodes to which some VI nodes are mapped. Accordingly, redundant facility nodes at different geographical locations and redundant optical connections have to be provisioned such that the VI can still be mapped after the failure. Another distinguishing perspective is that with failure-dependent protection, the SVIM problem can be decomposed into several instances of the basic non-survivable VI mapping (NSVIM) problem, whose solution permits effective sharing of the redundant resources among all failures. In this paper, we first formulate the minimum-cost SVIM problem using mixed integer linear programming (MILP). We then propose an efficient heuristic solution to NSVIM, based on which two novel heuristic SVIM algorithms called Separate Optimization with Unconstrained Mapping (SOUM) and Incremental Optimization with Constrained Mapping (IOCM). Simulations are performed to study and compare the performance of the MILP and heuristics.