A method for failure recovery in a virtual network environment including a virtual network having virtual nodes and virtual links mapped onto substrate nodes and substrate paths, respectively, of a substrate network, the method comprising, in response to an indication of failure of at least one substrate node in the substrate network: re-mapping a virtual node mapped to a failed substrate node to a selected substrate node other than the failed substrate node; and re-mapping a virtual link mapped to a substrate path that involves the failed substrate node to a substrate path that does not involve the failed substrate node; wherein the re-mapping is carried out to achieve at least one re-mapping objective.