CSQF-based Time-Sensitive Flow Scheduling in Long-distance Industrial IoT Networks

CSQF only specifies an underlying packet scheduling mechanism on the data plane, which brings a significant problem of network-wide traffic planning to the control plane. To be more specific, how to construct the CSQF mathematical model and how to implement the SID calculation need to be solved. Next, We refer to the CQF in the range of local area to analyze the key points, i.e., link delays and cycle mapping relationships between adjacent nodes, in the process of modeling CSQF.

The features of local area include[13]: (1) The network diameter is restricted to a small scale, such as seven hops. (2) The time on switches can be strictly synchronized. (3) The propagation latency can be ignored. Based on these features, CQF supposes that the cycle length exceeds the summation of transmission latency, link latency, processing latency, and queueing latency. As detailed in Fig. 2(a), the CQF-enabled switch has two queues, and each queue’s behavior is controlled by the receive (Rx) and transmit (Tx) gates. Determined by the gate control list (GCL), the two queues conduct enqueue and dequeue actions alternately. Thus, in a single cycle of $T$, the packet can be sent from the upstream device and received by the downstream device, then forwarded to the next-hop device in the subsequent cycle. As depicted in Fig. 2(b), if the packet is the last issued and first arrived, the minimum latency is $(H-1)\times T$, where $H$ is the number of hops. In contrast, a packet takes the maximum delay of $(H+1)\times T$ when it is the first sent and last received.

However, in wide-area networks, accurate time synchronization[20] is not easy to obtain and the varied propagation latency cannot be regarded as zero. Hence, it is not trivial to fix the per-hop latency to a certain cycle time $T$. To address these challenges, CSQF relaxes the synchronized time to the frequency[21], i.e., all switches maintain the same clock frequency but do not require the same initial phase, which introduces the initial phase deviation between devices. Then, CSQF enlarges the two queues of CQF to multiple queues, where one queue is for transmitting packets and the others for receiving packets. Fig. 2(c) depicts an instance of three-queues CSQF. Each queue corresponds to a cycle, and the queues dequeue packets in a periodic pattern. More than one receiving queues are utilized to absorb a certain amount of traffic bursts, but the mapping relationship between link delays and cyclic queuing behavior is still undefined.

Based on the above analysis, we propose the cycle tags planning (CTP), an integer programming model for the CSQF. First, we argue that switches can be aware of the initial phase deviation and update it to the controller. The cycle mapping pattern still holds if we consider the phase deviation is 0 [14]. Thus, for simplicity but without loss of generality, CTP assumes an initial phase deviation of 0 in the control plane as the basis of the scheduling model. Second, our CTP model decouples link delays from the cycle time $T$ to hold a constant queue rotation duration. Specifically, the irregular link delay is divided by the cycle time and rounded up. Third, to unify the link delay and cyclic queuing behavior, we model the underlying network resources as time-discrete queue resource blocks. An auxiliary variable named arriving cycle is utilized to map the arriving time of packets to an appropriate receiving queue, which ensures aligned adjacent cycles. More details of CTP model are in Section IV.

Another key challenge for CSQF is how to compute the cycle tags for each flow under the CTP model. Since multiple flows will compete for the queue resources of each output port along the path, an efficient scheduling algorithm is needed to not only maximize the number of flows that meet the deadline, but also avoid breaking the maximum queue length constraints. In addition, for different network scenarios, how to set appropriate configuration parameters (such as the queue number and the cycle size) also needs to be investigated.

Specifically, there are two typical traffic access situations in real deployment scenarios: access-aware[17][22], and access-unaware. Access-aware means that access network devices are gateways that can negotiate with terminal hosts and control when traffic will enter the CSQF-enabled network domain. Unawareness of the access indicates that the flow’s arrival time of the first hop is uncontrollable. Thus, to make the cycle tags computation adapt to practical deployments, we propose two intuitive flow scheduling methods. One is to set the flow offset at the first hop (i.e., access-aware), and the other is to control the cycle shift at each receiving queue (i.e., access-unaware).

To make it clear, we design a simple access-aware scenario where the maximum queue capacity is limited to three packets. As shown in Fig. 3, Node A functions as the access gateway device, and there’s a time-sensitive flow ($f_{1}$) directed towards the downstream node, Node B. It is not allowed to enqueue the receiving queue $Q_{6}$, because $Q_{6}$ is already at full capacity. One method, as demonstrated in Fig. 4(a), is to change the flow offset. By delaying the sending start time of flow $f_{1}$ at Node A by one cycle, the overflow at queue $Q_{6}$ can be circumvented. An alternative strategy involves adjusting the cycle shift, as seen in Fig. 4(b). Here, the flow $f_{1}$ is deferred to enqueue the queue $Q_{5}$. Consequently, both methods ensure that the flow $f_{1}$ is successfully scheduled and transmitted out during Cycle 3. The difference is that the flow offset operation can search over the entire sending period time series, while the cycle shift operation is limited to available queue numbers. Note that Node A can execute both flow offset and cycle shift operations if it is access-aware, but can only execute the cycle shift operation if it is access-unaware. Moreover, if there is no available queue for choosing (e.g., all queues are full), the flow $f_{1}$ will fail to be scheduled. In this case, the flow needs to wait until some resources occupied by other flows are released, or the underlying network resources need to be expanded.

Inspired by the aforementioned exploration, our objective is to devise a heuristic flow scheduling algorithm called flow offset and cycle shift (FO-CS) that possesses the following characteristics:

Predictable performance: The algorithms should adhere to the constraints of bounded queue length and ensure time-sensitive flows reach their destination within the stipulated deadline and jitter.

High scalability: Our approach ought to exhibit high scalability, scheduling thousands of time-sensitive flows across long-distance industrial IoT networks.

Feasible execution time: Employing heuristic methods, our scheme aims for a practical algorithm execution time.

The FO-CS algorithm are elaborated in Section V.

We denote sets using calligraphic letters (e.g., $\mathcal{V,E,F}$) and vectors with bold letters. The physical network topology is conceptualized as a graph $\mathcal{G}=\left\{\mathcal{V},\mathcal{E}\right\}$, where $\mathcal{V}$ represents vertices, encompassing switches $\mathcal{S}$ and hosts $\mathcal{H}$. $\mathcal{E}$ symbolizes tuples indicative of network links, defined as $\mathcal{E}=\left\{(v_{i},v_{j})\mid v_{i},v_{j}\in\mathcal{V},i\neq j\right\}$, signifying a link exists between $v_{i}$ and $v_{j}$. Additionally, every edge possesses a link delay attribute of $LD$.

A loop-free path $p$ comprised of edges $e_{k}$ is depicted in (4). Here, $e_{1}$ signifies the edge associated with the output port of the first switch (hop) of the path, while $e_{j}$ is associated with the last switch:

A periodic TS flow is characterized as a single unicast traffic from a source node to a destination node. The collection of periodic TS flows is denoted as $\mathcal{F}=\left\{f_{i}\right\},i=\left\{0,...,n-1\right\}$. The flow feature of each flow $f_{i}$ is defined as

The transmission time of each output interface is segmented into a series of equal time intervals, each lasting a duration of $T_{cycle}$, commonly referred to as a cycle. Each cycle corresponds to a queue. Thus, each output port consists of a sequence of cycle-related queue resource blocks that can be defined as $Q_{E_{(e_{k})}}^{T_{(t)}}$, and the superscript of $T_{(t)}$ is a variable that denotes the specific location of the cycle in the sequence. Specifically, $t\in\left\{0,1,...,\beta-1\right\}$, and $T_{(1)}$ denotes the Cycle 1 as exhibited in Fig. 6. The parameters related to the graph and flow, which are used in the CTP problem formulation, are presented in Table II.

As illustrated in Fig. 5, the buffer allocated for TS traffic is partitioned into $N$ TS-queues. Of these, one queue is designated for transmission while the other $N-1$ queues are for receiving. The buffer is used to store the packet data, while the metadata of packets is stored in the queue. Each of the TS-queues is assigned the topmost priority level of seven. As per the CSQF mechanism, the queue for transmission is chosen cyclically. In addition, the queue capacity $L$ is constrained and correlates with the size of $T_{cycle}$. A flow must determine the appropriate receiving TS-queue for enqueueing, upon arrival at an interface (edge). The variable $\Delta_{(f_{i},e_{k})}$ represents the distance between the chosen receiving queue and the transmitting queue, measured by cycle shift operations at the associated edge $e_{k}$. Typically, the $\Delta$ is an integer value that ranges from $0$ to $N-2$.

Fig. 6 presents an illustration of the CTP model from a comprehensive flow perspective. Flow $f_{1}$ initiates transmission at the first hop, specifically edge $e_{1}$, during the flow offset of Cycle 0. Following a link latency equivalent to nearly two cycles, $f_{1}$ arrives at the edge $e_{2}$ in the Cycle 2. Then, it enqueues the second receiving queue, thus the value of $\Delta(f_{1},e_{2})$ is one cycle and $f_{1}$ will be transmitted at the edge $e_{2}$ in the Cycle 3. After that, it is received at the edge $e_{3}$ with $\Delta(f_{1},e_{3})$ of zero and transmitted in the Cycle 5. In its entirety, $f_{1}$ traverses through the path $\left\langle e_{1},e_{2},e_{3}\right\rangle$ adhering to the designated cycle tags $\left\langle 0,3,5\right\rangle$.

Integer programming is a widely recognized mathematical method used to model network scheduling problems. The following are the inputs and decision variables.

1) Integer Programming Inputs:

$\bullet$ Physical topology graph $\mathcal{G}=\left\{\mathcal{V},\mathcal{E}\right\}$.

$\bullet$ A collection of periodic time sensitive flows $\mathcal{F}$.

$\bullet$ Queue length $L$, queue number $N$, cycle size $T_{cycle}$.

2) Decision Variables:

$\bullet$ Flow offset, $\left\{\Omega_{i}\mid\Omega_{i}\in\Omega\right\}$.

$\bullet$ Cycle shift, $\left\{\Delta_{(f_{i},e_{k})}\mid f_{i}\in F,e_{k}\in p_{i}\right\}$.

1) Hyper-cycle Constraint: Various flows have different sending periods. A hyper-cycle is used to determine the time series bounds for the scheduling solution. As shown in (6), the hyper-cycle is defined as the least common multiple of all flows’ sending periods ($\mathcal{SP}$). Thus, the sending pattern repeats from the global perspective, and we only need to make the flow satisfy the scheduling constraints in one hyper-cycle. The hyper-cycle is a widely-used term in real-time system fields[13][24]. In the same vein, this paper focuses on scheduling periodic TS flows, where the sending period is considered as an integer within a reasonable range to comply with industrial tasks. The sporadic flows can be delivered with other QoS methods, such as asynchronous traffic shaping and frame preemption. Moreover, in specific industrial scenarios, such as 5G TSCAI[25], IEC 60802[26], and DetNet use cases[19], it is possible to register all types of devices and the periods of flows in advance. Consequently, the hyper-cycle can be established as the greatest value of the least common multiple derived from the flow periods of all known devices.

2) Cycle Constraint: In this study, we define the granularity of scheduling by the cycle time. This mandates that every sending period must be divisible by the cycle time. Consequently, the upper bound of $T_{cycle}$ aligns with the greatest common divisor of the sending periods of all flows, as depicted in (7). On the other hand, the lower bound of $T_{cycle}$ must ensure that during its duration, all packets stored in a queue are dispatched. This duration encompasses the cumulative value of the processing latency $\delta_{p}$, maximum queuing latency $\delta_{q}$, and transmission latency $\delta_{m}$, , as represented in (8).

In (8), $Bw$ is the link capacity, $MTU$ is the maximum transmission unit of packet size, and $L$ is the maximum queue length. Typically, the value of $T_{cycle}$ is chosen to be greater than its minimum, and $Hyper_{cycle}$ is divisible by $T_{cycle}$. Then, $\beta$ is utilized to denote the total count of $T_{cycle}$ in a $Hyper_{cycle}$ as presented in (9).

3) Offset Constraint: The offset of each flow determines the sending initial cycle at the first switch device ($\Omega_{i}$) linked to the terminal node, which must be less than the defined sending period of the flow, as outlined in (10). In other words, the TS flow should be entirely forwarded within the current sending period to avoid stream interference that may occur during adjacent sending periods.

4) Arriving Cycle Constraint: As defined in (11), $A_{(f_{i},e_{k})}$ denotes the arriving cycle when the flow is arriving at the output port of a node. $t_{A_{(f_{i},e_{k})}}$ is the specific time point that packets may arrive. This constraint is satisfied by default if the cycle size is set to no less than the minimal value of $T_{cycle}$ defined in (8).

and $LD_{(f_{i},0)}=0$ , $\Delta_{(f_{i},0)}=0$.

5) Deadline Constraint: For each flow, all packets need to reach their destination within the designated deadline, i.e.,

6) Flow and Edge-Cycle Mapping Constraint: This constraint gives the mapping relationship between flow $f_{i}$ and queue resource block $Q_{E_{(e_{k})}}^{T_{(t)}}$ at the edge $e_{k}$ and cycle $t$. If a flow $f_{i}$ maps to a $Q_{E_{(e_{k})}}^{T_{(t)}}$ successfully, i.e., the utilization of queue resource block does not exceed the queue length $L$, the value of the auxiliary variable $M\left(f_{i},Q_{E_{(e_{k})}}^{T_{(t)}}\right)$ is 1, as depicted in (13). Otherwise, it is 0.

The actual transmitting cycle at the edge is determined by the sum of the arriving cycle $A_{(f_{i},e_{k})}$ and the cycle shift $\Delta_{(f_{i},e_{k})}$. Given that a flow can be issued from its source multiple times within a $Hyper_{cycle}$, the variable $\lambda$ specifies the sending period to which the flow pertains. Moreover, to ensure that the arriving time of flows does not exceed a $Hyper_{cycle}$, the transmitting cycle is subjected to a modulus operation with $\beta$. In summary, the variable of $t$ encapsulates all the transmitting cycles a flow undergoes along its path within the range of a hyper-cycle.

7) Bounded Queue Length Constraint: As defined in (14), if a flow $f_{i}$ is scheduled along the path successfully, i.e., for all the edges along the path the value $M\left(f_{i},Q_{E_{(e_{k})}}^{T_{(t)}}\right)$ is 1 while the deadline constraint and bounded queue length constraint are satisfied, then the value of $S_{i}$ is 1. We call this kind of flow a schedulable flow. Otherwise, it is 0.

The constraint on bounded queue length necessitates that the cumulative number of packets from all flows in any given queue not surpass the designated queue capacity, i.e.,

In this paper, the optimization objective is to maximize the number of schedulable TS flows, which is described as:

where $\mathbf{\Omega}$ is the variable of flow offsets ( $\mathbf{\Omega}=\left[\Omega_{0},...,\Omega_{n-1}\right]^{T}$), and $\mathbf{\Delta}$ is the variable of cycle shifts of flows ($\mathbf{\ \Delta}=\left[\mathbf{\Delta}_{0},...,\mathbf{\Delta}_{n-1}\right]^{T}$, $\mathbf{\ \Delta}_{i}=\left[\Delta_{i,1},...,\Delta_{i,j}\right]^{T}$).

In this paper, schedulability refers to the number of time-sensitive flows that could be scheduled by the network under constrained network resources and desired quality of service. Many factors such as traffic characteristics, flow sequence, and topology size, may affect scheduling capabilities. One of the most important factors is the configurable parameter of queue length $L$. In (15), it seems that as $L$ becomes larger, the number of packets each queue can hold increases, so the number of schedulable flows $\sum_{i=0}^{n-1}S_{i}$ improves (i.e., $\sum_{i=0}^{n-1}S_{i}\propto L$). Instead, we derive Theorem 1:

We adopt the bounded queue length constraints in (15) instead of frame isolation constraints in (21) for the following reasons. First, unlike LANs, it is hard to obtain fine-grained traffic characteristics (such as packet size or transmission duration) for all Industrial IoT flows in wide-area scheduling. Second, there is inevitable traffic aggregation in wide-area networks that causes queuing. Finally, the execution time of the solution grows exponentially as the queue length gets smaller. Thus, the queue length $L$ should be set to an appropriate value to balance the schedulability and time costs.

The most naive method to calculate the SID information for TS flows is formulating multiple constraints and inputting the flows’ parameters to the integer programming solver. However, this method is memory-intensive and may cost several hours to obtain a premium scheme for long-distance Industrial IoT scenarios. Fundamentally, the scheduling problem parallels the bin packing problem, which is NP-hard[14]. Hence, obtaining the optimal solution within a practical timeframe might be unattainable.

To reduce the complexity and improve the schedulability, we opt for computation-intensive heuristic methods to address this issue. Similar to the idea in [27], we split the CTP problem into a basic flow scheduling problem and an enhanced flow sequencing problem. In incremental online scheduling scenarios, the basic flow scheduling algorithm targets to quickly compute cycle tags for an ordered set of flows. For offline optimization contexts, the enhanced flow sequencing algorithm, which leverages the meta-heuristic Tabu search, focuses on establishing a complete order of the flow set to optimize the count of schedulable flows.

Generally, periodic TS flows account for a relatively small portion of bandwidth (e.g., 7% for scheduled flows in literature[6] and no more than 20% for critical control streams in literature [19]) compared to BE flows. For example, the differential protection traffic is just 64 kbps [4], but requires millisecond-level delay and microsecond-level jitter. Thus, to meet such stringent delay demands, the link delay weighs more than the bandwidth. In this study, we focus on CSQF scheduling and employ a weighted shortest path routing approach based on Dijkstra’s algorithm. The link delay is denoted as the weight of each edge, and the path with the smallest end-to-end weight is selected as the routing path. The time complexity is $O(\left|V\right|\log\left|V\right|+\left|E\right|)$, where $\left|V\right|$ is the number of vertexes and $\left|E\right|$ is the number of edges. Moreover, plenty of works have been done on the realization of routing for time-sensitive networks[9], such as Equal Cost Multi-Pathing (ECMP), Maximum Scheduled Traffic Load (MSTL), and segment routing. A load balancing based on CSQF is presented in [10], which can be applied to reduce the single point of congestion with additional complexity. Routing optimization with heuristic algorithms will be considered as future work.

Based on the insights from Section III.C, our basic scheduling algorithm encompasses the cycle shift (CS), flow offset (FO), and a combined FO-CS algorithm. The FO-CS algorithm integrates elements from both the FO and CS. The FO algorithm operates under the premise that cycle shift operations in network output ports are zero, catering to situations where switches lack more than two queues. Simultaneously, the CS algorithm posits that TS traffic is dispatched with unpredictable initial times (offsets), addressing instances where the access arrival time point is uncontrolled.

The FO-CS algorithm sets both the offset value and cycle shift value to zero, sequencing the flows in a predetermined order, as outlined in Algorithm 1. For each flow $f_{i}$, the initial step determines whether $S(f_{i})$ is 1 according to constraints (12)-(15). If $S(f_{i})$ is 1, $f_{i}$ will be put into $F_{suc}$ (lines 1-6). Subsequently, if the flow is deemed unschedulable, the algorithm identifies the node where the mapping was unsuccessful. It then incrementally adjusts the cycle at that specific node, ensuring it stays within the constraints of the receiving queue’s capacity (lines 9-13). Once a flow $f_{i}$ is scheduled successfully along a route, it will be placed into the $F_{suc}$ set (lines 14-16). Otherwise, the value of flow offset is increased by one and re-operates the cycle shift part considering the constraint of offset(lines 17-18). If the flow still cannot be scheduled after traversing all the flow offset and cycle shift operations, the flow will be placed into $F_{fai}$ (line 19). Finally, the algorithm outputs scheduling parameters of $\Omega_{i}$ and $\mathbf{\Delta}_{i}$ for each scheduled flow $f_{i}$ in schedulable flow set $F_{suc}$. The CS part is preferentially executed because it has a smaller search space and lower time complexity than FO. Note that the worst-case time complexity of this FO-CS algorithm is $O(\sum_{i=0}^{n-1}\frac{SP_{i}}{T_{cycle}}\times N\times H)$, where $n$ is the number of flows, $N$ is the queue number at each output port, and $H$ is the number of hops. The queue number $N$ and the hop number $H$ are bounded in a specific network. Therefore, the worst-case time complexity is $O(\sum_{i=0}^{n-1}\frac{SP_{i}}{T_{cycle}})$ for the FO-CS algorithm.

The FO-CS algorithm is flexible and efficient within the following three aspects. First, the maximum queue length and queue number can be adjusted with the increase of flow number and topology size. Second, the FO algorithm and CS algorithm can be utilized respectively under different scheduling scenarios, such as symmetric and asymmetric topologies. In symmetric topologies, traffic aggregation can be greatly alleviated by first-hop shaping of access switches; thus the flow offset algorithm works well independently and reduces the computational overhead. Third, the FO-CS algorithm quickly generates incremental flow scheduling solutions, which supports online long-distance Industrial IoT traffic transmission.

The enhanced flow sequence algorithm creates a varied scheduling order for the flow set $F$, to maximize the resulting number of schedulable time-sensitive flows computed by the FO-CS algorithm. The maximum number of the search space for the sequencing problem is $n!$, where $n$ is the number of flows. Since the brute force approach cannot be scaled to large problem sizes, it is unacceptable in real-world applications. There are many mete-heuristic algorithms to approximate the optimal solution. Due to the advantage of recording the previously searched solutions, we utilize the Tabu search[27] with a simplified Tabu list as a guided exploration of the solution space. Wide-area deployment often is incapable of knowing all traffic prior. Thus, feasible online solutions are more appropriate than optimal offline solutions. We leave other mete-heuristic offline searching strategy with domain-specific knowledge (DSK) as future work.

As outlined in Algorithm 2, the Tabu FO-CS algorithm generates the initial results using a random order, and defines it as the current result (lines 1-3). Then, the neighborhood of the current order is derived from the exchanging mode[13]. In this mode, a subset of mapped flows in $F_{suc}$ are randomly removed by cleaning the queue resource block associated with these flows. Following this, the flows in $F_{fai}$ are integrated into $F_{suc}$ until no enough network resources can be allocated (lines 5-6). Exchange operations are recorded in (and removed from) the Tabu list to avoid local optima. If the current result is better than the previous best result, it will be marked as the best result and selected as the next solution for the next iteration. To reduce the superfluous search, the termination criteria are set based on two conditions: either the number of iterations surpasses the maximum threshold $K$, or there is no improvement observed in the best result over the past $P$ iterations (line 4). The efficacy of the Tabu FO-CS algorithm can be adjusted by varying the values of $K$ and $P$. While setting larger values for both parameters might lead to superior outcomes, it could significantly prolong the computation time.

All evaluations are conducted on a computing device powered by four Intel i5-8259U CPUs, operating at a base clock speed of 2.3 GHz, and complemented with 16 GB of RAM.

Furthermore, we evaluate the performance of Tabu FO-CS under different topologies, including the linear, the ring, and a part of Internet2. For the termination criteria in Algorithm 2, we set the maximum iterations $K$ to 1000 and the maximum repetitions $P$ to 100. The queue length of 10 and queue number of 4 are adopted for the FO-CS algorithm based on the previous evaluations. Each test is performed five times, and we calculate the average number of schedulable flows and the mean time consumed.