Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised
Open accessThe DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Abstract
Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times of CAN messages could be calculated and hence guarantees provided that message response times would not exceed their deadlines. This seminal research has been cited in over 200 subsequent papers and transferred to industry in the form of commercial CAN schedulability analysis tools. These tools have been used by a large number of major automotive manufacturers in the design of in-vehicle networks for a wide range of cars, millions of which have been manufactured during the last decade. This paper shows that the original schedulability analysis given for CAN messages is flawed. It may provide guarantees for messages that will in fact miss their deadlines in the worst-case. This paper provides revised analysis resolving the problems with the original approach. Further, it highlights that the priority assignment policy, previously claimed to be optimal for CAN, is not in fact optimal and cites a method of obtaining an optimal priority ordering that is applicable to CAN. The paper discusses the possible impact on commercial CAN systems designed and developed using flawed schedulability analysis and makes recommendations for the revision of CAN schedulability analysis tools.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source doesn’t support the claim as written.
In the citing paper
“It is well-known that there is no optimal priority assignment policy when the system is non-preemptive and the tasks have arbitrary deadlines (deadlines that can be greater than the periods) [5].”
From Real-Time Analysis of Time-Critical Messages in IEC 61850 Electrical Substation Communication Systems (2019) · cites this paper as [5]
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“In this paper is presented an analytical assessment tool that is based on legacy response time analysis research works [3-6] previously proposed for the analysis of CAN (Controller Area Network) communication.”
From Real-Time Analysis of Time-Critical Messages in IEC 61850 Electrical Substation Communication Systems (2019) · cites this paper as [5]
The cited source says what the claim attributes to it.
In the citing paper
“The adoption of similar analysis tools in the context of CAN networks leveraged the average bus utilization from around 35% to 80% due to the designers' confidence that the time constraints of all tasks would be met even for high load conditions [5].”
From Real-Time Analysis of Time-Critical Messages in IEC 61850 Electrical Substation Communication Systems (2019) · cites this paper as [5]
The cited source says what the claim attributes to it.
In the citing paper
“The response time analysis for a non-preemptive fixed-priority system, as proposed in [3-5], can be adapted to estimate the maximum response time of message exchanges in an IEC 61850 process bus communication system Equation (1).”
From Real-Time Analysis of Time-Critical Messages in IEC 61850 Electrical Substation Communication Systems (2019) · cites this paper as [5]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Scheduling algorithms for multiprogramming in a hard-real-time environment
Liu, C. L., & Layland, J. W. (1973) · Journal of the ACM · doi:10.1145/321738.321743 · Cited by 8,433
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
LIU, C. L., & LAYLAND, J. W. (2002) · Readings in Hardware/Software Co-Design · doi:10.1016/b978-155860702-6/50016-8 · Cited by 3,233
On the complexity of fixed-priority scheduling of periodic, real-time tasks
Leung, J. Y.-T., & Whitehead, J. (1982) · Performance Evaluation · doi:10.1016/0166-5316(82)90024-4 · Cited by 1,154
Fixed priority scheduling of periodic task sets with arbitrary deadlines
Lehoczky, J. P. (1990) · [1990] Proceedings 11th Real-Time Systems Symposium · doi:10.1109/real.1990.128748 · Cited by 802
An extendible approach for analyzing fixed priority hard real-time tasks
Tindell, K. W., Burns, A., & Wellings, A. J. (1994) · Real-Time Systems · doi:10.1007/bf01088593 · Cited by 565
Self-citationCalculating controller area network (CAN) message response times
Tindell, K., Burns, A., & Wellings, A. (1994) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)45747-8 · Cited by 439
Self-citationAnalysing real-time communications: controller area network (CAN)
Tindell, Hansson, & Wellings (1994) · Proceedings Real-Time Systems Symposium REAL-94 · doi:10.1109/real.1994.342710 · Cited by 427
Calculating controller area network (can) message response times
Tindell, K., Burns, A., & Wellings, A. J. (1995) · Control Engineering Practice · doi:10.1016/0967-0661(95)00112-8 · Cited by 420
Self-citationOPTIMAL PRIORITY ASSIGNMENT AND FEASIBILITY OF STATIC PRIORITY TASKS WITH ARBITRARY START TIMES
Audsley, N. (2007) · Cited by 318
Scheduling fixed-priority tasks with preemption threshold
Wang, Y., & Saksena, M. (2003) · Proceedings Sixth International Conference on Real-Time Computing Systems and Applications. RTCSA'99 (Cat. No.PR00306) · doi:10.1109/rtcsa.1999.811269 · Cited by 267
Preemptive priority-based scheduling: an appropriate engineering approach
Burns, A. (1995) · Cited by 252
Self-citationFixed priority scheduling periodic tasks with varying execution priority
Harbour, M. G., Klein, M. H., & Lehoczky, J. P. (2002) · [1991] Proceedings Twelfth Real-Time Systems Symposium · doi:10.1109/real.1991.160365 · Cited by 171
Fault-tolerant broadcasts in CAN
Rufino, J., Veríssimo, P., Arroz, G., Almeida, C., & Rodrigues, L. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1998.689464 · Cited by 117
Scheduling tasks with mixed preemption relations for robustness to timing faults
Regehr, J. D. (2003) · doi:10.1109/real.2002.1181585 · Cited by 113
Probabilistic analysis of CAN with faults
Broster, I., Burns, A., & Rodríguez-Navas, G. (2003) · doi:10.1109/real.2002.1181581 · Cited by 98
Self-citationIntegrating reliability and timing analysis of CAN-based systems
Hansson, H., Nolte, T., Norström, C., & Punnekkat, S. (2002) · IEEE Transactions on Industrial Electronics · doi:10.1109/tie.2002.804970 · Cited by 89
Bril, R. J., Lukkien, J. J., & Verhaegh, W. (2007) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2007.38 · Cited by 88
Self-citationProbabilistic worst-case response-time analysis for the controller area network
Nolte, T., Hansson, H., & Norström, C. (2004) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rttas.2003.1203052 · Cited by 85
Schneider, F. B., Gries, D. J., & Schlichting, R. D. (1984) · Science of Computer Programming · doi:10.1016/0167-6423(84)90009-1 · Cited by 84
Response time analysis under errors for CAN
Punnekkat, S., Hansson, H., & Norström, C. (2002) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rttas.2000.852470 · Cited by 84
An analysable bus-guardian for event-triggered communication
Broster, I., & Burns, A. (2004) · International Symposium on System-on-Chip · doi:10.1109/real.2003.1253288 · Cited by 62
Self-citationMinimizing CAN response-time jitter by message manipulation
Nolte, T., Hansson, H., & Norström, C. (2003) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rttas.2002.1137394 · Cited by 54
Timing Analysis of Real-Time Communication Under Electromagnetic Interference
Broster, I., Burns, A., & Rodríguez-Navas, G. (2005) · Real-Time Systems · doi:10.1007/s11241-005-0504-z · Cited by 47
Self-citationShare-Driven Scheduling of Embedded Networks
Nolte, T. (2006) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 37
Message response time analysis for ideal controller area network (CAN) refuted
Bril, R. J., Lukkien, J. J., Davis, R. I., & Burns, A. (2006) · TU/e Research Portal · Cited by 29
Self-citationComputational System for Real-Time Distributed Control
Rufino, M. (2002) · Cited by 17
Bril, R. J. (2006) · TU/e Research Portal · Cited by 13
Self-citation
Research works printed but not linked: 8
- Bril RJ, Lukkien JJ, Davis RI, Burns A (2006b) Message response time analysis for ideal Controller Area Network (CAN) refuted. In: Proceedings of the 5th International Workshop on Real-Time Networks (RTN’06)
- Broster I (2003) Flexibility in dependable communication. PhD Thesis, Department of Computer Science, University of York, UK
- Ferreira J, Oliveira A, Fonseca P, Fonseca JA (2004) An experiment to assess bit error rate in CAN. In: Proceedings of 3rd international workshop of real-time networks (RTN2004). Cantania, Italy, pp 15–18
- Frischkorn H-G (2005) Automotive architecture requirements. In: Proceedings of the summer school on architectural paradigms for dependable embedded systems. Vienna, Austria,. Vienna University of Technology, pp 45–74
- Leohold J (2004) Communication requirements for automotive systems. Keynote speech 5th IEEE international workshop on factory communication systems, Vienna, Austria, Vienna University of Technology
- Leohold J (2005) Automotive system architecture. In: Proceedings of the summer school on architectural paradigms for dependable embedded systems. Vienna, Austria, Vienna University of Technology, pp 545–591
- Tindell KW, Burns A (1994) Guaranteeing message latencies on Controller Area Network (CAN). In: Proceedings of 1st international CAN conference, pp 1–11
- Wang Y, Saksena M (1999) Scheduling fixed priority tasks with pre-emption threshold. In: Proceedings of the 6th international workshop on real-time computing systems and applications (RTCSA’99), pp 328–335
Cited by
Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance
Vestal, S. (2007) · 28th IEEE International Real-Time Systems Symposium (RTSS 2007) · doi:10.1109/rtss.2007.47 · Cited by 547
A Survey of Intrusion Detection for In-Vehicle Networks
Wu, W., Li, R., Xie, G., An, J., Bai, Y., Zhou, J., & Li, K. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2908074 · Cited by 394
Real-Time Wireless Sensor-Actuator Networks for Industrial Cyber-Physical Systems
Lu, C., Saifullah, A., Li, B., Sha, M., Gonzalez, H., Gunatilaka, D., Wu, C., Nie, L., & Chen, Y. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2497161 · Cited by 388
A Survey of Research into Mixed Criticality Systems
Burns, A., & Davis, R. I. (2018) · ACM Computing Surveys · doi:10.1145/3131347 · Cited by 282
Self-citationLeón, H., Montez, C., Valle, O., & Vasques, F. (2019) · Energies · doi:10.3390/en12122272 · Cited by 35
“It is well-known that there is no optimal priority assignment policy when the system is non-preemptive and the tasks have arbitrary deadlines (deadlines that can be greater than the periods) [5].”
BackgroundMethodInfluential
Metadata
- Authors
- Davis, R. I., Burns, A., Bril, R. J., & Lukkien, J. J.
- Affiliations
- University of York (GB)
- Eindhoven University of Technology (NL)
- Corresponding author
- Davis, Robert I.
- Venue
- Real-Time Systems
- Published
- 2007-01-30
- Volume
- 35
- Issue
- 3
- Pages
- 239-272
- ISSN
- 0922-6443 (ISSN-L)
- 1573-1383
- OpenAlex
- W2119167559
- Cited by
- 786
- References
- 27
- Citations by year
- 2026: 12 · 2025: 16 · 2024: 22 · 2023: 33 · 2022: 30 · 2021: 34 · 2020: 37 · 2019: 62 · 2018: 47 · 2017: 47 · 2016: 47 · 2015: 38 · 2014: 61 · 2013: 65 · 2012: 79
- FWCI
- 72.20
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by-nc
- creativecommons.org/licenses/by-nc/2.0 (tdm)
- creativecommons.org/licenses/by-nc/2.0 (vor)
- Locations
- Real-Time Systems (publishedVersion, cc-by-nc)
- TU/e Research Portal (publishedVersion)
- TU/e Research Portal (submittedVersion)
- Funders
- Engineering and Physical Sciences Research Council
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Real-Time Systems Scheduling
- Physical Sciences › Engineering › Safety, Risk, Reliability and Quality › Safety Systems Engineering in Autonomy
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
- Keywords
- CAN bus, schedulability analysis, worst-case response time, deadline guarantees, priority assignment, in-vehicle networks
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.