  Network function virtualization (NFV) enables on-demand network function (NF)
deployment providing agile and dynamic network services. Through an evaluation
metric that quantifies the minimal reliability among all NFs for all demands,
service providers and operators may better facilitate flexible NF service
recovery and migration, thus offer higher service reliability. In this paper,
we present evaluation metrics on NFV reliability and solution approaches to
solve robust NFV under random NF-enabled node failure(s). We demonstrate how to
construct an auxiliary NF-enabled network and its mapping onto the physical
substrate network. With constructed NF-enabled network, we develop
pseudo-polynomial algorithms to solve the robust NF and SFC $s-t$ path problems
-- subproblems of robust NFV. We also present approximation algorithms for
robust NFV with the SFC-Fork as the NF forwarding graph. Furthermore, we
propose exact solution approaches via mixed-integer linear programming (MILP)
under the general setting. Computational results show that our proposed
solution approaches are capable of managing robust NFV in a large-size network.
