home · mobile · calendar · defenses · 2004-2005 · 

Thesis Defense - Garnett

Adaptive, Nonlinear, Resource-Distribution Control
James Garnett
Computer Science PhD Candidate

Control systems for software resources, such as memory buffers or CPU cycles, are difficult to design due to the bursty nature of the demands for those resources, nonlinear effects that result from adjusting the control variables, and the unpredictable saturation dynamics that result when the resource under control is depleted. Variables derived from gaussian statistics, such as the average of the number of resources in use, are easy to compute, can be used to smooth burstiness, and facilitate controller stability, but may not be representative of the true system state. Abandoning statistics in favor of unaggregated information about the system dynamics becomes critical in resource starvation conditions, wherein minute changes in the operating environment can result in abrupt system failures.

This research describes an adaptive, nonlinear, model-reference software control algorithm in which the variable to be controlled is the full distribution of resource states. In this algorithm the plant is the resource, modeled by a Markov Chain, and the reference is an arbitrary (user-chosen) specification distribution. The state-transition probabilities of this model are estimated on-line from resource demand rates using linear filters, and the estimates are used to adapt the plant behavior to changing operating conditions. A nonlinear Proportional/Integral/Derivative (PID) control scheme is then used to regulate and reduce demands for resources, thereby shaping the stationary distribution of the resource usage to match the specification.

Demonstrations of this resource-distribution control paradigm have proven that it is capable of improving the stability and security of existing software systems, and that the method has low computational and memory overhead. In one example, a TCP/IP network router that previously failed under the load of a simulated Internet Denial of Service (DoS) attack was retrofitted with the controller and subsequently was able to block the attack while simultaneously passing valid Intranet traffic.

Committee: Elizabeth Bradley, Professor (Chair)
Andrzej Ehrenfeucht, Professor
Gary Nutt, Professor
Richard Osborne, Assistant Professor
John Hauser, Department of Electrical and Computer Engineering
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:20)