Path Mapping Approach for Network Function Virtualization Resource Allocation with Network Function Decomposition Support

Abstract

Recently, Network Function Virtualization (NFV) and Software Defined Networking (SDN) have attracted many mobile operators. For the flexible deployment of Network Functions (NFs) in an NFV environment, NF decompositions and control/user plane separation have been introduced in the literature. That is to map traditional functions into their corresponding Virtual Network Functions (VNFs). This mapping requires the NFV Resource Allocation (NFV-RA) for multi-path service graphs with a high number of virtual nodes and links, which is a complex NP-hard problem that inherited its complexity from the Virtual Network Embedding (VNE). This paper proposes a new path mapping approach to solving the NFV-RA problem for decomposed Network Service Chains (NSCs). The proposed solution has symmetrically considered optimizing an average embedding cost with an enhancement on average execution time. The proposed approach has been compared to two other existing schemes using 6 and 16 scenarios of short and long simulation runs, respectively. The impact of the number of nodes, links and paths of the service requests on the proposed scheme has been studied by solving more than 122,000 service requests. The proposed Integer Linear Programming (ILP) and heuristic schemes have reduced the execution time up to 39.58% and 6.42% compared to existing ILP and heuristic schemes, respectively. Moreover, the proposed schemes have also reduced the average embedding cost and increased the profit for the service providers.