求解菊花链拓扑 TSN 的无等待调度问题

1] \orgdiv Shenzhen lnternational Center For Industrial And Applied Mathematics, \orgname Shenzhen Research Institute of Big Data, \orgaddress \city Shenzhen, \country China

2] \orgname CRRC, Zhuzhou Institute, \orgaddress \city Zhuzhou, \country China

3] \orgname Tengen Intelligence Institute, \orgaddress \city Zhuzhou, \country China

4] \orgname South China University of Technology, \orgaddress \city Guangzhou, \country China

MSC Classification]90B35, 90C27, 05C15

In recent years, the rapid advancement of communication technologies has revolutionized various industries, enabling the development of complex systems with demanding real-time requirements. From industrial automation, in-vehicle communication, and avionics to multimedia streaming and telecommunication networks, there is an increasing need for reliable and deterministic communication to ensure the timely delivery of critical data. In particular, one central characterization of Industry 4.0 paradigm is networked cyber-physical systems, where computers control physical processes. So a real-time communication network with deterministically bounded network delay and jitter is usually needed to guarantee the physical system under control.

Time-Sensitive Networking (TSN) has emerged as a set of standards to address these requirements and provide a unified solution for time-sensitive applications over Ethernet networks. TSN represents a significant evolution of traditional Ethernet, which was primarily designed for best-effort communication without any guarantees on timing or determinism. TSN is a suite of standards developed by the Institute of Electrical and Electronics Engineers (IEEE) 802.1 working group, and its main objective is to enable deterministic and predictable communication over Ethernet networks. To achieve the objective, TSN introduces several features and enhancements to traditional Ethernet, including time synchronization, traffic shaping and scheduling, and stream reservation.

More specifically, TSN incorporates precise clock synchronization protocols, such as IEEE 1588 [ 1 ] or IEEE802.1AS [ 2 ], to achieve tight synchronization (up to nanoseconds precision) of switches and end stations in a network, which ensures that all the devices are able to coordinate their actions and thus allows scheduling of streams across the switched network. End stations inject data streams into the switched network at precise predetermined time points based on a schedule. Then streams pass through switches and reach their respective destinations. The destination of a stream must be an end station. The routing paths of streams are a predefined part of the input and are fixed. A switch supports multiple priority queues per egress port. Each queue has a so-called gate, and whether the gate is opening or closed determines whether this queue can access the medium. The opening and closing of the gates of an egress port are controlled by a so-called Gate Control List (GCL), which is also predetermined according to a schedule.

However, the standards of TSN do not configure the scheduling. In fact, it is the main open problem around TSN how to compute a schedule that coordinates the injection times for all streams and the GCLs of switches to ensure the requested real-time requirements of all time-triggered traffic (a.k.a. scheduled traffic) are met. It turns out that deciding whether there is a valid schedule for a given set of streams is a very difficult combinatorial optimization problem: it is NP-hard even when restricted to various special classes of instances [ 3 ]. The scheduling algorithms in the literature can be classified into exact approaches and heuristic approaches. The exact approaches express the scheduling problem as a satisfiability modulo theory (SMT) problem, an integer linear programming (ILP) problem, or a constraint programming (CP) problem, etc, and then invoke the corresponding solver to find the optimal solution. The exact approaches would compute an optimal schedule if one exists, but they are not scalable beyond very small problem instances. Besides the exact approaches, many heuristic algorithms have been developed to try to find reasonably good schedules within a short time, such as the algorithms based on Tabu search [ 4 ] or simulated annealing [ 5 ]. However, in the common case, the heuristic approaches cannot deduce whether a problem instance is infeasible, nor are guaranteed to find a solution if one exists. See e.g. [ 3 ] for an excellent survey of scheduling algorithms in TSN. In summary, the existing scheduling algorithms are either poorly scalable or suboptimal.

In contrast to previous works designing general-purposed scheduling algorithms but without theoretical guarantees, this paper takes a different approach: it aims to develop algorithms with theoretical guarantees for a special kind of scenarios, which however still covers a notable proportion of real-life scenarios. Precisely, we focus on no-wait scheduling of time-triggered streams in TSN with daisy-chain topology.

The daisy-chain topology (a.k.a. the line topology, see Figure 1 for an illustration) is one of the most commonly used topologies and also the simplest and cheapest topologies to implement, and can be found in several real-life TSN systems such as the ones equipped on trains.

In a no-wait schedule, streams are not allowed to wait in switches, and a switch must forward a stream to the next node immediately upon receiving the stream. The rationale of the no-wait constraint is that both the network delay and jitter of all streams are minimized simultaneously since no queuing delay occurs. No-wait schedules are particularly suitable for extremely high real-time requirements. Durr and Nayak [ 4 ] presented a Tabu Search algorithm to compute no-wait schedules, where they model the no-wait scheduling problem as the well-known no-wait job-shop scheduling problem. Wang et al. [ 6 ] proposed a reinforcement learning method for no-wait scheduling, where they train machine learning models aiming to reduce the maximum arrival time among all frames. Both of the above two methods are heuristic and thus are suboptimal in the common case. Moreover, they are not scalable beyond medium-size problem instances: the method in [ 4 ] needs about 3 hours to compute schedules for about 1500 streams, and the one in [ 6 ] needs about 400 seconds to compute schedules for 100 streams in a network with 9 switches and 10 end stations.

Our Contribution. In this paper, we propose an efficient algorithm (Algorithm 1) that optimally computes no-wait schedules on the daisy-chain topology (a.k.a. the line topology). Precisely, given a set of streams to be transmitted in TSN with a daisy-chain topology, Algorithm 1 returns a no-wait schedule if one exists or proves that no such no-wait schedules exist, in O ​ ((n + | 𝒮 |) ⋅ | 𝒮 | 1.5 ​ log 2 ⁡ p 𝒮 + | 𝒮 | ⋅ p 𝒮 ​ log 2 ⁡ p 𝒮) O((n+|\mathcal{S}|)\cdot|\mathcal{S}|^{1.5}\log_{2}p_{\mathcal{S}}+|\mathcal{S}|\cdot p_{\mathcal{S}}\log_{2}p_{\mathcal{S}}) time. Here, | 𝒮 | |\mathcal{S}| is the number of streams, n n is the length of the daisy chain, and p 𝒮 p_{\mathcal{S}} is the least common multiple of the periods of streams in 𝒮 \mathcal{S} (a.k.a. hyperperiod of 𝒮 \mathcal{S}). Evaluations based on a real-life TSN network (with 32 switches) show that Algorithm 1 can compute schedules for about 45,000 flows in only about 30 minutes. Moreover, if we only care about whether there exist no-wait schedules or not, then it can be decided in O ​ (| 𝒮 | ⋅ n) O(|\mathcal{S}|\cdot n) time (Corollary 4.6).

Our basic idea is that the no-wait scheduling problem can be recast as a variant of a graph coloring problem where some restrictions are imposed on the colors available for every vertex. Since the topology is the daisy chain, the underlying graph is an interval graph. Our main technical part is to show that this variant of graph coloring problem can be solved in polynomial time for interval graphs, though it is NP-hard for general graphs.

Organization. The rest of this paper is organized as follows. We provide some details about TSN relevant to this paper in Section 2, and then some notations and the mathematical model in Section 3. In Section 4, we present the algorithms and the analysis. We present evaluation results in Section 5, and conclude the paper in Section 6.

According to the IEEE 802.1Qbv standards, a Time-Sensitive Network consists of network elements (i.e., switches and end stations) and a Central Network Controller (CNC) for configuring and managing the network. In this paper, we focus on scheduling time-triggered traffic (a.k.a. scheduled traffic), which consists of periodic data streams with hard real-time requirements. A time-triggered stream is specified by its source device, destination device, routing path, period, and amount of data per period. These properties of all streams are a part of the input to scheduling algorithms. Besides, the source device and destination device of each stream must be end stations.

The transit of time-trigger streams in TSN is scheduled by specifying (i) the injection time of each stream and (ii) the Gate Control List (GCL) of each egress port of switches. Precisely, the schedule is executed periodically for an indefinite number of times. The injection time of a stream is the relative time to the start of the scheduled period to be injected into the network. Each egress port of a switch has multiple queues, and each queue has a so-called gate. When the gate is in the open state, data in the queue is considered for transmission. The opening and closing of the gates of an egress port are controlled by a GCL. A GCL entry consists of two parts: a time interval [ T i, T i + 1 ] [T_{i},T_{i+1}], and a bit string indicating which gates are open or closed in the time interval [ T i, T i + 1 ] [T_{i},T_{i+1}]. Typically, the GCLs of all egress ports are programmed with the same period as the schedule. See Figure 2 for an illustration of GCL. In addition, in contrast with egress ports, an ingress port is capable of receiving multiple streams simultaneously.

Scheduling would be simplified when we restrict our attention to no-wait scheduling: we only need to specify the injection time of each stream. Precisely, noting that streams cannot be scheduled to wait at closed gates, we can deploy any no-wait schedule by opening all gates all the time.

In this paper, we assume that for all streams and all switches, the time that the switch forwards the stream (i.e., from when the switch receives the first bit of the stream to when the next node receives the first bit) is the same and set to be 1 unit time. The forwarding time consists of transmission time and several types of delays, namely the propagation delay of signals along the link, the processing delay for deciding on which port to forward an incoming packet, and the queuing delay of a packet in the queue of an outgoing port (which is zero in no-wait schedules). The forwarding time interval of two streams by the same egress port could overlap slightly, but the transmission time interval must not since otherwise their electrical signals would interfere. Here, we impose that the forwarding time interval of two streams by the same egress port must not overlap. This imposed restriction will make things much simpler, with decreasing little capacity of TSN because all the delays are much smaller than the transmission time. Finally, we remark that the assumption of the same forwarding time is reasonable, since (a) the forwarding time is mainly determined by the packet size and the link bandwidth; (b) the packet sizes and the bandwidth of links respectively are usually similar in practical TSN; and (c) large packets can be split into multiple small unit-forwarding-time packets.

In this section, we present the mathematical model of the no-wait scheduling problem for TSN with a daisy-chain topology and recast it to a variant of graph coloring problem with some restrictions on the colors available for every vertex (see Theorem 3.1).

For two integers a ≤ b a\leq b, define [ a, b ]:= { a, a + 1 ​ ⋯, b } [a,b]:=\{a,a+1\cdots,b\}. As shorthand, we write [ n ] [n] for [ 1, n ] = { 1, 2, ⋯, n } [1,n]=\{1,2,\cdots,n\}. Figure 1 illustrates the daisy-chain topology. In Figure 1, there are n n switches wired together in sequence, and named by SW 1, SW 2, ⋯, SW n \mathrm{SW}_{1},\mathrm{SW}_{2},\cdots,\mathrm{SW}_{n} from left to right. We use P i, i + 1 P_{i,i+1} to denote the right egress port of SW i \mathrm{SW}_{i}, which sends data from SW i \mathrm{SW}_{i} to SW i + 1 \mathrm{SW}_{i+1}, and use P i, i − 1 P_{i,i-1} to denote the left egress port of SW i \mathrm{SW}_{i}, which sends data from SW i \mathrm{SW}_{i} to SW i − 1 \mathrm{SW}_{i-1}. Let ℰ ​ [ i ] \mathcal{E}[i] denote the set of end stations directly connected with SW i \mathrm{SW}_{i}. For example, in Figure 1, ℰ ​ [ 1 ] = { E ​ S 1, E ​ S 2 } \mathcal{E}[1]=\{ES_{1},ES_{2}\} and ℰ ​ [ 2 ] = { E ​ S 3, E ​ S 4, E ​ S 5 } \mathcal{E}[2]=\{ES_{3},ES_{4},ES_{5}\}.

We use 𝒮 \mathcal{S} to denote the set of data streams to be scheduled. For a stream s ∈ 𝒮 s\in\mathcal{S}, let p s ∈ ℕ p_{s}\in\mathbb{N} denote the period of s s (i.e, the period of s s is p s p_{s} units time), and define a s, b s ∈ [ n ] a_{s},b_{s}\in[n] such that s s is sent from an end station in ℰ ​ [ a s ] \mathcal{E}[a_{s}] to another one in ℰ ​ [ b s ] \mathcal{E}[b_{s}]. We focus on streams where a s ≠ b s a_{s}\neq b_{s}. According to whether a s > b s a_{s}>b_{s} or not, we divide 𝒮 \mathcal{S} into two groups: (i) one group consists of all streams s ∈ 𝒮 s\in\mathcal{S} that goes from right to left, i.e., a s > b s a_{s}>b_{s}; and (ii) the other group consists of all streams s ∈ 𝒮 s\in\mathcal{S} that goes in the reverse direction, i.e., a s < b s a_{s}<b_{s}. Transmission of these two groups involves different egress ports and thus can be scheduled separately. So, for convenience of presentation, we assume a s < b s a_{s}<b_{s} for any s ∈ 𝒮 s\in\mathcal{S}. Note that s s will go through the egress ports P a s, a s + 1, P a s + 1, a s + 2, ⋯, P b s − 1, b s P_{a_{s},a_{s}+1},P_{a_{s}+1,a_{s}+2},\cdots,P_{b_{s}-1,b_{s}} in order.

one group consists of all streams s ∈ 𝒮 s\in\mathcal{S} that goes from right to left, i.e., a s > b s a_{s}>b_{s}; and

the other group consists of all streams s ∈ 𝒮 s\in\mathcal{S} that goes in the reverse direction, i.e., a s < b s a_{s}<b_{s}.

Let p 𝒮 p_{\mathcal{S}} denote the hyperperiod of 𝒮 \mathcal{S}, which is defined to be the least common multiple 𝖫𝖢𝖬 (p s: s ∈ 𝒮) \mathsf{LCM}(p_{s}:s\in\mathcal{S}) of the periods of streams in 𝒮 \mathcal{S}. A no-wait schedule is executed periodically with the hyperperiod p 𝒮 p_{\mathcal{S}} as its period. A schedule for 𝒮 \mathcal{S} contains p 𝒮 / p s p_{\mathcal{S}}/p_{s} replications of s s, each having the hyperperiod as its period.

For each stream s ∈ 𝒮 s\in\mathcal{S}, we associate it with an interval ℐ s:= [ a s, b s − 1 ] \mathcal{I}_{s}:=[a_{s},b_{s}-1]. Furthermore, we associate 𝒮 \mathcal{S} with an undirected graph G 𝒮 G_{\mathcal{S}} which (i) has a vertex v s v_{s} for each stream s ∈ 𝒮 s\in\mathcal{S} and (ii) has an edge (v s, v s ′) (v_{s},v_{s^{\prime}}) if and only if ℐ s ∩ ℐ s ′ ≠ ∅ \mathcal{I}_{s}\cap\mathcal{I}_{s^{\prime}}\neq\emptyset (i.e., the transmission of s s and s ′ s^{\prime} would use a common egress port). A useful observation is that G 𝒮 G_{\mathcal{S}} is an interval graph. In addition, we associate 𝒮 \mathcal{S} with another undirected graph G 𝒮 ⋆ G^{\star}_{\mathcal{S}} which (i) has p 𝒮 / p s p_{\mathcal{S}}/p_{s} vertices v s 1, ⋯, v s p 𝒮 / p s v_{s}^{1},\cdots,v_{s}^{p_{\mathcal{S}}/p_{s}} for each stream s ∈ 𝒮 s\in\mathcal{S} and (ii) has an edge (v s i, v s ′ j) (v^{i}_{s},v^{j}_{s^{\prime}}) if and only if ℐ s ∩ ℐ s ′ ≠ ∅ \mathcal{I}_{s}\cap\mathcal{I}_{s^{\prime}}\neq\emptyset. In other words, G 𝒮 ⋆ G_{\mathcal{S}}^{\star} is obtained from G 𝒮 G_{\mathcal{S}} by duplicating each v s v_{s} p 𝒮 / p s p_{\mathcal{S}}/p_{s} times. Note that G 𝒮 ⋆ G^{\star}_{\mathcal{S}} is also an interval graph. See Figure 3 (c)-(d) for an example of G 𝒮 G_{\mathcal{S}} and G 𝒮 ⋆ G^{\star}_{\mathcal{S}}.

has a vertex v s v_{s} for each stream s ∈ 𝒮 s\in\mathcal{S} and

has an edge (v s, v s ′) (v_{s},v_{s^{\prime}}) if and only if ℐ s ∩ ℐ s ′ ≠ ∅ \mathcal{I}_{s}\cap\mathcal{I}_{s^{\prime}}\neq\emptyset (i.e., the transmission of s s and s ′ s^{\prime} would use a common egress port).

has p 𝒮 / p s p_{\mathcal{S}}/p_{s} vertices v s 1, ⋯, v s p 𝒮 / p s v_{s}^{1},\cdots,v_{s}^{p_{\mathcal{S}}/p_{s}} for each stream s ∈ 𝒮 s\in\mathcal{S} and

has an edge (v s i, v s ′ j) (v^{i}_{s},v^{j}_{s^{\prime}}) if and only if ℐ s ∩ ℐ s ′ ≠ ∅ \mathcal{I}_{s}\cap\mathcal{I}_{s^{\prime}}\neq\emptyset.

A no-wait scheduling can be graphically described by a Gantt chart (see Figure 3 (e) for an example). Specifically, in the Gantt chart, • The horizontal axis corresponds to time and is divided into slots of 1 unit time. Recall that 1 unit time is the amount of time that a switch forwards a stream. • The vertical axis corresponds to the n − 1 n-1 egress ports P 1, 2, P 2, 3, ⋯, P n − 1, n P_{1,2},P_{2,3},\cdots,P_{n-1,n}. • A stream s s corresponds to b s − a s b_{s}-a_{s} horizontal bars, each lasting 1 unit time, stepping down from left to right (see Figure 3 (h) for examples). The “no-wait" restriction corresponds to that the finishing time of the previous bar is also the beginning time of the next bar. The Gantt chart can be viewed as a (n − 1) × ∞ (n-1)\times\infty dimensional table. We divide the table into parallelograms in the fashion shown in Figure 3 (f): each parallelogram consists of p 𝒮 p_{\mathcal{S}} layers, and each layer is defined to be a stepdown stair (Figure 3 (g) draws a layer). A crucial observation is that the bars of a stream are all contained in only one layer. So the no-wait scheduling is equivalent to packing the given set of stepdown-shape bars (e.g. the “tiles" in Figure 3 (h)) into a parallelogram, under the constraint that there is a replication of s s between the ((i − 1) ⋅ p s + 1) ((i-1)\cdot p_{s}+1) -th layer and the (i ⋅ p s) (i\cdot p_{s}) -th layer for all s s and i ∈ [ p 𝒮 / p s ] i\in[p_{\mathcal{S}}/p_{s}]. For example, Figure 3 (e) successfully packs the “titles" in Figure 3 (h) into a parallelogram, so a no-wait schedule exists.

The horizontal axis corresponds to time and is divided into slots of 1 unit time. Recall that 1 unit time is the amount of time that a switch forwards a stream.

The vertical axis corresponds to the n − 1 n-1 egress ports P 1, 2, P 2, 3, ⋯, P n − 1, n P_{1,2},P_{2,3},\cdots,P_{n-1,n}.

A stream s s corresponds to b s − a s b_{s}-a_{s} horizontal bars, each lasting 1 unit time, stepping down from left to right (see Figure 3 (h) for examples). The “no-wait" restriction corresponds to that the finishing time of the previous bar is also the beginning time of the next bar.

Inspired by the Gantt chart description, the no-wait scheduling can be recast in a variant of graph coloring problem where some restrictions are imposed on the colors available for every vertex. Precisely, recall that a proper q q -coloring of a graph G = (V, E) G=(V,E) is a function C: V → [ q ] C:V\rightarrow[q] such that no two adjacent vertices share the same color, i.e., C ​ (v) ≠ C ​ (v ′) C(v)\neq C(v^{\prime}) for any (v, v ′) ∈ E (v,v^{\prime})\in E. For a proper p 𝒮 p_{\mathcal{S}} -coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star}, we say it good if for each s ∈ 𝒮 s\in\mathcal{S} and each i ∈ [ p 𝒮 / p s ] i\in[p_{\mathcal{S}}/p_{s}], C ​ (v s i) ∈ [ (i − 1) ⋅ p s + 1, i ⋅ p s ] C(v_{s}^{i})\in[(i-1)\cdot p_{s}+1,i\cdot p_{s}]. Suppose G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a good p 𝒮 p_{\mathcal{S}} -coloring C C. Then we can get a no-wait schedule by placing the i i -th replication of s s in the C ​ (v s i) C(v_{s}^{i}) -th layer of the parallelogram. On the other hand, suppose 𝒮 \mathcal{S} admits a no-wait schedule, then we can obtain a good p 𝒮 p_{\mathcal{S}} -coloring C C of G 𝒮 ⋆ G_{\mathcal{S}}^{\star} by setting C ​ (v s i) C(v_{s}^{i}) to be the number of the layer containing the i i -th replication of s s. In summary, we have the following theorem.

There exists a no-wait schedule for 𝒮 \mathcal{S} if and only if there is a good p 𝒮 p_{\mathcal{S}} -coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star}. Furthermore, a no-wait schedule can be easily obtained from a good p 𝒮 p_{\mathcal{S}} -coloring.

By Theorem 3.1, the no-wait scheduling problem is equivalent to finding a good p 𝒮 p_{\mathcal{S}} -coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star}. In this section, we present an efficient algorithm to solve this variant of graph coloring problem, whose time complexity scales polynomially in both the number of streams and the network size.

We first consider the baby case where all streams have the same period, i.e., p s = p 𝒮 p_{s}=p_{\mathcal{S}} for any s ∈ 𝒮 s\in\mathcal{S}. In this case, G 𝒮 ⋆ G_{\mathcal{S}}^{\star} reduces to G 𝒮 G_{\mathcal{S}}, and every proper p s p_{s} -coloring of G 𝒮 G_{\mathcal{S}} is good. So the no-wait scheduling problem further reduces to finding a proper p s p_{s} -coloring of G 𝒮 G_{\mathcal{S}}. Recall that G 𝒮 G_{\mathcal{S}} is an interval graph. While the q q -coloring problem is a famous NP-complete problem for general graphs and general q q, it can be solved by a greedy algorithm in linear time for interval graphs [ 7 ]. So when all streams have the same period, the no-wait scheduling problem can be solved in linear time, i.e., O ​ (| 𝒮 | ​ log ⁡ | 𝒮 |) O(|\mathcal{S}|\log|\mathcal{S}|) time.

Now, we consider the general case, where streams have different periods. Here, we impose that each p s p_{s} must be a power of two, i.e., p s = 2 k p_{s}=2^{k} for some non-negative integer k k. On one hand, this imposed restriction does not lose much generality, since any p s ∈ ℕ p_{s}\in\mathbb{N} can be approximated by some 2 k 2^{k} up to factor at most 2 ≈ 1.414 \sqrt{2}\approx 1.414. On the other hand, it seems that this imposed restriction makes the no-wait scheduling problem tractable: the no-wait scheduling problem can be solved efficiently under this imposed restriction (as we will see later), whereas we are not aware of and haven’t come up with any algorithm computing no-wait schedules for general p s p_{s} with a time complexity that scales polynomially in both the number of streams and the network size.

In the following, we present our scheduling algorithm. We first introduce some notations. Define k ∗:= max s ∈ 𝒮 ⁡ log 2 ⁡ p s k^{\ast}:=\max_{s\in\mathcal{S}}\log_{2}p_{s}. Note that k ∗ k^{\ast} is a non-negative integer and the hyperperiod p 𝒮 = 2 k ∗ p_{\mathcal{S}}=2^{k^{\ast}}. For 0 ≤ k ≤ k ∗ 0\leq k\leq k^{\ast}, let 𝒮 k = { s ∈ 𝒮 ∣ p s = 2 k } \mathcal{S}_{k}=\{s\in\mathcal{S}\mid p_{s}=2^{k}\} denote the subset of 𝒮 \mathcal{S} consisting of all streams with period 2 k 2^{k}. Define 𝒮 ≤ k = 𝒮 1 ∪ ⋯ ∪ 𝒮 k \mathcal{S}_{\leq k}=\mathcal{S}_{1}\cup\cdots\cup\mathcal{S}_{k}. Note that 𝒮 = 𝒮 1 ∪ 𝒮 2 ∪ ⋯ ∪ 𝒮 k ∗ = 𝒮 ≤ k ∗ \mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{2}\cup\cdots\cup\mathcal{S}_{k^{\ast}}=\mathcal{S}_{\leq k^{\ast}}.

Given a partition 𝒮 k ∗ = 𝒮 k ∗ a ∪ 𝒮 k ∗ b \mathcal{S}_{k^{\ast}}=\mathcal{S}_{k^{\ast}}^{a}\cup\mathcal{S}_{k^{\ast}}^{b} of 𝒮 k ∗ \mathcal{S}_{k^{\ast}}, where 𝒮 k ∗ a ∩ 𝒮 k ∗ b = ∅ \mathcal{S}_{k^{\ast}}^{a}\cap\mathcal{S}_{k^{\ast}}^{b}=\emptyset, we define 𝒮 a:= 𝒮 ≤ k ∗ − 1 ∪ 𝒮 k ∗ a ^ \mathcal{S}^{a}:=\mathcal{S}_{\leq k^{\ast}-1}\cup\widehat{\mathcal{S}_{k^{\ast}}^{a}} (1) and 𝒮 b:= 𝒮 ≤ k ∗ − 1 ∪ 𝒮 k ∗ b ^. \mathcal{S}^{b}:=\mathcal{S}_{\leq k^{\ast}-1}\cup\widehat{\mathcal{S}_{k^{\ast}}^{b}}. (2) Here, 𝒮 k ∗ a ^ \widehat{\mathcal{S}_{k^{\ast}}^{a}} (and 𝒮 k ∗ b ^ \widehat{\mathcal{S}_{k^{\ast}}^{b}} respectively) is obtained from 𝒮 k ∗ a \mathcal{S}_{k^{\ast}}^{a} (and 𝒮 k ∗ b \mathcal{S}_{k^{\ast}}^{b} respectively) by changing the period of its streams from 2 k ∗ 2^{k^{\ast}} to 2 k ∗ − 1 2^{k^{\ast}-1}. For example, if 𝒮 k ∗ a \mathcal{S}_{k^{\ast}}^{a} contains a stream s s with (a s, b s, p s) = (1, 4, 2 k ∗) (a_{s},b_{s},p_{s})=(1,4,2^{k^{\ast}}), then 𝒮 k ∗ a ^ \widehat{\mathcal{S}_{k^{\ast}}^{a}} contains a stream s ^ \hat{s} with (a s ^, b s ^, p s ^) = (1, 4, 2 k ∗ − 1) (a_{\hat{s}},b_{\hat{s}},p_{\hat{s}})=(1,4,2^{k^{\ast}-1}). Note that the hyperperiods of 𝒮 a \mathcal{S}^{a} and 𝒮 b \mathcal{S}^{b} are 2 k ∗ − 1 2^{k^{\ast}-1} rather than 2 k ∗ 2^{k^{\ast}}.

In addition, we can define G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} and G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star}. Note that G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} and G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star} have exactly one vertex v s 1 v_{s}^{1} for s s in 𝒮 k ∗ a ^ \widehat{\mathcal{S}_{k^{\ast}}^{a}} or 𝒮 k ∗ b ^ \widehat{\mathcal{S}_{k^{\ast}}^{b}}. We have the following lemma.

G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a good p 𝒮 p_{\mathcal{S}} -coloring if and only if there is a partition 𝒮 k ∗ = 𝒮 k ∗ a ∪ 𝒮 k ∗ b \mathcal{S}_{k^{\ast}}=\mathcal{S}_{k^{\ast}}^{a}\cup\mathcal{S}_{k^{\ast}}^{b} such that both G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} and G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star} admit good (p 𝒮 / 2) (p_{\mathcal{S}}/2) -colorings.

On one hand, suppose C: V ​ (G 𝒮 ⋆) → [ 2 k ∗ ] C:V\left(G_{\mathcal{S}}^{\star}\right)\rightarrow\left[2^{k^{\ast}}\right] is a good 2 k ∗ 2^{k^{\ast}} -coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star}. Note that G 𝒮 ⋆ G_{\mathcal{S}}^{\star} has exactly one vertex v s 1 v_{s}^{1} for each s ∈ 𝒮 k ∗ s\in\mathcal{S}_{k^{\ast}}. According to whether C ​ (v s 1) C(v_{s}^{1}) is in [ 1, 2 k ∗ − 1 ] [1,2^{k^{\ast}-1}] or [ 2 k ∗ − 1 + 1, 2 k ∗ ] [2^{k^{\ast}-1}+1,2^{k^{\ast}}], we get a partition 𝒮 k ∗ = 𝒮 k ∗ a ∪ 𝒮 k ∗ b \mathcal{S}_{k^{\ast}}=\mathcal{S}_{k^{\ast}}^{a}\cup\mathcal{S}_{k^{\ast}}^{b} where 𝒮 k ∗ a = { s ∈ 𝒮 k ∗ ∣ C ​ (v s 1) ∈ [ 1, 2 k ∗ − 1 ] } \mathcal{S}_{k^{\ast}}^{a}=\left\{s\in\mathcal{S}_{k^{\ast}}\mid C(v_{s}^{1})\in\left[1,2^{k^{\ast}-1}\right]\right\} and 𝒮 k ∗ b = { s ∈ 𝒮 k ∗ ∣ C ​ (v s 1) ∈ [ 2 k ∗ − 1 + 1, 2 k ∗ ] }. \mathcal{S}_{k^{\ast}}^{b}=\left\{s\in\mathcal{S}_{k^{\ast}}\mid C(v_{s}^{1})\in\left[2^{k^{\ast}-1}+1,2^{k^{\ast}}\right]\right\}. For G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star}, we define a coloring C a: V ​ (G 𝒮 a ⋆) → [ 1, 2 k ∗ − 1 ] C^{a}:V(G_{\mathcal{S}^{a}}^{\star})\rightarrow[1,2^{k^{\ast}-1}] as follows: for each vertex v s i v_{s}^{i} in G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star}, let C a ​ (v s i) = C ​ (v s i) C^{a}(v_{s}^{i})=C(v_{s}^{i}). One can easily check that C a C^{a} is good 2 k ∗ − 1 2^{k^{\ast}-1} -coloring of G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} by definition. For G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star}, we define a coloring C b: V ​ (G 𝒮 b ⋆) → [ 1, 2 k ∗ − 1 ] C^{b}:V(G_{\mathcal{S}^{b}}^{\star})\rightarrow[1,2^{k^{\ast}-1}] as follows: • for any s ∈ 𝒮 ≤ k ∗ − 1 s\in\mathcal{S}_{\leq k^{\ast}-1} and any 1 ≤ i ≤ 2 k ∗ − 1 / p s 1\leq i\leq 2^{k^{\ast}-1}/p_{s}, define C b ​ (v s i) = C ​ (v s i + (2 k ∗ − 1) / p s) − 2 k ∗ − 1; C^{b}(v_{s}^{i})=C\left(v_{s}^{i+(2^{k^{\ast}-1})/p_{s}}\right)-2^{k^{\ast}-1}; Here, we claim that C b ​ (v s i) C^{b}(v_{s}^{i}) is nonnegative and thus properly defined. Since C C is a good coloring, by definition, we have that for each s ∈ 𝒮 s\in\mathcal{S} and each i ∈ [ p 𝒮 / p s ] i\in[p_{\mathcal{S}}/p_{s}], C ​ (v s i) ∈ [ (i − 1) ⋅ p s + 1, i ⋅ p s ] C(v_{s}^{i})\in[(i-1)\cdot p_{s}+1,i\cdot p_{s}]. In particular, C ​ (v s i + (2 k ∗ − 1) / p s) − 2 k ∗ − 1 ∈ [ (i − 1) ⋅ p s + 1, i ⋅ p s ]. C\left(v_{s}^{i+(2^{k^{\ast}-1})/p_{s}}\right)-2^{k^{\ast}-1}\in[(i-1)\cdot p_{s}+1,i\cdot p_{s}]. • for any s ∈ 𝒮 k ∗ b s\in\mathcal{S}_{k^{\ast}}^{b}, define C b ​ (v s 1) = C ​ (v s 1) − 2 k ∗ − 1 C^{b}(v_{s}^{1})=C(v_{s}^{1})-2^{k^{\ast}-1}. One can easily check that C b C^{b} is good 2 k ∗ − 1 2^{k^{\ast}-1} -coloring of G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star} by definition.

for any s ∈ 𝒮 ≤ k ∗ − 1 s\in\mathcal{S}_{\leq k^{\ast}-1} and any 1 ≤ i ≤ 2 k ∗ − 1 / p s 1\leq i\leq 2^{k^{\ast}-1}/p_{s}, define C b ​ (v s i) = C ​ (v s i + (2 k ∗ − 1) / p s) − 2 k ∗ − 1; C^{b}(v_{s}^{i})=C\left(v_{s}^{i+(2^{k^{\ast}-1})/p_{s}}\right)-2^{k^{\ast}-1}; Here, we claim that C b ​ (v s i) C^{b}(v_{s}^{i}) is nonnegative and thus properly defined. Since C C is a good coloring, by definition, we have that for each s ∈ 𝒮 s\in\mathcal{S} and each i ∈ [ p 𝒮 / p s ] i\in[p_{\mathcal{S}}/p_{s}], C ​ (v s i) ∈ [ (i − 1) ⋅ p s + 1, i ⋅ p s ] C(v_{s}^{i})\in[(i-1)\cdot p_{s}+1,i\cdot p_{s}]. In particular, C ​ (v s i + (2 k ∗ − 1) / p s) − 2 k ∗ − 1 ∈ [ (i − 1) ⋅ p s + 1, i ⋅ p s ]. C\left(v_{s}^{i+(2^{k^{\ast}-1})/p_{s}}\right)-2^{k^{\ast}-1}\in[(i-1)\cdot p_{s}+1,i\cdot p_{s}].

for any s ∈ 𝒮 k ∗ b s\in\mathcal{S}_{k^{\ast}}^{b}, define C b ​ (v s 1) = C ​ (v s 1) − 2 k ∗ − 1 C^{b}(v_{s}^{1})=C(v_{s}^{1})-2^{k^{\ast}-1}.

On the other hand, suppose 𝒮 k ∗ = 𝒮 k ∗ a ∪ 𝒮 k ∗ b \mathcal{S}_{k^{\ast}}=\mathcal{S}_{k^{\ast}}^{a}\cup\mathcal{S}_{k^{\ast}}^{b} is a partition of 𝒮 k ∗ \mathcal{S}_{k^{\ast}}, and C a C^{a} and C b C^{b} are good 2 k ∗ − 1 2^{k^{\ast}-1} -colorings of G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} and G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star} respectively. We define a coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star} as follows: • for any s ∈ 𝒮 ≤ k ∗ − 1 s\in\mathcal{S}_{\leq k^{\ast}-1} and any 1 ≤ i ≤ 2 k ∗ / p s 1\leq i\leq 2^{k^{\ast}}/p_{s}, define C ​ (v s i) = { C a ​ (v s i), if ​ 1 ≤ i ≤ 2 k ∗ − 1 p s; C b ​ (v s i − 2 k ∗ − 1 p s) + 2 k ∗ − 1, if ​ 2 k ∗ − 1 p s + 1 ≤ i ≤ 2 k ∗ p s. \displaystyle C(v_{s}^{i})=\begin{cases}C^{a}(v_{s}^{i}),&\text{if }1\leq i\leq\frac{2^{k^{\ast}-1}}{p_{s}};\\ C^{b}\left(v_{s}^{i-\frac{2^{k^{\ast}-1}}{p_{s}}}\right)+2^{k^{\ast}-1},&\text{if }\frac{2^{k^{\ast}-1}}{p_{s}}+1\leq i\leq\frac{2^{k^{\ast}}}{p_{s}}.\end{cases} • for any s ∈ 𝒮 k ∗ a s\in\mathcal{S}_{k^{\ast}}^{a}, define C ​ (v s 1) = C a ​ (v s 1) C(v_{s}^{1})=C^{a}(v_{s}^{1}); • for any s ∈ 𝒮 k ∗ b s\in\mathcal{S}_{k^{\ast}}^{b}, define C ​ (v s 1) = C b ​ (v s 1) + 2 k ∗ − 1 C(v_{s}^{1})=C^{b}(v_{s}^{1})+2^{k^{\ast}-1}. One can check that C C is good 2 k ∗ 2^{k^{\ast}} -coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star} by definition. ∎

for any s ∈ 𝒮 ≤ k ∗ − 1 s\in\mathcal{S}_{\leq k^{\ast}-1} and any 1 ≤ i ≤ 2 k ∗ / p s 1\leq i\leq 2^{k^{\ast}}/p_{s}, define C ​ (v s i) = { C a ​ (v s i), if ​ 1 ≤ i ≤ 2 k ∗ − 1 p s; C b ​ (v s i − 2 k ∗ − 1 p s) + 2 k ∗ − 1, if ​ 2 k ∗ − 1 p s + 1 ≤ i ≤ 2 k ∗ p s. \displaystyle C(v_{s}^{i})=\begin{cases}C^{a}(v_{s}^{i}),&\text{if }1\leq i\leq\frac{2^{k^{\ast}-1}}{p_{s}};\\ C^{b}\left(v_{s}^{i-\frac{2^{k^{\ast}-1}}{p_{s}}}\right)+2^{k^{\ast}-1},&\text{if }\frac{2^{k^{\ast}-1}}{p_{s}}+1\leq i\leq\frac{2^{k^{\ast}}}{p_{s}}.\end{cases}

for any s ∈ 𝒮 k ∗ a s\in\mathcal{S}_{k^{\ast}}^{a}, define C ​ (v s 1) = C a ​ (v s 1) C(v_{s}^{1})=C^{a}(v_{s}^{1});

for any s ∈ 𝒮 k ∗ b s\in\mathcal{S}_{k^{\ast}}^{b}, define C ​ (v s 1) = C b ​ (v s 1) + 2 k ∗ − 1 C(v_{s}^{1})=C^{b}(v_{s}^{1})+2^{k^{\ast}-1}.

For 0 ≤ k ≤ k ∗ 0\leq k\leq k^{\ast} and ℓ ∈ [ n − 1 ] \ell\in[n-1], define c k, ℓ:= \displaystyle c_{k,\ell}:= 2 k − k ∗ ⋅ | { v s i ∈ V ​ (G 𝒮 ⋆) ∣ s ∈ 𝒮 ≤ k ​ and ​ ℓ ∈ ℐ s } | \displaystyle 2^{k-k^{\ast}}\cdot\left|\left\{v_{s}^{i}\in V(G_{\mathcal{S}}^{\star})\mid s\in\mathcal{S}_{\leq k}\mbox{ and }\ell\in\mathcal{I}_{s}\right\}\right| = \displaystyle= ∑ i = 0 k 2 k − i ⋅ | { s ∈ 𝒮 i ∣ ℓ ∈ ℐ s } |. \displaystyle\sum_{i=0}^{k}2^{k-i}\cdot|\{s\in\mathcal{S}_{i}\mid\ell\in\mathcal{I}_{s}\}|. In particular, c k ∗, ℓ = | { v s i ∈ V ​ (G 𝒮 ⋆) ∣ ℓ ∈ ℐ s } | c_{k^{\ast},\ell}=\left|\left\{v_{s}^{i}\in V(G_{\mathcal{S}}^{\star})\mid\ell\in\mathcal{I}_{s}\right\}\right|. The following theorem is the main technical part.

G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a good p 𝒮 p_{\mathcal{S}} -coloring if and only if c k ∗, ℓ ≤ 2 k ∗ c_{k^{\ast},\ell}\leq 2^{k^{\ast}} for any ℓ ∈ [ n − 1 ] \ell\in[n-1].

The proof is by induction on k ∗ k^{\ast}. When k ∗ = 0 k^{\ast}=0, the theorem is trivial. By induction, we assume the theorem holds when k ∗ = k ′ k^{\ast}=k^{\prime}, and we are going to show the theorem when k ∗ = k ′ + 1 k^{\ast}=k^{\prime}+1.

According to Lemma 4.1, G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a good 2 k ∗ 2^{k^{\ast}} -coloring if and only if there is a partition 𝒮 k ∗ = 𝒮 k ∗ a ∪ 𝒮 k ∗ b \mathcal{S}_{k^{\ast}}=\mathcal{S}_{k^{\ast}}^{a}\cup\mathcal{S}_{k^{\ast}}^{b} such that both G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} and G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star} admit good (2 k ∗ − 1) \big(2^{k^{\ast}-1}\big) -colorings. Remember that the hyperperiods of 𝒮 a \mathcal{S}^{a} and 𝒮 b \mathcal{S}^{b} are both 2 k ∗ − 1 2^{k^{\ast}-1}. So by the induction hypothesis, G 𝒮 a ⋆ G_{\mathcal{S}^{a}}^{\star} admit a good (2 k ∗ − 1) \big(2^{k^{\ast}-1}\big) -coloring if and only if c k ∗ − 1, ℓ + | { s ∈ 𝒮 k ∗ a ∣ ℓ ∈ ℐ s } | ≤ 2 k ∗ − 1 ​ for any ​ ℓ ∈ [ n − 1 ]. \displaystyle c_{k^{\ast}-1,\ell}+|\{s\in\mathcal{S}_{k^{\ast}}^{a}\mid\ell\in\mathcal{I}_{s}\}|\leq 2^{k^{\ast}-1}\mbox{ for any }\ell\in[n-1]. (3) Similarly, by the induction hypothesis, G 𝒮 b ⋆ G_{\mathcal{S}^{b}}^{\star} admit a good (2 k ∗ − 1) \big(2^{k^{\ast}-1}\big) -coloring if and only if c k ∗ − 1, ℓ + | { s ∈ 𝒮 k ∗ b ∣ ℓ ∈ ℐ s } | ≤ 2 k ∗ − 1 ​ for any ​ ℓ ∈ [ n − 1 ]. \displaystyle c_{k^{\ast}-1,\ell}+|\{s\in\mathcal{S}_{k^{\ast}}^{b}\mid\ell\in\mathcal{I}_{s}\}|\leq 2^{k^{\ast}-1}\mbox{ for any }\ell\in[n-1]. (4)

Define a Boolean vector 𝒙 = (x s: s ∈ 𝒮 k ∗) \boldsymbol{x}=(x_{s}:s\in\mathcal{S}_{k^{\ast}}) where x s = 0 x_{s}=0 indicates s ∈ 𝒮 k ∗ a s\in\mathcal{S}_{k^{\ast}}^{a} and x s = 1 x_{s}=1 indicates s ∈ 𝒮 k ∗ b s\in\mathcal{S}_{k^{\ast}}^{b}. Define a (n − 1) × | S k ∗ | (n-1)\times|S_{k^{\ast}}| Boolean matrix A A where A ​ [ ℓ, s ] = 1 ℓ ∈ ℐ s A[\ell,s]=1_{\ell\in\mathcal{I}_{s}}. That is, A ​ [ ℓ, s ] = 1 A[\ell,s]=1 if ℓ ∈ ℐ s \ell\in\mathcal{I}_{s} and A ​ [ ℓ, s ] = 0 A[\ell,s]=0 otherwise. Note that A (𝟏 − 𝒙) = (| { s ∈ 𝒮 k ∗ a ∣ ℓ ∈ ℐ s } |: ℓ ∈ [ n − 1 ]) A(\boldsymbol{1}-\boldsymbol{x})=\left(|\{s\in\mathcal{S}_{k^{\ast}}^{a}\mid\ell\in\mathcal{I}_{s}\}|:\ell\in[n-1]\right) and A 𝒙 = (| { s ∈ 𝒮 k ∗ b ∣ ℓ ∈ ℐ s } |: ℓ ∈ [ n − 1 ]), A\boldsymbol{x}=\left(|\{s\in\mathcal{S}_{k^{\ast}}^{b}\mid\ell\in\mathcal{I}_{s}\}|:\ell\in[n-1]\right), where 𝟏 \boldsymbol{1} is the all ones vector. Define a vector 𝒄 = (2 k ∗ − 1 − c k ∗ − 1, ℓ: ℓ ∈ [ n − 1 ]). \boldsymbol{c}=(2^{k^{\ast}-1}-c_{k^{\ast}-1,\ell}:\ell\in[n-1]). Then (3) and (4) can be rewritten as A ​ (𝟏 − 𝒙) ≤ 𝒄 A(\boldsymbol{1}-\boldsymbol{x})\leq\boldsymbol{c} and A ​ 𝒙 ≤ 𝒄 A\boldsymbol{x}\leq\boldsymbol{c} respectively. So we have the following claim.

G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a good p 𝒮 p_{\mathcal{S}} -coloring if and only if { A (𝟏 − 𝐱) ≤ 𝐜, A 𝐱 ≤ 𝐜, 𝟎 ≤ 𝐱 ≤ 𝟏, 𝐱 ∈ ℤ } ≠ ∅ \{A(\boldsymbol{1}-\boldsymbol{x})\leq\boldsymbol{c},A\boldsymbol{x}\leq\boldsymbol{c},\boldsymbol{0}\leq\boldsymbol{x}\leq\boldsymbol{1},\boldsymbol{x}\in\mathbb{Z}\}\neq\emptyset.

Noting that A A is a consecutive-ones matrix, i.e., the ones appearing consecutively in each column, we have that A A is a totally unimodular matrix [ 8 ]. So we get the following claim.

{ A (𝟏 − 𝒙) ≤ 𝒄, A 𝒙 ≤ 𝒄, 𝟎 ≤ 𝒙 ≤ 𝟏, 𝒙 ∈ ℤ } ≠ ∅ \{A(\boldsymbol{1}-\boldsymbol{x})\leq\boldsymbol{c},A\boldsymbol{x}\leq\boldsymbol{c},\boldsymbol{0}\leq\boldsymbol{x}\leq\boldsymbol{1},\boldsymbol{x}\in\mathbb{Z}\}\neq\emptyset if and only if { A ​ (𝟏 − 𝐱) ≤ 𝐜, A ​ 𝐱 ≤ 𝐜, 𝟎 ≤ 𝐱 ≤ 𝟏 } ≠ ∅ \{A(\boldsymbol{1}-\boldsymbol{x})\leq\boldsymbol{c},A\boldsymbol{x}\leq\boldsymbol{c},\boldsymbol{0}\leq\boldsymbol{x}\leq\boldsymbol{1}\}\neq\emptyset.

The following claim is crucial.

{ A ​ (𝟏 − 𝒙) ≤ 𝒄, A ​ 𝒙 ≤ 𝒄, 𝟎 ≤ 𝒙 ≤ 𝟏 } ≠ ∅ \{A(\boldsymbol{1}-\boldsymbol{x})\leq\boldsymbol{c},A\boldsymbol{x}\leq\boldsymbol{c},\boldsymbol{0}\leq\boldsymbol{x}\leq\boldsymbol{1}\}\neq\emptyset if and only if A ⋅ 𝟏 ≤ 2 ​ 𝐜 A\cdot\boldsymbol{1}\leq 2\boldsymbol{c}.

For convenience of presentation, let ℱ:= { A ​ (𝟏 − 𝒙) ≤ 𝒄, A ​ 𝒙 ≤ 𝒄, 𝟎 ≤ 𝒙 ≤ 𝟏 } \mathcal{F}:=\{A(\boldsymbol{1}-\boldsymbol{x})\leq\boldsymbol{c},A\boldsymbol{x}\leq\boldsymbol{c},\boldsymbol{0}\leq\boldsymbol{x}\leq\boldsymbol{1}\}. On one direction, if A ⋅ 𝟏 ≤ 2 ​ 𝒄 A\cdot\boldsymbol{1}\leq 2\boldsymbol{c}, then 1 2 ⋅ 𝟏 ∈ ℱ \frac{1}{2}\cdot\boldsymbol{1}\in\mathcal{F}, so ℱ ≠ ∅ \mathcal{F}\neq\emptyset. On the other direction, suppose 𝒙 ∗ ∈ ℱ \boldsymbol{x}^{\ast}\in\mathcal{F}. Then (𝟏 − 𝒙 ∗) ∈ ℱ (\boldsymbol{1}-\boldsymbol{x}^{\ast})\in\mathcal{F}. Because ℱ \mathcal{F} is a convex set, 𝒙 ∗ / 2 + (𝟏 − 𝒙 ∗) / 2 = 1 2 ⋅ 𝟏 ∈ ℱ \boldsymbol{x}^{\ast}/2+(\boldsymbol{1}-\boldsymbol{x}^{\ast})/2=\frac{1}{2}\cdot\boldsymbol{1}\in\mathcal{F}, which implies that A ⋅ 𝟏 ≤ 2 ​ 𝒄 A\cdot\boldsymbol{1}\leq 2\boldsymbol{c}. ∎

Finally, A ⋅ 𝟏 ≤ 2 ​ 𝒄 A\cdot\boldsymbol{1}\leq 2\boldsymbol{c} means that | { s ∈ 𝒮 k ∗ ∣ ℓ ∈ ℐ s } | ≤ 2 k ∗ − 2 ​ c k ∗ − 1, ℓ ​ for any ​ ℓ ∈ [ n − 1 ], \displaystyle|\{s\in\mathcal{S}_{k^{\ast}}\mid\ell\in\mathcal{I}_{s}\}|\leq 2^{k^{\ast}}-2c_{k^{\ast}-1,\ell}\mbox{ for any }\ell\in[n-1], which is equivalent to saying: for any ℓ ∈ [ n − 1 ] \ell\in[n-1], c k ∗, ℓ = 2 ​ c k ∗ − 1, ℓ + | { s ∈ 𝒮 k ∗ ∣ ℓ ∈ ℐ s } | ≤ 2 k ∗ \displaystyle c_{k^{\ast},\ell}=2c_{k^{\ast}-1,\ell}+|\{s\in\mathcal{S}_{k^{\ast}}\mid\ell\in\mathcal{I}_{s}\}|\leq 2^{k^{\ast}} The conclusion follows from Claims 4.3, 4.4, and 4.5 immediately. ∎

It is a basic fact that an interval graph admits a proper k k -coloring if and only if it contains no clique of size greater than k k. Thus G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a proper 2 k ∗ 2^{k^{\ast}} -coloring if and only if c k ∗, ℓ ≤ 2 k ∗ c_{k^{\ast},\ell}\leq 2^{k^{\ast}} for any ℓ ∈ [ n − 1 ] \ell\in[n-1]. So G 𝒮 ⋆ G_{\mathcal{S}}^{\star} admits a proper 2 k ∗ 2^{k^{\ast}} -coloring if and only if it admits a good 2 k ∗ 2^{k^{\ast}} -coloring.

Note that all c k ∗, ℓ = ∑ i = 0 k ∗ 2 k ∗ − i ⋅ | { s ∈ 𝒮 i ∣ ℓ ∈ ℐ s } | c_{k^{\ast},\ell}=\sum_{i=0}^{k^{\ast}}2^{k^{\ast}-i}\cdot|\{s\in\mathcal{S}_{i}\mid\ell\in\mathcal{I}_{s}\}| can be computed in O ​ (| 𝒮 | ⋅ n) O(|\mathcal{S}|\cdot n) time. By Theorem 4.2 and 3.1, we have

It can be decided in O ​ (| 𝒮 | ⋅ n) O(|\mathcal{S}|\cdot n) time whether there exists a no-wait schedule for 𝒮 \mathcal{S}.

Furthermore, if no-wait schedule exists for 𝒮 \mathcal{S}, then the procedure 𝖥𝗂𝗇𝖽 ​ (𝒮, k ∗) \mathsf{Find}(\mathcal{S},k^{\ast}), described in Algorithm 2, would return a good 2 k ∗ 2^{k^{\ast}} -coloring of G 𝒮 ⋆ G_{\mathcal{S}}^{\star}, represented in the form of dictionary { (v s i, C ​ (v s i)) } \{(v_{s}^{i},C(v_{s}^{i}))\}. Given a good 2 k ∗ 2^{k^{\ast}} -coloring C: V ​ (G 𝒮 ⋆) → [ 2 k ∗ ] C:V\left(G_{\mathcal{S}}^{\star}\right)\rightarrow\left[2^{k^{\ast}}\right] of G 𝒮 ⋆ G_{\mathcal{S}}^{\star}, we can easily get a no-wait schedule by placing the i i -th replication of s s in the C ​ (v s i) C(v_{s}^{i}) -th layer of the parallelogram, i.e., by setting the injection time of the i i -th replication of s s to be C ​ (v s i) + a s − 1 C(v_{s}^{i})+a_{s}-1.

Algorithm 1 solves the no-wait scheduling problem in O ​ ((n + | 𝒮 |) ⋅ | 𝒮 | 1.5 ​ log 2 ⁡ p 𝒮 + | 𝒮 | ⋅ p 𝒮 ​ log 2 ⁡ p 𝒮) O((n+|\mathcal{S}|)\cdot|\mathcal{S}|^{1.5}\log_{2}p_{\mathcal{S}}+|\mathcal{S}|\cdot p_{\mathcal{S}}\log_{2}p_{\mathcal{S}}) time.

We first show the correctness of Algorithm 1. By Theorem 4.2 and 3.1, there exist no-wait schedules for 𝒮 \mathcal{S} if and only if c k ∗, ℓ ≤ 2 k ∗ c_{k^{\ast},\ell}\leq 2^{k^{\ast}} for any ℓ ∈ [ n − 1 ] \ell\in[n-1]. Moreover, from the proof of Theorem 4.2, one can easily verify that the procedure 𝖥𝗂𝗇𝖽 ​ (𝒮, k ∗) \mathsf{Find}(\mathcal{S},k^{\ast}) would return a no-wait schedule if one exists. So Algorithm 1 returns a no-wait schedule if one exists or returns “no-wait schedules do not exist" otherwise.

What remains is to analyze the time complexity of Algorithm 1. It executes O ​ (| 𝒮 | ⋅ n) O(|\mathcal{S}|\cdot n) time to execute Lines 1-5. In the following, we will show that it costs O ​ ((n + | 𝒮 |) ⋅ | 𝒮 | 1.5 ​ log 2 ⁡ p 𝒮 + | 𝒮 | ⋅ p 𝒮 ​ log 2 ⁡ p 𝒮) O((n+|\mathcal{S}|)\cdot|\mathcal{S}|^{1.5}\log_{2}p_{\mathcal{S}}+|\mathcal{S}|\cdot p_{\mathcal{S}}\log_{2}p_{\mathcal{S}}) time to run the procedure 𝖥𝗂𝗇𝖽 ​ (𝒮, k ∗) \mathsf{Find}(\mathcal{S},k^{\ast}), and then finish the proof.

Let T ​ (| 𝒮 |, k ∗) T(|\mathcal{S}|,k^{\ast}) denote the time complexity of 𝖥𝗂𝗇𝖽 ​ (𝒮, k ∗) \mathsf{Find}(\mathcal{S},k^{\ast}). First, it is easy to see that it costs O ​ (n ⋅ | 𝒮 |) O(n\cdot|\mathcal{S}|) time to execute Lines 1-13, 15-16, and 24-28. It costs O ​ ((n + | 𝒮 |) ⋅ | 𝒮 | 1.5) O((n+|\mathcal{S}|)\cdot|\mathcal{S}|^{1.5}) time to solve the linear programming in Line 14 [ 9 ], and costs O ​ (| 𝒮 | ⋅ 2 k ∗) = O ​ (| 𝒮 | ⋅ p 𝒮) O(|\mathcal{S}|\cdot 2^{k^{\ast}})=O(|\mathcal{S}|\cdot p_{\mathcal{S}}) time to execute Lines 18-23. In addition, it costs at most 2 ​ T ​ (| 𝒮 |, k ∗ − 1) 2T(|\mathcal{S}|,k^{\ast}-1) time to execute Line 17. So we have T ​ (| 𝒮 |, k ∗) ≤ 2 ​ T ​ (| 𝒮 |, k ∗ − 1) + O ​ ((n + | 𝒮 |) ⋅ | 𝒮 | 1.5 + | 𝒮 | ⋅ p 𝒮). T(|\mathcal{S}|,k^{\ast})\leq 2T(|\mathcal{S}|,k^{\ast}-1)+O((n+|\mathcal{S}|)\cdot|\mathcal{S}|^{1.5}+|\mathcal{S}|\cdot p_{\mathcal{S}}). By solving the above recursion, we have T ​ (| 𝒮 |, k ∗) = O ​ ((n + | 𝒮 |) ⋅ | 𝒮 | 1.5 ​ log 2 ⁡ p 𝒮 + | 𝒮 | ⋅ p 𝒮 ​ log 2 ⁡ p 𝒮). ∎ T(|\mathcal{S}|,k^{\ast})=O((n+|\mathcal{S}|)\cdot|\mathcal{S}|^{1.5}\log_{2}p_{\mathcal{S}}+|\mathcal{S}|\cdot p_{\mathcal{S}}\log_{2}p_{\mathcal{S}}).\qed

We present the evaluations of Algorithm 1 for time-sensitive networks to demonstrate optimality and high scalability.

Qualitative Evaluations. The qualitative evaluations are conducted on a real-life TSN system equipped on a metro train, where sensors across the train collect the status data of the train and then send data to controllers, which in turn send commands to actuators to keep the state of the train close to the desired setpoint. The topology is described in Figure 4. Here, the controller is located in Carriage 1, and most of the streams go from the other carriages to Carriage 1 or in the reverse direction. To verify the optimality of Algorithm 1, we compared the schedules computed using Algorithm 1 to the ones generated by an SAT Modulo Theory (SMT) solver which exactly solves the SMT formulation of the corresponding problem [ 3 ]. Note that the SMT solver is poorly scalable and can only solve small instances with up to about 300 flows in 1 hour.

We executed our evaluations in 10 practical scenarios on the topology in Figure 4 with respectively 3, 8, 40, 128, and 256 flows. We configured the SMT solver with a time limit of 1 hour for solving each scenario. Then we also run Algorithm 1 on the same instance. The evaluation shows that the SMT solver returns a no-wait scheduling if and only if Algorithm 1 returns one. Besides, the average execution time of the SMT solver on these instances is about 3 minutes, while Algorithm 1 solves these instances in 2 seconds on average.

Scalability Evaluations. To determine the scalability of Algorithm 1, we measure the averaged execution times of Algorithm 1 with up to tens of thousands of flows on a personal computer (multi-processor machine (Intel(R) Core(TM) CPU i5- 12500H @ 2.50GHz) with 4P + 8E cores and 16 GB of memory). Precisely, we run Algorithm 1 on randomized instances with varying numbers of flows on the daisy-chain topology with varying lengths. The evaluation results show that Algorithm 1 can compute schedules for about 45,000 flows in only about 30 minutes.

In this paper, we propose an efficient algorithm to compute no-wait schedules on the daisy-chain topology, with a time complexity that scales polynomially in both the number of streams and the network size. The basic idea is to view the scheduling problem as a variant of graph coloring problem on the interval graphs. Our algorithm is proven to be optimal, and evaluations on real-life TSN systems justify the high scalability. In our future work, we plan to investigate other commonly used topologies, such as the star topology, cycle topology, and tree topology.