A Matrix Pattern Compliant Strong Stochastic Bound

Time Markov

Description

A Matrix Pattern Compliant Strong Stochastic Bound A. Busic and J.M. Fourneau PRiSM, Universite de Versailles Saint-Quentin en Yvelines, 45 Av. des Etats Unis, 78000 Versailles, France Abstract Stochastic bounds are a promising method to analyze QoS requirements. Indeed it is sufficient to prove that a bound of the real performance satisfies the guarantee. How- ever, the time and space complexity issues are not well un- derstood so far. We propose a new algorithm to derive a strong stochastic bound of a Markov chain, using a ma- trix pattern specifing the structural properties a bounding matrix should comply with. Thus we can obtain a simpler Markov chain bounding for which the numerical computa- tion of the steady-state solution is easier. 1. Introduction Despite considerable works (see for instance Stewart's book [16] and the recent LAA issue [9] devoted to this subject), the numerical analysis of Markov chains is still a very difficult problem when the state space is too large or the eigenvalues badly distributed. Fortunately enough, while modeling high speed networks, it is often sufficient to satisfy the requirements for the Quality of Service (QoS) we expect. Exact values of the performance indices are not nec- essary in this case and bounding some reward functions is often sufficient. Stochastic bounds are in general obtained with sample path arguments and coupling theorems ap- plied to models transformation (see [14] for an example on Fair Queueing delays comparison based on sample-paths).

• matrix


• end


• rules associated


• matrix pattern


• macro-state


• dtmc


• strong stochastic


• stochastic complement


• dtmc compliant

Sujets

• Vincent
• Yvelines
• Markov
• United States
• Fourneau
• Princeton University
• Matrix

Informations

• Publié par: pefav
• Nombre de lectures: 8
• Langue: English

Extrait

A Matrix Pattern Compliant Strong Stochastic Bound

A. Busic and J.M. Fourneau

PRiSM, Universit´e de Versailles Saint-Quentin en Yvelines,

45 Av. des Etats Unis, 78000 Versailles, France

Abstract

Stochastic bounds are a promising method to analyze

QoS requirements. Indeed it is sufficient to prove that a

boundof the real performance satisfies the guarantee. How-

ever, the time and space complexity issues are not well un-

derstood so far. We propose a new algorithm to derive a

strong stochastic bound of a Markov chain, using a ma-

trix pattern specifing the structural properties a bounding

matrix should comply with. Thus we can obtain a simpler

Markov chain bounding for which the numerical computa-

tion of the steady-state solution is easier.

1. Introduction

Despite considerable works (see for instance Stewart’s

book [16] and the recent LAA issue [9] devoted to this

subject), the numerical analysis of Markov chains is still

a very difficult problem when the state space is too large

or the eigenvalues badly distributed. Fortunately enough,

while modeling high speed networks, it is often sufficient to

satisfy the requirements for the Quality of Service (QoS) we

expect. Exact values of the performanceindices are not nec-

essary in this case and bounding some reward functions is

often sufficient. Stochastic bounds are in general obtained

with sample path arguments and coupling theorems ap-

plied to models transformation (see [14] for an example on

Fair Queueing delays comparison based on sample-paths).

Here, we only consider Markov chains and algorithmic op-

erations on stochastic matrices. Indeed, in the last decade,

many algorithmic techniques have been designed to model

complex systems with large Markov chains (Stochastic Au-

tomata Network [15], Superpositionof Stochastic Petri Nets

[2], Stochastic Process Algebra [7]). So there are now sev-

eral well-founded methods to model complex systems us-

ing Markov chains with large state space but these models

can still not be solved.

The key idea of ourmethodologyis to design a new chain

such that the reward functionswill be upperor lower bounds

of the exact reward functions. This new chain is a simplified

model of the former one to reduce the complexity of the nu-

merical analysis. These bounds are based on stochastic or-

derings applied to Markov processes (see Stoyan [12] and

other references therein).

The fundamental algorithm to obtain a strong stochastic

(”st”) bound was developped by Vincent [1]. But it has sev-

eral drawbacks: the bounding matrix may be reducible and

the time and space complexity for the storage and the nu-

merical resolution are not considered. Unfortunately they

can be very bad and even worse than the original problem.

Thus we present here a new algorithm based on a matrix

pattern to insure irreducibility, and control the storage and

the resolution.

The remaining of the paper is as follows: in section 2, we

introduce briefly ”st” bounds and Vincent’s algorithm. Sec-

tion 3 is devoted to the matrix pattern approach and in sec-

tion 4 we show two structures which can be represented by

patterns and which simplify the computation.

2. Strong Stochastic Bounds

For the sake of simplicity, we restrict ourselves to Dis-

crete Time Markov Chains (DTMC) with finite state space

but continuous-time models can be con-

sidered after uniformization. In the following,

will denote

the size of matrix

and

will refer to row

of

. First,

we give a brief overview on ”st” ordering for Markov chains

and we obtain a set of inequalities to imply bounds which

gives us the basic algorithm proposed by Vincent and Abu-

Amsha [1].

2.1. A brief overview

Following [12], we define the strong stochastic ordering

by the set of non-decreasing functions.

Definition 1

Let

and

be random variables taking val-

ues on a totally ordered space. Then

is said to be less

than

in the strong stochastic sense, that is,

if and only if

for all non decreasing

functions

whenever the expectations exist.