CSE 590K: Analysis and Control of Computing Systems Using Linear Discrete-Time System Theory

University of Washington, Winter 2008

Joe Hellerstein and Jie Liu


Syllabus:

Week Date Topic Content
1 1/7/2008 Introduction Course structure, objectives of control theory, spreadsheet example, "qualitative control theory", SASO properties.
2 1/14/2008 System, modeling, and structures Modeling systems in the time domain. First principles models using queuing. Modeling with finite state machines.
3 1/28/2008 Basics of LTI systems Signals. Transfer functions. Poles. Steady state gain. Stability. Settling times, block diagrams.
4 2/4/2008 State space modeling & control Multiple-input, multiple-output control. Controllability, observability, hybrid control.
5 2/11/2008 Controllers, control design, control analysis PID controllers. Design using pole placement. Root locus analysis. Analysis of control systems. Gain margins.
6 2/25/2008 Systems with discontinuities. Lyapunov stability; Finite state machines; Hybrid systems; Timed automata; Switched linear systems; Jump linear systems.
7 3/3/2008 Advanced topics Nonlinear control; stochastic control; adaptive control.
8 3/10/2008 Case studies: 1 Throttling utilities in the IBM DB2 database management system and power management in a data center; garbage collection; other?
9 3/17/2008 Case studies: 2 Papers

Lecture Notes:

Software:

Reference Books:

Paper Review and Discussions:

All students will review papers listed in this section. Students taking the class for 1.0 credit will review 2 papers per week; students taking the class for 2.0 credits will review 3 papers per week, and present a 10-15 min discussion of one paper at a time of your choice. The reviews will be turned in via email by Friday before each of the last three lectures (i.e. 2/29/08, 3/7/08, and 3/14/08). Details of what is expected for a review are listed below. Each review should be 1 page and contain the following information:

  • Summary of the paper. What research problem is addressed? How does control theory relate to the problem statement and/or the problem solution? What is the technical approach? How are the results assessed?
  • Strengths of the paper. What results are either particularly interesting or useful?
  • Weaknesses of the paper. What other results or work should be done for the work to have more impact? What are the limitations of the technical approach and/or its assessment?
  • Questions. What didn�t make sense, either as a technical result or in terms of why a particular approach was taken?

Student presentations (2 credits)

There will be 3 presentations on 3/3/08; 3 presentations on 3/10/08; and 4 presentations on 3/17/08. Presentations will be 10-15 minutes (about 5 slides) each. The presenter should either provide an in-depth discussion of one paper along the lines of the topics listed above or the presenter may choose to compare 2 or more papers as to these same criteria.

You should send email to joehe@microsoft.com and jie.liu@microsoft.com by no later than Monday 2/25 to request a date and the paper(s) that you will present. Requests will be honored in the order that they are received. After 2/25, we will assign presentation dates and papers.

Paper discussion schedule

3/3/08 (Performance Control):

  1. Sujay Parekh, Kevin Rose, Yixin Diao, Victor Chang, Joseph L. Hellerstein, Sam Lightstone, Matthew Huras, " Throttling Utilities in the IBM DB2 Universal Database Server" American Control Conference, 2004. [Presenter: Blake Kumabe]
  2. S Parekh, N Gandhi, JL Hellerstein, D Tilbury, TS Jayram, J Bigus, " Using Control Theory to Achieve Service Level Objectives in Performance Management," Real Time Systems Journal, Vol.23, No. 1-2, 2002. [Presenter: Alex Stupakov]
  3. Ying Lu, Tarek F. Abdelzaher, Avneesh Saxena. " Design, Implementation, and Evaluation of Differentiated Caching Services." IEEE Transactions on Parallel and Distributed Systems Vol. 15, No. 5, pp. 440-452, May 2004. [Presenter: Ali Al-Awami]

 

3/10/08 (Resource provisioning)

  1. Jin Heo, Dan Henriksson, Xue Liu, Tare Abdelzaher, " Integrating Adaptive Components: An Emerging Challenge in Performance-Adaptive Systems and a Server Farm Case-Study," in Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS'07), Tucson, Arizona, 2007.[Presenter: Ivayla Dermendjieva]
  2. Pradeep Padala, Kang G. Shin, Xiaoyun Zhu, Mustafa Uysal, Zhikui Wang, Sharad Singhal, Arif Merchant, Kenneth Salem. " Adaptive Control of Virtualized Resources in Utility Computing," Eurosys, 2007 [Presenter: Salvatore Guarnieri]
  3. Dara Kusic and Nagarajan Kandasamy, " Risk-Aware Limited Lookahead Control for Dynamic Resource Provisioning in Enterprise Computing Systems," IEEE International Conference on Autonomic Computing (ICAC '06), June 2006, pp 74-83. [Presenter: Ethan Apter]

     

3/17/2008 (Network and distributed systems)

  1. C. V. Hollot, Vishal Misra, Don Towsley, and Weibo Gong. " A control theoretic analysis of RED," Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Anchorage, AK, USA, April 22�26 2001. IEEE [Presenter: Nathan Parrish]
  2. Srinivasan Keshav. "A control-theoretic approach to flow control." In Proceedings of the ACM Conference on Communications Architecture & Protocols (SIGCOMM �91), pages 3�15, Zurich, Switzerland, September 1991. ACM, ACM Press.[Presenter: Majdi Al Badarin]
  3. Hieu Le Khac, Dan Henriksson, and Tarek F Abdelzaher, " A Control Theory Approach to Throughput Optimization in Multi-Channel Collection Sensor Networks," IPSN 2007, Cambridge, MA. [Presenter: Sandy Chan]
  4. 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 [Presenter: Andrew Peck]

Additional Reading Materials

  1. 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.
  2. Gong Chen, Wenbo He, Jie Liu, Suman Nath, Leonidas Rigas, Lin Xiao, and Feng Zhao, " Energy-Aware Server Provisioning and Load Dispatching for Connection-Intensive Internet Services," NSDI 2008, San Francisco, April 2008.
  3. Sam S. Lightstone, Guy Lohman, and Danny Zilio. "Toward autonomic computing with DB2 universal database." ACM SIGMOD Record, 31(3):55�61, 2002.
  4. Yixin Diao, Joseph L. Hellerstein, Adam Storm,  Maheswaran Surendra, Sam Lightstone, Sujay Parekh, and Christian Garcia-Arellano, �Incorporating Cost of Control Into the Design of a Load Balancing Controller,� . Invited paper, Real-Time and Embedded Technology and Application Systems Symposium, 2004.
  5. Abdelzaher, T. F., Shin, K. G., and Bhatti, N. 2002. "Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach." IEEE Trans. Parallel Distrib. Syst. 13, 1 (Jan. 2002), 80-96.
  6. X. Koutsoukos, P. Antsaklis, "Design of Stabilizing Switching Control Laws for Discrete and Continuous-Time Linear Systems Using Piecewise-Linear Lyapunov Functions," International Journal Control, 75(12), 932-945, 2002

Last modified on: 2/19/2008.

 > People > Jie Liu