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
Synthesis of Extremely Large Time-Triggered Network Schedules
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1228-5176
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: urn:nbn:se:mdh:diva-34974ISBN: 978-91-7485-314-8 (print)OAI: oai:DiVA.org:mdh-34974DiVA: diva2:1077648
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
List of papers
1. SMT-based synthesis of TTEthernet schedules: A performance study
Open this publication in new window or tab >>SMT-based synthesis of TTEthernet schedules: A performance study
2015 (English)In: 2015 10th IEEE International Symposium on Industrial Embedded Systems, SIES 2015 - Proceedings, 2015, 162-165 p.Conference paper, Published paper (Refereed)
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.

Keyword
Context, High definition video, Real-time systems, Receivers, Schedules, Spread spectrum communication, Synthesizers
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-31307 (URN)10.1109/SIES.2015.7185055 (DOI)000380569800021 ()2-s2.0-84959556249 (Scopus ID)9781467377119 (ISBN)
External cooperation:
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: 2017-02-28Bibliographically approved
2. A decomposition approach for SMT-based schedule synthesis for time-triggered networks
Open this publication in new window or tab >>A decomposition approach for SMT-based schedule synthesis for time-triggered networks
2015 (English)In: 2015 IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA), 2015, Article number 7301436- p.Conference paper, Published paper (Refereed)
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.

Keyword
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:nbn:se:mdh:diva-31553 (URN)10.1109/ETFA.2015.7301436 (DOI)000378564800037 ()2-s2.0-84952883901 (Scopus ID)9781467379298 (ISBN)
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
3. Period-Aware Segmented Synthesis of Schedules for Multi-Hop Time-Triggered Networks
Open this publication in new window or tab >>Period-Aware Segmented Synthesis of Schedules for Multi-Hop Time-Triggered Networks
2016 (English)In: 22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2016), IEEE, 2016, 170-175 p.Conference paper, Published paper (Refereed)
Abstract [en]

Time-triggered offline scheduling is a cost-efficien way to guarantee low communication end-to-end latency and minimal jitter for communication networks in real-time systems. The schedule is generated pre-runtime and indicates the transmission times of time-triggered frames such that contention is prevented. The synthesis of such offline schedules is a bin-packing problem, known to be NP-complete, with complexity driven by the constraints on frame transmissions, and the number of frames in the schedule. Satisfiability Modulo Theories combined with segmented approaches have been successfully used for synthesizing schedules of large networks. However, such synthesis did not take into account frames periods that are much shorter than the time to execute the schedule cycle. This paper presents a periodaware segmented approach that takes into account the frame periods in order to allocate various instances of a frame within a single cycle. We describe three different synthesis strategies and evaluate them with different synthetic experiments. The results show better performance for one of the strategies, which can synthesize schedules of large networks with high communication loads in less than one hour. We also report how the synthesis time and the schedule quality can change with different parameter configurations.

Place, publisher, year, edition, pages
IEEE, 2016
Series
IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, ISSN 1533-2306
Keyword
computational complexity, optimization, time-triggered networks
National Category
Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-34010 (URN)10.1109/RTCSA.2016.42 (DOI)000387085600032 ()2-s2.0-84994525123 (Scopus ID)
Conference
22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2016)
Available from: 2016-11-30 Created: 2016-11-30 Last updated: 2017-02-28Bibliographically approved
4. Schedule Synthesis for Next Generation Time-Triggered Networks
Open this publication in new window or tab >>Schedule Synthesis for Next Generation Time-Triggered Networks
2017 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Sweden: Mälardalen Real-Time Research Centre, Mälardalen University, 2017
Series
MRTC Reports, ISSN 1404-3041
Keyword
Real-Time Networks, Scheduling, SMT Solver, Time-Triggered Networks
National Category
Engineering and Technology Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-34973 (URN)MDH-MRTC-314/2017-1-SE (ISRN)
Projects
RetNet - The European Industrial Doctorate Programme on Future Real-Time Networks
Available from: 2017-02-28 Created: 2017-02-28 Last updated: 2017-10-16Bibliographically approved

Open Access in DiVA

fulltext(670 kB)70 downloads
File information
File name FULLTEXT03.pdfFile size 670 kBChecksum SHA-512
dc3516d84cd823b2c62b18990dfe060198d5662d59a82d5705f95ee88fc7145aa3966f4d1ef01334325c1394dae93017f62fc171ab7e18c73423ef35ff32e31e
Type fulltextMimetype application/pdf

Authority records BETA

Pozo, Francisco

Search in DiVA

By author/editor
Pozo, Francisco
By organisation
Embedded Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 70 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

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