Simple bounds on deadline failure probabilities in fault-tolerant real-time networks

Real-time communication networks are often required to operate reliably in harsh environments which expose the system to random errors. Although probabilistic schedulability analysis can employ rich stochastic error models to capture these random behaviors, this is most often at the expense of increased analysis complexity. In this paper, some recent results on probabilistic real-time schedulability analysis are extended to propose an efficient method of time complexity O(n log n) to tightly bound the deadline failure probability for a fault-tolerant real-time network transmitting n periodic/sporadic messages. The paper assumes Earliest Deadline First (EDF) message scheduling is employed and considers both random errors and bursts of errors. A simple example is first used to illustrate the technique, and a more realistic example related to EDF scheduling of a Controller Area Network (CAN) then helps to show the technique has practical value. Although EDF message scheduling is assumed, the technique is readily adaptable to other forms of scheduling.