mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A decomposition approach for SMT-based schedule synthesis for time-triggered networks
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1228-5176
TTTech Computertechnik AG, Vienna, Austria.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-4987-7669
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-7235-6888
2015 (English)In: 2015 IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA), 2015, Article number 7301436- p.Conference paper, Published paper (Refereed)
Resource type
Text
Abstract [en]

Real-time networks have tight communication latency and minimal jitter requirements. One way to ensure these requirements is the implementation of a static schedule, which defines the transmission points in time of time-triggered frames. Synthesizing such static schedules is known to be an NP-complete problem where the complexity is driven by the large number of constraints imposed by the network. Satisfiabily Modulo Theories (SMT) have been proven powerful tools to synthesize schedules of medium-to-large industrial networks. However, the schedules of new extremely large networks, such as integrated multi-machine factory networks, are defined by an extremely large number of constraints exceeding the capabilities of being synthesized by the tool alone. This paper presents a decomposition approach that will allow us to improve to synthesize schedules with up to two orders of magnitude in terms of the number of constraints that can be handled. We also present an implementation of a dependency tree on top of the decomposition approach to address application-imposed constraints between frames.

Place, publisher, year, edition, pages
2015. Article number 7301436- p.
Keyword [en]
computational complexity, jitter, optimisation, relay networks (telecommunication), telecommunication scheduling, NP-complete problem, SMT based schedule synthesis, communication latency, integrated multimachine factory networks, jitter requirements, satisfiabily modulo theories, time-triggered networks, Complexity theory, Context, Context modeling, Receivers, Schedules, Spread spectrum communication, Synthesizers
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-31553DOI: 10.1109/ETFA.2015.7301436ISI: 000378564800037Scopus ID: 2-s2.0-84952883901ISBN: 9781467379298 (print)OAI: oai:DiVA.org:mdh-31553DiVA: diva2:927199
Conference
2015 IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA)
Available from: 2016-05-11 Created: 2016-05-11 Last updated: 2017-02-28Bibliographically approved
In thesis
1. Synthesis of Extremely Large Time-Triggered Network Schedules
Open this publication in new window or tab >>Synthesis of Extremely Large Time-Triggered Network Schedules
2017 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Many embedded systems with real-time requirements demand minimal jitter and low communication end-to-end latency for its communication networks. The time-triggered paradigm, adopted by many real-time protocols, was designed to cope with these demands. A cost-efficient way to implement this paradigm is to synthesize a static schedule that indicates the transmission times of all the time-triggered frames such that all requirements are met. Synthesizing this schedule can be seen as a bin-packing problem, known to be NPcomplete, with complexity driven by the number of frames. In the last years, requirements on the amount of data being transmitted and the scalability of the network have increased. A solution was proposed, adapting real-time switched Ethernet to benefit from its high bandwidth. However, it added more complexity in computing the schedule, since every frame is distributed over multiple links. Tools like Satisfiability Modulo Theory solvers were able to cope with the added complexity and synthesize schedules of industrial size networks. Despite the success of such tools, applications are appearing requiring embedded systems with even more complex networks. In the future, real-time embedded systems, such as large factory automation or smart cities, will need extremely large hybrid networks, combining wired and wireless communication, with schedules that cannot be synthesized with current tools in a reasonable amount of time. With this in mind, the first thesis goal is to identify the performance limits of Satisfiability Modulo Theory solvers in schedule synthesis. Given these limitations, the next step is to define and develop a divide and conquer approach for decomposing the entire scheduling problem in smaller and easy solvable subproblems. However, there are constraints that relate frames from different subproblems. These constraints need to be treated differently and taken into account at the start of every subproblem. The third thesis goal is to develop an approach that is able to synthesize schedules when different frame constraints related to different subproblems are inter-dependent. Last, is to define the requirements that the integration of wireless communication in hybrid networks will bring to the schedule synthesis and how to cope with the increased complexity. We demonstrate the viability of our approaches by means of evaluations, showing that our method is capable to synthesize schedules of hundred of thousands of frames in less than 5 hours.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2017
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 255
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-34974 (URN)978-91-7485-314-8 (ISBN)
Presentation
2017-04-06, Gamma, Mälardalens högskola, Västerås, 14:00 (English)
Opponent
Supervisors
Projects
RetNet
Available from: 2017-02-28 Created: 2017-02-28 Last updated: 2017-03-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Pozo, FranciscoRodriguez-Navas, GuillermoHansson, Hans
By organisation
Embedded Systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 7 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf