Efficient Algorithm for Jitter Minimization in Time-Triggered Periodic Mixed-Criticality Message Scheduling Problem

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00304028" target="_blank" >RIV/68407700:21230/16:00304028 - isvavai.cz</a>

Alternative codes found

RIV/68407700:21730/16:00304028

Result on the web

<a href="http://dx.doi.org/10.1145/2997465.2997481" target="_blank" >http://dx.doi.org/10.1145/2997465.2997481</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/2997465.2997481" target="_blank" >10.1145/2997465.2997481</a>

Result language

angličtina

Original language name

Efficient Algorithm for Jitter Minimization in Time-Triggered Periodic Mixed-Criticality Message Scheduling Problem

Original language description

The current research in real-time scheduling focuses mostly on the certification of functionalities with respect to safety requirements under conservative assumptions or to achieve efflcient resource utilization but with optimistic assumptions. With growing system complexity, the safety certifi- cation is becoming hard, especially in event-triggered environments. In time-triggered environments, the network nodes are synchronized by clocks and follow a static schedule hence they are easily certifiable. However, the timetriggered paradigm has two disadvantages. The first one is its general non- exibility (e.g. message retransmission, effi- cient resource usage) and the second one is the need for an efflcient scheduling algorithm producing the schedule. In this paper, we propose a solution to both of these issues. To address the first disadvantage, we propose a method for non-preemptive message retransmission in time-triggered environments while preserving the efflcient use of resources. Based on the message criticality we allow a certain number of retransmissions. The observed prolongation of the processing time of a highly critical message is compensated by skipping transmission of less critical messages. Static schedules then contain all alternatives caused by the retransmissions that can occur during a run time execution. Schedules conform with certification requirements imposed on the highly critical messages while preserving the efflcient use of resources. To address the second disadvantage, we propose a novel heuristic scheduling algorithm with an unscheduling step for solving large instances of periodic message scheduling problem. The message periodicity is assumed to be a power of two and the objective is to minimize the maximal jitter. The efflciency of the approach is demonstrated on problem instances with up to 2000 messages.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

ACM International Conference Proceeding Series

ISBN

978-1-4503-4787-7

ISSN

—

e-ISSN

—

Number of pages

9

Pages from-to

23-31

Publisher name

ACM

Place of publication

New York

Event location

Brest

Event date

Oct 19, 2016

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000391255400003