Background: Network Functions Virtualization (NFV) is a paradigm shift in the way
network operators deploy and manage their services. The basic idea behind this new technology is
the separation of network functions from the traditional dedicated hardware by implementing them
as a software that is able to run on top of general-purpose hardware. Thus, the resulting pieces of
software are called Virtual Network Functions (VNFs). NFV is expected, on one hand, to lead to increased
deployment flexibility and agility of network services and, on the other hand, to reduce operating
and capital expenditures. One of the major challenges in NFV adoption is the NFV Infrastructure's
Resource Allocation (NFVI-RA) for the requested VNF-Forwarding Graph (VNF-FG).
This problem is named VNF-forwarding graph mapping problem and is known to be an NP-hard
Objective: To address the VNF-FG mapping problem, the objective is to design a solution that uses
a meta-heuristic method to minimize the mapping cost.
Methods: To cope with this NP-Hard problem, this paper proposes an algorithm based on Greedy
Randomized Adaptive Search Procedure (GRASP), a cost-efficient meta-heuristic algorithm, in
which the main objective is to minimize the mapping cost. Another method named MARA (Most
Available Resource Algorithm) was devised with the objective of reducing the Substrate Network’s
resources use at the bottleneck clusters.
Results: The Performance evaluation is conducted using real and random network topologies to confront
the proposed version of GRASP with another heuristic, existing in the literature, based on the
Viterbi algorithm. The results of these evaluations reveal the efficiency of the proposed GRASP ‘s
version in terms of reducing the cost mapping and performs consistently well across all the evaluations
Conclusion: The problem of VNF-FG mapping is formalized, and a solution based on GRASP meta-
heuristic is proposed. Performance analysis based on simulations are given to show the behavior
and efficiency of this solution.