Introduction to control theory for computer scientists

Abstract

Feedback control is central to network and systems management. Feedback is employed to achieve service level objectives by taking resource actions, and it is used to optimize resource allocations for a workload mix. While computing systems in general and network management in particular make broad use of feedback control, this has traditionally been done in an ad hoc manner. In contrast, mechanical, electrical, and most other engineering disciplines use control theory to systematically analyze and design feedback systems. Control theory provides a way to determine if feedback loops are stable (e.g., avoid wild oscillations), accurate in their control (e.g., achieve the right resource allocation policies), and settle quickly to their steady state values (e.g., to adjust to workload dynamics). Unfortunately, existing books on control theory are not well suited to computer scientists both because of the examples (e.g., electrical circuits, dash pots) and the emphasize on continuous time instead of discrete time systems. This tutorial provides an introduction to control theory for computer scientists that is sufficient to do basic control analysis and design. The tutorial begins with an introduction to key concepts such as control goals (e.g., regulation, optimization, disturbance rejection) and the control architecture. The second part provides background on linear system theory in areas such as transfer functions, settling times, and steady state gain. The third section shows by example how to analyze a control system to assess its stability, accuracy, and settling time. The fourth section provides case studies of applying control theory including utilities throttling and optimization of buffer pools in a commercial database management system. Although the tutorial introduces some mathematical concepts, the emphasis is on an intuitive approach. In particular, it turns out that spreadsheets provide a simple and very effective environment in which to explore control systems. We use spreadsheet based models of the IBM Lotus Domino Server to probe key concepts and as a vehicle for students to explore the impact of control design and system structure on stability, accuracy, and settling time. The tutorial is a much abbreviated version of a class taught at Columbia University in the Spring and Fall of 2004. The class is based on the Wiley book Feedback Control of Computing Systems by JL Hellerstein, Y Diao, S Parekh, and DM Tilbury.