NFV Resource Allocation: a Systematic Review and Taxonomy of VNF Forwarding Graph Embedding

The emergence of Network Functions Virtualisation (NFV) is drastically reshaping the arrangement of network functions. Instead of being built on dedicated hardware (network appliances), network functions are now implemented as software components that run on top of general purpose hardware through virtualisation, namely virtualised network functions (VNFs). From this paradigm-shifting technology arise two problems: (i) how to place VNFs in an NFV-enabled network; and (ii) how to chain these VNFs. These problems are jointly referred to as the VNF forwarding graph embedding (VNF-FGE) problem. Having efficient solutions to the VNF-FGE problem is key to the success of NFV because placing and chaining VNFs automatically and efficiently reduces network and computing resources, thus reducing capital expenditure (CAPEX) and operating expenditure (OPEX). In this work, we systematically review the literature on the VNF-FGE problem. We present a novel taxonomy for the classification and study of proposed solutions to this problem. Research challenges that remain unaddressed are also discussed, providing recommendations for future work.