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
SMT-based synthesis of TTEthernet schedules: A performance study
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1228-5176
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
TTTech Computertechnik AG, Vienna, Austria .
2015 (English)In: 2015 10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015 - Proceedings, 2015, p. 162-165Conference paper, Published paper (Refereed)
Resource type
Text
Abstract [en]

Time-triggered networks, like TTEthernet, require adoption of a predefined schedule to guarantee low communication latency and minimal jitter. The synthesis of such schedules is a problem known to be NP-complete. In the past, specialized solvers have been used for synthesizing time-triggered schedules, but more recently general-purpose tools like Satisfiability Modulo Theories (SMT) solvers have reported synthesis of large network schedules in reasonable time for industrial purposes. An interesting characteristic of any general-purpose tool is that its configuration parameters can be tuned in order to fit specific problems and achieve increased performance. This paper presents a study identifying and assessing which SMT solver parameters have the highest impact on the performance when synthesizing schedules for time-triggered networks. The results show that with appropriate values of certain parameters, the time can be reduced significantly, up to 75% in the best cases compared to previous work. © 2015 IEEE.

Place, publisher, year, edition, pages
2015. p. 162-165
Keywords [en]
Context, High definition video, Real-time systems, Receivers, Schedules, Spread spectrum communication, Synthesizers
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-31307DOI: 10.1109/SIES.2015.7185055ISI: 000380569800021Scopus ID: 2-s2.0-84959556249ISBN: 9781467377119 (print)OAI: oai:DiVA.org:mdh-31307DiVA, id: diva2:912776
Conference
10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015, 8 June 2015 through 10 June 2015
Available from: 2016-03-17 Created: 2016-03-17 Last updated: 2019-09-06Bibliographically 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-11-01Bibliographically approved
2. Methods for Efficient and Adaptive Scheduling of Next-Generation Time-Triggered Networks
Open this publication in new window or tab >>Methods for Efficient and Adaptive Scheduling of Next-Generation Time-Triggered Networks
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Real-time networks play a fundamental role in embedded systems. To meet timing requirements, provide low jitter and bounded latency in such networks the time-triggered communication paradigm is frequently applied in such networks. In this paradigm, a schedule specifying the transmission times of all the traffic is synthesized a priori. Given the steady increase in size and complexity of embedded systems, coupled with the addition of wireless communication, a new time-triggered network model of larger and mixed wired-wireless network isdeveloping. Developing such next-generation networks entails significant research challenges, especially concerning scalability, i.e., allowing generation of schedules of the very large next-generation networks in a reasonable time. A second challenge concerns a well-known limitation of the time-triggered paradigm: its lack of flexibility. Large networks exacerbate this problem, as the number of changes during network operation increases with the number of components, which renders static scheduling approaches unsuitable.

In this thesis, we first propose a remedy to the scalability challenge that the synthesis of next-generation network schedules introduces. We propose a family of divide-and-conquer approaches that segment the entire scheduling problem into small enough subproblems that can be effectively and efficiently solved by state-of-the-art schedulers. Second, we investigate how adaptive behaviours can be introduced into the time-triggered paradigm with the implementation of a Self-Healing Protocol. This protocol addresses the flexibility challenge by only updating a small segment of the schedule in response to changes during runtime. This provides a significant advantage compared to current approaches that fully reschedule the network. In the course of our research, we found that our protocol become more effective when the slack in the original schedule is evenly distributed during the schedule synthesis. As a consequence, we also propose a new scheduling approach that maximizes the distances between frames, increasing the success rate of our protocol.

The divide-and-conquer approaches developed in this thesis were able to synthesize schedules of two orders of magnitude more traffic and one order of magnitude more nodes in less than four hours. Moreover, when applied to current industrial size networks, they reduced the synthesis time from half an hour to less than one minute compared with state-of-the-art schedulers. The Self-Healing Protocol opened a path towards adaptive time-triggered being able to heal schedules online after link and switch failures in less than ten milliseconds.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2019
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 296
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-45165 (URN)978-91-7485-436-7 (ISBN)
Public defence
2019-10-24, Milos, Mälardalens högskola, Västerås, 13:30 (English)
Opponent
Supervisors
Available from: 2019-09-10 Created: 2019-09-06 Last updated: 2019-09-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Pozo, FranciscoRodriguez-Navas, GuillermoHansson, Hans

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 457 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