# Exploring the Effectiveness of Service Migration Strategies for Virtual Network Embedding

Federico Giarrè

Univ Rennes, Inria, CNRS, IRISA

Rennes, France

federico.giarre@inria.fr

Yassine Hadjadj-Aoul

Univ Rennes, Inria, CNRS, IRISA

Rennes, France

yhadjadj@irisa.fr

***Abstract***—Network slicing, a key component of post-5G networks, has brought virtual network embedding (VNE) to the forefront of networking research. However, existing VNE approaches are limited by their consideration of static network topologies, failing to account for the dynamic nature of real-world networks. This limitation becomes particularly problematic in the face of link failures or topology modifications, rendering these approaches ineffective. To address this, we propose a new service placement strategy that remains effective even when the network topology changes. Furthermore, we introduce several service migration strategies and thoroughly investigate their effectiveness. Our results demonstrate the adaptability of our proposed strategy, which leverages graph neural networks, in handling link failures without necessitating relearning. This adaptability underlines the potential of our approach to significantly enhance the robustness and flexibility of service migration in VNE, thereby contributing to the evolution of network slicing in post-5G networks.

***Index Terms***—Network Slicing, Virtual Network Embedding, Service migration, Reinforcement learning, Network Robustness.

## I. INTRODUCTION

In the rapidly evolving telecommunications sector, network slicing is emerging as a cornerstone of post-5G networks [1]. This technology, which allows for the creation of multiple virtual networks on a single physical infrastructure, is revolutionizing the way we manage and operate networks. However, realizing this potential depends on our ability to effectively enforce Virtual Network Embedding (VNE), which is a crucial yet complex aspect of network slicing [2].

Traditional approaches to network slicing often consider static network topologies, a perspective that is increasingly inadequate in the face of today's rapidly changing network environments [3]. Link failures, topology modifications, and other unforeseen changes can render these static methods ineffective, highlighting the need for a more robust network with the capability of service migration, to adapt to the ever-changing networks.

The literature on service migration has evolved significantly over the years. While classical research has focused on single Network Functions (NFs) migration or paths' replacements, recent studies have highlighted the importance of considering graph-structured services. Various methodologies, ranging from Integer Linear Programming (ILP) to heuristics and metaheuristics, have been proposed to address the challenges

of service migration in dynamic networks [4]. However, many of these approaches are limited in their ability to handle complex network scenarios, particularly those involving changing topologies. Our work builds on these foundations, aiming to address the identified gaps and provide a more comprehensive solution for service migration in post-5G networks.

In this paper, we tackle the challenges above. We propose and analyze several service migration strategies capable of efficiently placing services even in the case of topology changes. Our approach leverages the power of Graph Neural Networks (GNN), allowing for a high degree of adaptability without the need for relearning [5]. These contributions represent a significant advancement in the field of VNE, which traditionally considers only static topologies, offering new avenues for enhancing the robustness and flexibility of network slicing in post-5G networks.

The remainder of this paper is organized as follows: In Section III we delve into the VNE problem, providing a comprehensive formalization and shedding light on the methodology employed for its resolution. Section II introduces a brief overview of the related work and positions our contribution. Section IV shifts focus to the Virtual Network Request (VNR) migration problem, where we introduce and formalize the concept. In Section V, we detail the migration strategies we propose, elucidating their design and functionality. In Section VI, we present a detailed evaluation of our strategies, highlighting their advantages and limits. Finally, Section VIII concludes the paper and discusses potential future research.

## II. RELATED WORK

The advent of network slicing in 5G networks has reinforced the importance of service migration strategies in future networks, particularly as these networks become increasingly complex and dynamic. In fact, service migration plays a crucial role in maintaining network performance and reliability, particularly in scenarios of changing network conditions (e.g., network congestion, link degradation or failure) [4]. In such situations, the ability to quickly and seamlessly migrate services to less congested or more reliable parts of the network can significantly improve network performance and user experience [6].

Existing work can be classified according to several criteria: the **triggers for migration**, which could include congestion
detection or avoidance, network defects, or energy consump-
tion optimization; the **methodology** employed, which could
be either reactive or proactive; and the **characteristics of
the services** being migrated, whether they are monolithic or
graph-structured; and the **resources' allocation/reallocation
algorithms**. The different points listed here are orthogonal and
can be present together [7], but in what follows we will only
focus on the last two points.

A. *Services’ characteristics*

The characteristics of the services being migrated can
significantly influence the migration strategy. Monolithic ser-
vices, which are self-contained and independent, can often be
migrated more easily than graph-structured services, which
consist of multiple interconnected components. Indeed, the
migration of graph-structured services requires a guaranteed
networking resources to maintain the dependencies and in-
teractions between different components. The majority of
literature falls into the first category, i.e., where we have
monolithic services [4].

Furthermore, services can be either constrained or uncon-
strained. Constrained services, such as those explored in this
study, have specific requirements. These may include the
amount of bandwidth that must be available between the
services' components, particular latency concerns, and other
system requirements. This complexity of requirements greatly
complicates the resource allocation process and, in particular,
the migration process.

B. Resource allocation/reallocation algorithms

Resource allocation/reallocation algorithms are crucial in
service migration, and the complexity of the algorithms in-
volved often depends on the available resources and the
constraints of the services to be migrated [8]. Indeed, in the
case of over-dimensioned systems with ‘best-effort’ monolithic
services, a very basic migration strategy, such as First-Fit,
might be quite sufficient [9]. The issue becomes significantly
more complex when resources are not abundant (e.g., network
edges) and when dealing with constrained services structured
as graphs. Our approach falls into the latter category, in which
we delve in the rest of the section.

The approaches proposed in the literature can be classified
in different ways (see the summary in Table I).

While the literature contains limited studies specifically
addressing the service migration problem, it is worth noting
that traditional research on service placement could be adapted
for redeploying services, just as new ones. However, migrating
a service without considering its current placement can be
inefficient, as demonstrated in this paper, and might even risk
destabilizing the network.

Most of the literature approaches formalize the problem
using Integer Linear Programming (ILP) [10], [12], [14], [16]–
[19], [23]–[25]. Given the NP-completeness of the problem,
these methods invariably suggest alternative solutions for
better scalability. An exact model is typically limited to solving
small problem instances. Moreover, without knowledge of

future requests, such models aren't efficiently applicable and
can't guarantee optimality [27].

The prevalent heuristics to address the migration challenge
often employ “First-Fit” or “Decreasing First-Fit” strategies
for node placement [10]–[21], with variations to optimize
energy consumption or minimize congestion [11], [12]. For
virtual link placement, these strategies typically rely on
shortest-path calculations. While effective for determining
the shortest path between two points, they fall short when
placing graphs. These heuristics often underperform. More
sophisticated heuristics, like those based on the Hopcroft-
Karp [21] or Edmonds-Karp algorithms [18], offer worst-case
guarantees. While not optimal, they present more efficient
alternatives.

Meta-heuristics, such as “Ant colony” [22], “Bee
colony” [24], “Simulated Annealing” [25], and “Particle-
swarm” [23], have been introduced to identify global optima
for the resource relocation challenge. These methods have
proven to be adapted to tackle complex combinatorial
problems. They facilitate a comprehensive exploration of the
solution space, but require a digital twin, a precise replica of
reality, to test the solutions’ efficiency before the placement.
This requirement can be costly. In addition, each relocation
request requires a new calculation, as this type of approach
is deprived of any learning.

Recent advancements have applied reinforcement learning
to the VNE problem, yet few have specifically tackled ser-
vice migration. The Irregular Cellular Learning Automata
(ICLA) method, primarily focusing on SDN controller and
flows placements, has been suggested [26]. This method,
however, presumes a limited state and action spaces for timely
convergence, which isn't the case for VNE. More critically,
such techniques demand recurrent learning for convergence,
rendering them impractical for real-world scenarios.

In our study, we aim to advance the current state of the art
by introducing a technique that not only identifies superior so-
lutions or even the global minimum using deep reinforcement
learning but also eliminates the need for repetitive learning
for each migration computation through the integration of
Graph Neural Nets (GNN). In addition, we evaluate various
migration strategies, demonstrating that approaches based on
partial migration offer the best balance between cost and
efficiency.

III. VNE MAPPING PROBLEM

A. Problem Description

The Virtual Network Embedding (VNE) problem involves
the allocation of physical resources to Virtual Network Re-
quests (VNRs). A VNR is a graph that connects Virtual Net-
work Functions (VNFs) with specific resource requirements.
For the sake of simplicity, we will focus solely on the CPU
requirements that the VNFs will demand from the physical
nodes of the underlying topology (i.e., substrate network).

In this work, we will take into account a variation of the
virtual node mapping (VNM) process where the mapping
<table><caption>TABLE I
SUMMARY OF EXISTING APPROACHES</caption><thead><tr><th rowspan="2">Ref.</th><th colspan="4">Type of migration</th><th rowspan="2">Type of Network</th><th rowspan="2">Type of Algorithm</th><th rowspan="2">Exact</th><th rowspan="2">Objective</th><th rowspan="2">Triggering Event</th><th rowspan="2">Re-learning</th></tr><tr><th>NFs</th><th>Paths</th><th>Part S.</th><th>Whole S.</th></tr></thead><tbody><tr><td>[10]</td><td></td><td></td><td></td><td>✓</td><td>DC</td><td>Heuristic</td><td>ILP</td><td>SA</td><td>Any</td><td>Not applicable</td></tr><tr><td>[11]</td><td></td><td></td><td></td><td>✓</td><td>DC</td><td>Heuristic</td><td>ILP</td><td>Energy</td><td>Any</td><td>Not applicable</td></tr><tr><td>[12]</td><td></td><td></td><td></td><td>✓</td><td>DC</td><td>Heuristic</td><td>ILP</td><td>Energy</td><td>Any</td><td>Not applicable</td></tr><tr><td>[13]</td><td></td><td>✓</td><td></td><td></td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>SA</td><td>Any</td><td>Not applicable</td></tr><tr><td>[14]</td><td></td><td></td><td></td><td>✓</td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Mobility</td><td>Not applicable</td></tr><tr><td>[15]</td><td></td><td></td><td></td><td>✓</td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>SA</td><td>Any</td><td>Not applicable</td></tr><tr><td>[16]</td><td></td><td></td><td></td><td>✓</td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Mobility</td><td>Not applicable</td></tr><tr><td>[17]</td><td></td><td></td><td></td><td>✓</td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Any</td><td>Not applicable</td></tr><tr><td>[18]</td><td></td><td></td><td>✓</td><td></td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Failure</td><td>Not applicable</td></tr><tr><td>[19]</td><td></td><td></td><td>✓</td><td></td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Any</td><td>Not applicable</td></tr><tr><td>[20]</td><td></td><td></td><td>✓</td><td></td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Any</td><td>Not applicable</td></tr><tr><td>[21]</td><td></td><td></td><td>✓</td><td></td><td>WAN</td><td>Heuristic</td><td>ILP</td><td>R2C</td><td>Mobility</td><td>Not applicable</td></tr><tr><td>[22]</td><td>✓</td><td></td><td></td><td></td><td>DC</td><td>Meta-heuristic</td><td>ILP</td><td>Energy</td><td>Any</td><td>Needed</td></tr><tr><td>[23]</td><td></td><td>✓</td><td></td><td></td><td>WAN</td><td>Meta-heuristic</td><td>ILP</td><td>Energy</td><td>Any</td><td>Needed</td></tr><tr><td>[24]</td><td></td><td></td><td></td><td>✓</td><td>WAN</td><td>Meta-heuristic</td><td>ILP</td><td>SA</td><td>Any</td><td>Needed</td></tr><tr><td>[25]</td><td></td><td></td><td></td><td>✓</td><td>WAN</td><td>Meta-heuristic</td><td>ILP</td><td>R2C</td><td>Congestion</td><td>Needed</td></tr><tr><td>[26]</td><td></td><td>✓</td><td></td><td></td><td>WAN</td><td>RL</td><td>ILP</td><td>R2C</td><td>Any</td><td>Needed</td></tr><tr><td>Our</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>WAN</td><td>DRL</td><td>ILP</td><td>R2C</td><td>Any</td><td>Not needed</td></tr></tbody></table>

function, $f_{VNM}(VNR) : \mathbb{N}^{VNR} \to \mathbb{N}^s$ is injective VNR-wise. This implies that VNFs belonging to the same VNR cannot be placed on the same substrate node. Additionally, to connect different VNFs, virtual links (VLs) are mapped onto the topology using a virtual link mapping (VLM) function $f_{VLM}(VNR) : \mathbb{L}^{VNR} \to \mathbb{L}^s$. One VL is composed of the succession of substrate links that it has to traverse to get from one VNF to another ($P_{l^v}$). Each VL requires a certain amount of bandwidth for its deployment, and it is possible for multiple VLs (even belonging to the same VNR) to share the same substrate link. The substrate link has a limited total bandwidth capacity, which serves as a constraint when deploying VLs onto it.

We can formalize the resource constraint for both $f_{VNM}$ and $f_{VLM}$ for the placement as:

$$c_{n^v} \le c_{n^s}^i \quad \text{where} \quad c_{n^s}^i = c_{n^s}^{0,i} - \sum_{n \in \mathbb{N}_s^v} c_{n^v} \quad (1)$$

$$b_{l^v} \le b_{l^s}^i \quad \text{where} \quad b_{l^s}^i = b_{l^s}^{0,i} - \sum_{l \in \mathbb{L}_s^v} b_{l^v} \quad (2)$$

In equation (1), $c_{n^v}$ represents the resource requirement of VNF $n^v$, and $c_{n^s}^i$ represents the available residual CPU resources at the placement location $n^s$ after considering the resource consumption of all currently placed VNFs. This constraint guarantees that the placement of VNFs is resource-aware, preventing the overloading of the substrate nodes and ensuring the efficient utilization of available resources in the network.

Equation (2) applies similar reasoning to the bandwidth constraint. Here, $b_{l^v}$ represents the resource requirement of VL $l^v$, and $b_{l^s}^i$ represents the available residual bandwidth resources on the physical link $l^s$. The constraint ensures that a VL can only be placed if there are sufficient residual bandwidth resources available after accounting for the existing VLs on that link.

<table><caption>TABLE II
NOTATION</caption><thead><tr><th>Notation</th><th>Description</th></tr></thead><tbody><tr><td>G<sup>s</sup>, G<sup>v</sup></td><td>Substrate network and VNR graphs</td></tr><tr><td>N<sup>s</sup>, N<sup>v</sup></td><td>Set of substrate nodes and VNFs</td></tr><tr><td>L<sup>s</sup>, L<sup>v</sup></td><td>Set of substrate links and VLs</td></tr><tr><td>N<sup>r</sup>, L<sup>r</sup></td><td>Set of VNFs and VLs to remap</td></tr><tr><td>N<sup>v</sup><sub>s</sub>, L<sup>v</sup><sub>s</sub></td><td>Set of VNFs and VLs on node or link s</td></tr><tr><td>N<sup>V</sup><sub>s</sub>, L<sup>V</sup><sub>s</sub></td><td>Set of VNFs and VLs of a VNR V</td></tr><tr><td>R(v)</td><td>Revenue to cost of the VNR v</td></tr><tr><td>M(N<sup>r</sup>, L<sup>r</sup>)</td><td>Migration cost of a VNR</td></tr><tr><td>c<sup>0,i</sup><sub>l<sup>s</sup></sub></td><td>Overall CPU capacity of sub. node n<sup>s</sup> at time i</td></tr><tr><td>c<sup>n<sup>s</sup></sup><sub>l<sup>s</sup></sub></td><td>Available CPU at sub. node n<sup>s</sup> at time i</td></tr><tr><td>b<sup>0,i</sup><sub>l<sup>s</sup></sub></td><td>Bandwidth capacity of sub. link l<sup>s</sup> at time i</td></tr><tr><td>b<sup>i</sup><sub>l<sup>s</sup></sub></td><td>Available Bandwidth at sub. link l<sup>s</sup> at time i</td></tr><tr><td>c<sub>n<sup>v</sup></sub></td><td>CPU requested by VNF n<sup>v</sup></td></tr><tr><td>b<sub>l<sup>v</sup></sub></td><td>Bandwidth requested by VL l<sup>v</sup></td></tr><tr><td>P<sub>l<sup>v</sup></sub></td><td>Substrate path for a VL l<sup>v</sup></td></tr><tr><td>|P<sub>l<sup>v</sup></sub>|</td><td>Number of substrate link hops for a VL l<sup>v</sup></td></tr></tbody></table>

The goal of the VNE mapping problem is to map a VNR graph with the best possible fit onto the substrate network. In this study, we focus solely on evaluating the quality of the placement based on the distance (measured in hops) between the VNFs. Thus, a perfect fit will have VNFs connected by VLs that are formed by only one substrate link. In order to measure this, we utilized the Revenue to Cost ($R(VNR)$) measure, which is computed as:

$$H_{l^v} = \begin{cases} \rho b_{l^v} (|P_{l^v}| - 1) & \text{if } |P_{l^v}| > 1 \\ 0 & \text{otherwise} \end{cases} \quad (3)$$

$$\mathcal{R}(\text{VNR}) = \frac{\sum_{l^v \in \mathbb{L}^v} b_{l^v}}{\sum_{l^v \in \mathbb{L}^v} b_{l^v} + H_{l^v}} \quad (4)$$

The factor described in equation (3) is meant to be penalizing the $\mathcal{R}(VNR)$ when paths $P_{l^v}$ are composed of more than one substrate link. To avoid penalizing too much the Revenue to Cost of a VNR due to longer substrate hops, the
discount factor $\rho$ is applied. As for equation (4), the $\mathcal{R}(\text{VNR})$ will return a value in the range $[0, 1]$, where a higher value corresponds to a better placement.

## B. DRL approach

The problem defined in the previous section is a more complex version of the knapsack problem, which is already NP-complete and thus very hard to solve with exact optimization techniques. Moreover, the system under consideration is dynamic (dynamic arrival and departure of services), which makes classical methods unsuitable [27]. Indeed, since we do not have access to future requests, we cannot guarantee optimality. However, learning techniques are able to generalize from past experiences and enable a real-time execution once trained.

As labeled data is not available, and knowing the superiority of reinforcement learning strategies [28], we decided to tackle the node mapping phase of the problem by proposing a Deep Reinforcement Learning (DRL) Agent.

In order to build such an agent, we need to express the VNE mapping problem as a Markov Decision Process [29] (MDP). In the following, we outline this MDP through its state representation, action space, and reward function (see Fig. 1).

a) **State representation:** The state is given by the pair $(\mathcal{G}^s, \mathcal{G}^v)$. Each substrate node at time $i$ has two defining features: $c_{n^s}^{0,i}$ and $b_{i^s}^{0,i}$. VNFs are characterized by their CPU and bandwidth demands, represented as $c_{n^v}$ and $b_{i^v}$.

b) **Action space:** The action space only concerns the VNM phase of the VNR placement. Let $A_i$ represent the set of potential substrate nodes for deploying the $i^{th}$ VNF of the VNR, and $a_i$ be the chosen action. Given that VNFs are placed in sequence and the VNM function's injectivity must be maintained, the action space can be expressed as:

$$A_i = A_0 / \{a_1...a_{i-1}\}$$

c) **Reward function:** The reward function is designed to guide the Agent towards optimal VNR placements. It operates as follows:

* **Successful Placement:** If the Agent successfully completes both the VNM and VLM phases, it receives a reward equivalent to the R2C of the placed VNR. This encourages the Agent to find placements that optimize the R2C metric.

* **Unsuccessful Placement:** In cases where the Agent fails in either the VNM or VLM phases, a penalty of -1 is given. This discourages the Agent from making placements that lead to failures.

* **Intermediate Placements:** During the process, each VNF is placed sequentially. For these individual or intermediate placements, the Agent receives a neutral reward of 0. This ensures that the Agent doesn't receive premature positive or negative feedback before the entire VNR is placed.

In order to prioritize immediate over distant rewards, the reward function incorporates a discount factor, denoted as $\gamma$.

This not only accelerates decision-making but also aids in the learning process's convergence toward optimal outcomes.

The DRL agent we propose leverages a Graph Convolutional Network (GCN) [30] to extract key features from the substrate network, such as bandwidth and CPU availability in nodes and links, as well as details about the VNR to be mapped. Upon processing these features, the agent attempts to place the VNFs and receives the corresponding reward. After an initial exploration phase where the agent takes random actions, it begins to adopt policies that optimize the mapping process.

This paper builds on the previous work in [31], which introduced a novel GCN model for a batch of services placement. While we retain the models and specifications from the original study, our contribution broadens their application to accommodate dynamic service arrivals and departures, as well as network changes such as link failures and updates, which can necessitate service migrations.

## IV. VNR MIGRATION

VNFs within the same VNR need to cooperate in order to achieve a common objective. This implicitly requires Quality of Service (QoS) measures in case the physical links that host the connections of such VNFs degrade or break. We tackled this problem by proposing link-aware migration strategies to be applied to the VNR in case of link deterioration or outage.

### A. Problem description

In our system, whenever a physical link experiences a failure or degradation, the migration process is promptly initiated. If the process is successful, meaning that the Agent was successful in finding a remapping for the affected resources, we proceed with committing the operation. However, if the Agent fails, the entire VNR will be extracted from the network and placed in a priority queue.

Each time a resource in the network becomes available (i.e., when other VNRs leave the network), the Agent tries mapping queued VNRs according to their priorities. Popping a VNR from the queue can happen in three cases: i) The Agent is able to map the VNR correctly; ii) The Agent encounters repeated failures in mapping the VNR for a predefined number of attempts ($k$), where $k$ can be configured to align with the system's requirements or the criticality of the service; iii) The VNR exhausts its available time in the system, signifying the end of its active state, and it can be removed from the queue.

Arriving VNRs are also enqueued, ensuring that extracted VNRs waiting to be remapped receive higher priority. This strategy is proposed to prevent starvation issues, especially when dealing with a high arrival rate of VNRs.

In case of a physical link outage, migration is initiated for every VNR that utilizes the affected link. However, when faced with link degradation, the Agent adopts a different approach. It performs migration for the minimum number of VNRs required to alleviate the saturation on the physical link, effectively restoring it to a non-saturated state. This strategy ensures that resources are optimally utilized, minimizing disruption
<figure><img src="image_1.png" /><figcaption>Fig. 1. MDP for VNR migration</figcaption></figure>

to the network while efficiently mitigating the impact of link degradation.

## B. Problem Formulation

We can present link degradation or outage using the following expression:

$$b_{ls}^{0,i} < b_{ls}^{0,i-1} \wedge b_{ls}^{i} < 0 \quad (5)$$

In this formulation, $b_{ls}^{0,i}$ represents the bandwidth capacity of the physical link $l^s$ at time $i$, and $b_{ls}^{0,i-1}$ denotes the bandwidth capacity on the same link at the previous time step. The inequality $b_{ls}^{0,i} < b_{ls}^{0,i-1}$ indicates link degradation. Additionally, the right-hand side of the equation means that the available bandwidth on the link is less than zero, reflecting the saturation state of the link, and therefore the need for migration.

Whenever a migration is triggered, we compute the migration cost of all involved VNRs using the expression:

$$\mathcal{M}(\mathbb{N}^r, \mathbb{L}^r) = \omega \sum_{n^v \in \mathbb{N}^r} c_{n^v} + (1 - \omega) \sum_{l^v \in \mathbb{L}^r} b_{l^v} \quad (6)$$

where $\omega$ represents a hyperparameter applied to the costs of migrating nodes and links in order to modify the importance of one with respect to the other.

Each VNR is enqueued in a priority queue, with its migration cost serving as the priority. Lower migration cost values are given higher priority, ensuring that VNRs requiring fewer resources to be migrated are placed before others in the queue.

The success of migration of a VNR $V$ is contingent upon remapping all its nodes $n \in \mathbb{N}^r \cap \mathbb{N}^V$ and its links $l \in \mathbb{L}^r \cap \mathbb{L}^V$ without encountering any issues. This priority-based approach allows for efficient migration of VNRs with minimal resource disruption and optimizes resource utilization during the remapping process.

Considering that $\mu$ denotes the average value of $\mathcal{M}(\mathbb{N}^r, \mathbb{L}^r)$, we introduce a constant $c$ such that $c \gg \mu$. When the migration

process is unsuccessful, the corresponding Virtual Network Request (VNR) is enqueued with its priority modified to the following:

$$-c + \mathcal{M}(\mathbb{N}^r, \mathbb{L}^r) \quad (7)$$

This modification ensures that VNRs extracted from the network and awaiting remapping are assigned higher priority compared to arriving VNRs, while still maintaining the relative priority order between them. By employing this approach, we ensure the utilization of network resources while enhancing the overall service provisioning efficiency.

## V. MIGRATION STRATEGIES

In this section, we propose several migration strategies. These strategies vary in the selection of resources to be migrated, and hence the migration cost, ranging from the most DRL-intensive approach (whole VNR migration) to not utilizing DRL at all (edge remapping). Our study explores the effectiveness and trade-offs of these strategies, delving into their impact on network performance and resource optimization.

### A. Whole VNR Migration

This strategy involves migrating all nodes and edges of a VNR. When coming to link degradation, not only the directly connected VNFs are affected, but the entire service graph can experience degradation. Nonetheless this method incurs the highest migration cost among the three strategies.

For this strategy, the links and the nodes to remap are trivially computed as:

$$\mathbb{N}^r = \mathbb{N}^V$$

$$\mathbb{L}^r = \mathbb{L}^V$$

By migrating the entire VNR we address potential service interruptions and enable the DRL Agent to adapt and
optimize its decisions over time. This iterative learning process enhances the strategy's efficiency and ultimately leads to improved resource utilization and better overall network performance.

Note that this method can be especially beneficial in situations in which the network is congested in a certain area, so migrating the entire VNR to a new location can be a good strategy.

## B. VNR Subgraph Migration

This strategy consists in migrating all the VNFs attached to the ends of the VLs mapped on the degraded substrate link, and then remapping the virtual links to reconnect the VNFs. This allows the DRL Agent to find a placement only for the resources that would be impacted directly by the substrate link degradation, leading the Agent to have fewer resources to move with respect to migrating the whole VNR. For this strategy the links and the nodes to remap are computed as follows:

$$ \mathbb{N}^r = \text{VNFs connected by } l^V \ \forall l^V \in \mathbb{L}_s^V $$

$$ \mathbb{L}^r = \text{VLs attached to } n^V \ \forall n^V \in \mathbb{N}^r $$

This method will be beneficial in scenarios in which resources are available in the surroundings of the VNR, so not only the placement can have a similar Revenue to Cost, but the latter can also improve based on newly freed resources.

## C. Edge Remapping

This strategy involves a straightforward remapping of the VLs that were originally mapped on the degraded substrate link using Dijkstra's shortest path algorithm.

It does not involve the DRL Agent at all, since no remapping of nodes is required. Therefore, the results depend only on the network load. In this case, the cost of migration will be solely made of the number of virtual links that have to be remapped. With this strategy, we only need to compute the set $\mathbb{L}^r$, which consists of the VLs that were using the broken or degraded substrate link $s$.

We can finally compute the remapping set as:

$$ \mathbb{L}^r = \mathbb{L}_s^V $$

By adopting this approach, we address links' failures or degradation efficiently and optimize network performance based on the network's current state without the need for complex DRL-based decisions.

# VI. PERFORMANCE EVALUATION

In this section, the evaluation of the three strategies will be presented. Additionally, the migration problem will also be solved with a modified First-Fit agent for comparison purposes.

## A. Evaluation setup

The performance of the proposed strategies is carried out using a customized discrete-event simulator based on [32]. This simulator is specially designed to reproduce real network scenarios and dynamics, allowing us to comprehensively evaluate the performance of our strategies in a controlled environment [33].

To model the stochastic events (i.e., VNR arrivals and link failures or capacity modification), we considered a Poisson process, which is a common and effective method in network simulation studies to account for the randomness and unpredictability of these events [34]. For VNR departures, we adopt an exponential service time model, which is widely accepted to represent the varying lifetimes of VNRs in the network.

<table><caption>TABLE III
PARAMETERS USED FOR RUNNING TESTS</caption><thead><tr><td>Parameter</td><td>Value</td></tr></thead><tbody><tr><td>Simulation time</td><td>180000 ticks</td></tr><tr><td>Episode duration</td><td>300 ticks</td></tr><tr><td>Mean time between VNR arrival</td><td>5 ticks</td></tr><tr><td>Mean time between bandwidth variation</td><td>10 ticks</td></tr></tbody></table>

We defined the Mean Time Between Arrivals (MTBA) for each event in discrete simulation time, along with other relevant parameters listed in Table III.

For testing purposes, during each bandwidth variation event, one used substrate link will be intentionally broken to trigger migration. Once the migration is resolved, the link is restored. The simulated VNR will be placed in a network topology, specifically the BtEurope topology<fnref n="1" />.

It is important to note that while we have presented results for a specific topology, the proposed approach can be applied to both smaller and larger network topologies. The convergence of the algorithm may vary depending on the topology's size; however, the results obtained align consistently with those presented below. Furthermore, the incorporation of GNNs enables generalization in the learning process, facilitating the adaptation to topologies of different sizes without requiring relearning. While this aspect will be a focus of future work, our current approach demonstrates the adaptability of the learning process with small variations in the network topology (i.e., link failures).

## B. Results

As explained in previous sections, the revenue-to-cost ratio (R2C for short) is a measure of the quality of placement, where a high R2C indicates that the DRL agent has been able to efficiently place the VNR graph onto the substrate network.

To measure the quality of a migration, we introduce the ΔR2C measure, which quantifies the percentage of improvement of the R2C after the resources' migration.

Let $\mathcal{R}(V)$ be the R2C of a given VNR $V$ before migration, and $\mathcal{R}(V')$ be the R2C of the same VNR after the migration. The ΔR2C is then computed using the formula:

<footnote n="1">¹BtEurope topology: http://www.topology-zoo.org/explore.html</footnote>
$$ \Delta R2C = \frac{\mathcal{R}(V') - \mathcal{R}(V)}{\mathcal{R}(V)} \qquad (8) $$

This measure provides valuable insights into the effectiveness of the migration process conducted by the DRL agent. A positive value for ΔR2C indicates an improvement in revenue compared to the initial placement. Conversely, a negative value does not imply the agent's ineffectiveness, but rather reflects the challenge of remapping the VNR considering resource alterations.

The upcoming plots will follow a consistent format: each point on the graph represents the results of an episode, with an average of 30 migrations occurring within each episode. For each episode, the median of all ΔR2Cs and the mean of all R2Cs will be displayed. A lighter area around the ΔR2C show the standard deviation of the migrations' ΔR2C of the episodes (σΔR2C), that will be both added and subtracted from the ΔR2C in order to indicate where the majority of results fall for an episode.

In the first three result plots (Figs. 4,3 and 2), the mean R2C for the FF Agent is shown, but not the ΔR2C and σΔR2C. This has been done in order to enhance the readability of such plots, yet the essence of the results can be gathered in the plots presented, later on, in Figs. 5 and 6.

1) **VNR's edges remapping:** Figure 2 illustrates the results for the edges' remapping strategy. In this case, the ΔR2Cs systematically fall below the 0 line, indicating that this strategy leads to a decline in R2C. Indeed, the R2C of the migrated resources is found to be approximately 3% to 5% worse than the resources before migration. As this approach does not involve the use of the DRL agent during migration, the DRL Mean R2C measure does not influence the ΔR2Cs, but it can be used to understand that the behavior of this strategy is not at all impacted by the initial placement of the VNRs by the controller.

<figure><img src="image_2.png" /><figcaption>Fig. 2. Results for edges' remapping</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 3. Results for Subgraph Migration</figcaption></figure>

Regarding σΔR2C, a linear trend is observed, with stability observed around 7.5% to 8%. This consistency in the standard deviation reflects the predictable performance of the edges' remapping strategy across multiple episodes.

2) **VNR's subgraph migration:** In Figure 3, the results for the subchain migration strategy are presented. With this strategy, the ΔR2Cs tends to be closer 0, indicating an equal (or eventually very close to equal) mapping for most episodes. Thus, by moving just a few more resources than the previous strategy, the DRL agent is able to more or less maintain the quality of the initial service placement, although without really being able to improve it significantly.

Since more resources are moved with respect to the previous strategy, a wider σΔR2C is achieved, spanning between 7% to 8% of improvement/loss in R2C after the initial learning period.

3) **Whole VNR Migration:** In Fig.4 and Fig.5 the results are shown for the Whole VNR Migration strategy. As it is possible to notice by the figures, the ΔR2Cs is positive in several episodes, indicating that migration of the whole nodes and edges can result in a better (even if slightly) placement overall. The area given by the σΔR2C also shows how the possible improvement (and deterioration) is wide enough to allow a 10% to 12% gain (or loss) in R2C when coming to migrations after the initial learning period.

4) **First-Fit Agent:** The First-Fit agent have consistent results in all the executed tests: i) The σΔR2C in all tests is around 20% though not plotted for readability reasons. While not readable directly, this can be noticed from Figs. 5 and 6 where, excluding the outliers, the spread of the median ΔR2C is also in the order of 20% ii) Even if the results of plots 5 and 6 show a good margin of improvement in all the tests (apart from the Edges remapping), due to the low R2C of the mapped VNRs it is easy to improve or worsen a placement sensibly.
<figure><img src="image_4.png" /><figcaption>Fig. 4. Results for Whole VNR Migration</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5. Spread of the median ΔR2C values of the different strategies</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 6. Spread of the median ΔR2C with subgraph strategy, different MTBA</figcaption></figure>

### C. Performance of the Subgraph-Based Strategy under Varied Network Loads

The results of the subgraph migration strategy offer the best trade-off in terms of cost-gain (and reliability) ratio, we decided to analyze the performance of it in less stressed environment. We conducted two more tests, where the only difference from the parameter in Table III is the mean time between arrival (MTBA) of new placement requests. While this doesn't directly affect the remapping of the VNR, there are some obvious consequences of making these changes. For instance, a less congested network allows for virtually better placements, but at the same time the DRL Agent will not learn what to do when more resources than usual are utilized. This factor leads to some good, yet counter-intuitive, results.

For the following tests, the mean time between arrival is set to 10 and 15 ticks. In Figure 6, the results for these tests are plotted, accompanied by the result of the strategy with MTBA of 5 (as for the previous tests), for comparison.

To begin, let's consider the behavior of the First-Fit agent, which exhibits the expected natural response: when more resources are available, there are increased placement possibilities, leading to a wider range of potential improvement or degradation in the R2C metric.

For what concerns the DRL agent, the more loaded the network is, the more precise it gets with the placements, achieving a much narrower spread in the 5 ticks between arrivals compared to 10 or 15 ticks. This behavior arises from the agent's adaptation to the congested environment during interactions. In such situations, the agent learns to be mindful of other VNRs when migrating to avoid degrading the R2C. In contrast, in less congested scenarios, the agent may prioritize reaching higher R2Cs directly. Consequently, when the network is relatively loaded at migration time, the agent might be forced to take suboptimal actions, resulting in potential degradation in R2C.

Regardless of the test conditions, the subgraph strategy consistently maintains its unique properties. The observations discussed earlier remain valid, highlighting the strategy's stability and reliability. It consistently delivers enhanced R2C outcomes in various network scenarios.

### D. Migration Costs of different strategies

As explained in detail in Section IV, the cost of migrating a VNR (or more precisely, its elements to be migrated) is a measure used to guarantee the priority of remapping among extracted VNRs and new arrivals in the system. We can use this measure to compare the cost of using one strategy against the others.

In Fig. 7 the migration costs resulting from our tests are reported. After the first learning period, the DRL agent is able to take better decisions in placing the VNRs, decreasing the migration cost for all strategies. Excluding the Edge remapping strategy, which yields a low migration Cost by design, the trends for Whole VNR and Subgraph migrations are very similar and close for an initial period, then diverge more and more as the agent learns. This depends directly on how the
Agent places the elements to be migrated in the subgraph strategy. Indeed, when more than one VL (from the migration elements) uses the same substrate link, the number of VNFs (and thus VLs) to be migrated is very close to the whole VNR. However, at around 150 episodes, the subgraph strategy Agent starts minimizing the overlap of VLs from the same VNR on identical substrate links, leading to consistently reduced migration costs. Investigating other functions to choose the migration items for the subgraph strategy could lead to even lower migration costs overall.

<figure><img src="image_7.png" /><figcaption>Fig. 7. Migration Cost for the different strategies</figcaption></figure>

## E. Remarks on the Results

The results from the three strategies can be summed up in the following table:

<table><caption>TABLE IV
PERFORMANCE SUMMARY</caption><thead><tr><th></th><th colspan="3">Remapping strategy</th></tr><tr><th></th><th>Whole</th><th>Subgraph</th><th>Edge</th></tr></thead><tbody><tr><th>Migration cost</th><td>High</td><td>Middle</td><td>Low</td></tr><tr><th>ΔR2C</th><td>Better</td><td>Equal/Better</td><td>Worse</td></tr><tr><th>σ<sub>ΔR2C</sub></th><td>±10%</td><td>±7%</td><td>±7%</td></tr><tr><th>R2C</th><td>Middle</td><td>High</td><td>Low</td></tr></tbody></table>

The results clearly indicate that no single strategy outperforms the others; each strategy comes with its own set of advantages and disadvantages. Nevertheless, certain conclusions can be drawn from the findings:

* Depending on the criticality of the service deployed and resources available, migrating the full graph leads to better results on average;

* If the service can account for little degradation, remapping the edges will be the fastest and the cheapest (in terms of the resources to be migrated) way of ensuring QoS;

* In a situation in which migration costs have to be minded, but service is critical, remapping a subgraph of the VNR

will lead to equal or better results (on average) with a fair cost, while improving the overall R2C;

* When training the DRL Agent, a high load on the network can be beneficial in allowing the Agent to manage the opportunistic resources' allocation of other VNRs.

## VII. ACKNOWLEDGMENT

This research work is conducted as part of the NaviDEC project, funded by the Brittany Region, France, under grant agreement #21004179.

## VIII. CONCLUSION

In this paper, we propose to extend a deep reinforcement learning model to solve service placement and migration problems. We have, thus, proposed several migration models that not only allow to react to congestion problems, but also to topological changes, due in particular to link failures. To this end, we have resorted to graph neural networks to avoid relearning each time a topological change occurs, unlike existing approaches. Among the strategies proposed, the strategy based on migrating the sub-graph directly affected by the network incident proved to be the best cost-performance trade-off, when compared with strategies that solely modify the links affected by the incident or those that migrate the entire service.

For the future work, our research agenda includes several directions. Firstly, we plan to delve deeper into the exploration of techniques for selecting specific sets of nodes and links for migration within the context of the sub-graph strategy. We aim to further refine our approach and enhance its adaptability to diverse network conditions. In addition, we recognize the need to study the impact of multiple link failures on network performance. Indeed, multiple simultaneous link failures present a significant challenge in network management and can severely disrupt service migration strategies. Therefore, we intend to investigate the effects of such failures and propose robust techniques to mitigate their impact.

## REFERENCES

[1] Wen Wu, Conghao Zhou, Mushu Li, Huaqing Wu, Haibo Zhou, Ning Zhang, Xuemin Sherman Shen, and Weihua Zhuang. Ai-native network slicing for 6g networks. *IEEE Wireless Communications*, 29(1):96-103, 2022.

[2] Fadoua Debbabi, Rihab Jmal, Lamia Chaari Fourati, and Adlen Ksentini. Algorithmics and modeling aspects of network slicing in 5g and beyonds network: Survey. *IEEE Access*, 8:162748-162762, 2020.

[3] Yuan Yang, Mingwei Xu, and Qi Li. Fast rerouting against multi-link failures without topology constraint. *IEEE/ACM Transactions on Networking*, 26(1):384-397, 2018.

[4] Shangguang Wang, Jinliang Xu, Ning Zhang, and Yujiong Liu. A survey on service migration in mobile edge computing. *IEEE Access*, 6:23511-23528, 2018.

[5] Jose Suarez-Varela, Paul Almasan, Miquel Ferriol-Galmes, Krzysztof Rusek, Fabien Geyer, Xiangle Cheng, Xiang Shi, Shihan Xiao, Franco Scarselli, Albert Cabellos-Aparicio, and Pere Barlet-Ros. Graph neural networks for communication networks: Context, use cases and opportunities. *IEEE Network*, pages 1-8, 2022.

[6] Zeineb Rejiba, Xavier Masip-Bruin, and Eva Marín-Tordera. A survey on mobility-induced service migration in the fog, edge, and related computing paradigms. *ACM Comput. Surv.*, 52(5):901-903, 2019.
[7] Tarik Taleb, Adlen Ksentini, and Pantelis A. Frangoudis. Follow-me cloud: When cloud services follow mobile users. *IEEE Transactions on Cloud Computing*, 7(2):369–382, 2019.

[8] Federico Giarrè, Yassine Hadjadj-Aoul, and Soraya Ait-Chellouche. A service migration strategy for resilient multi-domain networks in outage scenarios. In *2023 International Conference on Information and Communication Technologies for Disaster Management (ICT-DM)*, pages 1–4, 2023.

[9] Haotong Cao, Han Hu, Zhicheng Qu, and Longxiang Yang. Heuristic solutions of virtual network embedding: A survey. *China Communications*, 15(3):186–219, 2018.

[10] Nashid Shahriar, Reaz Ahmed, Aimal Khan, Shihabur Rahman Chowdhury, Raouf Boutaba, and Jeebak Mitra. Renovate: Recovery from node failure in virtual network embedding. In *2016 12th International Conference on Network and Service Management (CNSM)*, pages 19–27, 2016.

[11] Xinjie Guan, Baek-Young Choi, and Sejun Song. Energy efficient virtual network embedding for green data centers using data center topology and future migration. *Computer Communications*, 69:50–59, 2015.

[12] Xinjie Guan, Baek-Young Choi, and Sejun Song. Topology and migration-aware energy efficient virtual network embedding for green data centers. In *2014 23rd International Conference on Computer Communication and Networks (ICCCN)*, pages 1–8, 2014.

[13] Mahboobeh Zangiabady, Christian Aguilar-Fuster, and Javier Rubio-Loyola. A virtual network migration approach and analysis for enhanced online virtual network embedding. In *2016 12th International Conference on Network and Service Management (CNSM)*, pages 324–329, 2016.

[14] Giorgos Chochlidakis and Vasilis Friderikos. Mobility aware virtual network embedding. In *2015 IEEE International Conference on Communications (ICC)*, pages 5846–5852, 2015.

[15] Minlan Yu, Yung Yi, Jennifer Rexford, and Mung Chiang. Rethinking virtual network embedding: substrate support for path splitting and migration. 38(2):17–29, March 2008.

[16] Yingying Guan, Yue Zong, Yejun Liu, Lei Guo, Zhaolong Ning, and Joel J. P. C. Rodrigues. Virtual network embedding supporting user mobility in 5g metro/access networks. In *ICC 2019 - 2019 IEEE International Conference on Communications (ICC)*, pages 1–7, 2019.

[17] Sheng Zhang, Zhuzhong Qian, Jie Wu, Sanglu Lu, and Leah Epstein. Virtual network embedding with opportunistic resource sharing. *IEEE Transactions on Parallel and Distributed Systems*, 25(3):816–827, 2014.

[18] Nashid Shahriar, Reaz Ahmed, Shihabur Rahman Chowdhury, Aimal Khan, Raouf Boutaba, and Jeebak Mitra. Generalized recovery from node failure in virtual network embedding. *IEEE Transactions on Network and Service Management*, 14(2):261–274, 2017.

[19] Zhiping Cai, Fang Liu, Nong Xiao, Qiang Liu, and Zhiying Wang. Virtual network embedding for evolving networks. In *2010 IEEE Global Telecommunications Conference GLOBECOM 2010*, pages 1–5, 2010.

[20] Ye Zhou, Yong Li, Depeng Jin, Li Su, and Lieguang Zeng. A virtual network embedding scheme with two-stage node mapping based on physical resource migration. In *2010 IEEE International Conference on Communication Systems*, pages 761–766, 2010.

[21] Sherif Abdelwahab, Bechir Hamdaoui, Mohsen Guizani, and Taieb Znati. Efficient virtual network embedding with backtrack avoidance for dynamic wireless networks. *IEEE Transactions on Wireless Communications*, 15(4):2669–2683, 2016.

[22] Xinjie Guan, Xili Wan, Baek-Young Choi, and Sejun Song. Ant colony optimization based energy efficient virtual network embedding. In *2015 IEEE 4th International Conference on Cloud Networking (CloudNet)*, pages 273–278, 2015.

[23] Sen Su, Zhongbao Zhang, Alex X. Liu, Xiang Cheng, Yiwen Wang, and Xinchao Zhao. Energy-aware virtual network embedding. *IEEE/ACM Transactions on Networking*, 22(5):1607–1620, 2014.

[24] Zhu Qiang, WangHui Qiang, FengGuang Sheng, and LvHong Wu. Heuristic survivable virtual network embedding based on node migration and link remapping. In *2014 IEEE 7th Joint International Information Technology and Artificial Intelligence Conference*, pages 181–185, 2014.

[25] Shihabur Rahman Chowdhury, Reaz Ahmed, Nashid Shahriar, Aimal Khan, Raouf Boutaba, Jeebak Mitra, and Liu Liu. Revine: Reallocation of virtual network embedding to eliminate substrate bottlenecks. In *2017 IFIP/IEEE Symposium on Integrated Network and Service Management (IM)*, pages 116–124, 2017.

[26] Dipanwita Thakur and Manas Khatua. Multi-domain virtual network embedding with dynamic flow migration in software-defined networks. *Journal of Network and Computer Applications*, 162:102639, 2020.

[27] Pham Tran Anh Quang, Yassine Hadjadj Aoul, and Abdelkader Outtagarts. A deep reinforcement learning approach for VNF forwarding graph embedding. *IEEE Trans. Netw. Serv. Manag.*, 16(4):1318–1331, 2019.

[28] Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In *5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net*, 2017.

[29] Martijn Otterlo and Marco Wiering. Reinforcement learning and markov decision processes. *Reinforcement Learning: State of the Art*, pages 3–42, 01 2012.

[30] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017.

[31] Anouar Rkhami, Tran Anh Quang Pham, Yassine Hadjadj-Aoul, Abdelkader Outtagarts, and Gerardo Rubino. On the use of graph neural networks for virtual network embedding. In *2020 International Symposium on Networks, Computers and Communications (ISNCC)*, pages 1–6, 2020.

[32] Meurer et al. Sympy: symbolic computing in python. *PeerJ Computer Science*, 3:e103, January 2017.

[33] Ghina Dandachi, Sophie Cerf, Yassine Hadjadj Aoul, Abdelkader Outtagarts, and Éric Rutten. A robust control-theory-based exploration strategy in deep reinforcement learning for virtual network embedding. *Comput. Networks*, 218:109366, 2022.

[34] Farah Slim, Fabrice Guillemin, Annie Gravey, and Yassine Hadjadj Aoul. Towards a dynamic adaptive placement of virtual network functions under ONAP. In *2017 IEEE Conference on Network Function Virtualization and Software Defined Networks, NFV-SDN 2017, Berlin, Germany, November 6-8, 2017*, pages 210–215. IEEE, 2017.