2.2 Multi-channel QS with wait
System with limited queue length. Let's consider a channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel); number of places in the queue.
System states are numbered according to the number of requests associated with the system:
no queue:
All channels are free;
One channel is occupied, the rest are free;
-channels are occupied, the rest are not;
All channels are occupied, there are no free channels;
there is a queue:
All n-channels are occupied; one application is in the queue;
All n-channels, r-requests in the queue are occupied;
All n-channels, r-requests in the queue are occupied.
GSP is shown in Fig. 17. Each arrow is marked with the corresponding intensities of event flows. Along the arrows from left to right, the system is always transferred by the same flow of requests with an intensity of
Rice. 17. Multi-channel QS with waiting
The graph is typical for the processes of reproduction and death, for which the solution was previously obtained. Let us write expressions for the limiting probabilities of states using the notation: (here we use the expression for the sum geometric progression with denominator).
Thus, all state probabilities have been found.
Let us determine the performance characteristics of the system.
Probability of failure. An incoming request is rejected if all n-channels and all m-places in the queue are occupied:
(18)
The relative throughput complements the probability of failure to one:
Absolute throughput of QS:
(19)
Average number of busy channels. For QS with refusals, it coincided with the average number of applications in the system. For a QS with a queue, the average number of busy channels does not coincide with the average number of applications in the system: the latter value differs from the first by the average number of applications in the queue.
Let us denote the average number of occupied channels by . Each busy channel serves on average A-claims per unit of time, and the QS as a whole serves on average A-claims per unit of time. Dividing one by the other, we get:
The average number of applications in the queue can be calculated directly as the mathematical expectation of a discrete random variable:
(20)
Here again (the expression in parentheses) the derivative of the sum of the geometric progression occurs (see above (11), (12) - (14)), using the relation for it, we obtain:
Average number of applications in the system:
Average waiting time for an application in the queue. Let's consider a number of situations that differ in the state in which a newly arrived request will find the system and how long it will have to wait for service.
If a request does not find all channels busy, it will not have to wait at all (the corresponding members in mathematical expectation are equal to zero). If a request arrives at a time when all n-channels are busy and there is no queue, it will have to wait on average for a time equal to (because the “release flow” of -channels has intensity ). If a request finds all channels busy and one request in front of it in the queue, it will have to wait on average for a period of time (for each request in front), etc. If a request finds itself in a queue of -requests, it will have to wait on average for time If a newly arrived request finds m-requests already in the queue, then it will not wait at all (but will not be served). We find the average waiting time by multiplying each of these values by the corresponding probabilities:
(21)
Just as in the case of a single-channel QS with waiting, we note that this expression differs from the expression for the average queue length (20) only by the factor , i.e.
.
The average residence time of a request in the system, as well as for a single-channel QS, differs from the average waiting time by the average service time multiplied by the relative throughput:
.
Systems with unlimited queue length. We considered a channel QS with waiting, when no more than m-requests can be in the queue at the same time.
Just as before, when analyzing systems without restrictions, it is necessary to consider the obtained relations for .
We obtain the probabilities of states from the formulas by passing to the limit (at ). Note that the sum of the corresponding geometric progression converges at and diverges at >1. Assuming that<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Probability of failure, relative and absolute throughput. Since each request will sooner or later be serviced, the characteristics of the QS throughput will be:
The average number of applications in the queue is obtained from (20):
,
and the average waiting time is from (21):
.
The average number of occupied channels, as before, is determined through the absolute throughput:
.
The average number of applications associated with the QS is defined as the average number of applications in the queue plus the average number of applications under service (average number of busy channels):
Example 2. A gas station with two pumps (n = 2) serves a flow of cars with an intensity of =0.8 (cars per minute). Average service time per machine:
There is no other gas station in the area, so the line of cars in front of the gas station can grow almost unlimitedly. Find the characteristics of the QS.
Because the<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
etc.
We will find the average number of busy channels by dividing the absolute capacity of the QS A = = 0.8 by the service intensity = 0.5:
The probability of no queue at a gas station will be:
Average number of cars in queue:
Average number of cars at gas stations:
Average waiting time in queue:
Average time a car spends at a gas station:
QS with limited waiting time. Previously, we considered systems with waiting limited only by the queue length (the number of m-requests simultaneously in the queue). In such a QS, an application that has grown in a queue does not leave it until it waits for service. In practice, there are other types of QS in which an application, after waiting for some time, can leave the queue (so-called “impatient” applications).
Let's consider a QS of this type, assuming that the waiting time constraint is a random variable.
Let us assume that there is an n-channel QS with waiting, in which the number of places in the queue is unlimited, but the time a request stays in the queue is some random variable with a mean value, thus, each request in the queue is subject to a kind of Poisson " flow of care” with intensity:
If this flow is Poisson, then the process occurring in the QS will be Markovian. Let us find the state probabilities for it. The numbering of system states is associated with the number of applications in the system - both being served and standing in queue:
no queue:
All channels are free;
One channel is busy;
Two channels are busy;
All n-channels are occupied;
there is a queue:
All n-channels are occupied, one request is in the queue;
All n-channels are occupied, r-requests are in queue, etc.
The graph of states and transitions of the system is shown in Fig. 23.
Rice. 23. QS with limited waiting time
Let's mark this graph as before; all arrows leading from left to right will indicate the intensity of the flow of applications. For states without a queue, the arrows leading from them from right to left will, as before, indicate the total intensity of the flow servicing all occupied channels. As for states with a queue, the arrows leading from them from right to left will have the total intensity of the service flow of all n-channels plus the corresponding intensity of the flow of departures from the queue. If there are r-applications in the queue, then the total intensity of the flow of departures will be equal to .
As can be seen from the graph, there is a pattern of reproduction and death; using general expressions for the limiting probabilities of states in this scheme (using abbreviated notations, we write:
(24)
Let us note some features of a QS with limited waiting compared to the previously considered QS with “patient” requests.
If the length of the queue is not limited and the requests are “patient” (do not leave the queue), then the stationary limit regime exists only in the case (at , the corresponding infinite geometric progression diverges, which physically corresponds to unlimited growth of the queue at ).
On the contrary, in a QS with “impatient” requests leaving the queue sooner or later, the established service mode at is always achieved, regardless of the reduced intensity of the flow of requests. This follows from the fact that the series for in the denominator of formula (24) converges for any positive values of and .
For a QS with “impatient” requests, the concept of “probability of failure” does not make sense - each request gets in line, but may not wait for service, leaving ahead of time.
Relative throughput, the average number of requests in the queue. The relative capacity q of such a QS can be calculated as follows. Obviously, all applications will be serviced, except those that leave the queue ahead of schedule. Let's calculate the average number of applications that leave the queue early. To do this, we calculate the average number of applications in the queue:
Each of these applications is subject to a “flow of departures” with an intensity of . This means that out of the average number of -applications in the queue, on average, -applications will leave without waiting for service, -applications per unit of time and in total per unit of time, on average -applications will be served. The relative capacity of the QS will be:
We still obtain the average number of occupied channels by dividing the absolute bandwidth A by:
(26)
Average number of applications in queue. Relation (26) allows you to calculate the average number of applications in the queue without summing the infinite series (25). From (26) we obtain:
and the average number of occupied channels included in this formula can be found as the mathematical expectation of a random variable Z, taking values 0, 1, 2,..., n with probabilities ,:
In conclusion, we note that if in formulas (24) we go to the limit at (or, what is the same, at ), then at 
A queue of length k remains in it with probability Pk and does not join the queue with probability gk=1 - Pk." This is exactly how people usually behave in queues. In queuing systems, which are mathematical models of production processes, the possible queue length is limited by a constant size (bunker capacity, for example). Obviously, this is a special case of the general setting. Some...
In this section we will look at some of the simplest QSs and derive expressions for their characteristics (performance indicators). At the same time, we will demonstrate the main methodological techniques characteristic of the elementary, “Markov” theory of queuing. We will not chase the number of QS samples for which final expressions of characteristics will be derived; This book is not a reference book on the theory of queuing (this role is much better fulfilled by special manuals). Our goal is to introduce the reader to some “little tricks” that make the path easier through the theory of queuing, which in a number of existing (even pretending to be popular) books may seem like an incoherent set of examples.
In this section, we will consider all flows of events that transfer the QS from state to state to be the simplest (without specifically stipulating this each time). Among them will be the so-called “service flow”. It refers to the flow of requests served by one continuously busy channel.
In this flow, the interval between events, as always in the simplest flow, has an exponential distribution (in many manuals they say instead: “service time is exponential”; we ourselves will use this term in the future). In this section, the exponential distribution of service time will go without saying, as always for the “simplest” system.
We will introduce the performance characteristics of the QS under consideration as we proceed.
1. n-channel QS with failures (Erlang problem).
Here we will consider one of the first, “classical” problems of queuing theory; this problem arose from the practical needs of telephony and was solved at the beginning of this century by the Danish mathematician Erlang. The problem is formulated as follows: there are channels (communication lines) that receive a flow of requests with intensity K. The flow of services has an intensity (the inverse value of the average service time). Find the final probabilities of the QS states, as well as the characteristics of its effectiveness:
A - absolute throughput, i.e. the average number of applications served per unit of time;
Relative throughput, i.e. the average share of incoming applications served by the system;
Rotk is the probability of refusal, i.e., that the application will leave the QS unserved;
k is the average number of occupied channels.
Solution. We will number the states of the system S (SMO) according to the number of requests located in the system (in this case it coincides with the number of occupied channels):
There is not a single application in the CMO,
There is one request in the QS (one channel is busy, the rest are free),
In the QS system, the requests for channels are occupied, the rest are free),
There are requests in the QS (all channels are busy).
The state graph of the QS corresponds to the pattern of death and reproduction (Fig. 20.1). Let's mark this graph - put the intensity of the event flows next to the arrows. The flow of applications with intensity X is transferred from the system (as soon as an application arrives, the system jumps from ).
The same flow of requests transfers the system from any left state to the neighboring right one (see the top arrows in Fig. 20.1).
Let's put the intensities at the bottom arrows. Let the system be in the state (one channel is working). It performs maintenance per unit of time. We indicate the intensity of the arrow. Now let’s imagine that the system is in the state (two channels are working). In order for it to go to, either the first channel or the second must finish servicing; the total intensity of their service flows is equal to the corresponding arrow. The total flow of services provided by three channels has an intensity equal to the channels - We put these intensities at the bottom arrows in Fig. 20.1.
And now, knowing all the intensities, we will use ready-made formulas (19.7), (19.8) for the final probabilities in the scheme of death and reproduction. Using formula (19.8) we get:
The terms of the expansion will be the coefficients in the expressions for
Note that in formulas (20.1), (20.2) the intensities of the Eggs are included not individually, but only in the form of a ratio. Let us denote
and we will call the value “reduced intensity of the flow of applications.” Its meaning is the average number of requests received during the average time of servicing one request. Using this notation, we rewrite formulas (20.1), (20.2) in the form:
Formulas (20.4), (20.5) for the final probabilities of states are called Erlang formulas - in honor of the founder of queuing theory. Most of the other formulas of this theory (today there are more of them than mushrooms in the forest) do not bear any special names.
Thus, the final probabilities have been found. Using them, we will calculate the performance characteristics of the QS. First, let's find the probability that an incoming application will be rejected (will not be serviced). To do this, all channels must be busy, which means
From here we find the relative throughput - the probability that the request will be served:
We obtain the absolute throughput by multiplying the intensity of the flow of applications X by
All that remains is to find the average number of occupied channels k. This value could be found “directly”, as the mathematical expectation of a discrete random variable with possible values and probabilities of these values
Substituting expressions (20.5) for here and performing the corresponding transformations, we would eventually obtain the correct formula for k. But we will derive it much more simply (here it is, one of the “little tricks”!) In fact, we know the absolute throughput A. This is nothing more than the intensity of the flow of applications served by the system. Each busy channel serves an average of requests per unit time. This means that the average number of occupied channels is
And what proportion of channels will be idle?
There is already some hint of optimization visible here. In fact, the maintenance of each channel per unit of time costs a certain amount. At the same time, each serviced application generates some income. Multiplying this income by the average number of applications A serviced per unit of time, we obtain the average income from the QS per unit of time. Naturally, as the number of channels increases, this income increases, but the expenses associated with maintaining the channels also increase. What will outweigh - an increase in income or expenses? It depends on the terms of the operation, the “fee for servicing the application” and the cost of maintaining the channel. Knowing these values, you can find the optimal number of channels, the most cost-effective. We will not solve such a problem, leaving it to the same “non-lazy, curious reader” to come up with an example and solve it. In general, inventing problems develops more than solving those already posed by someone.
ML systems are part of a broader class of dynamical systems that are sometimes called flow systems. Thread system is a system in which certain objects are moved through one or more channels of limited capacity for the purpose of moving from one point to another. When analyzing flow systems, they are divided into two main classes:
regular systems, i.e. systems in which flows behave in a predictable manner (the magnitude of the flow and the time of its appearance in the channel are known). In the case where there is only one channel, the calculation of the system is trivial. It is obvious that between the flow intensity λ and speed of service With there is a ratio λ < c;
irregular systems, i.e. systems in which threads behave in unpredictable ways.
More interesting is the case of a regular flow that is distributed over a network of channels. It is obvious that the condition λ < c saved for each channel. This creates a complex combinatorial problem.
There are seven roads:
A→B→D→E→F
A→C→B→ E→F
A→C→B→D→E→F
A→C→B→ D→F
It is necessary to transport cargo from A V F. The capacity of each channel is known. What is the network capacity and what path should the flow take? This problem can be solved using the maximum flow theorem, which we considered earlier (Fig. 6).
The second class includes random probable flows, in which the time of receipt of a requirement is not determined and the number of requirements is unpredictable. The theory of queuing deals with solving such problems.
In general, the queuing system can be represented in Figure 7.
Rice. 7.
The subject of queuing theory is to establish the relationship between the nature of the flow of requests, the number of channels, productivity, correct operation and efficiency.
As performance characteristics The following quantities and functions can be used:
the average number of applications that the QS can service per unit of time;
the average number of applications being rejected and leaving the CMO;
the likelihood that the received application will be immediately serviced;
average waiting time in queue;
average number of applications in the queue;
average income of SMO per unit of time and others economic indicators of SMO.
The analysis of QS is simplified if a Markov process occurs in the system, then the system can be described by ordinary differential equations, and the limiting probabilities - by linear algebraic equations.
A Markov process requires that all flows be Poisson (without aftereffects), but the apparatus of Markov processes is also used when the process is different from Markov. In this case, the characteristics of the QS can be estimated approximately: the more complex the QS, the more accurate the approximation.
Classification of queuing systems
QS can be of two types:
QS with failures;
QS with waiting (i.e. with a queue).
Service in systems with a queue can be of a different nature:
service can be streamlined;
random service;
service with priority, while priority can be with or without interruption.
Queuing systems are divided into:
systems with unlimited waiting, and the task received by the QS becomes queued and waits for service. Sooner or later she will be served;
systems with limited expectation, while restrictions are imposed on the application in the queue, for example, a limited time spent in the queue, the length of the queue, the total time spent in the QS. Depending on the type of QS, different indicators can be used to evaluate effectiveness.
For QS with failures, the following performance indicators are used:
absolute throughput A– the average number of applications that can be serviced per unit of time;
relative throughput Q– relative average number of applications. In this case, the relative throughput can be found using the formula
Where λ is the intensity of requests received by the QS.
For SMO with expectation absolute throughput A And relative throughput Q lose their meaning, but other characteristics become important:
unit of waiting time in queue;
average number of applications in queue;
average time spent in the system.
For a QS with a limited queue, both groups of characteristics are interesting.
Consider n - channel queuing system with waiting.
The service flow intensity is μ. The duration of service is a random variable subject to the exponential distribution law. The service flow is the simplest Poisson flow of events.
The size of the queue allows people to be in it m applications.
To find the marginal probabilities, you can use the following expressions.
(0‑1)
Where.
Probability of refusal to service an application(failure will occur if all channels are busy and there are m requests):
(0‑2)
Relative Bandwidth.
(0‑3)
Absolute throughput.
(0‑4)
Average number of busy channels.
For a QS with a queue, the average number of busy channels does not coincide (unlike the QS with failures) with the average number of requests in the system. The difference is equal to the number of applications waiting in the queue.
Let us denote the average number of occupied channels. Each busy channel serves on average μ claims per unit of time, and the QS as a whole serves A claims per unit of time. Dividing A by μ we get
(0‑5)
The average number of applications in the queue.
To find the average number of applications waiting in the queue if χ≠1, you can use the expression:
(0‑6)
(0‑7)
where = .
The average number of applications in the system.
(0‑8)
Average waiting time for an application in queue.
The average waiting time for an application in the queue can be found from the expression (χ≠1).
(0‑9)
Average time an application stays in the system.
Just as in the case of a single-channel QS, we have:
(0‑10)
The content of the work.
Preparation of experimental instruments .
Performed in accordance with general rules.
Calculation using an analytical model .
1. Prepare the following table in Microsoft Excel.
|
Options |
Analytical |
Imitation |
|||||||||||||||
|
n |
m |
Ta |
Ts |
ρ |
χ |
P0 |
P1 |
p2 |
Rotk |
W |
nozh |
q |
A |
Rotk |
W |
q |
A |
2. In the columns for the QS parameters of the table, write down your initial data, which is determined according to the rule:
n =1,2,3
m=1,3,5
For each combination ( n,m) it is necessary to find theoretical and experimental values of QS indicators for the following pairs of values:
= <порядковый номер в списке группы>
3. Enter the appropriate formulas in the columns with the analytical model indicators.
Experiment on a simulation model.
1. Set the launch mode with exponentially distributed service time by setting the value of the corresponding parameter to 1.
2. For each combination of n, m, and run the model.
Enter the results of the runs into the table.
3. Enter formulas for calculating the average value of the indicator Ptk, q and A in the corresponding columns of the table.
Analysis of results .
1. Analyze the results obtained by theoretical and experimental methods, comparing the results with each other.
2. For one of the combinations (n,m), plot on one diagram the dependence of Ptk on the theoretically and experimentally obtained data.
Optimization of QS parameters .
Solve the problem of optimizing the size of the number of places in a queue m for two devices with average service time = from the point of view of obtaining maximum profit. As the conditions of the problem, take:
- income from servicing one application equal to 80 USD/hour,
- the cost of maintaining one device is 1$/hour,
- the cost of maintaining one place in the queue is 0.2 USD/hour.
1. For calculations, it is advisable to create a table:
The first column is filled with the number of devices n =1.
The second column is filled with the values of the numbers in the natural series (1,2,3...).
All cells in the third and fourth columns are filled with values.
Formulas for the columns of the table in section 0 are transferred to the cells of columns from five to fourteen.
In the columns with the initial data of the Income, Expense, Profit sections, enter the values (see above).
In the columns with calculated values of the Income, Expense, Profit sections, write down the calculation formulas:
- number of applications per unit of time
N r =A
- total income per unit of time
I S = I r *N r
- total consumption per unit of time
E S =E s *n + E q *m
- profit per unit of time
P = I S - E S
Where
I r - income from one application,
E s - consumption per device,
Eq - cost per place in line
2. Fill in the table rows for n=2 and n=3.
Find m opt for n =1,2,3.
3. Draw graphs of the dependence C(m) for n=1,2,3 on one diagram.
Work report:
The work report should include:
- initial data,
- results of calculations and experiments with the software model,
Graphs for P open,
- table with data to find the best m and the value of m opt,
- graphs of profit per unit of time depending on m for n=1,2,3.
Control questions :
1) Give a brief description of the multi-channel QS model with a limited queue.
2) What indicators characterize the functioning of a multi-channel QS with a limited queue?
3) How are the marginal probabilities of a multi-channel QS with a limited queue calculated?
4) How to find the probability of failure to service an application?
5) How to find relative bandwidth?
6) What is the absolute throughput?
7) How is the average number of applications in the system calculated?
8) Give examples of a multi-channel QS with a limited queue.
Tasks.
1) The gas station has 3 pumps and a platform for 3 cars to wait for refueling. On average, one car arrives at the station every 4 minutes. The average service time for one machine is 2.8 minutes. Determine the operating characteristics of a gas station.
2) The vehicle technical inspection station, which has 3 inspection posts, receives on average 1 vehicle every 0.4 hours. Parking in the yard accommodates 3 cars. The average operating time of one post is 0.5 hours. Determine the characteristics of the service station.
3) Goods are delivered to the store by vehicles. During the day, an average of 6 cars arrive. Utility rooms for preparing goods for sale allow you to process and store goods brought by two vehicles. The store employs three product packers in shifts, each of whom on average can process the goods of one machine within 5 hours. The working day of packers is 12 hours. Determine the operating characteristics of the store, as well as what the capacity of the utility rooms should be so that the probability of complete processing of goods is greater than 0.96.
4) The store has three cash registers. The average service time for one customer is 3 minutes. The intensity of customer flow is 7 people per minute. The number of customers standing in line at the checkout cannot exceed 5 people. A buyer who comes to a store in which there are 5 people in each line at the cash register does not wait, but leaves the store. Determine the characteristics of the store.
5) The wholesale warehouse releases goods to customers. Loading the vehicle is carried out by three teams of loaders, each of which consists of 4 people. The warehouse can simultaneously accommodate 5 vehicles and if a new vehicle arrives at this time, it is not serviced. The intensity of the incoming flow is 5 cars per hour. The loading rate is 2 vehicles per hour. Give an assessment of the warehouse operation and an option for its reorganization.
6) The customs office has three terminals. The intensity of the flow of vehicles transporting goods and subject to customs control is 30 units. per day. The average customs processing time at the terminal for one vehicle is 3 hours. If there are 5 cars in line to go through customs control, then the arriving cars go to another customs office. Find customs performance indicators.
7) On average, vehicles with construction materials arrive at the construction site within 40 minutes. The average time for unloading one vehicle is 1.8 hours. Two teams of loaders take part in the unloading. No more than 5 vehicles may be in line for unloading on the construction site. Determine construction site performance indicators.
8) On average, 12 cars arrive per hour at a car wash with three work stations. If there are already 6 cars in the queue, newly arriving cars do not join the queue, but leave the wash. The average car wash time is 20 minutes, the average cost of car wash services is 150 rubles. Determine the performance indicators of the car wash and the average loss of revenue during the working day (from 9 a.m. to 7 p.m.).
9) The intensity of the flow of vehicles transporting goods and subject to customs control is 50 units. per day. The average customs processing time at the terminal for one vehicle is 2.8 hours. The maximum queue for customs control should be no more than 8 cars. Determine how many terminals need to be opened at customs so that the likelihood of vehicle downtime is minimal.
System with limited queue length. Let's consider a channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel); number of places in the queue.
System states are numbered according to the number of requests associated with the system:
no queue:
All channels are free;
One channel is occupied, the rest are free;
The channels are busy, the rest are not;
All channels are occupied, there are no free channels;
there is a queue:
All n channels are busy; one application is in the queue;
All n channels are busy, r applications are in the queue;
All n channels are busy, m applications in queue.
GSP is shown in Fig. 5.9. Each arrow is marked with the corresponding intensities of event flows. Along the arrows from left to right, the system is always transferred by the same flow of requests with an intensity of
Multichannel exponential SMO differs from single-channel as follows. There are more than one channels in it. An incoming request becomes queued if all channels are busy. Otherwise, the request occupies a free channel. 
(5.56)
Let's write expressions for the limiting probabilities of states using the notation: (see 5.45)
Probability of failure. An application received is rejected if everyone is occupied n channels and everything m places in line:
(5.57)
The relative throughput complements the probability of failure to one:
Absolute throughput of QS:
(5.58)
Average number of busy channels. For SMO with refusals, it coincided with the average number of applications in the system. For SMO with a queue, the average number of busy channels does not coincide with the average number of applications in the system: the latter value differs from the first by the average number of applications in the queue.
Let us denote the average number of occupied channels by . Each busy channel serves on average requests per unit of time, and SMO overall service is average A applications per unit of time. Dividing one by the other, we get:
The average number of requests in a queue can be calculated directly as the mathematical expectation of a discrete random variable:
(5.59)
Here again (the expression in brackets) the derivative of the sum of the geometric progression occurs (see above (5.50), (5.51)-(5.53)), using the relation for it, we obtain:
Average number of applications in the system:
Average waiting time for an application in queue. Let's consider a number of situations that differ in the state in which a newly arrived request will find the system and how long it will have to wait for service.
If a request does not find all channels busy, it will not have to wait at all (the corresponding terms in the mathematical expectation are equal to zero). If the application arrives at a time when everyone is busy P channels, but there is no queue, she will have to wait on average for a time equal to (because the “flow of releases” of channels has an intensity of ). If an application finds all channels busy and one application in front of it in the queue, it will have to wait on average for an amount of time (for each application in front), etc. If an application finds itself in a queue of applications, it will have to wait on average for a period of time . If a newly arrived application finds itself in the queue m applications, then it will not wait at all (but will not be served).
Average waiting time we find by multiplying each of these values by the corresponding probabilities:
(5.60)
Just as in the case of a single-channel QS with waiting, we note that this expression differs from the expression for the average queue length (5.59) only by the factor , i.e.
Average time an application stays in the system, the same as for single-channel SMO, differs from the average waiting time by the average service time multiplied by the relative throughput:
Systems with unlimited queue length.
We considered a channel QS with waiting, when no more than m applications.
Just as before, when analyzing systems without restrictions, it is necessary to consider the obtained relations for .
We obtain the probabilities of states from formulas (5.56) by passing to the limit (at ). Note that the sum of the corresponding geometric progression converges at and diverges at > 1. Assuming that< 1 и устремив в формулах (5.56) величину m to infinity, we obtain expressions for the limiting probabilities of states:
(5.61)
Probability of failure, relative and absolute throughput. Since each request will sooner or later be serviced, the characteristics of the QS throughput will be:
We obtain the average number of applications in the queue at from (5.59):
and the average waiting time is from (5.60):
The average number of occupied channels, as before, is determined through the absolute throughput:
The average number of applications associated with the QS is defined as the average number of applications in the queue plus the average number of applications under service (average number of busy channels):
The increasing complexity of the structures and modes of real systems complicates the use of classical methods of queuing theory due to the increasing dimension of the problems being solved, which is especially typical for systems with a network structure. One of the possible ways to overcome dimensionality is to use models in the form of queuing networks (Queuing).
SeMO is a collection of a finite number of serving nodes in which requests circulate, moving in accordance with the routing matrix from one node to another. The node is always open SMO. At the same time, separate SMO SMO− the structure of the system, and the requirements circulating through SeMO, − components of material flows (messages (packets) in a communication network, tasks in multiprocessor systems, containers of cargo flows, etc.).
In its turn, SeMO used to determine the most important system characteristics of information systems: productivity; package delivery time; probability of message loss and blocking in nodes; areas of permissible load values at which the required quality of service is ensured, etc.
In theory SeMO The concept of network state is fundamental. The most important characteristic of networks MO− probabilities of their states. To determine the probabilities of states SeMO investigate the random process occurring in the network. As models flowing in SeMO Markov and semi-Markov processes are also most often used.
3.3. Queuing system as a model
1.5. Queuing networks
A Markov process with continuous time describes the functioning of exponential SeMO.
The network is called exponential if incoming flows of requirements in each SMO Poisson, and the times of each stage of service implemented at any SMO networks have exponential distribution. This allows us to assume that the service stages are independent of each other and do not depend either on the parameters of the incoming flow, or on the state of the network, or on the routes of the requests.
Theory of exponentials SeMO most developed, and it is widely used both for the study of PD networks and for the study of multiprocessor computing systems (CS). Practical formulas have been developed for calculating the probabilistic-temporal characteristics (PTC) of such networks and systems.
Attempts to deeply analyze non-Markov models of network systems encounter significant difficulties, which are caused, in particular, by the lack of independence of the duration of stay of requirements in various nodes of models of network systems with non-standard disciplines. So, for example, with a fairly realistic assumption that the length of the request remains constant during its transmission through network nodes, it is necessary to trace the path of each request, which makes it impossible to analytically calculate the characteristics for a network with the number of nodes M>2.
An analysis of works devoted to the study or calculation of non-Markov models shows that solutions, as a rule, are obtained algorithmically through complex numerical calculations using Laplace-Stieltjes transformations, are implemented in software, are highly labor-intensive, or have significant errors in assessing the performance indicators of information systems (IS) in the area of medium and heavy load. Therefore, for modeling SeMO, leaving the class of multiplicative ones, they use approximate methods.
Comparative analysis of approximate modeling methods SeMO and the examples given in show that it is necessary to use approximate methods for calculating SeMO with great caution, that when calculating specific SeMO, in the process of solving various applied problems, it seems necessary to conduct research in order to assess the accuracy and sensitivity of the method used, as well as conduct a simulation experiment the original SeMO for a sufficiently large set of values of varied parameters.
Analytical methods for calculating IS characteristics are based, as a rule, on the analysis of exponential CeMO. Using this mathematical apparatus, it is possible to obtain analytical models for solving a wide range of problems in the study of systems. SeMO is, first of all, a set of interconnected queuing systems. Therefore, it is necessary to recall the main features of these systems.
Queuing network represents a collection of finite numbers N serving nodes, in which requests circulate, moving in accordance with the routing matrix from one node to another. A node is always an open QS (and the QS can be of any class). At the same time, separate SMO display functionally independent parts of a real system, connections between SMO- the structure of the system, and the requirements circulating through SeMO,- components of material flows (messages (packets) in a communication network, tasks in multiprocessor systems, containers of cargo flows, etc.).
For visual representation SeMO a graph is used whose vertices (nodes) correspond to individual SMO, and arcs display connections between nodes.
The transition of applications between nodes occurs instantly in accordance with transition probabilities 
, p ij- the probability that the request after servicing in the node i will go to node j. Naturally, if the nodes are not directly connected to each other, then p ij= 0. If from i- th node transition to only one node j, That p ij= 1.
SeMO classified according to several criteria (Fig. 4).
The network is called linear, if the intensities of application flows at nodes are interconnected by a linear relationship
l j=a ij l i,
where a ij- proportionality coefficient, or relative to the source
l j=a j l 0 ,.
Coefficient a j called the transmission coefficient, it characterizes the share of applications received in j- th node from the source of applications, or - the average number of times an application passes through this node during the time the application is in the network.
If the intensities of application flows at network nodes are related by a nonlinear relationship (for example, 
), then the network is called nonlinear..
A network is always linear if applications are not lost or multiplied in it.
Open A network is an open network into which requests come from the external environment and leave the network into the external environment after being serviced. In other words, the feature of the open-loop SeMO(RSeMO) is the presence of one or more independent external sources that generate applications entering the network, regardless of how many applications are already in the network. At any time in RSeMO there can be an arbitrary number of applications (from 0 to ¥).
Rice. 4. Classification of queuing networks
IN closed SeMO (ZSeMO) a fixed number of applications circulate, and there is no external independent source. Based on physical considerations, in ZSeM About the outer arc is selected, on which it is marked pseudo-zero a point relative to which timing characteristics can be measured.
Combined a network is a network in which a certain number of applications constantly circulate and there are applications coming from external independent sources.
IN homogeneous applications of the same class circulate in the network. And, conversely, in heterogeneous networks may contain applications of several classes. Applications belong to different classes if they differ in at least one of the following attributes:
The law of distribution of service duration in nodes;
Priorities;
Routes (paths of movement of requests in the network).
IN exponential service duration networks in all nodes are distributed according to an exponential law, and the flows entering the open-loop network are simple (Poisson). In all other cases the network is non-exponential.
If priority service is provided in at least one node, then this is - priority net. Priority is a sign that determines the order of service. If servicing of requests in nodes is carried out in the order of receipt, then such a network no priority.
Thus, we will call exponential SeMO, meeting the requirements:
Input streams SeMO Poisson;
In all N SMO the service time of requests has an exponential probability distribution function, and requests are serviced in the order of arrival;
Transfer of application from exit i th SMO at the entrance j- is an independent random event with a probability p ij ; p i0- the probability of the application leaving CeMO.
If applications come into the network and leave it, then the network is called open. If applications do not enter or leave the network, the network is called closed. The number of applications in a closed network is constant.
