License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2017.12
URN: urn:nbn:de:0030-drops-71551
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7155/
Go to the corresponding LIPIcs Volume Portal

Joshi, Prachi ; Zeng, Haibo ; Bordoloi, Unmesh D. ; Samii, Soheil ; Ravi, S. S. ; Shukla, Sandeep K.

The Multi-Domain Frame Packing Problem for CAN-FD

pdf-format:
LIPIcs-ECRTS-2017-12.pdf (5 MB)

Abstract

The Controller Area Network with Flexible Data-Rate (CAN-FD) is a new communication protocol to meet the bandwidth requirements for the constantly growing volume of data exchanged in modern vehicles. The problem of frame packing for CAN-FD, as studied in the literature, assumes a single sub-system where one CAN-FD bus serves as the communication medium among several Electronic Control Units (ECUs). Modern automotive electronic systems, on the other hand, consist of several sub-systems, each facilitating a certain functional domain such as powertrain, chassis and suspension. A substantial fraction of all signals is exchanged across sub-systems. In this work, we study the frame packing problem for CAN-FD with multiple sub-systems, and propose a two-stage optimization framework. In the first stage, we pack the signals into frames with the objective of minimizing the bandwidth utilization. In the second stage, we extend Audsley's algorithm to assign priorities/identifiers to the frames. In case the resulting solution is not schedulable, our framework provides a potential repacking method. We propose two solution approaches: (a) an Integer Linear Programming (ILP) formulation that provides an optimal solution but is computationally expensive for industrial-size problems; and (b) a greedy heuristic that scales well and provides solutions that are comparable to optimal solutions. Experimental results show the efficiency of our optimization framework in achieving feasible solutions with low bandwidth utilization. The results also show a significant improvement over the case when there is no cross-domain consideration (as in prior work).

BibTeX - Entry

@InProceedings{joshi_et_al:LIPIcs:2017:7155,
  author =	{Prachi Joshi and Haibo Zeng and Unmesh D. Bordoloi and Soheil Samii and S. S. Ravi and Sandeep K. Shukla},
  title =	{{The Multi-Domain Frame Packing Problem for CAN-FD}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Marko Bertogna},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7155},
  URN =		{urn:nbn:de:0030-drops-71551},
  doi =		{10.4230/LIPIcs.ECRTS.2017.12},
  annote =	{Keywords: Frame Packing, CAN-FD, Integer Linear Programming, Audsley's Algorithm}
}

Keywords: Frame Packing, CAN-FD, Integer Linear Programming, Audsley's Algorithm
Collection: 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)
Issue Date: 2017
Date of publication: 23.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI