mdh.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Schedule Synthesis for Next Generation Time-Triggered Networks
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.ORCID-id: 0000-0002-1228-5176
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system. IS (Embedded Systems).ORCID-id: 0000-0002-4987-7669
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system. IS (Embedded Systems).ORCID-id: 0000-0002-7235-6888
TTTech Computertechnik AG.
2017 (engelsk)Rapport (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Sweden: Mälardalen Real-Time Research Centre, Mälardalen University , 2017.
Serie
MRTC Reports, ISSN 1404-3041
Emneord [en]
Real-Time Networks, Scheduling, SMT Solver, Time-Triggered Networks
HSV kategori
Identifikatorer
URN: urn:nbn:se:mdh:diva-34973ISRN: MDH-MRTC-314/2017-1-SEOAI: oai:DiVA.org:mdh-34973DiVA, id: diva2:1077629
Prosjekter
RetNet - The European Industrial Doctorate Programme on Future Real-Time NetworksTilgjengelig fra: 2017-02-28 Laget: 2017-02-28 Sist oppdatert: 2017-10-16bibliografisk kontrollert
Inngår i avhandling
1. Synthesis of Extremely Large Time-Triggered Network Schedules
Åpne denne publikasjonen i ny fane eller vindu >>Synthesis of Extremely Large Time-Triggered Network Schedules
2017 (engelsk)Licentiatavhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Västerås: Mälardalen University, 2017
Serie
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 255
HSV kategori
Forskningsprogram
datavetenskap
Identifikatorer
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 (engelsk)
Opponent
Veileder
Prosjekter
RetNet
Tilgjengelig fra: 2017-02-28 Laget: 2017-02-28 Sist oppdatert: 2017-11-01bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Personposter BETA

Pozo, FranciscoRodriguez-Navas, G.Hansson, Hans A

Søk i DiVA

Av forfatter/redaktør
Pozo, FranciscoRodriguez-Navas, G.Hansson, Hans A
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 712 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf