You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.
The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.
For the reports in this repository we specifically note that
- the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
- the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
- technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
- in other cases, please contact the copyright owner for detailed information
By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.
If you are in doubt, feel free to contact webmaster@ide.mdh.se
Schedule Synthesis for Next Generation Time-Triggered Networks
Publication Type:
Report - MRTC
Venue:
MRTC Report, Mälardalen Real-Time Research Centre
Publisher:
Mälardalen Real-Time Research Centre, Mälardalen University
ISRN:
MDH-MRTC-314/2017-1-SE
Abstract
For handling frame transmissions in highly deterministic
real-time networks, i.e. networks requiring low communication
latency and minimal jitter, an offline time-triggered
schedule indicating the dispatch times of all frames can be used.
Generation of such an offline schedule is known to be a NPcomplete
problem, with complexity driven by the size of the
network, the number and complexity of the traffic temporal
constraints, and link diversity (for instance, coexistence of wired
and wireless links). As embedded applications become more
complex and extend over larger geographical areas, there is a
need to deploy larger real-time networks, but existing schedule
synthesis mechanisms do not scale satisfactorily to the sizes of
these networks, constituting a potential bottleneck for system
designers.
In this paper, we present an offline synthesis tool that overcomes
this limitation and is capable of generating time-triggered
schedules for networks with hundreds of nodes and thousands of
temporal constraints, also for systems where wired and wireless
links are combined. This tool models the problem with linear
arithmetic constraints and solves them using a Satisfiability
Modulo Theory (SMT) solver, a powerful general purpose tool
successfully used in the past for synthesizing time-triggered
schedules. To cope with complexity, our algorithm implements
a segmented approach that divides the total problem into easily
solvable smaller-size scheduling problems, whose solutions can
be combined for achieving the final schedule. The paper also
discusses a number of optimizations that increase the size and
compactness of the solvable schedules. We evaluate our approach
on a set of realistic large-size multi-hop networks, significantly
bigger than those in the existing literature. The results show
that our segmentation reduces the synthesis time dramatically,
allowing generation of extremely large compact schedules.
Bibtex
@techreport{Pozo4698,
author = {Francisco Pozo and Guillermo Rodriguez-Navas and Hans Hansson and Wilfried Steiner},
title = {Schedule Synthesis for Next Generation Time-Triggered Networks},
month = {February},
year = {2017},
publisher = {M{\"a}lardalen Real-Time Research Centre, M{\"a}lardalen University},
url = {http://www.es.mdu.se/publications/4698-}
}