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:
- Signal-to-Frame Packing: The primary goal here is to minimize the total bandwidth utilization across all domains. They offer two approaches:
- 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.
- 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.
- 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