Progressive Slice Recovery With Guaranteed Slice Connectivity After Massive Failures

In presence of multiple failures affecting their network infrastructure, operators are faced with the Progressive Network Recovery (PNR) problem, i.e., deciding the best sequence of repairs during recovery. With incoming deployments of 5G networks, PNR must evolve to incorporate new recovery opportunities offered by network slicing. In this study, we introduce the new problem of Progressive Slice Recovery (PSR), which is addressed with eight different strategies, i.e., allowing or not to change slice embedding during the recovery, and/or by enforcing different versions of slice connectivity (i.e., network vs. content connectivity). We propose a comprehensive PSR scheme, which can be applied to all recovery strategies and achieves fast recovery of slices. We first prove the PSR's NP-hardness and design an integer linear programming (ILP) model, which can obtain the best recovery sequence and is extensible for all the recovery strategies. Then, to address scalability issues of the ILP model, we devise an efficient two-phases progressive slice recovery (2-phase PSR) meta-heuristic algorithm, small optimality gap, consisting of two main steps: i) determination of recovery sequence, achieved through a linear-programming relaxation that works in polynomial time; and ii) slice-embedding recovery, for which we design an auxiliary-graph-based column generation to re-embed failed slice nodes/links to working substrate elements within a given number of actions. Numerical results compare the different strategies and validate that amount of recovered slices can be improved up to 50% if operators decide to reconfigure only few slice nodes and guarantee content connectivity.