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

13

Applications

This chapter considers several large applications. The set of applications is

organized into three sections. In Section 13.1, we present case studies of

queueing network applications. In Section 13.2 we present case studies of

Markov chains and stochastic Petri nets. In Section 13.3, case studies of

hierarchical models are presented.

13.1 CASE STUDIES OF QUEUEING NETWORKS

Five different case studies are presented in this section. These range from

multiprocessor system model, several networking applications one operating

system model and a flexible production system model.

13.1.1 Multiprocessor Systems

Models of tightly coupled multiprocessor systems will be discussed first fol￾lowed by models of loosely coupled systems.

13.1,l.l Tightly Coupled Systems Consider a tightly coupled multiprocessor

system with caches at each processor and a common memory, connected to

the processors via a common bus (see Fig. 13.1). The system consists of m

processors and a common memory with n memory modules. A processor

sends a request via the common bus to one of the n memory modules when a

cache miss occurs, whereupon the requested data is loaded into the cache via

603

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

604 APPLICATIONS

PTl Processor n 72 = 1,...,5

cn Cache n n= 1,...,5

iVIAl, Memory Module n n = 1,. . . ,4

fig. 13.1 A multiprocessor system with caches, common memory, and common bus.

the common bus. Figure 13.2 shows a product-form queueing network model

of such a multiprocessor system.

Replies to Memory Requests

Replies to Memory Requests Memory Modules

fig. 13.2 Queueing network model of the multiprocessor system shown in Fig. 13.1.

The m processors are modeled by an IS node and the bus and the memory

modules by single server nodes. The number of requests in the system is

m since a processor is either working or waiting until a memory request is

finished. Using this model we can calculate the utilization of the bus or the

mean response time of a memory request from a processor. The mean time

between two cache misses is modeled by the mean thinking time of the IS

node. Other parameters that we need are the mean bus service time, the mean

memory request time, and, finally, pi, the probability of a request to memory

module i. In the absence of additional information, we assume pi = l/n

CASE STUDIES OF QUEUEING NETWORKS 605

(i = 1,2,... , n). Note that for each cache miss, there are two service requests

to the bus. It is for this reason that with probability 0.5, a completed bus

request returns to the processor station. Similarly, the probability of visiting

memory module i subsequent to the completion of a bus request is pi/2.

We assume that the service times for the two types of bus requests have

the same mean. This assumption can be easily relaxed. If we have explicit

values for these parameters, then we can calculate interesting performance

measures such as bus utilization and mean response time as functions of the

number of processors. Another interesting measure is the increase in the mean

response time assuming a fixed number of processors and memory modules,

while changing the mean bus service time and the mean time between two

cache misses. In Fig. 13.3 the mean response time is shown as a function

of the mean bus service time and the mean time between two cache

[BolcSl].

R

Mean

.espont

Time

misses

4ce Time

Mean Time Between Cache Misses 5o

fig. 13.3 Mean response time as a function of the bus service time, and the mean

time between cache misses (m = 5, n = 4).

We can see that there is a wide area where the increase in the mean response

time is tolerable (1501) o compared to the case with no waiting time at the bus

or a memory queue (this is the minimum value of the mean response time).

On the other hand, there is also a wide area with an intolerable increase in

the mean response time. Thus the analysis of such a queueing network model

can help the system designer to choose parameter values in a tolerable area.

Problem 13.1 Verify the results shown in Fig. 13.3 by hand computation

and using any software package available (e.g., SHARPE or PEPSY).

606 APPLICATIONS

Problem 13.2 Improve the model described in Section 13.1.1.1 by consid￾ering different mean service times for bus requests from processor to memory

and from memory to cache (Hint: Use a multiclass queueing network model).

13.1.1.2 Loosely Coupled Systems In a loosely coupled multiprocessor sys￾tem, the processors have only local memory and local I/O devices, and com￾municate via an interconnection network by exchanging messages. A simple

queueing network model of such a system is shown in Fig. 13.4. The mean

Network

Processors

Fig. 13.4 A simple queueing network model of a loosely coupled system.

service time at the processors is the mean time between the messages, and

the mean service time at the network node N is the mean message delay at

the network. The routing probability pi is the probability that a message is

directed to processor i.

Arriving / Departing Jobs Replies to I/O Requests

Processors

Replies to Memory Requests I/O Processors

Fig. 13.5 A complex queueing network model of a loosely coupled system.

A more complex and detailed model of a loosely coupled multiprocessor sys￾tem is shown in Fig. 13.5 [MAD94]. Here we assume that we have n separate

I/O processors and m “computing” processors. The computing processors

send I/O requests via the network N to the I/O processors and get the replies

to these requests also via the network N. We assume that a job that begins at

a computing processor is also completed at this processor and that the proces￾sors are not multiprogrammed and are heavily loaded (for each job that leaves

the system after being processed by a processor, a new job arrives immediate-

CASE STUDIES OF QUEUEING NETWORKS 607

ly at the processor). This system can be modeled by a closed product-form

queueing network with m job classes (one for each computing processor) with

the population of each class equal to 1 [MAD94].

As an example we consider a loosely coupled multiprocessor system with

eight computing processors and n = 2,3,4 I/O processors. The mean com￾puting processor service time is 30 msec, the mean I/O time is 50 msec, and

the mean message delay at the network is 1 msec. The probability that a

job leaves the system after it has been processed at a computing processor

is p&ne = 0.05. we assume that pi = l/n for all i. Some interesting results

from this model are listed in Table 13.1.

Table 13.1 Performance measures for the loosely coupled multiprocessor system for

different, numbers of I/O processors

Number of I/O Processors 2 3 4

mean response time

throughput

Pcomputingprocessor

Pnetwork

PI/Oprocessor

4.15 set

1.93 set- l

0.145

0.070

0.867

3.18 set

2.51 set-l

0.189

0.090

0.754

2.719 set

2.944 set-l

0.220

0.106

0.662

Problem 13.3 Verify the results shown in Table 13.1 by hand computa￾tion and using any software package available (e.g., PEPSY or SHARPE).

Problem 13.4 Extend the complex model described in Section 13.1.1.2 so

as to allow distinct mean network service times for request from a computing

processor to I/O processor and vice versa.

13.1.2 Client Server Systems

A client server system consists of client and server processes and some method

of interprocess communication. Usually the client and the server processes

are executing on different machines and are connected by a LAN. The client

interacts with the user, generates requests for a server, transmits the request

to the server, receives the results from the server, and presents the results to

the user. The server responds to requests from the clients and controls access

to resources such as file systems, databases, wide area networks, or printers.

As an example we consider a client server system with a fixed number m of

client workstations that are connected by an Ethernet network to a database

server. The server consists of a single disk (node number 4) and a single

CPU (node number 3). This leads to a closed product-form queueing network

model shown in Fig. 13.6.

The client workstations are modeled as an IS node (node number 1)

[MAD94], and the number of jobs in the closed system is equal to the number

of workstations m. The Ethernet network (carrier sense multiple access with

608 APPLICATIONS

Workstations

fig. 13.6 Closed qucueing network model of a client server system.

collision detection, or CSMA/CD, network) can be modeled as a server (node

number 2) with the load-dependent service rate [LZGS84, MAD94, HLM96]:

i

-

(

PIlet (W =

y$ * 3 + s * c(l))-l, k = 1,

- (13.1)

( ~.~+S*C(t+l))-l, k>l,

where C(k) = (1- A(k))/A(k) is tk re average number of collisions per request

and A(k) = (1 - l/k)'-' is the probability of a successful transmission and Ic

the number of workstations that desire the use of the network.

Other parameters are described in Table 13.2 and shown in Fig. 13.6. We

Table 13.2 Parameters for the client server example

Parameter Description

NP

B

S

GJ

Average number of packets generated per request

Network bandwidth in bits per second

Slot duration (i.e., time for collision detection)

Average packet length in bits

compute the throughput X and other interesting performance measures using

the load-dependent MVA ( see Section 8.2). As an example we use the param￾eters from Table 13.3 and determine the throughput as a function of the

number of client workstations m (see Fig. 13.7)

Problem 13.5 Verify the results shown in Fig. 13.7 by hand computation

and using an available modeling package such as SHARPE or PEPSY.

13.1.3 Communication Systems

13.1.3.1 Description of the System As an example of a more complex queue￾ing network and the performance evaluation of communication systems, we

consider the LAN of a medium size enterprise [Ehre96].

CASE STUDIES OF QUEUEING NETWORKS 609

” 20 4b 6b 8b 160

m

Fig. 13.7 Throughput as a function of the number of workstations.

Table 13.3 Numerical parameter values for the client￾server example

Np = 7 pl = pc~ = O.l/ set

B = 10 Mb/ set CL2 = pNet(k)

S = 51.2 psec p3 = pcpu = 16.7/set

z, = 1518 bits p~q = PDisk = 18.5/set

P12 = 1 pa1 = 0.5 p32 = 0.5 P43 = 1

p23 = 0.5 p34 = 0.5

m Bridges in the Computer Center

0 Bridges in the Other Buildings

WAN Router

LAN Analyzer

@ Server

•i Computer

Fig. 13.8 The FDDI backbone with 13 stations.