Multimedia search: From Lab to Web
Download
Report
Transcript Multimedia search: From Lab to Web
Markov Reward Models
By H. Momeni
Supervisor: Dr. Abdollahi Azgomi
Contents
Modeling Taxonomy
Markov Reward Models Definition
Reliability measures
Availability measures
Performance measures
Conclusion
2
31
Markov Reward Models
MODELING TAXONOMY
“All Models are Wrong; Some Models are Useful” George Box
Simulation
Modeling
Non-State-Space
Method
Analytic modeling
State-Space
Method
3
31
Markov Reward Models
Non-State-Space Modeling Taxonomy
Non-State-Space method
Performance models
Queuing models
Dependability models
Fault Tree models
Reliability Block Diagram models
4
31
Markov Reward Models
State Space Modeling Taxonomy
discrete-time Markov chains
Markovian models
continuous-time Markov chains
Markov reward models
State space models
Semi-Markov process
Non-Markovian models
Markov regenerative process
5
31
Non-Homogeneous Markov
Markov Reward Models
Motivation
Extension of CTMC to Markov reward models make them
even more useful
Markov reward models is used as a means to obtain
performance and dependability measures.
6
31
Markov Reward Models
Dependability Concepts
DEPENDABILITY
ATTRIBUTES
AVAILABILITY
RELIABILITY
SAFETY
CONFIDENTIALITY
INTEGRITY
MAINTAINABILITY
MEANS
FAULT
FAULT
FAULT
FAULT
THREATS
FAULTS
ERRORS
FAILURES
PREVENTION
REMOVAL
TOLERANCE
FORECASTING
Faults are the cause of errors that may lead to failures
7
31
Fault
Error
Markov Reward Models
Failure
SECURITY
MRM Formal Definition
A Markov reward model consists of a continuous time
Markov chain X={X(t), t 0)} with a finite state space S,
and a reward function r where r:S
Usually, for each state i S, r(i) represents the reward
obtained per unit time in that state
With MRMs, rewards can assign to states or transitions
The reward rates are defined based on the system
requirements (availability, reliability, performance,…)
8
31
Markov Reward Models
Formal Definitions
is the system reward rate at time t
Accumulated reward in the interval [0, t) is denoted as
The expected accumulated reward is
Li(t) denotes the expected total time the CTMC spends
in state i during the interval [0, t]
9
31
Markov Reward Models
Formal Definition (cont’d)
Let i be the steady state probability for state i
The expected steady-state reward rate is
The expected instantaneous reward rate is
10
31
Markov Reward Models
Example
A three state Markov Reward model
The reward rate vector is r=(3,1,0)
Initial probability vector is
11
31
Markov Reward Models
12
31
Markov Reward Models
Case Study
Consider a multiprocessor system with n processor elements
processing a given workload
13
31
Markov Reward Models
System Availability
Definition: The availability of a system at time t (A(t)) is the
probability that the system is accessible to perform its tasks correctly
Availability measures are based on a binary reward structure
One processor is sufficient for the system to be up, otherwise it is
considered as being down
Set of states
where
and
Reward rate 1 is attached to the states in U and a reward rate 0 to
those in D
14
31
Markov Reward Models
System Availability
Reward function r is:
Availability reward rates
Instantaneous availability is :
15
31
Markov Reward Models
System Availability
Unavailability can be calculated with a reverse reward assignment
to that for availability
Steady state availability
16
31
Markov Reward Models
System Availability
There are related measures that do not rely on the binary
reward structure (e.g. uptime, number of repair calls)
Mean uptimes reward rates
Mean transient uptime
17
31
Markov Reward Models
System Availability
Very important measures related to the frequency of
certain events of interest (e.g. average number of repair
calls in [0,t) )
Reward rates for average number of
repair calls in [0,t)
With repair rate
the transient average number of repair
call
and steady-state
18
31
Markov Reward Models
System Reliability
Definition: The reliability of a system at time t (R(t)) is the probability
that the system operation is proper throughout the interval [0,t]
A binary reward function r is defined that assigns reward
rates 1 to up states and reward rates 0 to down states.
19
31
Markov Reward Models
System Reliability
Reliability is the likelihood that an unwanted event has
not yet occurred since the beginning of the system
operation.
T is the time to the next occurrence of an unwanted
(failure) event
Reward rates for reliability
20
31
Markov Reward Models
System Reliability
21
31
Markov Reward Models
System Reliability
Mean time to the occurrence of an unwanted (failure)
event is given by:
Unreliability follows as the complement:
The unreliability also could be calculated based on a
reward assignment complementing the one in Table
22
31
Markov Reward Models
System Reliability
Related to Reliability measures, the expected number of
catastrophic events C(t) in [o,t) is important
Reward assignment for predicting
the number of catastrophic incidents
23
31
Markov Reward Models
System and Task Performance
Definition: measure of responsiveness
The use of reward rates is not restricted to availability,
reliability and performability models
This concept can also be used in pure (failure-free)
performance models (e.g. throughput, response time,
utilization, total task loss probability)
24
31
Markov Reward Models
System and Task Performance
The values
are used to characterize the percentage
loss of tasks arriving at the system in state
Reward rates for computing the total loss
probability
Reward rates for throughput
25
31
Markov Reward Models
System and Task Performance
The expected total loss probability, TLP, in the steady
state an transient state TLP(t) are:
26
31
Markov Reward Models
System and Task Performance
Throughput can be achieved by assigning state transition
rates corresponding to departure from a queue (service
completion) as reward rates
Mean response time can be achieved by assigning
number of customers present in a state as a reward rate
Utilization is based on binary reward structure, if a
particular resource is occupied in a given state, reward
rate 1 is assigned, otherwise reward rate 0, indicates the
idleness of the resources.
27
31
Markov Reward Models
System and Task Performance
imagine customers arriving at a system with λ, service time is μ
Single server
Throughput reward rates
Mean number of
customers reward rates
28
31
Markov Reward Models
Utilization reward rates
Performance’s Measures
Throughput
Mean number of customers
Mean response time
– Use Little’s law
Utilization
29
31
Markov Reward Models
Conclusion
MRM is State space model
MRM is more useful than CTMC to obtain Performance
and dependability measures
Reward Rates are assigned based on system
requirements
Structure of Reward rate can be various (usually binary)
Stochastic Reward Nets (SRN) are an extension on SPN
that assign reward rate to transitions
30
31
Markov Reward Models
References
Gunter Bluch et al, Queuing network and markov chain, 2nd
Ed., John Wiley and Sons, 2006
J.c. Laprie, Fundamental Concepts of Dependability, IEEE
Transaction, 2004
K. Trivedi, Probability and Statistics with Reliability, Queuing,
and Computer Science Applications, 2nd Ed., John Wiley and
Sons, New York, 2001
B. Haverkort et al, Performability Modeling, John Wiley, 2001
31
31
Markov Reward Models