In a virtualized infrastructure where physical resources are shared, a single physical server failure will terminate several virtual servers and crippling the virtual infrastructures which contained those virtual servers. In the worst case, more failures may cascade from overloading the remaining servers. To guarantee some level of reliability, each virtual infrastructure, at instantiation, should be augmented with backup virtual nodes and links that have sufficient capacities. This ensures that, when physical failures occur, sufficient computing resources are available and the virtual network topology is preserved. However, in doing so, the utilization of the physical infrastructure may be greatly reduced. This can be circumvented if backup resources are pooled and shared across multiple virtual infrastructures, and intelligently embedded in the physical infrastructure. These techniques can reduce the physical footprint of virtual backups while guaranteeing reliability.
Analysis on the reliability of overlay networks in terms of connectivity in the overlays has been developed @cite_9 . It achieves a good estimation of connectivity in the embedded overlay networks through a Monte Carlo simulation-based algorithm. Unfortunately, it is not applicable to our problem as we are concerned with critical virtual nodes and embedding them, as well as the whole infrastructure with reliability guarantees.
@cite_9
2027480718
We consider network reliability in layered networks where the lower layer experiences random link failures. In layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. We generalize the classical polynomial expression for network reliability to the multilayer setting. Using random sampling techniques, we develop polynomial-time approximation algorithms for the failure polynomial. Our approach gives an approximate expression for reliability as a function of the link failure probability, eliminating the need to resample for different values of the failure probability. Furthermore, it gives insight on how the routings of the logical topology on the physical topology impact network reliability. We show that maximizing the min cut of the (layered) network maximizes reliability in the low-failure-probability regime. Based on this observation, we develop algorithms for routing the logical topology to maximize reliability.