CSE 590K: Analysis and Control of Computing Systems Using Linear DiscreteTime 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 
Multipleinput, multipleoutput 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:
 Joe Hellerstein, Yixin Diao, Sujay Parekh, and Dawn Tilbury, Feedback Control of Computer Systems, IEEE Press, Wiley Interscience, 2004
 Edward Lee and Pravin Varaiya, Structure and Interpretation of Signals and Systems, Addison Wesley, 2003
 Lennart Ljung, System Identification: Theory for the User, 2nd Edition, Prentice Hall PTR, 1999
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 1015 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 1015 minutes (about 5 slides) each. The presenter should either provide
an indepth 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):

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]

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. 12, 2002.
[Presenter: Alex Stupakov]

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. 440452, May 2004.
[Presenter: Ali AlAwami]
3/10/08 (Resource provisioning)

Jin Heo, Dan Henriksson, Xue Liu, Tare Abdelzaher,
"
Integrating Adaptive Components: An Emerging Challenge in PerformanceAdaptive
Systems and a Server Farm CaseStudy,"
in Proceedings of the 28th IEEE RealTime Systems Symposium (RTSS'07), Tucson, Arizona,
2007.[Presenter: Ivayla Dermendjieva]

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]

Dara Kusic and Nagarajan Kandasamy, "
RiskAware Limited Lookahead Control for Dynamic Resource Provisioning in Enterprise Computing
Systems,"
IEEE International Conference on Autonomic Computing (ICAC '06), June 2006,
pp 7483.
[Presenter: Ethan Apter]
3/17/2008 (Network and distributed systems)

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]

Srinivasan Keshav. "A controltheoretic 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]

Hieu Le Khac, Dan Henriksson, and Tarek F Abdelzaher, "
A Control Theory Approach to Throughput Optimization
in MultiChannel Collection Sensor Networks,"
IPSN 2007, Cambridge, MA.
[Presenter: Sandy Chan]

X. Wang, D. Jia, C. Lu and X. Koutsoukos, "
DEUCON: Decentralized
EndtoEnd Utilization Control for Distributed RealTime Systems,"
IEEE Transactions on Parallel and Distributed Systems, 18(7):9961009, July 2007
[Presenter: Andrew Peck]
Additional Reading Materials

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): 10141027, September
2006.

Gong Chen, Wenbo He, Jie Liu, Suman Nath, Leonidas Rigas, Lin Xiao, and Feng Zhao,
"
EnergyAware Server Provisioning and Load Dispatching for ConnectionIntensive
Internet Services," NSDI 2008, San Francisco, April 2008.

Sam S. Lightstone,
Guy Lohman, and Danny Zilio. "Toward autonomic computing with DB2 universal database."
ACM SIGMOD Record,
31(3):55ï¿½61, 2002.

Yixin Diao, Joseph L. Hellerstein, Adam Storm, Maheswaran Surendra, Sam Lightstone, Sujay Parekh, and Christian GarciaArellano,
ï¿½Incorporating Cost of Control Into the Design of a Load Balancing Controller,ï¿½ .
Invited paper, RealTime and Embedded Technology and Application Systems Symposium,
2004.

Abdelzaher,
T. F., Shin, K. G., and Bhatti, N. 2002. "Performance Guarantees for Web Server
EndSystems: A ControlTheoretical Approach." IEEE Trans. Parallel Distrib. Syst.
13, 1 (Jan. 2002), 8096.

X. Koutsoukos, P. Antsaklis,
"Design of Stabilizing Switching Control Laws for Discrete and ContinuousTime Linear Systems
Using PiecewiseLinear Lyapunov Functions," International Journal Control, 75(12), 932945, 2002
Last modified on: 2/19/2008.