Files in this item



application/pdf3182247.pdf (7MB)Restricted to U of Illinois
(no description provided)PDF


Title:Bounded Aggregation Techniques to Solve Large Markov Models
Author(s):Daly, David M.
Doctoral Committee Chair(s):Sanders, William H.
Department / Program:Electrical Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Markovian modeling of systems is a promising technique used to gauge the performance, dependability, and performability of systems. It can be used to aid design decisions by evaluating a range of design options for a range of environments, and it can be used to increase understanding of operational systems. Unfortunately, Markovian modeling is limited by the "state-space explosion," or the exponential growth of the state space of a Markovian model as detail is added to the model. It is our thesis that aggregation techniques can be used to solve, at an acceptable level of accuracy, Markovian models that are more than an order of magnitude more complex than models solvable by current techniques, and that the aggregation techniques can be automated in many cases. We prove that claim by extending existing aggregation techniques to develop a new partial order that we apply to the solution of large models. In the partial order, if one state is larger than another state then all of the reward variables will be greater for all instants and intervals of time if the model starts in the first state instead of the second state. We show how the partial order can be computed, how it can be used to generate aggregates and compare aggregates to an original model, and how it can be applied to compositionally defined models. We then use the developed aggregation techniques to solve models that would be infeasible to solve otherwise.
Issue Date:2005
Description:190 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2005.
Other Identifier(s):(MiAaPQ)AAI3182247
Date Available in IDEALS:2015-09-25
Date Deposited:2005

This item appears in the following Collection(s)

Item Statistics