mdh.sePublications
1234561 of 6
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
Methods for Efficient and Adaptive Scheduling of Next-Generation Time-Triggered Networks
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1228-5176
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: urn:nbn:se:mdh:diva-45165ISBN: 978-91-7485-436-7 (print)OAI: oai:DiVA.org:mdh-45165DiVA, id: diva2:1349118
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
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, p. 162-165Conference 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.

Keywords
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: 2019-09-06Bibliographically approved
2. Methods for large-scale time-triggered network scheduling
Open this publication in new window or tab >>Methods for large-scale time-triggered network scheduling
2019 (English)In: Electronics (Switzerland), ISSN 2079-9292, Vol. 8, no 7, article id 738Article in journal (Refereed) Published
Abstract [en]

Future cyber–physical systems may extend over broad geographical areas, like cities or regions, thus, requiring the deployment of large real-time networks. A strategy to guarantee predictable communication over such networks is to synthesize an offline time-triggered communication schedule. However, this synthesis problem is computationally hard (NP-complete), and existing approaches do not scale satisfactorily to the required network sizes. This article presents a segmented offline synthesis method which substantially reduces this limitation, being able to generate time-triggered schedules for large hybrid (wired and wireless) networks. We also present a series of algorithms and optimizations that increase the performance and compactness of the obtained schedules while solving some of the problems inherent to segmented approaches. We evaluate our approach on a set of realistic large-size multi-hop networks, significantly larger than those considered in the existing literature. The results show that our segmentation reduces the synthesis time by up to two orders of magnitude.

Place, publisher, year, edition, pages
MDPI AG, 2019
Keywords
Cyber-physical systems, Real-time networks, Scheduling, SMT solvers, Time-triggered
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-45101 (URN)10.3390/electronics8070738 (DOI)000482063200063 ()2-s2.0-85070718684 (Scopus ID)
Available from: 2019-08-28 Created: 2019-08-28 Last updated: 2019-09-12Bibliographically approved
3. Schedule reparability: Enhancing time-triggered network recovery upon link failures
Open this publication in new window or tab >>Schedule reparability: Enhancing time-triggered network recovery upon link failures
2019 (English)In: Proceedings - 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2018, Institute of Electrical and Electronics Engineers Inc. , 2019, p. 147-156Conference paper, Published paper (Refereed)
Abstract [en]

The time-triggered communication paradigm has been shown to satisfy temporal isolation while providing end to end delay guarantees through the synthesis of an offline schedule. However, this paradigm has severe flexibility limitations as any unpredicted change not anticipated by the schedule, such as a component failure, might result in a loss of frames. A typical solution is to use redundancy or replace and update the schedule offline anew. With the ever increase in size of networks and the need to reduce costs, supplementary solutions that enhance the reliability of such networks are also desired. In this paper, we introduce a repair algorithm capable of reacting to unpredicted link failures. The algorithm quickly modifies the schedule such that all frames are transmitted again within their timing guarantees. We found that the success of our algorithm increases significantly with the existence of empty slots spread over the schedule, an opposite approach compared to packing frames, commonly used in the literature. We propose a new ILP formulation that includes a maximization of frame and link intermissions to stretch empty slots over the schedule. Our results show that we can repair with 90% success rate within milliseconds to a valid schedule compared to a few minutes needed to re-schedule the whole network. 

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc., 2019
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-42810 (URN)10.1109/RTCSA.2018.00026 (DOI)000458980300017 ()2-s2.0-85061771050 (Scopus ID)9781538677599 (ISBN)
Conference
24th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2018; Hakodate; Japan; 29 August 2018 through 31 August 2018
Available from: 2019-02-28 Created: 2019-02-28 Last updated: 2019-09-06Bibliographically approved
4. Self-Healing Protocol: Repairing Scheduels Online after Link Failures in Time-Triggered Networks
Open this publication in new window or tab >>Self-Healing Protocol: Repairing Scheduels Online after Link Failures in Time-Triggered Networks
(English)In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, E-ISSN 1941-0050Article in journal (Refereed) Submitted
Abstract [en]

The time-triggered paradigm is not adaptive, a static schedule determines the time-triggered communication and, then, any unpredicted change, like a link failure, might result in the loss of frames. Using spatial redundancy or recomputing a new schedule for replacement achieves fault tolerance only in moderate-size networks. With the increase in size and complexity of cyber-physical systems, more scalable and cost-efficient mechanisms are needed in order to complement conventional solutions. We propose a distributed Self-Healing Protocol that instead of recomputing the whole schedule, repairs the existent schedule at runtime. The basis of our protocol is the collaboration of nodes in the network to individually adjust their local schedules for rerouting the frames affected by link failures. Our protocol exhibits a high success rate compared to full rescheduling, as well as remarkable scalability; it repairs the schedule in milliseconds, whereas rescheduling requires minutes.

National Category
Communication Systems Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-45127 (URN)
Available from: 2019-09-02 Created: 2019-09-02 Last updated: 2019-09-13Bibliographically approved
5. Semi-Distributed Self-Healing Protocol for Online Schedule Repair after Network Failures
Open this publication in new window or tab >>Semi-Distributed Self-Healing Protocol for Online Schedule Repair after Network Failures
2019 (English)Report (Other academic)
Abstract [en]

Adaptive requirements for networks with strict timing restrictions do challenge the static nature of the time-triggered communication paradigm. Continuous changes in the network topology during operation require frequent rescheduling, followed by schedule distribution, a process that is excessively time-consuming as it was intended to be performed only during the design phase. The fully-distributed Self-Healing Protocol introduced a collaborative method to quickly modify the local schedules of the nodes during runtime, after link failures. This protocol gets the network back to correct operation in milliseconds, but it assumes that only the nodes are able to modify their local schedules, which limited the achieved improvement. This paper proposes to shift to a semi-distributed strategy, where high-performance nodes are responsible for the nodes and links within a small network segment. These nodes rely on their privileged view of the system in order to reduce the response time, increase the healing success rate, and extend the fault model to include switch failures. 

National Category
Communication Systems
Identifiers
urn:nbn:se:mdh:diva-45162 (URN)
Available from: 2019-09-06 Created: 2019-09-06 Last updated: 2019-09-13Bibliographically approved

Open Access in DiVA

fulltext(1253 kB)19 downloads
File information
File name FULLTEXT01.pdfFile size 1253 kBChecksum SHA-512
7cb9b20e354dfc206007a38fc7e42a90158aca0432bde45d18571ceefbe1bad4a0c3f6cb393baf594553321472685d5a24a568ff08c110eb8164b4497e5b4158
Type fulltextMimetype application/pdf

Authority records BETA

Pozo Pérez, Francisco Manuel

Search in DiVA

By author/editor
Pozo Pérez, Francisco Manuel
By organisation
Embedded Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 19 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: 108 hits
1234561 of 6
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