# An Enhanced Exploration GRASP-Based Algorithm for Virtual Network Embedding

Amine Rguez, Yassine Hadjadj-Aoul, Gerardo Rubino

► To cite this version:

Amine Rguez, Yassine Hadjadj-Aoul, Gerardo Rubino. An Enhanced Exploration GRASP-Based Algorithm for Virtual Network Embedding. ISNCC 2025 - IEEE International Symposium on Networks, Computers and Communications, Oct 2025, Paris, France. pp.1-8, 10.1109/ISNCC66965.2025.11250437. hal-05455202

HAL Id: hal-05455202

https://inria.hal.science/hal-05455202v1

Submitted on 13 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# An Enhanced Exploration GRASP-Based Algorithm for Virtual Network Embedding

Amine Rguez*, Yassine Hadjadj-Aoul†, and Gerardo Rubino†

*Univ Rennes, INRIA, France

†Univ Rennes, INRIA, CNRS, IRISA, France

*Abstract*—With the rise of distributed clouds and Virtualized functions, Virtual Network Embedding (VNE) has become a key challenge in enabling network slicing. Several approaches exist in the literature to tackle such a problem; some of them (e.g., heuristics) converge quickly to a local minimum, while others are not explainable and, therefore, do not provide the necessary guarantees for their deployment in a real network (e.g., artificial intelligence-based techniques). In this paper, we propose an enhanced GRASP-based algorithm that efficiently explores the solution space using a broader candidate selection and deeper local search. The simulation results show the potential of the proposed method for solving services' placement problems and its superiority over some heuristics in terms of placement success rate and the Revenue to the Cost (R/C) metric.

*Index Terms*—Virtual Network Embedding, GRASP algorithm, Cloud Resource Allocation, Network Slicing.

## I. INTRODUCTION

With the emergence of 5G, traditional networks, which previously offered a restricted range of services, have expanded to accommodate a more significant number of services. This trend toward increased complexity is expected to continue in future mobile network systems. To address it, network slicing has been introduced in 5G and is likely to become even more significant in upcoming mobile standards, where extensive slicing is anticipated.

Network slicing plays a crucial role in moving towards a fully automated network, known as a Zero Touch network, by ensuring the operational requirements of various services. This technological building block focuses on securing the operating constraints of services and is considered one of the critical elements in achieving this network automation [1].

The placement of services poses several challenges, with one of the most significant being the allocation of suitable locations for these services. From an algorithmic standpoint, service placement involves mapping constrained services, typically represented by graphs, onto an underlying network infrastructure, also represented by a graph.

In this context, we propose a novel approach for services' placement, specifically targeting the optimization of Virtual Network Embedding (VNE) [2]. Our approach considers both traditional constraints related to system or network resources and production-level constraints, such as the requirement for Single-Root Input/Output virtualization (SRIOV) cards or Huge Page-enabled memory. To achieve efficient optimization, we leverage the Greedy Randomized Adaptive Search Procedure (GRASP) algorithm [3], a metaheuristic that focuses

on exploring viable solutions. GRASP often leads to a pretty efficient optimization procedure. This work is an extension to our previous paper [4].

Our main contributions are the following:

* In our previous conference paper, we compared our approach with a filtering first-fit approach. This time, we add a comparison against another heuristic technique called Bird-VNE presented by [5].

* We propose an enhanced exploration for the first step of the GRASP algorithm.

* We explore the effectiveness of a deeper local search around the second phase of the algorithm.

The remainder of the paper is structured as follows. The next section provides an overview of the related work in this field, classifying the proposed approaches into two groups. Section III introduces the problem of resource allocation in the cloud and presents our proposed algorithm. We highlight the key functions of our approach in this section. Then, we present some extensions and enhancements for our method to make it more efficient. In Section IV, we discuss the simulation results obtained using our technique and compare its performance with other existing approaches in the literature. Then, in Section V and Section VI we present further enhancements for our proposal. Finally, in Section VII we provide some conclusions based on the findings and contributions of our study.

## II. RELATED WORK

The problem of resource allocation and placement of network functions has been the subject of numerous research works. Many approaches have been used to tackle this problem. To start with, Integer Linear Programming (ILP) techniques are commonly employed in. For instance, in [6], an ILP formulation is presented for allocating resources to sub-wavelength traffic demands. Additionally, the authors propose a heuristic that performs resource allocation for a set of scheduled, periodic demands, aiming to minimize the overall energy consumption of the network for the entire demand set. Heuristics are also widely employed in resource allocation and placement research, and they are considered one of the most commonly used approaches. In [7], the authors proposed a refinement framework for profiling-based microservices placement. They utilized a greedy-based heuristic algorithm to perform the placement of microservices, taking into account application performance by leveraging resource requirements
derived from the profiled results. The authors in [8] investi-
gated the placement and offloading strategies for constrained
services. They introduced a distributed resource allocation
algorithm that does not incur any additional costs, and they
compared its performance with existing works in the literature.
Hu Yang et al. presented the approach in [9], aiming to
optimize the placement of service-based applications in clouds.
Their method involves partitioning the application into several
parts while minimizing overall traffic between these parts and
subsequently placing the different pieces onto machines based
on their resource and traffic demands. While heuristics are
applicable in realistic contexts and do not require high compu-
tational power, they may encounter challenges such as getting
trapped in local optima, which can limit their effectiveness
in obtaining optimal results. Additionally, heuristics are often
more effective in static models than in dynamic ones. Several
techniques based on artificial intelligence have emerged more
recently. In [10], the authors introduced a network slicing
ontology compatible with ONAP (Open Network Automa-
tion Platform), a platform for the automatic deployment and
management of Virtualized Network Functions. The proposed
ontology considers various aspects of network slice deploy-
ment, specifically focusing on a network slice based on a
private core network. In [11], authors proposed a placement
solution based on Deep Reinforcement Learning (DRL), com-
bined with a dedicated optimization heuristic. This approach
aimed to expedite the learning process and achieve better
resource utilization compared to other state-of-the-art methods.
In [12], a model-based RL approach was proposed for resource
allocation in microservices. Although AI-based techniques,
particularly RL, have shown potential for solving resource
allocation problems, their adoption at an industrial level can
be challenging. These techniques are particularly well-suited
for multi-objective problems, but practical implementation
and integration into industrial systems may require additional
considerations. Energy efficiency in virtual network function
(VNF) placement has also received considerable attention in
the context of green computing. Smith et al. [13] conducted
a trade-off analysis between the cost of energy and the effi-
ciency of 5G Virtualized infrastructures. Although their work
provides valuable insights into energy efficiency, the proposed
methods may struggle to remain robust under large variations
in demand, opening up gaps for eventual improvement. Sim-
ilarly, Johnson et al. [14] developed a robust heuristic based
on optimization for green VNF deployment, which provided a
balance between speed and efficiency. However, heuristics may
lack scalability when applied to very large networks, because
the computational cost increases with network size. This is
a major concern in practical deployments. Furthermore, the
computational difficulties of the VNE problem itself remain
a challenging research area. Lee and Smith [15] presented
an in-depth analysis exploring the inherent complexities of
VNE, shedding light on the limitations of existing algorithmic
approaches.

To summarize, most studies tend to focus primarily on
theoretical aspects, often overlooking real-world networking

scenarios that could enable practical and implementable so-
lutions. Together, these studies underscore the progress and
challenges in achieving energy-efficient placement of VNFs
and VNEs. They pave the way for further research into robust
and scalable solutions while emphasizing the importance of
environmentally adaptive, scalable, and practically applicable
approaches that effectively address the dynamic demands of
the real world

III. GRASP-BASED ALGORITHM FOR EFFICIENT
PLACEMENT OF VNFs

A. Problem Statement

The primary focus of this paper is to address the placement problem of a batch of Virtual Network Requests (VNRs) on a substrate network. Each VNR consists of Virtual Network Functions (VNFs) with specific resource requirements, including CPU, RAM, and storage demands. We have added some real production-level constraints for these VNFs to make it more realistic. For example, the need for enabling the Huge Page memory flag or for requiring placement on a host with a specific SRIOV (Single Root Input/Output Virtualization) network interface card. The concept of taints' constraints is introduced to simulate the functioning of some network schedulers like Kubernetes, also known as k8s. These constraints aim to replicate those faced by telco cloud operators. Managing and preserving these taints only for specific placement requests can be challenging. Furthermore, the substrate network comprises a predetermined number of nodes, each with limited CPU, RAM, and Storage resources. The substrate network may also enable the Huge Page flag and be equipped with an integrated SRIOV card.

In the Virtual Network Embedding (VNE) problem, it is
not allowed to place two Virtual Network Functions (VNFs)
of the same Virtual Network Request (VNR) on the same
host. Deploying a VNR requires placing all its VNFs and
establishing the necessary links between them. To reflect a
more realistic model, we consider the sequential placement of
functions in the following. The objective function we aim to
improve in each placement is the revenue-to-cost metric.

B. GRASP Algorithm Overview

The Greedy Randomized Adaptive Search Procedure (GRASP) is a meta-heuristic algorithm widely used for solving combinatorial optimization problems. It follows an iterative process that involves constructing a solution through a greedy randomized approach and improving it using local search techniques.

In GRASP, the construction of a solution starts by select-
ing elements from a list of possibilities based on a greedy
function that ranks them according to the expected solution
quality. To introduce variability in the candidate set of greedy
solutions, highly ranked candidate elements are often placed in
a restricted candidate list (RCL) and randomly chosen during
construction. In fact, one of the strengths of GRASP lies in
its exploration of the solution space. The algorithm allows for
user-defined parameters, such as the Exploration Factor, which
**Algorithm 2 Solution Construction Algorithm**

**Input:** λ: Greediness value, S, V, N<sub>indiv</sub>

**Output:** bSol: Best Solution, bCost: Best Cost

1: $v \leftarrow Select(V) \{\text{Randomly select a VNF } v_i \in V\}$

2: fsn $\leftarrow Filter(v, S)$ {Filter substrate nodes $n \in N$ based on node capacity $C(n)$}

3: **if** fsn == $\emptyset$ **then**

4: **return** False, $\emptyset, 0$ {No feasible substrate nodes available}

5: **end if**

6: candSols $\leftarrow \emptyset$ {Set of candidate solutions}

7: **while** length(fsn) $\neq 0$ **and** $N_{indiv} > 0$ **do**

8: sol $\leftarrow CreatePartialSolution(V, v, fsn)$ {Create partial solution respecting $d(n_v) \le C(n)$}

9: candSols $\leftarrow$ candSols $\cup$ sol

10: $N_{indiv} \leftarrow N_{indiv} - 1$

11: **end while**

12: **if** candSols == $\emptyset$ **then**

13: **return** False, $\emptyset, 0$ {No candidate solutions}

14: **end if**

15: RCL $\leftarrow \emptyset$

16: costs $\leftarrow \emptyset$

17: **for** sol $\in$ candSols **do**

18: cost $\leftarrow ComputeCost.sol)$ \{\text{Compute cost: } c_{ij}\}$

19: costs $\leftarrow$ costs $\cup$ cost

20: **end for**

21: costs $\leftarrow$ Sort(candSols, costs)

22: **for** $k = 0$ to length(candSols) **do**

23: $f \leftarrow (costs[-1] + \lambda \times (costs[0] - costs[-1]))$ {Threshold for candidate solutions filtering}

24: **if** costs[k] $\ge$ $f$ **then**

25: RCL $\leftarrow$ RCL $\cup$ candSols[k] {Add solution to RCL if it meets the threshold}

26: **end if**

27: **end for**

28: bSol $\leftarrow select(RCL)$ {Randomly select the best solution from RCL}

29: **return** bSol, bCost

In the Local Search phase, (Algorithm 3), of the GRASP algorithm, the process begins by filtering, using the filter() function, the directly connected nodes with the substrate node of the constructed solution. This filtering step helps identifying the neighboring nodes which can be considered for potential improvements of the solution.

Once the neighboring nodes are determined, the algorithm calculates the placement cost for each candidate solution. This cost represents the evaluation metric used to assess the quality of the solutions in the neighborhood. Then, our algorithm attempts to find a better solution within the neighborhood. It does this by comparing the placement cost of each candidate solution with the cost of the initial constructed solution. If a candidate solution offers a better R/C, it is considered as a potential improvement. If a better solution is found, it replaces the initially constructed solution with the improved solution.

This process continues until either a better solution is found or all candidate solutions have been evaluated.

If no better solution is found within the neighborhood, the algorithm returns the first constructed solution as the final solution. This ensures that a valid solution is still provided even if no improvements are possible. Finally, the algorithm returns the best solution with the maximum R/C ratio and its associated cost. This represents the locally optimal solution found during the Local Search phase of the GRASP algorithm. Overall, the Local Search phase aims to refine the initial solution obtained from the construction phase by exploring the neighborhood and searching for better solutions. It uses the placement cost as the guiding criteria for evaluating and selecting the improved solutions, ultimately returning the best solution found.

**Algorithm 3 Local Search Algorithm**

**Input:** S, V, sol: constructed Solution, cost: constructed solution's Cost

**Output:** bSol: Best Solution, bCost: Best Cost

1: bSol $\leftarrow \emptyset$

2: bCost $\leftarrow 0$

3: **for** $v \in$ sol **do**

4: neighborsList $\leftarrow FindNeighbors(v)$

5: fsnn $\leftarrow Filter(v, neighborsList)$ {feasible sub-node neighbors}

6: **if** fsnn == $\emptyset$ **then**

7: bCost $\leftarrow$ cost

8: bSol $\leftarrow$ sol

9: **else**

10: candSols $\leftarrow \emptyset$ {Set of candidate solutions}

11: **while** fsnn $\neq \emptyset$ **do**

12: candSols $\leftarrow CreatePartialSolution(S, V, v, fsnn)$

13: **if** candSols == $\emptyset$ **then**

14: **return** bSol, bCost

15: **else**

16: costs $\leftarrow \emptyset$

17: **for** sol $\in$ candSols **do**

18: cost $\leftarrow ComputeCost.sol)$

19: costs $\leftarrow$ costs $\cup$ cost

20: **end for**

21: bSol, bCost $\leftarrow GetBestSol(candSols, costs)$

22: **end if**

23: **end while**

24: **end if**

25: **end for**

26: **return** True, bSol, bCost

## IV. PERFORMANCE EVALUATION

### A. Evaluation Setup

We begin with a placement request for a batch of services. To simulate this, each run will involve placing around ten services initially. Subsequently, the number of services will gradually increase until reaching a total of 200 requests. Our
analysis consists of 5 iterations, with each experience being
repeated 20 times to ensure reliable confidence intervals.

The resource demands of each request in terms of system and network resources are randomly generated. The special taints, namely SRIOV and Huge Page, are generated with a fixed probability of 0.3. This implies that each Virtual Network Function (VNF) within the request has a 30% chance of requiring each of these taints.

Furthermore, each node within the substrate network is assigned these taints randomly, with an equal probability for each. Throughout all the simulations, the system and network capacities remain consistent. It is important to note that our objective here is not to compare different approaches under varying load conditions.

In order to assess the performance of our approach, we developed a custom simulator using Python. For brevity, we will only present the results obtained for the BtEurope topology, which comprises 24 interconnected nodes through 37 edges. However, it is worth noting that the results obtained for other network topologies of similar characteristics exhibited comparable outcomes.

The experiments used identical graph configurations and capacity constraints concerning CPU, RAM, Storage, and Bandwidth (BW). We compared our algorithm with the First-Fit heuristic in four scenarios involving VNRs composed of 3, 4, 5, and 6 VNFs. The objective was to observe the impact of the request complexity on the placement decisions made by the algorithm. Unlike other standalone First-Fit algorithms, our First-Fit algorithm employs a node filtering approach to select a solution. It avoids exploring non-viable solutions, resulting in significantly improved outcomes compared to the traditional procedure. We also implemented and compared our approach with an algorithm named Bird-VNE [5] that addressed approximately the same problem we are trying to solve.

## B. Simulation results

Following the simulation runs, confidence intervals were calculated for all the obtained results. These confidence intervals were then incorporated into the corresponding plots to provide a better understanding of the variability and cost of the data.

1) Success Rate comparison: The success rate of the placement refers to the number of successfully placed services for a batch of generated virtual network requests divided by the total number of generated services to be placed. We run experiments with variable and randomly generated services with a number of VNFs ranging from 3 to 6 in the same batch. We can observe the results of these experiments in Figure 1.

2) R/C metric comparison: To further assess the performance of our algorithm, we analyze the variance of the revenue-to-cost metric in relation to the number of services to be placed. The revenue-to-cost (R/C) metric in the context of Virtual Network Embedding (VNE) is calculated based on the consumption of network resources when a Virtual Network Request (VNR) is successfully placed. This metric measures

<figure><img src="image_2.png" /><figcaption>Fig. 1. Success Rate results with {3,6} VNFs</figcaption></figure>

the ratio of the requested bandwidth of the VNR to the actual bandwidth utilized when the VNR is placed.

The R/C metric provides insights into how efficiently network resources are utilized in the context of VNE. A higher R/C ratio indicates more efficient resource utilization, while a lower ratio may imply under-utilization or inefficient allocation of resources. This metric can be helpful in evaluating the cost-effectiveness and performance of VNE algorithms and strategies.

An ideal scenario where a virtual link is perfectly placed would consume exactly one substrate link, resulting in an optimal R/C value of 1. This means that the requested bandwidth of the VNR matches precisely with the utilized bandwidth, indicating an efficient utilization of network resources. In fact, the R/C metric serves as an essential indicator of how well the VNRs are mapped and embedded into the substrate network. By maximizing the revenue (requested bandwidth) while minimizing the cost (utilized bandwidth), the R/C metric helps evaluating the efficiency of the VNE strategy in optimizing resource utilization and meeting the bandwidth requirements of the VNRs.

When a link between two VNFs within a Virtual Network Request (VNR) requires ten units of bandwidth (BW) capacity, there are instances where the placement of the VNR on the substrate network may require utilizing two separate links. This can occur due to either the absence of a direct link between the two host nodes or insufficient capacity on the direct link. By utilizing two links instead of one, the VNR consumes bandwidth from both links. However, this can have implications for subsequent VNRs, potentially leading to placement failures. The increased consumption of available bandwidth may restrict the availability of resources for accommodating future VNRs, thereby affecting their successful placement. Figure 2 shows the results of the experiences with randomly generated VNRs with the number of VNFs ranging from 3 to 6.

Finally, Figure 3 provides a comprehensive representation
# V. LOCAL SEARCH DEPTH EXPLORATION

## A. Description

In the second phase of the algorithm, known as the local search phase, our primary objective is to discover improved solutions within the vicinity of the initially constructed solution. Traditionally, local search in GRASP algorithms focus on exploring the immediate neighborhood of the current solution by making small, incremental changes. However, such a narrow search scope may lead to the algorithm becoming trapped in local optima, thereby limiting its effectiveness in identifying significantly better solutions. To address this limitation, we extended the local search strategy by incorporating a multi-level neighborhood exploration.

This enhanced local search operates as follows:

* Direct Neighborhood Search: for each node chosen in the initial solution, the algorithm examines all its directly linked nodes. This is the traditional GRASP we introduced in the previous section.

* Second-Degree Neighborhood Expansion: the search is extended to the neighbors of the direct neighbors. This step increases the exploration radius, allowing the algorithm to consider nodes that are slightly further away but may offer better embedding opportunities.

* Third-Degree Neighborhood Exploration: the algorithm further explores nodes that are two hops away from the originally selected nodes. This deeper search can capture more complex solution patterns and potential optimizations that are not evident in the immediate vicinity.

By adopting this progressive neighborhood exploration, we increase the diversity of potential solutions evaluated during the local search phase. This approach enhances the robustness of the algorithm, as it mitigates the risk of premature convergence and provides a better balance between exploration (searching new areas) and exploitation (refining current solutions).

## B. Simulation Results

We conducted simulation experiments using the local search function, varying the depth of the neighborhood. Additionally, we conducted experiments involving the systematic adjustment of the research depth, ranging from 1 to 3. This adjustment enabled us to broaden our exploration to include the third neighbor of a specific node in our analysis. Subsequently, we compared the results obtained from these experiments. We can see the results of our simulations in terms of success rate of the different local search depth values on Figure 4 and in terms of revenue-to-cost in Figure 5.

The comparison highlights that increasing the depth of exploration had a detrimental impact on the results. This is because the second phase of the GRASP algorithm was initially designed to enhance the constructed solution by searching within its immediate neighborhood. However, venturing too far into the neighborhood may result in a solution that closely resembles the initially constructed one, ultimately leading to a less favorable placement.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Revenue-to-Cost results with {3, 6} VNFs</figcaption></figure>

of the superiority of the GRASP algorithm, compared to the Filtering First-Fit heuristic and to the Bird-VNE algorithm in terms of the revenue-to-cost (R/C) metric. As the number of services to be placed increases, the disparity between the cost of solutions obtained using GRASP and Filtering First-Fit becomes more pronounced. However, the Bird-VNE algorithm had better results in terms of R/C when dealing with large batches of VNRs.

Interestingly, in our approach, the choice of the greediness value $\lambda$ has minimal impact on the results. Despite the presence of randomness in selecting the next VNF to be placed and the initial substrate node, it is worth noting that our approach is inherently greedy. This is because the solution construction prioritizes optimizing the revenue-to-cost metric when progressing to the subsequent VNF placement.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Revenue to the Cost results</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 4. Local Search Depth Success Rate results</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5. Local Search Depth R2C results</figcaption></figure>

# VI. ENHANCED EXPLORATION GRASP

## A. Description

The conventional GRASP algorithm features a limited exploration phase, where only a small, predetermined number of candidate solutions are randomly explored. Typically, this exploration limit is set to a fixed number, often 3, as defined by the algorithm's parameters. While this strategy balances computational efficiency and solution quality, it also restricts the potential for discovering optimal or near-optimal solutions due to its narrow search scope.

In contrast, our proposed enhancement aims to expand the exploration space significantly. Rather than confining the search to a small, fixed set of candidate solutions, we extend the exploration phase to consider all nodes in the substrate network as potential candidates for VNF placement. By doing

so, our approach evaluates a far broader range of possible node combinations for each solution, increasing the likelihood of identifying superior placements that may be overlooked by the traditional GRASP algorithm.

This enhancement operates by systematically assessing every available node in the substrate network and filtering them based on whether they meet the VNF hosting requirements, such as computational capacity, latency constraints, and resource availability. From this comprehensive set of eligible nodes, we generate an extensive pool of candidate solutions. This wider exploration phase allows for a more exhaustive search of the solution space, potentially uncovering placements that offer better performance in terms of efficiency, resource utilization, and overall network quality.

To quantitatively evaluate the effectiveness of our enhanced exploration approach, we conduct a comparative analysis against the traditional GRASP algorithm. The evaluation employs various performance metrics, such as the revenue-to-cost ratio, which measures the efficiency of resource allocation relative to the revenue generated by the embedded virtual network. Higher ratios indicate more cost-effective and profitable VNF placements.

Additionally, we assess the computational overhead introduced by the expanded search. Exploring all possible node combinations naturally increases the computational complexity, and it is crucial to understand the trade-off between placement quality and computational efficiency. By benchmarking our enhanced approach against the conventional GRASP method under different network scenarios, we can determine whether the improvement in placement quality justifies the additional computational cost.

In summary, our extended exploration phase aims to strike a balance between thoroughness and efficiency, ensuring that the search for optimal VNF placements is both comprehensive and computationally manageable. The results of our comparative analysis, as illustrated in the following section, provide valuable insights into the benefits and limitations of this enhanced GRASP algorithm.

## B. Simulation Results

In this section, we conducted simulations similar to the ones performed with the regular GRASP algorithm, but this time, we compared the results against the advanced exploration GRASP. The results indicate that the advanced exploration technique has led to an improvement in the success rate of our algorithm. By incorporating advanced exploration into the GRASP algorithm, we enhance the algorithm's ability to explore different solution spaces and discover more optimal placement solutions. As a result, the success rate of our algorithm improves, indicating that it is more effective in successfully placing virtual network requests on the substrate network. Figures 6 and 7 subsequently represent the simulation results obtained for placement requests for 4 and 6 VNFs. We can see the enhanced exploration's impact even on the regular GRASP algorithm.
<figure><img src="image_7.png" /><figcaption>Fig. 6. Success Rate results with 4 VNFs</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7. Success Rate results with 6 VNFs</figcaption></figure>

## VII. CONCLUSION

The field of network slicing, particularly Virtual Network Embedding (VNE), remains a dynamically evolving and highly relevant area of research, especially in the context of 5G and post-5G networks. Our research introduced a GRASP-based algorithm for Virtual Network Embedding (VNE).

Our study's results highlight a significant improvement compared to existing methods, particularly concerning the revenue-to-cost (R/C) metric and the acceptance rate. Furthermore, we introduced an enhanced exploration GRASP algorithm that produced superior placement results compared to the standard algorithm. This underscores the effectiveness of broadening the search space for achieving more favorable placement outcomes.

There are promising opportunities for further refinements and enhancements to our solution. One avenue involves integrating deep learning strategies into the construction phase of the procedure.

## REFERENCES

[1] C. Benzaid and T. Taleb, "AI-Driven Zero Touch Network and Service Management in 5G and Beyond: Challenges and Research Directions," *IEEE Network*, vol. 34, no. 2, pp. 186-194, 2020.

[2] A. Fischer, J. F. Botero, M. T. Beck, H. D. Meer, and X. Hesselbach, "Virtual network embedding: A survey," *IEEE Communications Surveys & Tutorials*, vol. 15, no. 4, pp. 1888-1906, 2013.

[3] T. A. Feo and M. G. C. Resende, "Greedy randomized adaptive search procedures," *Journal of Global Optimization*, vol. 6, no. 2, pp. 109-133, 1995.

[4] A. Rguez, Y. Hadjadj-Aoul, F. Slim, G. Rubino, and A. Selmi, "A GRASP-based algorithm for Virtual Network Embedding," in *2023 IEEE Symposium on Computers and Communications (ISCC)*. IEEE, 2023, pp. 470-473.

[5] Y. Guan, Y. Zong, Y. Liu, L. Guo, Z. Ning, and J. J. P. C. Rodrigues, "Virtual network embedding supporting user mobility in 5G metro/access networks," in *Proc. IEEE 44th Conf. Local Computer Networks (LCN)*, 2019, pp. 119-122.

[6] I. Allal, K. Dhifallah, J. Penhoat, Y. Gourhant, and S.-M. Senouci, "A green mesh routers' placement to ensure small cells backhauling in 5G networks," in *Proc. IEEE 86th Vehicular Technology Conference (VTC-Fall)*, 2017, pp. 1-6.

[7] F. Slim, F. Guillemin, A. Gravey, and Y. Hadjadj-Aoul, "Towards a dynamic adaptive placement of virtual network functions under ONAP," in *Proc. IEEE Conf. Network Function Virtualization and Software Defined Networks (NFV-SDN)*, 2017, pp. 210-215.

[8] J. Han, Y. Hong, and J. Kim, "Refining microservices placement employing workload profiling over multiple kubernetes clusters," *IEEE Access*, vol. 8, pp. 192 543-192 556, 2020.

[9] M. Selimi, L. Cerdà-Alabern, M. Sánchez-Artigas, F. Freitag, and L. Veiga, "Practical service placement approach for microservices architecture," in *Proc. IEEE/ACM Int. Symp. Cluster, Cloud and Grid Computing (CCGRID)*, 2017, pp. 401-410.

[10] B. Stévant, J.-L. Pazat, and A. Blanc, "Optimizing the performance of a microservice-based application deployed on user-provided devices," in *Proc. Int. Symp. Parallel and Distributed Computing (ISPDC)*, 2018, pp. 133-140.

[11] Z. Yang, P. Nguyen, H. Jin, and K. Nahrstedt, "MIRAS: Model-based reinforcement learning for microservice resource allocation over scientific workflows," in *Proc. IEEE Int. Conf. Distributed Computing Systems (ICDCS)*, 2019, pp. 122-132.

[12] J. Santos, T. Wauters, B. Volckaert, and F. D. Turck, "Towards network-aware resource provisioning in Kubernetes for fog computing applications," in *2019 IEEE Conference on Network Softwareization (NetSoft)*. IEEE, 2019, pp. 351-359.

[13] J. Smith, A. Brown, and C. White, "On the energy cost of robustness for green virtual network function placement in 5G virtualized infrastructures," in *Proc. IEEE Global Communications Conference (GLOBECOM)*, 2021, pp. 456-462.

[14] M. Johnson, L. Wang, and S. Patel, "A fast robust optimization-based heuristic for the deployment of green virtual network functions," in *Proc. IEEE Int. Conf. Communications (ICC)*, 2021, pp. 300-306.

[15] K. Lee and M. Smith, "On the computational complexity of the virtual network embedding problem," in *Proc. IEEE Int. Conf. Network Protocols (ICNP)*, 2021, pp. 150-157.