Worst-Case Response Time of a CAN Message Under Fixed-Priority Arbitration

The identifier in a CAN frame is not an address. It is a priority, written into the frame, and the arbitration mechanism makes the numeric comparison literal: at the first bit position where two frames differ, the one with a zero wins. Everything about the timing behaviour of a CAN network follows from treating the identifier as a priority value, and the analysis that gives a bound on message latency is the fixed-priority response-time analysis used for tasks, with two additions that the bus forces.

The model: messages as tasks, the bus as a processor

Consider each message as a periodic task with a period, a deadline, and a transmission time. The transmission time is not a constant: it depends on the payload length and on how many stuff bits the payload happens to require, which varies from frame to frame. The bus is a single-server resource, and a frame occupies it from its start-of-frame bit until the end of its intermission.

The priority of a message is the inverse of its identifier value, because a lower identifier wins arbitration. The set of messages is therefore a fixed-priority task set on one processor, and the standard response-time bound applies with the usual terms: the transmission time, the blocking time, and the interference from higher-priority messages.

The bound is computed iteratively. For a message with index i, the response time is the smallest fixed point of a recurrence in which the initial value is the message’s own transmission time plus the blocking term, and each iteration adds the interference from every higher-priority message, where each contributes one transmission time per instance that could be released during the interval.

The interference term is what makes the calculation more than an addition. A higher-priority message with period T can be released at most a number of times equal to the interval divided by its period, rounded up. Because that rounded-up count depends on the interval being computed, the recurrence must be iterated until it converges or until it exceeds the deadline. A message that misses its deadline has no fixed point below the deadline, and the iteration diverges.

Blocking: the frame that is already on the wire

On a processor, a task can be blocked by a lower-priority task holding a shared resource. On a bus, a message can be blocked by a lower-priority frame that is already in transmission when the message becomes ready. The bus cannot preempt a frame in progress, so the wait is the remaining transmission time of that frame, up to the full duration of the longest lower-priority frame.

Two refinements matter. The first is that the frame in progress may itself be a frame that has just won arbitration against other pending frames, so the blocking term is the maximum transmission time among all lower-priority messages, not the sum. Only one frame can be on the wire at the moment the message becomes ready.

The second refinement concerns the transmit queue of the node itself. If a controller holds several pending frames, they are transmitted in identifier order, so a node’s own lower-priority frame can block its own higher-priority frame by being in the queue ahead of it. A controller that transmits in arrival order instead of identifier order breaks the priority model entirely, and the analysis does not apply. Some controllers offer a mode in which the hardware arbitrates among queued frames; others require software to order the queue, and a driver that ignores the ordering produces a system whose latency bound is far worse than the calculated one.

There is a third case that is often missed. A message can be blocked by a lower-priority frame that is in the middle of an error recovery, which includes retransmissions. A frame that has failed and is being retried still occupies the bus, and the retry can extend the blocking beyond the nominal frame duration. The standard analysis either bounds the number of retries or treats the bus as error-free and then adds a separate allowance, because a bound that assumes no errors is optimistic on a real network.

Computing the transmission time with stuffing

The transmission time of a frame is its bit count divided by the bit rate, and the bit count is not fixed. Stuff bits are inserted after every five consecutive identical bits in the fields that are subject to stuffing, and the number of stuff bits depends on the data values.

The worst case is straightforward to bound: in the stuffed portion of the frame, no more than one stuff bit can be inserted per four data bits, so a portion of n bits can expand to at most n plus n divided by four. Using that worst case for every frame gives a safe but pessimistic bound, because most payloads do not come close to the worst pattern.

A tighter approach computes the exact worst-case stuff count for a specific payload by considering the bit patterns that maximise the number of insertions, which for a fixed-length payload is a small search. The difference between the crude bound and the exact count is a handful of bits per frame, and in a network with many messages the sum of those handfuls can consume a noticeable fraction of the utilisation budget.

The count also depends on the frame format. The start-of-frame bit, the acknowledge field, and the end-of-frame sequence are not stuffed, so the worst-case expansion applies only to the arbitration field, the control field, the data field, and the CRC field. Treating the whole frame as stuffable overestimates the transmission time and therefore underestimates the achievable bus load.

Applying the recurrence

The recurrence is short enough to write out literally. Messages are kept in identifier order, so a message’s index in that list is its priority, the higher-priority set is the prefix before it, and the blocking term is the largest transmission time in the suffix after it.

from math import ceil

def response_time(msgs, i):
    """msgs sorted by ascending identifier; worst-case blocking included."""
    hp = msgs[:i]                       # lower identifier means higher priority
    blocking = max((m["C"] for m in msgs[i+1:]), default=0.0)
    R = msgs[i]["C"] + blocking
    while True:
        interference = sum(ceil(R / m["T"]) * m["C"] for m in hp)
        new = msgs[i]["C"] + blocking + interference
        if new == R:
            return R
        if new > msgs[i]["D"]:
            return None                 # no fixed point: deadline missed
        R = new

The loop terminates either at a fixed point or by exceeding the deadline. The convergence is guaranteed to be fast in practice because the sum of the utilisation of higher-priority messages is below one whenever the message set is schedulable at all; the iteration behaves like a geometric series.

The bound this produces is safe, in the sense that a message that satisfies it will meet its deadline provided the assumptions hold. The assumptions are where the interesting failures live.

Where the analysis is optimistic

The first assumption is that messages are released periodically. Many CAN networks are event-driven: a message is queued when a value changes, and the release pattern depends on the physical process. An event-driven message set can have bursts in which several instances of the same message are queued at once, which the periodic model does not represent. The analysis can still be applied if the event pattern is bounded, but the bound has to come from the application.

The second assumption is that the transmit queue of each node holds only one instance of each message, or that the queue length is bounded. A node that queues every event without limit can build an unbounded backlog, and no response-time bound applies because the message is not even at the head of the queue. Limiting queue depth, and overwriting the oldest instance when a newer value arrives, is the standard remedy for state messages; it is not appropriate for event messages where each instance carries distinct information.

The third assumption is the error-free bus. Retransmission after an error is automatic in CAN, and a retry consumes the bus again. A burst of errors caused by a transient disturbance extends every affected frame and pushes the latency of everything that was waiting behind it. Bounding the effect requires either a bound on the error rate or a separate allowance, and a system that must be certified for a safety function will have that allowance audited.

The fourth is the assumption that the bus is the only resource. A frame that is ready to be transmitted but whose data has not been computed, or whose controller has not been serviced, is delayed by the node’s software. The end-to-end latency from a sensor reading to an actuator acting includes the application’s own scheduling, and a response-time bound for the bus alone is only one term of that sum.

The analysis is nevertheless the right tool, because the alternative is a utilisation rule of thumb. Bus load below some fraction of capacity is often quoted as a design guideline, and it is not a schedulability test: a set of messages can have low average load and still miss a deadline, because the load is not evenly distributed and because the longest frame determines the blocking term for everything below it.

Reading the result back into the identifier map

The bound is a function of the identifier assignment, and that makes identifier allocation a design activity rather than an administrative one. Moving a message to a lower identifier reduces its own latency and increases the latency of everything with a higher identifier. A message set that is infeasible under one assignment may be feasible under another, and the search over assignments is a search over priority orderings.

The practical rules that fall out are: assign the lowest identifiers to the messages with the tightest deadlines relative to their periods, keep the longest frames at the highest identifiers so their blocking term is small for everyone else, and avoid long frames entirely on a bus that must carry urgent short messages. A sixty-four-byte frame at a high rate in an FD network is a long blocking term for every message below it, which is one reason to segregate bulk transfers onto a separate bus rather than to mix them with control traffic.

The frame fields that determine the bit count are covered in CAN frame layout and bit stuffing, and the error-handling behaviour that the retry allowance must cover is in error counters and fault confinement. Both are inputs to the numbers above, and neither can be assumed away.