A heterogeneous graph neural network assisted multi-agent reinforcement learning for parallel service function chain deployment

Abstract

The deployment of parallel Service Function Chains (SFCs) in Network Function Virtualization (NFV) environments presents significant challenges in jointly optimizing Virtual Network Function (VNF) parallelization and placement decisions. Traditional approaches typically decouple these decisions, leading to suboptimal performance and inefficient resource utilization. This paper proposes HGNN-PSFC, a novel heterogeneous graph neural network-assisted multi-agent deep reinforcement learning framework that jointly optimizes VNF parallelization and placement for parallel SFC deployment. Our approach employs cooperative agents: a Parallelization Agent that determines optimal VNF parallelization structures, and multiple Placement Agents that make VNF placement decisions. The framework utilizes a heterogeneous graph representation to capture complex relationships between VNFs, substrate network topology, and current VNF placement states. Through Multi-Agent Proximal Policy Optimization (MAPPO) training within a Centralized Training with Decentralized Execution (CTDE) paradigm, our method achieves effective coordination between parallelization and placement decisions. Extensive experimental results demonstrate that HGNN-PSFC achieves near-optimal performance with approximately 92% of the optimal algorithm’s effectiveness while maintaining polynomial computational complexity.

Introduction

The exponential growth of network services demands increasingly sophisticated processing capabilities to meet stringent quality of service (QoS) requirements. Traditional network architectures, where network functions are implemented through proprietary hardware devices, face significant limitations in terms of flexibility, cost-efficiency, and scalability (Mijumbi et al. 2015). These hardware-based approaches often result in rigid network infrastructures that struggle to adapt to evolving service requirements and dynamic traffic patterns, leading to suboptimal resource utilization and increased operational complexity (Herrera and Botero 2016).

Network Function Virtualization (NFV) and Software-Defined Networking (SDN) have emerged as transformative paradigms that address these limitations by decoupling network functions from dedicated hardware and separating control logic from data forwarding. NFV enables the implementation of Virtual Network Functions (VNFs) as software components that can execute on general-purpose hardware (Yi et al. 2018), while SDN provides programmable control over network traffic by centralizing network intelligence (Kreutz et al. 2014). Together, these technologies create a more agile and efficient networking environment, enabling dynamic deployment and management of network services.

In the NFV paradigm, network services are commonly deployed as Service Function Chains (SFCs), which are ordered sequences of VNFs that process network traffic to deliver specific services (Mijumbi et al. 2015). While NFV and SDN enable flexible SFC deployment, the traditional serial execution model of SFCs presents significant performance challenges, particularly for latency-sensitive applications. As packets traverse each VNF sequentially, the end-to-end delay increases proportionally with chain length, creating bottlenecks for ultra-low latency services such as autonomous driving, telemedicine, and interactive gaming. Additionally, virtualization overhead can further degrade performance compared to hardware-based implementations (Sun et al. 2017a).

To address the aforementioned issues, one potential solution is to accelerate each individual network function (Li et al. 2016). However, this approach only yields a limited reduction in latency. In contrast, most of the recent studies aims to reduce SFC latency by introducing parallelism among VNFs. Studies have revealed that 53.8% of VNF pairs in an enterprise network can operate in parallel, while 41.5% of VNF pairs can be parallelized without incurring additional resource overhead (Sun et al. 2017b). The parallel processing of VNFs can significantly reduce end-to-end packet latency by exploiting functional independence and computational parallelism.

Early approaches to VNF parallelization, such as those by Sun et al. (2017b) and Zhang et al. (2017), focus on deploying VNFs in parallel on the same server to minimize packet duplication overhead through shared memory access. However, due to limited computational resources on individual servers, collocating all parallel VNFs on the same physical host is often impractical and restricts overall SFC deployment flexibility. When VNFs are distributed across multiple servers, two main challenges emerge:

Over-parallelization overhead

To achieve parallel execution across distributed servers, each packet must be duplicated and forwarded to parallel VNF instances, and their outputs subsequently merged. This duplication and merging process increases both processing latency and network bandwidth consumption, particularly under high-throughput or bursty traffic conditions. When individual VNFs have low intrinsic execution times, parallelization can paradoxically increase end-to-end delay due to synchronization and merging costs.

Packet reordering and buffering issues

Disparate processing delays among parallel VNF instances cause out-of-order packet arrivals at the merging module, necessitating additional memory buffers to cache early arrivals and wait for stragglers. Such buffering can exacerbate latency and memory overhead, degrading overall system performance.

Consequently, as observed by Lin et al. (2021), partial parallelization often yields the optimal trade-off between performance and resource consumption. Therefore, determining the optimal parallelization degree, in particular the construction of parallel SFC branches, is essential prior to deploying parallel SFCs. The number of parallel branches and the processing time of VNFs within each branch significantly influence parallelization effectiveness. Since VNF processing times vary across different nodes due to heterogeneous hardware capabilities and varying load conditions (Troia et al. 2023), the placement of parallel VNFs directly impacts their construction efficiency. This interdependence necessitates a joint optimization approach for both the construction and placement of parallel VNFs in order to achieve optimal performance.

Figure 1 illustrates the parallel SFC placement process. Beyond determining VNF placement and routing paths, it is critical to configure an optimal degree of parallelism to minimize end-to-end service chain delay. Existing research has explored heuristic (Luo et al. 2020; Lin and Chou 2021) and reinforcement learning (RL) approaches (Cai et al. 2021; Zhang et al. 2024) for parallel SFC deployment. However, compared to serial SFC deployment, parallel SFC deployment presents additional complexities and several open challenges remain unaddressed: 1) Separate treatment of parallelization and placement. Most studies decouple SFC parallelism decisions from VNF placement strategies, leading to suboptimal end-to-end performance. 2) Lack of RL-based parallelism adaptation. There is a scarcity of RL methods that dynamically determine the optimal parallelization configuration by capturing network state variations. 3) Insufficient distributed placement solutions.There is a deficiency of reinforcement learning-based distributed placement methods for parallel SFCs. For example, some studies only consider placing mutually parallel VNFs on a single physical node, or some studies treat the VNF placement problem as a deployed instance selection problem (Lin et al. 2021).

[See PDF for image]

Fig. 1

Illustration of parallel SFC placement

Our method comprises two types of cooperative agents: a Parallelization Agent dedicated to determining the degree and structure of SFC parallelism, and multiple Placement Agents for VNF placement decisions. A multi-agent cooperative learning paradigm is employed to simplify the joint action space and accelerate training. This multi-agent approach is superior to single-agent alternatives as it decomposes the complex joint optimization problem into more manageable sub-tasks, allowing each specialized agent to focus on its specific objective while maintaining coordination through shared information. Both agent policies are trained offline using Multi-Agent Proximal Policy Optimization (MAPPO) (Yu et al. 2022). We represent both the substrate network and the parallel SFC request as graph-structured data and use a heterogeneous GNN extractor to capture diverse node and edge features effectively.

The main contributions of this paper are summarized as follows:

• A novel heterogeneous graph neural network-assisted multi-agent deep reinforcement learning algorithm for parallelized SFC deployment is proposed, which jointly optimizes SFC parallelization and VNF placement, leading to significant improvements in deployment efficiency.

• We propose, to our knowledge, the first RL-based solution to the SFC parallelization problem. Our approach employs a novel VNF parallelism graph representation that captures dependencies between VNFs while substantially reducing action space complexity. The framework integrates parallelization decisions with placement optimization in a unified learning process, avoiding suboptimal outcomes of decoupled approaches.

• We develop a comprehensive heterogeneous graph representation that captures complex relationships between VNFs, substrate network topology, existing VNF-to-node mappings, enabling more effective feature learning for parallel SFC deployment decisions.

The remainder of this paper is organized as follows. Section 2 presents related work on SFC parallelization and deployment. Section 3 introduces the network model and problem formulation for parallelized SFC deployment. Section 4 presents the HGNN-PSFC framework. Section 5 provides comprehensive performance evaluation results. Finally, Section 6 concludes the paper.

Related works

SFC parallelization

Recent research has proposed parallelizing SFCs to reduce service latency by enabling simultaneous VNF processing. Zhang et al. (2017) and Sun et al. (2017b) pioneered the exploration of parallelism between different VNFs by analyzing dependencies between VNFs in SFCs to determine parallelization feasibility. These dependencies are determined by VNFs’ read and write operations on packet headers or payloads. These studies establish guidelines for identifying parallelizable VNFs in SFCs and deploy all parallelizable VNFs on the same server, duplicating only packet headers while accessing payloads through shared memory to avoid high overhead of complete packet duplication. Building on this foundation, Cai et al. (2020) extended the study of VNF dependencies to determine parallelization feasibility for any two VNFs in distributed networks. They designed a parallelization algorithm to convert serial SFCs into parallelized SFCs represented as service graphs. Zhang et al. (2019) proposed a parallelization framework supporting SFC parallelism across multi-core servers with a HybridSFC controller enabling parallelism at both VNF and traffic levels.

However, when parallelizable VNFs cannot be served by the same server due to limited capacity constraints, VNFs must be deployed on different servers, causing additional overhead from over-parallelization and packet reordering problems. Therefore, recent research by Wang et al. (2019), Lin et al. (2021), and Zhang et al. (2023a) has focused on determining optimal partial VNF parallelism that yields minimum end-to-end latency. Wang et al. (2019) proposed ParaNF, a delay-balanced parallelized SFC processing framework for delay coordination between parallel branches. They introduced a delay-balanced SFC parallelism optimization problem to eliminate unnecessary parallelism, though ParaNF lacks deployment flexibility due to strict requirements that newly created branch processing latency must not exceed maximum branch processing latency.

Similarly, Lin et al. (2021) investigated optimal parallel processing of distributed VNFs under different SFC scenarios and proposed PPC (Partially Parallelized Chain processing). The authors enumerate all feasible parallel structures for each requesting SFC and develop a heuristic approach to find optimal partial parallelism. Their results indicate that when packet processing delay exceeds VNF execution delay, SFC parallelization benefits are minimal. Zhang et al. (2023a) proposed a parallel SFC deployment model assuming VNF sojourn time as a nonlinear function of arrival traffic and allocated computational resources, determining location and routing of parallel SFCs to address imbalance problems while minimizing deployment cost under end-to-end delay constraints.

Parallelized SFC deployment

Beyond identifying parallelizable VNFs, research has increasingly focused on mapping parallelized service chains onto physical network infrastructure. Existing approaches can be categorized into heuristic algorithms and reinforcement learning-based methods.

Heuristic approaches

Early research primarily focused on latency minimization, recognizing the key advantage of SFC parallelization in reducing end-to-end service delay. Bao et al. (2020) proposed a Directed Acyclic Graph (DAG) abstraction model for parallel SFCs and introduced the Prune and Plant (P&P) scheme, which first prunes the original DAG into a series-parallel graph to maintain parallelism while eliminating NP-hardness, then optimizes VNF placement to minimize delay. Luo et al. (2020) developed ParaSFC, a dynamic programming-based approach that sequentially deploys parallelized SFCs while finding optimal deployment paths, introducing concepts of resource abusiveness and node competitiveness to coordinate resource competition. Xie et al. (2020) emphasized joint optimization of parallelization and placement decisions with FlexChain, enabling VNFs on the same server to work in parallel while allowing SFC placement across multiple servers.

Recognizing traditional delay models’ limitations, Zhang et al. (2023a) proposed a deployment model considering traffic-dependent delay characteristics, where VNF sojourn time is modeled as a nonlinear function of both traffic and allocated resources. Their approach incorporates VNF sharing and addresses imbalance between parallel branches through flexible resource allocation. Concurrently, Zheng et al. (2022) introduced a comprehensive framework for parallelism-aware service chaining and embedding (PSFCE) that jointly optimizes processing and propagation delays. They formalized parallel relationships using Parallel Graphs and quantified processing delay savings through Parallel Block Gain (PBG).

A significant advancement in addressing distributed VNF parallelism challenges came from Lin and Chou (2021), who identified that parallel functions distributed across multiple servers introduce substantial coordination overhead. They proposed a scoring-based VNF embedding algorithm that clusters independent functions to ensure homogeneous delays among parallel functions. Lin et al. (2021) further refined this approach with their Partial Parallel Chaining (PPC) framework, which identifies optimal partial parallelism by jointly considering function placement and parallelization costs, demonstrating that strategic partial parallelization often outperforms both full parallelism and sequential chaining.

Beyond delay optimization, research has expanded to address multiple objectives in parallelized SFC deployment. Lin et al. (2018) developed breadth-first search-based greedy methods to minimize VNF rental and link costs. Chintapalli et al. (2023) introduced ERASE, the first scheme to jointly consider energy consumption minimization and reliability guarantees in parallelized SFC deployment, employing a three-stage process with novel backup strategies. For dynamic network environments, Lin et al. (2022) proposed SFT-Box, an architecture enabling real-time response to multiple hybrid SFC requests through a pre-computing strategy with modules for problem decomposition, sub-solution calculation, and fast online solution generation.

While these heuristic approaches have made substantial progress in addressing various aspects of parallelized SFC deployment, they typically rely on problem-specific assumptions and may not adapt well to dynamic network conditions or varying traffic patterns.

Reinforcement learning approaches

Recognizing limitations of heuristic approaches in adapting to dynamic network environments, researchers have increasingly explored reinforcement learning techniques for parallelized SFC deployment. Cai et al. (2021) pioneered this direction with their Adaptive Parallel Processing Mechanism (APPM), which introduced joint optimization combining parallelism optimization and deployment scheduling using Q-learning-based Joint Optimization algorithm (JORL). APPM first optimizes the parallel structure using a Parallelism Optimization Algorithm (POA) based on bin-packing principles, then applies JORL for deployment and scheduling. This work demonstrated RL’s effectiveness in reducing delay while maintaining high resource utilization. Huang et al. (2022) developed a Delay-Aware traffic Scheduling Mechanism (DASM) that transformed Parallel SFCs (PSFCs) into multiple serial SFCs with reduced VNF dependencies, then employed Q-learning for delay-aware traffic scheduling. Zhang et al. (2023b) introduced PVRDU (Parallelizing VNFs under Resource Demand Uncertainty), formulating the problem using deep reinforcement learning with Markov-based approximation algorithms to handle dynamic resource requests. Similarly, Zhang et al. (2024) proposed LVPRU (Latency-aware VNF Parallelization strategy under Resource demand Uncertainty), employing Quadratic Integer Programming combined with Asynchronous Advantage Actor-Critic (A3C) algorithms. LVPRU introduced VNF reuse for computational acceleration and demonstrated the effectiveness of actor-critic methods in handling complex state and action spaces. In the context of mobile edge computing, Lu and Long (2025) developed a Network Function Parallelism (NFP)-enhanced SFC placement framework that addresses a fairness-aware throughput maximization problem.

Further advancing multi-objective optimization, Xu et al. (2023) developed DSPPR (Dynamic SFC Placement scheme with Parallelized SFCs and Reuse of initialized VNFs), which integrated A3C algorithms with VNF Queue Network for extracting the distribution of initialized VNFs over time. DSPPR effectively balanced five competing objectives: deployment success rate, resource consumption, resource utilization, throughput, and delay cost. Huang et al. (2024) introduced PVFP (Parallel VNF Placement), the first approach to realize parallel VNF placement via Federated Deep Reinforcement Learning (FDRL), combining federated learning with deep reinforcement learning to train global models while preserving data privacy across different administrative domains. Recently, Jang et al. (2025) proposed DeepNFP, a deep RL-based network function parallelism configuration scheme operating over Segment Routing over IPv6 (SRv6). DeepNFP dynamically selects sequential or parallel execution for each service function and implements the resulting processing policy via an SRv6-based data plane protocol to reduce configuration overhead.

Despite significant progress, existing RL-based approaches for parallelized SFC deployment face several limitations. Most current methods treat parallelization and placement as separate sequential decisions, leading to sub-optimal solutions due to the lack of joint optimization. Additionally, the action space complexity remains a significant challenge when dealing with large-scale networks and complex parallel structures. The representation of SFC parallel structures in RL frameworks often lacks the expressiveness needed to capture complex VNF dependencies and parallelization opportunities effectively.

Network model and problem formalization

This section presents a comprehensive formalization of the parallelized SFC deployment problem, addressing two interconnected subproblems: (1) constructing parallel SFCs from VNF parallelism relationships, and (2) optimally placing these parallel VNFs in substrate networks while considering resource constraints and delay requirements. We develop mathematical models for both subproblems and formulate a joint optimization objective.

Service function parallelism graph

Prior research by Sun et al. (2017b) has systematically investigated the conditions under which service functions can be executed in parallel. To effectively represent and analyze these parallelism relationships, we introduce the Service Function Parallelism Graph (SFPG). Unlike traditional representation methods that use notation such as parentheses to group parallelizable service functions, this graph-based model provides a formal foundation for describing concurrent execution possibilities. The SFPG not only captures complex parallelism relationships but also facilitates the study of mappings between theoretical parallelism opportunities and implementable parallel service function chains.

Definition 1

(Service Function Parallelism Graph) A Service Function Parallelism Graph (SFPG) is an undirected graph $G_P=(V_P,E_P)$, where:

• $V_P$ represents the set of VNFs in the service function chain, with each vertex $v_i\in V_P$ corresponding to a VNF $f_i$ in the chain.

• $E_P$ denotes the set of edges between vertices, where an edge $e_{i,j}=(v_i,v_j)\in E_P$ exists if and only if VNFs $f_i$ and $f_j$ can be executed in parallel without compromising the functional correctness of the service chain.

The absence of an edge between two vertices indicates that the corresponding VNFs must be executed sequentially due to dependency constraints.

The SFPG represents potential parallelism, while the derived structure implementing these relationships is called the Parallel Service Function Graph (PSFG). Figure 2 illustrates both an SFPG and its corresponding Parallel Service Function Graph.

[See PDF for image]

Fig. 2

An example of a SFPG, its corresponding PSFG

The SFPG exhibits several important properties that directly inform parallel SFC deployment strategies. Not all SFPGs can be mapped to valid PSFGs. Specifically, an SFPG containing what we define as a Parallelism Conflict Subgraph (as illustrated in Fig. 3) cannot be mapped to a valid implementation:

[See PDF for image]

Fig. 3

Parallelism Conflict Subgraph

Definition 2

(Parallelism Conflict Subgraph) A Parallelism Conflict Subgraph is a substructure within an SFPG where VNFs $f_i$, $f_j$, $f_k$, and $f_l$ form a path such that:

• Edges $(f_i,f_j)$, $(f_j,f_k)$, and $(f_k,f_l)$ exist in the SFPG

• Edges $(f_i,f_k)$, $(f_j,f_l)$, and $(f_i,f_l)$ do not exist in the SFPG

Theorem 1

An SFPG containing a Parallelism Conflict Subgraph cannot be mapped to a valid PSFG.

Proof of Theorem 1

We prove that an SFPG containing a Parallelism Conflict Subgraph cannot be mapped to a valid Parallel Service Function Graph through the following steps:

First, we demonstrate that a Parallelism Conflict Subgraph itself cannot be mapped to a valid implementation. Consider VNFs $f_i$, $f_j$, $f_k$, and $f_l$ forming a path in the SFPG. By definition, $f_i$ can execute in parallel with $f_j$, $f_j$ with $f_k$, and $f_k$ with $f_l$. However, $f_i$ cannot execute in parallel with $f_k$, $f_j$ cannot execute in parallel with $f_l$, and $f_i$ cannot execute in parallel with $f_l$. If we attempt to position these functions in a Parallel Service Function Graph:

• If $f_i$ and $f_j$ are placed in parallel, and $f_j$ and $f_k$ are placed in parallel, and $f_i$ and $f_k$ must not be in parallel (as no edge exists between $f_i$ and $f_k$). This means $f_i$ and $f_k$ must form a sequential chain that together runs in parallel with $f_j$.

• If $f_j$ and $f_k$ are placed in parallel, and $f_k$ and $f_l$ are placed in parallel, and $f_j$ and $f_l$ must not be in parallel (as no edge exists between $f_j$ and $f_l$). This means $f_j$ and $f_l$ must form a sequential chain that together runs in parallel with $f_k$.

• Consequently, $f_l$ must be in parallel with the sequential chain containing $f_i$ (from the first condition), but $f_i$ and $f_l$ cannot be parallel (as no edge exists between $f_i$ and $f_l$), creating a contradiction.

Second, we extend this proof to show that any SFPG containing such a subgraph inherits this implementation impossibility. Since valid parallel implementation requires all substructures to be implementable, the presence of even one Parallelism Conflict Subgraph renders the entire SFPG unmappable to a valid Parallel Service Function Graph. $\square$

An SFPG may be a disconnected graph, where each connected component forms a parallel module. These disconnected components maintain sequential relationships with each other, with their execution order determined by the specified sequential constraints. Through our analysis, we observe that the complement graph of an SFPG represents the inverse parallelism relationship, where an edge indicates that two VNFs cannot be executed in parallel.

Notably, the complement of a Parallelism Conflict Subgraph is isomorphic to itself. We define an SFPG without any Parallelism Conflict Subgraph as a "feasible SFPG". The corresponding PSFG derived from a feasible SFPG represents a fully parallelized SFC. For implementation flexibility, we can also derive partially parallelized SFCs by selectively removing certain edges from a feasible SFPG, representing different implementation trade-offs.

Substrate networks

We model the substrate network as a weighted undirected graph $G_N=(N,L)$, where N denotes the set of substrate physical nodes and L refers to the set of substrate physical links. Each substrate node $n\in N$ has available computing resources $C_n$. The processing delay for a VNF instance of type m at node n is denoted as $d_{m,n}^{\text{proc}}$. Each physical link $l=(n_1,n_2)\in L$ connecting adjacent nodes $n_1$ and $n_2$ has bandwidth capacity $B_l$ and transmission delay $d_l^{\text{trans}}$.

Table 1. Notation Summary

Symbol	Description
$G_P^{(i)}=(V_P^{(i)},E_P^{(i)})$	Service Function Parallelism Graph for request i
$G_S^{(i)}=(V_S^{(i)},E_S^{(i)})$	Parallel Service Function Graph for request i
$G_N=(N,L)$	Substrate network with nodes N and links L
$R=\{r_1,\dots ,r_{|R|}\}$	Set of SFC requests
$r_i=(G_P^{(i)},G_S^{(i)},s_i,d_i,{\lambda }_i)$	SFC request i with source $s_i$, destination $d_i$, rate ${\lambda }_i$
$f_{i,j}$	The j-th VNF in request i
$K_i$	Number of VNFs in request i
$\mathcal{M}=\{m_1,\dots ,m_{|\mathcal{M}|}\}$	Set of VNF types
$\mathrm{\Gamma }(f_{i,j})$	VNF type of $f_{i,j}$
$C_n$	Computing capacity of node n
$B_l$	Bandwidth capacity of link l
$r_{m,n}^{\text{c}}$	Computing requirements of VNF type m at node n
$d_{m,n}^{\text{proc}}$	Processing delay of VNF type m at node n
$d_l^{\text{trans}}$	Transmission delay of link l
$z_{i,(j,k)}$	Binary variable: edge (j, k) retained in modified SFPG
$x_{i,j}^n$	Binary variable: VNF $f_{i,j}$ placed on node n
$y_{i,(j,k)}^l$	Binary variable: virtual link (j, k) uses substrate link l
$P_i$	Set of parallel branches in PSFG $G_S^{(i)}$
$D_p$	Delay of parallel branch p
$D_{e2e}^{(i)}$	End-to-end delay of request i

For the sake of clarity, all the variables and symbols introduced in this section are summarized in Table 1.

Parallel service function graph

We model the optimally parallelized SFC requests that need to be deployed into the substrate network as Directed Acyclic Graphs (DAGs), termed Parallel Service Function Graphs (PSFGs). For a set of parallelized SFC requests $R=\{r_1,r_2,\dots ,r_k\}$, each parallelized SFC request is represented as $r_i=(G_P^{(i)},G_S^{(i)},s_i,d_i,{\lambda }_i)$, where $G_P^{(i)}$ denotes the Service Function Parallelism Graph representing the parallelism relationships, $G_S^{(i)}$ denotes the PSFG structure, $s_i$ represents the source node where packets enter the SFC, $d_i$ represents the destination node where packets exit the SFC, and ${\lambda }_i$ represents the data rate requirement.

Each PSFG is formally defined as $G_S^{(i)}=(V_S^{(i)},E_S^{(i)})$, where $V_S^{(i)}$ represents the set of vertices and $E_S^{(i)}$ represents the set of directed edges. The vertex set $V_S^{(i)}$ includes VNF instances $F_i=\{f_{i,0},f_{i,1},f_{i,2},\dots ,f_{i,K_i},f_{i,K_i+1}\}$, where $f_{i,j},j\in \{1,K_i\}$ denotes the j-th VNF in parallel SFC request i, and $K_i$ is the number of VNFs in the SFC. To facilitate subsequent formulations, we introduce two virtual functions: $f_{i,0}$ and $f_{i,K_i+1}$, representing the virtual ingress and egress functions corresponding to source node $s_i$ and destination node $d_i$, respectively.

The directed edges $E_S^{(i)}\subseteq V_S^{(i)}\times V_S^{(i)}$ represent virtual links (VLs) that define traffic flow between VNFs. The set of all VNF types across all requests is represented by $\mathcal{M}=\{m_1,m_2,\dots ,m_{|\mathcal{M}|}\}$, where $|\mathcal{M}|$ is the total number of distinct VNF types. Let $\mathrm{\Gamma }(f_{i,j})\in \mathcal{M}$ denote the VNF type corresponding to the j-th VNF of service request $r_i$. The resource requirements for deploying a VNF of type m are characterized by computing resources $r_m^{\text{c}}$.

Problem definition and formulation

Given a substrate network $G_N=(N,L)$ and a set of parallel SFC requests represented by SFPG graphs, the parallel SFC deployment problem aims to: (1) determine the optimal partial parallelization by constructing valid PSFGs from given SFPGs, and (2) optimally place the VNFs and route virtual links to minimize end-to-end delay while satisfying resource constraints.

Specifically, the problem consists of two phases: In the first phase, we construct a valid PSFG from a given SFPG. The SFPG represents all potential parallelism relationships between VNFs, but not all these relationships can be simultaneously implemented in a valid deployment. Therefore, we must identify a feasible subset of parallelism relationships that can be realized in optimal partial parallelization. Given an original SFPG $G_P=(V_P,E_P)$, we aim to derive a modified SFPG $G_P^{\prime }=(V_P,E_P^{\prime })$ where $E_P^{\prime }\subseteq E_P$ by selectively removing certain edges (possibly none if the original SFPG is already conflict-free). This modified SFPG uniquely corresponds to a valid PSFG that will be deployed as the parallel SFC. In the second phase, given a constructed PSFG $G_S=(V_s,E_s)$ converted from a modified SFPG, we place all network function nodes.

Decision variables

We define the following decision variables that jointly represent parallelization and VNF placement for request i:

1

$$\begin{array}{c}\hfill z_{i,(j,k)}=\left\{\begin{array}{cc}1,\hfill & \text{if edge}{e}_{j,k}\text{from original SFPG}{G}_P^{(i)}\text{is retained}\hfill \\ 0,\hfill & \text{if edge}{e}_{j,k}\text{is removed}\hfill \end{array}\right)\end{array}$$

2

$$\begin{array}{c}\hfill x_{i,j}^n=\left\{\begin{array}{cc}1,\hfill & \text{if VNF}{f}_{i,j}\text{is placed on substrate node}n\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}\right)\end{array}$$

3

$$\begin{array}{c}\hfill y_{i,(j,k)}^l=\left\{\begin{array}{cc}1,\hfill & \text{if virtual link}(f_{i,j},f_{i,k})\text{uses substrate link}l\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}\right)\end{array}$$

Constraints

The parallel SFC deployment process is subject to several critical constraints, which we elaborate below:

Parallelization constraint

The modified SFPG $G_P^{\prime (i)}$ must not contain any Parallelism Conflict Subgraph:

4

$$\begin{array}{cc}\hfill \text{C1:}{G}_P^{\prime (i)}=& (V_P^{(i)},\{e_{j,k}\in E_P^{(i)}\mid z_{i,(j,k)}=1\})\text{contains no}\hfill \\ \hfill & \text{Parallelism Conflict Subgraph}\hfill \end{array}$$

Resource constraint

For each substrate node $n\in N$, the computing resource constraint must be satisfied:

5

$$\begin{array}{c}\hfill \text{C2:}\sum _{i=1}^{|R|}\sum _{j=1}^{K_i}{r}_{\mathrm{\Gamma }(f_{i,j}),n}^{\text{c}}·x_{i,j}^n\le C_n,\forall n\in N\end{array}$$where $r_{\mathrm{\Gamma }(f_{i,j}),n}^{\text{c}}$ denotes the required computational resources for VNF type $f_{i,j}$ placed on node n.

For each substrate link $l\in L$, the bandwidth constraint ensures that the total bandwidth used by the SFCs does not exceed the link capacity:

6

$$\begin{array}{c}\hfill \text{C3:}\sum _{i=1}^{|R|}{\lambda }_i\sum _{(j,k)\in E_S^{(i)}}{y}_{i,(j,k)}^l\le B_l,\forall l\in L\end{array}$$

VNF placement constraint

Each VNF must be deployed on exactly one physical node, ensuring uniqueness in placement:

7

$$\begin{array}{c}\hfill \text{C4:}\sum _{n\in N}{x}_{i,j}^n=1,\forall i\in \{1,2,\dots ,|R|\},\forall j\in \{1,2,\dots ,K_i\}\end{array}$$Moreover, the total number of VNFs deployed for request $r_i$ must match the number of required VNFs:

8

$$\begin{array}{c}\hfill \text{C5}:\sum _{j=1}^{K_i}\sum _{n\in N}{x}_{i,j}^n=K_i,\forall i\in 1,2,...,|R|\end{array}$$

Optimization objective

The primary objective of this work is to minimize the end-to-end delay in the deployment of parallel SFCs. Let $P_i$ denote the set of all possible parallel branches in PSFG $G_S^{(i)}$. For each branch $p\in P_i$, let $V_p$ be the set of VNFs on branch p and $E_p$ be the set of virtual links on branch p.

The delay in a parallel SFC has several components that affect the end-to-end performance:

Processing delay

The processing delay at node n for VNF $f_{i,j}$ is denoted as $d_{\mathrm{\Gamma }(f_{i,j}),n}^{\text{proc}}$, which depends on both the node capabilities and the service function requirements.

Transmission delay

The transmission delay over a substrate link l for traffic of rate ${\lambda }_i$ is denoted as $d_l^{\text{trans}}$.

For parallel execution, we need to consider the additional delays introduced by packet duplication and merging operations. Assuming that distributed parallel deployment only requires copying packet headers (Sun et al. 2017b).

Duplication delay

The time required to duplicate packet headers for parallel processing $d_{f_{i,j}}^{\text{dup}}=d_{\mathit{hdr}}^{\mathit{dup}}·(q-1)$, where $d_{\mathit{hdr}}^{\mathit{dup}}$ is the time to duplicate one packet header, q is the number of parallel branches at $f_{i,j}$.

Merging delay

The time required to merge results from parallel branches $d_{f_{i,j}}^{\text{merge}}=d_{\mathit{hdr}}^{\mathit{merge}}·(q-1)$, where $d_{\mathit{hdr}}^{\mathit{merge}}$ is the time to merge one packet header and $f_{i,j}$ is the merge node.

The delay of branch p is:

9

$$\begin{array}{cc}\hfill D_p=& \sum _{f_{i,j}\in V_p}\sum _{n\in N}{d}_{\mathrm{\Gamma }(f_{i,j}),n}^{\text{proc}}·x_{i,j}^n+\sum _{(j,k)\in E_p}\sum _{l\in L}{d}_l^{\text{trans}}·y_{i,(j,k)}^l\hfill \\ \hfill & +\sum _{f_{i,j}\in V_p}(d_{f_{i,j}}^{\text{dup}}+d_{f_{i,j}}^{\text{merge}})\hfill \end{array}$$The end-to-end delay is determined by the critical path:

10

$$\begin{array}{c}\hfill D_{e2e}^{(i)}=\underset{p\in P_i}{max}{D}_p\end{array}$$The objective is to optimize the parallelization and placement decisions, denoted as $z_{i,(j,k)}$, $x_{i,j}^n$ and $y_{i,(j,k)}^l$, to minimize end-to-end delay while ensuring the successful deployment of SFCs.

The objective function is formulated as:

11

$$\begin{array}{c}\hfill min\sum _{i=1}^{|R|}{D}_{e2e}^{(i)}\end{array}$$The inherent complexity stems from the VNF placement subproblem being NP-hard, rendering the overall problem computationally intractable for large-scale networks. This motivates our multi-agent deep reinforcement learning approach.

[See PDF for image]

Fig. 4

Overview of the Proposed HGNN-PSFC Approach

Proposed multi-agent reinforcement learning based approach

Overview of the proposed approach

This section presents our novel approach, HGNN-PSFC, for parallel SFC deployment using multi-agent reinforcement learning (MARL) assisted by heterogeneous graph neural networks (Hetero-GNN). We first introduce the multi-agent framework design, followed by the heterogeneous graph neural network architecture for feature extraction.

Multi-agent framework design

Parallel SFC deployment encompasses two distinct subtasks: determining VNF parallelization and placing VNFs across physical nodes. These tasks address fundamentally different aspects and require specialized agents with distinct policy strategies. To address this complexity, we propose a novel MARL framework employing two types of collaborative agents: a Parallelization Agent (PA) and multiple Placement Agents (PLAs), as illustrated in Fig. 4. The Parallelization Agent makes decisions regarding the parallelization structure of SFC components, while each Placement Agent is assigned to a specific VNF in the service chain and determines its optimal physical node placement within the network infrastructure.

This dual-agent architecture facilitates efficient coordination between parallelization and placement strategies through a sequential two-phase process. As illustrated in Fig. 5, in the initial phase, an initial SFPG is constructed based on the pairwise parallel relationships among the SFs in the SFC request. The PA then observes the network state and the SFPG, performing edge-removing actions to eliminate Parallelism Conflict Subgraphs while simultaneously constructing an optimal partial parallel structure. This feasible SFPG is subsequently transformed into a partial parallel PSFG structure using Algorithm 1. In the second phase, PLAs observe the network state and the generated PSFG to determine optimal physical nodes for hosting each VNF component.

[See PDF for image]

Fig. 5

Workflow of the dual-agent architecture

Algorithm 1 implements the transformation from a feasible SFPG to a PSFG structure. The algorithm leverages the fundamental principle that edges in the original graph represent potential for parallelism between VNFs–hence, disconnected components must be executed sequentially. Conversely, in the complement graph, edges imply sequential dependencies, and thus disconnected components can be executed in parallel. As illustrated in Fig. 5, starting from a feasible SFPG, the algorithm recursively constructs the complement graph for each connected component and determines the execution semantics (parallel or sequential) based on the above rules. This recursive process continues until the complete PSFG is constructed.

[See PDF for image]

Algorithm 1

Transformation from Feasible SFPG to PSFG

Effective coordination between the parallelization and placement phases is critical to deployment success. In our dual-agent architecture, decisions made by the PA directly shape the observation spaces of the PLAs, creating an implicit information flow that facilitates coordination during execution.

Heterogeneous graph network feature extraction

We model the system state as a heterogeneous graph ${\mathcal{G}}^t=(\mathcal{V},\mathcal{E},\mathcal{X},\mathcal{R})$ at each decision step t, where $\mathcal{V}$ denotes the heterogeneous node collection, $\mathcal{E}$ represents the heterogeneous edge collection, $\mathcal{X}$ contains node attribute matrices, and $\mathcal{R}$ encompasses edge attribute matrices. Here, the term heterogeneous refers to the structural differences between the two types of graphs involved in our problem: the parallel SFC request graph and the substrate network graph, which differ in node types and edge semantics, and connectivity patterns. The heterogeneous node set $\mathcal{V}={\mathcal{V}}_F\cup {\mathcal{V}}_N$ comprises:

VNF nodes${\mathcal{V}}_F=V_P$ representing virtual network functions derived from the SFPG vertex set, where each node corresponds to a VNF in the service function chain.

Physical nodes${\mathcal{V}}_N=N$ representing substrate network infrastructure.

The heterogeneous edge set $\mathcal{E}={\mathcal{E}}_{\mathit{dep}}\cup {\mathcal{E}}_{\mathit{net}}\cup {\mathcal{E}}_{\mathit{map}}$ encompasses:

VNF dependency edges${\mathcal{E}}_{\mathit{dep}}\subseteq {\mathcal{V}}_F\times {\mathcal{V}}_F$ representing parallelization dependencies within service chains, which are derived from the SFPG. It is important to note that the construction of dependency edges differs between agents: for the parallelization agent, dependency edges are derived from the original SFPG, while for the placement agent, dependency edges are derived from the modified SFPG that has been updated by the parallelization agent through selective edge removal decisions.

Physical network edges${\mathcal{E}}_{\mathit{net}}\subseteq {\mathcal{V}}_N\times {\mathcal{V}}_N$ representing substrate connectivity.

Deployment mapping edges${\mathcal{E}}_{\mathit{map}}\subseteq {\mathcal{V}}_F\times {\mathcal{V}}_N$ indicating current or potential VNF-to-node assignments.

To extract comprehensive topological and resource information, we develop an enhanced TransformerConv-based (Shi et al. 2020) architecture. Initially, we employ separate MLPs to generate base representations:

12

$$\begin{array}{c}\hfill H_F^{(0)}={\text{MLP}}_F({\mathbf{X}}_F),H_N^{(0)}={\text{MLP}}_N({\mathbf{X}}_N)\end{array}$$We apply K successive layers of heterogeneous GNNs. At layer $\kappa$, we deploy specialized TransformerConv operations:

13

$$\begin{array}{cc}\hfill {\tilde{H}}_F^{(\kappa )}=& \text{TransformerConv}(H_F^{(\kappa -1)},{\mathcal{E}}_{\mathit{dep}},{\mathbf{E}}_{\mathit{dep}})\hfill \end{array}$$

14

$$\begin{array}{cc}\hfill {\tilde{H}}_N^{(\kappa )}=& \text{TransformerConv}(H_N^{(\kappa -1)},{\mathcal{E}}_{\mathit{net}},{\mathbf{E}}_{\mathit{net}})\hfill \end{array}$$

15

$$\begin{array}{c}\hfill H_{F,cross}^{(\kappa )},H_{N,cross}^{(\kappa )}=\text{TransformerConv}([H_F^{(\kappa -1)};H_N^{(\kappa -1)}],{\mathcal{E}}_{\mathit{map}},{\mathbf{E}}_{\mathit{map}})\end{array}$$We employ additive aggregation to construct unified node representations:

16

$$\begin{array}{cc}\hfill H_F^{(\kappa )}=& {\tilde{H}}_F^{(\kappa )}+H_{F,cross}^{(\kappa )}\hfill \end{array}$$

17

$$\begin{array}{cc}\hfill H_N^{(\kappa )}=& {\tilde{H}}_N^{(\kappa )}+H_{N,cross}^{(\kappa )}\hfill \end{array}$$Finally, we incorporate residual connections to obtain final node embeddings:

18

$$\begin{array}{c}\hfill H_F=H_F^{(K)}+H_F^{(0)},H_N=H_N^{(K)}+H_N^{(0)}\end{array}$$This heterogeneous graph architecture enables our framework to capture multi-faceted interactions between service requirements, substrate capabilities, and network topology constraints, providing rich contextual embeddings that facilitate informed decision-making across both parallelization and placement optimization tasks.

Reinforcement learning framework

To effectively address the parallel SFC deployment challenge through multi-agent reinforcement learning, we formalize our approach within the Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek et al. 2016) framework. This section establishes the theoretical foundations of our model and details the specific implementation of state spaces, action spaces, and reward functions for our dual-agent architecture.

State space definition

VNF node features

For VNF nodes $f_i\in F$, the feature vector ${\mathbf{X}}_{f_i}\in {\mathbb{R}}^{d_f}$ encapsulates:

19

$$\begin{array}{c}\hfill {\mathbf{X}}_{f_i}={\left[\frac{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}{r_{\mathit{max}}^{\text{c}}},,,\frac{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}{\overline{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}},,,\frac{i}{K}\right]}^T\end{array}$$where $\frac{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}{r_{\mathit{max}}^{\text{c}}}$ represent normalized computational resource demands, $\frac{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}{\overline{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}}$ captures the relative resource intensity of node $f_i$ compared to the mean computational requirements across all VNF nodes, $\frac{i}{K}$ serves as a sequential identifier within the service chain architecture.

Physical node features

For physical nodes $n\in N$, the feature vector ${\mathbf{X}}_n\in {\mathbb{R}}^{d_n}$ contains:

20

$$\begin{array}{c}\hfill {\mathbf{X}}_n={\left[\frac{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}{Re{s}_u^{\text{c}}},,,\frac{Re{s}_u^{\text{c}}}{\overline{Re{s}^{\text{c}}}},,,\frac{d_{\mathrm{\Gamma }(f_i),u}^{\text{proc}}}{d_{\text{max-node}}^{\text{proc}}},,,|\mathcal{N}(n)|\right]}^T\end{array}$$Here, $Re{s}_u^{\text{c}}$ denote the available computational capacity remaining at node u. The metric $\frac{r_{\mathrm{\Gamma }(f_i)}^{\text{c}}}{Re{s}_u^{\text{c}}}$ quantifies the resource consumption ratio, where values below unity indicate sufficient capacity to accommodate the VNF requirements, while values exceeding unity signal insufficient resources, suggesting either non-availability or the need for alternative placement strategies.

The term $\frac{Re{s}_u^{\text{c}}}{\overline{Re{s}^{\text{c}}}}$ establishes the relative resource standing of node u against the network-wide average, facilitating load balancing decisions. The normalized processing daley $\frac{d_{\mathrm{\Gamma }(f_i),u}^{\text{proc}}}{d_{\text{max-node}}^{\text{proc}}}$ quantifies computational delay characteristics, where $d_{\text{max-node}}^{\text{proc}}$ serves as the network-wide delay benchmark. Finally, $|\mathcal{N}(n)|$ captures the node’s connectivity degree within the network topology.

Edge feature

SFC dependency edges $(f_i,f_k)\in {\mathcal{E}}_{\mathit{dep}}$ carry features:

21

$$\begin{array}{c}\hfill {\mathbf{E}}_{\mathit{ik}}^{\mathit{dep}}={\left[{\lambda }_{\mathit{ik}}\right]}^T\end{array}$$Physical network edges $(n_j,n_l)\in {\mathcal{E}}_{\mathit{net}}$ are characterized by:

22

$$\begin{array}{c}\hfill {\mathbf{E}}_{\mathit{jl}}^{\mathit{net}}={\left[\frac{{\lambda }_{j}l}{Re{s}_{(n_j,n_l)}^{\text{bw}}},,,\frac{Re{s}_{(n_j,n_l)}^{\text{bw}}}{\overline{Re{s}^{\text{bw}}}},,,\frac{d_{(n_j,n_l)}^{\text{trans}}}{d_{\text{max-link}}^{\text{trans}}}\right]}^T\end{array}$$where $Re{s}_{(n_j,n_l)}^{\text{bw}}$ denotes the unused bandwidth capacity on link $(n_j,n_l)$. The utilization factor $\frac{{\lambda }_i}{Re{s}_{(n_j,n_l)}^{\text{bw}}}$ evaluates whether current bandwidth reserves can satisfy SFC traffic demands. The values below one indicate adequate capacity, while higher values signal potential bottlenecks requiring traffic rerouting. The comparative bandwidth metric $\frac{Re{s}_{(n_j,n_l)}^{\text{bw}}}{\overline{Re{s}^{\text{bw}}}}$ positions the link’s capacity within the broader network context. Furthermore, $\frac{d_{(n_j,n_l)}^{\text{trans}}}{d_{\text{max-link}}^{\text{trans}}}$ represents the normalized current delay on link $(n_j,n_l)$, where $d_{\text{max-link}}^{\text{trans}}$ is the maximum delay across all links in the network.

Mapping edges $(f_i,n_j)\in {\mathcal{E}}_{\mathit{map}}$ represent deployment relationships with features:

23

$$\begin{array}{c}\hfill {\mathbf{E}}_{\mathit{ij}}^{\mathit{map}}={\left[t_{\mathit{deploy}}\right]}^T\end{array}$$where $t_{\mathit{deploy}}\in \{0,1\}$ is a binary indicator variable. Specifically, $t_{\mathit{deploy}}=1$ if function $f_i$ has been deployed on node $n_j$, and $t_{\mathit{deploy}}=0$ otherwise.

Action space definition

Parallelization agent

The action space $A_{\text{PA}}$ for the Parallelization Agent consists of edge removing operations on the SFPG, defined as:

24

$$\begin{array}{c}\hfill A_{\text{PA}}=a_{e_1},a_{e_2},\dots ,a_{e_{|{\mathcal{E}}_{\mathit{dep}}|}}\text{where}{a}_{e_i}\in 0,1,\forall e_i\in {\mathcal{E}}_{\mathit{dep}}\end{array}$$where $a_{e_i}=1$ indicates that edge $e_i$ in the SFPG should be removed, and $a_{e_i}=0$ indicates that edge $e_i$ should be preserved. Each combination of edge removals results in a specific parallelization structure, with the constraint that the resulting graph must be a feasible SFPG without Parallelism Conflict Subgraphs. The PA must learn to select edge removals that optimize parallelization potential while ensuring deployability.

Placement agent

The action space $A_{\text{PLA}}$ for each Placement Agent at time step t consists of selecting a physical node from the set of available nodes:

25

$$\begin{array}{c}\hfill A_{\text{PLA}}\in \{1,2,\dots ,|N|\}\end{array}$$where each action corresponds to selecting a specific physical node for hosting the VNF. The action creates a new mapping edge and updates the heterogeneous graph state.

Reward function design

The reward function design is critical for guiding the multi-agent learning process toward optimal parallel SFC deployment strategies. Given the sequential nature of our two-phase approach and the distinct objectives of parallelization and placement decisions, we develop a hierarchical reward mechanism that provides appropriate incentives for both individual agent performance and collaborative optimization.

Our reward system employs a three-tier structure: immediate rewards for phase-specific feedback, intermediate rewards for partial deployment assessment, and global rewards for overall deployment quality evaluation.

Immediate rewards

During the parallelization phase, the PA receives immediate feedback based on the validity of the generated SFPG structure:

26

$$\begin{array}{c}\hfill R_{\text{PA}}^{\text{immediate}}=\left\{\begin{array}{cc}-{\alpha }_{\text{conflict}}·N_{\text{conflict}},\hfill & \text{if Parallelism Conflict Subgraphs exist}\hfill \\ {\beta }_{\text{valid}}·\frac{|E_P^{\prime }|}{|E_P|},\hfill & \text{if feasible SFPG generated}\hfill \end{array}\right)\end{array}$$where $N_{\text{conflict}}$ denotes the number of detected Parallelism Conflict Subgraphs, ${\alpha }_{\text{conflict}}>0$ is the conflict penalty coefficient, ${\beta }_{\text{valid}}>0$ is the valid parallelization reward coefficient, and $|E_P^{\prime }|/|E_P|$ represents the ratio of preserved parallelization edges, encouraging maximal parallelization potential while maintaining feasibility.

For placement agents, immediate rewards provide feedback on constraint satisfaction and placement validity:

27

$$\begin{array}{c}\hfill R_{\text{PLA}j}^{\text{immediate}}=\left\{\begin{array}{cc}-{\gamma }_{\text{resource}},\hfill & \text{if resource constraints violated}\hfill \\ -{\gamma }_{\text{invalid}},\hfill & \text{if invalid placement executed}\hfill \\ {\delta }_{\text{success}},\hfill & \text{if successful placement achieved}\hfill \end{array}\right)\end{array}$$where ${\gamma }_{\text{resource}},{\gamma }_{\text{invalid}},{\delta }_{\text{success}}>0$ represent penalty coefficients for resource violations, invalid placements, and success rewards for valid placements, respectively.

Intermediate rewards

During the placement phase, when some PLAs have attempted placement while others remain unassigned, we provide differentiated rewards based on each agent’s current status and performance:

28

$$\begin{array}{c}\hfill R_{\text{PLA}j}^{\text{intermediate}}=\left\{\begin{array}{cc}-\eta ·\frac{D{\text{partial}}^{(i)}}{D_{\text{baseline}}},\hfill & \text{if PLA}j\text{successfully placed}\hfill \\ -{\gamma }_{\text{failure}},\hfill & \text{if}{\text{PLA}}_j\text{failed to place}\hfill \\ 0,\hfill & \text{if}{\text{PLA}}_j\text{not yet attempted}\hfill \end{array}\right)\end{array}$$where $D_{\text{partial}}^{(i)}$ represents the end-to-end delay of the currently deployed partial path that includes successfully placed VNFs, $D_{\text{baseline}}$ is a baseline delay reference (e.g., random placement), ${\gamma }_{\text{failure}}>0$ is the failure penalty coefficient, and $\eta >0$ is the weighting parameter that encourages placements contributing to lower partial delays.

[See PDF for image]

Fig. 6

Framework of the MAPPO algorithm within the CTDE paradigm for parallel SFC deployment

Global rewards

Upon successful completion of the entire deployment process, all agents receive a shared global reward based on the overall system performance:

29

$$\begin{array}{c}\hfill R_{\text{global}}=-\lambda ·D_{e2e}^{(i)}\end{array}$$where $D_{e2e}^{(i)}$ is the end-to-end delay for request i, and $\lambda >0$ is the global optimization coefficient.

Final reward allocation

The final reward for each agent combines immediate feedback, intermediate assessment, and global performance:

30

$$\begin{array}{cc}\hfill R_{\text{PA}}^{\text{final}}=& R_{\text{PA}}^{\text{immediate}}+w_{\text{global}}·R_{\text{global}}\hfill \end{array}$$

31

$$\begin{array}{cc}\hfill R_{\text{PLA}j}^{\text{final}}=& R_{\text{PLA}j}^{\text{immediate}}+R_{\text{PLA}j}^{\text{intermediate}}+w_{\text{global}}·R_{\text{global}}\hfill \end{array}$$where $w_{\text{global}}\in (0,1)$ is the global reward weight that ensures all agents benefit from successful collaborative deployment while maintaining sensitivity to individual performance. To ensure training stability and convergence, we apply reward normalization using exponential moving averages.

Training process and algorithms

In this work, our novel MARL framework, HGNN-PSFC, for parallel SFC deployment is trained using MAPPO, an extension of the Proximal Policy Optimization (PPO) algorithm (Schulman et al. 2017) designed for multi-agent environments. As illustrated in Fig. 6, MAPPO operates within the Centralized Training with Decentralized Execution (CTDE) paradigm (Lowe et al. 2017), which is particularly well-suited for our dual-agent architecture. During training, the Parallelization Agent and Placement Agents share information to enable a centralized critic to evaluate joint actions accurately, while maintaining separate policy networks for decentralized execution. This approach facilitates effective coordination between parallelization decisions and subsequent placement strategies while ensuring that each agent can operate independently during deployment.

Each agent type has separate actor and critic networks. The actor produces a probability distribution over actions given local observations, and the critic estimates the state value for advantage computation. As an on-policy algorithm, MAPPO improves data efficiency through importance sampling and a clipping mechanism to prevent excessive policy updates. The importance sampling ratio is defined as $r_t(\theta )=\frac{{\pi }_{\theta }(a_t|o_t)}{{\pi }_{{\theta }_{\text{old}}}(a_t|o_t)}$, where ${\theta }_{\text{old}}$ represents the policy parameters used to collect experience tuples $(o_t,a_t,r_t,o_{t+1})$. The clipped objective function in MAPPO is given by:

32

$$\begin{array}{c}\hfill L^{\text{MAPPO}}(\theta )={\mathbb{E}}_t\left[min,\left(r_t,(\theta ),{\widehat{A}}_t,,,,\text{clip},(r_t(\theta ),1-ϵ,1+ϵ),{\widehat{A}}_t\right)\right]\end{array}$$where ${\widehat{A}}_t$ is the advantage function estimated using generalized advantage estimation (GAE) (Schulman et al. 2015):

33

$$\begin{array}{c}\hfill {\widehat{A}}_t={\delta }_t+(\gamma \lambda ){\delta }_{t+1}+\cdots +{(\gamma \lambda )}^{T-t+1}{\delta }_{T-1}\end{array}$$with ${\delta }_t=r_t+\gamma V_{\varphi }(o_{t+1})-V_{\varphi }(o_t)$, where $\gamma$ is the discount factor and $\lambda$ is the GAE parameter.

Our approach employs two distinct categories of agents-the Parallelization Agent and multiple Placement Agents-each with specialized actor and critic networks tailored to their respective roles. Denoting a generic agent by index k (where $k=$ PA or $k={\text{PLA}}_j$), the actor objective is:

34

$$\begin{array}{c}\hfill L({\theta }_k)=\frac{1}{B{N}_k}\sum _{i=1}^B\sum _{j=1}^{N_k}min\left(r_{{\theta }_k,i}^{(j)},{\widehat{A}}_{k,i}^{(j)},,,\text{clip},(r_{{\theta }_k,i}^{(j)},1-ϵ,1+ϵ),{\widehat{A}}_{k,i}^{(j)}\right)\end{array}$$where B denotes the batch size and $N_k$ represents the number of each Agents. The probability ratio between updated and previous policies is denoted as $r_{\theta ,i}^{(j)}$, and ${\widehat{A}}_i^{(j)}$ is the advantage function for agent j.

For the critic networks, the objective is to minimize the value function loss, defined as:

35

$$\begin{array}{c}\hfill L({\varphi }_k)=\frac{1}{B{N}_k}\sum _{i=1}^B\sum _{j=1}^{N_k}{\left(V_{{\varphi }_k},(s_{k,i}^{(j)}),-,{\widehat{R}}_{k,i}\right)}^2\end{array}$$where $V_{\varphi }(s_i^{(j)})$ represents the predicted value of the state $s_i^{(j)}$, and ${\widehat{R}}_{k,i}$ is the discounted reward-to-go for agent k.

The overall training process is outlined in Algorithm 2, which iterates over multiple episodes until convergence. During each episode, both agent types interact with the environment in their prescribed sequence, collecting observations, rewards, and next states. These experiences are then used to update the actor and critic networks according to the MAPPO algorithm.

[See PDF for image]

Algorithm 2

MAPPO for Parallel SFC Deployment.

By leveraging MAPPO within the CTDE framework, our approach enables effective coordination between the Parallelization Agent and Placement Agents, balancing the trade-offs between parallelization potential and resource constraints. The Parallelization Agent learns to identify and eliminate Parallelism Conflict Subgraphs while maximizing parallelization opportunities, while Placement Agents learn to select optimal physical nodes that satisfy the constraints imposed by the parallelization structure.

Complexity analysis

In HGNN-PSFC method, the training phase is performed offline, allowing computationally intensive model updates without affecting real-time system performance. Its computational complexity is proportional to both the size of the training data and the training duration. The offline training phase ensures that, once completed, the system can efficiently handle SFC deployment tasks using the trained heterogeneous graph neural network model. Since the online scenario is where computational efficiency is most critical, we focus our analysis on the online complexity during real-time execution of SF placement decisions.

The complexity of the online execution is mainly driven by the feedforward pass of the heterogeneous graph neural network for graph representation learning. HGNN-PSFC exhibits a computational complexity of $O(|F|·K·(|{\mathcal{E}}_{\mathit{net}}|d+|N+F|d^2))$, where |F| and $|{\mathcal{E}}_{\mathit{dep}}|$ denote the number of VNF nodes and SFC dependency edges, |N| and $|{\mathcal{E}}_{\mathit{net}}|$ denote the number of physical nodes and substrate links, K denotes the number of GNN layers, and d denotes the embedding dimension.

Concretely, when constructing a solution for one parallel SFC deployment instance, HGNN-PSFC performs inference |F| times with the GNN policy for placement decisions, plus one additional inference for parallelization decisions. One TransformerConv layer has complexity $O(|\mathcal{E}|d+|\mathcal{V}|d^2)$, where $|\mathcal{V}|$ and $|\mathcal{E}|$ denote the number of nodes and edges. Our heterogeneous enhancement incorporates three specialized attention computation types: VNF dependency modeling with complexity $O(|{\mathcal{E}}_{\mathit{dep}}|d+|F|d^2)$, physical network topology modeling with complexity $O(|{\mathcal{E}}_{\mathit{net}}|d+|N|d^2)$, and cross-graph mapping relationship modeling with complexity $O(|N|d+|N+F|d^2)$.

Considering that |F| is significantly smaller than $|{\mathcal{E}}_{\mathit{dep}}|$ and typically $|{\mathcal{E}}_{\mathit{net}}|>|N|$ in practical network systems, the overall complexity of HGNN-PSFC is $O(|F|·K·(|{\mathcal{E}}_{\mathit{net}}|d+|N+F|d^2))$.

Because training is performed offline and inference is polynomial in substrate size and embedding dimension, HGNN-PSFC provides predictable online latency for repeated decision-making. By contrast, exact combinatorial solutions (e.g., ILP formulations or dynamic programming approaches such as PPC) have worst-case super-polynomial or exponential growth in problem parameters. In particular, the SF-cluster assignment step of PPC has been shown to admit worst-case growth of order $O(|F{|}^{1+|F|/2})$ in chain length |F| (cf. (Lin et al. 2021)), making such methods practical only for small |F| or when exact optimality is required.

Performance evaluation and analysis

This section presents the experimental evaluation of the proposed reinforcement learning-based parallel SFC deployment framework. The evaluation is conducted in two parts: the first part validates the effectiveness of parallel SFC placement by comparing with baseline methods when parallel SFC requests (represented as PSFGs, as described earlier) are pre-generated, focusing solely on the placement decision. The second part evaluates the complete framework performance where both parallelization and placement decisions are made jointly by the cooperative agents.

Baseline methods and algorithms compared

To the best of our knowledge, no existing RL-based approach explicitly addresses the parallelization decision in parallel SFC deployment. Therefore, for a fair comparison, we construct hybrid baselines in which the parallelization configuration is determined by an enumeration-based non-RL algorithm, while the VNF placement is handled by representative RL algorithms.

We compare the proposed method with four baseline algorithms:

1. Partial Parallel Chaining (PPC) (Lin et al. 2021): This approach identifies optimal partial parallelism configuration and instance selection to minimize end-to-end delay. PPC consists of two phases: partial parallelism enumeration using dynamic programming to find all feasible configurations, and NF instance assignment using layer graph construction to minimize overall delay considering execution, transmission, and parallelization costs.

2. Sequential Chaining (SEQ-PPC): This baseline represents PPC with a constrained partial parallelism enumeration phase that only considers sequential execution configurations. In this variant, all network functions are processed in strict sequential order without any parallelization, essentially selecting the fully sequential option from PPC’s configuration space. The NF instance assignment phase remains identical to PPC, using layer graph construction for optimal instance selection.

3. Full Parallelization (FULL-PPC): This baseline represents PPC with a constrained partial parallelism enumeration phase that only considers maximal parallelization configurations. All independent network functions identified by dependency analysis are executed simultaneously, essentially selecting the fully parallel option from PPC’s configuration space. The NF instance assignment phase follows the same layer graph approach as PPC.

4. PPC + MADRL-P&R (Wang et al. 2022): This hybrid baseline combines PPC’s partial parallelism configuration phase with the MADRL-P&R algorithm for VNF placement. MADRL-P&R utilizes a multi-agent deep reinforcement learning framework to jointly optimize placement and routing.

It is worth noting that while PPC can theoretically achieve optimal solutions within its defined search space through exhaustive enumeration of all feasible parallelization configurations, it suffers from exponential computational complexity that grows prohibitively with chain length and network size. This computational burden makes PPC impractical for large-scale real-time deployments where timely decision-making is critical. In contrast, our proposed HGNN-PSFC framework maintains polynomial complexity during online execution by leveraging offline training to learn efficient parallelization and placement policies. This design choice enables superior scalability while achieving near-optimal performance through intelligent approximation rather than exhaustive search.

Evaluation settings

We conduct experiments using the GEANT topology from the SDNlib (Orlowski et al. 2010) dataset, which represents the European academic network infrastructure. This real-world topology provides a realistic evaluation environment for testing the effectiveness of our parallel SFC deployment framework. The network nodes and link resources, including processing and transmission delays, are parameterized as follows: $C_u^{\text{c}}\sim U(250,350)$, $r_m^{\text{c}}\sim U(1,5)$, $d_{m,n}^{\text{proc}}\sim U(1.5,4)$, $d_l^{\text{trans}}\sim U(0.5,3)$. The number of VNF types and the SFC length are both set to 5. The VNFs used in our simulations are typical middleboxes (firewall, load balancer, NIDS, gateway, and monitor); for each SFC the VNFs are selected randomly. Parallelizability relationships between VNF pairs are assigned following the parallelization/duplication criteria described in Sun et al. (2017b). These settings are consistent with those used in prior work Wang et al. (2022); Lin et al. (2021).

For the reinforcement learning framework, the hetero GNN feature extractors consist of three layers of TransformerConv. The embedding dimension is 128. Training uses the MAPPO algorithm with default hyperparameters from RLlib (Liang et al. 2018).

[See PDF for image]

Fig. 7

CDF of end-to-end delay for parallel SFC placement

Evaluation results

Parallel SFC placement effectiveness

In this evaluation, we provide pre-generated parallel SFC requests where the parallelization decisions have been made, and algorithms only decide the placement of parallel VNFs. In this scenario, the parallelization agent remains inactive as the parallelization structure is predetermined. Since parallelization decisions are not considered in this phase, we compare our approach against SEQ-PPC, FULL-PPC, and the hybrid PPC + MADRL-P&R algorithms to evaluate the placement effectiveness under different parallelization strategies.

Delay performance

We evaluate the placement effectiveness by deploying 200 parallel SFC requests across the substrate network. Figure 7 shows the cumulative distribution function (CDF) of end-to-end delay for different placement algorithms. The HGNN-PSFC algorithm exhibits superior performance compared to the SEQ-PPC and the hybrid PPC + MADRL-P&R baseline, while remaining competitive with the benchmark FULL-PPC method. Specifically, HGNN-PSFC achieves an average delay of 39.78, closely aligning with FULL-PPC’s 36.65, and outperforming the hybrid PPC + MADRL-P&R baseline which records a slightly higher average delay of 43.27. By contrast, SEQ-PPC shows substantially worse performance with an average delay of 53.75. Remarkably, approximately 75% of the delay values for HGNN-PSFC are distributed within the range of 0 to 50 units, compared to only about 44% for SEQ-PPC and roughly 67% for the hybrid PPC + MADRL-P&R baseline. These results underscore that HGNN-PSFC effectively manages delay metrics within the parallel SFC deployment context.

Figure 8 further illustrates the average delay comparison among the three algorithms. HGNN-PSFC achieves approximately 92% of FULL-PPC’s performance while outperforming the hybrid PPC + MADRL-P&R baseline and significantly surpassing SEQ-PPC, demonstrating the effectiveness of our learning-based approach. This near-optimal performance is particularly noteworthy considering that HGNN-PSFC operates without the exponential computational overhead associated with PPC’s exhaustive search strategy.

[See PDF for image]

Fig. 8

Average end-to-end delay comparison for parallel SFC placement

Joint parallelization and placement performance

This evaluation validates the complete HGNN-PSFC framework’s capability for joint optimization of both parallelization and placement decisions. In this scenario, SFC requests are provided in SFPG format, allowing the cooperative agents to make both parallelization structure decisions and subsequent placement decisions collaboratively. We compare against PPC, SEQ-PPC, FULL-PPC, and the hybrid PPC + MADRL-P&R algorithms to assess the effectiveness of the joint optimization approach.

Delay performance

Figure 9 shows the CDF of end-to-end delay across different algorithms. HGNN-PSFC achieves performance that approaches PPC’s optimal results while substantially outperforming both SEQ-PPC and FULL-PPC baseline methods. Specifically, HGNN-PSFC attains an average delay of 33.90, which represents approximately 91.8% of PPC’s performance (31.13), while delivering significant improvements over SEQ-PPC (53.75) and FULL-PPC (36.65). Compared with the hybrid PPC + MADRL-P&R (39.73), HGNN-PSFC also achieves a notably lower average delay. Although the hybrid baseline uses PPC to determine a near-optimal parallelization configuration, its subsequent placement stage (being trained or designed separately) lacks the simultaneous coordination with parallelization that HGNN-PSFC performs. Notably, approximately 70% of HGNN-PSFC’s delay values fall within the optimal range of 0 to 40 units, compared to 62% for FULL-PPC and only 23% for SEQ-PPC. This distribution pattern underscores the effectiveness of joint optimization in achieving consistently low delay across diverse network scenarios.

Figure 10 further illustrates the average delay comparison among the four algorithms. The results clearly demonstrate that HGNN-PSFC achieves near-optimal performance compared to PPC. The 8.2% performance gap relative to PPC represents an excellent trade-off considering the substantial reduction in computational complexity from exponential to polynomial time. Moreover, HGNN-PSFC consistently outperforms the hybrid PPC + MADRL-P&R baseline, indicating the advantage of end-to-end joint learning over approaches that decouple parallelization and placement.

Figure 11 shows that HGNN-PSFC achieves a level of parallelization that is close to that of the benchmark PPC, indicating that while the learned policy may occasionally select suboptimal parallelization structures, it maintains high overall efficiency. This slight deviation in parallelization optimality is consistent with the delay results discussed previously, where the performance gap can be attributed to suboptimalities in both placement and parallelization decisions.

[See PDF for image]

Fig. 9

CDF of end-to-end delay for joint optimization

[See PDF for image]

Fig. 10

Average end-to-end delay comparison for joint optimization

[See PDF for image]

Fig. 11

Degree of parallelization comparison

[See PDF for image]

Fig. 12

Acceptance rate under varying arrival rates

[See PDF for image]

Fig. 13

Average delay by topology

Acceptance rate under varying arrival rates

To evaluate scalability under different traffic loads, we measure the acceptance rate as the SFC request arrival rate increases. SFC requests are generated according to a Poisson process with arrival rates varied between 50 and 300 arrivals per 100 time units; the lifetime of each request is modeled as an independent exponential random variable with mean 1000 time units. Figure 12 reports results for the three algorithms considered in this work (PPC, HGNN-PSFC, and the hybrid PPC + MADRL-P&R). While PPC attains the highest acceptance rate, HGNN-PSFC closely approaches PPC’s performance and consistently outperforms the hybrid PPC + MADRL-P&R across the tested range of arrival rates. For example, at the upper end of the tested load (300 arrivals per 100 time units), HGNN-PSFC sustains an acceptance rate of 41%, noticeably below PPC (52%) but substantially higher than the hybrid PPC + MADRL-P&R (21.5%). These results indicate that HGNN-PSFC effectively balances parallelization and placement decisions under resource contention.

Performance across different network topologies

We further verify the generality of HGNN-PSFC by evaluating it on the Abilene and ChinaNet (Knight et al. 2011) topologies in addition to GEANT. Figure 13 presents the average end-to-end delay across all three topologies. HGNN-PSFC achieves at least 90% of PPC’s performance in all cases, confirming that the learned policies are not overfitted to a specific network structure. These results highlight the adaptability of the proposed method to different topological scales and connectivity patterns.

The experimental results comprehensively validate that the proposed HGNN-PSFC framework effectively addresses both parallelization and placement decisions through joint optimization, while maintaining computational efficiency and adaptability to dynamic network environments.

Conclusion

This paper addresses the critical challenge of jointly optimizing parallelization and placement for parallel SFC deployment in NFV environments. Traditional methods that decouple these decisions often result in suboptimal performance due to the complex trade-offs between parallelization benefits and overhead costs.

We propose HGNN-PSFC, a novel framework that combines heterogeneous graph neural networks with multi-agent deep reinforcement learning to jointly optimize VNF parallelization and placement. The architecture introduces a Parallelization Agent for deciding VNF parallel structures and multiple Placement Agents for determining placements, coordinated via Centralized Training with Decentralized Execution. This design decomposes the joint optimization into manageable subtasks while maintaining coordination. HGNN-PSFC is the first RL-based solution for SFC parallelization, leveraging a new VNF parallelism graph to capture VNF dependencies and reduce action space complexity. A comprehensive heterogeneous graph representation further enables effective feature learning by modeling the interplay between VNFs, the substrate network, and current placements.

Extensive experiments show that HGNN-PSFC achieves around 92% of the performance of the optimal PPC algorithm while maintaining polynomial computational complexity, indicating its potential scalability and applicability to real-time decision-making in large problem instances. Future work will focus on incorporating additional objectives such as energy efficiency and security, and conducting in-depth evaluations under dynamic traffic conditions and fault scenarios to further assess robustness for real-world deployment.

Author Contributions

Yintan Ai: Conceptualization, Methodology, Software, Writing - original draft. Hua Li: Supervision, Project administration, Funding acquisition. Hongwei Ruan: Validation, Writing - review & editing. Hanlin Liu: Data curation, Investigation.

Funding

This work was supported by the National Natural Science Foundation of China (No. 61862047, No. 62262047), the Inner Mongolia Science and Technology Program (No.201802028, No.2020GG0186), the fund of Supporting the Reform and Development of Local Universities (Disciplinary Construction) and the special research project of First-class Discipline of Inner Mongolia A. R. of China (YLXKZX-ND-036) and the Inner Mongolia Key Research and Development and Achievement Transformation Project (2025YFHH0101).

Data Availability

Data will be made available on reasonable request.

Declarations

Competing interests

The authors declare that they have no competing interests.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

Bao, W; Yuan, D; Zhou, BB et al. Prune and plant: Efficient placement and parallelism of virtual network functions. IEEE Trans Comput; 2020; 69, 6 pp. 800-811.4102960 [DOI: https://dx.doi.org/10.1109/TC.2020.2967661]

Cai, J; Huang, Z; Luo, J et al. Composing and deploying parallelized service function chains. J Netw Comput Appl; 2020; 163, 102637. [DOI: https://dx.doi.org/10.1016/j.jnca.2020.102637]

Cai, J; Huang, Z; Liao, L et al. Appm: adaptive parallel processing mechanism for service function chains. IEEE Trans Netw Serv Manage; 2021; 18, 2 pp. 1540-1555. [DOI: https://dx.doi.org/10.1109/TNSM.2021.3052223]

Chintapalli, VR; Killi, BR; Partani, R et al. Energy-and reliability-aware provisioning of parallelized service function chains with delay guarantees. IEEE Trans Green Commun Network; 2023; 8, 1 pp. 205-223. [DOI: https://dx.doi.org/10.1109/TGCN.2023.3317927]

Herrera, JG; Botero, JF. Resource allocation in nfv: A comprehensive survey. IEEE Trans Netw Serv Manage; 2016; 13, 3 pp. 518-532. [DOI: https://dx.doi.org/10.1109/TNSM.2016.2598420]

Huang, Z; Li, D; Wu, C et al. Reinforcement learning-based delay-aware path exploration of parallelized service function chains. Math; 2022; 10, 24 4698. [DOI: https://dx.doi.org/10.3390/math10244698]

Huang H, Tian J, Min G, et al (2024) Parallel placement of virtualized network functions via federated deep reinforcement learning. IEEE/ACM Trans Network

Jang, S; Ko, N; Kyung, Y et al. Network function parallelism configuration with segment routing over ipv6 based on deep reinforcement learning. ETRI J; 2025; 47, 2 pp. 278-289. [DOI: https://dx.doi.org/10.4218/etrij.2023-0511]

Knight, S; Nguyen, HX; Falkner, N et al. The internet topology zoo. IEEE J Sel Areas Commun; 2011; 29, 9 pp. 1765-1775. [DOI: https://dx.doi.org/10.1109/JSAC.2011.111002]

Kreutz, D; Ramos, FM; Verissimo, PE et al. Software-defined networking: a comprehensive survey. Proc IEEE; 2014; 103, 1 pp. 14-76. [DOI: https://dx.doi.org/10.1109/JPROC.2014.2371999]

Liang E, Liaw R, Nishihara R, et al (2018) Rllib: Abstractions for distributed reinforcement learning. In: International conference on machine learning. PMLR, pp 3053–3062

Lin, KCJ; Chou, PL. Vnf embedding and assignment for network function parallelism. IEEE Trans Netw Serv Manage; 2021; 19, 2 pp. 1006-1016. [DOI: https://dx.doi.org/10.1109/TNSM.2021.3125619]

Lin, IC; Yeh, YH; Lin, KCJ. Toward optimal partial parallelization for service function chaining. IEEE/ACM Trans Network; 2021; 29, 5 pp. 2033-2044. [DOI: https://dx.doi.org/10.1109/TNET.2021.3075709]

Lin, X; Guo, D; Shen, Y et al. Sft-box: An online approach for minimizing the embedding cost of multiple hybrid sfcs. IEEE/ACM Trans Network; 2022; 31, 4 pp. 1463-1477. [DOI: https://dx.doi.org/10.1109/TNET.2022.3221868]

Lin X, Guo D, Shen Y, et al (2018) Dag-sfc: Minimize the embedding cost of sfc with parallel vnfs. In: Proceedings of the 47th international conference on parallel processing, pp 1–10

Li B, Tan K, Luo L, et al (2016) Clicknp: Highly flexible and high performance network processing with reconfigurable hardware. In: Proceedings of the 2016 ACM SIGCOMM Conference, pp 1–14

Lowe R, Wu YI, Tamar A, et al (2017) Multi-agent actor-critic for mixed cooperative-competitive environments. Adv Neural Inf Process Syst 30

Lu, D; Long, S. Enhancing network function parallelism in mobile edge computing using deep reinforcement learning. ICT Express; 2025; 11, 1 pp. 41-46. [DOI: https://dx.doi.org/10.1016/j.icte.2024.09.011]

Luo, J; Li, J; Jiao, L et al. On the effective parallelization and near-optimal deployment of service function chains. IEEE Trans Parallel Distrib Syst; 2020; 32, 5 pp. 1238-1255. [DOI: https://dx.doi.org/10.1109/TPDS.2020.3043768]

Mijumbi, R; Serrat, J; Gorricho, JL et al. Network function virtualization: State-of-the-art and research challenges. IEEE Commun Surveys Tutor; 2015; 18, 1 pp. 236-262. [DOI: https://dx.doi.org/10.1109/COMST.2015.2477041]

Oliehoek, FA; Amato, C et al. A concise introduction to decentralized POMDPs,; 2016; Springer: [DOI: https://dx.doi.org/10.1007/978-3-319-28929-8] 1

Orlowski S, Wessäly R, Pióro M, et al (2010) Sndlib 1.0—survivable network design library. Netw: An Int J 55(3):276–286

Schulman J, Moritz P, Levine S, et al (2015) High-dimensional continuous control using generalized advantage estimation. arXiv:1506.02438

Schulman J, Wolski F, Dhariwal P, et al (2017) Proximal policy optimization algorithms. arXiv:1707.06347

Shi Y, Huang Z, Feng S, et al (2020) Masked label prediction: Unified message passing model for semi-supervised classification. arXiv:2009.03509

Sun, C; Bi, J; Zheng, Z et al. Hyper: a hybrid high-performance framework for network function virtualization. IEEE J Sel Areas Commun; 2017; 35, 11 pp. 2490-2500. [DOI: https://dx.doi.org/10.1109/JSAC.2017.2760438]

Sun C, Bi J, Zheng Z, et al (2017b) Nfp: Enabling network function parallelism in nfv. In: Proceedings of the conference of the ACM special interest group on data communication, pp 43–56

Troia, S; Savi, M; Nava, G et al. Performance characterization and profiling of chained cpu-bound virtual network functions. Comput Netw; 2023; 231, 109815. [DOI: https://dx.doi.org/10.1016/j.comnet.2023.109815]

Wang, S; Yuen, C; Ni, W et al. Multiagent deep reinforcement learning for cost-and delay-sensitive virtual network function placement and routing. IEEE Trans Commun; 2022; 70, 8 pp. 5208-5224. [DOI: https://dx.doi.org/10.1109/TCOMM.2022.3187146]

Wang R, Luo J, Dong F, et al (2019) Paranf: Enabling delay-balanced network function parallelism in nfv. In: 2019 IEEE 23rd international conference on computer supported cooperative work in design (CSCWD). IEEE, pp 392–397

Xie, S; Ma, J; Zhao, J. Flexchain: Bridging parallelism and placement for service function chains. IEEE Trans Netw Serv Manage; 2020; 18, 1 pp. 195-208. [DOI: https://dx.doi.org/10.1109/TNSM.2020.3047834]

Xu, H; Fan, G; Sun, L et al. Dynamic sfc placement scheme with parallelized sfcs and reuse of initialized vnfs: An a3c-based drl approach. J King Saud University-Comput Inf Sci; 2023; 35, 6 101577. [DOI: https://dx.doi.org/10.1016/j.jksuci.2023.101577]

Yi, B; Wang, X; Li, K et al. A comprehensive survey of network function virtualization. Comput Netw; 2018; 133, pp. 212-262. [DOI: https://dx.doi.org/10.1016/j.comnet.2018.01.021]

Yu, C; Velu, A; Vinitsky, E et al. The surprising effectiveness of ppo in cooperative multi-agent games. Adv Neural Inf Process Syst; 2022; 35, pp. 24611-24624.

Zhang C, Sato T, Oki E (2023) Service deployment for parallelized function chains considering traffic-dependent delay. IEEE Trans Netw Serv Manage 21(2):2266–2286

Zhang, K; Zhou, Y; Zhang, S et al. Towards deploying sfc with parallelized vnfs under resource demand uncertainty in mobile edge computing. J King Saud University-Comput Inf Sci; 2023; 35, 7 101619. [DOI: https://dx.doi.org/10.1016/j.jksuci.2023.101619]

Zhang Y, Anwer B, Gopalakrishnan V, et al (2017) Parabox: exploiting parallelism for virtual network functions in service chaining. In: Proceedings of the symposium on SDN research, pp 143–149

Zhang D, Wang L, Rezaeipanah A (2024) Towards deploying parallelized service function chains under dynamic resource request in multi-access edge computing. IEEE Trans Netw Service Manage

Zhang Y, Zhang ZL, Han B (2019) Hybridsfc: Accelerating service function chains with parallelism. In: 2019 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). IEEE, pp 1–7

Zheng, D; Shen, G; Cao, X et al. Towards optimal parallelism-aware service chaining and embedding. IEEE Trans Netw Serv Manage; 2022; 19, 3 pp. 2063-2077. [DOI: https://dx.doi.org/10.1109/TNSM.2022.3142184]