{'fraction_non_alphanumeric': 0.03673897830650805, 'fraction_numerical': 0.014445666300109967, 'mean_word_length': 4.3068965517241375, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Long-distance Deterministic Transmission among TSN Networks: Converging CQF and DIP

With the development of 5G, innovative applications requiring bounded transmission delays and zero packet loss emerge, e.g., AR, industrial automation, and smart grid. In this circumstance, time-sensitive networking (TSN) is proposed, which addresses the deterministic transmission in the local area networks. Nevertheless, TSN is essentially a Layer 2 technique, which cannot provide deterministic transmission on a large geographic area. To solve this problem, this paper proposes a hierarchical network for the end-to-end deterministic transmission. In the proposed network, we leverage CQF (i.e., one of the most efficient TSN mechanisms) in the access networks which aggregates the traffic from end-devices. Meanwhile, in the core network, we exploit the DIP (i.e., a well-known deterministic networking mechanism for backbone networks) for long-distance deterministic transmission. We design the cycle alignment mechanism to enable seamless and deterministic transmission among hierarchical networks. A joint schedule is also formulated, which introduces the traffic shaping at the network edge to maximize the network throughput. Experimental simulations show that the proposed network can achieve end-to-end deterministic transmission, even in the highly-load scenarios.


I. INTRODUCTION
With the development of the Internet and communication networks, many time-sensitive applications are emerging, such as factory automation, connected vehicles and smart grids [1]. Traditional IP networks performing best-effort transmission provide some Quality of Service (QoS) strategies (e.g., DiffServ and congestion control [2]). However, due to microburst traffic [3] existing in networks, these mechanisms can not achieve deterministic transmission, which means zero packet loss, bounded delays and jitters (i.e., delay variation) [4]. Thus, for eliminating micro-burst traffic, IEEE aims to develop a set of standards named Time-Sensitive Networking (TSN) to provide deterministic transmission in layer 2. Due to the high efficiency, Cyclic Queuing Forwarding (CQF) [5] is one of the top choices in TSN [6]. Besides, Credit-Based Shaper [7] and Time-Aware Shaper [8] are also well-known mechanisms in TSN. However, TSN cannot provide longdistance deterministic transmission because of the requests for high precision time synchronization and low propagation delays, which leads to the "information isolated island" among TSN networks. Global management of TSN applications (e.g. teleprotection, wind farm applications, etc. [9]) requests longdistance deterministic transmission among TSN networks.
For achieving large-scale deterministic transmission, the IETF Deterministic Networking (DetNet) group focus on promoting the standardization in layer 3. The standards of DetNet are still under discussion. Some drafts have been proposed, such as Cycle Specified Queuing and Forwarding (CSQF) [10] and Deterministic IP (DIP) [11]. CSQF leverages Segment Routing [12] Identifier to coordinate cyclic transmission times across large-scale networks to offer deterministic transmission. DIP is one of the effective mechanisms in DetNet. The routers performing DIP (named as DIP routers) achieve frequency synchronization. Packets are transported in a slotted fashion by carrying a cycle identifier. After investigating recently proposed deterministic forwarding mechanisms, we find that no researches have been conducted to apply DetNet to achieve long-distance deterministic transmission among TSN networks. In this paper, we propose a hierarchical network for long-distance end-to-end deterministic transmission. CQF technique is used in the access layer, and DIP supports the core layer.
Due to the differences between CQF and DIP, it is not effective to integrate these two mechanisms directly. The first problem is different time synchronization mechanisms in CQF and DIP. Time synchronization with high precision used in most TSN mechanisms is hard to achieve in long-distance deterministic transmission. Thus, DIP only requests frequency synchronization. The second problem is the duration of a cycle may be different in CQF and DIP. These two problems are the barriers to construct correspondences between cycles in CQF switches and DIP routers because cycles in CQF do not correspond to cycles in DIP one by one. However, cycle correspondences are the foundation to achieve deterministic transmission in CQF and DIP.
To tackle the problems mentioned above, this paper establishes the network model of the hierarchical network and proposes a cycle alignment mechanism to establish the correspondences between cycles in CQF and DIP. Based on the cycle alignment, we propose a traffic shaping mechanism to solve the disorder of traffic at the edge of access and core networks to achieve end-to-end joint scheduling across CQF and DIP. The joint scheduling is formulated as integer linear programming to maximize the number of acceptable timesensitive flows. In the simulations, the scheduling is conducted in a greedy algorithm. The time-sensitive flows (TS flows) with high weight are scheduled preferentially. For each TS flow, the scheduling chooses the transmission pattern assuming minimum resources.
The rest of this paper is organized as follows. Section II details the deterministic networking technologies used in this paper (i.e., CQF and DIP). In Section III, the network model of the hierarchical network is introduced. Section IV proposes the end-to-end joint scheduling approach. Section V shows the setup and the results of simulations. Finally, Section VI concludes this paper.

II. BACKGROUND
A. Cyclic Queuing Forwarding IEEE 802.1Qch (CQF) standard [5] proposes a method to synchronize enqueue and dequeue operations, and schedule the transmission in a cyclic fashion. Time in CQF networks is divided into cycles with equal duration d. All CQF switches in the same CQF network are perfectly synchronized. There exist two queues (q1 and q2) in a CQF switch output port. In cycle c, queue q1 is open for dequeuing packets. At the same time, queue q2 enqueues packets from upstream. In the next cycle c+1, queue q1 enqueues packets and queue q2 dequeues packets. Due to the cyclic manner for transmission, the packets received in cycle c are scheduled to be retransmitted in cycle c + 1, and the maximum possible delay experienced in a CQF switch is from the beginning of cycle c to the end of c + 1, equal to 2d.
The upper and lower bounds are easily calculated in CQF networks. The number of hops is defined as h . D max and D min represent the maximum and minimum latency respectively. The equations to calculate D max and D min are as follows:

B. Deterministic IP
Time in DIP is also divided into cycles with equal duration T . Because perfect time synchronization is hard to achieve in large geographical coverage, DIP only requests frequency synchronization and permits the propagation delay exceeding the cycle duration. DIP leverages correspondences between cycles to achieve deterministic transmission. Fig. 1 shows the DIP transmission among three DIP routers (DR1, DR2, and DR3). Based on the propagation delays between DR1 and DR2, and the one between DR2 and DR3, the following cycle correspondences are constructed: the cycle x in DR1 is mapped to cycle y in DR2, and the cycle y is mapped to cycle z in DR3. These cycle correspondences imply that the packets sent in cycle x will be received in DR2 not later than cycle y −1, and retransmitted to DR3 in cycle y in DR2. It is similar between DR2 and DR3.
The packets sent at cycle x from DR1 carry the cycle identifier x. After receiving them, DR2 will check the cycles correspondences table stored in it, and find the correspondence x → y. Then DR2 enqueues these packets to the queue corresponding to cycle y. At cycle y, the queue will open and dequeue these packets to DR3. Fig. 1 shows the maximum and minimum delay from DR1 to DR3, and the maximum jitter is less than 2T .

A. Network model
The whole network is represented as G = {V, E}. V is the set of network devices, and E is the set of links. Network devices contain source hosts, destination hosts, CQF switches, CQF edge switches, DIP routers, and DIP edge routers, i.e., The processing delays in all devices are ignored.
For a link e ∈ E, source v 1 and end v 2 uniquely identify the link, i.e., e = (v 1 , v 2 ). A link e corresponds to a propagation delay ∆ e . The bandwidth of link e is denoted as BW e .
A path from the source v 0 ∈ V src to the destination v |p| ∈ V dest is denoted by p = (v 0 , v 1 , · · · , v |p| ), where |p| − 1 is the number of intermediate nodes along path p. A set P contains all possible paths from V src to V dest , i.e., p ∈ P .
Time-sensitive applications located in source hosts generate time-sensitive flows (TS flows). F represents the set of TS flows. Each TS flow f ∈ F is periodic, and the period is ∆ f .
A TS flow f emits packets in size of ω f bits during every ∆ f . Moreover, the source and destination of a flow f are deterministic. The maximum acceptable end-to-end delay of f is ∆ e2e f .

B. Time models in CQF and DIP
Time models in CQF and DIP are different. We define every access and core network as a time-domain named CQF-D and DIP-D respectively, as shown in Fig. 3. For uniformly scheduling, we introduce hypercycle, which contains multiple cycles in CQF and DIP.
CQF-D: CQF-D contains source/destination hosts, CQF edge switches and CQF switches. Fig. 3 shows that, in CQF-D, time is divided into time cycles with the same duration ∆ cqf . A hypercycle contains N cqf consecutive cycles. The length of a hypercycle is ∆ hc = N cqf ∆ cqf . All devices in CQF-D achieve perfect time synchronization, which means that the start time of a cycle (also a hypercycle) in all devices is the same.
where N cqf , N dip , N F ∈ Z + , N cqf and N dip are greater than the number of queues in output ports of CQF switches and DIP routers respectively.

C. Cycle alignment
We design a cycle alignment mechanism to construct correspondences between cycles in different devices. The cycle alignment is defined as follows: if packets sent in cycle a in a node A will all be received no later than cycle b in the downstream node B, we define a cycle alignment relationship as Φ (A,B) (a) = b.
Alignment in CQF-D: Inside CQF-D, packets transmitted by a node during cycle i must be received by the downstream node during the same cycle and retransmitted in cycle i + 1. Thus, the cycle alignment in CQF-D is Φ(i) = i.
Alignment in DIP-D: Fig. 4 illustrates a cycle alignment in DIP-D. There exist adjacent DIP devices node A and B with the same cycle length ∆ dip . The length of a hypercycle is ∆ hc = 3∆ dip (i.e., N dip = 3). Cycle 0 in node A is mapped to cycle 2 in node B (i.e., Φ (A,B) (0) = 2).
Note that the index x loops from 0 to N dip − 1. Alignment across CQF-D & DIP-D: Fig. 5 illustrates an established cycle alignment from node C to its adjacent node D. Node C and D are located in different time domains. The length of cycles in node C and D are ∆ C and ∆ D respectively. The length of hypercycle is ∆ hc = 5∆ C = 4∆ D , and the offset of hypercycle is ∆ C,D hco . Cycle 0 in node C is mapped to cycle 3 in node D, i.e., Φ (C,D) (1) = 3.
Note that the index x loops from 0.

D. Traffic shaping
The hierarchical network leverages cycle shifting to achieve traffic shaping. A cycle shift represents the additional cycles for retransmission based on the result of Φ(·). Cycle shifts in sources, CQF switches/DIP routers, and CQF edge switches/DIP edge routers are different respectively.
Cycle shifting in sources: A cycle shift r A f is corresponding to the TS flow f and the source A. If packets of f arrive at node A in cycle a, and a hypercycle contains N cycles, these packets will be retransmitted in cycle Fig. 6, packets of TS flows f 2 all arrive at cycle 0 from upper layer. Due to r A f2 = 3, f 2 will be sent out in cycle ((0 + 3) mod 5).

A. Decision variables
There are a series of decision variables to schedule TS flows in F . These variables can be classified into three types: admission control, path selection, and cycle shifting. Admission control: For a TS flow f ∈ F , x f is defined to describe whether f should be accepted ( Path selection: Cycle shifting: The cycle shifting for TS flow f is defined as

B. Constraints
There exist two constraints in joint scheduling: constraints on end-to-end delays and resource capacity.
Constraints on end-to-end delay: The end-to-end delay of a TS flow f depends on the scheduled path p f and the cycle shifting r p f . Thus, the end-to-end delay of f is described as For a link e i = (v i , v i+1 ) in path p f , we define the delay on e i as ∆ f ei , which contains the maximum time staying at v i and the propagation delay on e i (i.e., ∆ ei ). Thus, the upper bound of ∆ f ei can be defined as where ∆ vi is the duration of a cycle in node v i . The upper bound of path p f 's end-to-end delay can be calculated by For every TS flow f ∈ F , the constraint of end-to-end delay can be described as Constraints on resource capacity: The resource in the hierarchical network is cycles in every node. For a cycle c in node v i on link e = (v i , v i+1 ), if a set of TS flows F c is assigned to it, the total bits of F c should not exceed the transmission capacity of c (i.e., formula (11)).
f ∈Fc where ω c f is the total bits of f transmitted in cycle c, ∆ vi is the duration of a cycle in node v i , and BW e is the bandwidth of link e.

C. Objective function
The target of the joint scheduling is to accept as many f ∈ F as possible. The priority of every TS flow may be different. A weight value v f ∈ (0, 1] represents the priority of TS flow f . The problem can be formulated as an integer programming (IP): The hierarchical network shown in Fig. 2 is constructed in the simulation. The topology of the core network containing 15 DIP routers (with 10 µs as ∆ dip ) is established based on the network model Atlanta [13]. The lengths of links in the core network are 30 km to simulate long-distance transmission. The bandwidth of ports on DIP routers is 10 Gbps. We deploy 10 access networks, and every access network contains 2 CQF switches (with 25 µs as ∆ cqf ). The bandwidth of ports on CQF switches is 1 Gbps [14]. TS flows are connected to CQF switches. Packets of TS flows have to pass through the access network containing the source hosts, the core network, and the access network connected by the destination hosts.
Each access network contains 200 TS flows. The data rate of each TS flow is 500 kbps. Thus, the size of packets is 500 bit, and the interval of packets is 1ms. Besides, the maximum acceptable end-to-end delay of these TS flows is 1 ms. The schedule of packets is conducted in a greedy algorithm. In the simulation, the best-effort interference flows with a packet size of 1500 Byte are injected into the converged network. For verifying the effectiveness of the proposed joint scheduling in this paper, two experiments are conducted: (1) In different levels of interference flows, we compare the end-to-end delays of jointly scheduled flows and best-effort transmitted flows to verify the capability to providing bounded delays and jitters; (2) To prove the effectiveness of traffic shaping and path selection, the comparison of flows admission in three strategies (i.e., with traffic shaping and path selection, without traffic shaping, and without path selection) is performed.
Tabel I and Fig. 8 show the result of experiment 1, and prove the effectiveness of guaranteeing bounded end-toend delays and jitters. We randomly choose a TS flow in an access network to observe. The TS flow is transmitted in best-effort and the proposed joint scheduling. The total throughput of all 200 TS flows in the access network is 100 Mbps. With the increase of intensity (i.e., throughput) of interference flows, the end-to-end delays using best-effort (BE) grow significantly. In the light-load scenario injecting interference flows with throughput 229 Mbps, the maximum delay is 980 µs, and the jitter is 375 µs. In the mediumload scenario with 534 Mbps interference flows, the average delays are higher compared with light-load scenarios. The maximum delay is up to 1173 µs, and the jitter is up to 567 µs. Besides, there exist 26 TS flows having end-to-end delays beyond the maximum acceptable delay (1 ms). The delays using the joint scheduling is a constant 801 µs with zero jitters. Delays are not affected by the intensity of interference flows. In an extremely light-load scenario (i.e., the throughput of interference flows is 131Mbps), the maximum delay of best-effort transmission is less than the one in deterministic transmission. This phenomenon results from the extra delays introduced from cyclic transmission fashion in deterministic networking and cycle shifting. For guaranteeing bounded endto-end delays and jitters, the extra delays are acceptable, and the delays in deterministic transmission are significantly less than the maximum delay in light-load, medium-load, and highload scenarios.   9 illustrates the result of experiment 2. For verifying the proposed joint scheduling can raise the throughput of TS flows, we deploy a different number of TS flows that are waiting for scheduling in every access network. Obviously, the total throughput of these TS flows is less than the capacity of links. Using the joint scheduling with traffic shaping and path selection, the number of TS flows rejected for deterministic transmission starts increasing when every access network contains 1725 TS flows. Without path selection (i.e., all flows choose the path with a minimum number of hops), the number of rejected flows starts increasing when 1700 TS flows wait for scheduling in an access network. Moreover, with the same number of TS flows, the number of rejected flows is higher than the one using joint scheduling. Without traffic shaping, the scheduling starts to reject TS flows when there exist 1200 TS flows. The number of rejected flows starts to increase sharply when an access network contains 1500 TS flows. The rejection is severer than the joint scheduling and the scheduling without path selection. The result shows the traffic shaping and path selection can improve the throughput of TS flows, and  612  750  144  0  801  801  0  0  228.984  621  980  375  0  801  801  0  0  534.296  692  1173  567  26  801  801  0  0  697.856  847  2031  1426  402  801  801  0  0 the traffic shaping is the more important factor to improve the throughput. Due to traffic shaping can deploy flows to different transmission cycles, the conflict for transmission resources is reduced. However, because of the tree topology in access networks, all flows in the same access network have to pass through common CQF switches, which attenuate the influence of path selection. The increase of these three curves is not linear, because the newly added TS flows may have a high priority to be scheduled preferentially, and this will make the TS flows accepted formerly being rejected. Thus, the increase is not linear.

VI. CONCLUSION
To empower the end-to-end deterministic transmission, this paper proposes a hierarchical network that consists of the access networks and the core networks. In the access network, we use the CQF technique to ensure the deterministic transmission during the aggregation of the traffic from hosts. In the core network, DIP is exploited for the long-distance deterministic transmission over the backbone links. The endto-end deterministic transmissions are realized by the cycle alignment and traffic shaping at the network edge. Moreover, a joint scheduling approach is also formulated to improve the network throughput. Simulations results based on the realworld networks from sndlib show that the proposed network can achieve a deterministic transmission even in the high-load scenarios.