Multi-layer virtual network embedding

Abstract

Some aspects and embodiments of the present invention provide effective mechanisms for provisioning virtual networks on communication networks. In particular some aspects and embodiments provide an effective mechanism for embedding a virtual network into a multi-layered substrate network which utilizes a different communication technology at each layer. One such example is an IP network overlaid over an optical network, such as an OTN network. Embodiments jointly determine the assignment of virtual nodes and virtual links. Assigning the nodes and links together can provide for a more optimal solution than assigning the nodes and the links separately. Some embodiments generate a collapsed graph which includes the optical network and the IP network in a single layer. Accordingly some embodiments jointly determine the assignment of virtual nodes and virtual links within such a collapsed graph, which can provide more optimal assignments than considering assignments within each layer separately. In some embodiments, generating a collapsed graph includes allocating residual capacity to each link of the collapsed graph; and allocating a cost for each link of the collapsed graph. In some embodiments, allocating a cost for each link includes allocating a higher cost to optical links than to IP links. In some cases, allocating the higher costs can discourage the creation of new links unless they are needed or are beneficial (e.g. creating new links improves the overall cost/efficiency). Some embodiments utilize a heuristic method for solving an optimization function for the placement of virtual nodes and links.