1. A method for embedding a virtual network definition defining a virtual network comprising a plurality of virtual nodes and a plurality of virtual links on a physical network, the method comprising: determining a conflicting set for each virtual link of the virtual network definition, each conflicting set comprising a plurality of virtual links of the virtual network that must be embedded on disjoint paths in the physical network to maintain connectivity of the virtual network in the presence of k physical link failures; and embedding the virtual network onto the physical network so that each of the plurality virtual links in each conflicting set are embedded on disjoint paths of the physical network.