MESSAGE DELAY ANALYSIS FOR CAN

BASED NETWORKS

Zhengou Wang, Huizhu Lu, George E. Hedrick

Department of Computer Science

&

Marvin Stone

Agricultural Engineering Department

Oklahoma State University

Stillwater, OK 74078

Tel (405)744-5673

Abstract

Controller Area Network (CAN) defines a medium access control protocol developed by Intel Corp. and Robert Bosch Gmbh. for use in automobiles [Phai88]. In this paper, the authors further provide an analytical model for CAN. With this model, formulae for computing the maximum delay and the expected delay of each type of message are derived. These formulae can be used to evaluate delays of different priority messages. The analytical formulae also reveal the relationship among message delays, message priorities and offered loads of the system. This information is useful to network designers for choosing optimum design parameters, such as bandwidth, and can be used to determine message priorities. Both our analytical and simulation results show that CAN is an efficient medium access control protocol and it provides high channel utilization and short message delay for high priority messages.

I. Introduction

With the continuing decline in the cost of computing, the number of computers and microprocessors used for control systems has increased dramatically. These computers and microprocessors usually do not work in isolation, and with their proliferation comes the demand for suitable communication networks. Local area networks are needed, that can interconnect locally distributed computers and/or microprocessors to form rather complex control systems.

Controller Area Network (CAN) is a small local area network which is suitable especially for use in real-time distributed control systems. In real-time distributed control systems, communication networks play critical roles. Data transmission must be in time. Late delivery of data is a fault that can result in instability or catastrophe.

Data transmission in a network is influenced significantly by the intensity and distribution of message traffic in the network. Data transmission is subject to time-varying delays due to the latency of messages. In addition, messages may be corrupted by noise in the network medium or lost due to buffer saturation in the receiving stations and, therefore, have to be retransmitted. These problems increase the message transmission delay further and degrade the performance of real-time control systems. For a network such as CAN, which may be shared by processors, each with a different nature, appropriate traffic load distribution is critical

Previous research activities related to CAN have concentrated on its application in automobiles [Arne87, Bick89, Eyho89,Gupt88, Inte88 Iver88, Jord88, Jurg86, Kien86, Phai88]. This paper presents an analytical model which predicts the delay characteristics of CAN.

II. Overview of CAN

CAN is a single bus multi-master architecture network. Stations are connected to the bus through a communication controller. A unique feature of CAN is the non-destructive collision detection feature of the design. CAN protocol is a contention based protocol with a prioritized message scheme. Each type of message has a unique message identifier which serves as the name of the message as well as the priority code of the message. Lower numbered identifiers correspond to higher priority messages. The message identifier is the first component of a message sent by a node to the bus. When a node wants to transmit a message it checks the bus to see if there is a message on the bus. If not, the node will begin its transmission immediately. If there is a message on the bus, then transmission is delayed until the current message is completed. Once the node finds the bus idle transmission is begun immediately. Transmitted messages are broadcasted to the bus and all nodes on the network are constantly listening to the bus. When a message appears on the bus, every node checks the message identifier. If this message identifier matches a receiving object header in the node, then the node will retrieve the message otherwise the message is ignored. When two or more nodes begin their transmission at the same time, a collision will occur. As two message identifiers are sent to the bus bit by bit, the dominant 0 bit will overwrite the recessive 1 bit, so the identifier with the smaller binary value will overwrite the identifier with larger value. While a node is transmitting, it listens to see if the bit on the bus is the same as it is sending. If what it hears is different from what it sent, a collision has occurred and it will stop its transmission immediately. The higher priority message will continue until it is finished. After the higher priority message is finished, the lower priority message will try to transmit again. If there are other higher priority messages waiting to be transmitted, the lower priority message will lose arbitration again and again until all higher priority messages are finished.

III. Delay Analysis

Assumptions:

Delay characteristics of CAN based networks can be computed. The delay of a message is defined as the time interval between generation of a message and correct reception of this message. In the following discussion it is assumed that the message generation occurs in a fashion which is characterized by the Poisson distribution, which is expressed as:

In the above expression l is the expected number of messages generated per second and p(n) is the probability of n message generations per second in the network. For certain applications the messages may be generated according to certain pattern on some stations, but we are not concerned with particular applications. In most real situations message generation can be approximated by a Poisson distribution, and this is true especially when the number of stations and messages is large [Mcmi75] . In the same way the message length is also assumed to be exponentially distributed.

With these assumptions, CAN can be modeled as a single channel queuing system with a Poisson arrival process and an exponential distribution for service time. The bus is the server and all waiting messages form a single queue. There is no thrashing effect like CSMA/CD type networks, and no token passing time between data transmissions like token bus and token ring networks. The message transmission process is well described by the model. The priority scheme of CAN only influences the message order inside the queue. From the viewpoints of the bus and the whole system, the basic characteristics of the queue, such as expected number of messages in the system and probability of certain number of messages in the queue, are not influenced by the priority scheme.

For the purposes of simple modeling, it is also assumed that all frames are data frames. CAN supports other types of frames which are unimportant for this analysis. Data frames will dominate the network in normal situations and this assumption simplifies the analysis.

The possibility of message retransmission resulting from noise garbled frames is also ignored. This problem is related to the reliability problem which is usually analyzed in hardware design stage.

To make the analysis simple the time unit used to express the message delay will be the time needed to transmit just one bit. It is the inverse of the bus bandwidth.

Some Conclusions from Queuing Theory

In order to do the following analysis, some conclusions from queuing theory[Klei75, Mcmi73] are needed. These conclusions are summarized below.

Let li be the average message generation rate of ith priority message, l the message generation rate of the whole system, and that totally, n types of messages exist in the system. Then, the message generation rate of the whole system is given by:

In CAN and most distributed control systems, the length of each type of message is a constant. Let Li be the length of ith priority message and L be the expected message length for the whole system. Then L is given by :

or

In CAN, the overhead for each message is a constant. Let OHF be the overhead, F the expected frame length, IFS the minimum interframe space between two consecutive frames, B the bandwidth of the bus, and m the expected number of messages the bus can transmit per second. Then m is given by:

and

The traffic intensity of the network, r , is defined by :

When r < 1 the queuing system is in a stable state and the following conclusions exist. Let P(n) represent the probability of n messages in the system, that is messages in the queue and on the bus, then P(n) is given by:

The probability of no message in the system is:

The probability of one or more messages in the system is:

The expected number of messages in the system is given by:

The expected number of messages on the bus is given by:

r

The expected number of messages in the queue is given by:

Expected Delay of Different Priority Messages

In the following analysis, it is assumed that the network is in a stable state, that is r < 1, so that conclusions from the queuing theory can be employed for the analysis.

The expected delay of any type of message is a function of its priority and the offered load of the system. For ith priority message the expected delay is the sum of the expected waiting time and the time needed to transmit the message itself.

The expected waiting time for the ith priority message consists of three parts: the expected time for current message on the bus to finish, the expected time for transmitting all higher priority messages waiting in the queue, and the expected time for transmitting higher priority messages generated during the waiting time.

The expected waiting time needed for the current message on the bus to finish should be the product of the probability of a message on the bus and the expected number of bits remaining to be transmitted in the current message. From queuing theory, the probability of a message on the bus is the probability of one or more messages in the system which is r . The current message on the bus may be any type of message belonging to the system and the transmission may proceed to any bit of the current frame. It is reasonable to use the expected frame length of the system, F, to represent the length of any frames in the system. It is also reasonable to assume that the probabilities of 1 bit, 2 bits, . . . , up to F bits of the current frame and any one of the 3 interframe spaces have been transmitted are equal, and can be expressed as:

The expected number of bits already transmitted is:

Thus the number of bits including the interframe spaces remaining to be transmitted is :

So, the expected waiting time needed for the current message to finish is:

The second part of the waiting time is the time needed to transmit the higher priority messages waiting in the queue. According to the queuing theory the expected number of message waiting in the queue is:

Among these messages, only those messages with higher priorities will cause the ith priority message to wait. The number of these higher priority messages qh should be proportional to the generation rate of these higher priority messages, so the expected number of higher priority messages is:

or

The expected time needed to transmit the higher priority messages waiting in the queue is:

The third part of the waiting time is the time needed to transmit higher priority messages generated during the waiting time. Let w_i be the expected time the ith priority message has to wait, F_k the length of the frame for kth priority message, then the time needed for ith priority message to wait for the incoming higher priority messages to be transmitted during the waiting time is:

The total expected waiting time for the ith priority message is given by the following equation:

Solving the equation for w_i gives:

The expected delay of ith priority message is the sum of the expected waiting time and the time needed to transmit the ith priority message itself, which is:

or

For the highest priority message, the only waiting time is the time for the current message on the bus to finish and the above formula becomes :

Maximum Delay of Different Priority Messages

The maximum delay of ith priority message appears when this message is generated with all higher priority messages at the same time, and at that moment a longest message has just transferred one bit and seized the bus, and in the waiting time, higher priority messages continue to generate at their maximum rate. The maximum delay of the ith priority message is the maximum waiting time of this message plus the time needed to transmit this message itself. The maximum waiting time is the time needed to finish the current message on the bus plus the time needed to transfer all higher priority message waiting in the queue and arriving during the waiting time. Let Di be the maximum delay of ith priority message, Wi the maximum waiting time for ith priority message, Fk the length of the frame for kth priority message, and Mk the maximum message generate rate of kth priority message, then the maximum waiting time is given by the following equation:

In the right side of the above equation, the first term is the time needed for the longest message on the bus to finish, the second term the time needed to transmit higher priority messages waiting in the queue, the third term the time needed to transmit higher priority messages coming during the waiting time. Solve the equation for w_i gives:

The Maximum delay of ith priority message, Di, is

or

For the highest priority message, the maximum delay becomes :

IV. Simulation of CAN

The expected delay characteristics, obtained via simulation, can be used to verify the analytical results. Twelve set of data are used to run the simulation program. In order to be compatible, every set of data specifies the same network. Only the offered load changes from approximate 10% of the bandwidth to 100% of the bandwidth. Figure 1 and 2 compare the results obtained via simulation with the results obtained using the formulae.








Figure 1 shows the relationship between the expected delay and message priorities and Figure 2 shows the relationship between expected delay and the offered loads. The trends of the curves are the same but they do not completely agree. In figure 2 it can be seen that when the offered load reaches 70% of the bandwidth, the two curves which represent the expected delay of the two lowest priority messages begin to separate. When the load reaches 100% of the bandwidth the difference increases to about five times. This is because on heavy load the lower priority messages have to wait a relatively long time before they get transmitted. While waiting the next message may be generated. The dual port RAM of the communication controller has only one communication object for each type of message. The newly generated message will either overwrite the old message or be discarded. The simulation program adopts the latter policy. In either situation the actual offered load drops and the traffic becomes less heavy. From Figure 2 it can be seen that the delay of lower priority message is very sensitive to the load when the load exceeds 70% of the bandwidth. A small change in the load will cause a big change in the delay. Because the actual load drops, the expected delay drops by a relatively large amount.

The maximum delays of different priority messages are deterministic and they appear in worst case situations in which several messages are generated at the same time. The simulation program is designed to generate messages according to Poisson distribution and is not capable of simulating worst case situation.

V. Conclusion

In this paper the delay characteristics of the Controller Area Network (CAN) are studied. Messages are assumed to be generated according to Poisson distribution. Message transmission errors are ignored and the transmitted frames are assumed to be data frames and remote frames only. It is also assumed that the system is in a stable state, that is the offered load of the system is less than the bus bandwidth. The analytical result may give the control system designer some idea about the relationship among message delays, message priorities, and offered loads of the system and help him or her to choose optimum design parameters. Simulation of the network has been made to verify the analytical result. The simulation program can also be used as a tool to help system designer to evaluate his or her design.

References

[Arne87] Arnett, J. D. , A High Performance Solution for In-Vehicle Networking - "Controller Area Network (CAN)",Earthmoving Industry Conference,Peoria, IL, April 7, 1987, SAE paper #870823.

[Bick89] Bickerton, J. M. , & Chanham, R. , Simulation for Automotive System, International Congress and Exposition,Detroit, Michigan, Feb. 25 - March 3, 1989

[Eyho89] Ey, Horst, Controller Area Network(CAN) Components, Electronic Component & Application vol. 9, no. 3, 1989 pp 155-158

[Gupt88] Gupta, Asnjay, CAN Facilitates In-Vehicle Serial Communications, On Board Communication for Machinery & Control, American Society of Agricultural Engineers paper #88-1649.

[Inte88] Intel Corp. Auto-Communication Chip Replace Bulky Wires,Design News,vol. 44, Aug. 88, p120.

[Iver88] Iversen, Wesley R. , Intel Gets a jump on the Auto Multiplex Market, Electronics, Vol. 61, March 88, pp 31-32.

[Jord88] Jordan, Pat, Controller Area Network, Electronics & Wireless World, Vol 94, Aug. 88, pp. 816-819.

[Jurg86] Jurgen Ronald K. , Coming from Detroit: Network on Wheels,IEEE Spectrum June 1986, pp53-59.

[Kien86] Kiencke, U. , Dais, S. & Litschel, M. , Automotive Serial Controller Area Network,International Congress and Exposition, Detroit, Michigan, Feb. 24-28, 1986 SAE paper #860391.

[Klei75] Kleinrock, L. , Queuing System Volume I : Theory, John Wiley & Sun, Inc. , New York, 1975.

[Mcmi75] McMillan, C. & Gonzalez, R. F. , System Analysis : A Computer Approach to Decision Models, 3rd Edition,Richard D. Irvin,Inc., Homewood, Illinois, 1973.

[Phai88] Phail, F. H. , Controller Area Network - An In-Vehicle Network Solution, 1988 International Summer Meeting of the American Society of Agricultural Engineers, paper #88-3021.