Unavailability-Aware Backup Allocation Model for Middleboxes with Two-Stage Shared Protection

Middleboxes work as software which runs on a general-purpose server by adopting a network function virtualization. The unavailability of middlebox is a key metric. The previous study considers allocating backup servers to middleboxes to reduce the unavailability. While it adopts shared protection to save backup capacity, resource sharing has not been sufficiently explored as each middlebox can only use one backup server. This paper presents a backup allocation model in which a function can be protected by two backup servers and a backup server can protect multiple functions under a shared protection strategy to minimize the maximum unavailability among functions. We use Markov chains to analyze the state transitions and make equilibrium-state equations. By solving them, we obtain the probability of each state of the allocation and compute an unavailability of function. We introduce two algorithms to examine the proposed model; one of them uses the performance bound of the maximum unavailability which is analyzed in this paper. Numerical results show that the proposed model reduces the maximum unavailability by 13.9-51.2% compared to a baseline model that allocates one backup server for each middlebox in our examined cases.