Queuing networks and their application. Queuing network. Stochastic queue networks

Network queuing (SeMO) - a network that provides services to incoming requests. Service requirements in the QS are performed by service devices. The classical QS contains from one to an infinite number of devices. Depending on the availability of the possibility of waiting by incoming requests for the start of servicing, the QS are subdivided into: systems with losses, in which requests that did not find a single free device at the time of arrival are lost; systems with waiting, in which there is an infinite storage drive for buffering the received requests, when In this case, pending requests form a queue; systems with a drive of finite capacity (waiting and restrictions), in which the queue length cannot exceed the capacity of the drive; in this case, the demand arriving at the overcrowded QS (there are no free waiting places) is lost.

Each QS is designed to service (fulfill) a certain flow of claims (or requirements) arriving at the input of the system, for the most part, not regularly, but at random times. Service of applications, in general case, also does not last 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 servicing leads to uneven workload of the QS: at some time intervals, unserved claims can accumulate at the QS input (they either enter the queue or leave the QS unserved), while in other periods, with free channels at the QS input, there will be no claims , which leads to underloading of the system, i.e. to idle channels.

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

) incoming flow of applications;

) queue;

) service channels;

) the outgoing flow of serviced claims.

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 operational efficiency (bandwidth), which allows it to more or less successfully cope with the flow of applications.

The subject of studying the theory of queuing is the QS.

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

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

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 state of the QS). mass service

In many areas of economics, finance, production and everyday life important role play mass service systems (CMO), 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 CMOs in the financial and economic sphere, one can cite systems that are: banks of various types, insurance organizations, tax inspectorates, auditing services, various communication systems (including telephone stations), loading and unloading complexes (freight stations), gas stations, various enterprises and organizations of the service sector (shops, catering establishments, information bureaus, hairdressing salons, ticket offices, currency exchange offices, repair shops, hospitals).

Such systems as computer networks, systems for collecting, storing and processing information, transport systems, automated production areas, production lines can also be considered as a kind of CMO.

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

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

Another typical example of queuing systems can serve as warehouses or bases of supply and sales organizations, and the task of the queuing theory is to establish the optimal ratio between the number of service requirements entering the base and the number of service devices, at which the total maintenance costs and losses from transport downtime would be minimal. Queuing theory can also find application when calculating the area storage facilities, while the warehouse area is considered as a service device, and the arrival vehicle for unloading - as a requirement.

Main characteristics of CMO

CMO includes the following the elements: source of requests, incoming flow of requests, queue, server (service channel), outgoing flow of requests (served requests).

Each QS is designed to service (fulfill) a certain flow of claims (claims) arriving at the input of the system, mainly not regularly, but at random times. Serving applications also does not last 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 is ready to receive the next request.

The random nature of the flow of claims and the time of their service leads to uneven workload of the QS: at some time intervals at the input of the QS, unhandled claims can accumulate, which leads to an overload of the QS, in some other time intervals with free channels at the input of the CMO, there are no claims. will be, which leads to underloading of the system, i.e. to the freezing of its channels. Orders accumulating at the entrance of the QS, either "become" in the queue, or for some reason, the impossibility of further stay 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 servicing 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, cars, etc.

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

CMO is the subject of study queuing theory.

The goal of queuing theory - development of recommendations for the rational construction of the QS, rational organization of their work and regulation of the flow of applications to ensure high efficiency of the QS functioning.

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

As characteristics of the efficiency of the functioning of the system three main groups of (usually average) indicators can be selected:

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

1.1. Absolute throughput QS is the average number of applications that 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 received applications during the same time.

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

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

2. Service quality indicators:

2.1. Average waiting time for a request in the queue.

2.2. Average time spent by an application in the CMO.

2.3. The probability of denial of service request without waiting.

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

2.5. The law of distribution of the 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 CMO, etc.

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

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

The mathematical study of the functioning of the QS is greatly simplified if the random process taking place in it is markov... For a random process to be Markov, it is necessary and sufficient that all streams of events under the influence of which the system transitions from state to state are (simplest) poisson.

The simplest stream has three main properties: ordinariness, stationarity and absence of aftereffect.

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

Stationary is called a flow for which the mathematical expectation of the number of requests entering the system per unit of time (we denote λ ) does not change over time. Thus, the probability of a certain number of requirements entering the system within a given period of time ? T depends on its value and does not depend on its origin 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 (T +? T)... For example, if a cash register breaks at the moment and is eliminated by the cashier, this does not affect the possibility of a new break at this cash register at the next moment, and even more so on the likelihood of a break at other cash registers.

For the simplest flow, the frequency of arrival of claims in the system obeys Poisson's law, i.e., the probability of arrival in time Tsmooth k requirements is given by the formula

where λ — flow rate, i.e., the average number of applications arriving in the QS per unit of time,

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

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

The random waiting time in the queue for the start of service can also be considered exponentially distributed:

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

where T och is the average value of the 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 obeys in many cases an exponential distribution law with density

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

An important characteristic of CMO, combining indicators λ and μ , is an load intensity, which shows the degree of agreement of the specified flows of applications:

The listed indicators k, τ, λ, l pts, T pts, ν, T obs, μ, ρ, P k are the most common for CMOs.

Application of various mathematical methods to formalization. The emphasis is on a complex system - unpredictable. Carrier uncertainty is a person.

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

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

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

Examples of QSs are:

vehicle maintenance posts;

car repair posts;

audit firms, etc.

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

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

To describe the 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 as probabilistic distribution law moments of receipt of requests in the system, and number of claims in every admission.

When assigning service disciplines (DO) it is necessary to describe the rules for queuing and servicing requests in the system. Moreover, the queue length can be either limited or unlimited. In case of restrictions on the length of the queue, the request received at the input of the QS is refused. The most commonly used DOs are determined 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 request to the QS is a random variable. The most common distribution law is the exponential law.  - service speed.  \u003d number of service requests / unit. time.

Service channels, can be arranged in parallel and in series. With a sequential arrangement of channels, each customer 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 the establishment of the relationship between the factors that determine the functionality of the QS, and the efficiency of its functioning.

Problems of designing QS.

The problems of determining the characteristics of the structure of the QS include the problem of choosing the number of service channels (basic elements (Ф i )), the problem of determining a method for connecting channels (a set of link elements (Hj)), as well as the task of determining the bandwidth of the 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 serving part based on the condition of 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 operability condition... We denote:  - the average number of applications arriving per unit of time, i.e. input stream intensity;  is 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 calculating the lower limit of the number of channels.

If
, the system cannot handle the queue. At the same time, the queue grows infinitely.

2). It is necessary to determine the criterion of the effectiveness of the functioningQS taking into account the cost of loss of time both on the part of applications and on the part of the serving 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 CMO.

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 the QS is the ratio of the average number of applications served by the QS per unit of time to the average number of applications received during this time.

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

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

2. Indicators of the quality of service applications.

Average waiting time for a request in the queue.

Average time spent by an application in the CMO.

The probability of a request being denied service without waiting.

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

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

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

The average number of applications in the queue.

Average number of applications in the CMO.

3. Indicators of the effectiveness of the functioning of the “SMO - consumer” pair.

When choosing a criterion for the efficiency of the QS functioning, it is necessary to take into account a dual approach to the consideration of queuing systems. For example, the operation of a supermarket, as an SMO, can be viewed from opposite sides. On the one hand, traditionally accepted, the customer waiting in turn at the checkout represents 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 cash register and stop the forced idle cashier. (traditionally - buyers\u003e than cashiers, if cashiers\u003e than buyers, they wait for buyers).

FROM
taking this into account, it is advisable 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 simultaneously several indicators reflecting the interests of both the servicing and the serviced subsystems of the QS. For example, it is shown that the most important criterion of efficiency in queuing tasks is the total time spent by a client in a queue, on the one hand, and downtime of service channels, on the other.

Queuing system classification

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

1.1. Waiting systems or queuing systems... Requests entered into the system and not immediately accepted for service accumulate in a queue. If the channels are free, then the request is served. If all channels are busy at the time of the arrival of the request, then the next request will be served after the service of the previous one is completed. This system is called full access (with unlimited queue).

There are systems with stand-alone servicing, where servicing begins at certain points in time;

Limited queue systems... (garage repair)

Systems with failures... All applications that arrived at the time of service of the application are refused. (GTS)

Systems with group input flow and group service... In such systems, claims arrive in groups at times; service also occurs in groups.

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

Single-channel SMO.

Multichannel CMO... Servicing of the next request can begin before the end of servicing of the previous request. Each channel acts as a self-contained service device.

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

Closed CMOs. A closed queuing system is a queuing system in which serviced claims can be returned to the system and returned to service. Examples of a closed CMO are repair shops, savings banks.

Open CMOs.

4. According to the number of maintenance stages, single-phase and multiphase CMOs are distinguished.

Single phaseQS are homogeneous systems that perform the same maintenance operation.

Multiphase SMOs are systems in which service channels are located sequentially and perform various service operations. An example of a multiphase system are stations maintenance cars.

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

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

Queuing systems - these are systems in which service requests arrive 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, at enterprises;
personal computersserving incoming applications or requirements for solving certain problems;
car service stations; Gas station;
audit firms;
departments tax inspectoratesdealing with the acceptance and verification of the current reporting of enterprises;
telephone exchanges, etc.

	Nodes	Requirements

Hospital	Orderlies	The patients
Production
Airport	Runway exits Registration points	Passengers

Let's consider the scheme of work of the QS (Fig. 1). The system consists of a request generator, a dispatcher and a service unit, a failure accounting unit (terminator, order destroyer). In general, a service node can have several service channels.

Figure: one

Application generator - an object that generates applications: a street, a workshop with installed units. The entrance receives flow of applications (the flow of customers to the store, the flow of broken units (machines, machine tools) for repairs, the flow of visitors to the wardrobe, the flow of cars to the gas station, etc.).
Dispatcher - a person or device that knows what to do with the application. 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 available;
refuses applications (for various reasons);
receives information from the service node about free channels;
monitors the system uptime.

Queue - accumulator of applications. There may be no queue.
Service node consists of a finite number of service channels. Each channel has 3 states: free, busy, not working. If all channels are busy, then you can come up with a strategy to whom to transfer the request.
Renouncement from service occurs if all channels are busy (some of them may not work).

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

terminator - the destroyer of transactions;

warehouse - accumulator of resources and finished products;

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

manager - resource manager;

CMO classification

First division (by the presence of queues):

CMO with failures;
CMO with a queue.

IN CMO with rejections a request arriving at a time when all channels are busy receives a refusal, leaves the QS and is not serviced in the future.

IN CMO with queue a request arriving at the moment when all channels are busy does not leave, but enters the queue and waits for the opportunity to be served.

CMO 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 QSs are considered:

QS with impatient requests (queue length and service time are limited);
QS with service with priority, i.e., some requests 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 environmentthat exists independently of the system.

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

In addition, CMOs are divided into openCMO and closed CMO.

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 serves a group of machines that occasionally require adjustment, then the intensity of the flow of "requirements" from the machines depends on how many of them are already working properly and waiting for adjustment.

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

By the number of channels, CMOs are divided into:

single-channel;
multichannel.

Queuing system characteristics

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

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

Input stream requirements

To describe the input stream, you need to set a probabilistic law that determines the sequence of times when service requests arrive, 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 claims”. Here they can do as single and group requirements (the number of such claims in each regular admission). In the latter case, we are usually talking about a service system with parallel group service.

A i- the time of arrival between the requirements - independent identically distributed random variables;

E (A) - average (MO) time of admission;

λ \u003d 1 / E (A) - the intensity of the receipt of requests;

Input stream characteristics:

A probabilistic law that determines the sequence of times of receipt of service requests.
The number of requests in each successive arrival for group flows.

Queue discipline

Queue - a set of requirements awaiting service.

The queue has a name.

Queue discipline defines the principle according to which the requests arriving at the input of the serving 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 would be suitable for describing such a queue? The array is bad (limited). You can use a structure of the LIST type.

The list has a beginning and an end. The list consists of entries. A record is a cell in a list. The request arrives at the end of the list, and is selected for service from the beginning of the list. The record consists of a description of the application and a link (an indicator of who is behind). In addition, if the queue has a timeout limit, then the timeout limit must also be specified.

As programmers, you should be able to make two-sided, one-sided lists.

List actions:

insert into the tail;
take from the beginning;
remove from list after timeout.
came last - served firstLIFO (clip for cartridges, dead end at the railway station, went into a packed carriage).

A structure known as a STACK. Can be described by an array or a 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 in 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 the onset of service (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. The characteristics of the maintenance procedure include:

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

For an analytical description of the characteristics of the servicing procedure, one operates with the concept of “probabilistic distribution of customer servicing time”.

S i - service time ith requirements;

E (S) - average service time;

μ \u003d 1 / E (S)- the speed of servicing requests.

It should be noted that the service time of a request depends on the nature of the request itself or the client's requirements and on the state and capabilities of the serving 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 flow of failures entering the QS and having priority over all other applications.

Utilization rate of CMO

N· Μ is the service rate in the system when all service devices are busy.

ρ=λ/( Nμ) is called coefficient of use of the system , shows how much the system resources are involved.

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 can have not one service channel, but several; a system of this kind is capable of serving 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. Checkout counters in the store.

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

Example. Medical Commission.

Combined service - service of deposits in the savings bank: first the controller, then the cashier. As a rule, there are 2 controllers for one cashier.

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

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

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

As 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 request (P obsl \u003d K obs / K post);
the probability of refusal to service the received request (P open \u003d K open / K post);

Obviously, P obsl + P open \u003d 1

Streams, delays, maintenance. Pollachek-Khinchin formula

Delay - one of the criteria for servicing the QS, the time spent by the application waiting for 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 steady-state average delay of a request in the queue;

(with probability 1) - the steady-state average time spent by the request in the CMO (waiting).

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

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

Then the indicators (if they exist)

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

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

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

Recalling that ρ \u003d λ / ( Nμ), then it is seen that if the intensity of the arrival of requests is greater than Nμ, then ρ\u003e 1 and it is natural that the system will not be able to cope with such a flow of requests, and therefore, we cannot talk about the values d, w, Qand L.

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

It should be noted that the above-mentioned criteria for evaluating the performance of the system can be analytically calculated for queuing systems M / M / N(N\u003e 1), i.e., systems with Markov flows of claims and services. 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 of these quantities must be exponential (or a kind of exponential k-th order Erlang distribution) for an analytical solution to become possible.

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

absolute throughput of the system - A \u003d P obsl * λ;
relative system throughput -

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

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

So if E (S) is more important, then the overload (in this case measured as d) will be larger; which is to be expected. The formula also reveals a less obvious fact: congestion also increases when the variability of 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 random variable of the service time 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 the establishment of a relationship between the factors that determine the functionality of the queuing system, and the efficiency of its functioning. In most cases, all parameters describing queuing systems are random variables or functions, therefore these systems are referred to as stochastic systems.

The random nature of the flow of claims (claims), 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 the queuing system (QS), distinguish 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; therefore, most of the known applications of queuing theory use the Markov scheme. In the case of non-Markov processes, the problems of studying queuing systems become much more complicated and require the use of statistical modeling, numerical methods using computers.

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

In this paper, following it is assumed that, along with the service duration, each message is also characterized by its own volume, and with respect to the service durations, only their conditional (for 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 various stages of its route. In this case, we restrict ourselves to the principles of Kelly routing (Jackson-type networks with Markov routing are a special case of the considered model).

An alternative proof of the multiplicative representation for the stationary probabilities of the states of such networks with nodes of various types, implementing the so-called symmetric servicing disciplines, and admitting the dependence of servicing claims at different nodes of the route is given. This does not touch upon the subtle issues of the existence of stationary distributions for general networks, which are the subject of independent research.

5.2.1 Description of the network. Designations

Consider an MO network, for 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 multilinear ones with infinite storage capacity and FIFO discipline (note that the theorem below can be easily transferred to exponential nodes with a random choice of a device or a place in the queue);

1) infinite-linear;

2) single-line with infinite storage capacity, inversion discipline of service with service interruption and additional service;

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

The set of type nodes is designated and the number of devices in a node is.

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

The network receives poisson flow requests of intensity, and each incoming request is characterized by a set of random variables that do not depend on similar random variables for other requests and the history of the network, where:

The random length of the claim route, i.e. the number of stages at which it will be served;

A random route, which is a set of node numbers (possibly repeating), sequentially traversed by the claim at all L stages;

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

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

The volume Y can have both a real physical meaning in the form of, for example, the amount of memory required to record a message, or be of an auxiliary nature, for example, to specify the types of claims in the network; in the latter case, the model under consideration can be interpreted as an ML network with a continuous set of message types.

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

The statistical characteristics of a random variable are specified by the joint distribution function (DF)

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

conditional joint DF of the durations of service of the request at stages with fixed route and volumes and through

conditional DF of the duration of service of the request at the stage (in the node with the number) with fixed route and volumes.

The following assumptions are made regarding the introduced functions.

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

(A 2.) The exponential nodes s are -linear QS (with infinite storage capacity), the service rates in which any claim by each server are equal to

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

In other words, the duration of service in 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 a parameter.

(P 3). 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 put

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 a node), provided that it was served time Note that if at the route stage a claim is served at an exponential node with a number (i.e. if), then

It might be useful to read: