Programmable Cycle-Specified Queue for Long-Distance
Industrial Deterministic Packet Scheduling

Features of industrial time-sensitive traffic: Humans naturally can adapt to the congestion and collapse in the delivery of information, such as waiting for reconnections, retrying upon failures. Thus, network operators strive to reduce the average delays, e.g., round trip time (RTT) and flow completion time (FCT), and tolerate the packet loss and considerable jitter. In contrast, machines execute operations strictly according to timelines. Task-oriented industrial applications require on-time arrival of command packets, e.g., packets $p_{1}$ must arrive before the time of $t_{1}$ and packet $p_{2}$ should arrive between $t_{1}$ and $t_{2}$ in Figure. 1. If packet $p_{2}$ arrives early (i.e., before $t_{1}$), the command contained in packet $p_{1}$ will be invalid. Also, arriving late, out of order, and being dropped are not allowed.

Specifically, time-critical applications send promised periodic/aperiodic traffic and require the bounded delay of milliseconds and jitter of microseconds[2][18]. For example, the Differential Protection traffic[12] is just 64 kbps, but requires the maximum delay of less than 5 ms and the maximum jitter of less than 250 $\upmu$s. The remote control sends packets with sending period of 1-100 ms and packet size of 100-700 bytes, and the requirements are diverse as shown in Appendix A. For instance, the suturing operation in the da Vinci Surgical System[32] issues kinematic packets every 10 ms[8], updating Cartesian positions, orientations, velocities, angular velocities, and gripper angles to ensure real-time synchronized motion of the remote corresponding manipulators.

The impact of network environments on QoC: Literature [33] shows that there is a strong correlation between quality of control (QoC) and end-to-end latency, jitter, and packet drops of network environments. We briefly summarize part of the results in Table 1. In the kinematic-haptic loops, the controller sends the kinematic packets and the actuator feedbacks the haptic information (e.g., vibration, pressure, smooth or rough, and soft or firm), where the QoC metrics could be the step disturbance, quadratic costs, and the rise time of the step response curves. In the kinematic-video loops, the feedback is the real-time video stream, and the QoC metrics could be positional errors and the maximum move speed. For instance, a visible positional error (>1 mm) can result cybersickness (e.g., dry eyes, headaches, dizziness, and nausea) that prevents users from long-term use of cyber-physical systems. It is also worth noting that terminal enhancement (such as delay prediction and trajectory prediction applications based on AI algorithms in cloud games[34]) cannot solve this problem, due to the real industrial physical properties.

Furthermore, we built a TSN interconnection testbed to assess the impact of network parameters on master-slave motor synchronization. The servo motor is controlled by periodic pulse signals sent by the programmable logic controller (PLC). Each pulse drives the servo motor to rotate to a specific position with a default speed. Once a signal is disturbed or lost, the servo motor will automatically decelerate till stop running. The reaction time of the motor (from standstill to 3000 r/min) is within a few milliseconds. In Figure 2, the master PLC sends a 69-byte data packet, which contains the rotation speed and position information of the master servo motor, to the slave PLC every 500 $\upmu$s. The minimum static position alignment accuracy can be controlled at 0.001 degrees, and the required dynamic accuracy should be below 1 degree.

As shown in Figure 3, the maximum position error under 500 $\upmu$s jitter is 1.82 degrees, which exceeds the required 1 degree. In a common public network environment (100 ms delay, $\pm$50 ms jitter), the maximum position error expands to 10.57 degrees and 44.5 degrees at the speed of 30 r/min and 150 r/min, respectively. Moreover, we found that disabling out-of-order reduces the maximum position error to less than 3 degrees and less than 10 degrees. In Figure 4, a jitter of 500 $\upmu$s alone still has a certain probability of making the accuracy exceed 1 degree when the speed is 150 r/min. Table 2 shows that packet loss is also unacceptable in industrial networks. About 20% packet loss will cause systems to be out of work.

Limitations of best-effort forwarding: DetNet targets to bridge the gap between information technology (IT) and operational technology (OT) by enhancing real-time capabilities based on the Ethernet standard, as exhibited in Figure 5. Traditional Ethernet/IP adopts the best-effort forwarding that has the long-tail delay effect. To investigate this effect, we inject many token bucket flows into a commercial 10G Ethernet switch and measure the packet latency and queue length. As shown in Figure 6(a), with traffic load increases, more and more flows experience longer tail delays. The jitter is already in the order of tens of microseconds even for a load of 25%. When the load is 100%, the delay is unbounded and some packets are dropped. A very lightly-loaded (e.g., 5%) network may yield a low latency and small jitter, but huge bandwidth waste is unbearable.

Essentially, the uncertain queuing delay is the culprit causing the long-tailed effect. As the number of injected flows grows, the queue length of the output port increases dramatically as shown in Figure 6(b). And the maximum queue length is proportional to the flow number (indicated by the red line). The reason is that bursty flows may send multiple packets at once and packets from multiple flows may arrive at the same time, thus they contend for the output port and the packet queue builds up significantly. For example, if five flows arrive simultaneously, the last flow has to wait in the queue until the other four flows are completely transmitted, resulting in a worst-case queuing delay of four flows’ serialization time.

This problem can become worse with flow aggregations at the downstream node. In Figure 6(c), as the number of hops increases, the average delay of the flow grows gradually, while the worst-case delay increases sharply. In theory, it has been proved in [35] that the delay bound $D_{max}$ in a network with aggregate class-based strict priority scheduling is:

where $\tau$ is the maximum serialization delay and $\Delta$ is the maximum intra-node processing jitter. Specifically, $D_{max}$ is strongly correlated with the maximum link utilization $\alpha$ and the number of hops $h$. When the $\alpha$ approaches or exceeds $1/(h-1)$, there is no upper bound on the delay. That means, for a network with ten hops, as long as the link utilization approaches or exceeds 11%, the delay has no upper bound.

Observation 1: The uncertain queuing delay, which is caused by flow bursts and aggregations, prevents time-sensitive flows and best-effort traffic from co-transmitting.

The best-effort forwarding, i.e., transmitting packets as soon as possible, is not applicable to industrial networks. Marking time-sensitive traffic as the highest priority can isolate the impact of best-effort traffic and reduce the average queuing delay, but the queue resource contention among time-sensitive traffic of the same priority is still uncontrollable.

As depicted in Figure 7(a), we observe that the key point to bound the queuing delay is to restrict the maximum queue length at each output port and to bind the queue length to a time factor of the cycle $T$. During a cycle, packets in a queue must all be transmitted out from the current node. Compared to previous active queue management (AQM) mechanisms and congestion control mechanisms that also have a threshold for single queue length, cyclic scheduling refines time slot allocation by changing the queue model from time-continuous to time-discrete[36], and smoothes bursts in a time division multiplexing manner. For instance, assuming the shaping parameter $b^{{}^{\prime}}_{f}$ is 6 KB, the incoming bursts $b_{f}$ of 10.5 KB is smoothed into two queues with the discretized shaping delay of no more than $\left\lceil\frac{b_{f}}{b^{{}^{\prime}}_{f}}\right\rceil\times T$, which is $2T$ in Figure 7. The theoretical analysis for cyclic scheduling is presented in Appendix B.

Based on the idea of cyclic scheduling, plenty of mechanisms and algorithms have been proposed to facilitate the bounded delay and jitter transmission, such as stop-and-go[37], Damper[16], CQF[15], CSQF[25], LDN[38], and PPV(Per Packet Value)[27]. The recently proposed CSQF as a representative instance is presented in Appendix C. In response to above trends and benefits, it is necessary to implement a cyclic scheduling paradigm into devices for long-distance deterministic transmission.

Observation 2: The cyclic scheduling can strictly bound the queuing delay by smoothing the bursts and determine the queuing delay by discretizing the queue waiting time.

Several works concentrate on the practical experiments of small-scale deterministic networks (e.g., inside room [39], a lab [40], or a building [41]), but no extensional studies are carried out in large-scale deterministic network devices where network services suffer from long-propagation delay and imperfect time synchronization. Remarkably, programmable packet scheduling simplifies the testing and deployment of new scheduling algorithms, which is the best candidate for achieving cyclic scheduling.

Researchers have strived to find general scheduling primitives to cover as many scheduling algorithms as possible in the past decades. However, most of them target priority-based low-latency and weight-based fair scheduling algorithms, while the possibility of bounded delay and jitter scheduling has been largely ignored. Besides, it has been proved that no universal algorithm can express all scheduling algorithms[42]. To deal with this dilemma, a novel programmable cycle-specified queue (PCSQ) scheduler is highly desirable to imitate cyclic scheduling. Next, we present the generic packet scheduling model, and detail the progressive relationship of PCSQ to other packet scheduling primitives.

Generic model: In most Ethernet switches, the packet data is stored in a buffer pool when more than one input port is trying to send packets to the same output port simultaneously, and queues are used to store packets’ metadata for scheduling. As shown in Figure 8, packets are selected to enqueue, process, and dequeue according to some custom packet scheduling algorithm. The control plane can configure the scheduling state maintained in memory. And a packet scheduler is used to express and enforce the chosen scheduling algorithm.

Scheduling algorithms: Packet scheduling algorithm specifies when and in what order packets from each queue should be transmitted on the wire. The work-conserving algorithms do not let a link idle as long as there exists a packet waiting to be scheduled, such as Strict Priority (SP), Deficit Round Robin (DRR) [43], and Weighted Fair Queuing (WFQ)[44], which are popular for their high bandwidth, low latency and fairness. The non-work conserving algorithms allow a link to be idle even when there are outstanding packets to send, such as Token Bucket (TB)[45] , TAS[46], CQF[47], and CSQF[48][21]. Since non-work conserving algorithms can specify the time to schedule a packet by checking the eligible sending time against the current time, they are naturally suitable for traffic shaping, such as rate-limiting and packet pacing, further carving the stringent lower bound and upper bound for delay and even jitter.

Scheduling primitives: We briefly introduce the five related primitives: FIFO, PIFO, PIEO, PIPO, and PCQ. The FIFO, i.e., first-in and first-out, is the most basic scheduling primitive, which simply schedules packets in the order of their arrival. FIFO is easy to be implemented in hardware and multiple FIFOs can express the strict priority and some round robin algorithms, but it is incapable of expressing other popular scheduling algorithms. PIFO is a priority queue that associates a rank with each packet. The packet with the smallest rank (i.e., the highest priority) is always dequeued first. Different packet scheduling algorithms, such as Shortest Remaining Processing Time (SRPT)[49], can be implemented on top of PIFO by changing the rank computation function. PIEO not only utilizes the rank computation to enqueue packets, but also allows dequeue from arbitrary positions by supporting predicate-based filtering at dequeue. PIPO is an approximation of PIEO that can express all existing TSN scheduling algorithms, while it is limited to local-area networks that require ideal clocks and negligible link delay.

The solution of PCSQ: Programmable Calendar Queues (PCQ) is a recent proposal that supports the queue rotation mechanism. It stores packets in a queue corresponding to a particular day and moves onto the next day after all packets are processed from the current day. This rotation mechanism allows scheduling algorithms to escalate the priorities of buffered packets with time and reuse emptied queues for incoming packets with low priority, which is close to the appearance of cyclic scheduling. Inspired by the PCQ, we envision that a programmable cycle-specified queue (PCSQ) scheduler is ready to come out by jointly designing the priority queues and rotation queues. As shown in Figure 8, in the PCSQ, packets are enqueued to a specific cycle-related queue by cycle identification, and dequeued in a time-discrete rotation manner with bounded queuing delay. To some extent, the cycle tags computation of PCSQ is like buying time-stamped tickets for time-sensitive flows, which allows the packet to actively pick and lock its favorite seat (queue) in a sequence of stations (nodes). While with the previous rank computation, packets can only passively choose to be received or dropped.

It is significant to realize cyclic scheduling based on programmable packet scheduling. However, the previous packet scheduling primitives, such as FIFO, PIFO, PCQ, and PIPO, cannot express the features of cyclic scheduling. There are mainly four challenges in implementing PCSQ. (1) PCSQ executes the enqueue operation by parsing the cycle tags in the packet header, rather than the rank calculation. (2) It requires multi-queue rotation similar to the dynamic priorities of calendar queues, but one for transmitting and the remaining for receiving. (3) PCSQ dequeues in a time-division multiplexing manner, requiring nanosecond-level frequency synchronization and microsecond-level cycle-based forwarding, which is completely different from the previous priority-based, packet-size-based, or deadline-based forwarding. Although frequency synchronization has been well studied, how to convert clocks to an arbitrary length of cycle and ensure the time accuracy of dequeuing is a significant new challenge. (4) Lastly and most importantly, traditional queue scheduling is asynchronous, which has the cycle-queue mismatch problem that packets at queue boundaries may miss specific time slots and disrupt subsequent cycle-based forwarding behavior, while synchronous scheduling may introduce additional resource overheads.

Motivated by the above problems, we aim to design the Programmable Cycle Specified Queue (PCSQ) primitive for implementing cyclic scheduling with the following properties:

Microsecond-level dequeuing: By utilizing frequency synchronization and timing compensation, PCSQ must enable high-precision rotation dequeuing to reserve microsecond-level time slot resources for time-sensitive flows.

Bounded delay and low jitter: With the queue coordination and cycle mapping mechanism, the PSCQ must satisfy the queue-cycle match constraints and transmit flows to the destination within the required bounded delay and low jitter.

High scalability: By exploiting segment routing, our scheme should have high scalability and schedule thousands of time-sensitive flows in large-scale deterministic networks.

We show how PCSQ achieves the first two goals in the next section. The last goal is identified in the evaluation part.

The PCSQ framework is depicted in Figure 9. Switches have eight priority queues from seven to zero, and the highest priority is seven. We assume our PCSQ abstraction has a fixed number of buckets or FIFO queues, say N, each of which is marked with the highest priority to store the time-sensitive (TS) flows and mapped to an individual cycle time. The best-effort (BE) flows are marked with the remaining priority. The packet classifier distinguishes time-sensitive flows from best-effort flows based on QoS fields (e.g., DSCP or VLAN value) and sends them to the corresponding queue.

The workflow of PCSQ: Each time-sensitive packet is scheduled by making the following key decisions: ① First, the enqueue function identifies the port and cycle information by parsing the SRv6 header, and enqueues the packets to the specific queue binded to the cycle time. ② Second, the queue coordination function maintains the state of current transmitting queue (i.e., currQ=1) and receiving queue (i.e., headQ=2 and tailQ=N). The advancing of time can be done using a physical real-time clock (RTC), where the frequency synchronization (FS) module conducts the frequency synchronization protocol and the timing compensation (TC) module converts the clocks to an arbitrary length of the cycle. Then, the queue coordination function rotates the queue by periodically changing the current transmitting queue to the next queue after a fixed time interval. ③ Third, the packet is dequeued once the queue where the packet is located becomes the current transmitting queue. ④ Finally, the cycle mapping function learns the cycle relationship between adjacent nodes, so the packet can be accurately sent to the queue of the next node with the next segment ID.

To transmit time-sensitive flows and best-effort flows over one converged network, we cascade a strict-priority (SP) scheduler after the PCSQ scheduler. The BE queues are triggered whenever the TS queue is idle and the idle time is long enough to allow at least one current BE packet to be transmitted. Compared to the previous PIFO primitive, PCSQ scheduler needs to maintain states only at the granularity of switch queues (e.g., the queue corresponding to the current cycle). The scheduler does not require expensive sorting or comparisons to determine packet transmission order.

SLA configuration: In general, Internet operators use leased tunnels[50] to ensure strict QoS. After users provide service level agreement (SLA) parameters such as committed bandwidth and priority to the operator, the service can be activated in seconds. PCSQ is in the same vein as leased tunnels and requires more parameters such as deadline and jitter. Ideally, the controller may directly interact with end devices and update the configuration in microseconds[51]. Next, we separately present the key functions of dequeuing, queue coordination, cycle mapping, and cycle tags computation.

Traditional round-robin scheduling is based on bit counters and bandwidth calculations, such as WRR (Weighted Round Robin) and WFQ (Weighted Fair Queuing), which cannot provide strict guarantees on hop-by-hop queuing delays. The cyclic scheduling of PCSQ is based on the advancing of time, which arouses a new challenge of microsecond-level time slot calculation. For instance, if the cycle size is 10 $\upmu$s, the current transmitting queue needs to complete the dequeue operation within 10 $\upmu$s, and the cycle size of 10 $\upmu$s at each node must be the same. PCSQ realizes high-precision rotation dequeuing with the frequency synchronization (FS) and time compensation (TC) modules.

Frequency synchronization: Native Ethernet (IEEE 802.3) is asynchronous with no timing traceability to a reference clock, and there are two representative protocols for network-wide frequency synchronization: precision time protocol (PTP) and synchronous Ethernet (SyncE). PTP[52] is a data-link layer protocol that can achieve nanosecond-level accuracy under idle network conditions, but achieve only sub-microsecond level accuracy under network congestion.

SyncE[53] is a physical layer frequency distribution mechanism, which requires an external line card to be attached to the Ethernet interface. The master node transmits the bit clock signal to slave nodes and the latter recovers the clock via the transceiver CDR (Clock Data Recovery). SyncE has the advantage of relying on the physical layer only, thus the clock synchronization quality is not influenced by impairments introduced by the upper layers, such as packet delay variation (PDV), and packet losses[54]. While native Ethernet has an independent free-running clock with frequency accuracy not exceeding $\pm$ 100 ppm (parts per million), SyncE can achieve long-term accuracy of $\pm$ 10 parts-per-trillion as defined in ITU G.811[53]. Thus, this paper adopts the SyncE as the frequency synchronization mechanism.

Timing compensation: The controller can set the cycle size by modifying the localbus configuration register. And the time compensation module is responsible for converting clocks to an arbitrary cycle length. When the oscillator frequency of the device is a rational number (e.g., 400Mhz with the clock of 2.5 ns ) and the required cycle is also an integer multiple of the clock (e.g., 10 $\upmu$s), it is easy to obtain accurate time slot by iterative calculation (e.g., 2.5 ns for 4000 iterations is 10 $\upmu$s). However, when the device frequency is not a rational number, or the required cycle is not an integer multiple of the clock, a cycle conversion deviation will occur, which may further introduce a widening time-slot cumulative bias over the long run. To solve this problem, we keep the cycle in nanoseconds to twelve decimal places and design a five-level cascade counter from $zs$, $as$, $fs$, $ps$ to $ns$. Our design can calibrate the conversion deviation and obtain ns-level accurate cycle time to achieve $\upmu$s-level rotation dequeuing.

Since traditional queue scheduling is asynchronous, the enqueue and dequeue operations are separate and unaware. Asynchronous scheduling has the cycle-queue mismatch problem that packets at queue boundaries may miss specific time slots and disrupt subsequent cycle-based forwarding behavior. For the cyclic scheduling, when a rotation happens, we need to make sure all packets from the current transmitting queue are drained completely, which requires maintaining the state of head queue and notifying the enqueue operation when the dequeuing has been finished.

We first analyze the two cycle-queue mismatch cases of timeslot miss and traffic incast. Then, to ensure that the cycle tag information in the packet header is consistent with the actual underlying queue scheduling behavior, we design the enhanced enqueue function and dequeue function for the queue coordination mechanism.

Case-1: Cycle-queue mismatch caused by timeslot miss. In this case, some packages at the tail of the queue may miss the current timeslot after the cycle time has elapsed and the head of the dequeuing has moved to the next queue. As shown in Figure 10(a), we assume that the port rate is 100 Gbps, the cycle size is set to 10 $\upmu$s, and the maximum queue length is 100 packets. The $100^{th}$ packet may miss the current timeslot and wait a total hyper-cycle until the located queue becomes the transmission queue again. One might argue that if the sum of the packet sizes does not exceed 125 KB (i.e., 100 Gbps$\times$10 $\upmu$s), then the packets can always be transmitted within 10 $\upmu$s. However, assuming that the last packet is 64 Bytes, the required transmission time is 0.00512 $\upmu$s, which only accounts for about five ten thousandths of 10 $\upmu$s. Therefore, if we only check whether the queue is full when packets enter the queue, but do not judge whether the queue is empty when the packets are dequeuing, it is possible that the queue has been rotated before the transmission is completed. Another way to deal with the timeslot miss problem is to over-reserve time slots, e.g., only enqueuing 80 packets even though one cycle time can transmit 100 packets. Nevertheless, over-reservation fails to exert the forwarding capability of the device, which violates the goal of maximizing the number of time-sensitive flows that can be scheduled.

Case-2: Cycle-queue mismatch caused by traffic incast. When a node has multiple upstream nodes, the queue forwarding behavior may not conform to the cycle tags due to traffic incast. As shown in Figure 10(b), the traffic of the three nodes arrives at the same time and starts to calculate the cycle tags. When viewing each of them, the queue length meets the demands. However, traffic aggregating to the same queue causes queue overflow, so all packets cannot be transmitted within 10 $\upmu$s and the 100^th to 120^th packets will be dropped. On the contrary, time-sensitive flows are critical traffic, which are not allowed to be dropped. To tackle the traffic incast problem, we need to check whether the queue is full when enqueuing. If it is full, the enqueue operation should be notified to transfer the remaining packets to the next non-full queue for transmission.

PCSQ enqueue: Algorithm 1 shows the pseudocode of PCSQ enqueue function. First, the enqueue function obtains the $sid$ by parsing the SRv6 header of a packet (line 3), then it maps the $sid$ to the $qid$ based on the current transmission queue ($currQ$) state provided by the egress pipeline (line 4). If the length of the mapped queue is less than the queue size $S$, i.e., the queue is not full, the packet is enqueued to the mapped queue and the queue length is incremented by one (line 5-7). In most cases, the $sid$ is reasonably calculated by various scheduling algorithms in the control plane. To deal with the traffic incast problem, we allow packets with inappropriate $sid$ to shift one queue. In other words, if the mapped queue is full and the next queue is not full, the packet can be selected to the next queue (line 8-12). Otherwise, the packet is dropped (line 13-14). Theoretically, time-sensitive packets that cannot be discarded should enter any subsequent non-full queue. But this operation will cause persistent delay jitter and interfere with normal cyclic packet scheduling behavior. Thus, we only allow one queue shift, which keeps the jitter to one cycle.

PCSQ dequeue and rotation: Algorithm 2 shows the pseudocode of PCSQ dequeue and rotation function. The $t_{now}$ is the current time recorded by the RTC, and the $Flag$ is used to mark and iterate the time interval of one cycle (line 3). In one cycle time of $C$, if the $currQ$ is not empty, the egress pipeline executes the dequeue operation and sends out all the packets in the $currQ$ (line 5-9). Since we count the length of the enqueuing packet by adding operation, the dequeue operation can ensure that all data packets are transmitted by subtracting operation, which solves the problem of timeslot miss. After the $currQ$ is drained completely, the $t_{now}$ is updated to the RTC time again (line 10). If $t_{now}$ is still smaller than $Flag+C$, which means the TS queue is idle, the BE queues are triggered to transmit BE packets. Otherwise, the egress pipeline executes the rotation operation and the current transmission queue is moved to the next queue (line 11-12).

Previous packet scheduling works (such as PCQ) are unaware of link delay and internal device delay. Each node is scheduled independently, which makes it difficult to deal with the aggregation problem under long-distance links. Hence, another challenge for achieving cyclic scheduling is obtaining the cycle relationship between nodes. In a local-area network, the network-wide time synchronization can be conducted and the transmission slots can be strictly aligned (i.e., all devices in one time zone). For a large-scale wide-area network, frequency synchronization means that devices are in different time zones. Hence, the time zone conversion is required.

To sovle the time zone conversion problem, the cycle mapping mechanism between nodes is proposed. For instance, there are three PCSQ-enabled nodes as shown in Figure 11. First, when the device is initialized, the node A generates two SRv6 $probe$ packets and sends them to the adjacent node B and node C. When the $probe$ packet is transmitted to node B at the $currQ$ of the output port, 4 bits information (i.e., 0001 to 1111 for fifteen queues) of cycle $X$ is timestamped in the packet headers. Then, node B receives the $probe$ packet and transmits it at the $currQ$ with timestamped cycle $Y$ to node A. Thus, node A can learn the cycle mapping relationship with node B by parsing the packet header, which is $X\rightarrow Y$. In the same way, node B can learn that the relationship with node C is $Y\rightarrow Z$. Finally, each node will maintain a local cycle mapping table and update it to the control plane. For a network with $\eta$ nodes and $\varepsilon$ edges, the total number of required $probe$ packets is $2\left|\varepsilon\right|$, and the total number of entries for all cycle mapping tables is at most $\left|\eta\right|\times(\left|\eta\right|-1)$. Moreover, the packet processing complexity is only $O(1)$[43], which is suitable for large-scale networks.

Therefore, when a tunnel of $A\rightarrow B\rightarrow C$ is conducted, the controller learns the cycle mapping relationship of $X\rightarrow Y\rightarrow Z$ in the global view, which serves as the basis for scheduling algorithms. For a naive scheduling algorithm without $sid$ computation, if the relationship is $1\rightarrow 3\rightarrow 4$, all eligible incoming packets can be naturally transmitted with cycle sequence $2\rightarrow 4\rightarrow 5$, $3\rightarrow 5\rightarrow 6$, and so on.

Programmability to approximate cyclic scheduling: Since most cyclic scheduling algorithms (such as CQF, CSQF, Damper, and LDN) are developing, it is not trivial to implement these algorithms directly. The crucial difference is that varied constraints are used to shape the traffic and estimate the residence cycle time of packets at each hop. Thus, similar to rank computation in PIFO, we propose the concept of cycle tags computation for PCSQ to approximate a series of cyclic scheduling algorithms. Note that the value of $sid$ in Algorithm 1 is a non-negative integer determined by any customized top-level scheduling algorithm. For different time-sensitive flows, such as periodic/aperiodic flows, and constant/variable bit rate flows, various static planning or online scheduling algorithms[21][25][48] can be programmed to compute and optimize the cycle tags of packets.

Cycle tags computation vs rank computation: The rank computation is restricted by local ordering that cannot guarantee the global properties such as end-to-end delay and jitter. For example, PIFO[28] implements the Earliest Deadline First (EDF) by using Least Slack Time First (LSTF) scheduling. The rank of a packet is computed by:

The $slack$ is the time remaining till its deadline and is decremented by the wait time at each switch’s queue. The $rank$ ensures that the packet with the closest deadline is transmitted first, but packets with specific deadlines still have the probability of being violated or even dropped. On the contrary, the cycle tags of a packet can be computed by:

The $(Z-X)$ is the path delay measured by cycle mapping, $h$ is the number of hops, and $T$ is the cycle size. The packet’s SIDs are equal to the cycle offsets $\delta$ that uniformly divides the deadline into per-hop postponed time[55]. Thus, the deadline is strictly satisfied by mapping flows into underlying link capacity and cycle-queue resource blocks.

Another well-investigated instance is stop-and-go[37], which requires packets arriving within a cycle is always transmitted at the next cycle. PIFO defines two state variables of $cycle\_begin\_time$ and $cycle\_end\_time$ to track the beginning and end of the current cycle, where the cycle size is $T$:

In contrast, PCSQ is naturally suitable for cyclic scheduling. We just need to set each cycle tag to 1 (i.e., enqueue the next transmitting queue) to approximate the stop-and-go:

Moreover, LDN focuses on access shaping, thus computing the cycle tags of the first hop is enough to express LDN. Damper emphasizes reducing jitter, thus PCSQ can use a fixed cycle tags stack to simulate Damper. In fact, PCSQ’s rigid scheduling is suitable for typical industrial automation traffic (such as constant bit rate traffic or flows with committed microbursts). Large burst flows are still intractable and cause a great waste of reserved resources. Apart from the queuing delay, the shaping delay of different cyclic scheduling algorithms plays an important role in the cycle tags computation. Traffic shaping at end hosts, such as Carousel[56] and FlowBundler[57], can streamline the cycle tags computation by batching flows and releasing packets at scale accurately. More algorithm designs based on PCSQ will be future work.

Evaluation setup: We inject a large number of time-sensitive flows from multiple ingress ports to one egress port in a single PCSQ-enabled switch node. The cycle size $C$ is empirically set to 10 $\upmu$s and the queue number $N$ is set to 15. The number of queues can be larger by taking up more of the available on-chip memory. The time-sensitive flows are generated based on the token-bucket model with packet size ranges from 64 to 1500 bytes, flow rate from 256 kb/s to 10 Mb/s, and burst size from 1 to 10 packets. The maximum reserved bandwidth for time-sensitive flows is set to 12%, and many best-effort flows are injected as background traffic.

Bounded latency and jitter: First, we compare the PCSQ with the class-based strict priority (SP) scheduling under the port rate of 10 Gbps. As shown in Figure 12(a), with the loads increase, the queue length of SP scheduling grows sharply, while PCSQ maintains a strict upper bound of 12.5 KB on the queue length and enables all packets of a single cycle queue to be transmitted within 10 $\upmu$s. Then, we randomly select a time-sensitive flow to observe its end-to-end delay. In Figure 12(b), the minimum delay under SP scheduling is about 41.6 us, but the maximum delay reaches 261 $\upmu$s, resulting in jitter of about 219.4 $\upmu$s. The minimum and maximum delays of PCSQ are 78.7 $\upmu$s and 92.18 $\upmu$s, which only brings 13.48 $\upmu$s of jitter. To compare the impact of different rates on the delay and jitter, we conduct the same experiment at the 100 Gbps port rate. As shown in Figure 12(c), the maximum delay of SP scheduling at 100G rate is reduced by 58.2% compared with 10G rate. The increase of the port rate has little effect on the delay and jitter of PCSQ scheduling, but it will require a larger buffer to accommodate more packets under the same condition of cycle size. Additionally, PCSQ achieves more than 148 Mpps throughput, easily supporting 100 Gbps small-packet link-rate forwarding as presented in Figure 12(d).

Resource overheads: The resource usage of PCSQ is summarized in Table 3. Compared to the WRR queue, PCSQ’ URAM and BRAM consumption decreases by 12.5% and 11.2%. PCSQ utilizes the shared buffer to uniformly cache the deterministic flow of multiple queues into one buffer, which can not only handle the burst of each channel, but also reduce the memory resource overhead. Since the queue coordination and cycle mapping functions are implemented in LUTs and Flip Flop, PCSQ’s LUTs and Flip Flop consumption increases by 4.1% and 3.6% compared to FIFO queue. Moreover, PCSQ costs 0.7% resources of DSPs to compute the timestamp and carry the timing compensation algorithm.

Evaluation setup: To evaluate the PCSQ’s performance under typical long-distance aggregation scenarios, we construct a realistic testbed that contains six PCSQ-enabled nodes, which are hosted in six different cities, including Beijing, Shijiazhuang, Zhengzhou, Wuhan, Hefei, and Nanjing. The overall transmission distance from Beijing to Nanjing exceeds 1500 kilometers and the link capacity is 100 Gbps. In the experiments, the target time-sensitive flows originate from Beijing, pass through the intermediate nodes (i.e., Shijiazhuang, Zhengzhou, Wuhan, Hefei), and finally arrive at Nanjing. Numerous TS and BE traffic are injected into each node as interference flows. All flows are generated under the guidance of traffic characteristics in wide area monitoring and control systems (defined in the IEC 61850) and the industrial machine-to-machine (M2M) of the DetNet use case[12].

Synchronization accuracy: Frequency synchronization is the basis for high-precision rotation dequeuing. The PCSQ device is equipped with a TCXO (Temperature Compensate X’tal (crystal) Oscillator) of 38.88 Mhz, and we evaluate the synchronization accuracy of the PTP protocol (1588v2 with two-way, boundary clock model) and the SyncE under the same environmental conditions. As depicted in Figure 13(a), the average deviation of PTP gradually expands with the number of hops increasing. The maximum average deviation of PTP is 17.18 ns. In contrast, the average deviation of SyncE does not exceed 0.2 ns, which is stably maintained at a very low level for a long time. Figure 13(b) exhibits the synchronization waveform under the case of six hops. The time error of PTP ranges from 8.5 to 21 ns, while SyncE ranges from -1.85 to 1.82 ns. Based on the syncE and time compensation algorithm, PCSQ-enabled device can obtain ns-level accurate cycle time and maintain the cycle rotation consistency between adjacent nodes.

Performance under aggregations: Two typical wide-area scheduling methods, strict priority (SP) and calendar queue (CQ), are set as the comparison mechanisms. CQ is a general round-robin queue that does not have enhancements such as frequency synchronization, cycle identification, and cycle mapping. Figure 14(a) depicts the relationship between the end-to-end worst-case delay and the number of hops. PCSQ can strictly control the upper bound of hop-by-hop network delay through the cycle tags. The delay of PCSQ is close to that of CQ, and sometimes CQ has a slightly smaller delay because packets under CQ have some probability of entering the earlier periodic queue. Compared to SP, PCSQ reduces the end-to-end delay by up to 10.8% and queuing delay by up to 70%. More importantly, as the number of hops increases, the jitter of SP and CQ becomes larger, while PCSQ remains around 10 $\upmu$s. As shown in Figure 14(b), the maximum jitter under six hops for SP, CQ and PCSQ is 1220.4 $\upmu$s, 163 $\upmu$s, and 16.7 us, respectively. Compared to SP, PCSQ greatly reduces the jitter by up to 98.6%. Then, we set the cycle size to 20 $\upmu$s and 50 $\upmu$s, and test the delay and jitter of the target flows under the same conditions. As shown in Figure 14(c), the maximum jitter of PCSQ under cycle size of 10 $\upmu$s, 20 $\upmu$s, and 50 $\upmu$s is 12.51 $\upmu$s, 23.7 $\upmu$s, 54.45 $\upmu$s, which proves that the scheduling behavior of PCSQ conforms to the CSQF mechanism (i.e., limited to $2T$ regardless of hops). Although the cycle size of 50 $\upmu$s increases the end-to-end delay, there is no dependency between the cycle size and the delay since the delay can be reduced by adjusting the cycle tags. Furthermore, we assess the impact of PCSQ on best-effort (BE) flows. Figure 14(d) indicates that PCSQ will slightly increase the end-to-end delay of BE traffic compared to SP due to reserving dedicated time slots for time-sensitive traffic. To avoid starvation of BE flows, a certain percentage of gaps (e.g., 15%) can be preset for BE flows in each cycle queue scheduled by PCSQ.

Scalability: To evaluate the scalability of PCSQ, we divide the time-sensitive flows into five groups of 8k, 16k, 24k, 32k, and 40k, and observe the number of schedulable flows. The deadline and jitter requirements are randomly selected from 8-10 ms and 20-500 $\upmu$s. Figure 15 show that as the number of flows grows, 97.5% of the traffic can still be successfully scheduled by PCSQ for 40k flows. Practically, PCSQ can scale to tens of thousands of flows in large-scale deterministic networks. Since PCSQ does not need to maintain per-flow states at intermediate and egress nodes, its scheduling capability is proportional to the reserved bandwidth. As the network topology becomes larger, the complexity of cycle tag computation in the control plane may increase, but it will not affect the scheduling performance of PCSQ in the data plane. Global label optimization to maximize the schedulability will be future work.

In this section, we focus on specific emerging applications, such as industrial teleoperation, remote driving, remote surgery, and VR interaction. These applications often require co-transmission of remote control flows and real-time video flows. Next, we replace the target flows with the control flows and video flows, and conduct the following experiments.

Performance of remote control flows: The control flows are periodic mice flows, such as sending a 250-byte packet every 0.5 ms, occupying 4 Mbps of bandwidth but requiring a deadline of no more than 10 ms and jitter of 100 microseconds. Fifty control streams with different periods and packet sizes are generated and transmitted with video traffic and BE traffic under 80% heavy-load scenarios. As shown in Figure 16(a) and Figure 16(c), the maximum end-to-end delay and jitter under PCSQ is 8.12 ms and 10.83 $\upmu$s, which meet the deadline and jitter requirements for remote control. Although the minimum delay of SP and CQ is smaller than that of PCSQ, their jitter is as high as 802.6 $\upmu$s and 309.8 $\upmu$s.

Performance of real-time video flows: The single real-time video stream is quite bursty, with a mean bit rate of 5.4 Mb/s and a peak bit rate of about 120 Mb/s. A large video frame (e.g., 80 KB) is split into multiple packets not exceeding the MTU size, and large jitter between adjacent packets may cause video playback delays, quality loss, and stutters. To simulate wide-area real-time video streaming, one thousand video flows are aggregated with the mean bit rate of 5.4 Gb/s. As shown in Figure 16(b) and Figure 16(c), the maximum end-to-end delay and jitter under PCSQ is 8.22 ms and 12.18 $\upmu$s. To keep the bursty video streams from interfering with the transmission of the control flows, we assign the two applications to different cycle queues to enhance isolation. Once the video stream does not have enough bandwidth or the cycle tag calculation is unsuccessful, it can be degraded to a best-effort stream for delivery. As shown in Figure 16(d), degrading video streams will bring large latency fluctuations, while successfully tagged video streams can still maintain strictly bounded latency and jitter.