Designing Optimal Middlebox Recovery Schemes with Performance Guarantees

Enabling functionality in modern network is achieved through the use of middleboxes. Middleboxes suffer from temporal unavailability due to various reasons, such as hardware faults. We design a backup scheme that takes advantage of Network Function Virtualization (NFV), an emerging paradigm of implementing network functions in software, deployed on commodity servers. We utilize the agility of software-based systems, and the gap between the resource utilization of active and standby components, in order to design an optimal limited-resource backup scheme. We focus on the case where a small number of middleboxes fail simultaneously, and study the backup resources required for guaranteeing full recovery from any set of failures, up to a required small number thereof, under varying capacity assumptions. Via a novel graph-based presentation, we develop a provably optimal construction of such backup schemes. Since full recovery is guaranteed, our construction does not rely on failure statistics, which are typically hard to obtain. Simulation results show that even for the case of larger numbers of failures, our proposed approach is applicable, and superior to known approaches.