DeepNC: A Fast GNN-based Pre-Verification Surrogate for TSN Configuration Jiayi Zhua † , Jing Lina † , Zelong Tiana , Feng Hea , Luxi Zhaoa*
arXiv:2607.24398v1 [cs.NI] 27 Jul 2026
a
School of Electronics and Information Engineering, Beihang University, China
Abstract—Time-Sensitive Networking (TSN) is critical to deterministic communication in safety-critical domains, with formal verification such as Network Calculus (NC) serving as the cornerstone for schedulability guarantees. However, during automated configuration-space exploration, repeated schedulability analysis consumes over 90% of the total configuration time, becoming the primary bottleneck for large-scale TSN configurations. To address this challenge, we propose DeepNC, a novel pre-verification surrogate module that pioneers the structural fusion of NC principles into a Graph Neural Network (GNN) for TSN configuration-space exploration. Rather than replacing formal verification, DeepNC acts as a high-speed pre-verification filter, reserving computationally expensive formal verification only for promising candidates. Extensive evaluations demonstrate that DeepNC significantly improves worst-case delay prediction accuracy over state-of-the-art learning-based methods, increasing the average R2 by 55.8% and reducing the average MAPE by 65.3%. More importantly, its high-fidelity regression substantially reduces the number of formal verification calls during configuration-space exploration by 93.25%, while accelerating NC-based verification by more than two orders of magnitude.
I. I NTRODUCTION Time-Sensitive Networking (TSN) [1] has become the communication backbone for safety-critical systems such as autonomous driving, industrial automation, and aerospace by enabling deterministic communication over Ethernet. However, such determinism is not an inherent property of the TSN standard. Instead, it relies on appropriately configuring diverse scheduling mechanisms (Time-Aware Shaper (TAS) [2], Credit-Based Shaper (CBS) [3], Cyclic Queuing and Forwarding (CQF) [4], and their hybrid combinations) and performing formal schedulability verification to ensure that the resulting configuration satisfies end-to-end timing requirements. Consequently, practical TSN design relies on an iterative workflow that tightly couples configuration optimization with formal schedulability verification. Within this iterative design workflow, formal schedulability verification [5]–[8] provides the rigorous performance guarantees required for each candidate configuration. Although a single Network Calculus (NC)-based verification typically completes within seconds [6], automated configuration synthesis often requires tens of thousands of repeated verification calls while exploring a large configuration space. Consequently, the computational bottleneck shifts from configuration † Co-first authors with equal contribution. ∗ Corresponding author. Emails: [email protected]; [email protected]; zelongtian@buaa .edu.cn; [email protected]; [email protected].
optimization itself to the repeated execution of formal verification. Existing studies report that schedulability verification can account for over 90% of the total configuration time in automated TSN design workflows [9]. To alleviate this computational bottleneck, recent studies [10]–[12] have explored learning-based surrogate models that approximate the results of formal verification. Rather than replacing formal methods, these surrogates serve as fast preverification modules that rapidly filter unpromising configurations, allowing rigorous analysis to focus only on a much smaller candidate subset. Such a workflow significantly accelerates configuration-space exploration while preserving the correctness guarantees of formal verification. Despite recent progress, existing learning-based pre-verification surrogates remain largely output-driven. They primarily approximate the input-output relationship between network configurations and verification results, without explicitly encoding the analytical reasoning process underlying formal performance analysis methods. Consequently, existing studies have primarily focused on binary schedulability classification [10]–[12], which is well suited for feasibility screening but provides limited quantitative timing information to guide fine-grained configuration optimization. To address these limitations, we propose DeepNC, a novel pre-verification surrogate module for TSN configuration-space exploration by structurally integrating NC principles into Graph Neural Networks (GNN) [13]. Unlike prior learningbased surrogates that treat formal analysis merely as a source of supervision, DeepNC embeds the reasoning process of the Total Flow Analysis (TFA)-based NC analysis for hybrid TSN/TAS+CBS architectures [6] into the graph message-passing mechanism of the neural architecture. As a result, DeepNC closely approximates worst-case delay bound (WCDs) computed by NC formal analysis, providing quantitative timing information for efficient configuration-space exploration and candidate pruning in large-scale TSN networks. Our main contributions are as follows: • First, we propose an NC-guided heterogeneous graph representation to encode the analytical semantics of NC. By deconstructing the network into distinct F LOW, Q UEUE, and L INK nodes, we explicitly map the defining parameters of arrival curves and service curves into graph features, enabling DeepNC to preserve the analytical structure of NC. • Second, we develop a message-passing mechanism in-
II. R ELATED W ORK The growing demand for large-scale and dynamic TSN has motivated research into rapid network configuration [14]. To address the bottleneck of formal verification in configurationspace exploration, existing approaches can be broadly classified into two categories: a priori awareness [15]–[19] and a posteriori verification [20]–[22]. The a priori awareness paradigm integrates formal verification analysis into the optimization process by deriving specialized analytical or semianalytical models for specific scheduling policies or optimization objectives [15]–[19]. While computationally efficient, these methods require problem-specific mathematical formulations and are therefore difficult to generalize. In contrast, the a posteriori verification paradigm [20]–[22] preserves the conventional optimization-verification workflow while accelerating verification itself through techniques such as incremental verification [23], though their effectiveness diminishes with an increasing number of concurrent changes. More recently, learning-base surrogate models have been introduced to accelerate formal verification [10]–[12]. Behera et al. [10] propose a method for performing binary schedulability classification for variable-length periodic task sets under multiple uniprocessor scheduling policies, serving as a prefilter before formal schedulability analysis. In the networking domain, the RouteNet family [24]–[26] and CEA-GNN [27] predict average network performance. In contrast, Mai et al. [11], [12] formulate Ethernet/TSN verification as binary schedulability classification. However, all these methods primarily learn an input-output mapping without explicitly modeling the underlying analytical reasoning process. As a result, they are less suitable for highfidelity WCDs prediction required for refined configuration
ES1
ES3 SW1
SW2
ES2
(a) illustration of TSN network topology
.. .
p OTT
p OTT
2
1
Transmission Selection
CBS CBS CBS
TAS Shaper GCL TT Class Q1 .. Gate . CBS Shaper ... ET Class M1 Qm Gate ET Class M 2 Qm 1 Gate ET Class M 3 Qm 2 .. Gate . ... BE Class Q8 Gate Traffic Class Filtering
spired by the TFA-based NC analysis. It consists of two interleaved phases: a Path-Level Update, which employs Gated Recurrent Units (GRUs) to capture the evolution of arrival curves, and a Port-Level Update, which aggregates flow information to update service curves under resource contention. This incorporates NC domain knowledge into GNN learning, enabling DeepNC to achieve high-fidelity delay regression. • Third, extensive test cases, including both synthetic and realistic, demonstrate that DeepNC serves as an accurate and efficient pre-verification surrogate for TSN configuration workflows. Compared with state-of-the-art learning-based methods, DeepNC achieves significantly higher regression fidelity, improving the average R2 by 55.8% while reducing MAPE by 65.3%. As a result, DeepNC accelerates NC verification by over two orders of magnitude and reduces formal calls by 93.25% on average, significantly outperforming SOTA baselines. The rest of the paper is organized as follows: We first review related work in Sec. II. Sec. III presents the system model and NC background. Our proposed pre-verification surrogate module, DeepNC, is detailed in Sec. IV. Extensive evaluations are presented in Sec. V, and Sec. VI concludes the paper.
p
p PTT
p PTT
1
p LTT 1
ES3
2
t
p LTT 2
(c) TT traffic transmission
.. .
1 1 fM fM f1 1 2 M3
GB
1 f BE f M 1 p idSl p credit idSl M M2 1 p p sdSl M 1
(b) hybrid TSN/TAS+CBS architecture
f M2 1 fTT
1 2 1 fM fM fM 3 1 2
p idSl M
p sdSl M
2
3
(d) ET traffic transmission
p sdSl M
t 3
Fig. 1: TSN/TAS+CBS Hybrid Architecture optimization. In contrast, DeepNC, proposed in this paper, structurally integrates the analytical principles of TFA-based NC analysis into GNN to support high-fidelity worst-case delay regression. III. TSN S YSTEM M ODEL A. System Model In this work, we consider a TSN with an arbitrary topology, composed of End Systems (ESs) and Switches (SWs) interconnected by full-duplex links of rate C. Each ES connects to a switch, and switches connect to other switches or ESs via their egress ports, where there is one-to-one mapping between a link and an output port. Fig. 1(a) illustrates a typical example, consisting of four ESs and two SWs, where the double-headed arrows represent physical links. Messages are transmitted as flows, which contend for link resources at the output ports of nodes (ESs or SWs). In this paper, we adopt a widely used hybrid TSN scheduling architecture combining the Time-Aware Shaper (TAS) and the Credit-Based Shaper (CBS) to provide real-time guarantees for applications with diverse QoS requirements. As shown in Fig. 1(b), this architecture supports three traffic classes: TimeTriggered (TT) flows controlled by TAS, Event-Triggered (ET) flows shaped by CBS, and Best-Effort (BE) traffic. Each output port p has eight queues for these classes, each with its own gate that controls frame forwarding. TAS is used for periodic, hard real-time TT flows, which are given the highest priority. It employs a Gate Control List (GCL) at each output port p to precisely control the open/close times of the queue gate, ensuring deterministic forwarding of TT as illustrated in Fig. 1(c). The GCL at a port p, denoted as a matrix Gp , defines the transmission schedule. Following ⇀ a flow-based scheduling abstraction, we assume each entry gfp in Gp corresponds to a specific TT flow, defined by the tuple ⇀p p p p p gf = [LpTT , PTT , OTT ], for ∀f ∈ FTT , where LpTT , PTT and p OTT are the frame length, period, and offset of a TT flow f , respectively. We assume all GCLs are pre-configured, and their synthesis is outside the scope of this paper. CBS schedules lower-priority ET flows, which have less stringent timing requirements. It supports nCBS priority classes,
where class Mi has a higher priority than Mi+1 . To prevent interference with TT flows, CBS queue gates are only permitted to open when the TT gate is closed, allowing ET flows to contend for the remaining bandwidth. The CBS uses a credit mechanism for bandwidth management, governed by an idleSlope parameter idSlpMi for each Class Mi at port p. An ET frame can only be transmitted if its gate is open and the CBS permits it. Each CBS queue for Class Mi maintains a credit value cpMi , initialized to zero. When the CBS gate is closed, the associated credit is “frozen”. When the associated CBS gate is open, the credit decreases by sendSlope sdSlpMi = idSlpMi − C during the transmission and increases with idleSlope idSlpMi when ET frames are waiting to be transmitted, as shown for example in Fig. 1(d) with three CBS classes. For each ET flow f , its frame size Lf and minimum inter-arrival time Pf p sending from the source ES are known. We denote FM as i the set of flows of Class Mi at queue qMi of port p. The remaining queues are used for BE flows, which have the lowest priority and do not provide real-time guarantees. B. Network Calculus Background Network Calculus (NC), which serves as the theoretical foundation guiding the architecture of DeepNC, is a rigorous mathematical framework for worst-case analysis of queuing systems, employing min-plus algebra to derive deterministic bounds on traffic and service processes [28], [29]. Total Flow Analysis (TFA), a prominent method within the NC framework, provides a methodology to aggregate per-node results. Let F↑ be the set of non-decreasing functions from non-negative reals R+ to R+ . 1) Per-Node Modeling: NC theory leverages min-plus convolution to provide envelope bounds to abstract the behavior on a single server. This involves characterizing the arriving traffic and the guaranteed service. The arrival curve αfp (t) is used to upper bound the amount of data from a flow f arriving at server p over any time interval. Let Rfp (t) ∈ F↑ denote the cumulative arrival function of the flow, counting the total number of bits that have arrived at a server p by time t. We say that αfp (t) is an arrival curve for the arrival process Rfp (t) ∈ F↑ of a flow if Rfp (t) ≤ (Rfp ⊗ αfp )(t), ∀t ≥ 0,
(1)
where ⊗ is the min-plus convolution operator, defined for any ∀f, g ∈ F↑ as, +
(f ⊗ g)(t) = inf {f (t − s) + g(s)}, ∀t ∈ R . 0≤s≤t
(2)
A typical arrival curve is the linear “burst-rate” envelope, αfp (t) = σfp + ρpf · t,
(3)
where σfp and ρpf are the maximum burst and long-term rate, respectively. Especially, at the source server p0 , σfp0 = Lf and ρpf0 = Lf /Pf . Moreover, when multiple flows of the same priority class Mi converge at a server p, their combined arrival p envelope is modeled by an aggregate arrival curve, αM (t), i which is typically the sum of the individual curves, p αM (t) = i
X p f ∈FM i
αfp (t).
(4)
This aggregate arrival curve is then used to compute the performance bounds for the shared resources, which is fundamental to the TFA method. p The service curve βM (t) defines the lower bound of proi cessing capability of a server p provided to aggregate flows of p p∗ priority Mi . Let RM (t) ∈ F↑ and RM (t) ∈ F↑ denote the i i cumulative arrival and departure functions of these aggregate flows at server p, respectively. We say that the server p is to p offer a min-plus service curve βM (t) to the aggregate flows i of priority Mi if p p p∗ )(t). ⊗ βM (t) ≥ (RM RM i i i
(5)
Based on these aggregate-level models, the worst-case latency for the entire aggregate traffic of class Mi at server p is upper bounded by the maximum horizontal deviation p between the aggregate arrival curve αM (t) and the service i p curve βMi (t), p = sup{inf{d ≥ 0 DM i t≥0
p p (t + d)}} = Dfp , (t) ≤ βM αM i i
(6)
which is also the WCDs for every individual flow f within that aggregate according to the TFA method [6], [29]. 2) Network Modeling: The core principle of TFA is to derive an end-to-end delay bound by summing the per-server delay bounds along the flow path. As stated previously, computing the latency bound at any given server p requires knowledge of the input arrival curve of each flow at that server. The arrival curve αfp0 (t) at the source node p0 is directly determined by the specified flow parameters, such as its maximum frame size and minimum frame interval. For any subsequent server p downstream, however, the arrival curve for a flow is altered by the service it received from upstream nodes. In NC, this evolution is typically captured by computing the output arrival curve αfp∗ (t), which upper-bounds the data amount of a flow departing from server p over any time interval, p p+1 (t), αf∗p (t) = (αfp ⊘ δD p )(t) = αf
(7)
f
p where δD p (t) is the pure-delay function [28] which equals f to 0 if t ≤ Dfp and +∞ otherwise, and ⊘ is the min-plus deconvolution operator, defined for any ∀f, g ∈ F↑ as,
(f ⊘ g)(t) = sup{f (t + s) − g(s)}, ∀t ∈ R+ .
(8)
s≥0
Note that it in turn serves as the input arrival curve αfp+1 (t) of the flow f for the subsequent hop p + 11 . Subsequently, the end-to-end WCDs for a specific flow f is derived by summing these per-server delay bounds along its route rf , X Dfp .
DE2E,f =
(9)
p∈rf
1 In TFA application [6], [29], burstiness often propagates per-flow because frequent aggregating and splitting make end-to-end aggregate propagation infeasible. For persistent aggregates, pessimism is commonly mitigated via shaping curves.
Optimizer
Network Feature Extraction (§IV-B)
N Candidates
Message Passing Design (§IV-C)
Path-Level State Update §IV-C1
DeepNC WCD prediction
No
Meet Deadlines?
Yes top-K Promising Candidates ( K << N ) NC Formal Analysis
arrival curve
hl
Queue Node
service curve Mapping NC Primitives
hf
after T iterations §IV-C3 Latency Prediction Layer
Link Node
Worst-case Delay
hq
Best Candidate
§IV-C2 Port-Level State Update
Flow Node
Fig. 2: Overall Framework. IV. D EEP NC: A NC T HEORY-G UIDED GNN A RCHITECTURE A. Overall Framework Our proposed model, DeepNC, is a purpose-designed GNN that structurally integrates the analytical principles of TFAbased NC for hybrid TSN/TAS+CBS networks [6]. The overall workflow incorporating DeepNC is illustrated in Fig. 2. During configuration-space exploration, DeepNC does not replace formal verification. Instead, we adopt a filter-then-verify paradigm in which only the top-K configurations predicted by DeepNC are subjected to NC formal analysis, thereby preserving the formal guarantees provided by NC. Additionally, because DeepNC provides high-fidelity delay prediction with substantially lower computational cost than NC analysis, it effectively alleviates the verification bottleneck in large-scale TSN configuration. It is worth noting that since DeepNC is designed to accelerate formal verification rather than replace it, the surrogate is expected to approximate the analytical results of NC as close as possible rather than the exact worst-case network behavior. Therefore, the conservativeness of NC with respect to the actual network behavior does not affect the objective of DeepNC. The DeepNC framework is implemented in two main stages, as illustrated in the right panel of Fig. 2: Network Feature Extraction (Sec. IV-B) and Message Passing Design (Sec. IV-C). The first stage, Network Feature Extraction, bridges the representation gap by translating the curve functions of NC into a GNN-compatible vector format. To achieve this, we construct a heterogeneous graph with F LOW, Q UEUE, and L INK nodes from the arrival curve (Sec. IV-B1) and the service curve (Sec. IV-B2) perspectives. Simultaneously, the key parameters defining these curves are extracted to initialize the feature vectors of their respective nodes. The second stage, Message Passing Design, is engineered to capture the complex dependencies inherent in NC formal analysis. Through customized message-passing steps, the hidden states of the graph nodes are progressively updated to emulate the evolution of arrival curves (Sec. IV-C1) and the impact of inter-queue contention on service curves (Sec. IV-C2). Finally, a readout layer (Sec. IV-C3) utilizes the final Q UEUE N ODE states to predict the per-server and end-to-end WCDs for each ET flow. The predicted delay bounds are subsequently used to filter candidate configurations as described in Algo. 2.
B. Network Feature Extraction: Mapping NC Primitives The first stage in realizing our DeepNC framework is to bridge the fundamental data representation gap between NC and GNNs. NC operates on curve functions, whereas GNNs require fixed-size feature vectors as input. This section details our methodology for this critical “function-to-vector” mapping. Specifically, our approach is to, drawing directly from the foundational concepts of NC (i.e., the arrival and service curves), define a set of graph nodes and construct their corresponding initial feature vectors. 1) From the Arrival Curve Perspective: To represent arrival envelope of each flow in the GNN, we define a F LOW N ODE as a surrogate for the arrival curve, instantiating one such node per ET flow. The crucial question, however, is how to define the initial ⇀ features (xf ) for these F LOW N ODE instances. As established in our NC background (Section III-B2), for an ET flow in TSN networks, the burst σfp0 and long-term rate ρpf0 correspond directly to the frame size Lf and the ratio Lf /Pf . Therefore, the initial feature vector for each F LOW N ODE instance is defined based on its source characteristics. This vector contains the parameters that fully define the source arrival curve αfp0 (t). The F LOW N ODE feature vector is formally defined as follows. Definition 1: (F LOW N ODE Feature Extraction) A F LOW NODE instance is designed to abstract the arrival curve of an individual ET flow f , with its initial features captured from source ES: ⇀ xpf0 = [Lf , Pf ],
(10)
where Lf and Pf are respectively the frame size and minimum time interval between two consecutive frames of f . We use raw [Lf , Pf ] rather than precomputed long-term rate ρpf0 to reduce preprocessing on large-scale graphs and enable the GNN to implicitly learn the rate during training. 2) From the Service Curve Perspective: The goal is to represent the service guarantees for specific flows at each server within the GNN. In TSN networks featuring a hybrid p TSN/TAS+CBS architecture, the service curve βM (t) for the i aggregate flows of CBS Class Mi at an egress port p is explicitly given by [6], " !# p βM (t) = idSlpMi · i
t−
p cp,max αTT (t) Mi − C idSlpMi
+
,
(11)
↑
p where αTT (t) is the aggregate arrival curve of higher-priority TT traffic derived from the GCL matrix Gp , [f (t)]+ ↑ = max0≤s≤t {f (s), 0}, and cp,max is the credit upper bound, Mi which is influenced by contention from other CBS classes. All traffic classes share port p and this contention is reflected in the service curve in Eq. (11). Its parameters fall into two groups: (i) queue-specific: idle slope idSlpMj and credit bound cp,max . (ii) port-shared: physical link capacity C and TT Mi p interference αTT (t). This parametric duality motivates us to represent the CBS server by two dedicated graph node types: (a) We term Q UEUE N ODE to represent the queue-specific parameters for each CBS Class Mi . (b) We term L INK N ODE to represent the port-shared parameters. This design choice is crucial: it avoids redundant modeling of shared parameters
(e.g., repeating C and GCL information in every queue node at the same port) and allows the GNN to learn the interactions between queues and their shared link through message passing, as detailed in Sec. IV-C. Thus, we instantiate one Q UEUE N ODE for each CBS class at a port, and a single L INK N ODE for the port itself. ⇀ The initial features xpqM for a Q UEUE N ODE must capture i parameters that influence the credit upper bound cp,max , which Mi is dependent on other competing CBS priority classes. To ⇀ address this, we introduce a one-hot vector epMi to encode the priority information, providing a basis for the GNN to subsequently learn the interactive effects from these competing priorities during the message passing phase (Sec. IV-C). The Q UEUE N ODE feature vector is formally defined as follows. Definition 2: (Q UEUE N ODE Feature Extraction) A Q UEUE N ODE instance is designed to abstract the queue-specific part of service curve for a CBS Class Mi at port p, with its initial features captured as: ⇀p
⇀ xqM = idSlpMi , epMi , i
(12)
Here, epMi = [0, ...1, ...0] is a one-hot vector encoding the CBS priority, where the bit at the index for Class Mi is set to 1 and 0 otherwise. This vector provides the structural basis for learning priority contention effects via message passing. ⇀ Similarly, the initial features xpl for a L INK N ODE must p (t). As detailed capture the aggregate TT arrival curve αTT p in [6], αTT (t) is a deterministic, hyperperiodic step function fully determined by the GCL2 . However, computing the parameters of its tightest envelope is a computationally intensive process. To avoid this high feature extraction cost, we again adopt a strategy of using the raw, fundamental parameters. p (t), we directly Instead of pre-calculating the envelope αTT extract the information from the columns of the GCL matrix ⇀p Gp . Specifically, we form a frame size vector gL , a period ⇀p ⇀p vector gP , and an offset vector gO . These vectors serve to p implicitly capture the information of αTT (t) without explicit computation. The L INK N ODE feature vector is formally defined as follows. Definition 3: (L INK N ODE Feature Extraction) A L INK N ODE instance is designed to abstract the port-shared part of the service curve at an egress port p, with its initial features captured as: ⇀ ⇀ ⇀ ⇀ ⇀
p p p xpl = gL , gP , gO ,C ,
⇀p
⇀p
(13)
⇀p
where gL , gP , and gO are the column vectors derived from the GCL matrix Gp , representing the frame sizes, periods and offsets of TT flows, respectively. We have now established the three types of graph nodes in our DeepNC framework, i.e., F LOW N ODE, Q UEUE N ODE, ⇀ ⇀ L INK N ODE, and their initial feature vectors (xpf0 , xpqM , i ⇀p xl ). These features are grounded in NC theory, bridging the “function-to-vector” gap. However, the graph constructed is heterogeneous: the initial feature vectors for each node type 2 As discussed in Sec. IV-A, DeepNC is designed to approximate the analytical results of the TFA-based NC formulation in [6] as faithfully as possible. Therefore, we adopt the same TT step function model as in [6].
reside in disparate semantic spaces, possessing inconsistent dimensions and different physical units (e.g., bit vs. s vs. bps). To ensure mathematical and semantic compatibility for subsequent operations, we employ distinct multi-layer perceptrons (MLPs) [30] to project these raw features into a unified latent ⇀ space. This mapping transforms the initial feature vectors (xpf0 , ⇀ ⇀ ⇀ ⇀p ⇀p xqM , xl ) into initial hidden states (htf0 ,p0 , htq0M,p , htl 0 ,p ) of a i i unified dimension, ⇀t ,p ⇀ hf0 0 = MLP1 (xpf0 ) ⇀ ⇀ htq0M,p = MLP2 (xpqM ) i ⇀t0 ,pi ⇀ hl = MLP3 (xpl ).
(14)
These hidden states then serve as the input for the first iteration t0 of message passing. C. Message Passing Design The next stage is to design a message passing mechanism that emulates the NC calculation trajectory. As described in Sec. III-B, the worst-case end-to-end delay bound results from a multi-step process involving (a) arrival curve evolution along the path and (b) service curve affected under inter-queue contention of different priorities. Our message passing layers are designed to simulate these path-dependent and contentionaware processes by directly mirroring the core NC operations. ⇀ The mechanism iteratively updates the hidden states (h) of nodes, which serve as vector-based representations for evolving NC curves. By aligning the GNN with the mathematical principles of NC, the model effectively captures the underlying physics of network worst-case end-to-end delay accumulation. In the following, we detail how DeepNC simulates the NC calculation through message passing among its F LOW, Q UEUE, and L INK nodes to predict the WCDs, as outlined in Algo. 1. The message passing is designed as an iterative process over T iterations (indexed by t = t0 , ..., tT −1 ). Each iteration consists of two main phases: A Path-Level State Update phase, which tracks the evolution of arrival curves along each flow path. A Port-Level State Update phase, which refines the service curve representations by incorporating aggregated traffic load and inter-queue contention information. These two phases are implemented as three types of state updates for the F LOW, Q UEUE, and L INK nodes. 1) Path-Level State Update (Algo. 1 Lines 2-5): For a given ⇀ flow f , its hidden state ht,p represents its arrival curve at f ⇀ egress port p along its path. The initial hidden state htf0 ,p0 is defined for the source port and remains fixed. This phase simulates the evolution of the arrival curve of each flow along its multi-hop path. In NC theory, the output arrival curve αf∗p (t) from port p becomes the input arrival curve αfp+1 (t) for the next hop p+1. As given by Eq. (7), αf∗p (t) is the min-plus deconvolution of αfp (t) with the pure-delay function δDfp (t). Therefore, the GNN needs ⇀representations for both the input arrival curve (provided by ht,p pure-delay function, f ) and the ⇀ which is encoded in Q UEUE N ODE state ht,p qM for CBS Class i
Mi 3 after port-level state updates (Sec. IV-C2). Note that the ⇀ Q UEUE N ODE state ht,p qMi encodes latency information only after the message-passing iterations (t > t0 ). With the hidden state representations of the input arrival curve αfp (t) and the pure-delay function δDfp (t) available, we can now formally define the state update for the F LOW N ODE. We employ a Gated Recurrent Unit (GRU) [26], a type of recurrent neural network adept at modeling stateful, sequential transformations, which aligns well with the hop-by-hop nature of the NC process of transforming an arrival curve. Definition 4 (F LOW N ODE State Update): A GRU cell is applied at each hop ⇀ p. Its input consists of the current F LOW N ODE hidden state ht,p f and the Q UEUE N ODE⇀ hidden state ⇀ t,p hqM , and its output is the updated hidden state ht,p+1 , which f i represents the output arrival curve of flow f at port p and serves as the input arrival curve for the next hop p + 1: ⇀
⇀ ⇀ t,p ht,p+1 = GRU ht,p , f f , hqM
(15)
i
It is worth noting that as message-passing iterations (t > t0 ) ⇀ ⇀ proceed, ht,p+1 is progressively refined as ht,p qMi aggregates f increasingly richer contextual information (Eq. (18)), thereby better representing the corresponding NC arrival curve. Addi⇀ 0 tionally, since the source arrival curve is deterministic, ht,p f ⇀ ⇀ ⇀ t+1,p0 t,p0 t0 ,p0 at source ES p0 remains fixed: hf = hf = hf . 2) Port-Level State Update (Algo. 1 Lines 6-11): After the path-level state update phase, we proceed to the port-level state update phase. This phase updates the hidden states of the Q UEUE and L INK nodes, preparing them for the next iteration t + 1 to refine the NC reasoning process. ⇀ The purpose of updating the Q UEUE N ODE state ht,p qMi is to create an aggregated representation of both the arrival curve and service curve for CBS Class Mi at port p. This aggregated representation is then used to ultimately predict the delay p bound DM of aggregate flows of CBS Class Mi at port p, i as according to Eq. (6), which is jointly determined by the p p aggregate arrival curve αM (t) and the service curve βM (t). i i ⇀
t,p We first construct a vector representation βM of the service i p curve βMi (t) for the current iteration t. As shown in Eq. (11), the service curve depends on both queue-specific parameters (e.g., idle slope) and port-shared parameters (e.g., link capacity and TT traffic interference). As presented in Sec. IV-B, these two types of information are encoded in the Q UEUE ⇀ ⇀ t,p N ODE state ht,p qMi and the L INK N ODE state hl , respectively. Therefore, we fuse them through an MLP to obtain the service curve representation: ⇀
t,p βM = MLPS i
h⇀ i ⇀ t,p ht,p . qM ∥ hl
(16)
i
Next, we compute an intermediate hidden state αt,p Mi to p represent the aggregate arrival curve αM (t) as given by i Eq. (4). This is achieved by summing the hidden states of ⇀
3 Following the TFA methodology [6], [29], the delay bound derived for aggregate flows of the same class Mi applies to every flow within that aggregate, as shown by Eq. (6).
Algorithm 1: DeepNC Pseudocode Input: Flow set F, ⇀ Queue set Q, ⇀ Link set L, initial ⇀ embeddings htf0 ,p0 , htq0M,p , htl 0 ,p , number of iterations i T Output: Predicted end-to-end worst-case delays ŷDE2E,f 1 for t ← t0 to tT −1 do 2 foreach f ∈ F do // Path-Level State Update (Sec. IV-C1) ⇀ ⇀ 0 3 ht,p ← htf0 ,p0 ; f 4 foreach p ∈ Pf do ⇀ ⇀ ⇀ t,p 5 ht,p+1 ← GRU ht,p ; // Eq. (15) f f , hqM i
6 7 8 9 10 11
foreach p ∈ L do // Port-Level State Update (Sec. IV-C2) do foreach qMi ∈ Qp h i ⇀ ⇀ ⇀ t,p t,p βMi ← MLPS ht,p ; // Eq. (16) qMi ∥ hl ⇀ P ⇀ t,p p ← h ; // Eq. (17) αt,p Mi f f ∈FM ih i ⇀ ⇀ ⇀ t,p ht+1,p αt,p ; // Eq. (18) qMi ← MLPQ Mi ∥ βMi i h ⇀ ⇀ ⇀ P t+1,p CBS ; ht+1,p ← MLPL ht,p ∥ n l l j=1 hqMj // Eq. (19)
foreach f ∈ F do // Latency Prediction Layer (Sec. ⇀ IV-C3) P ; 13 ŷDE2E,f ← p∈Pf MLPReadout htqTM,p i // Eqs. (20), (21)
12
all F LOW N ODE instances corresponding to CBS Class Mi passing through port p, X
αt,p Mi = ⇀
⇀
ht,p f .
(17)
p f ∈FM i ⇀
t,p With both αt,p Mi and βMi available, we can formally define the state update for the Q UEUE N ODE. Definition 5: (Q UEUE N ODE State Update) The hidden state of a Q UEUE N ODE for CBS Class Mi at port p is updated for the next iteration t + 1. The update is performed by an MLP that takes the concatenation of the aggregate arrival hidden state and the service hidden state from the current iteration t as its input: ⇀
⇀
ht+1,p = MLPQ qM i
h
⇀
t,p αt,p Mi ∥ βMi ⇀
i
.
(18)
It is worth noting the evolution of this state. At the initial ⇀ iteration (t0 ), the hidden state hqt0M,p primarily encodes its own i p service parameters (e.g., idle slope idSlM and priority index). i However, in subsequent iterations (t > t ), the Q UEUE N ODE 0 ⇀ state ht,p qMi will have additionally incorporated the delay bound information derived from the interaction between the aggregate arrival curve and service curve. ⇀ t,p The purpose of updating the L⇀ INK N ODE state hl is to t+1,p enrich the service hidden state βMi of the next iteration with information about inter-queue priority contention. This is achieved by updating the L INK N ODE state⇀using the aggregated information from all Q UEUE N ODES ht+1,p (j ∈ q Mj [1, nCBS ]) at the same port. Consequently, when the L INK state
Arrival Curve Related
Service Curve Related
SW
f SW
f
h tf+1, p0 = h tf, p0 = h tf0 , p0
Message Passing
...
h tf, p t , p h f ' h tf, p +1 SW
... t , p h +t , p f ' M
h tf, p t , p h qM
'
SW
h tl , p
Concat
MLP
h tf, p +1 t , p +1 h qM
output port p +1 M i ...
h tl , p +1
M
i
h tq+M1, p h tl , p i −1 ...
i
+ h tq+M1, p
MLP
Concat
Flow Node Update
MLP
Mt , p +1 i
t , p +1 ... h l
+t , p+1
Concat
Concat
i
...
i
GRU
...
SW
t , p
i
GRU
output port p M i ...
h tq,Mp i h tl , p
Algorithm 2: Two-Stage Configuration Verification
iteration t to iteration t+1(t=t0,...,tT-1)
Mi
Concat
+ h tq+M1, p +1
MLP
Concat
i
h tq+M1, p i h tl +1, p MLP
h
t +1, p l
h tq+M1, p +1 i h tl +1, p +1 MLP
h tl +1, p +1
Link Node Update
Queue Node Update Port-Level
Fig. 3: Message Passing of DeepNC.
Based on DeepNC Input: Ctotal (candidate configuration set), Tdead,f (per-flow deadlines), K (number of top candidates to retain) Output: C ∗ (optimal configuration verified by NC formal analysis) 1 Cf easible ← ∅; 2 foreach C ∈ Ctotal do 3 {ŷDE2E,f } ← DeepNC(C); // DeepNC (fast) 4 if max({ŷDE2E,f − Tdead,f }) ≤ 0 then 5 Cf easible ← Cf easible ∪ {C}; 6
⇀
ht+1,p is used in the next iteration ⇀to synthesize the service l t+1,p hidden state via Eq. (16), the new βM inherently reflects i the contention from all competing CBS classes. Definition 6: (L INK N ODE State Update) The hidden state of a L INK N ODE at port p is updated for the next iteration t + 1. The update is performed by an MLP that takes⇀the concatenation of its own state from the current iteration, ht,p l , and the sum ⇀ of the newly updated states of all Q UEUE N ODES at that port, ht+1,p qM , j ∈ [1, nCBS ], as its input: j
⇀
⇀ ht+1,p = MLPL ht,p ∥ l l
X
⇀
. ht+1,p q Mj
(19)
j∈[1,nCBS ]
It is worth noting that at the initial iteration (t0 ), the state htl 0 ,p of each L INK N ODE is constructed purely from its own initial features, and thus lacks any information regarding inter-queue priority contention. The message passing described above is shown in Fig. 3. 3) Latency Prediction Layer (Algo. 1 Lines 12-13): After T iterations of message passing, the final hidden state ⇀ htqTM,p of the Q UEUE N ODE has comprehensively encoded the i p information of both the aggregate arrival curve αM (t) and i p the service curve βMi (t). At this point, we can leverage this rich representation to predict the per-server delay bound. We employ a readout MLP layer to emulate the computation from p p the curves (αM (t), βM (t)) to the delay bound (Eq. (6)). The i i input to this MLP is the final Q UEUE N ODE state:
⇀
ŷDp
Mi
⇀ = MLPReadout htqTM,p = ŷDp . i
f
(20)
As according to Eq. (6), the delay bound of an aggregate of class Mi flows applies to any individual flow, so we have p p DM = Dfp , and thus also the prediction ŷDM = ŷDfp . Finally, i i according to Eq. (9), the end-to-end predicted delay bound for flow f is the sum of the predicted per-hop bounds along its path: X ŷDE2E,f =
ŷDp . f
(21)
p∈Pf
Based on the above design, DeepNC provides end-to-end WCD predictions for all ET flows under a given configuration with extremely low inference latency, making it an ideal pre-screening tool for large-scale configuration verification. Algo. 2 presents a two-stage DeepNC-based pre-verification process with integrated configuration tuning. In the first stage (Lines 1-9), DeepNC rapidly evaluates all candidates. Config-
7 8
else
C ′ ← TuningOpt(C, {ŷDE2E,f }); Ctotal ← Ctotal ∪ {C ′ };
Ctopk ← TopK(Cf easible , K); C ∗ ← arg optC∈Ctopk metric(NC Tool(C)); // Formal NC (safe but slow) ∗ 11 return C ; 9
10
urations meeting deadlines are added directly to the feasible set Cf easible , while the others are passed to a designer-defined tuning strategy TuningOpt(·). Unlike binary schedulability classification [11], [12], designers can customize the tuning strategy (e.g., adjusting bandwidth allocation or routing paths) based on the deviation between the predicted WCDs and their deadlines. This may convert infeasible configurations into potentially feasible ones while enriching the pool of high-quality candidates. Each tuned configuration C ′ is then reinserted into the candidate set Ctotal for subsequent evaluation. After traversal, the top K configurations in Cf easible are selected according to the designer-specified performance metric to form Ctopk . In the second stage (Lines 10-11), only these K candidates are evaluated by the formal NC analysis tool (safe but slow), and the configuration that optimizes the designer-specified performance metric is selected as the final configuration C ∗ . V. E XPERIMENTAL R ESULTS This section systematically evaluates DeepNC across estimation fidelity, generalization to unseen networks, preverification efficiency, and the contribution of individual design components. Experiments run on a laptop (Intel Core i710510U) and a workstation (NVIDIA RTX A6000). A. Experiment Setup To evaluate scalability across different network structures, we design four synthetic topologies: mesh, ring, and star2 (shown in Fig. 4), along with an extended variant of star2, denoted as star4, obtained by adding two more ESs per branch of star2. Combined with the realistic industrial-scale test case, Orion CEV [31] (Fig. 5), these five scenarios are used for both training and testing. For the synthetic topology dataset, we also generate network instances of varying sizes (ranging from 10 to 100 devices) for generalization experiments. Furthermore, to test generalization on unseen industrial networks, we additionally introduce three topologies from automotive Original Equipment Manufacturers: Renault (rn), Volvo (vlv), and FACE (face) [32]–[34], which are used
TABLE I: Comparison of Regression Accuracy Dataset
(b) ring
(a) mesh
(c) star2
mesh ring star2 orion
Mai
RouteNet
MAPE
R
2
38.53% 25.88% 18.20% 19.16%
0.5656 0.7214 0.7021 0.7228
DeepNC
MAPE
R
2
MAPE
R2
26.52% 37.12% 21.99% 25.75%
0.6060 0.4183 0.5969 0.7421
5.62% 6.90% 6.47% 14.44%
0.9768 0.9692 0.9524 0.9202
Fig. 4: Synthetic Topologies. DU1
DU2
DU3
CM1CA
CM1CB
SW11 SBAND1
CMRIU1
FCM1
LCM1
SW41
RCM1
SMACA
SM1CB
SW51
SW12
SBAND2 SW21
SW31
MIMU1
MIMU3 StarTr1
SW8 SMRIU1
SW7
MIMU2
SW22
SW6
SW32
SMRIU2
SW13 CMRIU2 SW14
StarTr2 GPS1
BFCU
FCM2
LCM2
RCM2
SW42
CM2CA
CM2CB
SW52 SM2CA
SM2CB
GPS2
(a) mesh
(b) ring
(c) star2
Fig. 5: Realistic Test Case Orion CEV Topology.
Fig. 6: Learning-based vs. formal NC-computed WCDs.
exclusively in the screening threshold analysis (Sec. V-D). For traffic distribution, we generate both TT and ET flows randomly, following the IEEE 802.3 standard. For each flow, the source and destination ESs are selected uniformly at random from all terminals. Frame lengths range from 64 to 1518 bytes. Periods for TT flow are randomly chosen from {5, 10, 15, 20, 30}ms and from {5, 10}ms for ET flows. ET flow priorities are randomly assigned from {1, 2, 3}. In the default setting, each topology contains 24 to 48 flows. For baseline comparison, we benchmark DeepNC against two SOTA ML baselines, both adapted specifically for our delay prediction task. For the Mai baseline [12], originally for binary schedulability classification, we adapt its readout layer to output continuous delay bounds. For the RouteNet [26] baseline, based on the well-known RouteNet-Fermi architecture initially designed to predict simulation-based network performance (e.g., via OMNeT++), we repurpose it by retraining the model using the WCDs calculated by NC as ground-truth labels. To accommodate the hybrid TSN/TAS+CBS network, we also feed the TAS-related and CBS-related parameters extracted in Sec. IV-B as input features to both baselines. To ensure a fair comparison, all baselines adopt the same training configuration as DeepNC. We implement DeepNC with TensorFlow, using T=8 message-passing iterations and a hidden dimension of 32. All MLPs have 2 layers with the same hidden size. We use ReLU [35] activation, MAE loss, and Adam [36] optimizer with learning rate 0.001. All models are trained for 100 epochs (300 steps each). B. Estimation Fidelity Comparison We compare DeepNC against two baselines across four topologies. For each topology, we use 600 training, 200 validation, and 200 test samples. Performance is measured using Mean Absolute Percentage Error (MAPE) and the coefficient of determination (R2 ). As shown in Table I, DeepNC significantly outperforms both baselines on all test sets. Specifically, DeepNC achieves an average MAPE of 8.36%, reducing errors by 61.96% and 68.68% compared to Mai and RouteNet, respectively. Further-
more, DeepNC maintains a consistently high average R2 of 0.9547, whereas the baselines exhibit significant instability. To validate the applicability of DeepNC in industrial environments, we also analyzed its performance on the Orion CEV network. This real-world test case features highly irregular connectivity and heavier traffic flow. As shown in Table I, despite the challenges posed by limited training data for this specific topology, DeepNC still maintained a high R2 value of 0.9202. This result is significant for industrial deployments: it demonstrates that because DeepNC learns the underlying analytical logic of NC rather than memorizing the topology, it maintains high prediction fidelity even in complex real-world scenarios with scarce training data. Fig. 6 shows scatter plots for three topologies, comparing WCDs predictions of each learning-based model with the NCcomputed ground truth4 . The predictions of DeepNC lie tightly along the diagonal (x = y), indicating high fidelity to the NC bounds. In contrast, Mai and RouteNet show larger deviations. C. Generalization Performance Evaluation We evaluate the adaptability and stability of DeepNC on unseen networks across five dimensions: network scale, traffic load, traffic parameters, GCL configurations, and topological structure. The results are summarized in Fig. 7. For network scale, we train all models (DeepNC, Mai, and RouteNet) exclusively on the 13-device star2 topology as shown in Fig. 4(c), and test them on a set spanning a wide range of network sizes (10 to 100 devices). As shown in Fig. 7(a), DeepNC maintains a stable MAPE below 14% across all scales. While its error shows a slight upward trend, the overall predictive performance remains robust. In contrast, the error for Mai grows linearly with network size, and the error for RouteNet is highly unstable. For traffic load, we train all models on the star2 topology with 24–48 flows and evaluate them on configurations with a much higher flow count (50 to 110 flows). As shown in 4 DeepNC serves as a surrogate within the formal NC verification workflow rather than replacing it. It is meaningful as a surrogate only if it approximates the analytical results of NC, regardless of the pessimism of those results.
# of devices
# of streams
(a) Runtime Comparison
(b) Traffic Load
period groups(ms)
# of TT flows
(d) GCL
Topology
(e) Topological Structure
Fig. 7: Comparison of Scalability and Robustness. Fig. 7(b), DeepNC consistently maintains an MAPE below 12% across all tested flow densities. In comparison, both baselines lag significantly behind DeepNC. This again highlights the limitation of the baseline models: they lack a structural awareness of the NC process, reflecting overfit to the specific network characteristics of the training data. For traffic parameters, we train all models on star2 with TT periods from {5, 10, 15, 20, 30}ms and ET periods from {5, 10}ms. Test sets use periods as multiples of 4, 4.5, 5.5, and 6 ms. As shown in Fig. 7(c), DeepNC achieves MAPE between 8.29% and 10.69% (avg. 9.2%), while Mai (≈ 20.3%) and RouteNet (≈ 46.5%) lag far behind. This indicates that DeepNC learns the underlying NC logic rather than memorizing specific period values. For GCL configurations, we train all models on star2 with 15–30 TT flows and test them on five groups: 30–39, 40–49, 50–59, 60–69, and 70–79 TT flows. As shown in Fig. 7(d), DeepNC achieves MAPE between 5.67% and 9.37% (avg. 7.35%), with only a slight degradation as TT flows increase, while Mai (≈ 36.4%) and RouteNet (≈ 56.3%) perform significantly worse. This confirms that DeepNC provides accurate WCDs predictions for ET flows under unseen GCL configurations in TSN/TAS+CBS networks. For topological structures, we train all models on a single topology (e.g., mesh) as described in Sec. V-B, and then test them on a mixed set comprising the remaining two topologies (e.g., ring and star2 when training on mesh), with balanced samples from each topology. As shown in Fig. 7(e), DeepNC demonstrates stable cross-topology performance, consistently achieving R2 scores above 0.96 regardless of the training topology. In contrast, the Mai baseline shows only moderate adaptability, while RouteNet performs poorly. This is because DeepNC internalizes the structural dependencies of NC rather than overfitting to specific topologies.