Shared backup resource assignment for middleboxes

摘要

This paper presents five approaches to solve the problem of finding the optimal backup resource assignment which maximizes the survival probability of network functions of middleboxes. In the previous work, no mathematical model to solve this problem is provided, so we formulate the problem as a mixed-integer linear programming (MILP) problem as the first approach. Formulating this MILP problem includes some special steps, which are not considered in the previous work. The MILP problem is not always solved in a practical time when the problem size becomes large. Then, we develop two heuristic approaches by replacing the objective of the original MILP problem relying on the idea of balancing the failure probabilities of functions of connected components. We develop two heuristic approaches by extending the way of assigning functions and servers from the conventional heuristic algorithm. Numerical results show that our four developed heuristic approaches improve the survival probability from the conventional heuristic algorithm in some cases and reduce computation time compared to obtaining the optimal solution. Furthermore, one of our developed heuristic approaches provides exactly the optimal solution with shorter computation time compared to the time solving the original MILP problem in a special case.