There are a number of systems that consist of several queues. So a job may receive service at one or more queues before exiting from the system. Such systems are modeled by queueing networks. Usually, the model in which jobs are departing from one queue arrive at another queue (or possibly the same queue) is called queueing network. This section presents several basic concepts about queueing networks.
Unlike single queues, there is no easy notation for specifying the type of queueing networks. The simplest way to classify a queueing network is either open or closed. An open queueing network has external arrivals and departures as shown in figure 1. The jobs enter the system at "In" and exit at "Out". The number of jobs varies with time. In analyzing an open system, we assume that the throughput is known (to be equal to the arrival rate), and the goal is to characterize the distribution of number of jobs in the system. A closed queueing network has no external arrivals or departures. As shown in figure 2, the jobs in the system keep circulating from one queue to the next. The total number of jobs in the system is constant. It is possible to view a closed system as a system where the Out is connected back to the In. The jobs exiting from the system immediately reenter the system. The flow of jobs in the Out-to-In link defines the throughput of the closed system. In analyzing a closed system, we assume that the number of jobs is given, and we attemt to determine the throughput (or the job completion rate).
It is also possible to have mixed queueing networks that are open for some workloads and closed for others. Figure 3 shows an example of a mixed system with two classes of jobs. The system is closed for interactive jobs and open for batch jobs. The term class refers to types of jobs. All jobs of a single class have the same service demands and transition probabilities. Within each class, the jobs are indistinguishable.
In this section we consider network of queues among which jobs move after arriving at a queue. Our assumptions are that, there are K queues each of which operating under FCFS policy. The arrival rate for queue m is denoted by Ar(m) which is the parameter of the Poisson process. Each queue m has has c(m) identical servers. And each server has an exponentially distributed service rate with mean u(m). After a job leaves a queue, denoted by m, it immediately arrives to queue n with the propability p(mn). The static routing propabilities are stored in KxK martrix.
The probability that a job leaves the system can be calculated as follows:
where K is the number of queues. Note that for each queue there K+1 different sources from where processes can arrive. Let e(m) denote the aggragate arrival rate for queue m. So the aggregate arrival rates for each queue can be calculated by solving the K linear equations of the form:
Jackson shows that each of these queues behaves like M/M/1 queue in isolation with arrival rates e(m) [Jackson 1963]. More specifically let P(km,m) be the the probabilty that km jobs at queue m, and P(k1,k2,...,kK) be the probability that k1 jobs at queue1 , k2 jobs at queue 2, and so forth. Jackson shows that:
This solution depends on the observation that each queue is processes with exponential distributuion of service rate. By the use of the routing matrix we can split the arrival stream into multiple poisson streams. Because Poisson properties have some nice properties. Click on FIGURE 4 to see those properties.
As an example consider the network in FIGURE 5.
As it can be observed, the jobs arrive into system at queue 1 at rate A1=4.4. The probabilities for the routings from queue 1 to queue 2, queue 3, and queue 4 are 0.5, 0,25,and 0.125, respectively. All jobs exiting from queue 2, 3, and 4 return to queue 1. The servers running at the queues have service rates as defined by u1, u2, u3, and u4. We can analyze the system as follows:
We first determine the aggragate arrival rates at each queue:
e1 = 4.5 + e2 + e3 + e4
e2 = 0.5e1
e3 = 0.25e1
e4 = 0.125e1
The solutions to these linear equations are e1=36, e2=18, e3=19, and e4=4.5. The
expressions for calculating the probability of km jobs at each queue m can be
calculated as follows:
P(k1,1)=(0.1)power(0.9,k1)
P(k2,2)=[(1/19)power(0.8,k2)]/power(2,k2-1)
P(k3,3)=(0.1)power(0.9,k3)
P(k4,4)=(0.1)power(0.9,k4)
Those expressions allow us to answer questions about system-idle probability, job distribution probabilities, and so forth.
We assume that a FCFS queueing discipline and exponential distributions are used for service rates. In a closed system the KxK matrix [Pmk] describes the static routing probabilities among queues, but each row sums to 1 since system departures are impossible. Service rates may be dependent on the queue size at each queue m: um(k) = ku when k<=c(m) and is c(m)um when the queue is larger.
Let n(m) be the number of jobs at queue m. A state of the system (a distribution of N jobs across K queues) is a vector of K integers n = (n1,n2,n3,...,nk) that satisfies the condition N = (n1 + n2 +... + nK).