Constraint programming approaches to joint routing and scheduling in time-sensitive networks

作     者：Vlk, Marek Hanzalek, Zdenek Tang, Siyu 

作者机构：Czech Tech Univ Czech Inst Informat Robot & Cybernet Jugoslavskych Partyzanu 1580-3 Prague 16000 6 Czech Republic Charles Univ Prague Fac Math & Phys Malostranske Mimesti 25 Prague 11800 1 Czech Republic Huawei Technol Duesseldorf GmbH Appl Network Technol Lab Munich Res Ctr Riesstr 253-0G D-80992 Munich Germany 

出 版 物：《COMPUTERS & INDUSTRIAL ENGINEERING》 (计算机与工业工程)

年 卷 期：2021年第157卷

页      面：107317-107317页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：European Regional Development Fund under the project AIReasoning [CZ.02.1.01/0.0/0.0/15_003/0000466] 

主　　题：Time-sensitive networking Real-time communication Time-triggered communication Isochronous traffic Integer linear programming Satisfiability Modulo Theories 

摘      要：The deterministic behavior of real-time communication networks is achieved by time-triggered periodic schedules for critical data traffic. Calculating such a schedule requires satisfying a lot of constraints, which in practice may be difficult due to the increasing number of data flows in the network. In the current approaches, the routes of flows are usually given or determined separately from the scheduling process. If the routes of flows can be computed jointly with scheduling, more flows could be scheduled since the algorithm chooses among alternative paths. This paper formalizes the problem of joint routing and scheduling of time-triggered periodic communication in Time-Sensitive Networks, guaranteeing the required deterministic nature of the communication, and proposes two models in Constraint Programming formalism. We further apply the Logic-Based Benders Decomposition on the proposed models and give an extensive experimental evaluation of our solutions showing that our novel approach that models waiting of frames in queues along with the Logic-Based Benders Decomposition exhibits the best performance and significantly increases the schedulability over the state-of-the-art methods.