The article describes a parallel-sequential model of a non-stationary queueing system that simulates the operation of a Zabbix monitoring system based on a distributed architecture. An algorithm for generating a list of the states of such system and its flowchart is given. Derived state transition rules and transition diagram. A sequential algorithm for generating a coefficient matrix for system of ordinary differential equations and its flowchart are given.
1 Introduction Automated monitoring systems are an important part of any information system. Monitoring is a continuous process of observing and registering the parameters of an object, processing them, comparing them with threshold values. Information systems in transport are developing rapidly, which causes an increase in the amount of net-work devices within the information system. In order to maintain full operability and timely response to problems within the information system, it must be included in the monitoring system. This monitoring system must cope with the increasing load. One of the main tasks is the ability to carry out an analytical calculation of the probabilities of the states of the monitoring system under various loads.1
The most popular and easily scalable to adapt to the load freely distributed monitoring system for information systems is Zabbix [Sha18]. Many authors use stationary models of the theory [Zeg12Upa16]. But of great interest are non-stationary queueing systems (nQS). Examples of works devoted to the non-stationary models are [Bub11, Bub99, Bub15, Bub15]. The disadvantage of the works [Bub11, Bub99] is that they consider only the classical numerical method for solving systems of ordinary differential equations (ODE) - the Runge-Kutta method, but the numerical-analytical method is presented in [Bub15, Ser15] , the speed and accuracy of which, when solving ODE system describing nQS, exceed the most common, when solving this kind of problems, the Runge-Kutta method. The advantage of this method is a recursive algorithm for generating a matrix of coefficients of an ODE system without deriving the general equation of the ODE system. But this algorithm also has significant disadvantages, described in [Sha18]. Also, in [Sha18], a sequential method for generating matrix of coefficients was proposed, without the disadvantages of the recursive method. In [Ser15] an algorithm is presented for the network model of the nQS.
This article describes a previously unreleased parallel-sequential model of the nQS. In constructing the model, modified sequential algorithm for generating a matrix of coefficients was used. 2 General description of the parallelsequential model As is known from [Sha18], the Zabbix monitoring system allows to distribute the load and scale through proxy servers using. Each proxy server collects data from its own set of devices, and then sends the data to the main server, which handles the processing. Consider the option in which there are two proxy servers and one main server. Figure 1 shows a general scheme of the interaction of system components. An information system interacting according to such scheme can be considered as queuing system. We divide such system into two subsystems, in the first subsystem there will be a proxy server, in the second - the main server. Both proxy servers have the same bandwidth, each proxy server has a separate independent queue of tasks, since it is engaged in polling values from specific set of devices. In other words, proxy servers work in parallel. After the request is processed by the first subsystem (by any of proxy servers), it immediately goes to the main server for processing. After processing the task by the main server, task is considered as processed. Each server is considered as separate queueing channel. Figure 2 presents a simplified diagram of such queueing system (QS). At any time, such QS can be described by the vectors "in_system" = [in_1, in_2, in_3] and "served" = [out_proxy, out_main]. The "in_system" vector contains three values, each value is equal to the number of tasks in the channel with corresponding number, while ||in_system|| = $0$,$$N$ . The "served" vector contains two values, where each value is equal to the number of tasks served by corresponding subsystem, while ||served|| = $0$,$N$$$−$$$|$|$ı$n$$_$s$y$$s$t$e$m$$$|$|. Where N is the total number of tasks that can enter to the system. At the input, system receives successive which depend on the number of tasks. Tasks are served in the first subsystem with intensities {µ1, µ2, … , µN}, and in the second subsystem with intensities {µ_main1, µ_main2, … , µ_main N}, which also depends on the number of tasks. 3 Modification of the state list generation algorithm For a parallel-sequential model, the number of possible states is Ns = ((N+1)*(N+2)*(N+3)*(N+4))/24, and depends on the number of tasks which can enter to the system. With a successive increase in the number of such tasks by 1, a sequence of numbers is formed from the values of Ns, which is on line 5 of Pascal’s triangle (sequence A000332 in the OEIS). The next step is to divide the states into N+1 groups so that each group has a constant value of “served” [out_main] and other parameters can be changed. Each group must be divided into N+1 subgroups so that each subgroup has a constant value of “served” [out_proxy] and remaining parameters can be changed. Each subgroup must be divided into N+1 subgroups of the second order so that in each subgroup of second order there is a constant value ||in_system|| and other parameters can be changed. Create an empty structure to store the list of states. Iterate through all possible combinations of parameters describing the state of the system. We consider a combination as new state if it satisfies the following conditions simultaneously: (1) in_1 + in_2 + out_proxy <= N; (2) in_3 = out_proxy out_main. In this case, the generated state is placed in the list of states in the subgroup of the second order according to the order of grouping at the address “states” [out_main] [out_proxy] [||in_system||]. After list of states generating using this algorithm, all states will be listed in order in sequential numbering, which allows not to sort the list and the matrix of coefficients additionally and provides convenient way to describe possible transitions between states. Figure 3 shows the flowchart of the algorithm for generating a list of states for a parallel-sequential model.
In_3 = 0 In_2 = 0 In_1 = 0
Yes
In_2 > N
No
Out_proxy += 1 In_3 > N
Yes
In_2 += 1 In_1 > N
Yes Sum(In_1, In_2, Out_proxy) <= N No No No No Yes
Yes In_3 = Out_proxy – Out_main State = ([In_1, In_2,In_3] [Out_proxy, Out_main])
[sum(In_1, In_2, In_3)] =
Yes
states = [] Group number = 0
Subgroup number = 0
Under_subgroup number = 0
4 Formation of transition rules and matrix of coefficients In the previous step, a structured list of all possible states was obtained. Thanks to this grouping, you can easily derive the rules for transitions between states. Need to notice that the basic rules of transition between states can be represented as the life cycle of task that passes through the described QS:
1. The new task enters the system on any of proxy servers, transition from the current state; 2. The new task enters the system on any of proxy servers, transition to the next state; 3. Task is served in the first subsystem (by any proxy server), transition from the current state; 4. Task is served in the first subsystem (by any proxy server), transition to the next state; 5. Task is served in the second subsystem (main server), transition from the current state; 6. Task is served in the second subsystem (main server), transition to the next state.
Also, by grouping the list of states, we can derive several rules:
1. Transition within one subgroup of the second level is impossible;
2. Within the subgroup “subgroup”, transition from the second level subgroup “under_subgroup” to the state “i” and “i”+1 (if they exist) of the next second level subgroup “under_subgroup”+1 is possible, if that "under_subgroup" is not the last nonempty subgroup of the second level of the subgroup "subgroup". The trigger for such transition is the receipt of new task in the first subsystem;
3. Within one group "group" transition is possible from any subgroup "subgroup" to subgroup "subgroup"+1. In this case, the transition is possible from the state "i" of the second level subgroup "under_subgroup" to the states "i" and "i"-1 (if they exist) the second level subgroup "under_subgroup". The trigger of such transition is the task completion in first subsystem and its transition to second subsystem;
SSuubbggrroouupp:: 11
UUnnddeerrssuubbggrroouupp:: 00
SSuubbggrroouupp:: 22
UUnnddeerrssuubbggrroouupp:: 00
SSuubbggrroouupp:: 33
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11
1100[[
UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22
1166[[00,,00,,22]][[22,,00]]
UUnnddeerrssuubbggrroouupp:: 33
1177[[
UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
1199[[00,,00,,33]][[33,,00]] 4. Inside the list of states "states" transition is possible from group "group" to group "group"+1. The transition is possible from the state "i" of the subgroup of the second level "under_subgroup" of the subgroup "subgroup" to state "i" of the second level subgroup "under_subgroup" of the subgroup "subgroup". Such transition is im-possible from the first non-empty subgroups in the group. The trigger of such transition is the task completion in the main server.
Figure 4 shows a simplified diagram of transitions between states for a parallel-sequential model with N = 3. As you can see, all states are irretrievable, which corresponds to the goal.
GGrroouupp:: 11
SSuubbggrroouupp:: 00
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
SSuubbggrroouupp:: 22
UUnnddeerrssuubbggrroouupp:: 00
SSuubbggrroouupp:: 33
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11
2266[[
UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22
2299[[00,,00,,22]][[
SSuubbggrroouupp:: 00
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
SSuubbggrroouupp:: 11
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
SSuubbggrroouupp:: 22
UUnnddeerrssuubbggrroouupp:: 00
3300[[00,,00,,00]][[22,,22]]
UUnnddeerrssuubbggrroouupp:: 11
3311[[
SSuubbggrroouupp:: 33
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11
3333[[
SSuubbggrroouupp:: 00
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
SSuubbggrroouupp:: 11
UUnnddeerrssuubbggrroouupp:: 00
SSuubbggrroouupp:: 22
UUnnddeerrssuubbggrroouupp:: 00 UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33
SSuubbggrroouupp:: 33
UUnnddeerrssuubbggrroouupp:: 00
3344[[00,,00,,00]][[33,,33]] UUnnddeerrssuubbggrroouupp:: 11 UUnnddeerrssuubbggrroouupp:: 22 UUnnddeerrssuubbggrroouupp:: 33 Consistently going through the states from generated list of states and applying the detected rules to each condition that suits the conditions, it becomes possible to simultaneously fill the matrix of coefficients. Each state is checked for compliance with certain conditions. The required changes are made to the coefficient matrix on the run. After making all changes in the matrix of coefficients, it remains only to solve the system of ordinary differential equations by a numericalanalytical method.
Figure 5 shows the flowchart for generating “matrixA” coefficient matrix.
Ns = ((N+1)*(N+2)*(N+3)*(N+4))/24 matrixA (Ns x Ns) = 0
Group_index = 0
Subgroup_index = 0 Under_subgroup_index = 0
State_index = 0
No
Subgroup_index += 1
Yes State_index += 1 Group_index += 1 Yes
(Subgroup_index < N)
AND (under_subgroup_index < N-group-index) АNum,Num -= λ[under_subgroup_index] * 2 (Subgroup_index < N)
AND (length of under_subgroup > 1)
No
No No Yes Yes Yes
Yes
to_num=subgroup[under_subgroup_index
АNum,to_num += λ[under_subgroup_index-1] АNum,Num -= µ[subgroup_index]
Yes For the first time, a parallel-sequential model of a non-stationary queue system was built, which simulating the operation of the Zabbix monitoring system based on a distributed architecture. To build the model, modified sequential algorithm for matrix of coefficients generating of ordinary differential equations was used, which accelerated the process of matrix formation in several times. In the modified algorithm, state transition rules derived in the paper were used.
The further development of the model can be the introduction of a not instantaneous transition of each task to the second subsystem after servicing in the first subsystem. In this case, task will accumulate in the queue to the main server and arrive at it for processing by several pieces at once. Such addition will allow to more accurately simulate actual behavior of Zabbix monitoring system when using distributed architecture and increase the non-stationarity of system.