FlagVNE: A Flexible and Generalizable Reinforcement Learning Framework for Network Resource Allocation

1 Introduction

Network virtualization (NV) emerges as a pioneering technology that facilitates dynamic management of Internet architecture, which finds applications in 5G networks and cloud computing [Zhuang et al., 2020]. Through network slicing and shared infrastructure, NV enables the deployment of multiple user-submitted virtual network requests (VNRs) within the same physical network, thereby accommodating diverse network service requirements of users [Yang et al., 2021; Chen et al., 2022b]. The primary challenge in NV involves the embedding of VNRs within a physical network, known as virtual network embedding (VNE), an NP-hard combinatorial optimization problem [Rost and Schmid, 2020].

∗Chao Wang and Hui Xiong are both corresponding authors

Effective resource allocation for VNRs is essential to improve the quality of service and the revenue of Internet service providers (ISPs) [Wang et al., 2021b; Chen et al., 2022a]. Regrettably, it is hard to address the VNE problem involving tackling combinatorial explosion and differentiated demands [Fischer et al., 2013; Yang et al., 2022b]. On the one hand, the solution space of VNE is extensive, encompassing vast permutations of VNRs within the underlying physical network. Consequently, a comprehensive exploration of this expansive solution space becomes imperative to determine superior solutions. On the other hand, due to specific requirements of user service, the integration of diverse VNR topologies and their associated resource demands is dynamic. VNRs of varying sizes manifest unique complexities, rendering a one-size-fits-all strategy inadequate to effectively manage the inherent variability in such circumstances.

Recently, reinforcement learning (RL) has shown promising potential for the VNE problem [Yan et al., 2020; He et al., 2023b; Zhang et al., 2023]. RL approaches model the solution construction process of each VNR as Markov decision processes (MDPs), which can automatically build efficient solving policies. Unlike supervised learning relying on labeled data, RL facilitates the learning of effective heuristics through interactions with the environment. However, most existing RL-based VNE approaches are still plagued with some significant issues. Firstly, these approaches commonly adhere to a unidirectional action design within the MDP, i.e., presupposing a fixed decision sequence for virtual nodes, and subsequently designating a physical node to host each virtual node sequentially. Such unidirectional action schema significantly limits the available action space, consequently constraining the searchability of the agent and impeding the efficacy of exploring solution space. Secondly, conventional RLbased methods usually just train a single general policy, disregarding the distinctive complexities of VNRs with varying sizes in practice. Treating variable-sized VNRs equally poses challenges in achieving balanced learning of cross-size strategic knowledge and hinders the ability to generalize across VNRs of differing sizes. Thirdly, the direct training of multiple policies tailored to different VNR sizes slowly adapts to unseen distributions. In particular, training specific policies for large-sized VNRs from scratch tends to be stuck in the local optimum, due to the high complexity and challenges in exploring feasible solutions. These difficulties inevitably exert negative impacts on overall system performance. We conduct a preliminary study to highlight our motivations and latent challenges, which is detailed in Appendix A.

In this paper, we propose a novel FLexible And Generalizable RL framework for the VNE problem, named FlagVNE. Our framework aims to enhance the searchability and generalizability of RL-based VNE methods while achieving rapid adaption to the unseen distribution of VNR sizes. Specifically, our contributions are summarized as follows. (1) We propose a bidirectional action-based MDP modeling approach to enable the joint selection of virtual and physical nodes, enhancing the flexibility of agent exploration and exploitation. This method offers superior searchability and is proven theoretically. To handle the resulting large and changeable action space, we abstract it as two dependent aspects and design a hierarchical decoder with a bilevel policy, ensuring adaptive action probability distribution generation and high training efficiency. (2) We propose a metaRL-based training method to enable efficient acquisition of multiple size-specific policies and quick adaptation to new sizes. A meta-policy is trained to grasp cross-size knowledge for different VNR sizes and then fastly fine-tuned to develop size-specific policies for each VNR size, even unseen sizes. Specially, due to difficult exploration and prone to suboptimal convergence, using large-sized VNRs for initial meta-learning yields inferior knowledge, impairing the metapolicy and generalization. Thus, we develop a curriculum scheduling strategy that gradually incorporates larger VNRs, alleviating suboptimal convergence. (3) Finally, we conduct experiments on the simulation platform to mimic various network systems and extensive results demonstrate the superiority of FlagVNE in terms of multiple key indicators, compared to state-of-the-art (SOTA) heuristics and RL-based methods.

2 RelatedWork

Traditional Methods for VNE. Initially, the VNE problem was tackled using exact methods such as integer linear programming [Shahriar et al., 2018], which provides optimal solutions through exact solvers. However, these exact algorithms proved impractical for real-world scenarios due to their time-consuming nature. Thus, numerous heuristic algorithms have been proposed to find solutions in an acceptable time [Su et al., 2014; Jin et al., 2020; Fan et al., 2023]. Among these approaches, node ranking is a prevalent strategy, which ranks virtual and physical nodes to determine the decision sequence and the matching priority, respectively. For example, [Zhang et al., 2018] ranked nodes based on a node resource management (NRM) metric, and [Fan et al., 2023] proposed a node essentiality assessment (NEA) metric considering topology connectivity. Additionally, [Dehury and Sahoo, 2019] designed VNE algorithms based on metaheuristics, such as particle swarm optimization (PSO). However, these algorithms heavily rely on manual designs and are usually tailored to specific scenarios, limiting their performance in general cases.

Learning-based Methods for VNE. Recently, machine learning techniques have been used to solve VNE, leading to faster and more efficient solutions [Blenk et al., 2018; Geng et al., 2023; He et al., 2023b]. Particularly, RL has demonstrated significant potential as an intelligent decisionmaking framework [Liu et al., 2023; Yang et al., 2022a], which can effectively solve VNE with MDP modeling. In this paper, we unify most existing RL-based methods [Xiao et al., 2019; Wang et al., 2021c; Yan et al., 2020; Yao et al., 2020; Zhang et al., 2022; Zhang et al., 2023] into a general framework comprised of three key components: MDP modeling, policy architecture, and training methods. These methods model the process of VNE solution construction as unidirectional action-based MDPs, where a physical node is chosen to host a be-placing virtual node, and the decision sequence of virtual nodes is fixed. Then they build policy models with various neural networks and train a single general policy to deal with VNRs of varying sizes. For instance, [Xiao et al., 2019] used multilayer perception (MLP) as a policy model and trained it with policy gradient (PG) algorithm, [Zhang et al., 2023] designed a policy model with MLP and graph convolutional network (GCN) [Kipf and Welling, 2017] and trained it with asynchronous advantage actor-critic (A3C) [Mnih et al., 2016]. However, existing RL-based VNE methods suffer from limited searchability and generalizability due to their unidirectional action design and one-size-fits-all training policy, ultimately affecting overall performance.

3 Preliminaries

3.1 ProblemDefinition

As shown in Fig. 1, in a practical network system, users' service requests arriving continuously are represented as VNRs. We collect all VNRs with a set V. Mapping these VNRs onto physical networks managed by ISPs is known as VNE, crucial in managing the quality of various network services [Chen et al., 2020; Wang et al., 2023a; Chen et al., 2022c].

System Modeling. Physical network is formulated as a weighted undirected graph G p = (N p , Lp ), where N p is the set of physical nodes, Lp is the set of physical links. Each physical node np ∈ N p is equipped with multiple resource capacities {C(np ), ∀C ∈ C}, where C is the set of node resource types, and each physical link lp ∈ Lp has bandwidth capacity B(lp ). In this paper, we consider multidimensional node resources, including the central processing unit (CPU), storage resource, and graphics processing unit (GPU). Similarly, each VNR is modeled as a weighted undirected graph Gv = (N v , Lv , dv ), where N v is the set of virtual nodes and Lv is the set of virtual links, and dv denotes the lifetime of VNR. Once the VNR is accepted, it will be maintained for dv time slots. Each virtual node nv ∈ N v represents a virtual machine with resource demands {C(nv ), ∀C ∈ C} and each virtual link lv ∈ Lv indicates the bandwidth demand B(lv ).

Objective. Acknowledging the stochastic nature of online networking, most existing methods and this work aim to minimize the embedding cost of each VNR onto the physical network, which facilitates long-term performance. The quality of solutions is assessed using the revenue-to-cost ratio (R2C):

Here, REV(G v ) denotes the revenue of the VNR Gv (i.e., the sum of VNR's resource requirements) and COST(G v ) denotes the embedding cost resulting from the solution (i.e., the sum of ISP' resource consumption). Ψ is the binary variable that indicates the feasibility of a solution.

Constraints. The VNR embedding consists of two subprocesses. (1) Node mapping entails assigning each virtual node to a physical node with adequate resources, i.e., C(np ) ≥ C(nv ), ∀C ∈ C, while ensuring one-to-one placement and mutual exclusivity. (2) Link mapping involves finding a physical path for each virtual link, ensuring that the path connects the physical nodes hosting the virtual link endpoints and that each physical link lp in the path has sufficient bandwidth, i.e., B(lp ) ≥ B(lv ). A solution is deemed feasible (Ψ = 1) only when all these constraints are satisfied.

Due to the space limit, we place detailed formulations of VNE's objective and constraints in Appendix B.

3.2 Motivations and Challenges

We conduct a preliminary study placed in Appendix A, and motivate our framework from the following two aspects.

Flexibility of Action Space. Most existing RL-based VNE approaches employ a unidirectional action design, assuming that the decision sequence of virtual nodes is predetermined. However, our analysis in Appendix A.1 reveals that varying the decision sequences of virtual nodes significantly impacts performance. This underscores the necessity of exploring different decision sequences for optimal solutions. Moreover, the fixed decision sequence of virtual nodes lacks the flexibility needed to adapt to the dynamic nature of exploration process. Thus, to enhance the flexibility of exploration and exploitation, we aim to achieve a joint selection of both physical and virtual nodes to eliminate the fixed decision sequence. Nevertheless, it will pose some challenges, such as the difficulty of variable action probability distribution generation and the training efficiency issue caused by large action space.

Generalization of Solving Policy. VNRs of different sizes exhibit distinct complexities, necessitating varied solving strategies. Existing RL-based methods typically use a one-size-fits-all policy to tackle VNRs of varying sizes, leading to generalization issues. To address this, an intuitive approach might be to develop size-specific policies for different VNR sizes. Yet, as observed in Appendix A.2, specific policies for large-sized VNRs trained from scratch often get stuck in local optima due to their high complexity and the difficulty in exploring viable solutions. Their performance is even inferior to that of the general policy for all sizes. Furthermore, this strategy lacks the quick adaptability to handle previously unseen VNR sizes, since it requires extensive data demand.

4 FlagVNE Framework

In this section, we present the proposed RL-based framework for VNE, FlagVNE. As illustrated in Fig. 2, FlagVNE is designed to improve searchability and generalizability while achieving rapid adaptation to unseen distribution.

4.1 Bidirectional Action-basedMDP

We formulate the solution construction process of each VNR as a bidirectional action-based MDP, allowing joint selection of virtual nodes and physical nodes. Specifically, at each decision timestep t, observing the state st of the environment, the agent takes an action at ∼ π(·|st) according to the policy π. Then, the environment will feedback a reward R(st, at) and transit to a new state st+1 ∼ P (st, at) following the transition probability function. During interactions, a trajectory memory D = {s1, a1, s2, a2, · · · } collects state-action pairs. We present these notations in VNE as follows.

State represents the status of the network system at a specific decision timestep t, consisting of the current situation of VNR svt and physical network spt , i.e., st = (svt , spt ), st ∈ S, where S is the state space.

Action is defined as a pair of a virtual node to be placed and a physical node to host, denoted at = (nv , np ), at ∈ A, where nv ∈ N v , np ∈ N p , and A is the action space.

Transition P(st+1 | st, at) refers to the process of placing the virtual node nv to the physical node np and routing the virtual links, resulting in the changes of state from st to st+1. Based on the selected bidirectional action, the environment attempts to place the virtual node nv to the physical node np . If the node placement is successful, the link routing is executed based on the breadth-first search algorithm that finds the shortest physical paths meeting bandwidth demands from np to other physical nodes hosting the virtual node neighbors of nv . If node placement and link routing are successful, the available resource of the physical network is updated with the VNR requirement. Otherwise, the current VNR is rejected.

Figure 2: The overview of the FlagVNE framework. (a) For vary-sized VNRs that continuously arrive at the network system, we consider them as different tasks Mi ∼ p(M) based on their size. We first train a meta-policy πϕ with cross-task knowledge in the meta-learning process, using a curriculum scheduling strategy. Then, we fine-tune it to obtain a set of size-specific sub-policies πθi . This generalizable training method effectively obtains refined solving policies for each VNR size. (b) Within each inner loop, we formulate the solution construction process of each VNR as a bidirectional action-based MDP, which enables the joint selection of virtual and physical nodes. We also design a hierarchical encoder with a bilevel policy to adaptively generate action probability distributions and ensure high training efficiency.

Reward R measures the quality of agent's action at a given state. We define the reward function R as follows:

We design implicit rewards to encourage successful placement with 1/|N v | and punish failure with -1/|N v |. Once the G v is completed embedding, we return R2C(G v ).

Policy is parameterized by θ, which denotes the distributions over the action space under a given state st:

Discount factor λ ∈ (0, 1) balances the importance of immediate rewards versus future rewards. Overall, the optimization objective of RL is to maximize the expected return, i.e., cumulative discounted rewards over timesteps T :

If Jπ ≥ Jπ′ , then we denote it as π ⪰ π′ .

Theorem 1. Given two MDPs with bidirectional and unidirectional action, Mb = ⟨S b ,Ab , P b ,R, λ⟩ and Mu = ⟨S u ,Au , P u ,R, λ⟩, and their optimal policies denoted as π⋆,b and π⋆,u , respectively, we have π⋆,b ⪰ π⋆,u .

See Appendix C for its proof [Sutton and Barto, 2018]. Our bidirectional action enhances flexibility and expands the search space, allowing for a more comprehensive exploration of possible solutions, which offers superior MDP Optimality.

4.2 Hierarchical Policy Architecture

We construct raw features, encode them with a GCN-based encoder, and design a hierarchical decision module to ensure adaptive probability output and training efficiency.

Feature Constructor. We build the feature input for the subsequent encoder from the current state st, which includes the processing status of VNR svt and the current physical network situation spt . With comprehensive information on the current state, the agent gains deeper environmental insight, resulting in better decisions. For the VNR Gvt , the feature constructor takes into account not only various node resource requirements denoted Xv t,N , but also aggregates bandwidth resource requirements into the node features, represented as Xv t,L. These features include essential bandwidth metrics, such as maximum, mean, and sum of bandwidth requirements of virtual links adjacent to one node. To indicate the embedding status, a placement flag Xv t,P is designed for virtual nodes, with a value of 1 indicating that the virtual node has been placed and 0 otherwise. The VNR features Xv t are organized as follows: Xv t = (Xv t,N , Xv t,L, Xv t,P ) ∈ R|N v |×7 .

Similarly, the physical network features Xp t are constructed as follows: Xp t = (Xp t,N , Xp t,L, Xp t,S ) ∈ R|N p |×7 , where Xp t,N denotes available resources of physical nodes, Xp t,L similar toXv t,L denotes aggregated bandwidth availability, and Xp t,S is a selection flag indicating the status of physical nodes. A selection flag value of 1 indicates that a physical node has been selected to host a virtual node and 0 otherwise.

GNN-based Encoder. To encode the features of the virtual network Xv t and the physical network Xp t , into latent representations, Z v t and Z p t , respectively, we adopt a graph neural network (GNN) encoder. First, both Xv t and Xp t undergo the MLP to obtain the initial node representations, denoted I v t and I p t , respectively: I v t =MLP(Xv t ), I p t =MLP(Xp t ).

Then, we consider multiple GCN [Kipf and Welling, 2017] layers as the GNN modules to obtain the latent representations of virtual nodes ˜ Z v t and physical nodes ˜ Z p t : ˜ Z v t = GNN(I v t ,Av ), ˜ Z p t = GNN(I p t ,Ap ), where Av and Ap is adjacency matrixes of virtual and physical networks.

Furthermore, to enhance the feature representation ability, we also employ the residual connection method to combine the output of the GNN module with the initial representation: Z v t = ˜ Z v t + I v t ,Z p t = ˜ Z p t + I p t . Finally, we obtain the representation of each virtual and physical node.

Hierarchical Decoder with Bilevel Policy. In our bidirectional action-based MDP, the action space is represented by the matrix size |N v | × |N p |, reflecting the number of virtual and physical nodes. The variable and often large size of VNRs contribute to the expansive and dynamic nature of the space. To effectively manage this, we develop a hierarchical decoder with a bilevel policy, ensuring high training efficiency and adaptive action probability generation. Specifically, we abstract this task into two dependent aspects: virtual node ordering and physical node placement. Our bilevel policy, π(at|st) = πH (nv |st) · πL(np |st, nv ), consist of a highlevel ordering policy πH (nv |st) and a low-level placement policy πL(np |st, nv ). This hierarchical approach reduces the size of policy distribution from |N v | × |N p | to |N v | + |N p |, thus significantly enhancing training efficiency.

High-level ordering policy selects the appropriate virtual node nvt for placement. Concretely, we use an MLP-based compatibility scoring network (CSN) to calculate the fitness between each virtual node representation and the graph-level representation of the physical network Gpt = GMP(Z p t ). Here, GMP(Z) = 1 |Z| ∑z∈Z z denotes graph mean pooling (GMP), averaging all node representations. Then an MLP is applied to generate compatibility scores for each virtual node:

Although the VNR's sizes are variable, this layer adaptively generates scores with the shape of (1, |N v |). After masking virtual nodes already placed (i.e., setting their scores to -∞ on ˜ Y H ), we apply a softmax function to the resultant score Y H to produce the high-level action probability distribution.

Low-level placement policy identifies a suitable physical node npt for accommodating the to-be-placed virtual node nvt , which is selected by πH . Similarly, we adopt an MLP-based compatibility scoring network to calculate the fitness between the representation of each physical node and the current context representation of virtual network, including the graphlevel representation of virtual network Gvt = GMP(Z v t ) and to-be-placed virtual node's representation znvt :

To avoid unnecessary exploration, we mask the physical nodes that do not have enough resources or have been selected to obtain the final scores Y L. Then, the low-level action probability distribution is generated:

For both two-level probability distributions, we employ the sampling and greedy strategy to select actions during the training and inference phases, respectively.

4.3 Generalizable TrainingMethod

Training a general policy for VNRs of varying sizes leads to imbalanced learning of cross-size strategy and generalization issues. Conversely, individualized training of multiple policies for each size is slow to adapt to new sizes, in which policies for large-sized VNRs are prone to suboptimal. To address this, we develop a meta-RL-based training method with a curriculum scheduling strategy. As illustrated in Algorithm 1 (see Appendix D), our method enables efficient training of multiple size-specific policies and quick adaptation to new sizes, while balancing the learning process across tasks of varying difficulty and avoiding suboptimal convergence.

Meta-RL for VNE. We treat VNRs of different sizes as distinct tasks and formulate them as multiple MDPs following a distribution Mi ∼ p(M). Note that this distribution of VNR size is bounded and always obviously smaller than the number of physical nodes, following the network service orchestration standards [Zhuang et al., 2020]. We adopt model-agnostic meta-learning (MAML) as the basic training method [Finn et al., 2017]. MAML facilitates the learning of a meta-policy that can be swiftly fine-tuned on new tasks with only a few training samples, which improves generalizability and adaptability. This training process comprises two stages as follows. Firstly, during the meta-learning process, we iteratively execute the inner loops and outer loops to derive a well-trained meta-policy πϕ with cross-task knowledge. Secondly, in the fine-tuning process, we leverage taskspecific experiences to fine-tune the meta-policy to a set of size-specific policies πθi solely through inner loops.

Concretely, in the inner loop, the meta-policy πϕ is updated to accommodate a specific task Mi by performing gradient descents with the learning rate α and task-specific data Di:

Here, L(·) follows the objective of proximal policy optimization (PPO) algorithm [Schulman et al., 2017]:

where ˆ A denotes the estimated advantage of taking an action. rϕ = πϕ(at|st) πϕold (at|st) denotes the ratio between the current policy πϕ and the last updated policy πϕold . The clip function with a hyperparameter ϵ is used to limit rϕ within the range of [1-ϵ, 1+ϵ], improving the stability of policy updates. In PPO, the critic uses a GNN-based encoder and GMPs, then inputs concatenated virtual and physical graph representations into an MLP-based decoder to estimate value.

In the outer loop, our objective is to find a meta-policy πϕ that learns balanced strategy knowledge required by VNRs of different sizes and exhibits superior generalizability, enabling it to quickly learn optimal task-specific policies:

We update ϕ with a meta-learning rate β according to average second-order meta-gradient over task-specific policies:

Curriculum Scheduling Strategy. In our preliminary study (see Appendix A.2), we observed that training specific policies for large VNRs often leads to suboptimal convergence. This issue stems from the complexity of large-sized VNRs and the challenges of exploring the solution space to find feasible solutions. This tendency also towards local optima adversely impacts the meta-learning process. Specifically, using large-sized VNRs in the initial stages of metalearning results in low-quality gradients, which negatively affects the convergence and generalizability of the meta-policy.

To address this challenge, we draw inspiration from curriculum learning [Wang et al., 2021d] and propose a curriculum scheduling strategy to gradually integrate larger VNRs into the meta-learning process. This strategy enables highquality initializations for sub-policies of large-sized VNRs, alleviating the problems of suboptimal convergence and compromising meta-policy. We implement this by maintaining a training task list I, initially containing the smallest VNR size. The meta-learning process begins by focusing on tasks with smaller VNR sizes, which are inherently easier and provide beneficial foundational knowledge for tackling more complex tasks. Policies adeptly trained on these smaller tasks serve as effective initializations for larger VNR tasks, facilitating to mitigating local optima issues.

To achieve a gradual increase in task complexity, we use the entropy metric H(π) to evaluate the stability of policy. For our bilevel policy, we approximate it with H(π) = H(πH )+H(πL). A lower entropy suggests that the policy is making more confident decisions. When the policy entropy H(πθk ) for the largest size k = max(I) currently on the training task list falls below a specified threshold δ, we consider the policy ready to handle more complex tasks. At this point, we introduce the next larger VNR size to the training task list I. This progressive approach allows the meta-policy to adapt and generalize effectively to larger VNRs.

5 Performance Evaluation

In this section, we evaluate the effectiveness of FlagVNE.

5.1 Experiment Setup

Simulations. Following the latest works [He et al., 2023b; Wang et al., 2023b], we conduct experiments on the simulation platform to mimic various realistic network systems. We adopt two topologies, GEANT (40 nodes and 61 links) and WX100 (100 nodes and 500 links) [Waxman, 1988], as physical networks. See Appendix E.1 for these topologies' descriptions. The multiple-type resources (i.e., CPU, storage, GPU) of physical nodes and bandwidth resources of physical links are uniformly generated within the range of [50, 100] units. In each simulation run, we randomly generate 1000 VNRs with varying sizes ranging from 2 to 10. The virtual nodes within each VNR are randomly interconnected with a probability of 50%. Additionally, resource demands of each VNR's node and link requirements are uniformly generated within the range of [0, 20] and [0, 50] units, respectively. The lifetime of each VNR is exponentially distributed with an average of 500 time units. The arrival of these VNRs follows a Poisson process with an average rate η, wherein η VNRs are received per unit of time. In subsequent experiments, we first train models with η = 0.001 on GEANT and η = 0.08 on WX100, due to their different capacities of physical resources. Then we manipulate the value of η to emulate network systems with different traffic throughputs and infer with trained models to study the sensitivity of algorithms.

Implementations. During training, we first conduct metalearning in the initial 20 simulations and then focus on finetuning in the subsequent 10 simulations. We set the policy entropy threshold δ to 2. We implement neural network models with PyTorch and decide reasonable values for hyperparameters following the guide of related studies [Huang et al., 2022; Zhou et al., 2023; Wang et al., 2021a; He et al., 2023a; Kingma and Ba, 2014; Joshi et al., 2022]. See Appendix E.2 for hyperparameter settings on neural networks and meta-RL.

Baselines. To validate the effectiveness of FlagVNE, we compare it with the following SOTA heuristics (NRM-VNE [Zhang et al., 2018]; NEA-VNE [Fan et al., 2023]; PSO-VNE [Jiang and Zhang, 2021]) and RL-based baselines (MCTSVNE [Haeri and Trajkovi´c, 2017]; PG-CNN [Zhang et al., 2022]; A3C-GCN [Zhang et al., 2023]; DDPG-Attention [He et al., 2023b]). See Appendix E.3 for their descriptions.

Metrics. The following metrics are widely used to evaluate the long-term operational status of network systems over a period T [Fischer et al., 2013]: request acceptance rate (RAC), long-term average revenue (LAR) and long-term revenue-tocost (LT-R2C). See Appendix E.3 for their definitions.

5.2 Results and Analysis

Overall Performance. To simulate diverse and complex scenarios with varying traffic throughputs, we manipulate the arrival rate of VNRs in two settings due to the difference in physical resource capacity: in GEANT, we explore a range of [0.001, 0.006] with a step of 0.001, and in WX100, we investigate a range of [0.08, 0.18] stepped by 0.02.

Fig. 3(a)(b)(c) and (d)(e)(f) illustrate the performance of all algorithms in GEANT and WX100, respectively. As the arrival rate η increases, all algorithms experience a decline in RAC on both topologies, attributed to heightened competition for limited physical resources among VNRs. Despite the variability in algorithm performance across different network topologies, influenced by the varying abundance of physical bandwidth resources, FlagVNE consistently achieves the best performance in all scenarios. We observe that the improvements of FlagVNE are more pronounced at higher values of η, corresponding to heightened resource competition. This underscores the importance of searchability and generalizability in network environments with limited resources. Specifically, at η = 0.006 on GEANT, FlagVNE surpasses A3C-GCN, NEA-VNE and NRM-VNE by margins of 10.4%, 20.7% and 27.9% on RAC, 10.5%, 28.1%, and 44.2% on LAR, and 12.8%, 28.4%, and 45.1% on LT-R2C. On WX100, compared to A3C-GCN, NEA-VNE and NRM-VNE, FlagVNE shows average improvements over different η of 12.4%, 12.5% and 17.4% in RAC, 12.8%, 10.4% and 24.3% on LAR, and 9.1%, 6.7% and 36.7% on LT-R2C, respectively. Overall, FlagVNE demonstrates exceptional performance across various network system conditions.

Ablation Study. To verify the effectiveness of each proposed component, we build several variations of FlagVNE: (1) FlagVNE-UniActionNEA replaces the bidirectional action with the unidirectional one and sorts the decision sequence of virtual nodes with NEA [Fan et al., 2023]. (2) FlagVNE-MetaFree-SinglePolicy trains a single general policy with valina PPO, without the help of Meta-RL. (3) FlagVNE-MetaFree-MultiPolicy directly trains a set of subpolicies from scratch, without using Meta-RL. (4) FlagVNEMetaPolicy only uses the meta-policy to handle variable-sized VNRs. (5) FlagVNE-NoCurriculum discards the curriculum scheduling strategy during the meta-learning process.

We examine their performance under arrival rate settings of η = 0.006 on GEANT and η = 0.18 on WX100. These cases exhibit more intense competition for resources, accentuating the performance differentials stemming from the algorithms' searchability and generalizability. As shown in Table 1, FlagVNE outperforms all variations on three metrics, demonstrating that each component of FlagVNE contributes to the improvement in the final performance. Notably, we observe significant performance declines in FlagVNEMetaFree-MultiPolicy and FlagVNE-MetaFree-SinglePolicy compared to FlagVNE, which shows the effectiveness of our meta-RL training method with a curriculum scheduling strategy in achieving generalization.

Additional Evaluation. Due to the space limit, We place more experiments and analysis in Appendix F, including: the running time test on solving efficiency (F.1), adaptation and convergence analysis in both known and unknown distributions (F.2), scalability validation on large-scale network systems (F.3), and hyperparameter sensitivity study that explores the impact of the key hyperparameter ϵ (F.4).

6 Conclusion

In this paper, we proposed FlagVNE, a flexible and generalizable RL framework for VNE. Specifically, we developed a bidirectional action MDP modeling approach to enable the joint selection of virtual nodes and physical nodes, which expands the agent's search space. Additionally, we designed a hierarchical recorder with a bilevel policy to ensure adaptive output and high training efficiency. Furthermore, we presented a generalizable training method based on meta-RL that efficiently trains a set of size-specific policies to tackle VNRs of varying scales. We also developed a curriculum scheduling strategy that gradually incorporates larger VNRs, thus alleviating suboptimal convergence. Finally, we conducted extensive experiments to verify the effectiveness of FlagVNE.

Acknowledgements

This work was partially supported by National Natural Science Foundation of China (Grant No.92370204), Guangzhou-HKUST(GZ) Joint Funding Program (Grant No.2023A03J0008), Education Bureau of Guangzhou Municipality, Guangdong Science and Technology Department Project funded by China Postdoctoral Science Foundation (Grant No.2023M730785), National Natural Science Foundation of China (Grant No. 62102053).