Queuing networks and their applications. queuing network. Stochastic queuing networks

Net queuing(CEM) - a network that provides services to incoming requests. Maintenance of requirements in QS is performed by service devices. Classical QS contains from one to an infinite number of devices. Depending on whether it is possible for incoming requests to wait for service to begin, QSs are subdivided into: systems with losses, in which requests that have not found a single free server at the time of arrival are lost; systems with waiting, in which there is an infinite-capacity drive for buffering incoming requests, with In this case, the pending requests form a queue; systems with a drive of finite capacity (waiting and restrictions), in which the length of the queue cannot exceed the capacity of the drive; in this case, the claim arriving at the overcrowded QS (there are no free places to wait) is lost.

Each QS is designed to service (execute) a certain flow of applications (or requirements) that enter the system, for the most part, not regularly, but at random times. Application service, general case, also lasts not a constant, known in advance, but a random time. After servicing the request, the channel is released and is ready to receive the next request. The random nature of the flow and the time of their service leads to an uneven workload of the QS: at some time intervals, unserved requests may accumulate at the QS input (they either get into the queue or leave the QS unserved), while at other periods, with free channels at the QS input, there will be no requests , which leads to underloading of the QS, i.e. to idle channels.

Thus, in any QS, the following main elements can be distinguished:

) incoming flow of applications;

) turn;

) service channels;

) the outgoing stream of serviced requests.

Each QS, depending on its parameters: the nature of the flow of applications, the number of service channels and their performance, as well as the rules for organizing work, has a certain efficiency of functioning (capacity), which allows it to more or less successfully cope with the flow of applications.

The subject of study of the theory of queuing are QS.

The purpose of the queuing theory is to develop recommendations for the rational construction of a QS, rational organization their work and regulation of the flow of applications to ensure the high efficiency of the functioning of the QS.

To achieve this goal, the tasks of the theory of queuing are set, which consist in establishing the dependences of the efficiency of the functioning of the QS on its organization (parameters): the nature of the flow of applications, the number of channels and their performance, and the rules of the QS.

The random nature of the flow of requests and the duration of their service generates a random process in the QS.

Definition: A random process (or a random function) is a correspondence in which each value of the argument (in this case, a moment from the time interval of the experiment) is assigned a random variable (in this case, the QS state). queuing

In many areas of the economy, finance, production and life important role play queuing systems(SMO), i.e. such systems in which, on the one hand, there are massive requests (requirements) for the performance of any services, and on the other hand, these requests are satisfied.

As examples of QS in the financial and economic sphere, we can cite systems that are: banks of various types, insurance organizations, tax inspectorates, audit services, various communication systems (including telephone stations), loading and unloading complexes (commodity stations), petrol stations, various enterprises and service organizations (shops, catering establishments, information desks, hairdressers, ticket offices, currency exchange offices, repair shops, hospitals).

Systems such as computer networks, systems for collecting, storing and processing information, transport systems, automated production sites, production lines can also be considered as a kind of QS.

In trade, many operations are performed in the process of moving the commodity mass from the sphere of production to the sphere of consumption. Such operations are: loading and unloading of goods, transportation, packaging, packaging, storage, display, sale, etc. For trading activities characterized by a massive flow of goods, money, mass customer service, etc., as well as the performance of the corresponding operations, which are random in nature. All this creates unevenness in work. trade organizations and enterprises, generates underloads, downtime and overload. Queues take up a lot of time, for example, from buyers in stores, drivers of cars at commodity depots, waiting for unloading or loading.

In this regard, the tasks of analyzing the work of, for example, the trading department, commercial enterprise or sections, to evaluate their activities, identify shortcomings, reserves and ultimately take measures aimed at increasing its effectiveness. In addition, there are problems associated with the creation and implementation of more economical ways to perform operations within a section, department, trade enterprise, vegetable base, trade department, etc. Therefore, in the organization of trade, the methods of queuing theory make it possible to determine optimal amount outlets this profile, the number of sellers, the frequency of importation of goods and other parameters.

Warehouses or bases of supply and marketing organizations can serve as another typical example of queuing systems, and the task of queuing theory is to establish the optimal ratio between the number of service requirements arriving at the base and the number of serving devices, at which the total maintenance costs and losses from transport downtime would be minimal. The theory of queuing can also find application in calculating the area storage facilities, while the storage area is considered as a service device, and the arrival Vehicle for unloading - as a requirement.

Main characteristics of QS

QS includes the following elements: source of requirements, incoming flow of requirements, queue, service device (service channel), outgoing flow of requirements (serviced requests).

Each QS is designed to serve (execute) a certain flow of applications (requirements) that enter the system, mainly not regularly, but at random times. The service of applications also lasts not for a constant, predetermined time, but for a random time, which depends on many random reasons. After servicing the request, the channel is released and ready to receive the next request.

The random nature of the flow of requests and the time of their service leads to an uneven workload of the QS: at some time intervals, unserved requests may accumulate at the input of the QS, which leads to an overload of the QS, while at some other time intervals, with free channels at the input of the QS, there are no requests. will be, which leads to underloading of the QS, i.e. to the idleness of its channels. Applications that accumulate at the entrance of the QS either "become" in the queue, or, for some reason, the impossibility of further staying in the queue, leave the QS unserved.

The QS scheme is shown in Figure 5.1.

Figure 5.1 - Scheme of the queuing system

Each QS includes in its structure a certain number of service devices, which are called service channels. The role of channels can be played by various devices, persons performing certain operations (cashiers, operators, sellers), communication lines, vehicles, etc.

Each QS, depending on its parameters: the nature of the application flow, the number of service channels and their performance, as well as the rules for organizing work, has a certain operating efficiency (throughput), which allows it to more or less successfully cope with the flow of applications.

QS is the subject of study queuing theory.

Purpose of queuing theory- development of recommendations on the rational construction of the QS, the rational organization of their work and the regulation of the flow of applications to ensure high efficiency of the QS.

To achieve this goal, the tasks of the queuing theory are set, which consist in establishing the dependences of the efficiency of the functioning of the QS on its organization (parameters).

As characteristics of the effectiveness of the functioning of the QS There are three main groups of (usually average) indicators to choose from:

1. Indicators of the effectiveness of the use of QS:

1.1. Absolute throughput QS - the average number of applications that the QS can serve per unit of time.

1.2. The relative throughput of the QS is the ratio of the average number of applications served by the QS per unit of time to the average number of requests received over the same time.

1.3. The average duration of the period of employment of the SMO.

1.4. The QS utilization rate is the average share of time during which the QS is busy servicing requests.

2. Application service quality indicators:

2.1. Average waiting time for an application in the queue.

2.2. Average residence time of an application in the CMO.

2.3. The probability of refusal of the application in service without waiting.

2.4. The probability that the received application will be immediately accepted for service.

2.5. The law of distribution of waiting time for an application in the queue.

2.6. The law of distribution of the time spent by an application in the QS.

2.7. The average number of applications in the queue.

2.8. The average number of applications in the QS, etc.

3. Performance indicators of the pair "SMO - consumer", where "consumer" means the entire set of applications or some of their source (for example, the average income brought by the QS per unit of time, etc.).

The random nature of the flow of applications and the duration of their service generates in the QS random process. Because moments in time T i and time intervals for receipt of applications T, duration of service operations T obs, standing in line T och, queue length l och are random variables, then the characteristics of the state of queuing systems are probabilistic. Therefore, to solve the problems of the theory of queuing, it is necessary to study this random process, i.e. build and analyze it mathematical model.

The mathematical study of the QS functioning is greatly simplified if the random process occurring in it is Markovian. For a random process to be Markovian, it is necessary and sufficient that all flows of events, under the influence of which the system transitions from state to state, be (the simplest) Poisson.

The simplest flow has three main properties: ordinary, stationary and no aftereffect.

Ordinary flow means the practical impossibility of simultaneous receipt of 2 or more requirements. For example, the probability that several cash registers in a self-service store will fail at the same time is quite small.

Stationary is a flow for which the mathematical expectation of the number of requirements entering the system per unit of time (we denote λ ) does not change with time. Thus, the probability of a certain number of requirements entering the system during a given period of time ?T depends on its value and does not depend on the origin of its reference on the time axis.

No aftereffect means that the number of claims received by the system before the moment T, does not determine how many requests will enter the system during the time (T + ?T). For example, if in cash register at the moment there was a break in the cash tape and it was eliminated by the cashier, this does not affect the possibility of a new break at this checkout at the next moment, and even more so the likelihood of a break in other cash registers.

For the simplest flow, the frequency of receipt of requirements into the system obeys Poisson's law, i.e., the probability of arrival over time T smooth k requirements is given by the formula

where λ — application flow intensity, i.e., the average number of applications arriving at the QS per unit of time,

where τ - the average value of the time interval between two neighboring applications.

For such a flow of requests, the time between two neighboring requests is distributed exponentially with a probability density

Random waiting time in the service start queue can also be considered exponentially distributed:

where ν — queue traffic intensity, i.e., the average number of applications arriving for service per unit of time,

where T och is the average waiting time in the queue.

The output flow of requests is associated with the service flow in the channel, where the service duration T obs is a random variable and in many cases obeys the exponential distribution law with density

where μ — service flow rate, i.e., the average number of requests served per unit of time,

An important characteristic of QS, which combines indicators λ and μ , is load intensity, which shows the degree of coordination of the specified flows of applications:

Listed indicators k, τ, λ, l och, T och, ν, T obs, μ, ρ, Р k are the most common for QS.

Application of various mathematical methods to formalization. Emphasis on a complex system - unpredictable. Carrier uncertainty is the man.

A typical example of stochastic (random, probabilistic) problems are models of queuing systems.

SMOs are ubiquitous. These are telephone networks, gas stations, consumer services, ticket offices, trade events, etc.

From the position of modeling the queuing process, situations when queues of requests (requirements) for service are formed arise as follows. Having entered the serving system, the requirement joins the queue of other (previously received) requirements. The service channel selects a requirement from those in the queue in order to start servicing it. After the completion of the procedure for servicing the next request, the service channel starts servicing the next request, if there is one in the waiting block. The cycle of functioning of a QS of this kind is repeated many times during the entire period of operation of the serving system. It is assumed that the transition of the system to servicing the next requirement after the completion of servicing the previous requirement occurs instantly, at random times.

Examples of SMOs are:

car maintenance posts;

car repair posts;

audit firms, etc.

The founder of the theory of queuing, in particular, the theory of queues, is the famous Danish scientist A.K. Erlang (1878-1929), who studied the processes of service at telephone exchanges.

Systems in which service processes take place are called queuing systems (QS).

To describe a queuing system, you must specify:

- input flow of applications;

- service discipline;

- service time

- the number of service channels.

input stream requirements (applications) is described by identifying both probabilistic distribution law moments of receipt of requirements in the system, and number of requirements in every entry.

When asked service disciplines(DO) it is necessary to describe the rules for queuing requirements and servicing them in the system. The length of the queue can be both limited and unlimited. In the case of restrictions on the length of the queue, the application received at the input of the QS is refused. The most commonly used DOs are defined by the following rules:

first come - first served;

came last - served first; (box for tennis balls, stack in technique)

random selection of applications;

selection of applications by priority criterion.

Service time applications in QS is a random variable. The most common distribution law is the exponential law.  - service speed. =number of service requests/units. time.

Service channels, can be placed in parallel or in series. With a sequential arrangement of channels, each application is serviced on all channels sequentially. With a parallel arrangement of channels, service is performed on all channels simultaneously as they become free.

The generalized structure of the QS is shown in fig.

Subject queuing theory is to establish the relationship between the factors that determine the functionality of the QS, and the effectiveness of its functioning.

QS design problems.

The tasks of determining the characteristics of the QS structure include the problem of choosing the number of service channels (basic elements (F i)), the problem of determining the method of connecting channels (a set of connection elements (Hj)), as well as the problem of determining the throughput of channels.

one). Structure selection. If the channels operate in parallel, then the problem of choosing Str is reduced to determining the number of channels in the service part based on the condition for ensuring the operability of the QS. (Unless the queue is infinitely growing).

Note that when determining the number of system channels, in the case of their parallel arrangement, it is necessary to observe system health condition. Denote:  - the average number of requests received per unit of time, i.e. input flow intensity;  - the average number of applications satisfied per unit of time, i.e. service intensity; S - number of service channels. Then the condition for the operability of the QS will be written

or
. The fulfillment of this condition allows us to calculate the lower bound on the number of channels.

If
, the system can't handle the queue. The queue grows indefinitely.

2). It is necessary to determine the criterion for the effectiveness of functioning QS, taking into account the cost of time losses both on the part of applications and on the part of the service part.

The following three main groups of indicators are considered as indicators of the effectiveness of the functioning of the QS:

1. Indicators of the effectiveness of the use of QS.

The absolute throughput of the QS is the average number of applications that the QS can serve per unit of time.

The relative throughput of QS is the ratio of the average number of applications served by the QS per unit of time to the average number of requests received during this time.

The average duration of the period of employment of the SMO.

The QS utilization rate is the average share of time during which the QS is busy servicing applications.

2. Indicators of the quality of service applications.

Average waiting time for an application in the queue.

Average residence time of an application in the CMO.

Probability of request being denied service without waiting.

The probability that an incoming request will be immediately accepted for service.

The law of distribution of waiting time for an application in the queue.

The law of distribution of the time spent by an application in the QS.

The average number of applications in the queue.

The average number of applications in the CMO.

3. Indicators of the effectiveness of the functioning of the pair "QS - consumer".

When choosing a criterion for the efficiency of QS functioning, it is necessary to take into account the dual approach to the consideration of queuing systems. For example, the work of a supermarket, like a CMO, can be viewed from opposite sides. On the one hand, traditionally accepted, the buyer, waiting in line at the checkout, is a request for service, and the cashier is a service channel. On the other hand, a cashier who is waiting for customers can be considered as a service request, and a customer is a service device capable of satisfying the request, i.e. go to the cashier and stop the forced downtime of the cashier. (traditionally - buyers > than cashiers, if cashiers > than buyers, they are waiting for buyers).

FROM
With this in mind, it is expedient to minimize both parts of the QS simultaneously.

The use of such a dual approach implies the need to take into account, when forming the efficiency criterion, not only the above indicators separately, but also several indicators simultaneously, reflecting the interests of both serving and serviced QS subsystems. For example, it is shown that the most important efficiency criterion in queuing tasks is the total time spent by the client in the queue, on the one hand, and idle service channels, on the other.

Classification of queuing systems

1. By the nature of the service, the following types of QS are distinguished:

1.1. Waiting systems or queuing systems. Requirements that have entered the system and are not immediately accepted for service are accumulated in a queue. If the channels are free, then the request is served. If all channels are occupied at the time of receipt of the request, then the next request will be serviced after the completion of servicing the previous one. Such a system is called fully accessible (with unlimited queue).

There are systems with autonomous service, when the service starts at certain points in time;

Systems with limited queue. (garage repair)

Systems with failures. All requests that arrived at the time of servicing the request are rejected. (GTS)

Systems with group input flow and group service. In such systems, applications arrive in groups at time points, and servicing also occurs in groups.

2. According to the number of service channels, QSs are divided into the following groups.

Single channel QS.

Multichannel QS. The service of the next request may begin before the end of the service of the previous request. Each channel acts as an independent server.

3. According to the range of serviced objects, two types are distinguished.

Closed QS. A closed-loop queuing system is a queuing system in which serviced customers can return to the system and be served again. Examples of a closed SMO are repair shops, savings banks.

Open CMOs.

4. By the number of service stages, single-phase and multi-phase QS are distinguished.

single phase QS are homogeneous systems that perform the same service operation.

Polyphase QS are systems in which service channels are arranged in series and perform various service operations. Stations are an example of a multiphase QS Maintenance cars.

The above classification of QS is conditional. In practice, most often QSs act as mixed systems. For example, requests wait for the start of service until a certain moment, after which the system starts to work as a system with failures.

Considered in the previous lecture, a Markov random process with discrete states and continuous time takes place in queuing systems (QS).

Queuing systems - these are systems in which service requests are received at random times, while the received requests are serviced using the service channels available to the system.

Examples of queuing systems are:

settlement and cash nodes in banks, enterprises;
personal computers, serving incoming applications or requirements for solving certain problems;
car service stations; gas station;
audit firms;
departments tax inspections involved in the acceptance and verification of the current reporting of enterprises;
telephone exchanges, etc.

	Knots	Requirements

Hospital	Orderlies	Patients
Production
The airport	Runway exits Registration points	Passengers

Consider the scheme of QS operation (Fig. 1). The system consists of a request generator, a dispatcher and a service node, a failure accounting node (terminator, request destroyer). A service node can generally have several service channels.

Rice. one

Application Generator – an object that generates applications: a street, a workshop with installed units. The input is application flow(the flow of customers to the store, the flow of broken units (cars, machine tools) for repairs, the flow of visitors to the wardrobe, the flow of cars to gas stations, etc.).
Dispatcher – a person or device that knows what to do with the ticket. A node that regulates and directs requests to service channels. Dispatcher:

accepts applications;
forms a queue if all channels are busy;
directs them to service channels, if any;
refuses applications (for various reasons);
receives information from the service node about free channels;
keeps track of system time.

Turn - request accumulator. The queue may not exist.
Service node consists of a finite number of service channels. Each channel has 3 states: free, busy, idle. If all channels are busy, then you can come up with a strategy to whom to transfer the application.
Refusal from service occurs if all channels are busy (some of them may not work).

In addition to these basic elements in QS, some sources also distinguish the following components:

terminator - destroyer of transactions;

warehouse - storage of resources and finished products;

check accounting- to perform operations of the "posting" type;

manager - manager of resources;

CMO classification

The first division (by the presence of queues):

CMO with failures;
CMO with a queue.

AT CMO with failures a request that arrives at the moment when all channels are busy is rejected, leaves the QS, and is not served further.

AT CMO with a queue an application that arrives at a time when all channels are busy does not leave, but queues up and waits for an opportunity to be served.

QS with queues subdivided into different types depending on how the queue is organized - limited or not limited. Restrictions can relate to both the length of the queue and the waiting time, "service discipline".

So, for example, the following QS are considered:

QS with impatient requests (queue length and service time are limited);
QS with priority service, i.e. some applications are served out of turn, etc.

Queue restriction types can be combined.

Another classification divides the CMO according to the source of applications. Requests (requirements) can be generated by the system itself or by some external environment, which exists independently of the system.

Naturally, the flow of requests generated by the system itself will depend on the system and its state.

In addition, SMOs are divided into open CMO and closed SMO.

In an open QS, the characteristics of the flow of applications do not depend on the state of the QS itself (how many channels are busy). In a closed QS, they depend. For example, if one worker services a group of machines that require adjustment from time to time, then the intensity of the flow of "requirements" from the machines depends on how many of them are already in good order and waiting for adjustment.

An example of a closed system: the issuance of a salary by a cashier at an enterprise.

By the number of channels, QS are divided into:

single-channel;
multichannel.

Characteristics of the queuing system

The main characteristics of a queuing system of any kind are:

the input stream of incoming requirements or service requests;
queue discipline;
service mechanism.

Requirements input stream

To describe the input stream, you need to set a probabilistic law that determines the sequence of moments of receipt of service requirements, and indicate the number of such claims in each regular receipt. In this case, as a rule, they operate with the concept of "probabilistic distribution of the moments of receipt of requirements". Here you can act like single and group requirements (the number of such claims in each successive receipt). In the latter case, we are usually talking about a queuing system with parallel-group service.

A i– arrival time between requirements – independent identically distributed random variables;

E(A) is the mean (MO) arrival time;

λ=1/E(A)- the intensity of receipt of requirements;

Input stream characteristics:

A probabilistic law that determines the sequence of moments of receipt of service requirements.
The number of requests in each next arrival for multicast flows.

Queue discipline

Turn - a set of requirements waiting to be serviced.

The queue has a name.

Queue discipline determines the principle according to which the requests arriving at the input of the service system are connected from the queue to the service procedure. The most commonly used queue disciplines are defined by the following rules:

first come - first served;

first in first out (FIFO)

the most common type of queue.

What data structure is suitable for describing such a queue? The array is bad (limited). You can use a LIST structure.

The list has a beginning and an end. The list consists of entries. An entry is a list cell. The application comes to the end of the list, and is selected for service from the beginning of the list. The entry consists of a description of the application and a link (an index of who is behind it). In addition, if the queue has a time limit, then the time limit must also be specified.

You, as programmers, should be able to make lists two-sided, one-sided.

List actions:

insert into the tail;
take from the beginning;
remove from list after timeout.
last come, first served LIFO (cartridge clip, dead end at the railway station, went into a full car).

A structure known as a STACK. Can be described by an array or list structure;

random selection of applications;
selection of applications by priority criterion.

Each application is characterized, among other things, by a priority level and, upon arrival, is placed not at the tail of the queue, but at the end of its priority group. The dispatcher sorts by priority.

Queue characteristics

limitationwaiting time the moment of service occurrence (there is a queue with a limited waiting time for service, which is associated with the concept of “admissible queue length”);
queue length.

Service mechanism

Service mechanism is determined by the characteristics of the service procedure itself and the structure of the service system. Service procedures include:

number of service channels ( N);
the duration of the service procedure (probabilistic distribution of the service time of requirements);
the number of requirements satisfied as a result of the implementation of each such procedure (for group applications);
the probability of failure of the serving channel;
service system structure.

For an analytical description of the characteristics of the service procedure, the concept of "probabilistic distribution of the service time of requirements" is used.

Si– service time i th requirement;

E(S)– average service time;

μ=1/E(S)- the speed of service requirements.

It should be noted that the time for servicing an application depends on the nature of the application itself or the requirements of the client and on the state and capabilities of the servicing system. In some cases it is also necessary to take into account service channel failure probability after a certain limited time interval. This characteristic can be modeled as a stream of failures entering the QS and having priority over all other applications.

QS utilization factor

Nμ – service rate in the system when all service devices are busy.

ρ=λ/( Nμ) is called QS utilization factor , shows how much system resources are being used.

Service system structure

The structure of the service system is determined by the number and mutual arrangement of service channels (mechanisms, devices, etc.). First of all, it should be emphasized that a service system may have not one service channel, but several; a system of this kind is able to serve several requirements simultaneously. In this case, all service channels offer the same services, and, therefore, it can be argued that there is parallel service .

Example. Cash registers in the store.

The service system can consist of several different types of service channels through which each serviced requirement must pass, i.e. in the service system requirements servicing procedures are implemented sequentially . The service mechanism defines the characteristics of the outgoing (served) stream of requests.

Example. Medical Commission.

Combined Service - servicing deposits in the savings bank: first the controller, then the cashier. As a rule, 2 controllers per cashier.

So, the functionality of any queuing system is determined by the following main factors :

probabilistic distribution of the moments of receipt of service requests (single or group);
requirements source capacity;
probabilistic distribution of service duration time;
service system configuration (parallel, serial or parallel-serial service);
the number and performance of serving channels;
queue discipline.

The main criteria for the effectiveness of the functioning of the QS

As the main criteria for the effectiveness of the functioning of queuing systems Depending on the nature of the problem being solved, there may be:

the probability of immediate service of the received application (P service =K obs /K post);
the probability of denial of service of the received application (P otk =K otk /K post);

It is obvious that R obl + P otk =1.

Flows, delays, service. Pollacek–Khinchin formula

Delay – one of the QS service criteria, the time spent by the request in anticipation of service.

D i– delay in the request queue i;

W i \u003d D i + S i– time spent in the system of the requirement i.

(with probability 1) is the established average delay of a request in the queue;

(with probability 1) is the steady-state average time the requirement spends in the QS (waiting).

Q(t) - the number of requests in the queue at a time t;

L(t)– number of customers in the system at a time t(Q(t) plus the number of requirements that are in service at the time t.

Then exponents (if any)

(with probability 1) is the steady-state time-average number of requests in the queue;

(with probability 1) is the steady-state time-averaged number of requests in the system.

Note that ρ<1 – обязательное условие существования d, w, Q and L in the queuing system.

If we remember that ρ= λ/( Nμ), then it is clear that if the intensity of receipt of requests is greater than Nμ, then ρ>1, and it is natural that the system will not be able to cope with such a flow of applications, and therefore, one cannot speak of d, w, Q and L.

The most general and necessary results for queuing systems include the conservation equations

It should be noted that the above criteria for evaluating the performance of the system can be analytically calculated for queuing systems M/M/N(N>1), i.e., systems with Markov flows of customers and service. For M/G/ l for any distribution G and for some other systems. In general, the distribution of time between arrivals, the distribution of service time, or both must be exponential (or a kind of k-th order exponential Erlang distribution) for an analytic solution to be possible.

In addition, you can also talk about such characteristics as:

absolute throughput of the system – А=Р service *λ;
relative throughput of the system -

Another interesting (and illustrative) example of an analytical solution – calculation of steady-state average queue delay for a queuing system M/G/ 1 according to the formula:

In Russia, this formula is known as the Pollacek formula. – Khinchin, abroad this formula is associated with the name of Ross.

Thus, if E(S) has a greater value, then the overload (measured in this case as d) will be larger; which is to be expected. The formula also reveals a less obvious fact: congestion also increases when the variability in the service time distribution increases, even if the average service time remains the same. Intuitively, this can be explained as follows: the variance of the service time random variable can take on a large value (since it must be positive), i.e. the only service device will be busy for a long time, which will lead to an increase in the queue.

The subject of queuing theory is to establish the relationship between the factors that determine the functionality of the queuing system, and the efficiency of its functioning. In most cases, all parameters that describe queuing systems are random variables or functions, so these systems are referred to as stochastic systems.

The random nature of the flow of applications (requirements), as well as, in the general case, the duration of service leads to the fact that a random process occurs in the queuing system. By the nature of the random process occurring in a queuing system (QS) are distinguished Markov and non-Markov systems . In Markov systems, the incoming flow of requests and the outgoing flow of serviced requests (claims) are Poisson. Poisson flows make it easy to describe and build a mathematical model of a queuing system. These models have fairly simple solutions, so most of the well-known applications of queuing theory use the Markov scheme. In the case of non-Markovian processes, the problems of studying queuing systems become much more complicated and require the use of statistical modeling, numerical methods using a computer.

For all models of queuing networks described in Chapter 2, it was assumed that the service times of requests at different stages of the route are independent. This does not adequately reflect the real situation in information transmission networks, where the length (volume) of a message does not change during its transmission from one node to another, which leads to the need to study networks with dependent (in particular, identical) message transmission durations on channels.

In this paper, following, it is assumed that, along with the service duration, each message is also characterized by its volume, and with respect to the service durations, only their conditional (with a fixed volume) independence is assumed, which makes it possible to actually take into account the dependence of the service durations of the same message at different stages of its route. In this case, we restrict ourselves to the Kelly routing principles (Jackson-type networks with Markov routing are a special case of the model under consideration).

An alternative proof of the multiplicative representation for the stationary state probabilities of such networks with nodes of various types that implement the so-called symmetric service disciplines and allow the dependence of service requirements in different nodes of the route is given. At the same time, subtle questions of the existence of stationary distributions for general networks, which are the subject of independent research, are not touched upon.

5.2.1 Description of the network. Notation

Consider a MO network, for the description of which we will use the following notation:

M is a finite set of network nodes,

M is the number of nodes in the MO network,

Node number, .

Nodes are assumed to be of the following types:

0) exponential multi-line nodes with infinite storage capacity and FIFO discipline (note that the theorem below can be easily transferred to exponential nodes with a random choice of server or place in the queue);

1) infinite-linear;

2) single-line with infinite storage capacity, inverse service discipline with service interruption and after-service;

3) single-line with infinite storage capacity and the discipline of uniform division of the device.

The set of nodes of the type is denoted and the number of devices in the node - .

Everywhere, as before, we will denote random variables in uppercase Latin letters, and their realizations - in the corresponding lowercase letters, and vector random variables and vectors will be highlighted in bold.

The network receives Poisson flow requests intensity , and each incoming request is characterized by a set of random variables independent of similar random variables for other requests and the history of the network, where:

Random order route length, i.e. the number of stages at which it will be serviced;

Random route, which is a set of numbers of nodes (possibly repeating), sequentially passed by the application at all L stages;

Random volumes at successively passed stages of the route, generally speaking, are different at different stages;

Random service durations at successively passed stages of the route are also, generally speaking, different at different stages. Note that if, at some stage, a claim is serviced at a node of type 2 or 3, then the service duration for this stage represents the time that a customer would be served at this node if there were no other customers in it.

Volume Y can have both a real physical meaning in the form, for example, of the amount of memory required to write a message, or be of an auxiliary nature, for example, to set the types of requests in the network; in the latter case, the model under consideration can be interpreted as a MO network with a continual set of message types.

Obviously, with such a description of the network, the volume and length correspond to the service of the request in the node with the number . Recall that routes R are allowed in which numbers can be repeated, i.e. A claim can be serviced at the same node s several times with different service times.

Statistical characteristics of a random variable are given by the joint distribution function (DF)

joint RF of the route and volumes of the application at the stages, through

conditional joint DF of the duration of service of the application at the stages with a fixed route and volumes and after

the conditional RF of the duration of servicing the request at the stage (at the node with the number ) for a fixed route and volumes.

The following assumptions are made about the introduced functions.

(P 1.) Service times are assumed to be conditionally independent along the route, i.e. conditional DF has the form

(P 2.) The exponential nodes s are -linear QSs (with infinite storage capacity) in which the service rates of any customer by each server are equal to

Thus, if , i.e. at the stage of the route, the claim is serviced at node s of type 0, then

In other words, the duration of service at a node of type 0 does not depend on either the route R or the volumes Y (including the volume ) and has an exponential distribution with the parameter.

(P 3). The distribution functions do not contain a singular component.

Then their densities, understood in the usual sense for absolutely continuous distributions or in the generalized sense for discrete and mixed distributions, will be denoted by , respectively.

In addition, for nodes of types 1-3, we set

and, to shorten the notation of the results, we denote additionally by

conditional distribution densities of the end time (intensity) of servicing a claim with characteristics at the route stage (at the node ) provided that it was serviced for time then

It might be useful to read: