The Multi-Domain Frame Packing Problem for CAN-FD

Prachi Joshi, Haibo Zeng, Unmesh D. Bordoloi, Soheil Samii, S. S. Ravi, Sandeep K. ShuklaECRTS 2017 · OpenReview

TL;DR

This paper tackles the challenge of efficiently packing data into frames for CAN-FD, a crucial communication protocol in modern vehicles. They introduce a novel two-stage approach that considers data flow across multiple vehicle sub-systems (domains), a significant advancement over previous single-domain solutions. Their work offers both an optimal (ILP) and a practical (greedy heuristic) method, demonstrating substantial bandwidth savings and improved schedulability.

What Problem Does This Paper Address?

Modern vehicles are increasingly complex, with numerous Electronic Control Units (ECUs) distributed across different functional domains (e.g., powertrain, chassis, infotainment). These ECUs constantly exchange data, and the Controller Area Network with Flexible Data-Rate (CAN-FD) is a key protocol for this communication. However, existing methods for "frame packing" – the process of bundling data signals into transmission frames – typically assume a single, isolated CAN-FD bus. This overlooks the reality of multi-domain systems where data frequently travels between these domains. This cross-domain traffic creates bandwidth bottlenecks and complicates the task of ensuring timely data delivery (schedulability). This paper addresses this gap by proposing a framework for multi-domain frame packing in CAN-FD, aiming to minimize bandwidth usage and guarantee schedulability across all involved domains.

Methods

The authors propose a two-stage optimization framework:

  1. Signal-to-Frame Packing: The primary goal here is to minimize the total bandwidth utilization across all domains. They offer two approaches:
  2. Integer Linear Programming (ILP): This method provides an optimal solution but is computationally intensive and doesn't scale well for large systems. It formulates the problem as a set of linear constraints to find the absolute best packing.
  3. Greedy Heuristic (Bandwidth Best-Fit): This approach is designed for scalability. It iteratively packs signals into frames that minimize the overall system bandwidth utilization, considering signals from the same ECU and their harmonic period constraints.
  4. Priority Assignment: Once frames are packed, this stage assigns priorities to ensure schedulability. They extend Audsley's algorithm, a well-established method for priority assignment, to handle multi-domain frames. This modified algorithm checks schedulability across all relevant domains for each frame.

Handling Infeasibility: If the priority assignment stage fails to find a schedulable solution, the framework employs a repacking strategy. This involves unpacking frames (based on destination domains or deadlines) and then repacking the signals using various heuristics (first-fit, best-fit, worst-fit).

Datasets

The authors generated synthetic systems for their experiments. These systems were created based on guidelines for real-world automotive benchmarks, with modifications to simulate signal characteristics (periods, sizes) and their distribution. They specifically focused on systems with multiple domains, varying numbers of ECUs, and a range of signal counts. No pre-existing public datasets were explicitly mentioned or used.

Key Insights and Ideas

  • The Importance of Cross-Domain Consideration: Ignoring inter-domain communication leads to significantly higher bandwidth utilization. Explicitly accounting for data flow between domains is crucial for efficient CAN-FD usage.
  • Two-Stage Optimization is Effective: Separating the packing problem (minimizing bandwidth) from the priority assignment problem (ensuring schedulability) provides a structured way to tackle this complex issue.
  • Greedy Heuristic is a Viable Alternative to ILP: While ILP offers optimality, the greedy heuristic provides a highly competitive solution in terms of bandwidth utilization with a dramatic improvement in runtime, making it suitable for real-world industrial applications.
  • Harmonic Period Constraint is Key: The requirement that signals within a frame must have harmonic periods is a critical constraint that influences packing decisions and schedulability.
  • Repacking Strategies Can Salvage Infeasible Solutions: When initial packing and priority assignment fail, intelligent repacking methods can often salvage the situation and achieve schedulability.

Key Results

  • Bandwidth Savings: The proposed multi-domain approach, particularly the greedy heuristic, achieved bandwidth utilization reductions of 6-10% per domain compared to a baseline that ignored cross-domain traffic.
  • Greedy vs. ILP Performance: The greedy heuristic's bandwidth utilization was very close to the optimal ILP solution, with a maximum mean difference of only 2.7% for systems with 220 signals.
  • Runtime Efficiency: The greedy heuristic was orders of magnitude faster than the ILP. For systems with 220 signals, the ILP took over 2.5 hours, while the greedy approach was significantly faster. For very large systems (up to 1000 signals), the greedy approach still ran in under 6 seconds.
  • Schedulability: The modified Audsley's algorithm, combined with repacking strategies, was effective in finding schedulable solutions for a high percentage of tested systems. The "All" heuristic with first-fit repacking was particularly successful.

Limitations and Future Work

  • ILP Scalability: The ILP formulation, while optimal, does not scale to industrial-sized problems due to its exponential time complexity.
  • Heuristic Optimality: The greedy heuristic provides near-optimal solutions but is not guaranteed to be globally optimal.
  • Future Work: The authors suggest extending their work to heterogeneous multi-domain systems, where different domains might use various communication protocols (e.g., CAN, Ethernet). They also aim to explore other optimization metrics like extensibility and robustness.

Summary updated

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
@inproceedings{joshi2017multi,
  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 = {ECRTS},
  year = {2017},
  url = {https://openreview.net/forum?id=9FSq2Qrg3W2},
}
Figure