## 4 TSN Network-Wide Scheduling--Approaches Overview, Challenges, and Future Directions
### Methods and Approaches for Scheduling in TSN  
The scheduling problem in TSN aims to find the proper paths and configuration of shapers to fulfill the QoS requirements of different flows. Finding configurations by solving the scheduling problem in TSN has been an important research topic during the last few years. We summarize in Appendix A the different contributions in Tables 1 and 2. We deployed the \"quick and dirty\" search method in Google Scholar to gather an initial set of papers, then we used the \"Snowballing\" search method using databases such as Scopus and Web of Science. For conciseness, we focus on works published in 2016 and afterward. The tables present only scheduling solutions and exclude works that are not touching the problem directly. Other works treat related topics such as the effect of HTS scheduling on other traffic types [24, 25], comparing the performance of the different shapers [6, 26, 27], treating \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Traffic Category**} & \multicolumn{5}{c}{**Shaping Option**} \\ \cline{2-6}  & SP & CBS & ATS & CQF & TAS \\ \hline HTS (isochronous) & & & & & ✓ \\ \hline HTS (cyclic synchronous) & & & & ✓ & ✓ \\ \hline LTS streams & & & ✓ & ✓ & \\ \hline LTS nonstreams & & ✓ & ✓ & ✓ & \\ \hline BE & ✓ & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Traffic class to shaper mapping. the consistency [28] or stability [29] issues of the network, optimizing the topology given the network schedule [30], optimizing the assignments of queues [31], the limitation of joint routing and scheduling, etc. To help the classification of the state of the art, Tables A1 and A2 include columns identifying the task (i.e., S for scheduling, R for routing, T for topology optimization, and A for task or application placement), the selected approach, whether it is considering static scheduling (i.e., off for offline) or scheduling at runtime (i.e., on for online), whether it uses a distributed scheduling (i.e., D in the tables) or centralized scheduling (i.e., C in the tables) algorithm, and what shaper the work focuses on. As can be seen from the tables, most of the works treat scheduling in the TAS context. However, some works combine it with CQF (e.g., [11]), treated CQF (e.g., [32, 33]), or ATS (e.g., [34]) separately, or suggest enhancements to the shapers (e.g., study [35] proposed a TAS scheme with virtual queues (VQTAS), study [36] suggested a protection band to support emergency traffic, and study [6] suggested modifications to TAS to make it adaptive in a distributed approach). The developed approaches can be classified broadly into two main categories, as depicted in Figure 2. The first category focuses on the exact resolution of the scheduling problem through mathematical formulation as an optimization problem such as SMT/OMT, CP, and (M)ILP formulation and uses off-the-shelf solvers. (e.g., [37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]) to find a feasible or optimal solution. Solutions in the second category, including [34, 44, 45, 46, 47, 48, 49], develop heuristics or metaheuristics to solve the scheduling problem. While some of the works only tackle the scheduling problem (e.g., [34, 37, 38, 41]), other approaches such as [40, 43, 46, 50, 51] treat the combined scheduling and routing problem to gain more flexibility in the solution space. Several works treat the scheduling problem as an offline problem (e.g., [52, 53, 54, 55, 56]) while other works aim to develop online algorithms for runtime scheduling (e.g., [44, 57]). [PERSON] et al. [58] proposes both online and offline scheduling, while other works such as [59, 60, 61] calculate offline schedules, taking into consideration their effect on online scheduling. Some approaches aim for scalable solutions by fragmentation of the problem such as [48, 62]. Others, such as [11, 24], aim to improve LTS and BE QoS within TSN networks while serving HTS traffic.