Analytical modeling based on queuing systems - Computing...

Analytical modeling based on queuing systems

In analytical modeling, the study of processes or objects is replaced by the construction of their mathematical models and the study of these models. The basis of the method is the identity of the form of equations and the uniqueness of the relationships between the variables in the equations describing the original and the model. Since the events occurring in local computer networks are of a random nature, then probabilistic mathematical models of queuing theory are most suitable for their study [5].

Analytical network model is a set of mathematical relationships that connect the input and output characteristics of the network. In the derivation of such relations, some minor details or circumstances must be neglected [8].

The telecommunications network can be represented in some simplicity as a set of processors (nodes) connected by communication channels. The message arriving at the node is waiting for some time before it is processed. In this case, a queue of such messages waiting for processing can be formed. The transmission time or the total delay time of the message:


where - propagation time, service time and waiting time respectively. One of the tasks of analytical modeling is the determination of the average value of D. For large loads, the main contribution is given by the expectation of servicing IV. The notation of DJ Kendell will be used in the following to describe the queues:

where A is the arrival process; B - the maintenance process; C - the number of servers (nodes); K - the maximum size of the queue (by default - ∞);

in - the number of clients (by default - yes); z - scheme of the buffer (default FIFO).

The letters A and B represent the arrival and service processes and are usually replaced by the following letters characterizing the law corresponding to the distribution of events:

D - constant probability;

M - the Markov exponential distribution;

G - the generalized distribution law;

- the Erlang distribution of the order k;

is a hyperexponential distribution of order k [4].

The most common buffer schemes are

FIFO (First-In-First-Out), LIFO (Last-In-First-Out) and FIRO (First-In-Random-Out). For example, the record M/M/2 means a queue for which the arrival and maintenance times have an exponential distribution, there are two servers, the queue length and the number of clients can be arbitrarily large, and the buffer operates as FIFO [ 19].

The average value of the queue length Q for a given mean input frequency λ and the mean waiting time W is determined on the basis of Little's theorem (1961) [18]:


For the variant of the queue M/G/ 1, the input process is characterized by the Poisson distribution with the rate of arrival of the messages λ. The probability of entering to messages to the input for the time t is:


Let N be the number of clients in the system, Q - the number of clients in the queue and let the probability that the incoming client discovers j other clients , is equal to:


Then the average waiting time:


where σ is the root-mean-square deviation for the distribution of the service time.

For the variant of the queue (Η - function

distribution of service time). Whence follows [18].


For the M/D/ queue, 1 the service time is constant, and the average wait time is:


Consider an Ethernet version based on a switch concentrator with the number of channels N. It will be assumed that the messages at the input of all nodes have a Poisson distribution with an average intensity, the distribution of messages along the length is arbitrary. Messages are sent in the same order in which they arrived. Traffic in the network is assumed to be symmetric. The queue has a model . The average latency in this case is:




where , and is equal to the probability that the sender's message/'is sent to the recipient . The requirement of stability requires that . For large n this results in

The operation of the Ethernet network is characterized by a number of parameters, including the probability of channel capture and efficiency [18]. The first parameter is determined by the expression


where P is the probability that exactly one station will attempt to transmit a frame during the measure and capture the channel; Q - number of stations attempting to capture a channel for transmission of a data frame.

LAN Ethernet performance is defined as follows. The total operating time of the Ethernet network is divided between the transmission intervals and the competition intervals. To transfer a data frame, seconds are required, where L is the frame length in bits, C is the data transfer rate in bps. The average time T required to capture the channel is:


where W is the average number of cycles passed in the competition interval, until the station captures the channel for transmission of the data frame; B is the duration of the measure or the time until the conflict is detected after the beginning of the frame transfer.

The average number of cycles W is calculated as follows:


Taking into account the entered parameters, the efficiency Ε of the Ethernet LAN operation is defined as follows:


The following types of SMO are most often used for LAN modeling:

1. Single-channel SMO with waiting. They represent one serving device with an infinite queue. This QS is the most common in modeling. With a certain share of approximation with its help, you can simulate almost any LAN node.

2. Single-channel CMOs with losses. They represent one serving device with a finite number of seats in the queue. If the number of requests exceeds the number of seats in the queue, the excess entries are lost. This type of SMO can be used to simulate the transmission channels in the LAN.

3. Multichannel SMO with expectation. They represent several parallel operating devices with a common infinite queue. This type of SMO is often used in modeling groups of subscriber terminals of LANs that operate in interactive mode.

4. Multichannel CMOs with losses. They represent several parallel operating devices with a common queue, the number of places in which is limited. These SMOs, like single-channel ones with losses, are often used to simulate communication channels in a LAN.

5. Single-channel SMO with group receipt of applications. They represent one serving device with an infinite queue. Before serving, orders are grouped into packets according to a specific rule.

6. Single-channel SMO with group service requests. They represent one serving device with an infinite queue. Applications are served by packages that are compiled according to a certain rule. The last two types of SMO can be used to model such LAN nodes as switching centers (nodes).

The local computer network as a whole can be represented as a network of queuing. There are open , closed and mixed networks.

Open is called a mass service consisting of M nodes, and at least one of the nodes of the network receives from outside the incoming stream of applications and there is stock requests from the network. Open networks are characterized by the fact that the intensity of the receipt of applications to the network does not depend on the state of the network, that is, on the number of applications that have already entered the network. Open networks are used for modeling LANs operating in non-operational mode. Each application goes to the input of the appropriate switching node, where the place of its processing is determined. The application is then submitted to its server or on a communication channel - on "adjacent", where it is processed, then it returns to the source and leaves the network [18].

Closed is a queuing network with a set of nodes M without source and sink, in which a constant number of requests is circulating. Closed QSOs are used to simulate such LANs, the sources of information for which are subscriber terminals that work in interactive mode. In this case, each group of subscriber terminals is represented as a multi-channel queuing system with a wait and is included in the network devices [18].

There are simple and complex modes of interactive users. In simple mode, subscribers do not perform any actions other than sending jobs to the LAN and thinking about the response received. [18]

Subscribers from the terminals send requests that are sent to the switching nodes through the communication channels, and from there to the processing on the " or neighboring server. Further processing is carried out in the same way as in an open network [14].

With a complex mode of dialogue, the work of subscribers is represented as a set of operations of a certain process, called technological. Each operation of the technological process is modeled by the corresponding SMO. Some operations involve access to LAN, and some operations may not provide such treatment [18]. The algorithm of the LAN itself is the same as for a closed network.

Mixed is a network of queuing, in which several different types of applications (graphics) are circulating, and the network is closed with respect to some types of applications, and the network is open with respect to others. With the help of mixed SMO, such LANs are simulated, some of whose subscribers work in the interactive, and some in the non-operational mode. Dialogue subscribers also distinguish between simple and complex mode of operation. Often mixed SMOs simulate LANs, in which the server is additionally loaded with tasks that are solved on the background of the network itself [18].

The algorithm of network operation for interactive users is similar to the algorithm of closed network operation, and the algorithm of network operation for non-operative subscribers is the algorithm of open network operation.

Distinguish between exponential and non-exponential models of LAN. Exponential models are based on the assumption that the streams of applications entering the LAN are Poisson, and the maintenance time in the LAN nodes has an exponential distribution.

For such networks, exact methods are obtained to determine their characteristics; the complexity of obtaining a solution depends mainly on the dimension of the network [18].

However, in most networks (and local networks in particular) the streams are not Poisson. The models of such networks are called non-exponential . In the analysis of non-exponential networks, in the general case there are no exact solutions, therefore the approximate methods are most suitable here.

One of these methods is the diffusion approximation method . Using diffusion approximation has allowed to obtain approximate analytical dependencies to determine the characteristics of all types of QSOs discussed above.


This does not require an accurate knowledge of the distribution functions of random variables associated with a given QS (the intervals between receipts of applications by the service time in the devices), but only the knowledge of the first (mathematical expectation) and the second (variance or squared coefficient of variation - ΚΚΒ) of these quantities [18].

The application of diffusion approximation for LAN analysis is based on the following:

• for each type of application, the intensity of the receipt of applications of this type in the nodes of the network is calculated as if only one stream of applications circulated on the network only one;

• according to a certain rule, depending on the type of SMO and the discipline of service, the streams of applications from all sources are added;

• According to a certain rule, the average service time in each LAN node is determined;

• the obtained values ​​are substituted into the corresponding diffusion formula and the characteristics of the LAN nodes are determined;

• the characteristics of the LAN as a whole are determined.

The statement of the LAN analysis task assumes the following form. Given:

• the number of LAN nodes;

• the type of each LAN node (the type of SMO that simulates this node);

• service discipline in each LAN node;

• the total number of types of application sources working in interactive mode;

• the total number of types of application sources working in non-operational mode;

• for dialog sources in case of complex operation, the number of technological processes of each type, the number of operations in each technological process, the average and ΚΚΒ the execution time of each operation, the probability matrix of transfers between operations, and the presence or absence of each LAN access operation ;

• for dialog sources in the case of simple operation, the number of sources (terminals) of each type, the average and ΚΚΒ the response time of the subscriber to the network response;

• for non-operational subscribers - the average intensity of the receipt of applications and ΚΚΒ the time between the receipt of applications; for each type of request (dialog and non-operative), the average service intensity in each LAN node, ΚΚΒ the maintenance time in the LAN nodes, and the probability matrix of the transmissions between the nodes. It is required to find:

• mean and variance (or standard deviation) of the delay time of an application of each type in the LAN as a whole;

• mean and variance (or standard deviation) of the delay time in LAN nodes;

• loading of LAN nodes;

• probability of losing an application in the LAN node (for nodes simulated by QMS with losses).

Limitations can be as follows:

• Node loading should not exceed 1;

• The probability of losing an application should not exceed 1;

• all characteristics must be positive.

Sometimes it is of interest to determine such an indicator as the maximum delay time of an application of each type in the LAN. The maximum time is a time, the excess of which is permissible only for a certain, pre-defined percentage of applications of each type. To determine the maximum time, a technique is used based on the approximation of the delay time distribution function in the network by the Erlang or hypsrepansion distribution, and it is necessary to specify the percentage (percentage) of applications for which the maximum time is calculated.

thematic pictures

Also We Can Offer!

Ошибка в функции вывода объектов.