Combining Deep Reinforcement Learning With Graph Neural

Networks for Optimal VNF Placement

Penghao Sun, Julong Lan, Junfei Li, Zehua Guo, Yuxiang Hu

Abstract—Network Function Virtualization (NFV) technology sequence is known as a Service Function Chain (SFC). As
leverages software to execute network functions as virtual entities, a result, the positioning of VNF instances can significantly
thereby lowering costs associated with various middlebox hard- affect traffic routing within the network, thereby influencing
ware. A Virtual Network Function (VNF) instance necessitates
multiple resource types within the network (e.g., CPU, memory). transmission characteristics such as end-to-end delay. The
Thus, an effective VNF placement strategy must account for VNF placement problem involves addressing both the resource
both resource utilization challenges and the Quality of Service allocation for different types of VNFs and the Quality of
(QoS) of data flows, which has been proven to be NP-hard. Service (QoS) of network traffic, making it a complex issue
Recent research utilizes Deep Reinforcement Learning (DRL) that has been demonstrated to be NP-hard [3], making it
to tackle the VNF placement issue; however, existing DRL-
based approaches struggle to generalize across different network challenging to find an optimal way out in practice.
topologies. In this paper, we propose integrating the strengths of Recently, with the advancement of machine learning tech-
DRL and Graph Neural Networks (GNN) to develop our VNF nologies like Deep Reinforcement Learning (DRL), there
placement approach, DeepOpt. Simulation outcomes indicate that is optimism that DRL-based approaches could provide new
DeepOpt surpasses the current leading VNF placement methods insights into the VNF placement problem. For instance,
and demonstrates significantly better generalization capabilities
across various network topologies. [4] proposes addressing the VNF placement issue using a
Index Terms—Deep Reinforcement Learning, Network Func- DRL algorithm, which outperforms traditional methods due
tion Virtualization, Graph Neural Networks, Software-Defined to DRL’s ability to provide a data-driven explanation that
Networking. does not depend on human expertise or manually crafted
models. However, current DRL-based approaches, such as
I. I NTRODUCTION
the one presented in [4], often employ basic neural network
Internet Service Providers (ISPs) depend on multifarious architectures (e.g., feedforward neural networks) that lack
Network Functions (NFs) to manage and deliver services for strong generalization across varying network topologies. In
distinct traffic flows. Traditionally, NFs have been finished as contrast, Graph Neural Network (GNN)-based methods offer
dedicated middlebox hardware, which means that deploying superior generalization and enhanced capability in inferring
a new middlebox function or altering the network topol- relationships among network nodes, demonstrating significant
ogy typically involves high Capital Expenses (CAPEX) or potential for addressing networking challenges [5].
Operating Expenses (OPEX) [1]. Recently, the advancement In this paper, we introduce a VNF placement approach
of Network Function Virtualization (NFV) technology has called DeepOpt, which integrates DRL with GNN. Deep-
allowed NFs to be implemented via software [2]. Within NFV, Opt leverages a GNN to analyze network topology informa-
the functionality of software-based NFs (such as Firewalls, tion—such as resource types, node resource capacities, and
Deep Packet Inspection, and Intrusion Detection Systems) is link capacities—and utilizes a DRL framework to optimize
referred to as a Virtual Network Function (VNF), which can the GNN parameters through interactions with a simulated
be executed on Virtual Machines (VMs) [2]. network environment.
NFV enables flexible deployment of network functions,
but it introduces a new challenge in determining the optimal II. PROBLEM ANALYSIS
placement of VNF instances. Typically, network traffic must We model an NFV-enabled network using a graph G =
pass through a sequence of network functions in a specific (V ,E,M ), where each node v ∈ V has processing capacity
order to meet particular service requirements; this ordered C v proc and storage capacity C memv , each link e ∈ E has
“Penghao Sun, Julong Lan, Junfei Li, and Yuxiang Hu are affiliated with the bandwidth C bwe , and each m ∈ M represents a type
the Department of Computer Science, National Digital Switching System En- of VNF function. Additionally, we use de, dv and dm to
gineering & Technological Research and Development Center, China. Zehua refer the transmission delay on link e, the processing delay at
Guo is associated with the Beijing Institute of Technology. This research is routing node v and the processing delay of VNF instance m,
funded by the National Key Research and Development Program under Grant respectively. Specifically, in the NFV-enabled network, some
Number 2020YFB1804803, the National Natural Science Foundation of China routing nodes lack Virtual Machines (VMs), resulting in the
under Grant Numbers 61521003, the Beijing Institute of Technology Research C v proc and C mem
v values of zero for these nodes. At any time
Fund Program for Young Scholars, and PCL Future Greater Bay Area Network t, we denote the network flows as the flow set F t. For each
Facilities for Large-scale Experiments and Applications (LZC0019)”. flow f ∈ F t that needs to be transmitted and processed in
the network, we refer the storage resource requirement of this
flow as rscmem
f and the bandwidth requirement as rscbwf . We
use binary indicators nvf and nef to indicate whether flow f
passes through node v and edge e , respectively. Additionally,
we use the binary indicator nvf,m to show whether flow f is
processed by VNF m on node v and the constant rscproc f,m to
represent the processing resource consumption of flow f on
VNF m.
Using the definitions provided, for ∀v ∈ V , ∀e ∈ E and
∀m ∈ M , the resource constraints can be expressed as:
X
rscbw e bw
f n ≤ Ce (1)
b∈F t
X
rscmem
f nvf ≤ Cemem (2)
b∈F t
X
rscproc v proc
f,m nf,m ≤ Cv (3) Fig. 1. The architecture of DeepOpt
b∈F t

To guarantee the Quality of Service (QoS) for each flow,

the total delay of flow f in the network must not surpass its B. DRL FrameworkS
delay limit Df . Hence, for all flows f ∈ Ft , the end-to-end In our DRL framework, a Markov Decision Process (MDP)
delay constraint can be defined as: models the interaction between the DRL algorithm (also
X X X X referred to as the DRL agent) and the network environment.
de nef dv nvf dm nvf,m ≤ Df (4) The MDP is described by (S, A, R), where S represents the
e∈E v∈V v∈V m∈M observation space of the state s of the network environment, A
For a VNF placement strategy ψ that meets the constraints denotes the action space of the DRL action a and R indicates
(1)-(4) for all flows in the network, the expense of implement- the reward space of the reward value r. At each time step t,
ing this strategy can be represented as Cost(ψ). The collection the DRL agent perceives a state st from the environment. The
of all viable VNF placement strategies can be denoted by Ψ = DRL agent’s neural networks then generate an action at based
{ψ1, ψ2, ..., }. Our objective is to identify a VNF placement on st as the input. The action at (i.e., a VNF placement policy
strategy ψ∗ that minimizes the deployment cost: in DeepOpt) is executed within the environment, resulting in a
change in the state of the environment. Additionally, the action
Cost(ψ∗) = minCost(ψi)|ψi ∈ Ψ (5) at is assessed using the environment’s parameters, producing
a reward value rt based on the assessment. Using rt ,the DRL
III. DESIGN OF DEEPOPT agent will update the parameters of the neural networks and
In this section, we present the design of DeepOpt, encom- aim to maximize
PT the cumulative reward over a period T:
passing its architecture, the DRL framework, and the neural Repisode = t=0 γrt .
network implementation. In DRL, the policy for action generation is defined by
deep neural networks within the DRL agent, represented as
A. Architecture of DeepOpt π( at |st ). Since varying neural network parameters θ result
The overall framework of DeepOpt is illustrated in Fig. 1. in different action generation policies, the policy π( at |st )
DeepOpt operates on an SDN-enabled network and employs in the DRL agent can be further specified as π θ ( at |st ).
a DRL framework to formulate a VNF instance placement The training of the DRL agent essentially involves adjusting
strategy. Specifically, to determine a VNF location action, the the neural network parameters θ. In DeepOpt, we utilize the
SDN controller must gather the network information (Input REINFORCE method [6] to update θ.
Attributes) as state data (refer to Section III.D) for the DRL
agent. The DRL agent then uses GNN-based neural networks C. Neural Networks based on GNN
to process this state information and generate an action. This The network information is conveyed through the network
action specifies a set of network nodes for VNF placement (see topology. Unlike Euclidean data such as 2D images or 1D
Section III.D). The action is then converted into a specific VNF sequences, network topology information is organized as graph
placement policy ψ by the SDN controller and subsequently data. To efficiently handle this type of data, we employ Graph
implemented in the network. Once a policy ψ is deployed, Neural Networks (GNN) in DeepOpt as the neural network
performance metrics (e.g., Cost(ψ)) are collected to compute framework within the DRL system. The components (i.e.,
the reward value for the DRL agent, which is used to adjust nodes and edges) in GNNs acquire specific information pro-
the parameters of the DRL agent. cessing methods through interactions with neighboring compo-
nents, which are independent of the input format. This attribute configure the output dimension of each node in the GN block
grants GNNs superior generalization capabilities compared to consist of two neurons (with these neurons representing
to other neural networks. In particular, we utilize the Graph whether the node is utilized or not) and apply a softmax
Network (GN) [7] from the GNN family as the neural network function to select one neuron for the final action. For the
architecture. In GN, the input is symbolized as a directed graph selected nodes, we employ the same method to establish the
referred to as the GN block. The GN block consists of three VNF instances in the network as described in [4]..
types of elements: nodes, edges, and global attributes. Reward: The reward value for P a placement ψ is calculated
as rψ = −Cos(ψ) − penalty − β f delay(f ). The penalty
is assigned a large positive constant if the constraints (1)-(4)
for all flows are not met and is set to zero otherwise. The term
delay(f ) refers to the end-to-end delay of flow f and b is a
weight factor for delay(f ) . The Cost(ψ) is determined based
on the total resources utilized by all VNF instances.
The training procedure for DeepOpt is presented in Algo-
rithm 1.
Fig. 2. The calculation process of the GN block in DeepOpt

For each node, there is a node attribute vector attr_v that

defines the properties of that node; for each edge, there is an
edge attribute attr_e that specifies the properties of that edge;
and global attributes are described by a vector that conveys
the overall information of the graph. In DeepOpt, we simplify
by omitting the implementation of global attributes, as it does
not provide additional benefits based on our tests. There are
two update functions ϕe and ϕv and one aggregation functions
ρe→v , which operate on the node and edge attributes. The
operations are performed as follows:
1) attr_ek ' = ϕe (attr_ek , attr_vrk , attr_vsk ) is computed
for each edge, representing a specific type of edge in-
formation, where rk /sk denote the receiving and sending
node of edge k, respectively.
2) agge_ei ' = pe→v (Ei ') consolidates the edge information
and integrates it with the node information, where Ei '=
IV. SIMULATION
{(attr_ek ' ,rk , sk )}rk =i,k=1:|E| .
3) attr_vi ' = ϕv (aggr_ei ', attr_vi )is performed for each A. Simulation Environment
node, which computes a form of node-specific informa-
To evaluate the performance of DeepOpt, we create a sim-
tion.
ulation environment using the ns3gym tool [8]. Ns3gym is an
Fig. 2 illustrates the computation process of the GN block in
adaptation of NS3 for network simulation with reinforcement
DeepOpt.
learning-based policies, adhering to the standard interfaces for
D. Interface Design reinforcement learning test environments. We implement our
In this section, we outline the interfaces and training DRL algorithm using TensorFlow 1.12. The entire simulation
specifics of DeepOpt. The key interfaces between the DRL is conducted on a computer equipped with an Intel Core i7-
algorithm and the network environment comprise state, action, 7700 CPU, 32GB DDR4 RAM, and a GTX 1080Ti Graphics
and reward, which are defined as follows: card.
State: The state information includes the input of node The topology of the reproduction network is based on the
attributes and edge attributes. Specifically, DeepOpt employs TOTEM project [9], comprising 23 nodes and 37 links. We
the ratio of processing resource usage and storage space utilize the Google cluster traces [10] to define the traffic
utilization ratio for each network node as the input node demands in our reproduction network. The jobs in the Google
attributes, while the bandwidth application ratio and delay cluster traces, which include multiple tasks with specific re-
for each network link are used as the input edge features. source requirements, are formatted similarly to SFC requests.
Additionally, we reserve three empty positions in each attribute Consequently, we convert these jobs into SFC requests for per-
vector for the potential inclusion of additional input data in the formance comparison, as done in [4]. In our reproduction, each
future. SFC request necessitates three VNF instances for processing.
Action: The action value is represented by a binary list The following methods serve as the baseline for our simu-
that indicates the selection status of each network node. We lation.
 DDQN-VNFPA [4]: DDQN-VNFPA is an advanced method resources based on an aggregate of SFC requests over a period.
utilizing Deep Reinforcement Learning (DRL). DRL-based ap- These methods only ensure resource allocation based on the
proaches can automatically discover optimal solutions without average resource requirements during this period. However, at
requiring human expertise or labeled training data. However, a more granular time scale, network traffic fluctuations may
these methods encounter the challenge of exploring a vast cause some flows to receive suboptimal resource allocation at
action space, which represents the various combinations of certain times (e.g., during peak traffic).
VNF instance locations in the network. DDQN-VNFPA ad- Influence of Topology Change: In practice, network topol-
dresses this issue by dividing the network into several regions, ogy can evolve due to node failures or the addition of new
thereby mitigating the scalability problem associated with nodes. Thus, a VNF placement scheme must adapt to these
applying DRL to the VNF placement problem. Nonetheless, topology changes and demonstrate performance adaptability.
this approach employs feedforward neural networks within We assess the robustness of various schemes against random
the DRL algorithm to process the network state, which limits topology alterations (e.g., node failures or the addition of new
its ability to accurately capture network topology information nodes) by randomly selecting nodes for removal and adding
and reduces its generalization capability when the network new nodes to the original topology. For node addition, we
topology changes. incorporate nodes one at a time. To add a node, we first
MSGAS [11]:MSGAS aims to reduce the number of poten- randomly select an existing node to which the new node will
tial VNF placement locations to efficiently generate a VNF connect, then choose one of the adjacent nodes of the selected
placement policy. It introduces the concept of "accessible node to further connect the new node, thereby enhancing
scope," which refers to a set of potentially suitable positions the new node’s connectivity. For node deletion, we randomly
for VNF instances. By narrowing the search space for VNF select a node and its associated links for removal from the
placement, the accessible scope enhances scalability in large topology. It is important to note that we avoid deleting nodes
networks. However, this approach may compromise the accu- that would divide the topology into disconnected subgraphs,
racy of the VNF placement policy, as some optimal locations in order to preserve the network’s fundamental connectivity.
for VNF instances might be excluded from the accessible Fig.4 illustrates the performance variation (measured by
scope. the rejection ratio of SFC requests) of different schemes
Eigendecomposition [12]:Eigendecomposition utilizes in the modified topology. In this figure, a value of 0 on
matrix-based methods to address the VNF placement problem. the x-axis represents the original topology, serving as the
Specifically, it applies Umeyama’s eigendecomposition to baseline for performance (i.e., no change in performance). As
determine the optimal matching between VNF instances observed, DDQN-VNFPA experiences significant performance
and their placements within the network. This matrix- degradation under topology changes. This is primarily because
based approach strikes a balance between performance and the neural networks in DDQN-VNFPA struggle to adapt to the
computational efficiency. However, Eigendecomposition new topology states. In contrast, DeepOpt maintains relatively
involves several operations that may affect the accuracy of stable performance, as the GNN in DeepOpt demonstrates
the VNF placement policy. For instance, the method includes strong generalization across various topologies. The perfor-
matrix reshaping operations (e.g., expanding the adjacency mance of MSGAS and Eigendecomposition shows minimal
matrix of SFC requests to match the size of the network’s degradation, as these methods utilize traditional algorithms
adjacency matrix) and heuristic algorithms tailored to its that are not influenced by network topologies. Nonetheless,
specific characteristics (e.g., using a widest-shortest path DeepOpt outperforms MSGAS and Eigendecomposition sig-
algorithm to assign weight values to elements in the network nificantly, given that the fundamental performance of the latter
topology). These processes can introduce errors into the two schemes is inherently inferior (as shown in Fig. 3).
scheme. Time Consumption: Training for DRL-based schemes is
typically conducted offline. In our evaluation, the testing
B. Evaluation and Analysis platform consists of an Intel Core i7-7700 CPU, 32GB DDR4
The Reject Ratio of SFC Requests: Different VNF place- RAM, and a GTX 1080Ti Graphics card, with DeepOpt
ment schemes can result in varying rejection rates for SFC requiring approximately 5 hours for training. Once training
requests due to competition for resources. This is because is complete, DRL-based schemes compute VNF placement
different schemes lead to different levels of resource utiliza- solutions significantly faster than other methods. To assess the
tion, given the limited processing, storage, and bandwidth computational efficiency of various schemes, we conducted an
resources. Figure 3 illustrates the rejection ratio of all SFC experiment measuring the time required to place 50 service
requests in the network. It shows that DeepOpt achieves function chain requests. The results are illustrated in Figure 5.
the lowest rejection ratio (0.22%), outperforming DDQN- As depicted, DeepOpt requires only 2.1% of the computation
VNFPA (0.35%), MSGAS (15%), and Eigendecomposition time needed by MSGAS, 2.7% of that used by Eigendecompo-
(53%) in our test scenario. The performance of DeepOpt and sition, and just 5.3% more than DDQN-VNFPA. MSGAS and
DDQN-VNFPA is significantly better than that of MSGAS and Eigendecomposition have longer computation times due to the
Eigendecomposition. This is primarily because MSGAS and multiple steps involved in MSGAS, including the selection of
Eigendecomposition perform their computations and allocate accessible scopes, chaining VNF instances, and cost analysis,
and the matrix calculations performed by Eigendecomposition
for each service function chain request. Both DDQN-VNFPA
and DeepOpt use DRL for model training and share similar
calculation processes. However, DeepOpt, while outperform-
ing DDQN-VNFPA, requires slightly more computation time
because the GNN used in DeepOpt has higher computational
complexity compared to the feedforward neural networks
employed by DDQN-VNFPA.
Combining the simulation results from Figure 3, it is evident
that DeepOpt decreases the rejection ratio of service function
chain requests by 37.1% while requiring just 5.3% more
computation time compared to the best baseline, DDQN-
VNFPA. In summary, DeepOpt offers a superior trade-off
between complexity and accuracy compared to the other Fig. 5. Time consumption of different schemes
baseline schemes.

results demonstrate that our proposed scheme has superior

generalization capabilities across various network topologies
compared to existing state-of-the-art DRL-based solutions. In
future work, we plan to further explore and highlight the
advantages of DeepOpt through more extensive evaluations.
R EFERENCES
[1] R. Cziva, C. Anagnostopoulos, and D. P. Pezaros, “Dynamic, latency-
optimal vnf placement at the network edge,” in Ieee infocom 2018-ieee
conference on computer communications. IEEE, 2018, pp. 693–701.
[2] A. Gember-Jacobson, R. Viswanathan, C. Prakash, R. Grandl, J. Khalid,
S. Das, and A. Akella, “Opennf: Enabling innovation in network function
control,” ACM SIGCOMM Computer Communication Review, vol. 44,
no. 4, pp. 163–174, 2014.
[3] F. Bari, S. R. Chowdhury, R. Ahmed, R. Boutaba, and O. C. M. B.
Duarte, “Orchestrating virtualized network functions,” IEEE Transac-
Fig. 3. The reject ratio of all SFC requests under differentschemes tions on Network and Service Management, vol. 13, no. 4, pp. 725–739,
2016.
[4] J. Pei, P. Hong, M. Pan, J. Liu, and J. Zhou, “Optimal vnf placement via
deep reinforcement learning in sdn/nfv-enabled networks,” IEEE Journal
on Selected Areas in Communications, vol. 38, no. 2, pp. 263–278, 2019.
[5] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Al-
izadeh, “Learning scheduling algorithms for data processing clusters,” in
Proceedings of the ACM special interest group on data communication,
2019, pp. 270–288.
[6] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradi-
ent methods for reinforcement learning with function approximation,”
Advances in neural information processing systems, vol. 12, 1999.
[7] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zam-
baldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner
et al., “Relational inductive biases, deep learning, and graph networks,”
arXiv preprint arXiv:1806.01261, 2018.
[8] P. Gawłowicz and A. Zubow, “ns3-gym: Extending openai gym for
networking research,” arXiv preprint arXiv:1810.03943, 2018.
[9] S. Uhlig, B. Quoitin, J. Lepropre, and S. Balon, “Providing public in-
tradomain traffic matrices to the research community,” ACM SIGCOMM
Computer Communication Review, vol. 36, no. 1, pp. 83–86, 2006.
[10] C. Reiss, J. Wilkes, and J. L. Hellerstein, “Google cluster-usage traces:
Fig. 4. The performance of each scheme in the changedtopology (-1/+1 means format+ schema,” Google Inc., White Paper, vol. 1, pp. 1–14, 2011.
deleting/adding a node in the [Link] y-axis value of each scheme is [11] D. Qi, S. Shen, and G. Wang, “Towards an efficient vnf placement in
calculated with respectto the original SFC reject ratio (the SFC reject ratio in network function virtualization,” Computer Communications, vol. 138,
thetopology with no node variation) of each scheme) pp. 81–89, 2019.
[12] M. Mechtri, C. Ghribi, and D. Zeghlache, “A scalable algorithm for the
placement of service function chains,” IEEE transactions on network
V. C ONCLUSIONS and service management, vol. 13, no. 3, pp. 533–546, 2016.

In this press, we present DeepOpt, a method that integrates

DRL and GNN to address the VNF placement challenge.
DeepOpt is a data-driven approach for generating VNF place-
ment policies, independent of human expertise. Simulation