This paper proposes a backup resource allocation model for virtual network functions (VNFs) to minimize the total allocated computing capacity for backup with considering the service delay. If failures occur to primary hosts, the VNFs in failed hosts are recovered by backup hosts whose allocation is pre-determined. We introduce probabilistic protection, where the probability that the protection by a backup host fails is limited within a given value; it allows backup resource sharing to reduce the total allocated computing capacity. The previous work does not consider the service delay constraint in the backup resource allocation problem. The proposed model considers that the probability that the service delay, which consists of networking delay between hosts and processing delay in each VNF, exceeds its threshold is constrained within a given value. We introduce a basic algorithm to solve our formulated delay-constraint optimization problem. In a problem with the size that cannot be solved within an acceptable computation time limit by the basic algorithm, we develop a simulated annealing algorithm incorporating Yen's algorithm to handle the delay constraint heuristically. We observe that both algorithms in the proposed model reduce the total allocated computing capacity by up to 56.3% compared to a baseline; the simulated annealing algorithm can get feasible solutions in problems where the basic algorithm cannot.

This paper proposes a virtual network function (VNF) placement model considering both availability and probabilistic protection for the service delay to minimize the service deployment cost. Both availability and service delay are key requirements of services; a service provider handles the VNF placement problem with the goal of minimizing the service deployment cost while meeting these and other requirements. The previous works do not consider the delay of each route which the service can take when considering both availability and delay in the VNF placement problem; only the maximum delay was considered. We introduce probabilistic protection for service delay to minimize the service deployment cost with availability. The proposed model considers that the probability that the service delay, which consists of networking delay between hosts and processing delay in each VNF, exceeds its threshold is constrained within a given value; it also considers that the availability is constrained within a given value. We develop a two-stage heuristic algorithm to solve the VNF placement problem; it decides primary VNF placement by solving mixed-integer second-order cone programming in the first stage and backup VNF placement in the second stage. We observe that the proposed model reduces the service deployment cost compared to a baseline that considers the maximum delay by up to 12%, and that it obtains a feasible solution while the baseline does not in some examined situations.