The public defence of Francisco Manuel Pozo Pérez doctoral thesis

Doctoral thesis and Licentiate seminars

Datum: 2019-10-24
Tid: 13.30
Plats: room Milos, MDH Västerås

The public defence of Francisco Manuel Pozo Pérez doctoral thesis in Computer Science and Engineering will take place at Mälardalen University on October 24, 2019, at 13.30 in room Milos, Västerås.

Title: “Methods for Efficient and Adaptive Scheduling of Next-Generation Time-Triggered Networks”.

Serial number: 296.

The examining committee consists of Professor Roman Obermaisser, University of Siegen; Professor Franz Wotawa, Graz University of Technology; Dr Liliana Cucu-Grosjean, INRIA. Among the members of the examining committee, Professor Petru Eles, Linköping University has been appointed the faculty examiner.

Reserve: Professor Björn Lisper, MDH.

Abstract:

In many systems, nodes exchange information through messages over a network to perform the required functions. In some systems, on top of the correct information, the timing at which nodes exchange the messages is also essential. These systems are called real-time systems. For example, autonomous cars require to perform their actions at the right time. Braking too early or too late might cause an accident causing financial losses or even loss of human lives. An established method to achieve the desired message timings is the time-triggered approach. In time-triggered communication, a schedule is generated at design time that specifies all the messages transmission times. Typically, these messages are sent periodically, for example, every 10 milliseconds. In operation, the different nodes in the system follow the schedule to ensure that the messages are transmitted when they are supposed to. An analogue to this scheduling of real-time networks is the scheduling of timetables for trains. A train, like a message, needs to arrive from point A to B, following a series of stations at the right time to (1) not collide with other trains and (2) for the passengers (the information) to arrive at the expected time.

In the past, real-time systems were relatively small, usually implemented in cars, planes, trains or industrial machines. However, as industrial applications are increasing in size, we expect that such systems could be implemented soon into huge factories containing a very large number of production cells or supporting a smart city with smarter control of traffic, electricity consumption, etc. This dissertation deals with the two main problems that appear when applying time-triggered communication into large systems: high complexity and lack of flexibility.

Obtaining a static schedule is a very complex problem. One method is to translate the scheduling problem into a mathematical problem and feed into a so-called SMT solver that returns the transmission times of all the messages. Extending this problem to systems ten times larger than the current ones will, if solvable with current approaches, yield a problem of unmanageable solution time. To address this challenge, we propose to divide the problem into smaller, manageable problems. As an illustration, if we need to generate a schedule for a whole hour, we can divide it into 60 schedules of one minute. Each of these are relatively easy to solve. The lack of flexibility comes from the impossibility to support changes, such as adding new components or communication failures. Typically, in systems like planes, the network is triplicated, so in the case of a failure, another network would take over. However, this solution is too costly when the network is as vast as a whole city. A solution could be to obtain a new schedule that takes into account the variation in the network, but this change needs to be fast. Unfortunately, obtaining a new schedule could take up to a few hours. As a remedy, we propose methods that only change the affected section of the schedule, thereby allowing a quick patch to be applied without much delay.

We have evaluated our methods to generate schedules in a large number of scenarios. The results show that our scheduling approach can handle the complexity of systems that are up to an order of magnitude larger than what previous solutions could handle. Moreover, in the presence of failures, we are able to patch the schedule with a very high success rate in a negligible amount of time.