Flow-Based Joint Programming of Time Sensitive Task and Network

Abstract

Owning to the application of artificial intelligence and big data analysis in industry, automobiles, aerospace, and other fields, the high-bandwidth candidate, time-sensitive networking (TSN), is introduced into the data communication network. Apart from keeping the safety-critical and real-time requirements, it faces challenges to satisfy large traffic transmission, such as sampled video for computer vision. In this paper, we consider task scheduling and time-sensitive network together and formalize them into a first-order-constraints satisfy module theory (SMT) problem. Based on the result of the solver, we build flow-level scheduling based on IEEE 802.1 Qbv. By splitting the flow properly, it can reduce the constraint inequality as the traffic grows more than the traditional frame-based programming model and achieve near 100% utilization. It can be a general model for the deterministic task and network scheduling design.

1. Introduction

It has been globally recognized that the construction of an intelligent industrial Internet will significantly enhance society as a whole. One key enabling technology is ensuring smooth production pipeline operations as machines are interconnected akin to the Internet. Deterministic design is a fundamental requirement where data must be sent, received, and operated on in a timely manner without ambiguity, including for both hard and soft real-time applications such as motion control, equipment manufacturing, and self-driving.

Traditional industrial networks separately consider communication and computing, with a focus on real-time execution of task scheduling on the CPU (central processing unit) and treat the network as a transparent substrate. The upper layer logic entrusts all communication support to the best effort (BE) network after establishing coarse time precision. Logic is highly reliant on communication for the correctness of the logic, with a few mistakes. For example, consistency or Byzantine problems are the primary focus of applications that relax network time precision to a second or minute level to ensure such correctness.

Additionally, the lack of semantic abstraction in the substrate layer can hinder fine-grained time control (microseconds to milliseconds) due to queuing strategies. For example, regardless of how many new versions of TCP (transmission control protocol), such as New Nano, Cubic, and BBR New Nano, Cubic, and BBR are commonly used in TCP, the classic three-way handshake is always employed. All entities engage in non-cooperative competition, with the whole network fluctuating around a Nash equilibrium [1]. Therefore, integrated consideration of communication and computing has become an important candidate for achieving microsecond to millisecond precision control.

With regard to communication, TSN [2,3,4] strives to establish a deep interconnection between the industrial network and the current Internet. The latter’s ecosystem, high bandwidth, and generality bring endless opportunities for the former’s development. One benefit of TSN is the flexibility it offers in terms of business support, as it can accommodate both real-time and BE messages. Another benefit is the high bandwidth capacity that allows for a wider variety of traffic. For example, autonomous vehicles require action after the computer vision process involving video sampled by the camera, which generates traffic several orders of magnitude higher than traditional industrial messages, i.e., CAN [5], Flexray [6], Lin [7], EtherCat, and TTE (time-triggered ethernet) [8] (each message is approximately 30∼500 bytes). Currently, the main challenge in applying TSN is the complex scheduling mechanisms [9], including the fundamental standard 802.1 Qbv, which attempts to design the gate-control list of each switch to meet strict delay and jitter requirements.

Turning to computing, real-time task scheduling is a historically mature topic [10,11,12]. RMS (rate monotonic scheduling), EDF (earliest deadline first), LLF (least slack first), and other classic algorithms have been integrated into real-time operating systems (RTOS), which can provide excellent real-time computing capabilities. However, there is still a gap between task scheduling and TSN when combining them for end-to-end scheduling. Although Craciunas et al. [13] began to combine tasks with TTE based on the assumption that one time-triggered frame is assigned to one task and shares the same period, and it can achieve excellent end-to-end delay and jitter control, it has two disadvantages. Firstly, it inherits the low bandwidth utilization of TTE; secondly, its frame-based programming model based on SMT (satisfy module theory) hardly supports large traffic tasks, where the NP-hard computation cost of SMT makes it hardly acceptable when the number of frames is larger than 10,000. Therefore, based on a similar idea, this paper proposes replacing TTE with TSN and proposes joint scheduling of both time-sensitive tasks and the network. Moreover, Refs. [14,15,16,17] have carried out corresponding work in joint task and network scheduling. One class of methods is based on flow control strategies, adjusting the network traffic to meet task requirements. Another type of method focuses on task scheduling, selecting the optimal execution order based on task characteristics and network status. There are also methods that combine flow control and task scheduling strategies to achieve more comprehensive optimization. However, these kinds of ‘jointing’ take more attention with respect to the task and, we must consider how to adjust the network to satisfy the requirement. In our work, we can elevate the scheduling granularity of TSN data transmission from the frame level to the flow level, which can establish a one-to-one correspondence between the time control granularity of the task level and the granularity of network transmission, and has potential cross-layer transmission capabilities

Our main contributions are as follows.

• We propose a novel periodic flow split theory and method that enables the mixed transmission of both periodic large and small flows while achieving near-100% bandwidth utilization with appropriate jitter control.
• We introduce a flow-based SMT programming model and enumerate the corresponding first-order logical constraints. The scheduling unit is flow-level, while the identification unit is frame-level, enabling the support of larger-scale SMT solutions.
• We map the transmission data of tasks into flow-level or split-flow-level gates. This approach allows tasks to label their data and track them in each device, potentially providing a new paradigm for application design.

The remainder of this paper is organized as follows:

Section 2 provides the background information and definitions of key terminology. Section 3 presents the flow-level scheduling model. Section 4 formulates the corresponding constraints. Section 6 demonstrates the experiment results and discussion of the proposed model. Section 7 summarizes the related works. Finally, Section 8 concludes this work and outlines future work.

2. System Model and Terminology

2.1. Joint Programming Model

Figure 1 depicts the logical model, where the upper layer contains real-time computing nodes and the lower layer contains TSN switch nodes. The topological structure is abstracted as a directed graph $G(V,E)$, where the vertex set $V=N\cup S$, N represents the set of computing nodes, S is the set of switch nodes and E is the set of directed links connecting nodes in V. Each link is denoted by pair of nodes $〈v_i,v_j〉\in E$, indicating the direction from $v_i$ to $v_j$. $N_i▷N_j$ denote the flow path composed of the ordered sequence of links between $N_i$ and $N_j$. For instance,

$$N_1▷N_2=〈〈N_1,S_1〉,〈S_1,S_2〉,〈S_2,N_2〉〉$$

For simplicity, it can also be represented as an ordered sequence of nodes,

$$N_1▷N_2=〈N_1,S_1,S_2,N2〉$$

Let $\mathcal{P}$ denote the set of all the paths that have data transmission.

2.2. Time Sensitive Task and Flow Formulation

Assume all the tasks are generated by the computing nodes, we define $\mathcal{T}\left(t\right)$ as the set of live tasks at time t; when $\mathcal{T}\left(t\right)$ changes, the scheduling strategy must also be adjusted. Each task $T_i\in \mathcal{T}\left(t\right)$ has a life cycle characterized by the start time $T_i.start$ and end time $T_i.end$. In the majority of this paper, we focus on a relatively stable environment where $∥\mathcal{T}\left(t\right)∥$ remains constant in a long term, and $\mathcal{T}\left(t\right)$ can be simply denoted as $\mathcal{T}$.

Real-time systems typically involve periodic and aperiodic tasks. Aperiodic tasks can be classified into deadline-constrained and best effort (BE) tasks. The key to optimal scheduling lies in periodic and deadline-constrained aperiodic task scheduling. Therefore, our focus is on how to optimally schedule these types of tasks. We use ${\mathcal{T}}_p$ and ${\mathcal{T}}_d$ to denote the set of periodic task and deadline-constraint aperiodic tasks, respectively. For $T_i\in {\mathcal{T}}_p$, the tuple $〈T_i.\varphi ,T_i.C,T_i.D,T_i.P〉$ denotes the offset in each period, WCET (worst-case execution time), deadline and period. This 4-ary tuple can also represent the characteristics of tasks in ${\mathcal{T}}_d$ and BE tasks. For $T{d}_i\in {\mathcal{T}}_d$, we set $T{d}_i.P=-1$.

$N_i.\mathcal{T}$ represents the task set executed on node $N_i\in N$, which includes local tasks $N_i.{\mathcal{T}}_{local}$, input tasks $N_i.{\mathcal{T}}_{in}$ and output tasks $N_i.{\mathcal{T}}_{out}$. Each task in $N_i.{\mathcal{T}}_{out}$ generates a data flow sent to other nodes, and $F^{N_i▷N_j}$ denotes the flow from node $N_i$ to node $N_j$. Let $N_i.\Gamma$ denote the flow set on $N_i$. There is a bijective relationship between the task and flow, represented by $g:T\to F$, such that the flow set on node $N_i$ is $N_i.\Gamma =N_i.g\left({\mathcal{T}}_{out}\right)$ and flow $F_j$ generated by task $T_j$ is $F_j=g\left(T_j\right)$. We inherit the 4-ary tuple $〈F_i.\varphi ,F_i.C,F_i.D,F_i.P〉$ to denote the offset in each period, the transmission time, deadline, and period, where $F_i.C=\frac{flow-size}{link-bandwidth}$. Generally, $F_i.D=F_i.P=T_i.P$ because the flow deadline has little impact on the task deadline and every flow can finish transmission within its period to avoid piling up. Let $〈v_i,v_j〉.\Gamma$ and $F_x^{〈v_i,v_j〉}$ denote the flow set and the flow $F_x$ on link $〈v_i,v_j〉$, respectively. Note that in our figures and theoretical descriptions, we use $P_i$ and $C_i$ instead of $F_i.P$ and $F_i.C$ for simplicity; if there is any confusion, please treat the two as equivalent. Additionally, we stipulate that all periods within the same set are distinct because all flows with the same period can be bundled into one flow for scheduling.

Let $N_i.Des$ denotes the set of destination nodes that node $N_i$ will send data flow to and $N_i.Src$ denotes the set of source nodes that node $N_i$ will receive data flow from. Our objective is that every task T can be executed in real-time smoothly and $F=g\left(T\right)$ can be transmitted through the network deterministically and timely. The core question is how to schedule all the tasks and flows properly. Owing to the different requirements, we should first judge the schedulability and then give a related schedule strategy. We have the following definitions.

Definition 1 (task schedulable). 

If task $T\in N_i.\mathcal{T}$ can be executed in node $N_i$ within the constraints, we say T is task schedulable in $N_i$.

Definition 2 (flow schedulable). 

If flow $F^{N_i▷N_j}$ can obtain $N_j$ within the constraints, we say $F^{N_i▷N_j}$ is flow schedulable.

Definition 3 (end-to-end schedulable). 

For node pair ($N_i$, $N_j$), we say task T can be end-to-end schedulable if T and $g^{-1}\left(F\right)$ is task schedulable in $N_i$ and $N_j$, respectively, and $F=g{\left(T\right)}^{N_i▷N_j}$ is flow schedulable.

Definition 4 (computing node schedulable). 

If $\forall T\in N_i.\mathcal{T}$ are task schedule, we say the node $N_i$ is computing node schedulable.

Definition 5 (holistic schedulable). 

The system is holistically schedulable if $\forall N_i\in \mathit{N}$ are computing node schedulable and $\forall T_{out}\in N_i.{\mathcal{T}}_{out}$ are end-to-end schedulable.

According to the definition, our target is to design a holistic schedulable system. However, unlike the loosely coupled traditional Internet, many scenarios in the industrial Internet are tightly coupled. Owing to the task growth and resource limit, maximizing utilization is a big challenge. We first pay more attention to the real-time transmission and later make a joint optimization by combining both of them by building a connection between the time of task scheduling and the network.

3. Flow-Based Deterministic Scheduling

In the traditional industrial scenario, the instruction set of the servo/PLC (programming logic controller) has complete semantics, and one instruction can be encapsulated into one frame whose size is from 32 to 500 Bytes. The frame is non-preemptive and TTE/CAN/Lin is enough. While in the self-driving scenario, for instance, there are about several megabytes (MB) of video for every 33 ms from the camera, there are 100 bytes of detection signal for every 31 μs from Ladar [6]. To the best of our knowledge, they are always handled by hard slice isolation based on TDM (time-division multiplexing) or isolated physical channels, which is costly. How to make these two kinds of flow co-exist through TSN is a big challenge.

As depicted in Figure 2a, $F_2$ represents a large flow and $F_1$ a small flow. When they are sent to the same link, $F_1$ will occupy multiple periods of $F_2$. Similar to task scheduling, it is easy to think of assigning different priorities to different flows, and then a higher priority flow can preempt lower ones. Figure 2b indicates the scheduling effect after $F_1$ is preempted by $F_2$ based on the traditional scheduling algorithm, RMS, EDF, or LLF. $F_1$ is divided into three segments, but the cutoff positions, the number, and the size of the segments are unpredictable. Apart from this, these algorithms have the following features. An RMS algorithm flow with a smaller period has higher priority and can provide a stable scheduling strategy while the utilization is limited to about 70%. An EDF (LLF) algorithm flow with the earliest deadline (least slack) has higher priority and has a utilization close to 100%, although the priority is unstable.

Generally, we hope the initial offset in the first period of each flow will repeat in the following periods like TTE; however, because preemption is inevitable and unpredictable, the delay and jitter of the preempted parts will be out of control. Therefore, we propose flow-based deterministic scheduling (FDS). Just as TTE knows the location and length of all the frames in every period, FDS considers the offset of each flow and the time when preemption happens in every period. Then, we can schedule the flow but not the frame to support large traffic and meanwhile calculate the detailed information on the frame level. It is stable and has about 100% utilization.

Table 1. Different scheduling strategy comparation.

Strage	Stability	Utilization
RM	stable	≈$70\%$
EDF/LLF	unstable	≈$100\%$
FDS (this paper)	stable	≈$100\%$

shows the comparison.

Assume the flow set $\Gamma$ and $\forall F_i\in \Gamma ,F_i.C,F_i.P$ are given. These flows will repeat in a hyperperiod, $Hyp=lcm(F_1.P,F_2.P,\dots )$, which is the least common multiple (lcm) of all the periods in the flow set. If $F_i$ is not cut off by other flows, we need to know all the offsets, $F_i.{\varphi }_1$, …, $F_i.{\varphi }_{Hy{p}_i}$, in its hyperperiod, $Hy{p}_i=\frac{Hyp}{F_i.P}$. If $F_i$ is preempted, we can set $F_i=\left\{f_{i_1},f_{i_2},\dots ,f_{i_{m_i}}\right\}$, where $F_i.C={\sum }_{j=1}^{m_i}{f}_{i_j}.C$ and $f_{i_j}$ is the j-th segment, which has the offsets, $f_{i_j}.{\varphi }_1$, …, $f_{i_j}.{\varphi }_{Hy{p}_i}$, and transmission time, $f_{i_j}.C_1$, …, $f_{i_j}.C_{Hy{p}_i}$ in $Hy{p}_i$. According to the above analysis, $m_i$ determines the number of variables and the size of the problem. When $\forall F_i,m_i=1$, FDS is basked to one flow per period scenario, it is very similar to one frame per period of TTE. So the key problem is to find proper $m_i$.

Firstly, we consider two flow scenarios illustrated in Figure 3; the two flows are zero-released, $F_1$, $F_1.P=20$, $F_1.C=7$ and $F_2$, $F_2.P=50$, $F_2.C=28$, respectively. Assume $F_1$ is atomic and its periodic flow can move back and forth within its period; the maximal available transmission time is $2\ast ({\mathit{P}}_{\mathit{1}}-{\mathit{C}}_{\mathit{1}})$ and the minimal is 0 as shown in Figure 3a. $F_2$ is split into $⌈\frac{{\mathit{C}}_{\mathit{2}}}{2\ast ({\mathit{P}}_{\mathit{1}}-{\mathit{C}}_{\mathit{1}})}⌉$ segments, which is the lower bound of $m_i$. If $F_1$ has no jitter and is set as anchoring flow, the periodic flow of $F_1$ comes out in fixed time in every period. Figure 3b shows that $F_2$ is split into $⌈\frac{{\mathit{C}}_{\mathit{2}}}{({\mathit{P}}_{\mathit{1}}-{\mathit{C}}_{\mathit{1}})}⌉$ segments, which is the upper bound of $m_i$. However, these two extreme cases indicate $m_i$ is changing and hard to be predicted. If we slightly adjust the offset of $F_1$ as shown in Figure 3c, bringing in jitter, the segments of $F_2$ can keep the same number and size as a previous period in $F_2$. Therefore, it can be the first rule of $m_i$. To further simplify the number of parameters, we specify previous $m_i-1$ segments that have the same size, ${\ell }_i$, and the size of the last segment is $r_i$. In this way, a segment set of flow $F_i$ can be represented as $(m_i,{\ell }_i,r_i)$ and we have

$$F_i.C=(m_i-1)\ast {\ell }_i+r_i$$

(1)

After considering the two flow scenarios, Equation (1) is also suitable for multiple flows. Namely, $\forall F_i\in \Gamma$, we have $(m_i,{\ell }_i,r_i)\in (M,L,R)$ waiting for scheduling. Before obtaining $(M,L,R)$, we need to compute the available transmission time for multiple periodic flows. We have the following theory.

3.1. Available Transmission Time Theory

Definition 6 (available transmission time). 

The accumulated time that can be used for transmitting certain flows when all the flows are considered in the same timeline.

Theorem 1.

Given a set $(F_1,\dots ,F_n)$ of periodic flows, $P_1<P_2<\cdots <P_n$, the available transmission time for $F_i$ is

$$B_i=P_i-\sum _{j=1}^{i-1}{C}_j\ast ⌈\frac{P_i}{P_j}⌉$$

(2)

We use an inductive approach to give a strict proof.

Proof. 

It is very clear that if $i=1$, then $B_1=P_1$, which means the whole interval in period $P_1$ is available for $F_1$.

If $i=2$, then $B_2=P_2-C_1\ast ⌈\frac{P_2}{P_1}⌉$, which means the available for $F_2$ is $P_2$ minus the occupied interval $C_1$ for $⌈\frac{P_2}{P_1}⌉$ times.

Assume that for an arbitrary $i=k$, $B_k$ is true, i.e., $B_k=P_k-{\sum }_{j=1}^{k-1}{C}_j\ast ⌈\frac{P_k}{P_j}⌉$. Let us derive $B_{k+1}$ from this assumption. For $P_{k+1}>P_k$, the available interval in $P_k$ will repeat $⌈\frac{P_{k+1}}{P_k}⌉$ times and $F_k$ will consume the available interval $⌈\frac{P_{k+1}}{P_k}⌉$ times. Then the left time for $F_{k+1}$ is $(B_k-C_k)\ast ⌈\frac{P_{k+1}}{P_k}⌉$.

Bringing $B_k$ in the expression, we have

$$B_{k+1}=P_k\ast ⌈\frac{P_{k+1}}{P_k}⌉-\sum _{j=1}^{k-1}{C}_j\ast ⌈\frac{P_k}{P_j}⌉\ast ⌈\frac{P_{k+1}}{P_k}⌉-C_k\ast ⌈\frac{P_{k+1}}{P_k}⌉$$

(3)

It can be directly obtained that $B_{k+1}=P_{k+1}-{\sum }_{j=1}^k{C}_j\ast ⌈\frac{P_{k+1}}{P_j}⌉$ if $P_{k+1}$ is divisible by $P_k$ and $P_k$ is divisible by $P_1$, $P_2$, …, $P_{k-1}$. Otherwise, we need to consider the essence of the expression. We can see $⌈\frac{P_k}{P_j}⌉$ is an estimate of the number of occurrences of $F_j$ in period $P_k$ and $⌈\frac{P_{k+1}}{P_k}⌉$ is an estimate of the number of repetitions of $P_k$ in period $P_{k+1}$. The product of the two values is computed from the number of final repetitions of $F_j$ in $P_k$; therefore, we can replace $⌈\frac{P_k}{P_j}⌉\ast ⌈\frac{P_{k+1}}{P_k}⌉$ with $⌈\frac{P_k}{P_j}⌉$. It can minimize the loss of data rounding. In the same way, $P_k\ast ⌈\frac{P_{k+1}}{P_k}⌉$ should be $P_{k+1}$. Then, we can see that (1) holds when $i=k+1$. Above all, the claim follows. □

According to the theorem, we have the following corollary about the utilization of FDS.

Corollary 1.

The FDS scheduling utilization can close to 1.

Proof. 

According to Theorem 1, if all the available transmission time is exhausted, namely $\exists I,B_I=0$, then the whole transmission time is used by flows, $F_1\dots F_{I-1}$, and we have $P_I-{\sum }_{j=1}^{I-1}{C}_j\ast ⌈\frac{P_I}{P_j}⌉=0$. After dividing $P_I$ on side, we can obtain ${\sum }_{j=1}^{I-1}{C}_j\ast ⌈\frac{P_I}{P_j}⌉\ast \frac{1}{P_I}=1$. Using the same way as the proof of theorem 1, we can eliminate $P_I$ and obtain the approximate sum of the occupied ratio of $F_1\dots F_{I-1}$, which is the utilization that is close to 1. Then, the corollary claims. □

We can easily have the following corollary about schedulability without proof.

Corollary 2.

The flow $F_i$ can be schedulable if only if

$$B_i\ge C_i$$

(4)

The corollary means the total occupied time in period $P_i$ should be less than the available interval. It can be used to judge whether a new flow can be added. If the available interval is enough, it is important to arrange related flow in such an interval. As depicted in Figure 4, if $\exists C_j>max(P_i,2(P_1-C_1)$, $F_j$ must be preempted. Next, we need to estimate the number of segments $m_i$.

3.2. Segment Estimation

If all the periods are zero-released and we align smaller $P_j$, where $j\in \left[1,i-1\right]$ in the interval $\left[0,P_i\right]$. Algorithm 1 presents a simple way to compute the number of blocks that a smaller period cut a larger period. For example, in Figure 4, $P_1=2$, $P_2=5$, $P_3=12$, $P_1$ can split $P2$ into three blocks, $P_1$ and $P_2$ can together split $P_3$ into seven blocks. In our model, these estimated values are treated as a reference. Then, we have to obtain the estimated average available space $b_i$ in each block for flow $F_i$ by

$$b_i=\frac{B_i}{{\pi }_i}$$

(5)

where ${\pi }_i$ is the number of split blocks in one period $P_i$. The core idea is to repeat all periods in the hyperperiod and sort them in ascending order. The first index of value $P_i$ is ${\pi }_i$. The estimated $m_i$ can be

$$m_i=⌈\frac{C_i}{b_i}⌉$$

(6)

If there is $C_j\gg P_i$, flow $F_i$ has to preempt $F_j$ at least $\frac{C_j}{P_i}$ times, which can be used as reasonable evidence of our estimation algorithm.

Algorithm 1 Estimated number of segment

Require : Period set $\mathit{P}$, transmission time set $\mathit{C}$ Ensure : Segment set $(\mathit{M},\mathit{L},\mathit{R})$ 1: n ← size($\mathit{P}$) 2: Hyp ← LCM($\left(P\right)$) 3: for i in [$1,n-1$] do 4:    j ← 1 5:    while $H_i\le P_n$ do 6:      $List$.append($j\ast P_i$) 7:      j ← j+1 8:    end while 9: end for 10: $List$← DeduplicationAndSort($List$) 11: $B_1=P_1$, ${\pi }_1=1$, $m_1=1$ 12: for i in [$1,n-1$] do 13:    ${\pi }_i$← List[$P_i$].Index() 14:    $B_i=P_i-{\sum }_{j=1}^{i-1}{C}_j\ast \frac{P_i}{P_j}$ 15:    $b_i=\frac{B_i}{{\pi }_i}$ 16:    $m_i=⌈\frac{C_i}{b_i}⌉$, $\mathit{M}.append\left(m_i\right)$ 17:    ${\ell }_i=\frac{C_i}{m_i}$, $\mathit{L}.append\left({\ell }_i\right)$ 18:    $r_i=C_i-{\ell }_i\ast m_i$, $\mathit{R}.append\left(r_i\right)$ 19: end for 20: return $(\mathit{M},\mathit{L},\mathit{R})$

4. Constraints Formulation

After obtaining $(\mathit{M},\mathit{L},\mathit{R})$, the components of the scheduling flow set are also determined. The objective is to compute the offsets of all the flows and then transfer them into the gate control list. We use SMT to build the following first-order constraints. It mainly includes intra and inter-flow and task constraints in computing nodes.

4.1. Intra Flow Constraint

4.1.1. Boundary Constraints

The segment of flows $F_x$ needs to satisfy the boundary constraints, which means all the segments need to stay at their period. $f_{x_1}.{\varphi }_{\mu }$ and $f_{x_{m_x}}.{\varphi }_{\mu }$ are the first and the last segments, respectively, in its $\mu$-th period. The other segment $f_{x_i}.{\varphi }_{\mu }$ needs to keep transmission order in the same period. Unlike the constraints in the literature [18,19,20], the constraint of each segment in each period is independent of other periods in the same flow hyperperiod.

$$\begin{array}{cc}\hfill & \forall F_x\in \Gamma ,\forall 1\le i\le m_x,\hfill \\ \hfill & \forall \mu \in \left[1\dots Hy{p}_x\right]:\hfill \\ \hfill & f_{x_1}.{\varphi }_{\mu }\ge \mu \ast P_x,\hfill \\ \hfill & f_{x_i}.{\varphi }_{\mu }+{\ell }_x\le f_{x_{i+1}}.{\varphi }_{\mu }\hfill \\ \hfill & f_{x_{m_x}}.{\varphi }_{\mu }+r_x\le (\mu +1)\ast P_x\hfill \end{array}$$

(7)

The number of constraint inequalities is about ${\sum }_{\left|\Gamma \right|}{m}_x\ast (Hy{p}_x+1)$, where $\left|\Gamma \right|$ denotes the size of the set.

4.1.2. Dispersion Degree Constraints

Since the segment may be dispersed in all the possible positions in the period if it only satisfies the boundary constraint. The time span between $f_{x_1}$ and $f_{x_{m_x}}$ might cover the whole period, even if the $\frac{C_x}{P_x}$ is small. Hence, we introduce a coefficient $\alpha$, called the dispersion degree, to adjust the time span. We have the dispersion degree constraints.

$$\begin{array}{cc}\hfill & \forall F_x\in \Gamma ,\hfill \\ \hfill & \forall \mu \in \left[1\dots Hy{p}_x\right]:\hfill \\ \hfill & f_{x_{m_x}}.{\varphi }_{\mu }-f_{x_1}.{\varphi }_{\mu }\le {\alpha }_x\ast C_x\hfill \end{array}$$

(8)

The number of constraint inequalities is about ${\sum }_{\left|\Gamma \right|}Hy{p}_x$. In this constraint, to keep the same scaling ratio, we use the same $\alpha$ for one flow. It can further guarantee its stability at the task level. This constraint can improve performance when the whole system has a solution. It is usually used as an additional supplementary based on boundary constraints.

4.1.3. Local Jitter Constraints

As the segment $f_{x_i}$ from the different periods might have different offsets, it will bring inter-period jitter in the same flow period. By taking the segment in the chosen period as a reference, we set local jitter constraints.

$$\begin{array}{cc}\hfill & \forall F_x\in \Gamma ,\forall 1\le i\le m_x,\hfill \\ \hfill & \forall \mu \in \left[1\dots Hy{p}_x\right]:\hfill \\ \hfill & \left|f_{x_i}.{\varphi }_{\mu }-\mu \ast P_x-f_{x_i}.{\varphi }_0\right|\le {\delta }_x\hfill \end{array}$$

(9)

The number of constraint inequalities is about ${\sum }_{\left|\Gamma \right|}{m}_x\ast Hy{p}_x$. Usually, the first period is the chosen one, and the difference between the period and all the other corresponding segments in the subsequent periods is limited to ${\delta }_x$. It is also supplementarily based on the boundary constraints. If ${\delta }_x=0$, the offset of all the segments in each period is equal to each other, then the model can be simplified by only considering the first period like the TTE model. This strict constraint will reduce the solution space and bandwidth utilization. When $f_{x_0}.{\varphi }_0=0$ and $f_{x_0}.{\varphi }_{\mu }-\mu \ast P_x=P_x-C_x$, we can obtain the maximal ${\delta }_x$, namely $max{\delta }_x=P_x-C_x$, where the constraints has no practical effect. Hence, by adjusting ${\delta }_x\in \left[0,max{\delta }_x\right]$, we can control the trade-off between bandwidth utilization and jitter.

4.1.4. Hop Latency and Jitter Constraints

The previous constraints focus on single-node scenarios. Next, we consider the constraints when the flows are transmitted from one node to its adjacent node. To make sure the scheduling can succeed, the difference between the corresponding segment should be larger than the possible maximal hop delay so that the switch can successfully finish the switching operation. Because the time synchronization based on 802.1 Qas still introduces the synchronization time jitter ${\delta }_{syn}$, we add this value to tolerate the possible fluctuation.

$$\begin{array}{cc}\hfill & \forall F_x^{N_a▷N_b}\in {\Gamma }^{N_a▷N_b},\forall 1\le i\le m_x,\hfill \\ \hfill & \forall 〈v_r,v_s〉,〈v_s,v_t〉\in N_a▷N_b\hfill \\ \hfill & \forall \mu \in \left[1\dots Hy{p}_x\right]:\hfill \\ \hfill & f_{x_i}^{〈v_s,v_t〉}.{\varphi }_{\mu }-f_{x_i}^{〈v_r,v_s〉}.{\varphi }_{\mu }\ge maxhopdelay+{\delta }_{syn}\hfill \end{array}$$

(10)

These constraints are for flow schedulable of the flow set on path $N_a▷N_b$. The number of constraint inequalities is about ${\sum }_{\left|\Gamma \right|}(\left|N_a▷N_b\right|-1)m_x\ast Hy{p}_x$.

4.1.5. End-to-End Latency and Jitter Constraints

At the level of the task, it has a latency requirement. The tik starts with sending the first bit and the tok ends with receiving the last bit. The whole time to finish flow in each period, $L_{\mu }$, should be less than the end-to-end latency $L_x^{N_a▷N_b}$. Meanwhile, the end-to-end jitter should also keep at a proper value. Unlike the local jitter control, it is hard to find a reference, so we bound the difference between maximal and minimal latency by a ${\Delta }_x^{N_a▷N_b}$.

$$\begin{array}{cc}\hfill & \forall F_x^{N_a▷N_b}\in {\Gamma }^{N_a▷N_b},\forall 1\le i\le m_x,\hfill \\ \hfill & \forall \mu \in \left[1\dots Hy{p}_x\right]:\hfill \\ \hfill & L_{\mu }=f_{x_{mx}}^{〈\dots ,N_b〉}.{\varphi }_{\mu }+r_x-f_{x_1}^{〈N_a,\dots 〉}.{\varphi }_{\mu }\le L_x^{N_a▷N_b}\hfill \\ \hfill & max{L}_{\mu }-min{L}_{\mu }\le {\Delta }_x^{N_a▷N_b}\hfill \end{array}$$

(11)

The number of constraint inequalities is about ${\sum }_{\left|\Gamma \right|}2\ast m_x\ast Hy{p}_x$.

4.2. Inter Flow Constraint

Besides the intra flow constraints, the several co-existing flows in the same node might contend the same output link. When these flows interleave together, we need the following constraints to minimize the influence of each other.

4.2.1. Contention Free Constraint

Unlike the previous literature [18,21,22], we only handle the overlapping parts from different flows in its hyperperiod. It can effectively minimize the number of constraints.

$$\begin{array}{cc}\hfill & \forall F_x,F_y\in \Gamma ,\forall 1\le i\le m_x,\forall 1\le j\le m_y\hfill \\ \hfill & \forall \mu \in \left[1\dots Hy{p}_x\right],\forall \nu \in \left[1\dots Hy{p}_y\right]\hfill \\ \hfill & \forall ((\mu +1)\ast P_x\ge \nu \ast P_y)\wedge (\mu \ast P_x\le (\nu +1)\ast P_y):\hfill \\ \hfill & f_{x_i}.{\varphi }_{\mu }\ge f_{y_j}.{\varphi }_{\nu }+{\ell }_y\vee f_{x_i}.{\varphi }_{\mu }+{\ell }_x\le f_{y_j}.{\varphi }_{\nu }\hfill \\ \hfill & f_{x_i}.{\varphi }_{\mu }\ge f_{y_{m_y}}.{\varphi }_{\nu }+r_y\vee f_{x_{m_x}}.{\varphi }_{\mu }+r_x\le f_{y_j}.{\varphi }_{\nu }\hfill \end{array}$$

(12)

The number of constraint inequalities is about ${\left|\Gamma \right|}^2\ast m_x\ast m_y\ast Hyp\ast \frac{Hy{p}_y}{P_y}$ or ${\left|\Gamma \right|}^2\ast m_x\ast m_y\ast Hyp\ast \frac{Hy{p}_x}{P_x}$. Similarly, harmonious periodic flows can reduce the constraints.

4.2.2. Link Bandwidth Constraint

If multiple flows share the same link, the whole bandwidth consumption has its boundary. According to Corollary 1, the sum of the occupied ratio of all the flows should satisfy the bandwidth constraint on every link.

$$\begin{array}{cc}\hfill & \forall N_a▷N_b\in \mathcal{P}:\hfill \\ \hfill & \forall 〈v_r,v_s〉\in N_a▷N_b,\forall F_x\in {\Gamma }^{〈v_r,v_s〉}:\hfill \\ \hfill & \sum _{x=1}\frac{C_x}{P_x}\le 1\hfill \end{array}$$

(13)

The number of constraint inequalities is about ${\sum }_{\left|\mathcal{P}\right|}\left|N_a▷N_b\right|$.

4.3. Task Constraint

4.3.1. Computing Capability Contraint

All the tasks should satisfy the computing capability constraint. Let U denote the utilization function; then, we have

$$\begin{array}{cc}\hfill & \forall N_i\in \mathit{N},\forall T_i\in N_i.\mathcal{T}:\sum U\left(T_i\right)<1\hfill \end{array}$$

(14)

Task scheduling has many mature solutions, to which we will not go into much detail here. The number of constraint inequalities is about $\left|\mathit{N}\right|$.

4.3.2. Task Contention Free Constraint

In one node, the task scheduling should avoid contention like the interflow contention free.

$$\begin{array}{cc}\hfill & \forall N_i\in \mathit{N},\forall T_i,T_j\in N_i.\mathcal{T},i\ne j:\hfill \\ \hfill & T_i.\varphi +T_i.C\le T_j.\varphi \vee T_j.\varphi +T_j.C\le T_i.\varphi \hfill \end{array}$$

(15)

4.3.3. End-to-End Task Delay Constraint

To guarantee deterministic holistic scheduling, end-to-end scheduling is critical. Except for the contention of the computing resource, it is important to align the task with the flow in a timeline. The tasks that need end-to-end scheduling should satisfy the end-to-end delay and jitter requirements.

$$\begin{array}{cc}\hfill & \forall N_a▷N_b\in \mathcal{P},\forall T_i\in N_a.\mathcal{T},\hfill \\ \hfill & g^{-1}\left(F_i\right).\varphi +g^{-1}\left(F_i\right).C-T_i.\varphi <maxDelay\left(T_i\right)\hfill \\ \hfill & F_i.\varphi \ge T_i.\varphi +T_i.C\hfill \\ \hfill & g^{-1}\left(F_i\right).\varphi \ge F_i.\varphi +F_i.C\hfill \end{array}$$

(16)

The constraints indicate that task $T_i$ must finish execution before it releases the flow $F_i$ in the sender. Meanwhile, the receiver should start executing the task after the transmission of $F_i$ is finished. The number of constraint inequalities is about ${\sum }_{\left|\mathcal{P}\right|}3\ast \left|N_a.\mathcal{T}\right|$.

5. Independently Programmable Flow Subset

As our model is end-to-end scheduling and some flows are split into subsegments, the set of flows on one link will change when transmitted from one hop to the next hop. Some sets of flows are separated because they are switched into different ports, and some are converged from different ports into the same port. It is not practical to plan all the flows in the entire network for all the cases; we propose independent programmable flow subsets to minimize the number of variables in each independent scheduling.

Definition 7 (Independent programmable flow (IPF) subset). 

The minimal flow set that can independently make flow segmentation.

Consider the abstract graph of Figure 1.

Table 2. The flows on the directed link.

Link	Flows	Link	Flows
$N_1\to S_1$	$F_1^{12}$, $F_1^{13}$,$F_2^{13}$	$S_1\to S_2$	$F_1^{12}$
$S_2\to N_2$	$F_1^{12}$, $F_1^{32}$	$S_1\to S_3$	$F_1^{13}$, $F_2^{13}$
$S_3\to S_4$	$F_1^{13}$, $F_2^{13}$	$S_4\to N_3$	$F_1^{13}$, $F_2^{13}$, $F_1^{23}$
$N_2\to S_2$	$F_1^{21},F_1^{23}$	$S_2\to S_1$	$F_1^{21}$
$S_1\to N_1$	$F_1^{21}$, $F_1^{31}$	$S_2\to S_4$	$F_1^{23}$
$S_4\to S_2$	$F_1^{32}$	$S_4\to S_3$	$F_1^{31}$
$S_3\to S_1$	$F_1^{31}$	$N_3\to S_4$	$F_1^{31},F_1^{32}$

presents all the flows in the same direction sharing the same output port and link. The transmission paths and their related flows are presented in

Table 3. The flow sets on all the paths.

Path	Path Sequence	Flow Set	IPF Subset
$N_1▷N_2$	$〈N_1,S_1,S_2,N_2〉$	$F_1^{12}$, $F_1^{13}$,$F_2^{13}$, $F_1^{32}$	${\Gamma }_1$
$N_1▷N_3$	$〈N_1,S_1,S_3,S_4,N_3〉$	$F_1^{12}$, $F_1^{13}$,$F_2^{13}$, $F_1^{23}$	${\Gamma }_1$
$N_2▷N_1$	$〈N_2,S_2,S_1,N_1〉$	$F_1^{21},F_1^{23},F_1^{31}$	${\Gamma }_2$
$N_2▷N_3$	$〈N_2,S_2,S_4,N_3〉$	$F_1^{21},F_1^{23}$, $F_1^{13}$, $F_2^{13}$	${\Gamma }_1$
$N_3▷N_2$	$〈N_3,S_4,S_2,N_2〉$	$F_1^{31},F_1^{32},F_1^{12}$	${\Gamma }_3$
$N_3▷N_1$	$〈N_3,S_4,S_3,S_1,N_1〉$	$F_1^{31},F_1^{32}$, $F_1^{21}$	${\Gamma }_3$

. Take $N_1▷N_2$ as an example; link $N_1\to S_1$ has $F_1^{12}$, $F_1^{13}$, $F_2^{13}$, $S_1\to S2$ has $F_1^{12}$, and $S_2\to N_2$ has $F_1^{12}$, $F_1^{32}$. Assume the output port of the source nodes are the start-point where flows might be split into segments. All the flows should be considered in advance so that there is enough space to be allocated for all the flows. Hence, $N_1▷N_2$ needs to consider the cover set of the flows on all its links, namely flow set $\left\{F_1^{12},F_1^{13},F_2^{13},F_1^{32}\right\}$. Meanwhile, $N_1▷N_3$ needs to consider flow set $\left\{F_1^{12},F_1^{13},F_2^{13},F_1^{23}\right\}$. Then, we find $N_1▷N_2$ and $N_1▷N_3$ are connected because of $F_1^{12},F_1^{13},F_2^{13}$. Flows $F_1^{23}$ and $F_1^{32}$ are both needed to be considered by $N_1$. In this way, all the paths are connected by the intersecting flows, and then all the flows should be considered together. In this example, the IPF subset includes all the flows in the topology. The example shows that there are still relationships, even if some flows have completely different paths.

Generally, the connections built up by the intersecting flows are universal in such a multiple-node system, even if the flows are not split. One extreme case is that when all the flows have different prime periods the whole connected flows must be considered entirely to allocate the resource. Fortunately, the practical network usually adopts harmonic periods and constructs disjoint and redundancy paths, such as IEC 61508. The harmonic period means a small hyper-period and the flow set on one disjoint path can be treated as the IPF subset. Furthermore, the same period flows might cut off the connections when they have a similar size. For example, if flows $F_1^{23}$ and $F_1^{32}$ have the same period and similar size, namely the estimated number of segment for each flow, $m_1^{12},m_1^{13}$, and $m_2^{13}$ have no change and $m_1^{23}=m_1^{32}$, then flow set $\left\{F_1^{12},F_1^{13},F_2^{13},F_1^{23}\right\}$ or $\left\{F_1^{12},F_1^{13},F_2^{13},F_1^{32}\right\}$ can be considered independently. Therefore, we propose the following algorithm to find the IPF set.

The goal of Algorithm 2 is to find the maximum number of period flows that can be independently programmed. From line 1 to 10, it records all the flows that will be transmitted on each link after initializing the flow–link matrix with false. Then, we unite all the flows on each link on a certain path from line 11 to 15. In this step, there would be real flow on the corresponding link. After scanning all the paths from line 16 to 23, we can obtain all the possible IPF subsets. Finally, we can compare all the possible IPF and categorize them into different IPF subsets ${\Gamma }_1,{\Gamma }_2,\dots$ from line 24 to 26.

Algorithm 2 Independent programmable flow subset

Require : Path set $\mathcal{P}$, flow set $\Gamma$ Ensure : IPF subsets ${\Gamma }_1,{\Gamma }_2,\dots$ 1: Flow-Link matrix M←$False$ 2: Dict ←∅, srcDict ←∅ 3: for f in $\Gamma$ do 4:    for $link$ in $path\left(f\right)$ do 5:      if link is the starting link of flow f then 6:         $srcDict\left[link\right].append\left(f\right)$ 7:      end if 8:      $Dict\left[link\right].append\left(f\right)$, $M\left[Link\right]\left[f\right]=True$ 9:    end for 10: end for 11: for $pathID$ in $\mathcal{P}$ do 12:    for $link$ in path $\mathcal{P}\left[pathID\right]$ do 13:      $PFdict\left[pathID\right]\leftarrow \bigcup Dict\left[link\right]$ 14:    end for 15: end for 16: for $pI{D}_i$ in $\mathcal{P}$ do 17:    for $pI{D}_j$ in $\mathcal{P}$ and $pI{D}_j>pI{D}_i$ do 18:      if PFdict[$pI{D}_i$] ⋂ PFdict[$pI{D}_j$]) is no empty then 19:         $PFdict\left[pI{D}_i\right]\leftarrow \bigcup PFdict\left[pI{D}_j\right]$ 20:         $PFdict\left[pI{D}_j\right]\leftarrow PFdict\left[pI{D}_i\right]$ 21:      end if 22:    end for 23: end for 24: for $pI{D}_i$ in $\mathcal{P}$ do 25:    catalog the $PFdict\left[pI{D}_j\right]$ in the n IPF subsets, and each denoted by ${\Gamma }_i$, $i=1,2,...,n$ 26: end for

After identifying IPS, we use a segment estimation algorithm to compute the parameters of the flow or split-flow and then construct the constraint models based on formulations in Section 4. We can obtain the offsets of all the flows and tasks. If there is no split, each task has a list of offsets within its own hyper-period on the sender side, and the corresponding flow has delayed offsets in each TSN node. Because different flows may converge on a node and one of the flow’s offset plus its duration equals to other’s offset, we need to merge the offsets to find the start-time and end-time of the last GCL. If the flow is split, each task still keep one sending offset per period hyper-period, while the corresponding flow will be cut into several sub-flows and each sub-flow has its own offset. The sub-flows will be treated as normal flow to participate in the final merger into GCL.

6. Experiment and Evaluation

6.1. Experiment Setup

Based on the previous analysis, we implemented a simulation for a schedule, where we formulated the first-order logical constraint using the SMT model and solved by Z3 [23] v4.8.8-64bit, which runs on an Intel(R) Core(TM) i7-8700 64bit CPU @ 3.20 GHZ with 16 GB of RAM.

Assume the network bandwidth is 1 Gbps, and the minimum and maximum frame sizes are 84 and 1542 bytes according to IEEE 802.1 Q. The transmission time is 0.672 μs and 12.336 μs, respectively. Meanwhile, 84 bytes can also be treated as the shortest preempted frame according to IEEE 802.1 Qbu. For the IFS (inter-frame space) and the convenience of calculation, we round the two values as 1 unit and $⌈\frac{1542}{84}⌉\approx 20$ unit, where 1 unit ≈ 0.672 μs. We classify all the flows into three types.

• Ant flow, one frame per period, when transmission time varies within the range $\left[1,20\right]$;
• Mice flow, up to 10∼100 MTU frames per period, when transmission time varies within the range $\left[21,200\right]$
• Elephant flow, more than 100 MTU frames per period, when transmission time varies within the range in $\left[201,X\right]$, where X is its maximum period.

Each type has a matching period. In TTE and Flexray, the size of macrotick is about 60 μs to 1 ms, and the frame size is about 500 Bytes. So we refer to macrotick and set the period boundary for ant flows as $P{B}_{ant}=\left[50,1000\right]$, which is a finer time precision than that of TTE and Flexray. Then, we set $P{B}_{mice}=$ [1001, 10,000], $P{B}_{elephant}=$ [10,001, 50,000]. Here, taking $X=$ 50,000 unit ≈ 33 ms as the supper boundary for elephant flow is based on the requirement of 720P-30FPS (720P video at 30 FPS (frames per second) without compression, which needs about 2.8 MB per 30 ms to be transmitted, close to 1850 MTU frames per 33 ms).

Since there is a total of eight queues per port, we assume one queue for deadline-constrained aperiodic flows, one for BE flows, and two queues for 802.1 QCF. Four queues can be used for periodic flows. More radically, we map one period to one queue and one flow per period. The above constraints indicate that hyper-period takes a major proportion of the number of constraint inequalities, so we take the harmony period in the experiment.

6.2. Offset Computation Evaluation

Firstly, we consider the offset computation evaluation, where different groups of multiple periodic flows are depicted in

Table 4. Flow parameters.

Flow Type	Flow Size	Period
Ant Flow	10	50, 100, 1000
Mice Flow	50, 100, 200	2000, 5000, 10,000
Elephant Flow	500, 1000, 5000, 10,000, 20,000, 40,000	20,000, 50,000

.

For any flow, we only take one value for flow size due to its small range of variation, while we take three periods because the change has an impact on the available interval and then on the number of segments for elephant flow. For mice flow, we take three kinds of periods and three kinds of flow sizes. For elephant flow, six kinds of flow sizes are taken for the large range of variation and we only take two kinds of period which will be used by matching the flow size. We need to choose four flows to verify that flow-level programming has less constraint in contrast to frame-level programming. If there are too many combinations to experiment, we adopt a partial-flit way to observe the change in the number of segments in

Table 5. Partial-flit to observe the change in the number of segments vs. the number of frames.

Name	Flow Set (Flow Size, Period)	Number of Segment	Frame	Utilization
${\Gamma }_1$	(10, 50), (50, 2000), (50, 5000), (500, 20,000)	20	32	0.26
${\Gamma }_2$	(10, 50), (50, 2000), (50, 5000), (1000, 20,000)	34	57	0.285
${\Gamma }_3$	(10, 50), (100, 2000), (100, 5000), (1000, 20,000)	40	61	0.32
${\Gamma }_4$	(10, 50), (200, 2000), (200, 5000), (1000, 20,000)	50	71	0.39
${\Gamma }_5$	(10, 50), (200, 5000), (200, 10,000), (1000, 20,000)	45	71	0.31
${\Gamma }_6$	(10, 50), (200, 5000), (200, 10,000), (5000, 20,000)	224	271	0.51
${\Gamma }_7$	(10, 100), (200, 5000), (200, 10,000), (5000, 20,000)	96	271	0.41
${\Gamma }_8$	(10, 100), (200, 5000), (200, 10,000), (10,000, 20,000)	209	521	0.66
${\Gamma }_9$	(10, 1000), (200, 5000), (200, 10,000), (10,000, 20,000)	23	521	0.57
${\Gamma }_{10}$	(10, 1000), (200, 10,000), (10,000, 20,000), (20,000, 50,000)	72	2511	0.93

.

For example, there are only one or two flows incrementally changed from ${\Gamma }_i$ to ${\Gamma }_{i+1}$. As can be seen from the table, the number of frames keeps increasing with the growth of flow size and utilization, while flow-level strategy can reduce the number of scheduling variables, which means it can largely shorten the synthesis time. One direct programming result of ${\Gamma }_{10}$ is illustrated in Figure 5. In Figure 5a, only the boundary and contention-free constraints are used, we can see the large flow has been split into many segments and major of them are larger than a single frame. Based on the two kinds of constraints, Figure 5b depicted the effect when the intra-flow jitter constraint is imported. The jitter of queue1 and queue2 has improved.

After the problem of multiple flows in single-port has been solved, we try to consider the end-to-end scheduling problem. Here, we consider the model in Figure 1; there are six tasks whose periods are chosen based on Table 4 and make sure they have chosen different periods. Then, every task randomly chooses the flow size related to its period. The six flows are treated as their generated task. The task shares the same period as its flow, while their WCET is set as a random value between 1 and 50. The hop-delay of switches is determined by their flow size, if the flow size is less than MTU, then the maximum hop delay is the flow size; otherwise, the value of MTU is 20. After this setting, we can build a first-order constraint to reach end-to-end schedulability. Our goal is to minimize the end-to-end delay. Firstly, at some time, all the periodic flow will be put together to obtain the way to split. Then, each segment needs to satisfy hop-to-hop constraints. We evaluate the synthesis time of the following task set.

Compared to frame-based scheduling, Figure 6 represents the number of variables needed to construct the constraint solution, and Figure 7 shows the preliminary synthesis time of the task set in Table 5. Since tasks and flows can be treated as the same coarse-grained entity, the mapping relationship from tasks to flows or segments is easy to express, especially for tasks that require large traffic. Therefore, it is easy to handle the temporal logic between the network and tasks in the holistic schedulable scenario, resulting in a significant drop in synthesis time. The time series Gantt chart in Figure 8 shows all the scheduled time for all the tasks, flows or sub-flows that can be tracked in each link. As can be seen from the figure, large flows can be elegantly split and separated without harming smaller flows.

6.3. Various Topology with Multiple Periods

To verify the generality of the model, we constructed four representative network topologies and task models for experiments, and focused on the schedulability of the model in the experiments in Figure 9. Due to excessive SMT constraints, we can only obtain the offset time of flows or tasks when there are feasible solutions. In this model, single-node scheduling pursues utilization by splitting large flows, but due to changes in topology, we need to solve an IPF, which reduces the overall solution space. Figure 10 compares the feasible solutions obtained after approximately 20 rounds, and due to the existence of IPF, there is a real and virtual traffic occupancy on each link. Due to the differences in period and path, in order to ensure constraints such as end-to-end, the virtual flow can be interpreted as the interval time that must exist when the flow is scheduled on different links. During the actual trial period, the space occupied by these virtual traffic can be allocated to BE traffic. As can be seen from Figure 10a–d, as the network becomes increasingly complex, its true bandwidth utilization also decreases to some extent. This is due to the fact that the use of IPF results in a sharp decrease in the solution space due to the correlation between links and flows. This is also some of the shortcomings of the model, which we will optimize in our future work

7. Related Work

Steiner [19] defined SMT-base evaluation for TTE in multihop networks. It focused on building one-frame-per-period constraints and precisely formulating the scheduling problem. Many of the constraints provide a good reference for us to build our work. As mentioned in the previous section, it can be our special case when we only consider the network part. After that, Oliver et al. [2,24] and considered building a similar constraint by obeying the standard itself of IEEE 802.1 Qbv. It extends a single frame in TTE to multiple frames and the scale of the problem grows extremely, making it hard to resolve. Meanwhile, they also combined the task and network based on TTE [13] to make a schedule, and they pointed out that the number of frames is the biggest bottleneck to expanding the scale. Furthermore, when considering the coordination between routing and scheduling [25], the problem becomes complex and difficult to solve due to the sharp increase in the number of variables. Our flow-level scheduling might be an option to break the bottleneck for it can reduce the number of variables for these models. Ref. [18] adopted the first-order theory of arrays to express constraints and exposed synthesis of schedules via an SMT solver. It assumes the message size of one Ethernet frame and constructs time windows for GCLs based on IEEE 802.1 Qbv. In this model, the scale of the whole synthesis is still limited to 1000 frames of magnitude; the experiment shows that it takes 40 h to synthesize 264 frames with 32 windows. It is unacceptable in our megabytes per period scenarios. TSNsched [26] is a tool for generating TSN schedulers. They consider the flow fragment in their constraint and claim TSNshed can support both individual packets and time windows; however, how to generate such fragment is still unknown. In their experiment, the flow size is limited to five frames and there is no evaluation of utilization. Concerning these works, we discuss the method of generating segments, called fragments in [26] and the time window in [18]. Even though time windows have been introduced into industrial applications [27], the mapping problem from the frame to the window still exists. We think our work can make up the gap between frame and flow.

8. Conclusions

The conventional approach, inspired by the Internet, is to decouple task and network scheduling, while TSN strives to provide deterministic data streams and the computing nodes adjust their processing logic based on the parameters that the network can provide.

In this paper, we propose a joint programming method for real-time task and network scheduling. By considering periodic task execution and end-to-end network transmission together, we construct first-order constraints for an SMT (satisfy module theory) problem. Unlike related work, our method can achieve near 100% bandwidth utilization on a single TSN node. Moreover, it can reduce the number of constraints based on flow-level scheduling. FDS differs from the existing task and joint scheduling strategies in that it can elevate the scheduling granularity of TSN data transmission from the frame level to the flow level, which can establish a one-to-one correspondence between the time control granularity at the task level and the granularity of network transmission, and has potential cross-layer transmission capabilities.