IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
1
RQ-SAFE: Coupled Request–Resource Scheduling for Online Edge SFC-DAGs
arXiv:2606.25467v1 [cs.NI] 24 Jun 2026
Shengdong Gu, Hongyuan Wan, and Taixin Li
Abstract—Intent-driven edge services allow multiple virtual network function (VNF) segments in a service function chain directed acyclic graph (SFC-DAG) to be locally reordered without changing service semantics, creating richer request-side orchestration freedom. Existing orchestration methods mainly optimize VNF placement, routing, or queue-aware scheduling for a predetermined service order; they do not fully exploit this freedom or couple it with runtime resource scheduling. This paper presents RQ-SAFE, a request–resource coupled scheduling framework for online edge SFC-DAG orchestration with checked commitment. RQ-SAFE evaluates each feasible local order by previewing its resource-side consequences on the current edge infrastructure, and uses the retained order to guide VNF instance selection and path construction. Queue state is used throughout the decision process to evaluate local orders, rank per-VNF candidates, and perform final queue-aware quality-of-service (QoS) validation. A profile-aware learning-assisted re-ranker balances request-side QoS objectives and resource-side load objectives by refining retained top-K candidates. On matched edge SFC-DAG workloads, RQ-SAFE achieves comparable QoS-compliant service outcomes to graph-aware baselines while improving resource balance. Relative to the graph neural network (GNN)-based GNN-DAG-Score baseline on public-mixed workloads, it reduces central processing unit (CPU) imbalance by 6.1% and peak CPU by 2.3%, with limited additional control-plane decision time. Ablation results show that enabling local-order flexibility and queue awareness together improves QoS by 4.53 percentage points over disabling both factors, with a 3.83 percentage-point positive interaction between the two factors. Overall, RQ-SAFE offers a practical request–resource coupling paradigm for exploiting orchestration freedom in intent-aware edge SFC-DAG services. Index Terms—Service function chain, edge orchestration, SFCDAG, intent-driven networking, request–resource scheduling, queue-aware placement, VNF placement.
Shengdong Gu is with the School of Data Science and Artificial Intelligence, Dongbei University of Finance and Economics, Dalian, China. Hongyuan Wan is with the School of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian, China. Taixin Li is with the School of Data Science and Artificial Intelligence, Dongbei University of Finance and Economics, Dalian, China. Corresponding author: Taixin Li.
I. I NTRODUCTION
E
DGE computing, software-defined networking (SDN), and network function virtualization (NFV) allow service functions to run on shared infrastructure instead of dedicated appliances [1], [2]. Virtual network functions (VNFs) are commonly connected as service function chains (SFCs) for security inspection, traffic filtering, encryption, caching, and forwarding [3]–[5]. At the edge, orchestration must operate under limited node capacity, heterogeneous link delay, and time-varying demand [6]–[8]. Each active VNF instance also has running tasks, waiting requests, and finite service capability. A placement that looks feasible from static processing and path delay may therefore violate its quality-of-service (QoS) budget after the traffic reaches a congested instance [9]. Intent-driven management is also making service requests more flexible. A service objective, security rule, or QoS target can be specified while part of the VNF order remains open [10]–[12]. The resulting service may contain branches, merges, and functions whose relative order is only partially constrained. It is naturally represented as an SFC directed acyclic graph (SFC-DAG) or VNF forwarding graph [13], [14]. This representation exposes request-side orchestration freedom: several local execution orders can preserve service semantics but lead to different VNF instances, paths, queue pressure, and load-distribution outcomes. This freedom cannot be used effectively without observing the current resource state. A local rewrite that is beneficial under one service-pool snapshot can become inferior when queues or node loads change. Likewise, reusing a warm instance can reduce activation delay but consume the remaining QoS margin if that instance is busy. The orchestration problem therefore goes beyond choosing an order and then placing VNFs. Request-side order choices should be evaluated through their resource-side consequences, and resource-side placement should remain conditioned on the selected request structure. Recent placement and protection methods improve resource allocation for supplied SFCs [28], [29]. Parallelized-SFC studies further model dynamic resource demand and uncertain traffic [25], [26]. Queue-aware schedulers make congestion visible during routing or placement, and learning-based methods can absorb rich runtime features. These lines provide important building blocks. RQ-SAFE addresses a missing decision: how a bounded set of semantics-preserving local reordering actions should be used under the current queue, path, service-pool, and load state, and how the selected order should guide detailed instance construction. This paper presents RQ-SAFE, a request–resource coupled framework for joint online scheduling of edge SFC-DAGs.
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
RQ-SAFE extracts a compact set of semantics-preserving local-order actions and evaluates each action through a placement-aware preview. This preview links request completion and QoS requirements with queue, path, service-pool, and load conditions before the order is retained. Detailed placement then proceeds under the retained order, and candidate scores are recomputed as the partial plan evolves. Learningassisted re-ranking is used as a bounded refinement inside the retained top-K candidate neighborhood, while action choices, fallbacks, validation checks, and outcomes remain traceable. The main contributions are as follows. • We formulate online edge SFC-DAG orchestration as request–resource joint scheduling. A request-side order action is evaluated by the placement result it would produce, and the selected order then shapes the candidate instances and paths considered on the resource side. • We develop a semantics-preserving local reordering mechanism and a recursive order-aware candidate model. The model jointly considers QoS margin, queue pressure, path delay, service reuse, projected node load, hotspot risk, and candidate availability. • We make queue state the runtime coupling signal between request-side order flexibility and resource-side placement. Queue-aware feedback guides local-order evaluation, perVNF candidate ranking, and final QoS validation with queueing delay. The profile-aware learning-assisted reranker then adjusts the tradeoff between QoS and load within retained top-K candidates, while constrained selection and request-level records keep the decision path traceable. The remainder of this paper is organized as follows. Section II positions the work. Section III defines the request– resource coupling model. Section IV presents RQ-SAFE. Section V reports the evaluation, and Section VI concludes the paper. II. R ELATED W ORK SFC placement, routing, and protection. Classical SFC orchestration maps VNFs to physical nodes and routes service traffic through the selected instances under node, link, and delay constraints [15], [16]. Edge-oriented methods further consider service deadlines, heterogeneous edge devices, instance reuse, and protection requirements [17]–[19], [28], [29]. These studies form the resource-feasibility foundation for online SFC deployment. They also show that placement quality depends on multiple runtime factors rather than on CPU capacity alone. However, their decision input is usually a chain or service graph that has already been specified. The order in which functions should be executed is not treated as a runtime decision coupled with placement. RQ-SAFE keeps the familiar placement and path-construction view, but adds an earlier decision: which legal local order should be used before detailed instance selection begins. This distinction matters for edge environments because the placement decision is often made online and under partial resource visibility. A request can be accepted, delayed, or rejected according to the instance and path state that exists at
2
the arrival time. If the request order is treated as immutable, a scheduler can still improve path selection or load balancing, but it cannot ask whether an equivalent local order would avoid a congested instance or a hot node. RQ-SAFE therefore keeps the standard VNF-to-node and virtual-edge-to-path mapping interface, while moving one request-interpretation decision into the online loop. SFC-DAGs and parallelized deployment. VNF forwarding graphs and SFC-DAGs extend linear chains by representing branches, merges, partial ordering, and parallel processing [13], [21]–[24]. Recent studies optimize parallelized SFCs under dynamic resource requests, uncertain traffic arrival rates, and multi-domain migration [25]–[27]. These works are important because they move service descriptions beyond a single fixed chain. Their main concern, however, is how a supplied graph or parallel structure should be embedded, migrated, or protected. RQ-SAFE addresses a complementary question. It does not enumerate all topological orders or serialize independent branches. Instead, it exposes a compact set of semantics-preserving local reordering actions and asks whether any of them becomes useful under the current servicepool, path, queue, and load state. The difference is not only the size of the graph. In a forwarding graph, two services may be unordered because they are independent, or because their order is semantically interchangeable in a local context. Treating both cases as arbitrary topological choices can create a large and hardto-audit action space. Treating the graph as fixed loses the opportunity to exploit the interchangeable segment. RQ-SAFE takes a middle position: it records branch and merge structure, but turns only declared and structurally guarded serial pairs into runtime local-order actions. Queue-aware scheduling and QoS control. Queue-aware routing, fair scheduling, rate control, stochastic scheduling, and online SFC control use queue length, waiting time, or service rate to capture runtime congestion [9], [32]–[36]. These works motivate our use of instance-level queue state and QoS validation with queueing delay. In representative formulations, queue state changes resource-side routing or placement after the service order is given. This is valuable but still leaves request-side order freedom outside the queue-aware loop. RQ-SAFE uses queue-aware provisional placement to evaluate legal local orders themselves. Thus, queue state is not only a delay correction after placement; it is a signal that changes how request-side orchestration freedom is used. This placement of queue state also affects how QoS is interpreted. A delay budget can be satisfied by a static pathdelay estimate and still fail after deployment if the chosen instance has accumulated work. Conversely, a path with slightly higher propagation delay can be preferable when it reaches a low-waiting warm instance. RQ-SAFE therefore uses queue state before, during, and after candidate construction: before placement to compare legal local orders, during placement to rank instances, and after placement to validate the complete end-to-end delay with queueing. Learning-based and lifecycle-aware orchestration. Learning has been used for VNF placement, graph embedding, dynamic SFC deployment, and multiobjective coordination [30], [37]–
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
3
TABLE I P OSITIONING OF RQ-SAFE R ELATIVE TO R EPRESENTATIVE O RCHESTRATION L INES Approach line Request-side treatment Placement, routing, and protec- Fixed chain or supplied service graph tion [28], [29]
Runtime-state treatment Decision boundary relative to RQ-SAFE Resource, path, delay, heterogeneity, or pro- Optimizes deployment of the supplied request; localtection costs order freedom is handled outside the runtime decision Parallelized SFC/SFC- Rich branch/merge or parallel structure Dynamic demand, uncertain traffic, migra- Optimizes a supplied parallel structure rather than DAG [23], [25]–[27] tion, and placement state a bounded semantic rewrite chosen through live placement preview Queue-aware scheduling [9], Service order is generally given Queue length, waiting time, service rate, and Queue state changes routing or placement; RQ-SAFE [36] QoS are explicit also lets it change the use of legal order freedom Learning-based orchestra- Graph or placement actions may be Runtime features enter a learned score or RQ-SAFE separates semantic actions and placementtion [14], [30] learned jointly policy aware preview from retained-candidate re-ranking RQ-SAFE Bounded linear or branch-local semantic Order-aware completion, queue, path, Closes an action-level preview loop and a stagerewrites service-pool, and load state level placement loop before queue-aware checked commitment
[42]. Such methods can absorb graph and runtime features, but an end-to-end policy over orders, instances, paths, and access decisions can be difficult to inspect and validate online. Recent lifecycle-aware work also shows that activation, reconfiguration, and reuse state should remain visible to placement logic [31]. RQ-SAFE therefore places learning at a narrower boundary. Semantic action generation, placement-aware preview, feasibility checks, and fallback remain explicit. The learning-assisted component only refines the order of retained instance candidates inside a filtered neighborhood. This design also separates two forms of adaptivity. The first is structural adaptivity: the orchestrator may choose a different legal local order when runtime state changes. The second is candidate adaptivity: for the retained order, the orchestrator may prefer a different instance or path as queues, reuse opportunities, and node pressure evolve. A broad learned policy could merge these forms into one action, but then the reason for a decision is harder to isolate. RQ-SAFE keeps them as explicit interfaces and uses learning only where a bounded candidate neighborhood has already been constructed. Position of RQ-SAFE. The above lines are complementary rather than competing. Placement and routing provide the resource substrate, SFC-DAG studies provide the servicegraph representation, queue-aware methods expose runtime congestion, and learning-based orchestration offers candidate refinement. The gap is their decision boundary: existing methods typically optimize a supplied order or learn a broad action space. RQ-SAFE focuses on the missing middle layer between request semantics and resource placement. It evaluates a small set of legal local orders through live placement preview and then lets the retained order guide recursive instance and path construction. Table I summarizes this positioning.
III. R EQUEST–R ESOURCE C OUPLING M ODEL This section retains only the background needed to define the paper-specific decision interface. Standard SFC mapping and routing constraints are summarized in the appendix. The focus here is how partial-order freedom becomes an actionable online variable and how the request and resource sides are joined into one recursive decision process. Table II lists the symbols used in this section and in the online orchestration algorithm.
TABLE II K EY N OTATIONS Notation S(t) Gi = (Vi , Ei ) Ci Aord i πia a Pi,<v ea (t) A i,v creq , cres , ccpl b Pi (a) gi (a, t) K Ti,v b e2e , D max D i i Hi
Description Current service pools, queues, node loads, links, and active requests. SFC-DAG of request ri . Semantically and structurally admissible local reordering pairs. Bounded request-side local-order action set. Orchestration order induced by action a. Partial plan before placing VNF v under action a. Filtered instances for v under the partial plan. Request-side, resource-side, and coupled candidate costs. Provisional plan produced for order action a. Placement-aware preview vector of order action a. Retained top-K instance candidates. Estimated delay including queueing and request budget. Per-request trace of actions, candidates, checks, and result.
A. System and Request State Fig. 1 gives the deployment view used by the model. The orchestrator sits above SDN/NFV control and edge dataplane components, receives telemetry from queues, links, service pools, and node loads, and commits only the checked placement and path plan that will steer packet traffic through selected VNF instances. The edge infrastructure is a directed graph GE = (N , L). At time t, the orchestrator observes S(t) = ⟨P(t), Q(t), U(t), L(t), Ract (t)⟩,
(1)
where P(t) is the warm/cold VNF service pool, Q(t) is the instance-level queue state, U(t) is node utilization, L(t) is link state, and Ract (t) contains unfinished requests. Instance s cs (t), and hosting node has VNF type k(s), waiting estimate W n(s). Mapping VNF v to s adds an effective CPU increment cpu to the request-local ledger. This increment distinguishes ∆rv,s cold activation from conservative warm-instance reuse. Request ri contains an SFC-DAG Gi = (Vi , Ei ), traffic demand, QoS class, priority, and end-to-end delay budget Dimax . Its online decision is Xi (t) = ⟨ai , ϕi , ρi , δi ⟩,
(2)
where ai is a legal local-order action, ϕi maps VNFs to instances, ρi maps dependency edges to paths, and δi is the final success/reject decision. The key difference from a fixedorder formulation is that ai is evaluated through the placement process rather than fixed before it.
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
4
Fig. 1. System-level view of RQ-SAFE in an SDN/NFV-enabled edge deployment. Solid arrows denote packet traffic steered through selected VNF instances, dashed arrows denote policy and actuation commands from the orchestrator through SDN/NFV controllers, and dotted arrows denote telemetry feedback. RQ-SAFE couples bounded request-side local reordering actions with queue/resource/path-aware placement preview, candidate construction, learning-assisted retained-candidate re-ranking, and queue-aware validation before checked state update.
B. Request-Side Freedom At runtime, RQ-SAFE uses a compact set of request-side actions rather than all topological orders. Let Aloc i (u, v) = 1 indicate that (u, v) is a local pair eligible for structural inspection. In a linear chain, it is an internal adjacent pair. In a branch or general DAG, it is a directed serial pair on one branch whose two endpoints have unique local predecessor/successor context; merge and tail nodes are excluded. A pair is exposed only when its VNF types are declared semantically compatible and the local rewrite preserves the surrounding graph. We define
RQ-SAFE exposes the no-change action and at most one local rewrite per admitted pair: ord Aord = {a0i } ∪ {aswap i i,u,v : (u, v) ∈ Ci }, |Ai | ≤ 1 + |Ci |.
(4)
(3)
For a linear request, the action exchanges the adjacent internal pair. For an admissible branch-local serial pair, it rewrites only the local segment p → u → v → s as p → v → u → s. All other edges are retained. Independent siblings remain parallel and are not converted into a semantic order action. Eq. (4) therefore converts abstract partial-order freedom into a small and auditable online set without enumerating all topological orders.
where Ψτi is the request-family compatibility rule and Γi is the structural guard. Unknown or stateful combinations default to non-commutable. Starting from a valid base orchestration representation πi0 ,
C. Order-Aware Joint Candidate Model a For action a and partial plan Pi,<v , type compatibility, service availability, request-local available CPU capacity, and
Ci = {(u, v) : Aloc i (u, v) = 1, Ψτi (k(u), k(v)) = 1, Γi (u, v) = 1}.
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
configured path construction form the candidate set Aeai,v (t) = {s : k(s) = k(v), s is available and locally feasible}. (5)
The set and the value of a candidate both depend on a. A different order changes the predecessor nodes already selected, the path entering v, the remaining VNFs, the available service pools, and the QoS slack at this stage. The request side asks whether a candidate preserves the service’s completion capability. We summarize its completionoriented cost as path bsvc creq i,v,s (a, t) =λp dv,s + λl di,v,s (a, t) (6) future + λτ dct i,v,s (a, t) + λf di,v,s (a, t), where the terms describe processing/activation completion, predecessor-to-candidate path delay, critical/merge/tail exposure, and the risk of consuming a scarce candidate needed later. The resource side asks whether the same choice avoids current congestion and future concentration: cpu c cres i,v,s (a, t) =λq Ws (t) + λu pv,s (t) + λh Hi,v,s (a, t) (7) + λb Bi,v,s (a, t) − λw Rv,s (t), where H and B represent hotspot and branch-concentration pressure, and R is a bounded warm/service-pool reuse benefit. Projected CPU pressure is cpu cpu Un(s) (t) + ∆rv,s . (8) pcpu (t) = cpu v,s Cn(s) Queue pressure remains separate from CPU pressure because a node can have sufficient available CPU capacity while its matching service instance is busy. The two sides enter one order-aware preference: req req res res ccpl i,v,s (a, t; p) = βp ci,v,s (a, t) + βp ci,v,s (a, t),
(9)
where deployment profile p sets the relative emphasis on completion/QoS and load pressure. Because the components in Eqs. (6) and (7) have different physical units, each raw term is first converted by a fixed bounded transform into a dimensionless score. The scaling constants are taken from the configuration or validation split and remain fixed for the heldout test runs. The profile coefficients βpreq and βpres are nonnegative and are reported on the normalized scale βpreq + βpres = 1, which preserves the induced ordering. A conservative profile assigns more emphasis to completion slack, critical stages, and tail exposure, whereas a throughput-oriented profile tolerates greater projected pressure when reusable service capacity is available. The profile changes candidate preference while preserving the semantic action set, feasibility filters, and recursive coupling structure. The implementation realizes this preference through bounded base, critical-path, tail/future, and resource/reuse score groups. Eq. (9) is their compact modeling interface rather than a claim of global scalarized optimality. The joint process is recursive. Under action a, VNF v is considered using the current partial plan, and a retained candidate is chosen from the coupled ranking:
5
After the tentative assignment, predecessor locations, path costs, projected node pressure, reuse opportunities, and future scarcity all change. They are recomputed for the next VNF. The resource side therefore feeds back after every stage of the retained order rather than assigning one fixed score to the whole request. D. Placement-Aware Preview and Coupling Loop A legal action is useful only if it leads to a better provisional plan under the current state. RQ-SAFE applies the recursive process in Eq. (10) to build bi (a) = G(πia , S(t)), P (11) where G denotes the lightweight placement preview. Its observable consequences are summarized as b proc (a), D b queue (a), gi (a, t) = ⟨χi (a), D i i (12) net e2e b b b ie2e (a)⟩, Di (a), Di (a), Dimax − D where χi (a) indicates whether the provisional placement succeeds. The action comparison rule first favors feasibility and then lower completion cost including queueing. It retains the original order or a better local rewrite according to these runtime consequences. Eqs. (10)–(12) show how the two sides are connected. At the action level, a request-side rewrite induces a full provisional placement, and the resource state decides whether that rewrite is useful. At the stage level, the retained order determines the predecessor context, while every tentative resource choice updates the partial plan used by the next stage. This two-way dependency is the joint scheduling mechanism. It is stronger than placing VNFs after a fixed order, and more controlled than learning one unrestricted order–placement action. A concrete branch-local example illustrates the two-way dependence. Consider two legal alternatives, p → Detect → Cache → s and p → Cache → Detect → s. Suppose that the nearest detection instance currently has a long queue, while a low-waiting warm cache instance is available on another edge node. Under the base order, placing Detect first consumes part of the delay budget and fixes the predecessor node and path used to evaluate Cache. Under the rewrite, Cache is placed first, so its selected node changes the path, queue pressure, and feasible detection candidates seen by the next stage. After this tentative assignment, Eq. (10) updates the partial plan and recomputes all candidate terms for the second VNF. A later queue-state change can reverse the preferred order. Thus, the two orders do not receive fixed priorities; they are compared through the state transitions induced by their provisional placements. E. Queue Awareness Throughout the Online Model
cs (t) Queue information enters at three points. First, W changes the provisional placement and hence the comparison among legal actions. Second, it changes the per-VNF candidate ranking in Eq. (7). Third, the complete plan is evaluated with end-to-end delay including queueing. For VNF v mapped to K cpl a a Ti,v (a, t) = TopKs∈Aea (t) {−ci,v,s (a, t; p)}, Pi,≤v = Pi,<v ⊕ (v, sv ).s = ϕi (v), i,v start c (10) Tbifinish (v) = Tbistart (v) + dbproc , (13) v,s + Ws (t) + Ds
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
Algorithm 1 RQ-SAFE Online Orchestration Require: Request ri , runtime state S(t), deployment profile p Ensure: Decision δi and selected plan Pi 1: Apply lightweight risk screening 2: Extract Aord from semantic and structural rules i 3: for each a ∈ Aord do i bi (a) and preview gi (a, t) 4: Build provisional plan P 5: end for 6: Retain the preferred legal action(s) 7: for each retained action a in preview order do 8: for each VNF v in πia do ea (t) and compute coupled scores 9: Form A i,v K and optionally re-rank it 10: Retain Ti,v 11: Select a candidate and update the request-local partial plan 12: end for 13: Recompute end-to-end delay including queueing 14: if the complete request-local plan satisfies the success checks then 15: Update global runtime state and return δi = 1, Pi 16: end if 17: end for 18: return δi = 0
6
Access control is used only as a lightweight prefilter: clearly unsuitable requests are rejected, whereas accept and trial requests enter the same coupled action/placement loop. For each remaining request, the implementation extracts the legal actions in Aord i , builds a request-local provisional plan for each action, and retains at most Kπ actions according to their preview outcomes. Detailed placement then follows the retained order. At every VNF stage, the implementation evaluates bounded base, critical-path, tail/future, and resource/reuse groups corresponding to Eq. (9). The request-local partial plan is updated immediately after a tentative assignment. Consequently, predecessor paths, queue pressure, CPU pressure, reuse opportunities, and future scarcity are recomputed before the next VNF is ranked. This execution realizes the actionlevel and stage-level loops defined in Section III. B. Learning-Assisted Re-Ranking
where Dsstart is zero for an active instance and is the configured activation delay for a cold candidate. The start time follows the DAG precedence relation: αi , Pred(v) = ∅, Tbistart (v) = finish net b max { T (u) + D }, otherwise. i i,u,v u∈Pred(v)
(14) The request delay is b e2e = D i
max v∈Sink(Gi )
Tbifinish (v) − αi .
(15)
A successful plan must satisfy its request-local CPU checks and b ie2e + ξ q ≤ Dimax , D (16) i q where ξi is an optional queue-estimation margin. In the reported implementation, checked commitment covers requestlocal CPU feasibility, configured path reachability and latency, and delay-budget validation with queueing delay. Link state can enter path construction, but the paper does not rely on a separate universal residual-bandwidth or queue-capacity guarantee. The reported metrics retain QoS, delay, CPU balance, peak load, and per-request decision time separately so that the operating-point tradeoff remains visible. IV. RQ-SAFE O NLINE O RCHESTRATION Fig. 2 expands the request-level path inside the orchestrator. It separates the input SFC-DAG, the local reordering choice, the shared queue/resource snapshot, the retained top-K candidate lists, and the final validation gate. For each request, RQSAFE narrows the decision space through lightweight access control, semantic action extraction, placement-aware preview, recursive candidate construction, optional learning-assisted reranking, and checked state update. Algorithm 1 summarizes the online path.
The learning module is used only when several retained candidates are close under the deterministic score. It observes request and DAG context, the current partial plan, queue and resource pressure, QoS-related features, and candidate-level K score components. Its output is a revised order within Ti,v . Let 0 L σi,v be the deterministic order and σi,v the learned suggestion: ( L σi,v , if the learned suggestion is accepted, σi,v = (17) 0 σi,v , otherwise. The module operates inside the retained candidate set and leaves semantic order actions to the explicit request-side mechanism. Its role is to adjust the tradeoff among close instance candidates before the common completion and QoS path. C. Success Checks, Fallback, and State Update Candidate construction uses request-local node and queue state. A candidate that lacks service availability or available CPU capacity is skipped, and the next retained candidate can be tried. After a complete plan is formed, end-to-end delay including queueing is recomputed. In the serial replay used for evaluation, global CPU and queue state are updated only after a successful request result. Failed requests leave the shared runtime state unchanged. This structure gives learning a bounded and auditable influence. It may change which retained candidate is tried, but every selected plan reaches the same request-local CPU and queue-aware QoS path. Path reachability and link delay are incorporated during candidate construction. The commitment boundary is therefore explicit in the online path and is further detailed in the appendix. D. Per-Request Traceability
A. Executing the Coupled Model Section III defines the semantic action set, placementaware preview, recursive candidate preference, and queueaware completion check. This section specifies how those objects are executed online rather than defining them again.
For each request, the system records the exposed order actions, preview outcomes, retained candidates, actual candidate order, optional learned suggestion, fallback events, and final result: K run Hi = Aord i , {gi (a, t)}, ai , {Ti,v , σi,v }v∈Vi , Oi , δi . (18)
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
7
Fig. 2. Request-level coupling mechanism of RQ-SAFE. A semantic local rewrite is evaluated by placement-aware preview under the current queue, resource, and path state. The retained order guides recursive candidate construction; profile-aware re-ranking refines close top-K candidates; and the final plan is committed after CPU, path, and queue-aware QoS validation.
The trace links a request-side action to its resource evidence and eventual outcome. It supports mechanism analysis and auditability, and matched experiments provide the performance evidence. V. E XPERIMENTAL E VALUATION A. Experimental Setup We evaluate RQ-SAFE in an online edge SFC-DAG simulator with heterogeneous node capacities, link delays, warm/cold service pools, active tasks, and instance queues. Requests contain a dependency graph, traffic demand, explicit delay budget, priority, and request family. The workload suite covers public benchmark traces and high-concurrency or hybrid SFC-DAG snapshots with branches, merges, and local-order opportunities.
We compare with Greedy-CPU, Latency-Aware, DRLDDQN, and GNN-DAG-Score. All methods use a common request parser, runtime-state builder, workload sequence, topology snapshot, service-pool state, and metric exporter. Each baseline retains its characteristic candidate rule or learned model. GNN-DAG-Score receives graph and runtime-state features from the shared environment; RQ-SAFE additionally receives the semantic action set produced by its request abstraction. The appendix reports the method input/action boundary, figure-specific settings, archive fingerprints, and run accounting. The public-mixed families used in the repeated-run and factorial studies are denoted by W1–W4 when space is limited in tables and figures: W1 is Concurrent-balanced, W2 is Balanced-mixed, W3 is Queue-focused, and W4 is Safetymixed. Each family is evaluated under matched seeds so that
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
240
50
160
25
80
100
35 30 25 20
Germany50
Abilene
Germany50
Abilene
(b) Future-complex
75
80
50
60
25
40
0
Queue: Lower is better ↓
High-conc.
Hybrid
High-conc.
Hybrid
Germany50
Abilene
32 28 24 20
High-conc.
+6.1±4.8%
CPU imbalance
Hybrid
Fig. 3. Cross-workload performance comparison. Panel (a) reports public benchmark workloads, and panel (b) reports future-complex workloads. Markers denote matched workload–seed configurations. QoS-compliant service ratio is higher is better; E2E and queue delay are lower is better. TABLE III PAIRED C OMPARISON WITH GNN-DAG-S CORE
+2.3±2.4%
Peak CPU
+13.8±25.4%
Hot-node ratio -0.6±1.8%
Queue delay
Conc.
-40
-20
Bal.
Queue
0
Safety
Mean ± std
20
Reduction vs. GNN-DAG (%) ↑ better
40
(b) Decision overhead vs. resource balance CPU imbalance (pp; lower is better)
75
0
Success/QoS (%)
320
(a) Public benchmark
(a) Multi-seed edge-resource reduction
RQ-SAFE Queue latency (ms)
Success/QoS (%)
100
GNN
E2E: Lower is better ↓
Queue latency (ms)
DRL Success: Higher is better ↑
8
52
Safety
48
Conc. Queue
GNN-DAG RQ-SAFE GNN → RQ-SAFE
Bal.
44 Mean shift: +78.8 ms, -3.0 pp imbalance
275
300
325
Decision time (ms; lower is better)
350
375
Metric Mean difference 95% paired CI QoS-compliant ratio −1.01 pp [−2.14, 0.19] Success ratio −1.01 pp [−2.14, 0.17] End-to-end delay +0.21 ms [0.04, 0.36] Queue delay +0.12 ms [−0.07, 0.31] QoS-budget use +0.44 pp [0.13, 0.72]
Fig. 4. Multi-seed tradeoff between RQ-SAFE and GNN-DAG-Score on matched public-mixed SFC-DAG workloads. In (a), positive values mean that RQ-SAFE reduces a lower is better metric. In (b), moving right indicates higher per-request decision time and moving down indicates lower CPU imbalance.
paired differences compare the same topology, request order, and service-pool snapshot. The primary metric is the QoScompliant service ratio over all arrivals. We also report endto-end delay, queue delay, peak CPU, CPU imbalance, hotnode ratio, and per-request decision time. Lower values are better for all metrics except the service ratio. The evaluation answers three research questions (RQs): RQ1, how does RQSAFE perform on service outcome and delay; RQ2, how does it change resource balance and per-request decision time; and RQ3, how does request-side order flexibility interact with queue awareness in a direct factorial design?
leading group under strict request accounting. The resourcedistribution results below distinguish their operating points.
B. Research Question 1: Service Outcome Across Workloads Fig. 3 positions DRL-DDQN, GNN-DAG-Score, and RQSAFE by service outcome and delay. Each point corresponds to a matched workload–seed run rather than an independent topology design; the plot therefore visualizes both average behavior and seed-level dispersion. On both public and future-complex groups, RQ-SAFE remains close to the graphaware baseline and avoids the larger dispersion shown by DRL-DDQN in several groups. The explicit joint-scheduling pipeline therefore provides competitive service performance together with an inspectable request-action and candidate path. Table III adds paired accounting on the matched publicmixed workload–seed groups used in the multi-seed comparison. Values are RQ-SAFE minus GNN-DAG-Score; rate and budget metrics are reported in percentage points. The service-ratio interval crosses zero, and the end-to-end and queue-delay shifts are small in absolute value. RQ1 therefore shows that RQ-SAFE preserves the service-performance level of the graph-aware baseline while adding an explicit request– resource coupling path. The stricter topology-scale replay in the appendix reinforces this conclusion: RQ-SAFE and GNN-DAG remain in the
C. Research Question 2: Resource Balance and Decision Time Fig. 4 uses four public-mixed workload families and three matched seeds per family. Relative to GNN-DAG-Score, RQSAFE achieves relative reductions of 6.1% ± 4.8% in CPU imbalance and 2.3% ± 2.4% in peak CPU. The hot-node ratio has a larger mean reduction, 13.8%, together with high seedlevel dispersion (25.4% standard deviation), and is treated as secondary evidence. Queue delay is nearly neutral in this comparison (−0.6% ± 1.8%). Across the matched workload–seed pairs, the mean shift is +78.8 ms in per-request decision time and −3.0 percentage points in CPU imbalance. Paired tests show reductions of 2.995 percentage points in CPU imbalance (95% CI [−4.310, −1.749], Wilcoxon p = 0.0010) and 2.193 percentage points in peak CPU (95% CI [−3.452, −0.887], p = 0.0146). Per-request decision time increases by 78.772 ms (95% CI [71.847, 85.128], p < 0.001). The queue-delay difference is not significant (0.125 ms, 95% CI [−0.073, 0.305], p = 0.2036). RQ-SAFE thus incurs higher control-plane per-request decision time to reach a less concentrated CPU operating point while preserving a comparable service outcome. This overhead should be interpreted as orchestration time rather than data-plane packet latency; the supplementary decomposition below shows that it is dominated by checked placement-and-validation search. Profile-stress and queue-estimation-error results are reported in the appendix because they characterize deployment tuning rather than the central cross-method result. D. Research Question 3: Request–Queue Coupling Fig. 5 directly isolates the two factors underlying the jointscheduling claim. This experiment is a mechanism isolation
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
(a) Variant gains vs. Neither (↑ better) +0.45 ±0.93
+1.21 ±1.17
-0.15 ±2.66
+0.58 ±6.13
-652.65 ±47.96
Queue only
+0.77 ±5.49
+5.61 ±0.84
+2.55 ±1.25
+12.09 ±3.43
-4.05 ±2.12
+3.94 ±14.10
Coupled
+4.53 ±5.07
+5.51 ±0.80
+3.91 ±0.97
QoS (pp)
Queue (ms)
E2E (ms)
-612.90 ±47.04
CPU Peak Run time imb. (pp) CPU (pp) (ms)
(b) Order × queue interaction (↑ synergy) +4.69 ±3.12
-0.82 ±1.26
-0.27 ±0.98
+2.46 ±1.24
+1.92 ±4.08
+15.90 ±34.84
W2
+7.29 ±3.61
+0.03 ±1.29
+1.09 ±3.48
+2.40 ±1.09
-5.60 ±6.30
+50.27 ±12.97
W3
+0.95 ±4.36
-0.87 ±0.48
+0.07 ±0.94
-3.63 ±8.57
-0.28 ±4.79
+12.30 ±46.03
W4
+2.38 ±1.65
-0.55 ±1.09
-0.24 ±0.81
+0.11 ±2.48
-0.56 ±5.17
+64.77 ±117.24
Overall
+3.83 ±3.79
-0.55 ±0.99
+0.16 ±1.73
+0.34 ±4.65
-1.13 ±5.25
+35.81 ±60.66
QoS (pp)
Queue (ms)
E2E (ms)
CPU Peak Run time imb. (pp) CPU (pp) (ms)
TABLE V W ORKLOAD -L EVEL O RDER –Q UEUE I NTERACTION QoS (pp) W1 Concurrent-balanced +4.69 W2 Balanced-mixed +7.29 W3 Queue-focused +0.95 W4 Safety-mixed +2.38 Overall +3.83
−1
1
W1
Variant Requests Previewed Better alt. Applied Order only 804 804 221 (27.5%) 221 (27.5%) Coupled 804 804 336 (41.8%) 336 (41.8%) Order-enabled total 1608 1608 557 (34.6%) 557 (34.6%)
Workload
0
Within-metric normalized gain
-4.60 ±3.28
0
Within-metric normalized gain
-0.07 ±3.09
+12.27 ±2.65
TABLE IV L OCAL -O RDER ACTION C OVERAGE AND A DOPTION
1
Order only
9
−1
Fig. 5. Direct 2 × 2 factorial evaluation of request-side order flexibility and queue-aware decision making. (a) Gains of Order only, Queue only, and Coupled relative to Neither; signs are converted so that positive is preferable for every metric. (b) Order–queue interaction Im = sm (C − O − Q + N ), where sm = 1 for higher is better metrics and sm = −1 otherwise. Entries show mean±standard deviation. W1–W4 each contain three matched seeds; Overall contains all 12 workload–seed groups. Colors are normalized within each metric, while annotations retain raw percentage-point or millisecond values.
test rather than an external baseline ranking. The four matched variants are Neither, Order only, Queue only, and Coupled, giving 48 completed runs over four workload families and three seeds. Table IV summarizes the request-level coverage of the local-order mechanism in the factorial suite; adoption is measured only for order-enabled variants. In the table, Previewed counts requests for which the default order and a legal alternative were both evaluated, Better alt. counts cases where the non-default order produced a better provisional outcome, and Applied counts cases where that alternative became the selected order. In the order-enabled conditions, all 1608 eligible requests entered the serial placement preview, and 557 selected and applied the better legal alternative. The coupled variant applies local rewrites more often than the order-only variant, showing that queue/resource state changes how request-side freedom is used. Relative to Neither, Coupled improves the QoS-compliant service ratio by 4.53 ± 5.07 percentage points. It also reduces queue delay by 5.51 ms, end-to-end delay by 3.91 ms, and CPU imbalance by 12.27 percentage points. These gains are accompanied by a 4.60-percentage-point increase in peak CPU
Queue CPU imb. (ms) (pp) −0.82 +2.46 +0.03 +2.40 −0.87 −3.63 −0.55 +0.11 −0.55 +0.34
and about 612.90 ms of additional per-request decision time. The coupled condition serves more requests within QoS and spreads the admitted work more evenly; the larger served load can raise the absolute peak, while the extra previews add computation. For metric m, the signed interaction is Im = sm (Cm − Om − Qm + Nm ),
(19)
where N , O, Q, and C denote the four variants and sm makes positive values preferable. The interaction term measures the extra gain that appears when the two factors are enabled together, beyond the sum of their separate effects. The overall QoS interaction is 3.83 ± 3.79 percentage points, with a 95% bootstrap confidence interval of [1.77, 5.89] and a paired sign-flip p-value of 0.0059. Table V shows that the QoS interaction is positive in all four workload families. The W1– W4 labels follow the workload definitions in the setup, and each workload contains three matched seeds. Values are signed gains; for delay and CPU imbalance, positive values mean reductions. The additional QoS gain appears when legal order flexibility and current queue state are active together. The factorial design maps directly to the model. Order only activates Aord and the action-level preview while masking i queue information from the decision. Queue only activates the queue terms and queue-aware decision path while retaining the base order. Coupled closes both the action-level loop in Eq. (12) and the stage-level loop in Eq. (10). The positive QoS interaction is therefore evidence for the joint mechanism rather than a generic benefit from adding two independent modules. The direct delay and CPU-imbalance reductions arise mainly from the queue-aware main effect; their interaction intervals include zero. The evidence is consequently metricspecific: order–queue coupling contributes the clearest nonadditive gain to QoS-compliant service outcome, while queue awareness supplies most of the immediate delay and balancing benefit. Additional module-removal and request-trace results are reported in the appendix. E. Supplementary Order-Budget and Runtime Checks We add two lightweight checks to clarify the operating range of the mechanism. First, we vary the retained orderaction budget Kπ . In the action-rich suite, each eligible request exposes the default order plus one retained non-default local rewrite. Thus Kπ = 1 keeps only the default order, whereas
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
(a) Pareto trade-off: cost vs. resource balance
(b) Candidate-width pressure and stability
Normalized index
K=3--10 zoom 50
K=1 search-limited48
5 6 4 10 3
46
8
50
0.8 0.6 0.4 0.2
K=20 wide
44 350
400
0.0
450
48
1
3
PPO / QoS
46
300
4
5
6
8
10 20
(c) Intervention intensity and QoS risk QoS fail PPO applied
40
44
Over-wide Variation
Pareto front Top-K K=5 ref.
350
Delta guard
1.0
30
0.5
20
0.0
Delta guard
CPU imbalance (pp)
Width-deviation Search-limited
1.0
54
52
10
−0.5
10
−1.0 400
Decision time (ms)
450
500
0
1
3
4
5
6
Top-K
8
10 20
Fig. 6. Top-K candidate-width sensitivity. Panel (a) shows the per-request decision-time and CPU-imbalance tradeoff; panel (b) summarizes candidate-width pressure and stability; panel (c) reports intervention intensity and QoS-risk traces.
Kπ ≥ 2 saturates the retained order-action set. Moving from Kπ = 1 to Kπ = 2 enables placement-aware preview for 804 eligible coupled-variant requests and leads to 336 selected non-default local orders. Larger budgets (Kπ = 3, 5) leave the service and action-adoption outcomes unchanged in this suite. This result shows order-action budget saturation for the evaluated action-rich workload. Second, we decompose the measured per-request decision time using the recorded timing fields. The dominant component is placement-and-validation search, which accounts for 256.01 ms on average, or 67.84% of the mean decision time. Semantic order abstraction and access-control screening are small in comparison, at 0.07 ms and 1.22 ms, respectively. The higher decision time observed in the cross-method comparison is therefore mainly the cost of checked candidate construction and validation, not of extracting the bounded local-order action set. Full tables are reported in the appendix. Fig. 6 reports the retained candidate-width sensitivity. A moderate retained width provides enough search coverage for stable candidate selection, while a wider list increases controlplane computation. This supports the default top-K setting used in the main experiments. Fig. 7 tests the effect of bounded queue-estimation error. Under-estimating queueing delay can reduce actual QoS compliance, while adding a validation margin recovers QoS at the cost of a more conservative success rate. This result clarifies the runtime boundary of the queue-aware validation used by RQ-SAFE.
F. Interpreting the Joint Scheduling Mechanism The model joins the request and resource sides in a stronger sense than placing two objective terms in one weighted sum. The request-side action changes the order in which predecessor context, paths, service instances, and remaining QoS slack are exposed. The resource-side state then determines the provisional plan generated under that action. A different action can therefore change both the candidate set in Eq. (5) and the value of a candidate in Eqs. (6)–(7). Conversely, every tentative resource choice updates the partial plan and changes the information used for the next request stage. The action and placement variables are connected through state transitions, not only through a final scalar score. This distinction explains why the action-level and stagelevel loops are both needed. The action-level loop prevents a semantically legal rewrite from being selected only because it looks attractive in the request graph. It must first produce a feasible and competitive provisional placement under the current service pools and queues. The stage-level loop prevents the retained action from becoming a fixed template once detailed placement begins. CPU pressure, waiting time, path context, reuse opportunities, and future scarcity are updated after each tentative assignment. Thus, request-side freedom determines what resource alternatives become reachable, while resource-side feedback determines how that freedom is used. The profile weights in Eq. (9) change the operating point without changing this coupling structure. A conservative profile can place more emphasis on completion slack, critical
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
Actual QoS Δ vs exact (pp)
12 10 8
Margin ε=5
6 4 2
(b) Integrated effect matrix
(a) Robustness--conservativeness map Over ε=5 Under no margin Under +margin Over estimate
↑ QoS better
Exact
0 → higher success
−2 left = more conservative −40 −20
Success Δ vs exact (pp)
0
11
Under no margin
Q -0.6 S +9.0 q -4.8
Q -1.6 S +11.7 q -13.2
Q -1.6 S +11.7 q -17.8
Under +margin
Q +0.0 S +0.0 q +0.0
Q +0.0 S +0.0 q +1.2
Q +8.5 S -16.0 q +7.9
Over estimate
Q +5.1 S -10.2 q +4.8
Q +11.7 S -36.5 q +14.4
Q +11.7 S -56.0 q +24.0
1
3
5
Under ε=5
εq (ms); Q↑ better, S↑ better, q>0 conservative
Fig. 7. Queue-estimation-error robustness. Panel (a) maps QoS recovery against success-rate cost relative to exact queue estimation; panel (b) integrates QoS change, success change, and validation-queue shift for ϵq = 1, 3, 5 ms.
(a) Traceable mechanism evidence
Final validation
100.0 /100 req
PPO re-rank
29.59 /100 req
PPO QoS guard
221.9 /100 req
Access-risk trace intensity
3278 trace intensity Access-risk and DAG/order values are trace-intensity signals.
DAG/order trace intensity −1 10
15006 trace intensity
10
0
10
1
10
2
Evidence intensity, log scale
10
3
10
4
(b) Request-level QoS-resource decision map 100 n=268; QoS-boundary=79; CPU-pressure=12; QoS-fail=26 PPO applied=79; guard=597
90 80
Peak CPU (%)
stages, and tail exposure. A throughput-oriented profile can tolerate more projected pressure when reusable service capacity is available. Learning-assisted re-ranking operates one level lower: it adjusts the order of close retained candidates after the explicit score has exposed the relevant tradeoff. It refines instance ordering while the semantic action set, provisional placement, and recursive state update remain explicit. The model can therefore support multiobjective adjustment while preserving a readable path from the incoming request to the final resource outcome. This interpretation also guides the experiments. Crossmethod comparisons evaluate the service and resource operating point of the full process. The factorial design tests whether order flexibility becomes more valuable when queue information is active. Request-level traces then show which action, candidate order, and fallback path produced each observed outcome. Together, these views test the same mechanism at system, factor, and decision levels.
70 60 50 40
G. Traceability of the Coupled Decision Path Panel (a) reports evidence coverage rather than a ranking of mechanism frequency. The request-normalized group shows that the final result path is recorded for every request and that accepted learned re-ranking appears at 29.59 events per 100 requests. QoS-guard events are more frequent because one request can generate several candidate-level checks. The accessrisk and DAG/order entries belong to a second group: they count intermediate trace records produced while constructing actions and partial plans. Their larger values therefore indicate finer logging granularity rather than more requests or greater algorithmic importance. Panel (b) locates 268 final request outcomes in the QoS– resource operating space, including 79 requests near the QoS boundary, 12 under high CPU pressure, and 26 QoS failures. For a circled request, the record links the selected local action, its placement preview, the deterministic and learned candidate
30 40 All requests QoS boundary
60
80
QoS budget use (%) CPU pressure QoS fail
100
120
PPO applied QoS guard trace
Fig. 8. Traceability of the recorded decision path. (a) Two evidence groups are displayed on a logarithmic axis. Final validation, learned re-ranking, and QoS-guard events are request-normalized rates per 100 requests; access-risk and DAG/order entries are raw trace-record intensities and are not magnitudecomparable with those rates. (b) Request-level QoS-budget use and peak CPU. Circled points contain an accepted learned re-ranking record; the circle indicates mechanism involvement rather than a causal performance gain.
orders, fallback events, and the final outcome. A circle indicates that learning participated in the recorded candidate path. The paired comparisons and factorial experiment provide the performance evidence; Fig. 8 establishes that the intermediate decision path remains observable. A decoded request trace is reported in the appendix. In that
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
record, a legal local rewrite is exposed, evaluated through a queue-aware provisional placement, used to condition candidate scoring, and accepted only after the queue-aware end-toend budget is checked. The main role of Fig. 8 is therefore to show that this audit path exists for real requests, while the performance conclusions come from the matched comparisons above. VI. C ONCLUSION AND F UTURE W ORK This paper studied online orchestration for partially ordered edge SFC-DAGs. RQ-SAFE turns semantic partial-order freedom into bounded local actions, evaluates each action through placement-aware preview, and continues detailed placement under the retained order. The resulting two-level loop connects request-side completion and QoS requirements with queues, paths, service pools, projected CPU pressure, and future candidate availability. The experiments show that this joint-scheduling design maintains a service-performance level comparable to graphaware baselines and moves deployments toward lower CPU concentration with higher control-plane decision time. The direct factorial experiment identifies a positive order–queue interaction in QoS-compliant service outcome, showing that queue state changes how legal order freedom is used. Supplementary checks show that the retained order-action set saturates once the available non-default local rewrite is exposed in the action-rich suite, and that the measured decision cost is dominated by checked placement-and-validation search. Learning-assisted re-ranking remains a bounded candidate refinement, while request actions, partial plans, fallbacks, and outcomes remain traceable. Future work will extend queue estimation with production telemetry, calibrate marginal reuse cost, and evaluate larger physical and containerized testbeds. Migration, autoscaling, and lifecycle-aware activation can be placed around the same bounded action, recursive placement, and trace interfaces. R EFERENCES [1] D. Kreutz, F. M. V. Ramos, P. E. Verı́ssimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-defined networking: A comprehensive survey,” Proc. IEEE, vol. 103, no. 1, pp. 14–76, Jan. 2015. [2] Network Functions Virtualisation (NFV); Architectural Framework, document ETSI GS NFV 002, ETSI NFV ISG, Sophia Antipolis, France, Dec. 2014. [3] J. Halpern and C. Pignataro, “Service function chaining (SFC) architecture,” IETF RFC 7665, Oct. 2015. [4] R. Mijumbi, J. Serrat, J. L. Gorricho, N. Bouten, F. De Turck, and R. Boutaba, “Network function virtualization: State-of-the-art and research challenges,” IEEE Commun. Surveys Tuts., vol. 18, no. 1, pp. 236–262, First Quarter 2016. [5] D. Bhamare, R. Jain, M. Samaka, and A. Erbad, “A survey on service function chaining,” J. Netw. Comput. Appl., vol. 75, pp. 138–155, Nov. 2016. [6] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE Internet Things J., vol. 3, no. 5, pp. 637–646, Oct. 2016. [7] T. Taleb, K. Samdanis, B. Mada, H. Flinck, S. Dutta, and D. Sabella, “On multi-access edge computing: A survey of the emerging 5G network edge cloud architecture and orchestration,” IEEE Commun. Surveys Tuts., vol. 19, no. 3, pp. 1657–1681, Third Quarter 2017. [8] G. Premsankar, M. Di Francesco, and T. Taleb, “Edge computing for the Internet of Things: A case study,” IEEE Internet Things J., vol. 5, no. 2, pp. 1275–1284, Apr. 2018.
12
[9] J. Chen, J. Chen, and K. Guo, “Queue-aware service orchestration and adaptive parallel traffic scheduling optimization in SDNFV-enabled cloud computing,” IEEE Trans. Cloud Comput., vol. 11, no. 4, pp. 3525– 3540, Oct.–Dec. 2023. [10] K. Mehmood, K. Kralevska, and D. Palma, “Intent-driven autonomous network and service management in future cellular networks: A structured literature review,” Computer Networks, vol. 220, Art. no. 109477, Jan. 2023, doi: 10.1016/j.comnet.2022.109477. [11] K. Mehmood, K. Kralevska, and D. Palma, “Knowledge graph embedding in intent-based networking,” in Proc. IEEE Conf. Netw. Softwarization (NetSoft), 2024, pp. 13–18. [12] T. He, A. N. Toosi, N. Akbari, M. T. Islam, and M. A. Cheema, “An intent-based framework for vehicular edge computing,” in Proc. IEEE Int. Conf. Pervasive Comput. Commun. (PerCom), Atlanta, GA, USA, 2023, pp. 121–130, doi: 10.1109/PERCOM56429.2023.10099081. [13] S. Mehraghdam, M. Keller, and H. Karl, “Specifying and placing chains of virtual network functions,” in Proc. IEEE 3rd Int. Conf. Cloud Netw. (CloudNet), Luxembourg, 2014, pp. 7–13. [14] Y. Xie, L. Huang, Y. Kong, S. Wang, S. Xu, X. Wang, and J. Ren, “Virtualized network function forwarding graph placing in SDN and NFV-enabled IoT networks: A graph neural network assisted deep reinforcement learning method,” IEEE Trans. Netw. Service Manag., vol. 19, no. 1, pp. 524–537, Mar. 2022. [15] J. G. Herrera and J. F. Botero, “Resource allocation in NFV: A comprehensive survey,” IEEE Trans. Netw. Service Manag., vol. 13, no. 3, pp. 518–532, Sep. 2016. [16] M. F. Bari, S. R. Chowdhury, R. Ahmed, R. Boutaba, and O. C. M. B. Duarte, “Orchestrating virtualized network functions,” IEEE Trans. Netw. Service Manag., vol. 13, no. 4, pp. 725–739, Dec. 2016. [17] D. T. Nguyen, C. Pham, K. K. Nguyen, and M. Cheriet, “Placement and chaining for runtime IoT service deployment in edge-cloud,” IEEE Trans. Netw. Service Manag., vol. 17, no. 1, pp. 459–472, Mar. 2020. [18] P. Jin, X. Fei, Q. Zhang, F. Liu, and B. Li, “Latency-aware VNF chain deployment with efficient resource reuse at network edge,” in Proc. IEEE INFOCOM, Toronto, ON, Canada, 2020, pp. 267–276. [19] Y. Wang, C. K. Huang, S. H. Shen, and G. M. Chiu, “Adaptive placement and routing for service function chains with service deadlines,” IEEE Trans. Netw. Service Manag., vol. 18, no. 3, pp. 3021–3036, Sep. 2021. [20] L. Wang, M. Dolati, and M. Ghaderi, “CHANGE: Delay-aware service function chain orchestration at the edge,” in Proc. IEEE Int. Conf. Fog Edge Comput. (ICFEC), 2021, pp. 19–28. [21] P. T. A. Quang, Y. Hadjadj-Aoul, and A. Outtagarts, “A deep reinforcement learning approach for VNF forwarding graph embedding,” IEEE Trans. Netw. Service Manag., vol. 16, no. 4, pp. 1318–1331, Dec. 2019. [22] O. Houidi, O. Soualah, W. Louati, and D. Zeghlache, “Dynamic VNF forwarding graph extension algorithms,” IEEE Trans. Netw. Service Manag., vol. 17, no. 3, pp. 1389–1402, Sep. 2020. [23] J. Cai, Z. Huang, L. Liao, J. Luo, and W. X. Liu, “APPM: Adaptive parallel processing mechanism for service function chains,” IEEE Trans. Netw. Service Manag., vol. 18, no. 2, pp. 1540–1555, Jun. 2021. [24] C. Zhang, T. Sato, and E. Oki, “Service deployment for parallelized function chains considering traffic-dependent delay,” IEEE Trans. Netw. Service Manag., vol. 21, no. 2, pp. 2266–2286, Apr. 2024, doi: 10.1109/TNSM.2023.3340704. [25] D. Zhang, L. Wang, and A. Rezaeipanah, “Toward deploying parallelized service function chains under dynamic resource request in multi-access edge computing,” IEEE Trans. Netw. Service Manag., vol. 22, no. 2, pp. 1899–1910, Apr. 2025. [26] C. Zhang, T. Sato, and E. Oki, “Robust deployment model for parallelized service function chains against uncertain traffic arrival rates,” IEEE Trans. Netw. Service Manag., vol. 22, no. 2, pp. 2156–2180, Apr. 2025. [27] Y. Zhang, R. Wang, J. Hao, Q. Wu, Y. Teng, P. Wang, and D. Niyato, “Service function chain deployment with VNF-dependent software migration in multi-domain networks,” IEEE Trans. Mobile Comput., vol. 24, no. 5, pp. 3685–3702, May 2025. [28] Y. Huang, T. Yao, Z. Lin, X. Shang, Y. Yuan, L. Cui, and Y. Yang, “Efficient service function chain placement over heterogeneous devices in deviceless edge computing environments,” IEEE Trans. Comput., vol. 74, no. 1, pp. 222–236, Jan. 2025. [29] D. Zheng and X. Cao, “Provably efficient service function chain embedding and protection in edge networks,” IEEE/ACM Trans. Netw., vol. 33, no. 1, pp. 178–193, Feb. 2025. [30] C. Zhou, B. Zhao, F. Tang, B. Han, and B. Wang, “Dynamic multiobjective service function chain placement based on deep reinforcement learning,” IEEE Trans. Netw. Service Manag., vol. 22, no. 1, pp. 15–29, Feb. 2025.
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. XX, NO. X, MONTH 2026
[31] F. Giarrè and H. Karl, “RIPPLE: Lifecycle-aware embedding of service function chains in multi-access edge computing,” arXiv preprint arXiv:2602.03662, Feb. 2026. [32] J. Pei, P. Hong, K. Xue, and D. Li, “Resource aware routing for service function chains in SDN and NFV-enabled network,” IEEE Trans. Services Comput., vol. 14, no. 4, pp. 985–997, Jul.–Aug. 2021. [33] J. Zu, G. Hu, D. Peng, S. Xie, and W. Gao, “Fair scheduling and rate control for service function chain in NFV enabled data center,” IEEE Trans. Netw. Service Manag., vol. 18, no. 3, pp. 2975–2986, Sep. 2021. [34] S. Yang, F. Li, Z. Zhou, X. Chen, Y. Wang, and X. Fu, “Online control of service function chainings across geo-distributed datacenters,” IEEE Trans. Mobile Comput., vol. 22, no. 6, pp. 3558–3571, Jun. 2023. [35] B. Li, F. Hou, G. Yang, H. Zhao, and S. Chen, “Data analysis-oriented stochastic scheduling for cost efficient resource allocation in NFV based MEC network,” IEEE Trans. Veh. Technol., vol. 72, no. 5, pp. 6695– 6708, May 2023. [36] R. He, B. Ren, J. Xie, D. Guo, and L. Zhao, “Efficient online scheduling of service function chains across multiple geo-distributed regions,” IEEE Trans. Netw. Service Manag., vol. 21, no. 3, pp. 3440–3453, Jun. 2024, doi: 10.1109/TNSM.2024.3383213. [37] Y. Xiao, Q. Zhang, F. Liu, J. Wang, M. Zhao, Z. Zhang, and J. Zhang, “NFVdeep: Adaptive online service function chain deployment with deep reinforcement learning,” in Proc. IEEE/ACM Int. Symp. Quality Service (IWQoS), Phoenix, AZ, USA, 2019, Art. no. 21. [38] R. Solozabal, J. Ceberio, A. Sanchoyerto, L. Zabala, B. Blanco, and F. Liberal, “Virtual network function placement optimization with deep reinforcement learning,” IEEE J. Sel. Areas Commun., vol. 38, no. 2, pp. 292–303, Feb. 2020. [39] X. Fu, F. R. Yu, J. Wang, Q. Qi, and J. Liao, “Dynamic service function chain embedding for NFV-enabled IoT: A deep reinforcement learning approach,” IEEE Trans. Wireless Commun., vol. 19, no. 1, pp. 507–519, Jan. 2020. [40] J. Chen, J. Chen, and H. Zhang, “DRL-QOR: Deep reinforcement learning-based QoS/QoE-aware adaptive online orchestration in NFVenabled networks,” IEEE Trans. Netw. Service Manag., vol. 18, no. 2, pp. 1758–1774, Jun. 2021. [41] S. Schneider, R. Khalili, A. Manzoor, H. Qarawlus, R. Schellenberg, H. Karl, and A. Hecker, “Self-learning multiobjective service coordination using deep reinforcement learning,” IEEE Trans. Netw. Service Manag., vol. 18, no. 3, pp. 3829–3842, Sep. 2021. [42] Y. Bi et al., “Multi-objective deep reinforcement learning assisted service function chains placement,” IEEE Trans. Netw. Service Manag., vol. 18, no. 4, pp. 4134–4150, Dec. 2021. [43] S. Dräxler, H. Karl, and Z. Á. Mann, “JASPER: Joint optimization of scaling, placement, and routing of virtual network services,” IEEE Trans. Netw. Service Manag., vol. 15, no. 3, pp. 946–960, Sep. 2018. [44] S. Woo, J. Sherry, S. Han, S. Moon, S. Ratnasamy, and S. Shenker, “Elastic scaling of stateful network functions,” in Proc. USENIX NSDI, Renton, WA, USA, 2018, pp. 299–312. [45] T. Subramanya and R. Riggio, “Centralized and federated learning for predictive VNF autoscaling in multi-domain 5G networks and beyond,” IEEE Trans. Netw. Service Manag., vol. 18, no. 1, pp. 63–78, Mar. 2021. [46] Z. Luo and C. Wu, “An online algorithm for VNF service chain scaling in datacenters,” IEEE/ACM Trans. Netw., vol. 28, no. 3, pp. 1061–1073, Jun. 2020. [47] M. Dolati, S. H. Rastegar, A. Khonsari, and M. Ghaderi, “Layer-aware containerized service orchestration in edge networks,” IEEE Trans. Netw. Service Manag., vol. 20, no. 2, pp. 1830–1846, Jun. 2023. [48] L. Wang, W. Mao, J. Zhao, and Y. Xu, “DDQP: A double deep Qlearning approach to online fault-tolerant SFC placement,” IEEE Trans. Netw. Service Manag., vol. 18, no. 1, pp. 118–132, Mar. 2021. [49] Y. Qin, D. Guo, L. Luo, J. Zhang, and M. Xu, “Service function chain migration with the long-term budget in dynamic networks,” Comput. Netw., vol. 224, Art. no. 109563, 2023. [50] R. A. Addad, D. L. C. Dutra, T. Taleb, and H. Flinck, “AI-based networkaware service function chain migration in 5G and beyond networks,” IEEE Trans. Netw. Service Manag., vol. 19, no. 1, pp. 472–484, Mar. 2022. [51] Y. Liu, Y. Lu, X. Li, W. Qiao, Z. Li, and D. Zhao, “SFC embedding meets machine learning: Deep reinforcement learning approaches,” IEEE Commun. Lett., vol. 25, no. 6, pp. 1926–1930, Jun. 2021. [52] J. Chen, X. Cheng, J. Chen, and H. Zhang, “A lightweight SFC embedding framework in SDN/NFV-enabled wireless network based on reinforcement learning,” IEEE Syst. J., vol. 16, no. 3, pp. 3817–3828, Sep. 2022. [53] A. H. Ebrahimi, A. Ebrahimi, M. G. Arani, and H. Saboohi, “Cold start latency mitigation mechanisms in serverless computing: Taxonomy,
13
review, and future directions,” J. Syst. Archit., vol. 151, Art. no. 103115, Jun. 2024. [54] M. Femminella and G. Reali, “Application of proximal policy optimization for resource orchestration in serverless edge computing,” Computers, vol. 13, no. 9, Art. no. 224, Sep. 2024.
1
A PPENDIX A C OMMITMENT C HECKS AND Q UEUE -AWARE Q O S A NALYSIS This appendix states the commitment properties used by the main text and the exact runtime boundary supported by the released implementation. Candidate construction operates on request-local resource and queue state. A retained instance can be selected only when its service is available and its projected CPU increment fits the request-local CPU ledger. After a complete plan is formed, queue-aware end-to-end delay is recomputed. In the serial replay used for evaluation, global CPU and queue state advance only after a successful request result. Link reachability and latency enter candidate/path construction; the reported commitment boundary covers requestlocal CPU feasibility, path reachability/latency construction, and queue-aware QoS validation rather than a separate universal residual-bandwidth or queue-capacity guarantee. A. CPU Feasibility Under Atomic Commitment Proposition A.1. CPU feasibility under atomic commitment. Assume that resource updates are performed serially or through atomic commitment. If a request is committed by the validation layer, then the committed CPU usage of every physical node remains within its CPU capacity. Proof sketch. For each VNF-to-instance mapping (v, s) in a candidate deployment plan, let n(s) denote the physical node that hosts instance s. During validation, the orchestrator encpu (t). A candidate maintains a temporary resource ledger U can be selected only if cpu cpu e cpu (t) + ∆rv,s U ≤ Cn(s) − ξpcpu , n(s) cpu is the effective CPU increment caused by aswhere ∆rv,s signing VNF v to instance s, and ξpcpu ≥ 0 is the profiledependent safety margin. Candidates outside this bound are skipped. When no feasible candidate exists for any VNF, the request is rejected and the physical resource ledger remains unchanged. Hence every committed mapping satisfies cpu cpu e cpu (t) + ∆rv,s U ≤ Cn(s) . n(s) Under serial or atomic commitment, atomicity prevents intermediate conflicting updates from invalidating the checked condition. The committed CPU usage of each node therefore remains within its capacity. B. Queue-Aware QoS Compliance Under Exact Queue Estimation Proposition A.2. Queue-aware QoS compliance under exact queue estimation. If the queueing delay used in validation is exact, then any request committed by the validation layer satisfies its end-to-end delay budget. Proof sketch. For request ri , the validation layer recomputes the queue-aware end-to-end delay of the CPU-feasible plan: b e2e = De2e (P safe , S(t)). D i i i The final commitment condition is b ie2e ≤ Dimax . D b e2e equals the If the queueing-delay estimates are exact, then D i actual queue-aware end-to-end delay after deployment. Every committed request therefore satisfies the delay budget Dimax .
C. Robust QoS Estimation Error
Compliance
Under
Bounded
Queue-
Proposition A.3. Robust QoS compliance with queuemargin validation. Suppose that the queueing-delay estimation error of each selected VNF instance is bounded by b queue ≤ ϵq , ∀v ∈ Vi . Dqueue − D i,v
i,v
If the validation layer commits a request only when b e2e + |Vi |ϵq ≤ Dmax , D i i then the actual end-to-end delay of the committed request also satisfies the QoS budget. Proof sketch. For any source-to-sink path in the SFC-DAG, the total queueing-delay estimation error is upper-bounded by the number of VNFs on the path multiplied by ϵq . Since any path contains at most |Vi | VNFs, the queue-aware end-to-end delay satisfies b ie2e + |Vi |ϵq . Die2e ≤ D If the validation layer reserves the margin |Vi |ϵq , then b ie2e + |Vi |ϵq ≤ Dimax . Die2e ≤ D Thus the deployed request remains QoS-compliant under bounded queue-estimation error. A PPENDIX B S EMANTIC L OCAL -O RDER ACTIONS AND P LACEMENT-AWARE P REVIEW The request-side mechanism exposes only local rewrites that are supported by both declared VNF semantics and a conservative structural rule. It exposes a compact action set instead of enumerating all topological orders. Let Ci denote the admitted local pairs. The action set is Aord = {a0i } ∪ {aswap i i,u,v : (u, v) ∈ Ci }. The implementation uses two rule families. For a linear request, an eligible pair must be internal and adjacent in the base orchestration order. For a branch or general DAG, an eligible pair must be a directed serial pair on one branch. Its local predecessor and successor context must be unique, and merge and tail nodes are excluded. Independent siblings may be recorded as structural information, but they are not turned into semantic swap actions. Unknown type pairs default to non-commutable. For a branch-local serial segment p → u → v → s, a valid action rewrites only that segment as p → v → u → s. All other edges remain unchanged. The rewrite is admitted only when the configured type-pair rule and the local structural guard both pass. The rule families used by the released implementation are summarized in Table A.I. Each action is evaluated by the deterministic placementaware preview used in the online request path. The preview invokes the current queue/resource-sensitive candidate process and records whether a provisional plan can be formed, together with processing/activation delay, queue pressure, network delay, adjusted end-to-end delay, and QoS slack. The original order is retained unless a legal rewrite produces a preferable provisional outcome. Request-side order selection is therefore explicit and deterministic. The learned module acts later, only on retained instance candidates.
2
TABLE A.I I MPLEMENTED LOCAL - ORDER RULE FAMILIES . T YPE NAMES FOLLOW THE BENCHMARK SERVICE TAXONOMY. Rule family
Structural condition
Enabled type pairs
Conservative exclusions
Linear local rewrite
Internal adjacent pair in the base order; surrounding predecessor/successor context remains fixed Directed pair on one branch with unique local predecessor and successor context
cache–forward, cache–aggregate, aggregate– forward detect–cache, detect–compress, cache– compress
Source/sink endpoints, undeclared pairs, and state/side-effect conflicts Merge or tail nodes, independent siblings, ambiguous branch context, and undeclared pairs
Branch-local serial rewrite
A PPENDIX C Q UEUE E STIMATION E RROR A NALYSIS The main paper uses a lightweight queueing-delay estimator based on the observable queue length and service rate of each VNF instance: cs (t) = Qs (t) . W µs This estimator is suitable for online orchestration because it uses runtime information that can be collected from the service pool. It can still deviate from the actual waiting time when service times are heterogeneous, requests arrive in bursts, background tasks are present, or instance-level concurrency changes quickly. For VNF v assigned to instance s, we write the queueingdelay error as queue b queue + ei,v , Di,v =D i,v where ei,v is the estimation error. A conservative boundederror assumption is |ei,v | ≤ ϵq . Under this assumption, the total error of a chain-like request is at most |Vi |ϵq . For a general SFC-DAG, the end-to-end delay is determined by the maximum source-to-sink completion time. The bound can therefore be tightened by using the maximum path length: b ie2e + Lmax Die2e ≤ D ϵq , i max where Li is the maximum number of VNFs on any sourceto-sink path of Gi . Since Lmax ≤ |Vi |, the bound in Proposii tion A.3 is conservative. In practice, ϵq can be estimated from validation traces or set as a profile-dependent margin. Conservative profiles may use a larger queue margin, while throughput-oriented profiles may use a smaller margin. This gives a direct tradeoff between QoS robustness and access-control aggressiveness. A PPENDIX D B OUNDED D ECISION P ROPERTIES OF L EARNING -A SSISTED T OP -K R E -R ANKING The main text treats this component as learning-assisted re-ranking. The released online path loads a frozen ranking artifact and applies it to a retained instance-candidate list. The paper’s learning claim is scoped to this runtime role and to the retained-candidate neighborhood used by online orchestration. A. Bounded Online Decision Space and Inputs For VNF v of request ri , the learning module can select only an index in the retained list: K K ALR |Ti,v | ≤ K. i,v = {1, 2, . . . , |Ti,v |},
The action space therefore grows with the configured retained width, not with the total number of nodes or VNF instances. Online inputs contain only pre-commit information: request and DAG summaries, the current partial plan, queue/resource state, deterministic candidate scores, and candidate-level path, reuse, tail, and scarcity features. Realized post-deployment outcomes are not online inference features. B. Runtime Boundary and Fallback The learning component neither creates candidates nor selects request-side order actions. It returns a revised ordering K of Ti,v . If the suggestion is unavailable or rejected by the runtime control, the deterministic order is retained. Candidate feasibility, request-local CPU accounting, complete-plan latency computation, and the successful state-update path are shared with the rule-only mode. Proposition C.1. Learned re-ranking preserves the enabled success checks. If global state is updated only after a complete request-local plan passes service availability, CPU-capacity, and queue-aware QoS checks, then changing the order of canK didates inside Ti,v preserves the same state-update boundary. Proof sketch. The learned output is an ordering of an already retained set. Each candidate is processed by the same requestlocal construction path. A candidate that lacks service availability or available CPU capacity is skipped. After a complete plan is formed, queue-aware end-to-end delay is recomputed. If the plan fails, the next retained candidate/order can be tried or the request is rejected. Global state is advanced only for a successful result. Re-ranking therefore changes search order but not the enabled success conditions. C. Scope of the Learning Claim The results above establish the online boundary needed by this paper: learning can only reorder an already retained candidate set, and every resulting order enters the same request-local CPU, completion, fallback, and state-update path. The learning claim is limited to bounded retained-candidate re-ranking; global optimality, monotonic policy improvement, and calibrated approximation ratios are outside this runtime role. Candidate-width quality and overhead are evaluated directly by the sensitivity experiment and the complexity analysis. A PPENDIX E C OMPUTATIONAL C OMPLEXITY This appendix states the online complexity with the candidate-order and fallback loops made explicit. Let |Vi | and |Ei | be the numbers of VNFs and virtual dependency edges in
3
request ri . Let |N | and |L| be the numbers of physical nodes and links. Let M denote the average number of type-matched candidate instances per VNF before top-K truncation. Let Kπ be the maximum number of retained candidate execution orders, K be the local top-K candidate width per VNF, and B ≤ K be the maximum number of candidate retries per VNF and per retained order during validation. The top-K list in this paper is a local per-VNF candidate list, so the online path builds retained local lists rather than enumerating all complete plans in K |Vi | . A. Access Control and Order Abstraction The access-control layer computes queue, resource, latency, and structural risk scores. If candidate availability is checked over an average of M instances per VNF, the cost is O(|Vi |M ). The SFC-DAG/order abstraction layer extracts commutable segments, branch/merge labels, critical paths, and tail-sensitive VNFs. Let Ci be the number of candidate local-order actions before pruning. The implementation retains at most Kπ orders, so the abstraction and pruning cost can be written as O(|Vi | + |Ei | + Ci log Kπ ), or simply O(|Vi | + |Ei | + Ci ) when Kπ is treated as a small deployment constant. B. Candidate Generation Under Retained Orders For each retained order, the placement layer filters and scores candidate instances for every VNF. Filtering and scoring over the type-matched pool costs O(|Vi |M ), and retaining a local top-K list by heap or partial sorting costs O(|Vi |M log K). Across all retained orders, this part contributes O(Kπ |Vi |M log K) . This expression is the cost of building local candidate lists. It is not a full-plan enumeration cost. C. Path Search, Re-Ranking, and Validation Fallback Let Psp = O(|L| + |N | log |N |) be the cost of one configured shortest-path search over the current link-state snapshot. For a fixed retained order, path construction over the virtual edges costs O(|Ei |Psp ). During candidate construction or commitment, a candidate may fail a service-availability, CPU-capacity, configured-path, or QoS check. The validator may then try the next retained candidate. With at most B retries per VNF and per retained order, the fallback validation cost is bounded by O(B|Vi | + B|Ei |Psp ) , where the first term covers candidate and ledger checks and the second term covers the worst case in which retries trigger additional path searches. The learned module reorders only the retained local lists, so with fixed neural hidden size its cost is O(Kπ |Vi |K).
Combining retained orders, local candidate construction, reranking, fallback validation, and path search gives the perrequest upper bound O(Kπ [|Vi |M log K + |Vi |K + B|Vi | + B|Ei |Psp ]) , plus the access-control and structural-abstraction cost above. When Kπ , K, and B are bounded deployment parameters, the dominant terms are candidate filtering/scoring and, when enabled, path search. Increasing the retained order count, local candidate width, or retry budget improves search coverage but directly increases per-request decision time; this is the tradeoff characterized by the retained-candidate-width sensitivity and topology-scale experiments. A PPENDIX F E XPERIMENTAL S ETTINGS AND RUNTIME PARAMETERS This appendix summarizes the settings used in the reported experiments. The evaluation uses mixed edge SFCDAG benchmark snapshots rather than one fixed toy topology. All methods within the same comparison use the same topology snapshot, workload trace, seed, service-pool state, and request count. Exact YAML paths, generated configuration files, request-payload fingerprints, runtime-trace fingerprints, model aliases, and run modes are stored in the corresponding figure archives. The current experiments use CPU as the binding node resource in request-local feasibility checks. Memory is retained as an extensible resource dimension. Link state and latency are used during configured path construction; the reported runtime uses link reachability and latency during configured path construction rather than a separate universal residual-bandwidth hard guarantee. Peak node CPU denotes the maximum CPU utilization among physical edge nodes after a deployment attempt. The hot-node ratio is the fraction of nodes whose CPU utilization exceeds the hotspot threshold. The CPU-imbalance metric is the peak-to-minimum CPU spread over physical nodes. Shadow evaluation logs a learned suggestion in shadow mode, where the logged suggestion is not applied to the request path. For the multi-seed edge-deployment comparison in Fig. 4, the workloads are public-mixed SFC-DAG request sets on the SNDlib Germany50 topology. The four workload families are Concurrent-balanced, Balanced-mixed, Queue-focused, and Safety-mixed. Each family is evaluated with matched seeds 831, 832, and 833 for both RQ-SAFE and GNN-DAG. The generated archive verifies that the request payload, runtime trace, and metric fingerprints differ across seeds. Main-text Fig. 5 uses a direct 2 × 2 order-flexibility-by-queue-awareness factorial suite with the same four workload families, three matched seeds, and four variants (Neither, Order only, Queue only, and Coupled), giving 48 completed runs and 12 complete matched groups. Fig. 6 uses the request-level traceability and mechanism-evidence suite. The exact request counts are figure-specific and are recorded in the released archives. A PPENDIX G I MPLEMENTATION S COPE C LARIFICATIONS This section clarifies several implementation-sensitive components that are abstracted in the main text. The purpose is
4
TABLE A.II R EPORTED S IMULATION S ETTINGS Parameter Benchmark source Physical topology Node CPU capacity Memory capacity VNF types Warm VNF instances VNF CPU demand VNF processing delay Cold-start delay Link state and delay Traffic demand model QoS delay budgets Request families Fig. 4 workload families Fig. 4 seeds Seed verification Requests per workload seed Traffic profiles SFC structures Instance concurrency Queue estimator
Value Mixed edge SFC-DAG benchmark snapshots. Fig. 4 uses public-mixed SFC-DAG workloads on the SNDlib Germany50 topology. Main-text Fig. 5 uses matched order–queue factorial workloads, and Fig. 6 uses traceability snapshots recorded in the figure archives. Snapshot-specific directed edge topology; all methods in the same comparison use the same topology and link-state snapshot. Snapshot-specific normalized CPU capacity; CPU is the binding node resource in request-local success checks. Retained as an extensible resource dimension; reported hard node-feasibility checks use CPU. Configured service types include filtering, detection, encryption/decryption, caching, compression, forwarding, monitoring, policy checking, aggregation, re-ranking, and sanitization functions. Initialized from each benchmark service-pool snapshot; cold-start candidates are considered only when resources allow activation. Normalized per-type or per-instance demand from the selected benchmark configuration. Per-type processing delay from the selected benchmark configuration. Configuration-specific activation delay for cold candidates. Heterogeneous link-state and link-delay fields are read from the selected topology snapshot. Path reachability and latency enter candidate construction; link reachability and latency are used without a separate universal residual-bandwidth hard guarantee. Edge-specific traffic variables ℓi,u,v and bi,u,v are supported; request-level defaults are used when branch-specific traffic is unavailable. Explicit QoS budgets are stored with each workload snapshot and are reused by all compared methods under the same workload seed. Latency-sensitive, security-sensitive, long-chain, parallel, branch/merge, commutable-order, and tail-latency-sensitive services. Concurrent-balanced, Balanced-mixed, Queue-focused, and Safety-mixed public-mixed SFC-DAG workloads. Matched seeds 831, 832, and 833 for each workload family and for both RQ-SAFE and GNN-DAG. The Fig. 4 archive records generated configuration fingerprints, request-payload fingerprints, runtime-trace fingerprints, and metric fingerprints; all differ across the matched seeds. Figure-specific. Each paired comparison keeps the same request count for all compared methods under the same workload seed; exact counts are stored in the corresponding archive. Public-mixed explicit-QoS profiles, including concurrent-balanced, balanced-mixed, queue-focused, and safety-mixed variants; figure-specific variants are stored in the released archives. Linear chains and SFC-DAGs with branches, merges, commutable segments, and dependency-preserving local order choices. Configuration-specific; heavier or stateful VNF types use smaller concurrency limits than lightweight service types unless the snapshot specifies otherwise. cs (t) = Qs (t)/µs , computed from observable queue length and service state. Main matched Instance waiting proxy W experiments use ϵq = 0 to isolate scheduler effects; Appendix H-B injects bounded nonzero errors and evaluates marginprotected validation.
TABLE A.III O RCHESTRATION AND E VALUATION PARAMETERS Parameter Access states Supported deployment profiles Reported profile Trial access Top-K candidate size Candidate-order action set Candidate scoring terms Resource feasibility Path construction Queue treatment Queue-estimation margin Learning-module online role Successful state update Fig. 4 metrics Fig. 5 metrics Fig. 6 metrics
Value accept, trial, reject conservative, balanced, throughput The matched benchmark runs use the throughput profile unless otherwise stated. Borderline requests enter the same order/placement path with profile-specific screening or margins. Runtime default K = 3 unless explicitly overridden. Appendix sensitivity and selected control runs set K = 5 where noted. Base order plus conservative linear-adjacent or directed branch-local serial rewrites; compact local-order action set with no sibling serialization. Projected CPU pressure, queue waiting, path latency, service-pool reuse, critical/tail exposure, branch concentration, and future candidate scarcity. cpu Request-local CPU ledger with effective increments ∆rv,s ; global resource state advances only after a successful request result. Link-reachability and latency-aware path construction over the current snapshot. A separate universal residual-bandwidth hard guarantee is not part of the reported claim. Queue state enters order preview, instance ranking, and queue-aware end-to-end delay. No separate queue-capacity hard constraint is claimed. 0 ms in the main matched runs. Appendix C and the main-text queue-error robustness figure evaluate nonzero bounded-error margins. Reorder retained top-K instance candidates only; request-side order selection remains driven by deterministic placementaware preview. Service availability, request-local available CPU capacity, and queue-aware QoS are checked in the reported path; failed requests leave the shared runtime state unchanged. Per-request decision time, CPU imbalance, peak CPU, hot-node ratio, and queue delay. Variant gains relative to Neither and signed order–queue interaction for QoS ratio, queue delay, end-to-end delay, CPU imbalance, peak CPU, and runtime. Mechanism trace intensity and request-level QoS–resource outcomes, including learned re-ranking, QoS guards, QoSboundary requests, CPU-pressure requests, and QoS failures.
5
TABLE A.IV L EARNING -A SSISTED R E -R ANKING RUNTIME C ONFIGURATION Parameter Online role Runtime artifact
Value Revise the checking order inside a retained instance-candidate list; it refines candidate checking order before validation. Frozen V5 ranking artifact loaded through the structure-aware ranking path in the reported runs. The main claim is limited to its online candidate-ordering role. K Masked categorical index over Ti,v ; K is configuration-specific and the runtime default is 3. Request class, QoS context, DAG size and branch/merge summaries, critical/tail labels, and current placement stage. Deterministic score components, queue and resource state, path cost, remaining-capacity signal, reuse signal, tail risk, and future scarcity. Candidate index/order inside the retained list. Legal local-order actions and placement-aware action preview are generated and selected outside the learned candidate path. When an accepted learned order is unavailable, the deterministic candidate order is used. The selected candidate continues through the common request-local CPU and queue-aware completion path; global state advances only after success. Candidate list, deterministic order, learned suggestion, accepted change, guard/fallback events, and final request outcome. Rule-only, shadow, learning-assisted re-ranking, and module-removal controls that preserve the deterministic score and common result path.
Action space Request/DAG inputs Candidate inputs Output Request-side boundary Fallback State-update boundary Trace fields Evaluation modes
TABLE A.V BASELINE FAIRNESS AND REPRODUCTION SCOPE . A LL METHODS ARE EVALUATED INSIDE THE SAME SIMULATOR WITH MATCHED TOPOLOGY SNAPSHOTS , WORKLOAD TRACES , SERVICE - POOL STATES , REQUEST COUNTS , AND SEEDS FOR EACH PAIRED COMPARISON . Method
Input features
Greedy-CPU
VNF type, node CPU state, feasible Accepts SFC-DAG Queue and warm/cold sta- Same shared Self-reproduced heuristic; instance pool, and path feasibility. requests through the tus are visible to the com- success/evaluation path no training. Uses the same same request parser; uses mon validator; the greedy after candidate selection; workload seeds as other the default legal order and score itself prioritizes re- the reported hard request- methods. no learned order action. maining CPU. local checks are available CPU capacity and queueaware QoS. Processing delay, link delay, path Accepts SFC-DAG Queue is checked by the Same shared Self-reproduced latencycost, candidate feasibility, and QoS requests with the default common validator; the success/evaluation path oriented baseline based on budget. legal order; no local order- main score is latency and request traces. delay-aware VNF placement action search. and path oriented. Warm principles; no training. candidates are available in the common service pool. Normalized resource, queue, la- Handles SFC-DAG Uses the same observable Proposed actions are Self-reproduced DDQN-style tency, QoS, and candidate-state sum- requests after the same queue/resource state in its evaluated through the same baseline; trained on the trainmaries available before commit- parser and default order state vector; warm reuse request-result accounting ing split only, with held-out ment. abstraction; uses its is available through the and queue-aware QoS test workloads and archived own DDQN-style action shared candidate pool. metrics. random seeds. interface rather than the RQ-SAFE local orderaction set. Service-graph structure, Supports SFC-DAG graph Uses the same runtime Uses the same request- Self-reproduced graph-aware candidate/node features, resource scoring; it uses graph- state features where appli- result accounting and SFC-DAG baseline with state, path features, and queue- based scoring while RQ- cable; warm/cold instance exported CPU/queue/QoS archived model settings, related runtime features supplied by SAFE supplies semantic availability is from the metrics after graph-based training split, and evaluation the same environment. local-order swap actions common service pool. scoring. seeds. through its request abstraction. Request, SFC-DAG summaries, Supports SFC-DAG order Queue state and warm Same shared result Frozen offline-trained rankqueue/resource state, top-K abstraction and bounded le- reuse are explicit scoring path; learning can only ing artifact; the online role candidates, path cost, warm reuse, gal local-order actions. and re-ranking features. reorder retained instance and trace fields are summatail risk, and future scarcity features. candidates before the rized in Table A.IV. request-local completion checks.
Latency-Aware
DRL-DDQN
GNN-DAG
RQ-SAFE
SFC-DAG and order han- Queue / reuse use dling
to state how these quantities enter candidate scoring, requestlocal completion checks, and the successful state-update path. A. Queue Estimator Scope and Margin Selection The FCFS proxy cs (t) = Qs (t)/µs W is a lightweight online queue-pressure estimator based on queue length and effective service rate. It keeps access control and validation inexpensive while exposing instance-level congestion to the scheduler. Its error can increase when service times are heterogeneous, arrivals are bursty, background tasks
Validator and fairness con- Training trol scope
or
reproduction
share the instance, the service rate changes because of colocation, or the runtime scheduler is not FCFS. The theoretical and experimental robustness analysis therefore treats queue delay as a bounded-error estimate and calibrates margins from validation residuals. A practical deployment can choose the margin from recent validation residuals. Let obs cs,j es,j = Ws,j −W be the residual between observed waiting time and the online estimate for recent completed requests on instance s. A profilespecific margin may be set as ϵq (p) = Quantileρp (|es,j |) ,
6
where ρp is larger for conservative profiles and smaller for throughput-oriented profiles. The main reported runs set ϵq = 0 to keep the scheduler comparison matched, while Appendix the main-text queue-error robustness figure injects 1, 3, 5 ms errors to show how nonzero margins trade accesscontrol aggressiveness for QoS protection.
TABLE A.VI ACCESS - CONTROL SCORE WEIGHTS USED BY THE REPORTED IMPLEMENTATION . Profile Light-load / conservative Default / balanced Heavy-load / throughput-stress
wslack wqueue wres wlen 0.50 0.45 0.40
0.90 1.00 1.20
7.0 8.0 9.5
0.7 0.8 1.0
B. Effective Resource Increment
E. Learning-Assisted Runtime Boundary
r The effective resource increment ∆rv,s is the amount added to the temporary validation ledger if VNF v is assigned to instance s. For CPU in the reported experiments, the raw demand rvcpu is read from the benchmark VNF configuration. For a cold activation, the effective increment is the raw activation demand. For a warm or reusable instance, the increment is the additional task pressure on the already active instance, represented as a conservative reuse-adjusted demand,
The learned component receives candidate-level pre-commit features and returns a revised order inside the retained list. Reward definitions, optimizer choices, and training schedules are not part of the online orchestration model claimed by the paper. The released evaluation uses a frozen artifact. Candidate feasibility and request-result accounting remain in the common runtime path described in Appendix D.
cpu ∆rv,s = ϕv,s (t)rvcpu ,
0 < ϕv,s (t) ≤ 1,
with implementation floors to avoid treating reuse as free. cpu is not produced by the learned candidate ranker; it Thus, ∆rv,s is a validation-side accounting quantity derived from the VNF demand, warm-instance status, reusable-instance evidence, and deployment profile. If production telemetry is available, ϕv,s (t) can be calibrated from measured per-instance marginal CPU usage; in the submitted experiments it is determined by the benchmark configuration and conservative reuse rules. C. Implemented Semantic Compatibility and Structural Guards The released implementation uses explicit allow lists together with structural guards. The linear rule applies only to selected internal adjacent pairs. The DAG rule applies only to selected directed serial pairs on one branch with unique local predecessor/successor context. Merge and tail nodes are excluded. Independent siblings are not semantic swap actions. Table A.I records the actual rule families used by the main model. A candidate rewrite is rejected when its pair is undeclared, its local context is ambiguous, or the pair crosses a protected merge/tail boundary. These conditions are deliberately sufficient rather than necessary. New service taxonomies require an explicit metadata/rule update before additional rewrites are enabled. D. Access-Control and Trial-Gate Parameters The risk-aware access-control rule uses a profile-dependent linear score. In the implementation, the equivalent form is Si = wslack slacki − wqueue riskqi − wres costri − wlen |Vi |. The reported implementation uses the access-control weights in Table A.VI. They were selected on validation workloads and then kept fixed for the reported test runs. The hard accept/reject thresholds are profile- and QoS-class-specific guards that act before final validation; borderline requests can still enter trial placement, but final commitment is controlled by the enabled deterministic checks, including the temporary CPU ledger and queue-aware QoS validation.
F. Path Backtracking and Termination Path repair/backtracking is bounded by the retained local candidate list and by the retained local order-action set. The implementation searches retained alternatives rather than all complete infrastructure mappings. If the current candidate fails a service-availability, CPU-capacity, configured-path, or QoS check, the validator tries the next retained candidate for the affected stage and may trigger a new configured path search. Let Kπ be the retained order count and let B ≤ K be the maximum number of candidate retries per VNF and per order. The corresponding upper bound is given in Appendix E. Appendix the main-text top-K sensitivity figure and Table A.XV report the observed per-request decision-time tradeoff. A PPENDIX H A DDITIONAL S ENSITIVITY AND ROBUSTNESS E VIDENCE This section provides supplementary evidence on retainedcandidate sensitivity, retained order-action budget, queueestimation error, runtime controls, decision-time decomposition, and profile stress. The top-K sensitivity and queue-error robustness figures are placed in the main text, while the tables below give detailed numerical settings and controls. A. Top-K Candidate-Width Sensitivity The top-K sensitivity figure in the main text evaluates the retained candidate width K. The result supports using a moderate candidate width rather than an overly narrow searchlimited list or an over-wide list with extra online cost. B. Queue-Estimation-Error Robustness The queue-estimation-error robustness figure in the main text reports the queue-estimation-error robustness study. All values are relative to the exact queue-estimate baseline. Underestimating the queue without a margin can reduce actual QoS compliance, whereas adding the validation margin |Vi |ϵq moves the decision into a more conservative region and recovers QoS at the cost of lower acceptance/success. This supports the bounded-error argument in Appendix A: queue margins protect QoS by trading off conservativeness.
7
TABLE A.VII I MPLEMENTATION - SENSITIVE COMPONENT BOUNDARIES . Component
Reported interpretation
Queue estimate
Lightweight instance waiting estimate used in preview, can- Calibrate a nonzero margin when pro- Proposition A.3 and the main-text didate ranking, and queue-aware delay. duction residuals are material. queue-error robustness figure. Request-local ledger increment that distinguishes cold acti- Recalibrate marginal CPU when teleme- Proposition A.1 and runtime convation from conservative warm reuse. try differs from benchmark profiles. trol table. Explicit linear-adjacent and branch-local serial rule families; New VNF types require declared se- Table A.I. unknown pairs are disabled. mantic and structural rules. Reachability and link latency participate in candidate/path Add residual-bandwidth reservation if Tables A.II and A.III. construction. the deployment requires a bandwidth guarantee. Frozen artifact revises only the retained candidate order. Artifact and gate can be recalibrated Table A.IV and Proposition C.1. without changing the semantic action or completion path. Finite retry over retained instance candidates and retained Wider retained sets increase decision Complexity analysis, the main-text legal actions. time. top-K sensitivity figure, and Table A.XII.
Effective CPU increment Local-order semantics Path handling
Learning-assisted re-ranking
Fallback
Deployment consideration
Supporting evidence
TABLE A.VIII RUNTIME CONTROL BOUNDARY OF RQ-SAFE.
Component Service and CPU availability Queue-inclusive QoS State update Path handling
Implemented path Candidate construction uses available service instances and request-local projected CPU increments. Complete-plan latency is recomputed with instance waiting estimates and the request budget. Batch replay updates shared CPU and queue state only after a successful request result. Current path reachability/link latency enter candidate construction.
Learning action
The learned output is an order/index inside a retained candidate list.
Queue-error margin
Nonzero error and margin fields are exercised by the robustness experiment.
TABLE A.IX P ROFILE - STRESS REPLAY WITH LEARNING - ASSISTED / RULE - ONLY CONTROLS UNDER 15% QUEUE UNDER - ESTIMATION . Mode Profile Val. QoS (%) Rec. QoS (%) Rec. budget (%) Decision (ms) Learned Cons. 74.46 74.46 78.03 611.58 Learned Bal. 80.43 72.84 78.21 616.17 Learned Thr. 82.13 72.84 78.21 618.11 Rule-only Cons. 74.17 74.17 77.94 505.02 Rule-only Bal. 80.89 73.34 78.11 509.40 Rule-only Thr. 82.34 72.68 78.28 512.02
C. Runtime Control Boundary Table A.VIII summarizes the implemented boundary used by the main-text claims. D. Profile Stress Under Queue Under-Estimation Table A.IX reports the compact profile-control experiment moved from the main text. The table separates validationside decisions under a 15% underestimated queue contribution from recovered QoS under the injected true contribution. Conservative profiles preserve a smaller accepted set; balanced and throughput profiles admit more requests but lose recovered QoS. The learning-assisted and rule-only rows show that the profile trend is not created solely by candidate re-ranking.
Claim used in the paper A candidate without service availability or available CPU capacity is skipped. Successful results satisfy the configured queueaware QoS test. Failed requests do not advance the shared runtime state. The paper claims path-aware candidate construction, not a universal residual-bandwidth guarantee. Learning refines candidate order within the retained list; semantic order actions are selected by the explicit request-side mechanism. Bounded queue error can be traded against access-control aggressiveness through a validation margin.
E. Runtime Traceability as Secondary Evidence The runtime traceability figure in the main text summarizes this evidence. Final validation is recorded for every request in the reported set. Accepted learning-assisted re-ranking appears at 29.59 events per 100 requests, while guard records are more frequent because a single request can produce several candidate-level checks. Access-risk and DAG/order values count intermediate trace records and therefore use a different denominator and interpretation. The request map contains 268 outcomes, including 79 near the QoS boundary, 12 in the CPU-pressure region, and 26 QoS failures. Circled points identify requests for which an accepted candidate re-ranking is present in the recorded path. The figure establishes observability of actions, candidates, guards, fallback, and outcomes. Performance conclusions continue to rely on the matched comparisons and factorial experiment rather than on trace counts. Table A.X gives one decoded request path from the recorded log. It illustrates how local-order exposure, queue-aware preview, candidate construction, and final queue-aware validation are connected in a single inspectable record.
8
TABLE A.X D ECODED REQUEST- LEVEL TRACE USED AS AN EXAMPLE OF THE RECORDED DECISION PATH . Trace step Input Access control Order preview
Candidate scoring
Validation and result
Recorded values req_045; six VNFs; general-DAG low-latency request; legal serial pair (v2 , v3 ); QoS budget 52.75 ms. Estimated queue latency 15.83 ms; QoS slack 36.92 ms; queue-risk score 3.456; access decision accept. Base order filter–detect–compress–cache–aggregate–encrypt has adjusted preview latency 41.30 ms. The rewritten order filter–compress–detect– cache–aggregate–encrypt has adjusted preview latency 36.30 ms. Queue preview changes from 16.59 to 16.06 ms. 56 candidates are scored and 16 are filtered as unsupported or unavailable. The selected placement is node-a, node-c, node-b, node-d, node-b, node-c for the six VNFs. Final queue-aware adjusted delay is 40.77 ms, below the 52.75 ms budget; queue delay is 16.06 ms; QoS passes; recorded decision time is 986.83 ms.
Interpretation The request has bounded local-order freedom and an explicit end-to-end budget. Queue state is visible before placement, but commitment is not made at access control. The legal rewrite is selected because the provisional placement improves adjusted latency by 4.995 ms.
Candidate construction is conditioned on the retained order and service-pool state. The request becomes a committed success only after completeplan validation.
TABLE A.XI W ORKLOAD - LEVEL ORDER – QUEUE INTERACTION . VALUES ARE SIGNED GAINS ; POSITIVE IS PREFERABLE FOR EACH METRIC . Workload
QoS (pp) W1 Concurrent-balanced +4.69 W2 Balanced-mixed +7.29 W3 Queue-focused +0.95 W4 Safety-mixed +2.38 Overall +3.83
Queue (ms) −0.82 +0.03 −0.87 −0.55 −0.55
E2E CPU imb. Peak CPU Decision (ms) (pp) (pp) (ms) −0.27 +2.46 +1.92 +15.90 +1.09 +2.40 −5.60 +50.27 +0.07 −3.63 −0.28 +12.30 −0.24 +0.11 −0.56 +64.77 +0.16 +0.34 −1.13 +35.81
TABLE A.XII R ETAINED ORDER - ACTION BUDGET CHECK IN THE ACTION - RICH SUITE . A DOPTION IS COMPUTED OVER RETAINED ELIGIBLE REQUESTS . Q O S IS THE Q O S- COMPLIANT SERVICE RATIO , AND TIME IS MEAN PER - REQUEST DECISION TIME . Kπ 1 1 2 2 3 3 5 5
Variant Requests Retained eligible Applied non-default Adoption (%) Order only 804 0 0 – Coupled 804 0 0 – Order only 804 804 221 27.49 Coupled 804 804 336 41.79 Order only 804 804 221 27.49 Coupled 804 804 336 41.79 Order only 804 804 221 27.49 Coupled 804 804 336 41.79
F. Additional Factorial Details Table A.XI decomposes the order–queue interaction by workload and includes the metrics omitted from the main-text summary. The QoS interaction remains positive in all four workload families. The queue-delay, end-to-end-delay, CPU, and peak-CPU interactions are mixed, which is why the main text interprets non-additive coupling most strongly for QoScompliant service outcome. G. Stage-3 Checks: Retained Order-Action Budget and Decision Time Table A.XII reports the retained order-action budget check. The action-rich suite contains 4 workload families, 3 seeds, and 4 variants for each budget value, giving 192 raw run rows. Each order-enabled variant contains 804 requests across the matched workload–seed groups. In this suite, every eligible request exposes the default order and one non-default local rewrite. Hence Kπ = 1 disables the non-default rewrite under the same order-enabled code path, and Kπ ≥ 2 saturates the retained order-action set. The table should therefore be read as a saturation check for the retained action set, not as a claim that larger order budgets are always redundant in workloads with multiple legal local rewrites.
QoS (%) 53.76 54.53 53.69 58.29 53.69 58.29 53.69 58.29
Time (ms) 380.56 368.36 957.01 928.16 953.19 943.12 968.50 931.26
The results show two effects. First, exposing the first nondefault local rewrite activates the order-side mechanism: the coupled variant selects a non-default local order for 336 of 804 requests, compared with 221 of 804 in the order-only variant. Second, the Kπ = 2, 3, 5 rows are identical in service and action outcomes because the suite exposes only one nondefault local action per eligible request. The coupled QoS ratio increases from 54.53% at Kπ = 1 to 58.29% once the retained rewrite is available, while the order-only QoS ratio is almost unchanged. This supports the interpretation that order freedom becomes useful when it is evaluated through current queue/resource state. Table A.XIII decomposes the recorded decision time. The labels below use the paper-level terminology. The implementation timing field named access control corresponds to accesscontrol screening in the paper. The decomposition separates request normalization, semantic order abstraction, access-control screening, placement-and-validation search, QoS evaluation, queue-state evaluation, and residual runtime/logging cost. The decomposition shows that the observed decision-time cost is dominated by placement-and-validation search. Semantic order abstraction and access-control screening together account for less than 0.4% of the mean decision time. This supports the main-text interpretation that the additional runtime
9
TABLE A.XIII P ER - REQUEST DECISION - TIME DECOMPOSITION FROM 804 REQUEST- LEVEL TIMING RECORDS . Paper-level stage Request translation/normalization Semantic order abstraction Access-control screening Placement-and-validation search QoS evaluation Queue-state evaluation Residual runtime/logging/serialization
Mean (ms) 47.47 0.07 1.22 256.01 27.29 0.07 45.24
Median (ms) 47.89 0.05 1.15 250.80 26.03 0.06 39.95
95th perc. (ms) 68.45 0.12 1.86 360.86 34.64 0.12 84.05
Share of mean total (%) 12.58 0.02 0.32 67.84 7.23 0.02 11.99
TABLE A.XIV M AIN - TEXT CLAIM TO APPENDIX - EVIDENCE MAP. Main-text claim
Evidence
Supported interpretation
Scope
Request-side freedom is a bounded opera- Appendix B, Table A.I, and Table A.XII. tional variable.
Only declared linear-adjacent or branch-local serial rewrites are exposed; siblings remain parallel, and the budget and factorial suites record how often the enabled rewrite is adopted.
Request and resource sides are coupled Placement-aware preview, recursive canthrough placement consequences. didate model, main-text Fig. 5, and Tables A.X and A.XI. Learning has bounded online influence. Appendix D, Table A.IV, and Proposition C.1. Queue-error margins trade aggressiveness Proposition A.3 and the main-text queuefor robustness. error robustness figure. Moderate retained width balances search the main-text top-K sensitivity figure, Taand overhead. ble A.XII, Table A.XIII, and complexity analysis. Cross-method results use matched workload Tables A.II, A.V, and A.XV. state.
Rule set is benchmarktaxonomy specific; the budget check saturates at one nondefault rewrite in the reported action-rich suite. The statistically clear nonadditive effect is concentrated in QoS outcome. No new training-algorithm claim is made. Guarantee follows the bounded-error assumption. Optimal K and Kπ are deployment specific.
A legal action changes provisional placement; queue/resource feedback changes whether that action is retained and how later VNFs are placed. The artifact only reorders retained instance candidates and shares the common request-result path. A bounded per-stage error can be absorbed by a pathlength/request-size margin. Increasing retained candidate/order coverage can increase online cost; the measured cost is dominated by placement-and-validation search. Paired methods share topology, requests, seed, Baseline implementations folservice-pool snapshot, and metric accounting. low the stated information boundaries. Strict replay covers three public topologies, four Evidence is simulation/replay workload groups, five methods, and matched seeds. based.
The pipeline remains competitive across Tables A.XV and A.XVI. topology scale.
cost mainly comes from checked candidate construction and validation over retained alternatives, rather than from merely extracting local-order actions. H. Claim-to-Evidence Map Table A.XIV links the main claims to the supporting appendix evidence.
10
TABLE A.XV S TRICT PAIRED TOPOLOGY- SCALE SUMMARY. Method RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU
Runs
Arrivals
Rows
Success (%)
QoS (%)
Queue (ms)
Budget (%)
Decision (ms)
36 36 36 36 36
2412 2412 2412 2412 2412
2412 2412 2412 2412 2412
74.6 74.9 64.1 56.6 51.4
74.6 74.9 64.1 56.6 51.4
22.0 21.8 38.5 23.1 31.9
77.8 77.3 93.7 97.5 101.9
654.6 616.0 154.3 293.4 149.8
Notes: Arrivals is the number of replayed input requests. Rows is the number of request-level result rows after strict completeness filtering. All methods are evaluated on the same 2,412 arrivals. Success and QoS use the same denominator in this topology-scale replay, so they are equal in this table.
A PPENDIX I S TRICT T OPOLOGY-S CALE PAIRED C OMPARISON AND R AW RUN -L EVEL R ESULTS Tables A.XV and A.XVI report the topology-scale replay used for the appendix comparison. The replay covers 3 topologies × 4 workload groups × 5 methods × 3 seeds, for a total of 180 runs. Each topology–workload–seed group uses the same request trace for all methods. The completeness runtime check passes for all runs: each method is evaluated on the same 2, 412 arrivals, and every arrival contributes exactly one result row. This strict accounting removes the request-count ambiguity in the earlier export. Under this strict replay, RQ-SAFE and GNN-DAG form the leading service-outcome group. Their success/QoS rates are close under strict accounting, while both methods clearly outperform Latency-Aware, DRL-DDQN, and Greedy-CPU. Therefore, this topology-scale replay supports paired-accounting robustness and competitiveness with the graph-aware baseline, together with distinct placement behavior for the two methods. A placement-signature runtime check also confirms that the two methods are not collapsed into the same decision path: final assigned-node signatures differ in 2164 of 2412 paired requests. TABLE A.XVI: Complete strict run-level results for the topology-scale paired comparison. Topology
Size
Workload
Seed
Method
Arr.
Rows
Success (%)
QoS (%)
Queue (ms)
Budget (%)
Decision (ms)
Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet
19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E
W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W4 W4 W4 W4 W4
831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831
RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70
62.5 62.5 53.1 32.8 51.6 62.5 62.5 53.1 32.8 51.6 62.5 62.5 53.1 32.8 51.6 65.6 65.6 57.8 40.6 50.0 65.6 65.6 57.8 40.6 50.0 65.6 65.6 57.8 40.6 50.0 71.4 77.1 64.3 45.7 60.0 70.0 75.7 64.3 45.7 61.4 70.0 75.7 64.3 44.3 60.0 75.7 74.3 64.3 38.6 58.6
62.5 62.5 53.1 32.8 51.6 62.5 62.5 53.1 32.8 51.6 62.5 62.5 53.1 32.8 51.6 65.6 65.6 57.8 40.6 50.0 65.6 65.6 57.8 40.6 50.0 65.6 65.6 57.8 40.6 50.0 71.4 77.1 64.3 45.7 60.0 70.0 75.7 64.3 45.7 61.4 70.0 75.7 64.3 44.3 60.0 75.7 74.3 64.3 38.6 58.6
23.6 23.5 37.8 24.0 31.8 23.7 23.6 37.8 24.0 31.8 23.7 23.6 37.8 24.0 31.8 22.9 22.9 37.9 23.6 32.4 22.9 23.0 37.9 23.6 32.4 22.9 22.9 37.9 23.6 32.4 20.4 20.5 37.3 21.1 34.1 20.3 20.5 37.2 21.2 34.2 20.3 20.5 37.3 21.1 34.2 21.1 20.9 36.8 21.3 32.8
87.9 88.5 104.3 115.5 101.0 89.4 88.6 104.3 115.5 101.0 89.4 88.4 104.2 115.5 101.0 87.7 84.6 103.3 111.3 100.6 87.9 86.1 103.2 111.2 100.6 87.9 84.4 103.3 111.1 100.6 82.0 80.1 94.9 103.1 98.4 82.3 79.4 94.8 103.1 98.6 81.9 80.4 94.9 103.1 98.6 81.6 80.6 96.6 105.8 98.9
615.1 488.7 132.6 233.4 137.4 596.0 507.2 139.3 266.0 145.1 586.9 517.2 136.1 243.6 127.6 588.8 514.5 161.4 271.4 142.4 599.4 557.6 141.6 259.9 134.6 601.9 541.0 133.1 252.3 140.9 586.8 542.7 149.5 275.1 152.3 601.7 527.7 177.9 271.1 153.3 575.5 504.4 146.6 258.3 137.0 529.2 485.5 136.8 261.1 155.9
Continued on next page
11
TABLE A.XVI: Complete strict run-level results for the topology-scale paired comparison (continued). Topology
Size
Workload
Seed
Method
Arr.
Rows
Success (%)
QoS (%)
Queue (ms)
Budget (%)
Decision (ms)
Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Aarnet Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Abvt Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet
19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 19N/48E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E
W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W1 W2 W2 W2 W2
832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831
RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN
70 70 70 70 70 70 70 70 70 70 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64
70 70 70 70 70 70 70 70 70 70 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64
75.7 74.3 64.3 40.0 57.1 74.3 77.1 64.3 41.4 58.6 70.3 68.8 59.4 56.2 48.4 70.3 70.3 59.4 56.2 48.4 70.3 68.8 59.4 56.2 48.4 71.9 71.9 65.6 57.8 46.9 71.9 73.4 67.2 57.8 46.9 71.9 73.4 65.6 59.4 46.9 80.0 75.7 71.4 64.3 54.3 78.6 75.7 71.4 65.7 55.7 75.7 74.3 70.0 65.7 54.3 87.1 84.3 68.6 67.1 48.6 87.1 81.4 68.6 65.7 48.6 87.1 82.9 68.6 65.7 47.1 71.9 71.9 59.4 64.1 48.4 71.9 70.3 59.4 64.1 48.4 71.9 71.9 59.4 64.1 48.4 71.9 71.9 65.6 65.6
75.7 74.3 64.3 40.0 57.1 74.3 77.1 64.3 41.4 58.6 70.3 68.8 59.4 56.2 48.4 70.3 70.3 59.4 56.2 48.4 70.3 68.8 59.4 56.2 48.4 71.9 71.9 65.6 57.8 46.9 71.9 73.4 67.2 57.8 46.9 71.9 73.4 65.6 59.4 46.9 80.0 75.7 71.4 64.3 54.3 78.6 75.7 71.4 65.7 55.7 75.7 74.3 70.0 65.7 54.3 87.1 84.3 68.6 67.1 48.6 87.1 81.4 68.6 65.7 48.6 87.1 82.9 68.6 65.7 47.1 71.9 71.9 59.4 64.1 48.4 71.9 70.3 59.4 64.1 48.4 71.9 71.9 59.4 64.1 48.4 71.9 71.9 65.6 65.6
21.1 20.9 36.8 21.4 32.7 21.1 20.9 36.8 21.4 32.7 23.6 23.3 39.9 24.5 31.3 23.6 23.3 39.9 24.5 31.3 23.4 23.3 39.9 24.5 31.3 22.9 22.8 39.8 24.0 31.3 22.9 22.9 40.4 24.0 31.3 22.9 22.9 39.8 24.1 31.3 20.6 20.3 38.7 21.9 32.8 20.6 20.3 38.7 21.9 33.0 20.5 20.3 38.6 21.8 32.9 21.1 20.9 37.7 22.5 30.6 21.0 20.9 37.7 22.4 30.6 21.0 20.9 37.7 22.2 30.4 23.4 23.4 39.9 24.9 31.3 23.4 23.3 39.9 24.9 31.3 23.4 23.4 39.9 24.9 31.3 22.7 22.6 39.8 24.3
81.4 81.3 96.7 106.0 98.8 81.6 80.3 96.6 106.0 98.9 78.4 79.1 95.9 99.6 103.9 79.1 79.0 95.9 99.6 103.9 80.0 79.1 95.9 99.6 103.9 77.6 77.3 94.7 97.7 102.2 77.6 75.9 96.0 97.6 102.3 75.7 75.9 94.7 97.7 102.3 71.3 71.6 85.5 89.2 101.9 71.5 71.7 85.5 89.1 102.1 72.6 73.2 85.4 89.0 101.9 72.6 72.5 86.2 92.7 100.8 72.5 72.8 86.3 92.5 100.8 72.6 73.3 86.3 92.1 100.4 77.3 75.9 95.9 94.1 106.0 77.5 78.0 95.9 94.1 106.0 77.2 76.6 95.9 94.1 106.0 75.4 75.3 94.7 91.4
635.7 497.6 143.1 275.3 140.6 588.1 517.4 130.9 252.4 130.8 632.9 580.6 182.9 351.6 165.7 791.0 600.6 148.7 299.3 143.7 719.3 589.6 170.8 326.7 167.2 691.9 590.9 179.6 338.5 181.6 728.6 590.9 147.5 288.8 145.2 658.7 601.1 170.5 327.4 177.0 670.7 626.8 151.0 284.7 159.7 656.3 613.2 148.1 273.4 142.3 669.4 691.0 144.4 317.7 160.3 621.9 686.7 166.7 345.0 142.6 807.0 746.8 193.4 360.5 178.7 737.2 728.6 159.4 301.3 162.1 653.1 688.1 153.1 291.4 149.4 662.4 705.1 146.9 338.5 136.8 713.7 715.8 151.3 327.6 141.2 629.4 682.4 156.0 281.4
Continued on next page
12
TABLE A.XVI: Complete strict run-level results for the topology-scale paired comparison (continued). Topology
Size
Workload
Seed
Method
Arr.
Rows
Success (%)
QoS (%)
Queue (ms)
Budget (%)
Decision (ms)
Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet Aconet
23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E 23N/62E
W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W2 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W3 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4 W4
831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833 831 831 831 831 831 832 832 832 832 832 833 833 833 833 833
Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU RQ-SAFE GNN-DAG Latency-Aware DRL-DDQN Greedy-CPU
64 64 64 64 64 64 64 64 64 64 64 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70
64 64 64 64 64 64 64 64 64 64 64 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70
46.9 71.9 71.9 67.2 65.6 46.9 71.9 71.9 65.6 65.6 46.9 84.3 87.1 71.4 74.3 54.3 84.3 87.1 71.4 75.7 55.7 84.3 87.1 70.0 72.9 54.3 85.7 88.6 68.6 70.0 48.6 85.7 90.0 68.6 70.0 48.6 85.7 87.1 68.6 70.0 47.1
46.9 71.9 71.9 67.2 65.6 46.9 71.9 71.9 65.6 65.6 46.9 84.3 87.1 71.4 74.3 54.3 84.3 87.1 71.4 75.7 55.7 84.3 87.1 70.0 72.9 54.3 85.7 88.6 68.6 70.0 48.6 85.7 90.0 68.6 70.0 48.6 85.7 87.1 68.6 70.0 47.1
31.3 22.7 22.6 40.4 24.3 31.3 22.7 22.6 39.8 24.3 31.3 20.4 20.1 38.7 22.3 32.8 20.4 20.1 38.7 22.3 33.0 20.4 20.1 38.6 22.1 32.9 21.0 20.7 37.7 22.5 30.6 21.0 20.7 37.7 22.5 30.6 21.0 20.7 37.7 22.3 30.4
104.2 75.4 75.8 96.0 91.4 104.3 75.4 75.4 94.7 91.3 104.3 69.5 68.8 85.5 83.8 102.8 69.4 68.9 85.5 83.8 103.1 69.2 69.0 85.4 83.5 102.9 71.0 71.5 86.2 86.4 102.0 71.0 71.3 86.3 86.4 102.0 71.2 71.7 86.3 86.0 101.6
140.8 732.7 712.3 157.4 307.7 147.9 726.8 700.7 143.2 282.8 145.2 627.1 742.2 157.9 313.5 141.1 685.8 765.7 172.9 309.7 173.1 667.4 661.4 157.9 282.3 145.3 624.2 651.3 149.0 300.3 144.9 692.2 653.6 151.1 296.0 149.4 659.3 649.3 165.0 296.2 154.2
Notes: Each row corresponds to one topology–workload–method–seed run. Arrivals and Rows verify one-to-one request accounting for the run. Success and QoS are percentages. Queue, budget, and decision time are run-level means over requests. Budget is the mean queue-aware delay-budget usage. The corresponding CSV files and completeness runtime check are archived with the experimental artifacts.
13
A PPENDIX J S COPE B OUNDARIES AND D EPLOYMENT E XTENSIONS This appendix section collects the main deployment-scope and implementation boundaries so that the main text can focus on the orchestration design and experimental findings. The reported experiments are designed to evaluate validation-controlled online SFC-DAG orchestration under matched topology, workload, seed, and service-pool states. The following points clarify how the framework can be extended in broader deployments. A. Queueing and Traffic Models cs (t) = Qs (t)/µs as a lightweight online estimator. The robustness The reported scheduler uses the observable FCFS proxy W analysis and Appendix the main-text queue-error robustness figure evaluate bounded queue-estimation error and validationside margins. A complete queueing-model comparison under non-FCFS scheduling, heavy-tailed service times, background interference, and adversarial burst patterns would require a separate runtime study. In deployment, the margin ϵq (p) can be calibrated from recent validation residuals, as described in Appendix G. B. Resource Reuse and Activation Calibration r The effective resource increment ∆rv,s is computed from benchmark VNF demand, cold/warm instance status, and conservative reuse rules. This makes the reported matched replay reproducible. In a production system, the reuse coefficient ϕv,s (t) should be calibrated from telemetry, for example by measuring marginal CPU usage after assigning additional tasks to warm instances. Such calibration changes the validation ledger, while preserving the separation between learned candidate ordering and final feasibility validation.
C. Commutable Semantics and New VNF Types The semantic compatibility matrix is intentionally conservative. New VNF types can be introduced by declaring their type, statefulness, side-effect class, and admissible commutable partners. Unknown pairs are kept in their original dependency order until this metadata is available. A future extension can combine rule-based safety with learned semantic compatibility, provided that dependency preservation and validation remain explicit. D. Baselines, Testbeds, and Larger Deployments The evaluation compares representative heuristic, latency-aware, DRL, and graph-aware baselines under matched traces. It is intended to position the proposed request–resource joint-scheduling pipeline rather than to cover every hybrid learning-andverification implementation. Future work will add real edge testbed measurements, container start-up effects, cloud-edge or multi-domain orchestration, and integrated migration, autoscaling, and failure recovery. These extensions affect deployment realism and long-horizon resource governance, while the current paper focuses on per-request online SFC-DAG orchestration with explicit request-local completion checks and traceable state updates.