Networked Embedded Systems Technology

Researchers: Jie Liu
Advisor:Edward A. Lee
We consider networked embedded systems, where dedicated computers with sensors and actuators communicate via CAN bus, ethernet, bluetooth, or other networking technology. Today, such computers often run a real-time kernel, such as VxWorks, QNX, or frequently, a hand-tuned custom kernel. Software is architected as tasks with priorities. We raise the question of how design of such software would be changed if the networked processors shared a common time base. Although it is by no means trivial in hardware to achieve this, it has been demonstrated with high precision by Agilent using IP packets over ethernet for synchronization, and at lower precision in the time-triggered architecture from TTTech, which is popular among automotive manufacturers in Europe. At very large scales, the nationwide digital telephony network, which is isochronous (sharing a common frequency, though not quite a common time base) demonstrates that highly reliable networked real-time systems are achievable when there is shared temporal information.

Given a common time base, we can take a very different approach to task management than priority-based scheduling. One approach is to apply conservative distributed discrete-event simulation technology, not to simulation, but to embedded real-time software. In this approach, communication between components is by time-stamped messages. Because of the common time base, components can offer assurance of reacting to messages chronologically, in the order of their time stamps. As long as computational resources allow, this mechanism offers very precise timing of time-critical events without reliance on ad-hoc assignment of priorities. Moreover, synchronization is done via time stamps, not mutual exclusion or semaphores, so priority inversion is not possible. An interesting elaboration of this technique, which relies on faster than real-time computation, is to perform optimistic computation with rollback, where obviously interaction with physical actuators offers a physical barrier to rollback.

We are also exploring a second approach, in collaboration with the group of Prof. Tom Henzinger, where a common time base is used to orchestrate synchronous periodic computations in hard real-time systems. In this approach, specifications of networked systems are formally verifiable because of the common time base. Specifically, the common time base enables a precise definition of system state, and so verification techniques based on exhaustive state-space exploration, particularly model checking, are applicable. This offers the possibility of highly reliable systems with provable safety and liveness properties.

Last updated 11/02/00