skip to main content
10.1145/3061639.3062298acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

Optimizing Message Routing and Scheduling in Automotive Mixed-Criticality Time-Triggered Networks

Authors Info & Claims
Published:18 June 2017Publication History

ABSTRACT

Upcoming high-bandwidth protocols like Ethernet TSN feature mechanisms for redundant and deterministic (scheduled) message delivery to integrate safety- and real-time--critical applications and, thus, realize mixed-criticality systems. In existing design approaches, the message routing and system scheduling are generated in two entirely separated design steps, ignoring and/or not exploiting the distinct interrelations between routing and scheduling decisions. In this paper, we first introduce an exact approach to generate an implementation with a valid routing and a valid schedule in a single step by solving a 0-1 ILP. Second, we show that the 0-1 ILP formulation can be utilized in a design space exploration to optimize the routing and schedule with respect to, e.g., interference imposed on non-scheduled traffic or the number of configured port slots. We demonstrate the optimization potential of the proposed approach using a mixed-criticality system from the automotive domain.

References

  1. T. Blickle, J. Teich, et al. System-level synthesis using evolutionary algorithms. Design Automation for Embedded Systems, pp. 23--58, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. F. Boniol, P.-E. Hladik, et al. A framework for distributing real-time functions. In International Conference on Formal Modeling and Analysis of Timed Systems, pp. 155--169. 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. K. Deb, A. Pratap, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, pp. 182--197, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. D. Le Berre and A. Parrain. The SAT4J library, release 2.2, system description. Journal on Satisfiability, Boolean Modeling and Computation, pp. 59--64, 2010.Google ScholarGoogle Scholar
  5. M. Lukasiewycz, M. Glaß, et al. Flexray schedule optimization of the static segment. In Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis, pp. 363--372. 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. M. Lukasiewycz, M. Glaß. Opt4J - A Modular Framework for Meta-heuristic Optimization. In Proceedings of the Genetic and Evolutionary Computing Conference (GECCO 2011), pp. 1723--1730. 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. M. Lukasiewycz, S. Shreejith, et al. System simulation and optimization using reconfigurable hardware. In International Symposium on Integrated Circuits (ISIC), pp. 468--471. 2014.Google ScholarGoogle ScholarCross RefCross Ref
  8. M. Lukasiewycz, M. Streubühr, et al. Combined system synthesis and communication architecture exploration for MPSoCs. In Proceedings of the Conference on Design, Automation and Test in Europe, pp. 472--477. 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. A. Metzner, M. Franzle, et al. Scheduling distributed real-time systems by satisfiability checking. In 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 409--415. 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. OpenDSE. "Open design space exploration framework". http://opendse.sf.net/.Google ScholarGoogle Scholar
  11. Time Sensitive Networking Task Group of IEEE 802.1. IEEE P802.1Qbv/Standard for Local and Metropolitan Area Networks Bridges and Bridged Networks Amendment: Enhancements for Scheduled Traffic, Draft 3.1. 2016.Google ScholarGoogle Scholar
  12. F. Sagstetter, M. Lukasiewycz, et al. Schedule integration for time-triggered systems. In Design Automation Conference (ASP-DAC), Asia and South Pacific, pp. 53--58. 2013.Google ScholarGoogle ScholarCross RefCross Ref
  13. F. Smirnov, M. Glaß, et al. Formal timing analysis of non-scheduled traffic in automotive scheduled tsn networks. In Design, Automation and Test in Europe (DATE). 2017.Google ScholarGoogle Scholar
  14. W. Steiner. An evaluation of smt-based schedule synthesis for time-triggered multi-hop networks. In Real-Time Systems Symposium (RTSS), pp. 375--384. 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Optimizing Message Routing and Scheduling in Automotive Mixed-Criticality Time-Triggered Networks

      Recommendations

      Comments

      Login options

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

      Sign in
      • Published in

        cover image ACM Conferences
        DAC '17: Proceedings of the 54th Annual Design Automation Conference 2017
        June 2017
        533 pages
        ISBN:9781450349277
        DOI:10.1145/3061639

        Copyright © 2017 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]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 18 June 2017

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article
        • Research
        • Refereed limited

        Acceptance Rates

        Overall Acceptance Rate1,770of5,499submissions,32%

        Upcoming Conference

        DAC '24
        61st ACM/IEEE Design Automation Conference
        June 23 - 27, 2024
        San Francisco , CA , USA

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader