Tài liệu Queueing mạng lưới và chuỗi Markov P10 pdf

IO

Algorithms for

Non-Product-Form

Networks

Although many algorithms are available for solving product-form queueing

networks (see Chapters 8 and 9), most practical queueing problems lead to

non-product-form networks. If the network is Markovian (or can be Markovi￾zed), automated generation and solution of the underlying CTMC via stochas￾tic Petri nets (SPNs) is an option provided the number of states is fewer

than a million. Instead of the costly alternative of a discrete-event simula￾tion, approximate solution may be considered. Many approximation methods

for non-product-form networks are discussed in this chapter. These algo￾rithms and corresponding sections of this chapter are laid out as shown in

the flowchart of Fig. 10.1. Networks with non-exponentially distributed ser￾vice times are treated in the next section, while networks with FCFS nodes

having different service times for different classes are treated in Section 10.2.

Priority queueing networks and networks with simultaneous resource posses￾sion are treated in Sections 10.3 and 10.4, respectively. Network models of

programs with internal concurrency are treated in Section 10.5. Fork-join

systems and parallel processing are treated in Section 10.6. Networks with

asymmetric server nodes and blocking networks are discussed in Section 10.7

and Section 10.8, respectively.

421

Queueing Networks and Markov Chains

Gunter Bolch, Stefan Greiner, Hermann de Meer, Kishor S. Trivedi

Copyright  1998 John Wiley & Sons, Inc.

Print ISBN 0-471-19366-6 Online ISBN 0-471-20058-1

422 ALGORITHMS FOR NON-PRODUCT-FORM NETWORKS

Fig. 10.1 Different algorithms for non-product-form networks and corresponding sec￾tions.

NON-EXPONENTIAL DISTRIBUTIONS 423

10.1 NON-EXPONENTIAL DISTRIBUTIONS

10.1.1 Diffusion Approximation

Although we present diffusion approximation as a method to deal with net￾works with non-exponential service time and interarrival time distributions,

it is possible to apply this technique to Markovian networks as well. The

diffusion approximation is a technique based on an approximate product￾form solution. In this approximation, the discrete state stochastic process

{K(t) I t 2 O> d escribing the number of jobs at the ith node at time t

is approximated by a continuous state stochastic process (diffusion process)

{Xi(t) ] t 2 O}. For the fluctuation of jobs in a time interval we assume

a normal distribution. In the steady-state, the density function fi(x) of the

continuous state process can be shown to satisfy the Fokker-Planck equation

[Koba74] assuming certain boundary conditions. A discretization of the densi￾ty function gives the approximated product-form-like state probabilities ?i (Ici)

for node i (see Fig. 10.2).

K;(t) - - - - - - - - - - - - - - - +f(j&)

A

Substitute the

discrete process by Discretize the

a continuous density function

diffusion process

t

Xi@> +i (4

Determine the density function of the diffusion pro￾cess for the steady state case

Fig. 10.2 The principle of the diffusion approximation.

Although the derivation of this method is very complex, the method itself

is very simple to apply to a given problem. Steady-state behavior of net￾works with generally distributed service and interarrival times at nodes can be

approximately solved with the restriction of a single single server at each node.

At present no solutions are available for multiple class networks [Mitz97].

Consider a GI/G/l queueing system with arrival rate X, service rate p, and

the coefficients of variation cA and cg of the interarrival and service times,

respectively. Using the diffusion approximation, the following approximated

state probabilities can be obtained [Koba74, ReKo74]:

qk) =

{

l-P, k = 0,

p(l - &P’, Ic > 0,

with:

(10.2)

424 ALGORITHMS FOR NON-PRODUCT-FORM NETWORKS

and p = X/p < 1. Note that y is defined in Eq. (10.2) for convenience so that

fi = exp (y ) . For the mean number of jobs we then have:

(10.3)

Differential equations underlying the diffusion approximation need bound￾ary conditions for their solution. Different assumptions regarding these bound￾ary conditions lead to different expressions. The preceding expressions are

based on the work of [Koba74] and [ReKo74]. Using different boundary con￾ditions, [Gele75] and [Mitz97] get different results that are more accurate

than those of [Koba74] and [ReKo74] for larger values of utilization p. They

[Gele75], [Mitz97] d erived the following expression for the approximated state

probabilities:

1 - P, k = 0,

(10.4)

with ,6 and y as in Eq. (10.2). The mean number of jobs is then:

K=p 1+

1

pc; + c;

2u -4 1 * (10.5)

Next we show how the diffusion approximation can be applied to queueing

networks.

10.1.1.1 Open Networks We can make use of the results for the GI/G/l

system for each node in the network, provided that we can approximate the

coefficient of variation of interarrival times at each node. We assume the

following:

l The external arrival process can be any renewal process

arrival time 1 /X and coefficient of variation CA.

with inter￾l The service times at node i can have any distribution

time l/pi and coefficient of variation cgi.

with mean service

l All nodes in the network are single server with FCFS service strategy.

According to [ReKo74] the diffusion approximation for the

state probabilities of the network have a product-form solution

approximated

it(kl, I I. (10.6)

i=l

NON-EXPONENTIAL DISTRIBUTIONS

with the approximate marginal probabilities as in Eq. (10.1):

jqk;) =

1

l - Pi) I$ = 0,

pi(l- lj@-l, k 2 1,

with

X . ei pi = - 7

Pi

pi = exp ( w - Pi) - c& * pi + c& > *

425

(10.8)

(10.9)

We approximate the squared coefficient of variation of interarrival times at

node i using the following expression:

N

cf$ = 1+

cc C& - 1) .p$. ej . e,l, (10.10)

j=o

where we set:

2 -2 cBO - cA* (10.11)

For the mean number of jobs at node i we get:

k,=l

Similar results are presented in [Gele75], [GeMi80], and [Koba74].

Source

Sink

Fig. 10.3 A simple open queueing network.

(10.12)

Example 10.1 In this example (see Fig. 10.3), we show how to use the

diffusion approximation for a simple open network with N = 2 stations. The

426 ALGORITHMS FOR NON-PRODUCT-FORM NETWORKS

external arrival process has mean interarrival time l/X = 2.0 and the squared

coefficient of variation cA 2 - 0 . 94. The service times at the two stations have

the following parameters:

pl = 1.1, p2 = 1.2, c;r = 0.5, cg2 = 0.8.

With routing probabilities ~110 = ~112 = p21 = p22 = 0.5 and pal = 1, we

compute the visit ratios, using Eq. (7.4):

el = ~01 + e2 . ~21 = 2, e2 = el . ~12 + e2 . p22 = 2.

Node utilizations are determined using Eq. (10.8):

= 0.909,

X . e2

p2 = - = 0.833.

P2

We approximate the coefficients of variation of the interarrival time at both

the nodes using Eq. (10.10):

2

Gil = 1 + C(c& - l)p& * 3

j=o el

= 1 + (ci - I)& * z + <CL - QPL * z + (c”,, - l)p& * 2

= 0.920,

2

42 = 1 + c(c” Bj - 1)~;~ - 3 = 0.825.

j=o e2

With Eq. (10.9) we get:

& = exp at1 - Pd - c;1 * p1+ C&l >

= 0.873,

$2 = exp 21 - P2) - & - P2 + ($2 >

= 0.799.

For the mean number of jobs zi, we use Eq. (10.12) and obtain:

K1=P1=

1 - bl

K2 = A-S- = 4.151, 7.147, 1 - p2

and the marginal probabilities are given by Eq. (10.7):

%1(O) = 1 - pr = 0.091, ?r(k) = pr(1 - /?1)&-’

= 0.116.0.873k-1 for k > 0,

%2(O) = 1 - p2 = 0.167, ;r2(k) = p2(1 - @2)&1

= 0.167.0.799”-1 for k > 0.

NON-EXPONENTIAL DISTRIBUTIONS 427

10.1.1.2 Closed Networks To apply the diffusion approximation to closed

queueing networks with arbitrary service time distributions, we can use

Eq. (10.7) to approximate marginal probabilities %i(ki), provided that the

throughputs Xi and utilizations pi are known. In [ReKo74] the following two

suggestions are made to estimate Xi:

1. For large values of K we use the bottleneck analysis: Search for the

bottleneck node bott (node with the highest relative utilization), set its

utilization to 1, and determine the overall throughput X of the network

using Eq. (10.8). With this throughput and the visit ratios ei, compute

the utilization of each node. The mean number of jobs is determined

using Eq. (10.12).

2. If there is no bottleneck in the network and/or the number K of jobs in

the network is small, replace the given network by a product-form one

with the same service rates pi, routing probabilities pij, and the same

K, and compute the utilizations pi. The approximated marginal proba￾bilities given by Eq. (10.7) are then used to determine the approximated

state probabilities:

(10.13)

where G is the normalizing constant of the network. Then for the mar￾ginal probabilities and the other performance measures improved values

can be determined.

Fig. 10.4 A simple closed queueing network.

Example 10.2 Consider the closed network shown in Fig. 10.4 with the

following parameters:

p1 = 1.1, p2 = 1.2, c& = 0.5, ci2 = 0.8,

and the routing probabilities:

~12 = 1 and ~21 = ~22 = 0.5.

For the visit ratios we use Eq. (7.5) and get:

el = 1, e2 = 2.

At first we choose K = 6 and use the bottleneck analysis to study

network.

the

428 ALGORITHMS FOR NON-PRODUCT-FORM NETWORKS

10.1.1.2.1 Solution with Bottleneck Analysis Let node bott be the bottleneck

with the highest relative utilization:

pb&t = m:x {pi} = A. m”;” , = x . max{0.909,1.667},

which means that node 2 is the bottleneck and therefore its utilization is set

to 1:

p2 = 1.

Using Eq. (10.8) we determine the overall throughput X of the network:

x = p2 * E 1 Z-----E

1.667 0.6.

For the utilization of node 1 we get:

pl=+ 0.545.

Now we use Eq. (10.10) to determine the coefficients of variation of the inter￾arrival times:

2

cam = 1 -t- (&I - l)pfl * el . ell + (c”,, - 1)&r . e2 . ell = 0.9,

&2 = 1 + (431 - l)Pf2 * el * e;l + (~$3, - l)pz, s e2 . e;l = 0.7.

The pi are given by Eq. (10.9):

fi1 = exp ( w - Pl) - &'Pl+c;, >

= 0.3995, &j = exp -

(

W-P4 =

42.P2 +&2 >

1.

Now, by using Eq. (10.12) we can compute the

mean number of jobs:

approximate for the

= 0.908, x2 = K - El = 5.092.

Table 10.1 compares the values obtained by the preceding diffusion approx￾imation (DA) with those obtained via DES. We can see that in this case the

results match very well. Such close matching does not always occur, espe￾cially when one node in the network is highly utilized and the coefficients of

variation are very small.

To show the second method, we assume that there are K = 3 jobs in the

network.

NON-EXPONENTIAL DISTRIBUTIONS 429

Table 10.1 Comparison of results for the example (K = 6)

Pz (DES) z, (DES) Pi (DA) Et (DA)

Node 1 0.544 0.965 0.545 0.908

Node 2 0.996 5.036 1 5.092

10.1.1.2.2 Solution Using Product-Form Approximation Now we substitute

the given network by a product-form one. To determine the utilizations of

this network we can use the MVA and get:

pr = 0.501 and p2 = 0.919.

The coefficients of variation for the interarrival times remain the same as in

the previous met hod:

& = 0.9 and ci2 = 0.7.

For the ,!I& we use Eq. (10.9) and obtain:

j& = exp 21 - Pl) - cil * p1+ c& >

= 0.35, p2 = 0.894.

The approximated marginal probabilities can be computed using Eq. (10.7):

%1(O) = 1 - pr = 0.499, h(O) = 1 - p2 = 0.081,

*r(l) = pr(l - ,&) = 0.326, %(l) = pz(1 - @a) = 0.0974,

fh(2) = pr(1 - /%)br = 0.114, +2(2) = ,oa(l - fi2)& = 0.0871,

?I (3) = p1(1 - /qg = 0.039, h(3) = ,%(1 - &)p; = 0.0779.

Now the following network states are possible:

(3,0), (24, (1,2), (0,3),

whose probability is computed using Eq. (10.13):

k(3,O) = fq3) Gf2(0). ; = 0.00316 - $

?(2,1) = 0.01111~ $

;r(l,2) = 0.02839. $,

+(0,3) = 0.03887. $

With the normalizing condition:

fi(3,O) + ?(2,1) + q1,q + q&3) = 1,

430 ALGORITHMS FOR NON-PRODUCT-FORM NETWORKS

we determine the normalizing constant G:

G = 0.00316 + 0.01111 + 0.02839 + 0.03887 = 0.08153,

which is used to compute the final values of the state probabilities:

ii(3,O) = 0.039, +(2,1) = 0.136, ii(l,2) = 0.348, qo, 3) = 0.477,

and with these state probabilities the improved values for the marginal prob￾abilities are immediately derived:

~~(3) = ~~(0) = 0.039, ni(2) = ~~(1) = 0.136,

q(1) = 7r2(2) = 0.348, 7rl(O) = 7r2(3) = 0.477.

For the mean number of jobs we get

3 -

Ki = c Ice TV = 0.737 and ?7, = 2.263.

k=l

In Table 10.2 DES values for this example are compared to values from the

preceding approximation.

Table 10.2 Comparison of results for the example (K = 3).

~z (DES) K, (DES) pi (DA) ‘is7i (DA)

Node 1 0.519 0.773 0.501 0.737

Node 2 0.944 2.229 0.919 2.263

A detailed investigation of the accuracy of the diffusion method can be

found in [ReKo74]. The higher the utilization of the nodes and the closer the

coefficient of variation is to 1, the more accurate are the results.

10.1.2 Maximum Entropy Method

An iterative method for the approximate analysis of open and closed queueing

networks is based on the principle of the maximum entropy. The term entropy

comes from information theory and is a measure of the uncertainty in the

predictability of an event. To explain the principle of the maximum entropy,

we consider a simple system that can take on a set of discrete states S. The

probabilities 7r( S) for different states are unknown; the only information about

the probability vector is the number of side conditions given as mean values of

suitable functions. Because in general the number of side conditions is smaller

than the number of possible states, in most cases there is an infinite number of

probability vectors that satisfy the given side conditions. The question now is

NON-EXPONENTIAL DISTRIBUTIONS 431

which of these probability vectors shall be chosen as the one best suited for the

information given by the side conditions and which is least prejudiced against

the missing information. In this case the principle of maximum entropy says

that the best-suited probability vector is the one with the largest entropy.

To solve a queueing network using the maximum entropy method (MEM)

the steady-state probabilities r(S) are determined so that the entropy function

H(T) = -C7r(S)lnn(S) (10.14)

S

is maximized subject to given side conditions. The normalizing condition

-the sum of all steady-state probabilities is l-provides another constraint.

In [KGTA88], o en and p closed networks with one or several job classes and

-/G/l, -/G/m nodes are analyzed using this approach. Queueing disciplines

such as FCFS, LCFS, or PS as well as priorities are allowed. An extension to

the case of multiple server nodes is given in [KoA188]. For the sake of simplicity

we only consider single class networks with -/G/l-FCFS nodes based on the

treatment in [Kouv85] and [Wals85].

10.1.2.1 Open Networks If we maximize the entropy by considering the side

conditions for the mean number of jobs I?,, Eq. (7.18), and the utilization pi,

Eq. (7.26)) then the following product-form approximation for the steady-state

probabilities of open networks can be derived [Kouv85]:

where the marginal probabilities are given by:

(10.15)

(10.16)

and where:

(10.17)

b, = c-i - pi z - Ei ’ (10.18)

Gi zz e-i--

1 - pi * (10.19)

To utilize the MEM, we thus need the utilizations pi and

of jobs Ki at each node. The equation pi = Xi/pi can

the mean number

be used to easily

determine pi from the given network parameters. The mean number of jobs

432 ALGORITHMS FOR NON-PRODUCT-FORM NETWORKS

-

Ki can be approximated as a function of the utilization pi and the squared

coefficient of variation of the service and interarrival times [Kouv85]:

(10.20) K, = pi 2 2

I+ c$i + Pic%i

> l-pi ’

if the condition (1 - c2Ai)/(l + c’,i) 5 pi < 1 is fulfilled. The computation of - the Ki is made possible by approximating the squared coefficient of variation

c~i of interarrival times. The following iterative expressions for computing

the squared coefficients of variation is provided by [Kouv85] :

(-ii = -1+ ($.gql~ (10.21)

C3i = 1 + pji (Cgj - 1) ) (10.22)

c$i = pi(l - pi) + (1 - pi)Cii + pfC:i* (10.23)

There are other approximations for the computation of the mean number

of jobs ITi and for the estimation of the necessary squared coefficients of

variation. For more information on these equations, see Section 10.1.3.

With this information, the MEM for the analysis of open queueing networks

can be summarized in the following three steps:

Determine the arrival rates Xi using the traffic equations (Eq. (7.1))

and the utilizations pi = Xi/pi for all nodes i = 1, . . . , N.

Determine the squared coefficients of variation.

-1 Initialize. The squared coefficients of variations c2Ai of the inter￾arrival times are initially set to one for i = 1,. . . , N.

1 STEP 2.2 ] Compute the squared coefficients of variation c2oi of the inter￾departure times of node i for i = 1, . . . , N using Eq. (10.23). Compute the

squared coefficients of variation c& of node i for i = 1, . . . , N and j = 0, . . . , N

using Eq. (10.22). From these the new values of the squared coefficients of

variation cii of the interarrival times are computed using Eq. (10.21).

1 STEP 2.3 ] Check the halting condition. If the old and new values for the

c2Ai differ by more than E, then go back to Step 2.2 with the new & values.

Determine the performance measures of the network beginning

with the mean number of jobs ??i for i = 1,. . . , N using Eq. (10.20) and

then compute the maximum entropy solutions of the steady-state probabili￾ties using Eq. (10.15).

The MEM normally approximates the coefficients of variation less accurate￾ly than the method of Kiihn (see Section 10.1.3) and therefore the method

of Kuhn is generally preferred for open networks with a single job class. The

MEM is mainly used for closed networks.

NON-EXPONENTIAL DISTRIBUTIONS 433

IO. 1.2.2 Closed Networks For closed networks that consist only of -/G/l￾FCFS nodes, the following product-form formulation for the approximated

steady-state probabilities can be given if we maximize the entropy under the

side conditions on the mean number of jobs ??i and the utilization pi:

7r(kl . . .$N) = A- Aqkl). . . . G(K) - cv@N),

with:

(10.24)

(10.25)

and:

G(K) = c F&) . . . . . FN(kN). (10.26)

As in the case of open networks, coefficients ai and bi are respectively given

by Eqs. (10.17) and (10.18). Th e computation of the steady-state probabilities

of closed networks is more difficult than that for open networks as the pi and

17, values of the individual nodes cannot be determined directly. Therefore

we use the following trick: We construct a pseudo open network with the same

number of nodes and servers as well as identical service time distribution and

routing probabilities as the original closed network. The external arrival rates

of this open network are determined so that resulting average number of jobs

in the pseudo open network equals the given number of jobs K in the closed

network:

N

c 11; = K, (10.27)

i=l

where x: denotes the mean number of jobs at the ith node in the pseudo open

network. The pseudo open network arrival rate X is determined iteratively by

using Eqs. (10.20) and (10.27), assuming that the stability condition

Xei

max - <l i { I% 1

is satisfied. Here ei is the relative throughput of node i.

Then the performance measures K;* and pg of the pseudo open network can

be computed using the maximum entropy method for open networks as given

in the last algorithm. These performance measures are then used to determine

the coefficients ai and bi and steady-state probabilities of the pseudo open

network. To compute the probability vector of the original closed network, we

use the convolution method (see Section 8.1). By using the functions Fi(ki),