## 5 TSN Scheduling Problem Formulation
### TSN Scheduling Problem Constraints  
An important part of the TSN scheduling problem formulation is to identify constraints that limit the search space to only the feasible solutions. Optimally, the search space is equal to the solution space, i.e., every viable assignment fulfills all the constraints. Consequently, reducing the number of constraints eases the finding of an optimal solution. Nevertheless, different works use different constraints that are convenient for their formulation. In this section, we revisit the constraints used in the surveyed literature, classify them, and aim to analyze their coexistence in the different works. Although the specific set of constraints depends on the problem formulation, we can identify the following classes:  
1. **Constraints on the streams:** This set of constraints aims to look at the interaction between the streams and the network. From one side, each stream individually has a set of requirements from the network (i.e., requirements on latency, jitter, periodicity, and reliability) and from another side, all the streams impose more requirements collectively (i.e., dependency between streams, and sharing of the network resources considering all the streams). 1. MaxLatency constraint [11, 14, 24, 31, 32, 33, 35, 38, 40, 41, 42, 44, 46, 47, 48, 49, 50, 54, 60, 62, 63, 65, 69, 70, 72, 74, 76, 77, 77, 78, 84, 86, 87, 88, 90, 92, 94, 95, 96, 9  
* Interstream dependency constraint [47, 49, 54, 86, 119, 121]: This is required in case application embedding in the end-hosts is considered a part of the scheduling problem. This constraint is useful for use cases that involve service chaining. * **Constraints on the queues:*
* This set of constraints aims to look at the configuration of the queues in order to enforce a certain queuing discipline. * Allocation constraint [41, 74, 97, 116, 118, 122, 47]: This ensures that the traffic classes are properly allocated in the right priority queue (e.g., exclusive queue allocation introduced in [116]). * Accessibility constraint [24, 31, 35, 38, 41, 42, 44, 46, 50, 58, 71, 74, 79, 82, 84, 86, 87, 92, 97, 102, 105, 109, 116, 117, 118, 120, 122]: This controls the order of frames in the queues or limits the access of the different frames/flows to a certain queue. This constraint is also called isolation constraint in the literature and it has different variations, e.g., frame isolation, flow isolation [38], and size-based isolation [116]. * Zero-queueing constraint [98, 72, 99, 117]: This forbids the HTS frames to be queued in order to minimize latency and/or jitter. * **Constraints on the frames:*
* This set of constraints aims to look at frame-related aspects concerning its specifications (e.g., size), its relation with other frames (e.g., sequencing of frames), and its relation with the network (e.g., path). * Sequencing constraints [24, 72, 78, 87, 95, 98, 116, 121, 122]: These ensure that reordering of frames belonging to same stream will not occur in the network. * MaxSize constraint [37, 79, 84, 123]: This limits the maximum allowed size of the frames. * Routing constraints [14, 29, 30, 37, 38, 40, 42, 47, 49, 50, 58, 59, 60, 67, 69, 70, 72, 74, 78, 79, 84, 87, 98, 101, 104, 106, 109, 110, 111, 122, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]: This constraint is used to enforce certain routing rules on the frames, e.g., to prevent loops in the path, to limit the number of hops in the path, or to ensure the frames belonging to the same stream follow the same path. This constraint could be applied to scheduling problem with fixed paths. * **Constraints on the transmission windows:*
* This set of constraints aims to look at the transmission of frames in the link. It concerns the start and the end of transmission, and the spacing between consecutive transmissions.