More Web Proxy on the site http://driver.im/

research-article

Synthesis of communication schedules for TTEthernet-based mixed-criticality systems

Authors:

Domitian Tamas-Selicean,

Wilfried SteinerAuthors Info & Claims

CODES+ISSS '12: Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

Pages 473 - 482

https://doi.org/10.1145/2380445.2380518

Published: 07 October 2012 Publication History

Abstract

In this paper we are interested in safety-critical distributed systems, composed of heterogeneous processing elements interconnected using the TTEthernet protocol. We address hard real-time mixed-criticality applications, which may have different criticality levels, and we focus on the optimization of the communication configuration. TTEthernet integrates three types of traffic: Time-Triggered (TT) messages, Event-Triggered (ET) messages with bounded end-to-end delay, also called Rate Constrained (RC) messages, and Best-Effort (BE) messages, for which no timing guarantees are provided. TT messages are transmitted based on static schedule tables, and have the highest priority. RC messages are transmitted if there are no TT messages, and BE traffic has the lowest priority. TT and RC traffic can carry safety-critical messages, while BE messages are non-critical. Mixed-criticality tasks and messages can be integrated onto the same architecture only if there is enough spatial and temporal separation among them. TTEthernet offers spatial separation for mixed-criticality messages through the concept of virtual links, and temporal separation, enforced through schedule tables for TT messages and bandwidth allocation for RC messages. Given the set of mixed-criticality messages in the system and the topology of the virtual links on which the messages are transmitted, we are interested to synthesize offline the static schedules for the TT messages, such that the deadlines for the TT and RC messages are satisfied, and the end-to-end delay of the RC traffic is minimized. We have proposed a Tabu Search-based approach to solve this optimization problem. The proposed algorithm has been evaluated using several benchmarks.

References

[1]

SAE Technical Report J2056/1. Technical report, SAE International.

[2]

ISO 11898: Road Vehicles -- Controller Area Network (CAN). International Organization for Standardization (ISO), Geneva, Switzerland, 2003.

[3]

ARINC 664P7: Aircraft Data Network, Part 7, Avionics Full-Duplex Switched Ethernet Network. ARINC (Aeronautical Radio, Inc), 2009.

[4]

ISO 10681: Road vehicles -- Communication on FlexRay. International Organization for Standardization (ISO), Geneva, Switzerland, 2010.

[5]

AS6802: Time-Triggered Ethernet. SAE International, 2011.

[6]

M. Adnan, J.-L. Scharbarg, J. Ermont, and C. Fraboul. Model for worst case delay analysis of an AFDX network using timed automata. In Proceedings of the Conference on Emerging Technologies and Factory Automation, pages 1 --4, 2010.

[7]

N. Audsley, K. Tindell, and A. Burns. The end of the line for static cyclic scheduling. In Proceedings of Euromicro Workshop on Real-Time Systems, pages 36--41, 1993.

[8]

S. Baruah and G. Fohler. Certification-Cognizant Time-Triggered Scheduling of Mixed-Criticality Systems. Proceedings of the Real-Time Systems Symposium, pages 3--12, 2011.

Digital Library

[9]

S. Baruah, H. Li, and L. Stougie. Towards the design of certifiable mixed-criticality systems. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium, 2010.

Digital Library

[10]

S. K. Baruah, A. Burns, and R. I. Davis. Response-Time Analysis for Mixed Criticality Systems. Proceedings of the Real-Time Systems Symposium, pages 34--43, 2011.

Digital Library

[11]

H. Bauer, J.-L. Scharbarg, and C. Fraboul. Applying and optimizing trajectory approach for performance evaluation of AFDX avionics network. In Proceedings of the Conference on Emerging Technologies Factory Automation, pages 1 --8, 2009.

Digital Library

[12]

H. Bauer, J.-L. Scharbarg, and C. Fraboul. Worst-case end-to-end delay analysis of an avionics AFDX network. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 1220--1224, 2010.

Digital Library

[13]

A. Bouillard, L. Jouhet, and E. Thierry. Tight Performance Bounds in the Worst-Case Analysis of Feed-Forward Networks. In Proceedings of INFOCOM, pages 1--9, 2010.

Digital Library

[14]

M. Boyer and C. Fraboul. Tightening end to end delay upper bound for AFDX network calculus with rate latency FIFO servers using network calculus. In Proceedings of the International Workshop on Factory Communication Systems, pages 11 --20, 2008.

[15]

R. Ernst. Certification of Trusted MPSoC Platforms. 10th International Forum on Embedded MPSoC and Multicore, 2010.

[16]

R. N. et al. Steiner tree based distributed multicast routing in networks. In X. Cheng and D.-Z. Du, editors, Steiner Trees in Industry. Springer, 2002.

[17]

E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1--29, 1968.

Digital Library

[18]

F. Glover and M. Laguna. Tabu Search. Kluwer Academic Publishers, Norwell, MA, USA, 1997.

[19]

K. Hoyme and K. Driscoll. SAFEbus. IEEE Aerospace Electronic Systems Magazine, 8:34--39, 1993.

[20]

V. Izosimov, P. Pop, P. Eles, and Z. Peng. Scheduling of fault-tolerant embedded systems with soft and hard timing constraints. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 915--920, 2008.

Digital Library

[21]

H. Kopetz. Real-Time Systems: Design Principles for Distributed Embedded Applications. Springer, 2011.

Digital Library

[22]

B. Leiner, M. Schlager, R. Obermaisser, and B. Huber. A Comparison of Partitioning Operating Systems for Integrated Systems. Computer Safety, Reliability, and Security, pages 342--355, 2007.

Digital Library

[23]

H. Lonn and J. Axelsson. A comparison of fixed-priority and static cyclic scheduling for distributed automotive control applications. In Proceedings of the Euromicro Conference on Real-Time Systems, pages 142--149. IEEE, 1999.

[24]

U. Mohammad, N. Al-holou, and P. D. Development of an automotive communication benchmark. Canadian Journal on Electrical and Electronics Engineering, 1(5):99--115, 2010.

[25]

R. Obermaisser. Time-Triggered Communication. CRC Press, Inc., 2011.

Digital Library

[26]

P. Pop, P. Eles, and Z. Peng. Scheduling with optimized communication for time-triggered embedded systems. In Proceedings of the International Workshop on Hardware/Software Codesign, pages 178--182, 1999.

Digital Library

[27]

P. Pop, P. Eles, and Z. Peng. Analysis and Synthesis of Communication-Intensive Heterogenous Real-Time Systems. Kluwer Academic Publishers, 2004.

[28]

P. Pop, P. Eles, and Z. Peng. Schedulability-driven frame packing for multicluster distributed embedded systems. ACM Transactions on Embedded Computing Systems (TECS), 4(1):112--140, 2005.

Digital Library

[29]

T. Pop, P. Pop, P. Eles, and Z. Peng. Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems. International Journal of Parallel Programming, 36(1):37--67, feb 2008.

Digital Library

[30]

T. Pop, P. Pop, P. Eles, Z. Peng, and A. Andrei. Timing analysis of the FlexRay communication protocol. In Proceedings of the Euromicro Conference on Real-Time Systems, pages 11 pp. --216, 2006.

Digital Library

[31]

J. Rushby. Partitioning for Avionics Architectures: Requirements, Mechanisms, and Assurance. NASA Contractor Report CR-1999--209347, NASA Langley Research Center, 1999.

[32]

I. Saha and S. Roy. A Finite State Modeling of AFDX Frame Management Using Spin. In L. Brim, B. Haverkort, M. Leucker, and J. van de Pol, editors, Formal Methods: Applications and Technology, volume 4346 of Lecture Notes in Computer Science, pages 227--243. Springer, 2007.

Digital Library

[33]

P. K. Saraswat, P. Pop, and J. Madsen. Task Mapping and Bandwidth Reservation for Mixed Hard/Soft Fault-Tolerant Embedded Systems. Proceedings of the Real-Time and Embedded Technology and Applications Symposium, pages 89--98, 2010.

Digital Library

[34]

W. Steiner. An Evaluation of SMT-based Schedule Synthesis For Time-Triggered Multi-Hop Networks. In Proceedings of the Real-Time Systems Symposium, pages 375--384, 2010.

Digital Library

[35]

W. Steiner. Synthesis of Static Communication Schedules for Mixed-Criticality Systems. In Proceedings of the International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops, pages 11 --18, 2011.

Digital Library

[36]

W. Steiner, G. Bauer, B. Hall, M. Paulitsch, and S. Varadarajan. TTEthernet Dataflow Concept. In Proceedings of the International Symposium on Network Computing and Applications, pages 319 --322, 2009.

Digital Library

[37]

D. TÑmac-Selicean and P. Pop. Design Optimization of Mixed-Criticality Real-Time Applications on Cost-Constrained Partitioned Architectures. In Proceedings of the Real-Time Systems Symposium, pages 24--33, 2011.

Digital Library

[38]

J. D. Ullman. NP-complete scheduling problems. J. Comput. Syst. Sci., 10(3):384--393, 1975.

Digital Library

[39]

J. Xu and D. L. Parnas. On Satisfying Timing Constraints in Hard-Real-Time Systems. IEEE Transactions on Software Engineer, 19(1):70--84, 1993.

Digital Library

Cited By

Zhang LZhang TWu WFeng XLin GRen F(2024)Fault- Tolerant Cyclic Queuing and Forwarding in Time-Sensitive Networking2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546689(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546689
Zhong WZhou JSun TSong XLi Z(2024)A Verification Framework for Time-Triggered Networks Based on Timed Colored Petri NetIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335570843:7(2112-2125)Online publication date: Jul-2024
https://doi.org/10.1109/TCAD.2024.3355708
Sharma GTavernier WColle DPickavet MHaxhibeqiri JHoebeke JMoerman I(2024)End-to-End No-wait Scheduling for Time-Triggered Streams in Mixed Wired-Wireless NetworksJournal of Network and Systems Management10.1007/s10922-024-09837-532:3Online publication date: 8-Jul-2024
https://doi.org/10.1007/s10922-024-09837-5
Show More Cited By

Index Terms

Synthesis of communication schedules for TTEthernet-based mixed-criticality systems
1. Hardware
  1. Hardware validation
2. Networks
  1. Network protocols

Recommendations

Synthesis of Static Communication Schedules for Mixed-Criticality Systems
ISORCW '11: Proceedings of the 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops

Throughout many application areas of embedded and cyber-physical systems there is a demand to integrate more and more applications such that they share common resources. These applications may have different levels of criticality with respect to ...
Timing Analysis of Rate Constrained Traffic for the TTEthernet Communication Protocol
ISORC '15: Proceedings of the 2015 IEEE 18th International Symposium on Real-Time Distributed Computing

Ethernet is a low-cost communication solution offering high transmission speeds. Although its applications extend beyond computer networking, Ethernet is not suitable for real-time and safety-critical systems. To alleviate this, several real-time ...
Design optimization of TTEthernet-based distributed real-time systems

Many safety-critical real-time applications are implemented using distributed architectures, composed of heterogeneous processing elements interconnected in a network. Our focus in this paper is on the TTEthernet protocol, a deterministic, synchronized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CODES+ISSS '12: Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

October 2012

596 pages

ISBN:9781450314268

DOI:10.1145/2380445

General Chairs:
Ahmed Jerraya
CEA
,
Luca Carloni
Columbia University
,
Program Chairs:
Naehyuck Chang
Seoul National University, Korea
,
Franco Fummi
University of Verona, Italy

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWEEK'12

Sponsor:

ESWEEK'12: Eighth Embedded System Week

October 7 - 12, 2012

Tampere, Finland

Acceptance Rates

CODES+ISSS '12 Paper Acceptance Rate 48 of 163 submissions, 29%;

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
796
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)3

Reflects downloads up to 02 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LZhang TWu WFeng XLin GRen F(2024)Fault- Tolerant Cyclic Queuing and Forwarding in Time-Sensitive Networking2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546689(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546689
Zhong WZhou JSun TSong XLi Z(2024)A Verification Framework for Time-Triggered Networks Based on Timed Colored Petri NetIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335570843:7(2112-2125)Online publication date: Jul-2024
https://doi.org/10.1109/TCAD.2024.3355708
Sharma GTavernier WColle DPickavet MHaxhibeqiri JHoebeke JMoerman I(2024)End-to-End No-wait Scheduling for Time-Triggered Streams in Mixed Wired-Wireless NetworksJournal of Network and Systems Management10.1007/s10922-024-09837-532:3Online publication date: 8-Jul-2024
https://doi.org/10.1007/s10922-024-09837-5
Garreau RLadeira MGrolleau EBauer HRidouard FRichard P(2023)Link Between Real-Time Scheduling and Time-Triggered Networks2023 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS59052.2023.00041(397-410)Online publication date: 5-Dec-2023
https://doi.org/10.1109/RTSS59052.2023.00041
Wang ZZheng WTang JWang YSun FYao JWang W(2023)Traffic Scheduling Method for Power Low-Latency Business in TSN Based on Sending Time Scheduled2023 IEEE 7th Information Technology and Mechatronics Engineering Conference (ITOEC)10.1109/ITOEC57671.2023.10291968(1936-1941)Online publication date: 15-Sep-2023
https://doi.org/10.1109/ITOEC57671.2023.10291968
Zhu XGong BZhu H(2023)Hybrid Genetic-Based Traffic Scheduling Algorithm in In-Vehicle Time Sensitive Networks2023 3rd International Conference on Frontiers of Electronics, Information and Computation Technologies (ICFEICT)10.1109/ICFEICT59519.2023.00071(388-394)Online publication date: May-2023
https://doi.org/10.1109/ICFEICT59519.2023.00071
Han YYao MYang YShi YCao MWang Q(2023)The Impact of Traffic Compositions on the Performance of Schedule Partition and Schedule Porosity in Time-Triggered Ethernet2023 15th International Conference on Communication Software and Networks (ICCSN)10.1109/ICCSN57992.2023.10297381(90-94)Online publication date: 21-Jul-2023
https://doi.org/10.1109/ICCSN57992.2023.10297381
Likhttsinder BBakai Y(2023)Ethernet networks with deterministic delaysINSTRUMENTATION ENGINEERING, ELECTRONICS AND TELECOMMUNICATIONS – 2021 (IEET-2021): Proceedings of the VII International Forum10.1063/5.0126760(020015)Online publication date: 2023
https://doi.org/10.1063/5.0126760
Yang TZhang YYue FWuniri QTong C(2023)D-scheduler: A scheduler in time-triggered distributed system through decoupling dependencies between tasks and messagesScience China Technological Sciences10.1007/s11431-023-2492-867:1(183-196)Online publication date: 16-Nov-2023
https://doi.org/10.1007/s11431-023-2492-8
Lichtsinder B(2022)Ethernet networks with deterministic delaysVestnik of Samara State Technical University. Technical Sciences Series10.14498/tech.2022.3.630:3(81-97)Online publication date: 4-Dec-2022
https://doi.org/10.14498/tech.2022.3.6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten