Theory and Practice of Feedback Control Real-Time Scheduling


John Stankovic, Tarek Abdelzaher, Sang Son, Gang Tao



Our work is concerned with developing a fundamental theory and practice for performance control in future real-time software systems. Future real-time systems such as smart spaces, financial markets, wireless sensor networks, and the world wide web itself will be increasingly data-driven, and thus less amenable to traditional worst-case analysis. One main difficulty in meeting performance constraints in data-driven systems lies in their data-dependent resource requirements which cannot be predicted without interpreting input data. For example, the processing time of a radar data stream may depend on the number of current objects tracked. Similarly, the execution time of an information server (e.g., a web or database server) may depend on the current request rate and the content of requests. A second major issue is that these systems also have highly uncertain workloads; it is not clear how many users will request some resource in the WWW or how many users walk into a smart space. A third element of uncertainty involves the complex interactions among many distributed sites. Consequently, developing data-driven real-time systems will involve techniques for modeling the unpredictability of the environment, handling imprecise or incomplete knowledge, reacting to overload and unexpected failures (i.e., those not expressed by design-time failure hypotheses), and achieving the performance levels and temporal behavior necessary to successfully accomplish specified systems tasks. In doing so, these systems must consider limitations arising from bounds on available processing resources, sensors, actuators, and time.

At present, there is no established theory for analyzing and controlling the dynamics of these systems. We are developing a software-oriented theory and practice of feedback control that will provide aggregate performance guarantees for these types of systems. Our solutions will also demonstrate how to embed these controllers in the operating sytems of these types of applications.

The ultimate vision of this work is that software designers will be able to model parts of software systems (much as control engineers model electrical and mechanical systems), and use those models to develop software control algorithms based on a theory of feedback control. We have already demonstrated that this is feasible for a single site controller in various situations. We are extending the work by making it robust for single node controllers, and looking at large scale distributed systems composed of many interacting controllers. If we are successful, we will establish a scientific basis upon which to design and analyze the aggregate behavior of these large systems that operate under a great deal of uncertainty. This work is in contrast to ad hoc algorithms based on intuition and testing where it is very difficult to characterize the aggregate performance of the system and where major overloads and or anomalous behavior can occur since the algorithms are not developed to avoid these problems.

Recently, we are combining the ControlWare tool which facilitates the creation of feedback controllers with the VEST tool which aids in the composition of embedded systems. By combining the two, we can compose an embedded system with a feedback controller to meet QoS requirements. See the VEST home page for details.

Selected Publications