Our congratulations to Rapita Systems Director Robert Davis (also of the University of York) and his co-authors Steffen Kollmann, Victor Pollex and Frank Slomka of the University of Ulm, who won the Best Paper Award at the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011), for their work on “Controller Area Network (CAN) Schedulability Analysis with FIFO queues”.
Controller Area Network (CAN) is widely used in automotive applications, with around 750 million CAN enabled microcontrollers manufactured each year. Schedulability analysis techniques are used to guarantee that messages sent on CAN meet their deadlines.
Existing analysis for CAN is based on the assumption that the highest priority message ready for transmission at each node will be entered into network arbitration. In practice, some CAN device drivers implement FIFO rather than priority-based queues, invalidating this assumption.
The research introduced response time analysis and optimal priority assignment policies for CAN messages in networks where some nodes use FIFO queues while others use priority queues.
According to the findings, while FIFO queues are appealing because they are simpler to implement and make the device driver appear more efficient, this move undermines the priority-based message arbitration scheme used by CAN and significantly degrades the overall real-time performance capability of the network.
A case study and experimental evaluation demonstrated the detrimental impact that FIFO queues have on the real-time performance of CAN; the results saw the maximum achievable bus utilisation fall from above 80% to below 40%.