ILP 기반한 시간민감네트워크 스케줄 생성 = ILP-based Schedule Synthesis of Time-Sensitive Networking

다국어 초록 (Multilingual Abstract)

IEEE 802.1Qbv Time Sensitive Network (TSN), the latest real-time Ethernet standard, is a network designed to guarantee the temporal accuracy of streams. TSN is an Ethernet-based network system that is actively being developed for the factory automation and automobile network systems. TSN controls the flow of data streams based on schedules generated statically off-line to satisfy end-to-end delay or jitter requirements. However, the generation of TSN schedules is an NP-hard problem; because of this, constraint solving techniques, such as SMT (Satisfiability Modulo Theory) and ILP (Integer Linear Programming), have mainly been proposed as solutions to this problem. This paper presents a new approach using a heuristic greedy and incremental algorithm working with ILP to decrease the complexity of computing schedules and improve the schedule generation performance in computing TSN schedules. Finally, we compare our proposed method with the existing SMT solver approach to show the performance of our approach.

국문 초록 (Abstract)

최신 실시간 이더넷 표준인 IEEE 802.1Qbv 시간민감네트워크(Time Sensitive Network, 이하 TSN)는 스트림의 시간적 정확성을 보장하기 위해 고안된 네트워크의 표준이다. TSN은 공장 자동화나 자동차 네트워크 시스템을 대체할 이더넷 기반 네트워크로 현재 개발되고 있다. TSN은 오프라인 상에서 만들어진 스케줄에 근거하여 스트림의 흐름을 제어함으로써 주어진 스트림의 종단간지연 혹은 지터 요구사항을 만족시킬 수 있다. 하지만 TSN 스케줄 생성은 NP-hard 문제로 그 복잡도에 있어서 매우 풀기 어려운 문제이다. 그러한 이유로 최근에는 SMT(Satisfiability Modulo Theory)이나 ILP(Integer Linear Programming) 같은 제약사항 해결 기법(Constraint solving technique) 등이 해결방법으로 제시되고 있다. 이 논문에서는 오프라인 상에서의 생성하는 TSN 스케줄 생성을 위해 휴리스틱과 ILP를 함께 이용한 탐욕적이며 점증적인(greedy and incremental) 알고리즘을 제공한다. 이렇게 하여 계산 복잡도를 줄이고 스케줄 생성 성능을 높이고자 한다. 본 논문에서는 특히 기존의 SMT 솔버를 통한 접근과의 비교를 통해 본 연구에서 제시하는 방법에 대한 성능을 비교한다.

참고문헌 (Reference)

1 L. De Moura, "Z3: An efficient SMT solver" Springer 337-340, 2008

2 A. C. T. d. Santos, "TSNSCHED: Automated Schedule Generation for Time Sensitive Networking" 69-77, 2019

3 V. Gavrilut, "Scheduling in Time Sensitive Networks (TSN) for Mixed-Criticality Industrial Applications" IEEE 1-4, 2018

4 S. S. Craciunas, "Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks" ACM 183-192, 2016

5 D. Hellmanns, "Scaling TSN Scheduling for Factory Automation Networks" 1-8, 2020

6 N. G. Nayak, "Routing Algorithms for IEEE 802.1Qbv Networks" 13-18, 2018

7 F. Smirnov, "Optimizing Message Routing and Scheduling in Automotive Mixed-Criticality Time-Triggered Networks" ACM 2017

8 F. Durr, "No-wait Packet Scheduling for IEEE Time-Sensitive Networks" 203-212, 2016

9 E. Schweissguth, "ILP-based Joint Routing and Scheduling for Time-triggered Networks" ACM 8-17, 2017

10 E. Schweissguth, "ILP-Based Routing and Scheduling of Multicast Realtime Traffic in TimeSensitive Networks" 1-11, 2020

11 R. S. Oliver, "IEEE 802.1Qbv Gate Control List Synthesis using Array Theory Encoding" IEEE 13-24, 2018

12 M. Pahlevan, "Heuristic List Scheduler for Time Triggered Traffic in Time Sensitive Networks" 16 : 15-20, 2019

13 J. Falk, "Exploring Practical Limitations of Joint Routing and Scheduling for TSN with ILP" 136-146, 2018

14 B. Bansal, "Divide-and-conquer scheduling for timesensitive networks" 2018