Paper Info
Title
Ilp-Based Joint Routing And Scheduling For Time-Triggered Networks
Abstract
Networks in the automotive and aerospace area as well as in production facilities have to support time-critical (i.e., hard real-time) communication. For such applications, time-triggered EthernetNbased networking solutions provide the required timeliness, i.e., reliable packet delivery with deterministic latencies and low jitter. However, the routing and scheduling of the time-triggered traffic is an NP-hard problem. Hence, existing solutions to this problem make certain abstractions to reduce complexity if necessary. Nonetheless, such abstractions exclude feasible routing and scheduling options from the design space. Specifically, it is a typical approach to model routing and scheduling as separate problems, which are solved successively or with heuristic coupling. Therefore, we present a novel ILP formulation that can be used to jointly solve the routing and scheduling problem for time-triggered Ethernet networks. Using this formulation, it is possible to solve various scheduling problems that are infeasible when using a fixed shortest path routing with separate scheduling. Compared to a fixed load balanced routing with separate scheduling, schedules computed with our formulation offer lower communication latencies.
Year
DOI
Venue
2017
10.1145/3139258.3139289
PROCEEDINGS OF THE 25TH INTERNATIONAL CONFERENCE ON REAL-TIME NETWORKS AND SYSTEMS (RTNS 2017)
Keywords
Field
DocType
real-time, time-triggered, routing, scheduling, networks, integer programming, ILP, Time-Sensitive Networking, TSN, TTEthernet
Link-state routing protocol,Job shop scheduling,Fair-share scheduling,Shortest path problem,Computer science,Scheduling (computing),Wireless Routing Protocol,Schedule,Ethernet,Distributed computing
Conference
Citations 
PageRank 
References 
15
0.89
6
Authors
5
Name
Order
Citations
PageRank
eike bjoern schweissguth1233.59
Peter Danielis24213.13
Dirk Timmermann3846101.52
Helge Parzyjegla415217.17
Gero Mühl539645.36