This paper is concerned with the problem of reliability-aware embedding of Virtual Networks (VN), where substrate nodes exhibit heterogeneous and independent failure rates. In this context multiple problems emerge, particularly the concern of estimating the reliability of a VN. Further, a reliable embedding solution may result in a service with over-provisioned reliability (hence waste of network resources). We solve the problem of estimating a VN's reliability by introducing the concept of “protection-domains”. Further, we mathematically formulate the problem of reliability-aware VN embedding with “just-enough reliability provisioning”. Due to the complex nature of the model, we introduce CORNER: COst-Efficient and Reliability-Aware Virtual NEtwork Redesign and Embedding heuristic. CORNER is capable of achieving an embedding solution that both satisfies the reliability requirement of the VN without depletion, while reducing the cost across the network.