Imperial College London

ISE-2 Surprise 97 Project

Approaches to Performance Evaluation

Written by Wan Ling Li

Performance - the capabilities of a machine

Analytical Queuing Models

In a queueing model, we define a station as a location where customers are serviced. A station has one or more servers which processes the customer. A customer can be both an output and an input to a process within a system. This is shown in the diagram below:

The arrival time of a customer to a station can be model mathematically with a probability function, such as an exponential or Poisson distribution. The time taken by a station to process the customer can also be modeled with a probability distribution function.

So in an analytical model, we define a number of customers and stations along with their various probability distribution functions. Other parameters of the model include the maximum capacity of a station, the number of customers in a system.

Kendall's notation was developed to easily show a setup of a typical model. In the following table the naming convention is given.

Kendall's notation

The parameters A and B can take the following values:

The parameters K and m have default values of infinity. That is to say that the server can handle an infinite number of users or customers. The parameter Z takes the default option of a FIFO(First In First Out) system. Z could also be a FIRO(First In Random Out) or a FILO(First In Last Out) system or LCFS(Last Come First Out).

These 3 parameters will take on their default values if they are not specified.

The examples below explain some common analytical models and queues:

The M/M/1 Queue

This is the simplest of all queueing models. It assumes random arrivals, exponential service times and the model only has one server. The customers are served in a FIFO(First In First Out) fashion.

It is important to realize in this model that the probability of an arrival does not depend on the last arrivals. In this model a steady state is reached when the number of arriving customers is less than the output of the station/server. If this were not the case then the server cannot keep up with the rate of input.

Traffic Intensity is calculated by [the rate of inputs/rate of outputs].

The M/M/c Queue

Networks

A network is a collection of interconnected queueing models. Typically a system can be represented by a network. In this article we will examine the Jackson and the BCMP Networks.

Jackson Networks

Jackson Networks are used frequently in very complex computer systems and data transmission systems.

The Jackson model goes as follows. In the random case we have N service stations, and the lengths of the queue at each station is unbounded. The output of each station to the input of the next is modelled by a Markov Chain.

In the stochastic case the service times for each queue is always independent of each other. Exponential Distribution, with parameters depending on the length of the queue, model the queues.

From the above description of a Jackson network, we can see that it is essentially a M/M/c queue.

Open systems - receive customers from the exterior according to the Poisson process, the customers have a certain probability of leaving the system.

Closed systems - have a constant number of customers and hence no customers many enter or exit this system.

BCMP - Baskett, Chandy, Muntz and Palacios - Networks

A BCMP network can support customers of different classes. The service stations in a BCMP network can obey any one of the 4 possibilities:

Type	Description
1	This station has a single server with a FIFO service routine. The service time is exponentially distributed with the same mean for all classes of customer.
2	In this type the servers process each customer via a means of time division('processor sharing'). Each customer receives a fixed amount of service time.
3	Here there is always at least one server free. This allows for new customers entering the station to be services immediately.
4	This type obeys a Last arrived, first served. So when a new customer arrives, it is serviced first. The current customer is kick off and placed back at the queue. It is re-serviced again, once the newly entered customer is fully serviced.

BCMP networks differ to Jackson networks, in the respect of the different classes of customers that BCMP supports. Also BCMP offers some alternative service methods, namely types 2-4.

In a BCMP network it is also possible to specify capacity limitations either on individual classes of customer or globally, i.e. an identical value for all customers.

The operating system could be effectively modeled via a BCMP network. The processes and threads within the operating system could be thought of as the customers and the microprocessor could be a server, or at a higher level of abstraction the operating system could be thought of as the server. Obviously the different threads will have different processor requirements and so different classes can defined.