Network Function Virtualization in Elastic Optical Networks

In Network Function Virtualization (NFV), traditional purpose-built proprietary middle-boxes are replaced with virtual network function (VNF) instances that are deployed over generic hardware; network traffic flows are steered through a sequence of VNF instances (i.e., that forms a service function chain) after resolving the VNF Forward Graph Embedding (FGE) problem. NFV eases the network management and fosters the agile deployment of network services, thus enabling a foremost solution to address issues of traditional enterprise networks. With the everlasting Internet traffic growth, in this work, we extend the provision of NFV upon Elastic Optical Networks (EONs) that deliver abundant elastic and fine-granular bandwidth for connections between VNFs. We systematically examine the integrated NFV-EON architecture, and investigate one key enabler, namely the FGE-EON problem, where one has to coordinate the allocation of computing resources (as in a typical FGE problem) and the assignment of optical bandwidth (i.e., spectrum allocation in EONs). The contributions of this work are multi-fold. The FGE-EON problem is proven to be NP-Complete for the first time. An Integer Linear Programming (ILP) model is developed to address FGE-EON problem of small instances. Despite its complexity, with novel modeling techniques, the proposed ILP model maintains a compact structure even after accounting for VNF sharing and VNF co-location together for the first time. For large scale problems, we design a heuristic algorithm based on layered graph that is shown to be near-optimal in our evaluations.