Enhanced Reinforcement Learning
Approach for VNF-FG Embedding

Related work

 The need to dynamically deploy virtualized network services on-demand, through VNFFG embedding, is identified as the core technology of 5G networks. Therefore, this issue has been at the very center of academic and industrial research in recent years. Here, we give a summary of the use of Reinforcement Learning in networking and especially in the VNF-FG embedding domain. Since the VNF-FG embedding problem can be well described as a Markov decision process (MDP), then Reinforcement Learning (RL) is a good framework to use to find approximate optimal solutions. Recently, some works proposed RL-based approaches for VNF-FG embedding. With RL, an agent learns by interacting with its environment. The agent learns to perform the best action for each state by performing actions and observing the rewards. Given enough observations, an optimal policy can be learned. Thus, the training data in reinforcement learning is a set of state-action-rewards. Authors in [114] map the VNF-FG in two stages: node mapping stage then link mapping stage. They propose two algorithms for link mapping, based on a Multi-Commodity Flow approach and a shortest-path approach. Regarding the node mapping, the authors propose an MDP-based approach. Consequently, this approach is time consuming and not adapted for real-time embedding. In [115], authors propose a multi-agent-based reinforcement learning approach for virtual network embedding. These agents evaluate the feedback to learn the best policy to adopt in order to optimally allocate the required resources to the virtual nodes and links. In [116], authors propose a deep reinforcement learning-based approach for multi-domain VNF-FG embedding. Authors in [117] tackle the SFC allocation problem and present a learning method that places VNFs on an appropriate node that maximizes the performance of VNFs according to the load condition of the physical network. However, this method takes a huge amount of time to converge under an extensive exploration space. In [118], authors propose an RL-based algorithm to solve the NP-hard VNF scheduling problem. In some existing studies, the reinforcement learning is also used for VNF migration [78], [77], [119], and scaling [79], [72] problem under dynamic network load. Furthermore, the large action space, when selecting which VNF instance to migrate, leads to high complexity and poor convergence performance. To the best of our knowledge, we are the first to propose an enhanced RL-based approach combined with an expert knowledge mechanism to avoid a lengthy training process for VNF-FG placement and chaining.

Problem Description 

The VNF-FG embedding optimization problem, extensively addressed in the literature, corresponds to the placement of the requested VNFs and flow paths in the hosting infrastructure.

Substrate Graph or NFV Infrastructure

 Deriving an ILP formulation of the VNF-FG placement problem requires a mathematical graph representation of the service graph (SFC or VNF-FG) and the hosting infrastructure. The physical infrastructure, as defined by the ETSI NFV Infrastructure (NFV-I) in [83], is modeled as an undirected weighted graph Gp = (Np, Ep) where Ep is the set of physical links and Np is the set of physical nodes. Each substrate node, k ∈ Np, is characterized by its i) available processing capacity CP Uk (this can be easily extended to other types of resources: such as storage or memory capacity), and ii) type Tk: switch, server or Physical Network Function (PNF). The PNFs are the traditional physical middleboxes implementing network functions. Each physical link (i.e., e ∈ Ep) is characterized by its available bandwidth BWe. An example of such an infrastructure, known as the NFV-I, including two PNFs and two switches (serving the ingress and egress flows in the VNF-FG topologies) and some interconnected servers is presented in Figure 5.1.

 VNF Forwarding Graph or SFC Graph 

The client request (i.e., a requested SFC) is modeled as a directed graph Gv = (Nv, Ev) where Nv is the set of virtual nodes and Ev is the set of virtual links in the requested graph. Each virtual node, i ∈ Nv, is characterized by its i) required processing power cpui and ii) its type ti : VNF or switch (i.e., ingress or egress). Each virtual link eij ∈ Ev is described by its required bandwidth bweij . Note that we can also consider instead the end to end latency if this is the criterion to be taken into account. Our model is generic and can be adjusted based on the client criteria and requirements. As specified by the SFC IETF working groups [94], we associate a VNF-type to each VNF to represent the network service or function type (e.g., firewall, NAT, etc.). The VNFs can be hosted only by servers or PNFs having the same type. The ingress and egress nodes can be hosted only by switches. Figure 5.1 depicts two Network Forwarding Paths (NFP). Each Forwarding Path NFP describes the ordered VNF sequence the traffic must pass through. From the VNF forwarding graph Gv, we derive an intermediate request graph called the Network Connectivity Topology graph NCTv. The NCTv = (Nv, Ev) is a weighted undirected graph having exactly the same set of nodes and edges than Gv. The key attribute an NCT node i ∈ Nv is its requested processing capacity cpui . The weight (or requested bandwidth bweij ) of an NCT virtual link eij ∈ Ev is the sum of the requested bandwidths of all the VNF flows passing through it. 

 VNF-FG placement and chaining

 Figure 5.2 depicts a placement solution for the VNF forwarding graph (VNF-FG) highlighted by the dashed lines, starting from the ingress switch 1, crossing the VNF 1, VNF 2, and VNF 3 (hosted respectively in Server 1, PNF 1, and Server 2), and ending at the egress switch 2. The infrastructure providers can map the VNFs using multiple objectives: such as minimizing mapping costs [120], maximizing acceptance ratios and improving provider gains, and improving energy efficiency .