Design and Analysis of Real-time Message Scheduling under FlexRay Protocol

A typical automobile system consists of many Electronic Control Units (ECUs) for the purposes of safety, comfort, and entertainment applications. FlexRay is a high bandwidth protocol for such automotive requirements, which facilitates communication between distributed ECUs. This thesis addresses some of the issues associated with the design and implementation of the FlexRay protocol. The number of ECUs that are used in automobiles has an increasing trend to implement more functionality, which demands more bandwidth. By minimizing bandwidth requirements for servicing a given workload of periodic and sporadic real-time tasks, one can connect more ECUs to the same FlexRay bus. With this motivation, the first part of this thesis proposes new algorithms for minimizing bandwidth usage of ECUs in both the static and the dynamic segments of FlexRay. FlexRay provides a time-triggered static segment for the transmission of time critical periodic messages. The static segment consists of a fixed number of static slots each with a fixed duration. The duration of the static slot and the number of slots are design parameters which need to be fixed so as to meet all the deadline requirements of the workload in the application. The static slot duration can be minimized by packing the signals into message frames, while respecting scheduling constraints. Since message frames also contain overhead information, the duration of message frames can be optimized by proper signal packing, based on the network utilization constraints of individual ECUs. The thesis proposes a novel algorithm for packing of signals into message frames and fixing the static slot duration so that the total duration of the static segment is minimized. The dynamic segment of FlexRay caters to the transmission of event-triggered signals. A novel algorithm has been proposed to obtain the minimum duration of the dynamic segment while meeting the deadline constraints of all sporadic messages in their worst-case arrival instances. We also extend all these algorithms to the case of slot multiplexing scheme provided by FlexRay 3.0. Modern automobiles provide infotainment and in-car telemetry functions, which produce a high volume of soft deadline messages. This makes the problem of analyzing scheduling algorithms for such traffic important. The dynamic segment of the FlexRay cycle is used for transmission of such soft deadline messages. The second part of this thesis addresses the issue of analyzing the quality of performance in servicing of the soft deadline tasks in the FlexRay protocol. Two quality measures, namely, the average delay in servicing of the soft deadline tasks and the fraction of tasks that miss their deadlines, are considered. The generation of different soft deadline messages is modeled as independent Poisson processes. The generated messages are queued in different queues and are serviced according to pre-assigned priorities for different queues as per the FlexRay protocol. By analyzing this multiple queue model under some mild assumptions, upper bounds on the arrival rates for different messages are derived so that all the queues are stable. Analytical expressions are also derived for average delay and for deadline miss ratio. The correctness of these approximate analytical expressions are demonstrated through simulation studies