Adaptive QoS Control in Distributed Real-Time Embedded Systems

Supported in part by NSF CAREER Award CNS-0448554 and DARPA Adaptive and Reflective Middleware Systems Program NBCHC030140


Team: Chenyang Lu (PI), Yong Fu
Collaborators: Chris Gill (Washington University), Xenofon Koutsoukos, Nicholas Kottenstette, Aniruddha Gokhale, Douglas Schmidt (Vanderbilt University)

Allumni: Xiaorui Wang, Yuanfang Zhang, Yingming Chen

Distributed Real-time Embedded (DRE) systems play a crucial role in many mission-critical applications such as disaster recovery command and control, power grid management, and agile manufacturing. These applications have stringent requirements for end-to-end timeliness and availability whose assurance is essential to their proper operation. In recent years, many DRE systems become open to the Internet and volatile physical environments where system workloads may vary significantly at run-time. Such systems require a paradigm shift from classical real-time computing to adaptive solutions that handle workload variations dynamically. This project develops Adaptive QoS Control, a control-theoretic framework for adaptive DRE systems. This framework includes a suite of adaptive strategies and algorithms, formal models and analysis techniques, and a middleware architecture that integrates multiple adaptation strategies via distributed software feedback control loops. Adaptive QoS Control enables DRE systems to achieve and maintain critical performance assurances despite dramatic changes in operational conditions and system failures. As a result, mission-critical DRE systems will be able to provide significantly more robust and reliable services in a broad range of highly unpredictable environments.



Tutorials

T. Abdelzaher, C. Lu and A. Robertsson, Introduction to Control Theory and Its Application to Feedback Computing, Cyber-Physical Systems Week, April 2013.

T. Abdelzaher, Y. Diao, J.L. Hellerstein, C. Lu and S. Singhal, Recent Advances in the Application of Control Theory to Network and Service Management, IFIP/IEEE International Symposium on Integrated Network Management (IM'09), June 2009

T. Abdelzaher, Y. Diao, J.L. Hellerstein, C. Lu and X. Zhu, Introduction to Control Theory and its Application to Computing Systems, Tutorial Slides at International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'08), June 2008.

T. Abdelzaher, Y. Diao, J.L. Hellerstein, C. Lu and X. Zhu, Introduction to Control Theory and its Application to Computing Systems, Performance Modeling and Engineering, Springer, 2008. Note: Reading for SIGMETRICS'08 tutorial.


Publications

Journal Papers

Y, Chen, C. Lu and X. Koutsoukos, Optimal and Efficient Adaptation in Distributed Real-Time Systems with Discrete Rates, Real-Time Systems, Special Issue on Adaptive Embedded Systems,49(3): 339-366, May 2013. Note: Extended version of the RTSS'07 paper.

Y. Zhang, C. Gill and C. Lu, Configurable Middleware for Distributed Real-Time Systems with Aperiodic and Periodic Tasks, IEEE Transactions on Parallel and Distributed Systems, 21(3): 393-404, March 2010. Note: Extended version of the ICDCS'08 paper.

N. Shankaran, J.S. Kinnebrew, X. Koutsoukos, C. Lu, D.C. Schmidt and G. Biswas, An Integrated Planning and Adaptive Resource Management Architecture for Distributed Real-time Embedded Systems, IEEE Transactions on Computers, Special Issue on Autonomic Network Computing, 58(11): 1485-1499, November 2009.

X. Wang, Y. Chen, C. Lu and X. Koutsoukos, Towards Controllable Distributed Real-Time Systems with Feasible Utilization Control, IEEE Transactions on Computers, 58(8): 1095-1110, August 2009.. Note: Extended version of the ECRTS'07 paper.

X. Wang, C. Lu, and C. Gill, FCS/nORB: A Feedback Control Real-Time Scheduling Service for Embedded ORB Middleware, Microprocessors and Microsystems, 32(8): 413-424, November 2008. Note: Extended version of the RTAS'03 paper.

N. Shankaran, X. Koutsoukos, D. Schmidt, Y. Xue and C. Lu, Hierarchical Control of Multiple Resources in Distributed Real-time and Embedded Systems, Real-Time Systems, Special Issue on Best Papers at Euromicro Conference on Real-Time Systems (ECRTS'06), 39(1-3): 237-282, August 2008.

X. Wang, M. Chen, H.-M. Huang, V. Subramonian, C. Lu, and C. Gill, Control-based Adaptive Middleware for Real-time Image Transmission over Bandwidth-Constrained Networks, IEEE Transactions on Parallel and Distributed Systems, 19(6): 779-793, June 2008. Note: Extended version of the RTAS'04 paper on CAMRIT.

N. Shankaran, N. Roy, D. Schmidt, X. Koutsoukos, Y. Chen and C. Lu, Design and Performance Evaluation of an Adaptive Resource Management Framework for Distributed Real-time and Embedded Systems, EURASIP Journal on Embedded Systems, Special Issue on Operating System Support for Embedded Real-Time Applications, Volume 2008, Article ID 250895, 2008. Note: Extended version of the ISORC'07 paper.

X. Wang, D. Jia, C. Lu and X. Koutsoukos, DEUCON: Decentralized End-to-End Utilization Control for Distributed Real-Time Systems, IEEE Transactions on Parallel and Distributed Systems, 18(7):996-1009, July 2007. Note: Extended version of the RTSS'05 paper on DEUCON

X. Wang, Y. Chen, C. Lu, and X. Koutsoukos, FC-ORB: A Robust Distributed Real-time Embedded Middleware with End-to-End Utilization Control, Elsevier Journal of Systems and Software, Special Issue on Dynamic Resource Management in Distributed Real-Time Systems, 80(7): 938-950, July 2007. Note: Extended version of the RTSS'05 paper on FC-ORB. 

T. He, J.A. Stankovic, M. Marley, C. Lu, Y. Lu, T.F. Abdelzaher, S.H. Son and G. Tao. Feedback Control-based Dynamic Resource Management in Distributed Real-Time Systems. Elsevier Journal of Systems and Software, Special Issue on Dynamic Resource Management in Distributed Real-Time Systems, 80(7): 997-1004, July 2007. Note: Extended version of the RTSS'01 paper. 

C. Lu, Y. Lu, T.F. Abdelzaher, J.A. Stankovic and S.H. Son, Feedback Control Architecture and Design Methodology for Service Delay Guarantees in Web Servers, IEEE Transactions on Parallel and Distributed Systems, 17(9): 1014-1027, September 2006. Note: Extended version of the RTAS'01 paper.

C. Lu, X. Wang and X. Koutsoukos, Feedback Utilization Control in Distributed Real-Time Systems with End-to-End Tasks, IEEE Transactions on Parallel and Distributed Systems, 16(6): 550-561, June 2005. Note: Extended version of the ICDCS'04 paper on EUCON.

Conference Papers

Y. Fu, M. Sha, G. Hackmann and C. Lu. Practical Control of Transmission Power for Wireless Sensor Networks, IEEE International Conference on Network Protocols (ICNP'12), October 2012,

Y. Fu, N. Kottenstette, C. Lu and X. Koutsoukos, Feedback Thermal Control of Real-time Systems on Multicore Processors, ACM International Conference on Embedded Software (EMSOFT'12), October 2012.

Y. Fu, C. Lu and H. Wang, Robust Control-Theoretic Thermal Balancing for Server Clusters, IEEE International Parallel and Distributed Processing Symposium (IPDPS'10), April 2010.

Y. Fu, N. Kottenstette, Y. Chen, C. Lu, X. Koutsoukos and H. Wang, Feedback Thermal Control for Real-time Systems, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'10), April 2010.

J. Balasubramanian, S. Tambe, C. Lu, A. Gokhale, C. Gill and D.C. Schmidt, Adaptive Failover for Real-time Middleware with Passive Replication, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'09), April 2009.

T. Tidwell, X. Gao, H.-M. Huang, C. Lu, S. Dyke and C. Gill, Towards Configurable Real-Time Hybrid Structural Testing: A Cyber-Physical Systems Approach, IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'09). March 2009. Note: Invited paper.

Y. Zhang, C. Gill and C. Lu, Reconfigurable Real-Time Middleware for Distributed Cyber-Physical Systems with Aperiodic Events, International Conference on Distributed Computing Systems (ICDCS'08), June 2008.

Y. Chen, C. Lu and X. Koutsoukos, Optimal Discrete Rate Adaptation for Distributed Real-Time Systems, IEEE Real-Time Systems Symposium (RTSS'07), December 2007. 

X. Wang, Y. Chen, C. Lu, and X. Koutsoukos, On Controllability and Feasibility of Utilization Control in Distributed Real-Time Systems, Euromicro Conference on Real-Time Systems (ECRTS'07), July 2007. 

N. Shankaran, D. Schmidt, X. Koutsoukos, Y. Chen and C. Lu, Design and Performance Evaluation of Configurable Component Middleware for End-to-End Adaptation of Distributed Real-time Embedded Systems, IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'07). May 2007.

Y. Zhang, C. Lu, C. Gill, P. Lardieri and G. Thaker, Middleware Support for Aperiodic Tasks in Distributed Real-Time Systems, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'07), April 2007.

Y. Fu, H. Wang, C. Lu and R.S. Chandra, Distributed Utilization Control for Real-time Clusters with Load Balancing, IEEE Real-Time Systems Symposium (RTSS'06), December 2006.

N. Shankaran, X. Koutsoukos, D. Schmidt, Y. Xue and C. Lu, Hierarchical Control of Multiple Resources in Distributed Real-time and Embedded Systems, Euromicro Conference on Real-Time Systems (ECRTS'06), July 2006.

X. Wang, D. Jia, C. Lu and X. Koutsoukos, Decentralized Utilization Control in Distributed Real-Time Systems, IEEE Real-Time Systems Symposium (RTSS'05), December 2005.

X. Wang, C. Lu and X. Koutsoukos, Enhancing the Robustness of Distributed Real-Time Middleware via End-to-End Utilization Control, IEEE Real-Time Systems Symposium (RTSS'05), December 2005.

X. Koutsoukos, R. Tekumalla, B. Natarajan, and C. Lu, Hybrid Supervisory Utilization Control of Real-Time Systems, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'05), March 2005.

X. Wang, H.-M. Huang, V. Subramonian, C. Lu, and C. Gill, CAMRIT: Control-based Adaptive Middleware for Real-time Image Transmission, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), May 2004.

C. Lu, X. Wang, and X. Koutsoukos, End-to-End Utilization Control in Distributed Real-Time Systems, International Conference on Distributed Computing Systems (ICDCS'04), March 2004.

C. Lu, X. Wang, and C. Gill, Feedback Control Real-Time Scheduling in ORB Middleware, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'03), May 2003.

Workshop Papers

Y. Fu, C. Lu and H. Wang, Control-theoretic Thermal Balancing for Clusters, International Workshop on Feedback Control Implementation and Design in Computing Systems and Networks (FeBID'09), April 2009. Note: Invited paper.

N. Shankaran, J. Kinnebrew, X. Koutsoukos, C. Lu, D. Schmidt and G. Biswas, Towards an Integrated Planning and Adaptive Resource Management Architecture for Distributed Real-time Embedded Systems, Workshop on Adaptive and Reconfigurable Embedded Systems (APRES), April 2008.


Software

FC-ORB: Feedback Controlled ORB (Object Request Broker) Middleware. FC-ORB improves the robustness of real-time ORB middleware by maintaining both functional reliability and real-time performance guarantees. FC-ORB can adapt to fluctuations in application execution times, load disturbances caused by DOS attacks or third-party software, and permanent processor failures. FC-ORB has been released as open source software. Download the code and paper here.

FCS/nORB: Feedback Control real-time Scheduling service on nORB, a small-footprint Object Request Broker (ORB) middleware for networked embedded systems. FCS/nORB provides middleware support for real-time performance portability across platforms and robust performance guarantees in face of workload/platform variations. FCS/nORB has been released as open source software. More information and the recent release of FCS/nORB can be found on the FCS/nORB page.

CAMRIT: Control-based Adaptive Middleware for Real-Time Image Transmission over bandwidth-constrained networks. CAMRIT has been released as Download the code and paper here.

MPRA: MultiParametric Rate Adaptation (MPRA) algorithm for discrete rate adaptation in distributed real-time systems with end-to-end tasks. MPRA can efficiently produce optimal solutions in response to workload variations such as dynamic task arrivals. Through offline preprocessing MPRA transforms an NP-hard utility optimization problem to the evaluation of a piecewise linear function of the CPU utilization. At run time MPRA produces optimal solutions by evaluating the function based on the CPU utilization. Analysis and simulation results show that MPRA maximizes system utility in the presence of varying workloads, while reducing the online computation complexity to polynomial time. Download the code and paper here.

DEUCON: The Decentralized End-to-end Utilization CONtrol (DEUCON) algorithm is designed to guarantee all the end-to-end task deadlines in a real-time computing network, by adaptively controlling the utilizations of all processors. DECUON is systematically designed based on the Distributed Model Predictive Control (DMPC) theory. The novel decomposition strategy and peer-to-peer control structure enable DEUCON to be more scalable, more delay-tolerant in communication and more fault-tolerant. More information about DEUCON can be found here.

EUCON: The End-to-end Utilization CONtrol (EUCON) algorithm employs a distributed performance feedback loop that dynamically enforces desired CPU utilization bounds on multiple processors in distributed real-time embedded systems. EUCON is based on a novel model predictive control approach that models the utilization control problem on a distributed platform as a multi-variable constrained optimization problem. A multi-input-multi-output model predictive controller is designed and analyzed based on a difference equation model of distributed real-time systems. More information about EUCON can be found on the EUCON page.