Browse Prior Art Database

Exponential Transformation - Technique for Fast Simulation of Non- Markovian Highly Dependable Systems

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

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+3]

Abstract

An efficient simulation technique for estimating the failure time distribution in models of highly dependable systems is described. The technique employs importance sampling and uses an accelerated exponential distribution for the time to the next failure event.

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

Exponential Transformation - Technique for Fast Simulation of Non- Markovian Highly Dependable Systems

      An efficient simulation technique for estimating the failure
time distribution in models of highly dependable systems is
described.  The technique employs importance sampling and uses an
accelerated exponential distribution for the time to the next failure
event.

      Importance sampling is a general technique for attempting to
obtain variance reduction in rare event simulations; [2,3,4].  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 "balance failure biasing" was
introduced in [2].  This technique was shown to have the desirable
theoretical property known as "bound relative error" in [4].  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 [3]
for simulating highly available systems with non-exponential failure
and repair times.

      A different approach is described based on using an accelerated
exponential distribution for the time between failure events.  When
appropriately applied, this approach also has the bounded relative
error property for estimating the system failure time distribution.
Described is the approach and the calculation of the likelihood ratio
which is required when using importance sampling.  It was assumed
that there are N components which can fail and be repaired.  Let
G(i,x) denote the failure distribution of component i, let g(i,x) be
its density function, and let h(i,x) be its hazard rate function.
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.  If component i is operational at time s, let
f(i,s,t) = g(i,A(i,s) + t)/ G bar (i,A(i,s)) denote the conditional
density that component i fails at time t+s given that it is
operational at time s.  Similarly, if component i is operational at
time s, let F bar (i,s,t) = G bar (i,A(i,s) + t)/ G bar (i,A(i,s))
denote the conditional probability that component i does not fail
before ti...