Browse Prior Art Database

Uniformization-Based Approach to Importance Sampling in Simulations of Non-Markovian Highly Dependable Systems

IP.com Disclosure Number: IPCOM000106482D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 121K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+3]

Abstract

An efficient simulation technique, based on importance sampling and uniformization, for estimating the failure time distribution in models of highly dependable systems with general failure and repair distributions is described.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 41% of the total text.

Uniformization-Based Approach to Importance Sampling in Simulations of Non-Markovian Highly Dependable Systems

      An efficient simulation technique, based on importance sampling
and uniformization, for estimating the failure time distribution in
models of highly dependable systems with general failure and repair
distributions is described.

      Importance sampling is a general technique for attempting to
obtain variance reduction in rare event simulations; [2,4,5].  The
above mentioned papers deal with using importance sampling to
estimate certain performance measures associated with models of
highly dependable systems, such as those that can be described by the
System Availability Estimator (SAVE) modeling language, [1].  For
Markovian systems, a technique called "balanced failure biasing" was
introduced in [2].  This technique was shown to have the desirable
theoretical property known as "bounded relative error" in [5].
Bounded relative error implies an upper bound on the relative error
of a rare event simulation estimate, even as the probability of the
rare event goes to zero.  A "clock rescheduling" approach was
proposed in [4] for simulating highly available systems with
non-exponential failure and repair times.

      We describe a different approach, based on uniformization [3]
for efficient simulation of non-Markovian models of highly dependable
systems.  When appropriately applied, this approach also has the
bounded relative error property for estimating the system failure
time distribution.  We assume that there are N components which can
fail and be repaired.  Let G(i,x) denote the failure distribution of
component i, and let h(i,x) be the hazard rate associated with this
distribution.  There is a set of repairmen who repair failed
components according to some arbitrary priority mechanism.  As in
SAVE, when components fail they can affect other components, causing
them to fail as well.  We assume that components are reliable in the
sense that there exists a small epsilon  gt 0 such that h(i,x) le
lambda epsilon sup <b(i)> where 0 lt lambda lt infinity and b(i) ge
1.

      Repair actions will be sampled from their given distributions.
A typical implementation would use a standard "future event list" for
repairs.  "Components affected" probabilities are also sampled from
their given distributions.  Let A(i,s) denote the age of component i
at simulation time s.  Let lambda(i,s) = h(i,A(i,s)) if component i
is operational at time s, and lambda(i,s) = 0 otherwise.  Let
lambda (F,s) identical Sigma sub i=1 sup N lambda (i,s)
denote the total failure rate of all components at time s.  The goal
of the simulation is to estimate gamma = 'P' lbrace tau le t rbrace,
where &tau is the first time that the system enters the set of
failure states.

      Failures are simulated as follows.  Let T(0) = 0.  At time
T(n-1) ( n ge 1), an exponential random variable E(n) with rate
beta(n) is generated where b...