Play five possible values of a continuous random variable. Simulation of random events

The essence of the Monte Carlo method is as follows: you need to find the value A some studied quantity. For this purpose, choose a random variable X whose mathematical expectation is equal to a: M(X) = a.

In practice, they do this: they calculate (play out) n possible values x i of the random variable X, find their arithmetic mean

And they take a* of the desired number a as an estimate (approximate value). Thus, to use the Monte Carlo method, you must be able to play a random variable.

Let it be necessary to play a discrete random variable X, i.e. calculate the sequence of its possible values x i (i=1,2, ...), knowing the distribution law of X. Let us introduce the notation: R is a continuous random variable distributed uniformly in the interval (0,1); r i (j=1,2,...) – random numbers (possible values of R).

Rule: In order to play a discrete random variable X specified by the distribution law

X x 1 x 2 ... x n

P p 1 p 2 … p n

1. Divide the interval (0,1) of the or axis into n partial intervals:

Δ 1 =(0;р 1), Δ 2 =(р 1; р 1+ р 2), …, Δ n = (р 1 +р 2 +…+р n -1; 1).

2. Choose a random number r j . If r j fell into the partial interval Δ i, then the value being played took on a possible value x i. .

Playing out a complete group of events

It is required to play out tests, in each of which one of the events of the full group occurs, the probabilities of which are known. Playing out a complete group of events comes down to playing a discrete random variable.

Rule: In order to play tests, in each of which one of the events A 1, A 2, ..., A n of the complete group occurs, the probabilities of which p 1, p 2, ..., p n are known, it is enough to play a discrete value X with the following distribution law :

P p 1 p 2 … p n

If in the test the value X took on a possible value x i =i, then the event A i occurred.

Playing a Continuous Random Variable

The distribution function F of a continuous random variable X is known. It is required to play X, i.e. calculate the sequence of possible values x i (i=1,2, ...).

A. Method of inverse functions. Rule 1. x i of a continuous random variable X, knowing its distribution function F, you need to choose a random number r i, equate its distribution function and solve the resulting equation F(x i) = r i for x i.

If the probability density f(x) is known, then rule 2 is used.

Rule 2. To play out the possible value x i of a continuous random variable X, knowing its probability density f, you need to choose a random number r i and solve the equation for x i

or equation

where a is the smallest final possible value of X.

B. Superposition method. Rule 3. In order to play the possible value of a random variable X, the distribution function of which

F(x) = C 1 F 1 (x)+C 2 F 2 (x)+…+C n F n (x),

where F k (x) – distribution functions (k=1, 2, …, n), С k >0, С i +С 2 +…+С n =1, you need to choose two independent random numbers r 1 and r 2 and using the random number r 1, play the possible value of the auxiliary discrete random variable Z (according to rule 1):

p C 1 C 2 … C n

If it turns out that Z=k, then solve the equation F k (x) = r 2 for x.

Remark 1. If the probability density of a continuous random variable X is given in the form

f(x)=C 1 f 1 (x)+C 2 f 2 (x)+…+C n f n (x),

where f k are probability densities, coefficients C k are positive, their sum is equal to one, and if it turns out that Z=k, then solve (according to rule 2) with respect to x i with respect to or the equation

Approximate play of a normal random variable

Rule. In order to approximate the possible value x i of a normal random variable X with parameters a=0 and σ=1, you need to add 12 independent random numbers and subtract 6 from the resulting sum:

Comment. If you want to approximately play a normal random variable Z with mathematical expectation A and standard deviation σ, then, having played the possible value of x i according to the above rule, find the desired possible value using the formula: z i =σx i +a.

Definition 24.1.Random numbers name possible values r continuous random variable R, distributed uniformly in the interval (0; 1).

1. Playing a discrete random variable.

Suppose we want to play a discrete random variable X, that is, obtain a sequence of its possible values, knowing the distribution law X:

X x 1 X 2 … x n

r r 1 R 2 … r p .

Consider a random variable uniformly distributed in (0, 1) R and divide the interval (0, 1) with points with coordinates R 1, R 1 + R 2 , …, R 1 + R 2 +… +r p-1 on P partial intervals whose lengths are equal to the probabilities with the same indices.

Theorem 24.1. If each random number that falls into the interval is assigned a possible value, then the value being played will have a given distribution law:

X x 1 X 2 … x n

r r 1 R 2 … r p .

Proof.

Possible values of the resulting random variable coincide with the set X 1 , X 2 ,… x n, since the number of intervals is equal P, and when hit r j in an interval, a random variable can take only one of the values X 1 , X 2 ,… x n.

Because R is distributed uniformly, then the probability of it falling into each interval is equal to its length, which means that each value corresponds to the probability p i. Thus, the random variable being played has a given distribution law.

Example. Play 10 values of a discrete random variable X, the distribution law of which has the form: X 2 3 6 8

R 0,1 0,3 0,5 0,1

Solution. Let's divide the interval (0, 1) into partial intervals: D 1 - (0; 0.1), D 2 - (0.1; 0.4), D 3 - (0.4; 0.9), D 4 – (0.9; 1). Let's write out 10 numbers from the random number table: 0.09; 0.73; 0.25; 0.33; 0.76; 0.52; 0.01; 0.35; 0.86; 0.34. The first and seventh numbers lie on the interval D 1, therefore, in these cases, the random variable played took on the value X 1 = 2; the third, fourth, eighth and tenth numbers fell into the interval D 2, which corresponds to X 2 = 3; the second, fifth, sixth and ninth numbers were in the interval D 3 - in this case X = x 3 = 6; There were no numbers in the last interval. So, the possible values played out X are: 2, 6, 3, 3, 6, 6, 2, 3, 6, 3.

2. Acting out opposite events.

Let it be required to play out tests, in each of which an event A appears with a known probability R. Consider a discrete random variable X, taking the value 1 (if the event A happened) with probability R and 0 (if A did not happen) with probability q = 1 – p. Then we will play this random variable as suggested in the previous paragraph.

Example. Play 10 challenges, each with an event A appears with probability 0.3.

Solution. For a random variable X with the law of distribution X 1 0

R 0,3 0,7

we obtain the intervals D 1 – (0; 0.3) and D 2 – (0.3; 1). We use the same sample of random numbers as in the previous example, for which the numbers No. 1, 3 and 7 fall into the interval D 1, and the rest - into the interval D 2. Therefore, we can assume that the event A occurred in the first, third, and seventh trials, but did not occur in the remaining trials.

3. Playing out a complete group of events.

If events A 1 , A 2 , …, A p, whose probabilities are equal R 1 , R 2 ,… r p, form a complete group, then for play (that is, modeling the sequence of their appearances in a series of tests), you can play a discrete random variable X with the law of distribution X 1 2 … P, having done this in the same way as in point 1. At the same time, we believe that

r r 1 R 2 … r p

If X takes on the value x i = i, then in this test the event occurred A i.

4. Playing a continuous random variable.

a) Method of inverse functions.

Suppose we want to play a continuous random variable X, that is, get a sequence of its possible values x i (i = 1, 2, …, n), knowing the distribution function F(x).

Theorem 24.2. If r i is a random number, then the possible value x i played continuous random variable X with a given distribution function F(x), corresponding r i, is the root of the equation

F(x i) = r i. (24.1)

Proof.

Because F(x) monotonically increases in the interval from 0 to 1, then there is a (and unique) value of the argument x i, at which the distribution function takes the value r i. This means that equation (24.1) has a unique solution: x i= F -1 (r i), Where F-1 - function inverse to F. Let us prove that the root of equation (24.1) is a possible value of the random variable under consideration X. Let us first assume that x i is the possible value of some random variable x, and we prove that the probability of x falling into the interval ( s, d) is equal to F(d) – F(c). Indeed, due to monotonicity F(x) and that F(x i) = r i. Then

Therefore, So, the probability of x falling into the interval ( c,d) is equal to the increment of the distribution function F(x) on this interval, therefore, x = X.

Play 3 possible values of a continuous random variable X, distributed uniformly in the interval (5; 8).

F(x) = , that is, it is necessary to solve the equation. Let's choose 3 random numbers: 0.23; 0.09 and 0.56 and substitute them into this equation. Let's get the corresponding possible values X:

b) Superposition method.

If the distribution function of the random variable being played can be represented as a linear combination of two distribution functions:

then, since when X®¥ F(x) ® 1.

Let us introduce an auxiliary discrete random variable Z with the law of distribution

Z 12 . Let's choose 2 independent random numbers r 1 and r 2 and play the possible

p C 1 C 2

meaning Z by number r 1 (see point 1). If Z= 1, then we look for the desired possible value X from the equation, and if Z= 2, then we solve the equation .

It can be proven that in this case the distribution function of the random variable being played is equal to the given distribution function.

c) Approximate play of a normal random variable.

Since for R, uniformly distributed in (0, 1), then for the sum P independent, uniformly distributed random variables in the interval (0,1). Then, by virtue of the central limit theorem, the normalized random variable at P® ¥ will have a distribution close to normal, with the parameters A= 0 and s =1. In particular, a fairly good approximation is obtained when P = 12:

So, to play out the possible value of the normalized normal random variable X, you need to add 12 independent random numbers and subtract 6 from the sum.

Send your good work in the knowledge base is simple. Use the form below

Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

Posted on http://www.allbest.ru/

LESSON 1

Simulation of random events with a given distribution law

Playing a Discrete Random Variable

Let it be necessary to play a discrete random variable, i.e. obtain a sequence of its possible values x i (i = 1,2,3,...n), knowing the distribution law of X:

Let us denote by R a continuous random variable. The value of R is distributed uniformly in the interval (0,1). By r j (j = 1,2,...) we denote the possible values of the random variable R. Let us divide the interval 0< R < 1 на оси 0r точками с координатами на n частичных интервалов.

Then we get:

It can be seen that the length of the partial interval with index i is equal to the probability P with the same index. Length

Thus, when a random number r i falls into the interval, the random variable X takes on the value x i with probability P i .

There is the following theorem:

If each random number that falls into the interval is associated with a possible value x i , then the value being played will have a given distribution law

Algorithm for playing a discrete random variable specified by the distribution law

1. It is necessary to divide the interval (0,1) of the 0r axis into n partial intervals:

2. Select (for example, from a table of random numbers, or on a computer) a random number r j .

If r j fell into the interval, then the discrete random variable being played took on a possible value x i .

Playing a Continuous Random Variable

Let it be required to play a continuous random variable X, i.e. obtain a sequence of its possible values x i (i = 1,2,...). In this case, the distribution function F(X) is known.

Exists next theorem.

If r i is a random number, then the possible value x i of the played continuous random variable X with a known distribution function F(X) corresponding to r i is the root of the equation

Algorithm for playing a continuous random variable:

1. You must select a random number r i .

2. Equate the selected random number to the known distribution function F(X) and obtain an equation.

3. Solve this equation for x i. The resulting value x i will simultaneously correspond to the random number r i . and the given distribution law F(X).

Example. Play 3 possible values of a continuous random variable X, distributed uniformly in the interval (2; 10).

The distribution function of the X value has the following form:

By condition, a = 2, b = 10, therefore,

In accordance with the algorithm for playing a continuous random variable, we equate F(X) to the selected random number r i .. We get from here:

Substitute these numbers into equation (5.3). We obtain the corresponding possible values of x:

Problems of modeling random events with a given distribution law

1. It is required to play 10 values of a discrete random variable, i.e. obtain a sequence of its possible values x i (i=1,2,3,…n), knowing the distribution law of X

Let's select a random number r j from the table of random numbers: 0.10; 0.12; 0.37; 0.09; 0.65; 0.66; 0.99; 0.19; 0.88; 0.59; 0.78

2. The frequency of receipt of requests for service is subject to the exponential distribution law (), x, the parameter l is known (hereinafter l = 1/t - the intensity of receipt of requests)

l=0.5 requests/hour. Determine the sequence of values for the duration of intervals between receipts of applications. The number of implementations is 5. Number r j: 0.10; 0.12; 0.37; 0.09; 0.65; 0.99;

LESSON 2

Queuing system

Systems in which, on the one hand, there are massive requests for the performance of any type of service, and on the other hand, these requests are satisfied, are called queuing systems. Any QS serves to fulfill the flow of requests.

QS include: source of requirements, incoming flow, queue, serving device, outgoing flow of requests.

SMO are divided into:

QS with losses (failures)

Queue with waiting (unlimited queue length)

QS with limited queue length

QS with limited waiting time.

Based on the number of channels or service devices, QS systems can be single-channel or multi-channel.

By location of the source of requirements: open and closed.

By the number of service elements per requirement: single-phase and multiphase.

One of the forms of classification is the D. Kendall classification - A/B/X/Y/Z

A - determines the distribution of time between arrivals;

B - determines the distribution of service time;

X - determines the number of service channels;

Y - determines the system capacity (queue length);

Z - determines the order of service.

When the system capacity is infinite and the queue of service follows the first-come-first-serve principle, the Y/Z parts are omitted. The first digit (A) uses the following symbols:

The M-distribution has an exponential law,

G-the absence of any assumptions about the service process, or it is identified with the symbol GI, meaning a recurrent service process,

D- deterministic (fixed service time),

E n - Erlang nth order,

NM n - hyper-Erlang nth order.

The second digit (B) uses the same symbols.

The fourth digit (Y) shows the buffer capacity, i.e. maximum number of places in the queue.

The fifth digit (Z) indicates the method of selection from the queue in a waiting system: SP-equal probability, FF-first in-first out, LF-last in-first out, PR-priority.

For tasks:

l is the average number of applications received per unit of time

µ - average number of applications served per unit of time

Channel 1 load factor, or the percentage of time the channel is busy.

Main characteristics:

1) P reject - probability of failure - the probability that the system will refuse service and the requirement is lost. This happens when the channel or all channels are busy (TFoP).

For a multi-channel QS P open =P n, where n is the number of service channels.

For a QS with a limited queue length P open =P n + l, where l is the permissible queue length.

2) Relative q and absolute A system capacity

q= 1-P open A=ql

3) Total number of requirements in the system

L sys = n - for SMO with failures, n is the number of channels occupied by servicing.

For QS with waiting and limited queue length

L sys = n+L cool

where L cool is the average number of requests waiting for service to begin, etc.

We will consider the remaining characteristics as we solve the problems.

Single-channel and multi-channel queuing systems. Systems with failures.

The simplest single-channel model with a probabilistic input flow and service procedure is a model characterized by an exponential distribution of both the durations of the intervals between receipts of requirements and the service durations. In this case, the distribution density of the duration of intervals between receipts of requests has the form

Density of distribution of service durations:

The flows of requests and services are simple. Let the system work with failures. This type of QS can be used when modeling transmission channels in local networks. It is necessary to determine the absolute and relative throughput of the system. Let's imagine this queuing system in the form of a graph (Figure 2), which has two states:

S 0 - channel free (waiting);

S 1 - channel is busy (request is being serviced).

Figure 2. State graph of a single-channel QS with failures

Let us denote the state probabilities: P 0 (t) - the probability of the “channel free” state; P 1 (t) - probability of the “channel busy” state. Using the labeled state graph, we compile a system of Kolmogorov differential equations for state probabilities:

The system of linear differential equations has a solution taking into account the normalization condition P 0 (t) + P 1 (t) = 1. The solution of this system is called unsteady, since it directly depends on t and looks like this:

P 1 (t) = 1 - P 0 (t) (3.4.3)

It is easy to verify that for a single-channel QS with failures, the probability P 0 (t) is nothing more than the relative capacity of the system q. Indeed, P 0 is the probability that at time t the channel is free and a request arriving at time t will be serviced, and, therefore, for a given time t the average ratio of the number of requests served to the number of received ones is also equal to P 0 (t), i.e. q = P 0 (t).

After a large time interval (at), a stationary (steady) mode is achieved:

Knowing the relative throughput, it is easy to find the absolute one. Absolute throughput (A) is the average number of requests that a queuing system can serve per unit of time:

The probability of refusal to service a request will be equal to the probability of the “channel busy” state:

This value of P open can be interpreted as the average share of unserved applications among those submitted.

In the vast majority of cases, in practice, queuing systems are multi-channel, and, therefore, models with n serving channels (where n>1) are of undoubted interest. The queuing process described by this model is characterized by the intensity of the input flow l, while no more than n clients (applications) can be served in parallel. The average duration of servicing one request is 1/m. The input and output streams are Poisson. The operating mode of a particular servicing channel does not affect the operating mode of other servicing channels of the system, and the duration of the servicing procedure for each channel is a random variable subject to an exponential distribution law. The ultimate goal of using n parallel connected service channels is to increase (compared to a single-channel system) the speed of servicing requests by servicing n clients simultaneously. The state graph of a multi-channel queuing system with failures has the form shown in Figure 4.

Figure 4. State graph of a multi-channel QS with failures

S 0 - all channels are free;

S 1 - one channel is occupied, the rest are free;

S k - exactly k channels are occupied, the rest are free;

S n - all n channels are occupied, the rest are free.

Kolmogorov’s equations for the probabilities of system states P 0 , ... , P k , ... P n will have the following form:

The initial conditions for solving the system are:

P 0 (0) = 1, P 1 (0) = P 2 (0) = ... = P k (0) = ... = P 1 (0) = 0.

The stationary solution of the system has the form:

Formulas for calculating probabilities P k (3.5.1) are called Erlang formulas.

Let us determine the probabilistic characteristics of the functioning of a multi-channel QS with failures in a stationary mode:

1) probability of failure:

since a request is rejected if it arrives at a time when all n channels are busy. The value P open characterizes the completeness of servicing the incoming flow;

2) the probability that the request will be accepted for service (it is also the relative capacity of the system q) complements P open to one:

3) absolute throughput

4) the average number of channels occupied by service () is as follows:

The value characterizes the degree of loading of the QS.

Tasksfor lesson 2

1. A communication branch with one channel receives the simplest flow of messages with an intensity of l = 0.08 messages per second. The transmission time is distributed according to the exp law. Servicing of one message occurs with intensity µ=0.1. Messages arriving at times when the serving channel is busy transmitting a previously received message receive a transmission failure.

Coeff. Relative channel load (probability of channel occupancy)

P reject probability of failure to receive a message

Q relative capacity of the internode branch

And the absolute throughput of the communication branch.

2. The communication branch has one channel and receives messages every 10 seconds. The service time for one message is 5 seconds. The message transmission time is distributed according to an exponential law. Messages arriving when the channel is busy are denied service.

Define

Rzan - probability of communication channel occupancy (relative load factor)

Q - relative throughput

A - absolute capacity of the communication branch

4. The internodal branch of the secondary communication network has n = 4 channels. The flow of messages arriving for transmission through the communication branch channels has an intensity = 8 messages per second. The average transmission time of one message is t = 0.1 seconds. A message arriving at a time when all n channels are busy receives a transmission failure along the communication branch. Find the characteristics of the SMO:

LESSON 3

Single channel system with standby

Let us now consider a single-channel QS with waiting. The queuing system has one channel. The incoming flow of service requests is the simplest flow with intensity. The intensity of the service flow is equal (i.e., on average, a continuously busy channel will issue serviced requests). The duration of service is a random variable subject to the exponential distribution law. The service flow is the simplest Poisson flow of events. A request received when the channel is busy is queued and awaits service. This QS is the most common in modeling. With one degree or another of approximation, it can be used to simulate almost any node of a local computer network (LAN).

Let us assume that no matter how many requests arrive at the input of the serving system, this system (queue + clients being served) can not accommodate more than N-requirements (applications), i.e. customers who are not on hold are forced to be served elsewhere. System M/M/1/N. Finally, the source generating service requests has unlimited (infinitely large) capacity. The state graph of the QS in this case has the form shown in Figure 3

Figure 3. State graph of a single-channel QS with waiting (scheme of death and reproduction)

The QS states have the following interpretation:

S 0 - “channel free”;

S 1 - “channel busy” (no queue);

S 2 - “channel busy” (one request is in queue);

S n - “channel busy” (n -1 applications are in queue);

S N - “channel busy” (N - 1 applications are in queue).

The stationary process in this system will be described by the following system of algebraic equations:

where p=load factor

n - state number.

The solution to the above system of equations for our QS model has the form:

Initial probability value for a QS with a limited queue length

For a QS with an infinite queue Н =? :

P 0 =1- s (3.4.7)

It should be noted that the fulfillment of the stationarity condition for a given QS is not necessary, since the number of applications admitted to the serving system is controlled by introducing a restriction on the length of the queue, which cannot exceed (N - 1), and not by the ratio between the intensities of the input flow, i.e. not the ratio c = l/m.

Unlike the single-channel system, which was considered above and with an unlimited queue, in this case a stationary distribution of the number of requests exists for any finite values of the load factor c.

Let us determine the characteristics of a single-channel QS with waiting and a limited queue length equal to (N - 1) (M/M/1/N), as well as for a single-channel QS with a buffer of unlimited capacity (M/M/1/?). For a QS with an infinite queue, the condition with<1, т.е., для того, чтобы в системе не накапливалась бесконечная очередь необходимо, чтобы в среднем запросы в системе обслуживались быстрее, чем они туда поступают.

1) probability of refusal to service an application:

One of the most important characteristics of systems in which loss of requests is possible is the probability P loss that an arbitrary request will be lost. In this case, the probability of losing an arbitrary request coincides with the probability that at an arbitrary moment in time all waiting places are occupied, i.e. the following formula is valid: Р from k = Р Н

2) relative system capacity:

For SMO with unlimitedth queue q =1, because all requests will be serviced

3) absolute throughput:

4) the average number of applications in the system:

L S with unlimited queue

5) average time an application stays in the system:

For unlimited queue

6) average length of stay of a client (application) in the queue:

With unlimited queue

7) average number of applications (clients) in the queue (queue length):

with unlimited queue

Comparing the expressions for the average waiting time in the queue T och and the formula for the average length of the queue L och, as well as the average residence time of requests in the system T S and the average number of requests in the system L S, we see that

L och =l*T och L s =l* T s

Note that these formulas are also valid for many queuing systems that are more general than the M/M/1 system under consideration and are called Little’s formulas. The practical significance of these formulas is that they eliminate the need to directly calculate the values of T och and T s with a known value of the values L och and L s and vice versa.

Single-channel tasks SMOwith anticipation, Withwaiting andlimited queue length

1. Given a single-line QS with an unlimited queue storage. Applications are received every t = 14 seconds. The average transmission time of one message is t=10 seconds. Messages arriving at times when the serving channel is busy are received in the queue without leaving it before servicing begins.

Determine the following performance indicators:

2. The internode communication branch, which has one channel and a queue storage for m=3 pending messages (N-1=m), receives the simplest message flow with an intensity of l=5 messages. in seconds. The time of message transmission is distributed according to an exponential law. The average transmission time of one message is 0.1 seconds. Messages arriving at times when the serving channel is busy transmitting a previously received message and there is no free space in the drive are rejected.

P reject - probability of failure to receive a message

L system - the average total number of messages in the queue and transmitted along the communication branch

T och - the average time a message remains in the queue before transmission begins

T syst - the average total time a message remains in the system, consisting of the average waiting time in the queue and the average transmission time

Q - relative throughput

A - absolute throughput

3. The internode branch of the secondary communication network, which has one channel and a queue storage for m = 4 (N-1=4) waiting messages, receives the simplest message flow with an intensity = 8 messages per second. The message transmission time is distributed according to an exponential law. The average transmission time of one message is t = 0.1 second. Messages arriving at times when the serving channel is busy transmitting a previously received message and there is no free space in the drive are rejected by the queue.

P open - probability of failure to receive a message for transmission over the communication channel of the internode branch;

L och - the average number of messages in the queue to the communication branch of the secondary network of the queue;

L system - the average total number of messages in the queue and transmitted along the communication branch of the secondary network;

T och - the average time a message remains in the queue before transmission begins;

R zan - probability of the communication channel being busy (relative channel load coefficient);

Q is the relative capacity of the internodal branch;

A is the absolute capacity of the internodal branch;

4. The internode communication branch, which has one channel and a queue storage for m=2 waiting messages, receives the simplest message flow with an intensity of l=4 messages. in seconds. The time of message transmission is distributed according to an exponential law. The average transmission time of one message is 0.1 seconds. Messages arriving at times when the serving channel is busy transmitting a previously received message and there is no free space in the drive are rejected.

Determine the following performance indicators of the communication branch:

P reject - probability of failure to receive a message

L och - average number of messages in the queue to the communication branch

L system - the average total number of messages in the queue and transmitted along the communication branch

T och - the average time a message remains in the queue before transmission begins

T syst - the average total time a message remains in the system, consisting of the average waiting time in the queue and the average transmission time

Rzan - probability of communication channel occupancy (relative channel load coefficient c)

Q - relative throughput

A - absolute throughput

5. The internode branch of the secondary communication network, which has one channel and an unlimited volume storage queue of waiting messages, receives the simplest flow of messages with an intensity of l = 0.06 messages per second. The average transmission time of one message is t = 10 seconds. Messages arriving at times when the communication channel is busy are received in the queue and do not leave it until service begins.

Determine the following performance indicators of the secondary network communication branch:

L och - the average number of messages in the queue to the communication branch;

L syst - the average total number of messages in the queue and transmitted along the communication branch;

T och - the average time a message stays in the queue;

T syst is the average total time a message remains in the system, which is the sum of the average waiting time in the queue and the average transmission time;

Rzan is the probability of the communication channel being busy (relative channel load factor);

Q - relative capacity of the internodal branch;

A - absolute capacity of the internodal branch

6. Given a single-line QS with an unlimited queue storage. Applications are received every t = 13 seconds. Average time to transmit one message

t=10 seconds. Messages arriving at times when the serving channel is busy are received in the queue without leaving it before servicing begins.

Determine the following performance indicators:

L och - average number of messages in the queue

L system - the average total number of messages in the queue and transmitted along the communication branch

T och - the average time a message remains in the queue before transmission begins

T syst - the average total time a message remains in the system, consisting of the average waiting time in the queue and the average transmission time

Rzan - probability of occupancy (relative channel load coefficient c)

Q - relative throughput

A - absolute throughput

7. The specialized diagnostic post is a single-channel QS. The number of parking lots for cars awaiting diagnostics is limited and equal to 3 [(N - 1) = 3]. If all parking lots are occupied, i.e., there are already three cars in the queue, then the next car that arrives for diagnostics will not be placed in the queue for service. The flow of cars arriving for diagnostics is distributed according to Poisson's law and has an intensity = 0.85 (cars per hour). The vehicle diagnostic time is distributed according to an exponential law and averages 1.05 hours.

It is required to determine the probabilistic characteristics of a diagnostic station operating in stationary mode: P 0 , P 1 , P 2 , P 3 , P 4 , P open, q,A, L och, L sys, T och, T sys

LESSON 4

Multi-channel QS with waiting, with waiting and limited queue length

Let's consider a multi-channel queuing system with waiting. This type of QS is often used when modeling groups of LAN subscriber terminals operating in interactive mode. The queuing process is characterized by the following: the input and output flows are Poisson with intensities and, respectively; no more than n clients can be served in parallel. The system has n service channels. The average duration of service for one client is 1/m for each channel. This system also refers to the process of death and reproduction.

c=l/nm - the ratio of the intensity of the incoming flow to the total intensity of service, is the system load factor

(With<1). Существует стационарное распределение числа запросов в рассматриваемой системе. При этом вероятности состояний Р к определяются:

where P 0 is the probability of all channels being free with an unlimited queue, k is the number of requests.

if we take c = l / m, then P 0 can be determined for an unlimited queue:

For a limited queue:

where m is the queue length

With unlimited queue:

Relative capacity q=1,

Absolute capacity A=l,

Average number of occupied channels Z=A/m

With limited queue

1 The internode branch of the secondary communication network has n = 4 channels. The flow of messages arriving for transmission through the communication branch channels has an intensity = 8 messages per second. The average time t = 0.1 for transmitting one message by each communication channel is t/n = 0.025 seconds. The waiting time for messages in the queue is unlimited. Find the characteristics of the SMO:

P open - probability of message transmission failure;

Q is the relative capacity of the communication branch;

A is the absolute throughput of the communication branch;

Z - average number of occupied channels;

L och - average number of messages in the queue;

T = average waiting time;

T syst - the average total time of messages staying in the queue and transmission along the communication branch.

2. A mechanical workshop of the plant with three posts (channels) carries out repairs of small mechanization. The flow of faulty mechanisms arriving at the workshop is Poisson and has an intensity = 2.5 mechanisms per day, the average repair time for one mechanism is distributed according to the exponential law and is equal to = 0.5 days. Let's assume that there is no other workshop at the plant, and, therefore, the queue of mechanisms in front of the workshop can grow almost unlimitedly. It is required to calculate the following limiting values of the probabilistic characteristics of the system:

Probabilities of system states;

Average number of applications in the queue for service;

Average number of applications in the system;

Average length of time an application stays in queue;

The average duration of an application's stay in the system.

3. The internodal branch of the secondary communication network has n=3 channels. The flow of messages arriving for transmission through the communication branch channels has an intensity of l = 5 messages per second. The average transmission time of one message is t=0.1, t/n=0.033 sec. The queue storage of messages awaiting transmission can contain up to m= 2 messages. A message arriving at a time when all places in the queue are occupied receives a transmission failure along the communication branch. Find the characteristics of the QS: P open - probability of message transmission failure, Q - relative throughput, A - absolute throughput, Z - average number of occupied channels, L och - average number of messages in the queue, T so - average waiting time, T system - the average total time a message remains in the queue and is transmitted along the communication branch.

LESSON 5

Closed QS

Let's consider a machine fleet servicing model, which is a model of a closed queuing system. Until now, we have considered only queuing systems for which the intensity of the incoming flow of requests does not depend on the state of the system. In this case, the source of requests is external to the QS and generates an unlimited flow of requests. Let's consider queuing systems for which it depends on the state of the system, and the source of requirements is internal and generates a limited flow of requests. For example, a machine park consisting of N machines is serviced by a team of R mechanics (N > R), and each machine can be serviced by only one mechanic. Here, machines are sources of requirements (requests for service), and mechanics are service channels. A faulty machine, after servicing, is used for its intended purpose and becomes a potential source of service requirements. Obviously, the intensity depends on how many machines are currently in operation (N - k) and how many machines are being serviced or standing in line waiting for service (k). In the model under consideration, the capacity of the requirements source should be considered limited. The incoming flow of demands comes from a limited number of operating machines (N - k), which at random times break down and require maintenance. Moreover, each machine from (N - k) is in operation. Generates a Poisson flow of requirements with intensity X regardless of other objects, the total (total) incoming flow has intensity. A request that enters the system when at least one channel is free is immediately processed. If a request finds all channels busy servicing other requests, then it does not leave the system, but gets into a queue and waits until one of the channels becomes free. Thus, in a closed queuing system, the incoming flow of requirements is formed from the outgoing one. The system state S k is characterized by the total number of requests being serviced and in queue equal to k. For the closed system under consideration, obviously, k = 0, 1, 2, ... , N. Moreover, if the system is in the state S k, then the number of objects in operation is equal to (N - k). If is the intensity of the flow of demands per machine, then:

The system of algebraic equations describing the operation of a closed-loop QS in stationary mode is as follows:

Solving this system, we find the probability of the kth state:

The value of P 0 is determined from the condition of normalizing the results obtained using the formulas for P k , k = 0, 1, 2, ... , N. Let us determine the following probabilistic characteristics of the system:

Average number of requests in queue for service:

Average number of requests in the system (serving and queuing)

average number of mechanics (channels) “idle” due to lack of work

Idleness ratio of the serviced object (machine) in the queue

Utilization rate of facilities (machines)

Downtime ratio of service channels (mechanics)

Average waiting time for service (waiting time for service in queue)

Closed QS problem

1. Let two engineers of equal productivity be allocated to service ten personal computers (PCs). The flow of failures (malfunctions) of one computer is Poisson with intensity = 0.2. PC maintenance time obeys the exponential law. The average time for servicing one PC by one engineer is: = 1.25 hours. The following service organization options are possible:

Both engineers service all ten computers, so if a PC fails, it is serviced by one of the free engineers, in this case R = 2, N = 10;

Each of the two engineers maintains five PCs assigned to him. In this case R = 1, N = 5.

It is necessary to choose the best option for organizing PC maintenance.

It is necessary to determine all the probabilities of states P k: P 1 - P 10, taking into account that using the results of calculating P k, we calculate P 0

LESSON 6

Traffic calculation.

Teletraffic theory is a section of queuing theory. The foundations of the theory of teletraffic were laid by the Danish scientist A.K. Erlang. His works were published in 1909-1928. Let us give important definitions used in the theory of teletraffic (TT). The term “traffic” corresponds to the term “telephone load”. This refers to the load created by the flow of calls, demands, and messages arriving at the inputs of the QS. The volume of traffic is the amount of the total, integral time interval missed by one or another resource during which this resource was occupied during the analyzed period of time. A unit of work can be considered a second occupation of a resource. Sometimes you can read about an hour's work, and sometimes just seconds or hours. However, ITU recommendations give the traffic volume dimension in erlango-hours. To understand the meaning of such a unit of measurement, we need to consider another traffic parameter - traffic intensity. In this case, they often talk about the average intensity of traffic (load) on a certain given pool (set) of resources. If at each moment of time t from a given interval (t 1,t 2) the number of resources from a given set occupied with servicing traffic is equal to A(t), then the average traffic intensity will be

The value of traffic intensity is characterized as the average number of resources occupied by servicing traffic at a given time interval. The unit for measuring load intensity is one Erlang (1 Erl, 1 E), i.e. 1 Erlang is such a traffic intensity that requires the full employment of one resource, or, in other words, at which the resource performs work worth one second-occupation in one second. In American literature, you can sometimes find another unit of measurement called CCS-Centrum (or hundred) Calls Second. The CCS number reflects the server occupation time in 100 second intervals per hour. The intensity measured in CCS can be converted to Erlang using the formula 36CCS=1 Erl.

Traffic generated by one source and expressed in hour-occupations is equal to the product of the number of call attempts c over a certain time interval T and the average duration of one attempt t: y = c t (h-z). Traffic can be calculated in three different ways:

1) let the number of calls c per hour be 1800, and the average duration of the session t = 3 minutes, then Y = 1800 calls. /h. 0.05 h = 90 Earl;

2) let the durations t i of all n occupations of the outputs of a certain bundle be fixed during time T, then the traffic is determined as follows:

3) let the number of simultaneously occupied outputs of a certain beam be monitored at equal intervals during time T; based on the observation results, a step function of time x(t) is constructed (Figure 8).

Figure 8. Samples of simultaneously occupied beam outputs

Traffic during time T can be estimated as the average value of x(t) over that time:

where n is the number of samples of simultaneously occupied outputs. The value Y is the average number of simultaneously occupied beam outputs during time T.

Traffic fluctuations. Traffic on secondary telephone networks fluctuates significantly over time. During the working day, the traffic curve has two or even three peaks (Figure 9).

Figure 9. Traffic fluctuations during the day

The hour of the day during which traffic observed over a long period of time is most significant is called the busiest hour (BHH). Knowledge of traffic in the CNN is fundamentally important, since it determines the number of channels (lines), the volume of equipment of stations and nodes. Traffic on the same day of the week has seasonal variations. If the day of the week is a pre-holiday, then the NNN of this day is higher than the day after the holiday. As the number of services supported by the network increases, so does the traffic. Therefore, it is problematic to predict with sufficient confidence the occurrence of traffic peaks. Traffic is closely monitored by network administration and design organizations. Traffic measurement rules were developed by ITU-T and are used by national network administrations to meet the quality of service requirements for both subscribers of their network and subscribers of other networks connected to it. Teletraffic theory can be used for practical calculations of losses or the volume of station (node) equipment only if the traffic is stationary (statistically steady). This condition is approximately satisfied by the traffic in the CHNN. The amount of load entering the automatic telephone exchange per day affects the prevention and repair of equipment. The unevenness of the load entering the station during the day is determined by the concentration coefficient

A more strict definition of the NNN is made as follows. ITU Recommendation E.500 requires analyzing 12 months of intensity data, selecting the 30 busiest days, finding the busiest hours on those days, and averaging the intensity measurements over these intervals. This calculation of traffic intensity (load) is called a normal estimate of traffic intensity in the CHN or level A. A more stringent estimate can be averaged over the 5 busiest days of the selected 30-day period. This grade is called an increased grade or a grade at level B.

The process of creating traffic. As every user of the telephone network knows, not all attempts to establish a connection with the called subscriber are successful. Sometimes you have to make several unsuccessful attempts before the desired connection is established.

Figure 10. Diagram of events when establishing a connection between subscribers

Let's consider possible events when simulating the establishment of a connection between subscribers A and B (Figure 10). Statistics on calls in telephone networks are as follows: the share of completed conversations is 70-50%, the share of failed calls is 30-50%. Any attempt by the subscriber takes the QS input. With successful attempts (when the conversation has taken place), the occupation time of the switching devices that establish connections between inputs and outputs is longer than with unsuccessful attempts. The subscriber can interrupt attempts to establish a connection at any time. Retries may be caused by the following reasons:

The number was dialed incorrectly;

Assumption of an error in the network;

The degree of urgency of the conversation;

Failed previous attempts;

Knowing the habits of subscriber B;

Doubt about dialing the number correctly.

A retry may be made depending on the following circumstances:

Degrees of urgency;

Assessment of the reasons for failure;

Assessing the feasibility of repeating attempts,

Estimates of acceptable interval between attempts.

Failure to retry may be due to low urgency. There are several types of traffic generated by calls: incoming (proposed) Y n and missed Y n. Traffic Y n includes all successful and unsuccessful attempts, traffic Y n, which is part of Y n, includes successful and some unsuccessful attempts:

Y pr = Y r + Y np,

where Y p is conversational (useful) traffic, and Y np is traffic generated by unsuccessful attempts. The equality Y p = Y p is possible only in the ideal case if there are no losses, errors by calling subscribers and no responses from called subscribers.

The difference between the incoming and transmitted loads over a certain period of time will be the lost load.

Traffic forecasting. Limited resources lead to the need for a gradual expansion of the station and network. The network administration forecasts an increase in traffic during the development phase, taking into account that:

Income is determined by the part of the transmitted traffic Y p, - costs are determined by the quality of service with the highest traffic;

A large proportion of losses (low quality) occurs in rare cases and is typical for the end of the development period;

The largest volume of missed traffic occurs during periods when there are practically no losses - if the losses are less than 10%, then subscribers do not respond to them. When planning the development of stations and the network, the designer must answer the question of what are the requirements for the quality of service provision (losses). To do this, it is necessary to measure traffic losses according to the rules adopted in the country.

Traffic measurement example.

First, let's look at how you can display the operation of a QS that has several resources that simultaneously serve some traffic. We will further talk about such resources as servers that serve the flow of applications or requirements. One of the most visual and frequently used ways to depict the process of servicing requests by a pool of servers is a Gantt chart. This diagram is a rectangular coordinate system with the x-axis depicting time and the y-axis marking discrete points corresponding to the pool servers. Figure 11 shows a Gantt chart for a three-server system.

In the first three time intervals (we count them as a second), the first and third servers are busy, the next two seconds - only the third, then the second one works for one second, then the second and the first for two seconds, and the last two seconds - only the first.

The constructed diagram allows you to calculate the volume of traffic and its intensity. The diagram reflects only served or missed traffic, since it does not say anything about whether requests entered the system that could not be serviced by the servers.

The volume of passed traffic is calculated as the total length of all segments of the Gantt chart. Volume in 10 seconds:

We associate with each time interval, plotted on the abscissa, an integer equal to the number of servers occupied in this unit interval. This value A(t) is the instantaneous intensity. For our example

A(t)= (2, 2, 2, 1, 1, 1, 2, 2, 1, 1)

Let us now find the average traffic intensity over a period of 10 seconds

Thus, the average intensity of traffic passed by the system of three servers under consideration is 1.5 Erl.

Basic load parameters

Telephone communications are used by various categories of subscribers, which are characterized by:

number of load sources - N,

average number of calls from one source over a certain time (NNN usually) - c,

the average duration of one session of the switching system when servicing one call is t.

The load intensity will be

Let's identify different call sources. For example,

Average number of calls to CHN from one office telephone;

Average number of calls from one individual apartment telephone; random event mass service teletraffic

with count - the same from the apparatus for collective use;

with ma - the same from one coin machine;

with sl - the same from one connecting line.

Then the average number of calls from one source:

There are approximate data for the average number of calls from one source of the corresponding category:

3.5 - 5, =0.5 - 1, with count = 1.5 - 2, with ma =15 - 30, with sl =10 - 30.

There are the following types of connections, which, depending on the outcome of the connection, create different telephone loads at the station:

k р - coefficient showing the proportion of connections that ended in conversation;

k з - connections that did not end in conversation due to the busyness of the called subscriber;

k but - coefficient expressing the proportion of connections that did not end in conversation due to non-response of the called subscriber;

k osh - connections that did not end in conversation due to errors by the caller;

k those - calls that did not end in conversation due to technical reasons.

During normal network operation, the values of these coefficients are equal to:

k p =0.60-0.75; k z =0.12-0.15; k but =0.08-0.12; k osh =0.02-0.05; k those =0.005-0.01.

The average duration of a session depends on the types of connections. For example, if the connection ended with a conversation, the average duration of device occupation t state will be equal to

where is the duration of connection establishment;

t comp. - a conversation that took place;

t in - the duration of sending a call to the telephone of the called subscriber;

t r - duration of conversation

where t co is the station answer signal;

1.5n - time to dial the number of the called subscriber (n - number of characters in the number);

t s is the time required to establish a connection by switching mechanisms and disconnect the connection after the end of the conversation. Approximate values of the considered quantities:

t co = 3 sec., t c = 1-2.5 sec., t b = 8-10 sec., t p = 90-130 sec.

Calls that do not end in conversation also create telephone load.

The average time for occupying devices when the called subscriber is busy is

where t installation connection determined by (4.2.3)

t зз - time of hearing the busy buzzer, t зз =6 sec.

The average duration of device occupation when the called subscriber does not answer is

where t pv - time of listening to the ringback signal, t pv = 20 sec.

If there was no conversation due to subscriber errors, then on average t osh = 30 sec.

The duration of classes that did not end in conversation due to technical reasons is not determined, since the percentage of such classes is small.

From all of the above it follows that the total load created by a group of sources behind the CNN is equal to the sum of the loads of individual types of activities.

where is a coefficient that takes into account the terms as shares

On a telephone network with seven-digit numbering, an automatic telephone exchange has been designed, the structural composition of which subscribers is as follows:

N account = 4000, N ind = 1000, N count = 2000, N ma = 400, N sl = 400.

The average number of calls received from one source in the CHNN is equal to

Using formulas (4.2.3) and (4.2.6) we find the load

1.10.62826767 sec. = 785.2 hz.

Average lesson duration t from the formula Y=Nct

t= Y/Nc= 2826767/7800*3.8=95.4 sec.

Load task

1. On a telephone network with seven-digit numbering, an automatic telephone exchange is designed, the structural composition of subscribers of which is as follows:

N uchr =5000, Nind=1500, N count =3000, N ma =500, N sl =500.

Determine the load arriving at the station - Y, the average duration of occupation t, if it is known that

with ind =4, with ind =1, with count =2, with ma =10, with sl =12, t r =120 sec., t in =10 sec., k r =0.6, t s =1 sec., =1.1.

Posted on Allbest.ru

Portal for schoolchildren. Self-preparation

Play five possible values of a continuous random variable. Simulation of random events

Send your good work in the knowledge base is simple. Use the form below

Traffic calculation.

Similar documents

Portal for schoolchildren. Self-preparation

Send your good work in the knowledge base is simple. Use the form below

Traffic calculation.

Similar documents

RELATED ARTICLES