This paper reviews the research work done on the response time analysis of messages in controller area network (CAN) from the time CAN specification was submitted for standardization (1990) and became a standard (1993) up to the present (2012). Such research includes the worst-case response time analysis which is deterministic and probabilistic response time analysis which is stochastic. A detailed view on both types of analyses is presented here. In addition to these analyses, there has been research on statistical analysis of controller area network message response times. 1. Introduction The arbitration mechanism employed by CAN means that messages are sent as if all the nodes on the network share a single global priority-based queue. In effect, messages are sent on the bus according to fixed priority nonpreemptive scheduling [1]. In the early 1990s, a common misconception was that although the protocol was very good at transmitting the highest priority messages with low latency, it was not possible to guarantee that the less urgent signals carried in lower priority messages would meet their deadlines [1]. In 1994, Tindell et al. [2–5] showed how research into fixed priority preemptive scheduling for single processor systems could be applied to the scheduling of messages on CAN. This analysis provided a method of calculating the worst-case response times of all CAN messages. Using this analysis it became possible to engineer CAN-based systems for timing correctness, providing guarantees that all messages and the signals that they carry would meet their deadlines. In 2007, Davis et al. [1] refuted this analysis and showed that multiple instances of CAN messages within a busy period (this period begins with a critical instant) need to be considered in order to guarantee that the message and the signals that they carry would meet their deadlines, since CAN effectively implements fixed priority nonpreemptive scheduling of messages. Real-time researchers have extended schedulability analysis to a mature technique which for non-trivial systems can be used to determine whether a set of tasks executing on a single CPU or in a distributed system will meet their deadlines or not [1, 2, 4, 5]. The essence of this analysis is to investigate if deadlines are met in a worst-case scenario. Whether this worst case actually will occur during execution, or if it is likely to occur, is not normally considered [6]. In contrast with schedulability analysis, reliability modelling involves the study of fault models, the characterization of distribution functions of faults,
References
[1]
R. I. Davis, A. Burns, R. J. Bril, and J. J. Lukkien, “Controller area network (CAN) schedulability analysis: refuted, revisited and revised,” Real-Time Systems, vol. 35, no. 3, pp. 239–272, 2007.
[2]
K. W. Tindell, H. Hansson, and A. J. Wellings, “Analysing real-time communications: controller area network (CAN),” in Proceedings of the 15th IEEE Real-Time Systems Symposium (RTSS '94), pp. 259–263, IEEE Computer Society Press, 1994.
[3]
K. Tindell and J. Clark, “Holistic schedulability analysis for distributed hard real-time systems,” Microprocessing and Microprogramming, vol. 40, no. 2-3, pp. 117–134, 1994.
[4]
K. Tindell and A. Burns, “Guaranteeing message latencies on control area network (can),” in Proceedings of the 1st International CAN Conference, Citeseer, 1994.
[5]
K. Tindell, A. Burns, and A. J. Wellings, “Calculating controller area network (can) message response times,” Control Engineering Practice, vol. 3, no. 8, pp. 1163–1169, 1995.
[6]
T. Nolte, H. Hansson, and C. Norstrom, “Minimizing CAN response-time analysis jitter by message manipulation,” in Proceedings of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '02), pp. 197–206, September 2002.
[7]
T. Nolte, H. Hansson, and C. Norstrom, “Probabilistic worst-case response-time analysis for the controller area network,” in Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '03), pp. 200–207, May 2003.
[8]
S. Punnekkat, H. Hansson, and C. Norstrom, “Response time analysis under errors for CAN,” in Proceedings of the 6th IEEE Real-Time Technology and Applications Symposium (RTAS '00), pp. 258–265, June 2000.
[9]
H. Hansson, C. Norstr？m, and S. Punnekkat, “Integrating reliability and timing analysis of CAN-based systems,” in Proceedings of the IEEE International Workshop on Factory Communication Systems (WFCS '00), IEEE Industrial Electronics Society, Porto, Portugal, September 2000.
[10]
H. Hansson, C. Norstr？m, and S. Punnekkat, “Reliability modelling of time-critical distributed systems,” in Proceedings of the 6th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems (FTRTFT '00), M. Joseph, Ed., vol. 1926 of Lecture Notes in Computer Science, Springer, Pune, India, September 2000.
[11]
T. Nolte, H. Hansson, C. Norstr？m, and S. Punnekkat, “Using bit-stuffing distributions in CAN analysis,” in Proceedings of the IEEE/IEE Real-Time Embedded Systems Workshop (RTES '01), December 2001.
[12]
K. W. Tindell, A. Burns, and A. J. Wellings, “An extendible approach for analyzing fixed priority hard real-time tasks,” Real-Time Systems, vol. 6, no. 2, pp. 133–151, 1994.
[13]
J. Lehoczky, “Fixed priority scheduling of periodic task sets with arbitrary deadlines,” in Proceedings of the 11th IEEE Real-Time Systems Symposium (RTSS '90), pp. 201–209, IEEE Computer Society Press, December 1990.
[14]
M. G. Harbour, M. H. Klein, and J. P. Lehoczky, “Fixed priority scheduling periodic tasks with varying execution priority,” in Proceedings of the 12th IEEE Real-Time Systems Symposium (RTSS '91), pp. 116–128, IEEE Computer Society Press, December 1991.
[15]
L. George, N. Rivierre, and M. Spuri, “Pre-emptive and non-pre-emptive real-time uni-processor scheduling,” Tech. Rep. 2966, Institut National de Recherche et Informatique et en Automatique, Versailles, France, 1996.
[16]
R. J. Bril, “Existing worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred pre-emption is too optimistic,” CS-Report 06-05, Technische Universiteit, Eindhoven, The Netherlands, 2006.
[17]
A. Burns, “Pre-emptive priority based scheduling: an appropriate engineering approach,” in Advances in Real-Time Systems, S. Son, Ed., pp. 225–248, Prentice-Hall, 1994.
[18]
Y. Wang and M. Saksena, “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, December 1999.
[19]
J. Regehr, “Scheduling tasks with mixed pre-emption relations for robustness to timing faults,” in Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS '02), pp. 315–326, IEEE Computer Society Press, December 2002.
[20]
R. J. Bril, J. J. Lukkien, R. I. Davis, and A. Burns, “Message response time analysis for ideal controller area network (CAN) refuted,” CS-Report 06-19, Technische Universiteit Eindhoven, Eindhoven, The Netherlands, 2006.
[21]
R. J. Bril, J. J. Lukkien, R. I. Davis, and A. Burns, “Message response time analysis for ideal controller area network (CAN) refuted,” in Proceedings of the 5th International Workshop on Real-Time Networks (RTN '06), 2006.
[22]
International Standards Organisation, ISO 11898. Road Vehicles—Interchange of Digital Information—Controller Area Network (CAN) for High-Speed Communication, 1993.
[23]
A. Cheng, L. Zhang, and T. Zheng, “The schedulability analysis and software design for networked control systems of vehicle based on CAN,” in Proceedings of the IEEE 2nd International Conference on Computing, Control and Industrial Engineering (CCIE '11), vol. 2, pp. 274–278, Wuhan, China, August 2011.
[24]
P. Axer, M. Sebastian, and R. Ernst, “Probabilistic response time bound for CAN messages with arbitrary deadlines,” in Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE '12), pp. 1114–1117, Dresden, Germany, March 2012.
[25]
N. Navet, Y. Q. Song, and F. Simonot, “Worst-case deadline failure probability in real-time applications distributed over controller area network,” Journal of Systems Architecture, vol. 46, no. 7, pp. 607–617, 2000.
[26]
I. Broster, A. Burns, and G. Rodriguez-Navas, “Probabilistic analysis of can with faults,” in Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS '02), pp. 269–278, 2002.
[27]
M. Sebastian and R. Ernst, “Reliability analysis of single bus communication with real-time requirements,” in Proceedings of the 15th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC '09), pp. 3–10, November 2009.
[28]
I. Broster and A. Burns, “Comparing real-time communication under electromagnetic interference,” in Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS '04), pp. 45–52, July 2004.
[29]
M. Grenier, L. Havet, and N. Navet, “Pushing the limits of CAN—scheduling frames with offsets provides a major performance boost,” in Proceedings of the 4th European Congress on Embedded Real Time Software, Toulouse, France, 2008.
[30]
L. Du and G. Xu, “Worst case response time analysis for CAN messages with offsets,” in Proceedings of the IEEE International Conference on Vehicular Electronics and Safety (ICVES '09), pp. 41–45, Pune, India, November 2009.
