Graduate Exam Abstract

James Smith

Ph.D. Preliminary

June 8, 2007, 9am

ECE conference room

Robust Resource Allocation in a Stochastic Dynamic Environment

Abstract: In a heterogeneous distributed computing environment, it is often advantageous to allocate system resources in a manner that optimizes a given system performance measure. However, this optimization is often dependent on system parameters that are subject to uncertainty. Thus, an important research problem arises where system resources must be allocated given uncertainty in the system parameters. Robustness can be defined as the degree to which a system can function correctly in the presence of parameter values different from those assumed. Existing research in this area has focused on environments where no prior information is available for characterizing the uncertainty in system parameters. In this research, we present a methodology for quantifying the robustness of resource allocations in environments where the uncertainty in system parameters can be modeled stochastically. We analyze the effectiveness of our approach through direct comparison with prior work in this area. We also demonstrate a design methodology for utilizing the robustness metric to produce effective resource allocation heuristics. This research is also used as a basis for deriving a robustness metric suitable for a dynamic environment. We present a mathematical formulation of robustness in such a stochastic dynamic environment and analyze the effectiveness of the metric for evaluating a select group of resource allocation heuristics. Finally, we consider the optimization of resource allocation in a transshipment overlay network where the arrival rate of packets to the network is not known in advance. We propose a robust decentralized methodology for resource allocation in such an environment and consider an automated robust capacity planning methodology. The main contributions of this research are (1) a mathematical definition of robustness applicable to environments where the uncertainty in system parameters can be modeled stochastically, (2) a demonstration of the use of this metric to design resource allocation heuristics in a static environment, (3) a mathematical definition of robustness in a stochastic dynamic environment, (4) we demonstrate the use of this dynamic robustness metric through the design of resource allocation heuristics suitable for a given heterogeneous computing system.

Adviser: HJ Siegel
Co-Adviser: Anthony Maciejewski
Non-ECE Member: Patrick J Burns, Mechanical Engineering
Member 3: Edwin Chong, ECE
Addional Members:


Program of Study: