Stochastic Model of a High-Loaded Monitoring System of Data
Transmission Network
Kirill S. Shardakov Vladimir P. Bubnov
Department of Information Systems and Department of Information Systems and
Technologies, Emperor Alexander I St. Technologies, Emperor Alexander I St.
Petersburg State Transport University Petersburg State Transport University
k.shardakov@gmail.com bubnov1950@yandex.ru
queueing systems (nQS). Examples of works
devoted to the non-stationary models are [Bub11,
Bub99, Bub15, Bub15]. The disadvantage of the
Abstract works [Bub11, Bub99] is that they consider only
the classical numerical method for solving systems
The article describes a parallel-sequential of ordinary differential equations (ODE) - the
model of a non-stationary queueing system Runge-Kutta method, but the numerical-analytical
that simulates the operation of a Zabbix method is presented in [Bub15, Ser15] , the speed
monitoring system based on a distributed and accuracy of which, when solving ODE system
architecture. An algorithm for generating a describing nQS, exceed the most common, when
list of the states of such system and its solving this kind of problems, the Runge-Kutta
flowchart is given. Derived state transition method. The advantage of this method is a
rules and transition diagram. A sequential recursive algorithm for generating a matrix of
algorithm for generating a coefficient coefficients of an ODE system without deriving the
matrix for system of ordinary differential general equation of the ODE system. But this
equations and its flowchart are given. algorithm also has significant disadvantages,
described in [Sha18]. Also, in [Sha18], a sequential
1 Introduction method for generating matrix of coefficients was
proposed, without the disadvantages of the
Automated monitoring systems are an important recursive method. In [Ser15] an algorithm is
part of any information system. Monitoring is a presented for the network model of the nQS.
continuous process of observing and registering the This article describes a previously unreleased
parameters of an object, processing them, parallel-sequential model of the nQS. In
comparing them with threshold values. Information constructing the model, modified sequential
systems in transport are developing rapidly, which algorithm for generating a matrix of coefficients
causes an increase in the amount of net-work was used.
devices within the information system. In order to
maintain full operability and timely response to 2 General description of the parallel-
problems within the information system, it must be
included in the monitoring system. This monitoring
sequential model
system must cope with the increasing load. One of As is known from [Sha18], the Zabbix monitoring
the main tasks is the ability to carry out an system allows to distribute the load and scale
analytical calculation of the probabilities of the through proxy servers using. Each proxy server
states of the monitoring system under various collects data from its own set of devices, and then
loads.1 sends the data to the main server, which handles the
The most popular and easily scalable to adapt to processing. Consider the option in which there are
the load freely distributed monitoring system for two proxy servers and one main server. Figure 1
information systems is Zabbix [Sha18]. Many shows a general scheme of the interaction of system
authors use stationary models of the theory [Zeg12- components.
Upa16]. But of great interest are non-stationary
Copyright c by the paper's authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). In:
A. Khomonenko, B. Sokolov, K. Ivanova (eds.): Selected Papers
of the Models and Methods of Information Systems Research
Workshop, St. Petersburg, Russia, 4-5 Dec. 2019, published at
http://ceur-ws.org
29
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
Figure 1: Simplified diagram of the interactions as separate queueing channel. Figure 2 presents a
of the monitoring system components simplified diagram of such queueing system (QS).
Figure 2: Simplified diagram of parallel-sequential QS
At any time, such QS can be described by the the number of tasks which can enter to the system.
vectors "in_system" = [in_1, in_2, in_3] and With a successive increase in the number of such
"served" = [out_proxy, out_main]. The "in_system" tasks by 1, a sequence of numbers is formed from
vector contains three values, each value is equal to the values of Ns, which is on line 5 of Pascal’s
the number of tasks in the channel with triangle (sequence A000332 in the OEIS).
corresponding number, while ||in_system|| = $$$$$
0, N . The next step is to divide the states into N+1 groups
The "served" vector contains two values, where so that each group has a constant value of “served”
each value is equal to the number of tasks served by [out_main] and other parameters can be changed.
corresponding subsystem, while ||served|| = Each group must be divided into N+1 subgroups so
$$$$$$$$$$$$$$$$$$$$$$$$$
0, N − ||ın_system||. Where N is the total number that each subgroup has a constant value of “served”
of tasks that can enter to the system. At the input, [out_proxy] and remaining parameters can be
system receives successive which depend on the changed. Each subgroup must be divided into N+1
number of tasks. Tasks are served in the first subgroups of the second order so that in each
subsystem with intensities {µ1, µ2, … , µN}, and in subgroup of second order there is a constant value
the second subsystem with intensities {µ_main1, ||in_system|| and other parameters can be changed.
µ_main2, … , µ_main N}, which also depends on Create an empty structure to store the list of states.
the number of tasks. Iterate through all possible combinations of
parameters describing the state of the system. We
3 Modification of the state list consider a combination as new state if it satisfies
the following conditions simultaneously: (1) in_1 +
generation algorithm
in_2 + out_proxy <= N; (2) in_3 = out_proxy -
out_main. In this case, the generated state is placed
For a parallel-sequential model, the number of
in the list of states in the subgroup of the second
possible states is Ns =
order according to the order of grouping at the
((N+1)*(N+2)*(N+3)*(N+4))/24, and depends on
30
address “states” [out_main] [out_proxy] provides convenient way to describe possible
[||in_system||]. After list of states generating using transitions between states. Figure 3 shows the
this algorithm, all states will be listed in order in flowchart of the algorithm for generating a list of
sequential numbering, which allows not to sort the states for a parallel-sequential model.
list and the matrix of coefficients additionally and
Start
N – amount of tasks
Structure for states keeping is Empty structure preparing
preparing
Out_main = 0
Out_proxy = 0
In_3 = 0
In_2 = 0 Create empty list of states
In_1 = 0
Finish states = []
Group number = 0
Subgroup number = 0
Out_main > N Yes Empty structure is Under_subgroup number = 0
prepared
Out_main += 1 No
Yes Out_proxy > N Yes
Group number > N
No Out_proxy += 1
In_3 > N Yes No Group number += 1
In_3 += 1 No Create empty group in states
list
Yes In_2 > N
No In_2 += 1 Yes
Subgroup number > N
In_1 > N Yes
In_1 += 1
No Subgroup number += 1 No
No
Sum(In_1, In_2, Out_proxy) <= N
Create empty subgroup in
Yes group
No
Yes
In_3 = Out_proxy – Out_main
Yes Under_subgroup number > N
State = ([In_1, In_2,In_3]
[Out_proxy, Out_main])
No
States[Out_main][Out_proxy]
[sum(In_1, In_2, In_3)] = Create under_subgroup in subgroup
State
Figure 3: The flowchart of the sequential algorithm
4 Formation of transition rules and 3. Task is served in the first subsystem (by any
matrix of coefficients proxy server), transition from the current state;
In the previous step, a structured list of all possible 4. Task is served in the first subsystem (by any
states was obtained. Thanks to this grouping, you proxy server), transition to the next state;
can easily derive the rules for transitions between 5. Task is served in the second subsystem (main
states. Need to notice that the basic rules of server), transition from the current state;
transition between states can be represented as the 6. Task is served in the second subsystem (main
life cycle of task that passes through the described server), transition to the next state.
QS: Also, by grouping the list of states, we can
1. The new task enters the system on any of derive several rules:
proxy servers, transition from the current state; 1. Transition within one subgroup of the second
2. The new task enters the system on any of level is impossible;
proxy servers, transition to the next state; 2. Within the subgroup “subgroup”, transition
from the second level subgroup “under_subgroup”
31
to the state “i” and “i”+1 (if they exist) of the next 4. Inside the list of states "states" transition is
second level subgroup “under_subgroup”+1 is possible from group "group" to group "group"+1.
possible, if that "under_subgroup" is not the last The transition is possible from the state "i" of the
nonempty subgroup of the second level of the subgroup of the second level "under_subgroup" of
subgroup "subgroup". The trigger for such the subgroup "subgroup" to state "i" of the second
transition is the receipt of new task in the first level subgroup "under_subgroup" of the subgroup
subsystem; "subgroup". Such transition is im-possible from the
3. Within one group "group" transition is first non-empty subgroups in the group. The trigger
possible from any subgroup "subgroup" to of such transition is the task completion in the main
subgroup "subgroup"+1. In this case, the transition server.
is possible from the state "i" of the second level Figure 4 shows a simplified diagram of transitions
subgroup "under_subgroup" to the states "i" and between states for a parallel-sequential model with
"i"-1 (if they exist) the second level subgroup N = 3. As you can see, all states are irretrievable,
"under_subgroup". The trigger of such transition is which corresponds to the goal.
the task completion in first subsystem and its
transition to second subsystem;
Group:
Group: 00
Subgroup:
Subgroup: 00 Subgroup:
Subgroup: 11 Subgroup:
Subgroup: 22 Subgroup:
Subgroup: 33
Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00
00 [0,
[0, 0,
0, 0]
0] [0,
[0, 0]
0]
Under
Under subgroup: 11
subgroup: Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11
11 [1,
[1, 0,
0, 0]
0] [0,
[0, 0]
0] 10
10 [0,
[0, 0,
0, 1]
1] [1,
[1, 0]
0]
22 [0,
[0, 1,
1, 0]
0] [0,
[0, 0]
0]
Under subgroup:
Under subgroup: 2 2 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22
33 [2,
[2, 0,
0, 0]
0] [0,
[0, 0]
0] 11
11 [1,
[1, 0,
0, 1]
1] [1,
[1, 0]
0] 16
16 [0,
[0, 0,
0, 2]
2] [2,
[2, 0]
0]
44 [1,
[1, 1,
1, 0]
0] [0,
[0, 0]
0] 12
12 [0,
[0, 1,
1, 1]
1] [1,
[1, 0]
0]
55 [0,
[0, 2,
2, 0]
0] [0,
[0, 0]
0]
Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33
66 [3,
[3, 0,
0, 0]
0] [0,
[0, 0]
0] 13
13 [2,
[2, 0,
0, 1]
1] [1,
[1, 0]
0] 17
17 [1,
[1, 0,
0, 2]
2] [2,
[2, 0]
0] 19
19 [0,
[0, 0,
0, 3]
3] [3,
[3, 0]
0]
77 [2,
[2, 1,
1, 0]
0] [0,
[0, 0]
0] 14
14 [1,
[1, 1,
1, 1]
1] [1,
[1, 0]
0] 18
18 [0,
[0, 1,
1, 2]
2] [2,
[2, 0]
0]
88 [1, 2, 0] [0, 0]
[1, 2, 0] [0, 0] 15 [0, 2, 1] [1,
15 [0, 2, 1] [1, 0]0]
99 [0,
[0, 3,
3, 0]
0] [0,
[0, 0]
0]
Group:
Group: 11
Subgroup:
Subgroup: 00 Subgroup:
Subgroup: 11 Subgroup:
Subgroup: 22 Subgroup:
Subgroup: 33
Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00
20
20 [0,
[0, 0,
0, 0]
0] [1,
[1, 1]
1]
Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11
21
21 [1,
[1, 0,
0, 0]
0] [1,
[1, 1]
1] 26
26 [0,
[0, 0,
0, 1]
1] [2,
[2, 1]
1]
22
22 [0,
[0, 1,
1, 0]
0] [1,
[1, 1]
1]
Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22
23
23 [2,
[2, 0,
0, 0]
0] [1,
[1, 1]
1] 27
27 [1,
[1, 0,
0, 1]
1] [2,
[2, 1]
1] 29
29 [0,
[0, 0,
0, 2]
2] [3,
[3, 1]
1]
24
24 [1,
[1, 1,
1, 0]
0] [1,
[1, 1]
1] 28
28 [0,
[0, 1,
1, 1]
1] [2,
[2, 1]
1]
25
25 [0,
[0, 2,
2, 0]
0] [1,
[1, 1]
1]
Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33
Group:
Group: 22
Subgroup:
Subgroup: 00 Subgroup:
Subgroup: 11 Subgroup:
Subgroup: 22 Subgroup:
Subgroup: 33
Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00
30
30 [0,
[0, 0,
0, 0]
0] [2,
[2, 2]
2]
Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11
31 [1, 0, 0] [2,
31 [1, 0, 0] [2, 2]2] 33
33 [0,
[0, 0,
0, 1]
1] [3,
[3, 2]
2]
32
32 [0,
[0, 1,
1, 0]
0] [2,
[2, 2]
2]
Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22
Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33
Group:
Group: 33
Subgroup:
Subgroup: 00 Subgroup:
Subgroup: 11 Subgroup:
Subgroup: 22 Subgroup:
Subgroup: 33
Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00 Under
Under subgroup:
subgroup: 00
34
34 [0,
[0, 0,
0, 0]
0] [3,
[3, 3]
3]
Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup:
subgroup: 11 Under
Under subgroup: 11
subgroup:
Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22 Under
Under subgroup:
subgroup: 22
Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33 Under
Under subgroup:
subgroup: 33
Figure 4: Simplified state transition diagram with N = 3
Consistently going through the states from run. After making all changes in the matrix of
generated list of states and applying the detected coefficients, it remains only to solve the system of
rules to each condition that suits the conditions, it ordinary differential equations by a numerical-
becomes possible to simultaneously fill the matrix analytical method.
of coefficients. Each state is checked for Figure 5 shows the flowchart for generating
compliance with certain conditions. The required “matrixA” coefficient matrix.
changes are made to the coefficient matrix on the
32
Start
N – amount of tasks
Num – state number
Ns – amount of states
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
Finish
Group_index > N Yes
Group_index += 1
No
Yes
Subgroup_index > N
No Subgroup_index += 1
Yes
Under_subgroup_index > N
Under_subgroup_index += 1 No State_index += 1
Yes State_index > N
No
(Subgroup_index < N)
AND
(under_subgroup_index < N-group-index) Subgroup_index > group_index
Yes
Yes
to_num_1=group[subgroup-index-
АNum,Num -= λ[under_subgroup_index] * 2 1][under_subgroup_index][state_inde
x].number
No to_num_2=group[subgroup-index-
1][under_subgroup_index][state_inde
(Subgroup_index < N) No x+1].number
AND АNum,to_num_1 += µ[subgroup_index-1]
(length of under_subgroup > 1) АNum,to_num_2 += µ[subgroup_index-1]
АNum,Num -= µ_main[group_index]
Yes
(Group_index > 0)
AND
State_index < length of under_subgroup - 1 (subgroup_index >= group_index)
No
Yes
Yes
to_num=subgroup[under_subgroup_index-
1][state_index].number
to_num=states[group_index-
АNum,to_num += λ[under_subgroup_index-1]
1][subgroup_index][under_subgro
АNum,Num -= µ[subgroup_index]
up_index+1][state_index].number
АNum,to_num += µ
State_index < 0 No
Yes
to_num=subgroup[under_subgroup_index-1]
[state_index-1].number
АNum,to_num += λ[under_subgroup_index-1]
АNum,Num -= µ[subgroup_index]
Figure 5: The flowchart of the algorithm for generating matrix of coefficients
33
5 Conclusion [Bub15] Bubnov V., Eremin A., Sergeev S.:
Osobennosti programmnoj realizacii
For the first time, a parallel-sequential model of a chislenno analiticheskogo metoda
non-stationary queue system was built, which raschyota modelej nestacionranyh sistem
simulating the operation of the Zabbix monitoring obsluzhivaniya. [Features of the software
system based on a distributed architecture. To build implementation of numerical-analytical
the model, modified sequential algorithm for matrix method of calculation models non-
of coefficients generating of ordinary differential stationary service systems.] SPIIRAS
equations was used, which accelerated the process Proceedings. 2015(1), pp. 218-232
of matrix formation in several times. In the (2015). (in Russ)
modified algorithm, state transition rules derived in [Bub15] Bubnov V., Khomonenko A., Sergeev S.:
the paper were used. Recursive method for generating the
The further development of the model can be coefficient matrix of the system of
the introduction of a not instantaneous transition of homogeneous differential equations
each task to the second subsystem after servicing in describing nonstationary system
the first subsystem. In this case, task will maintenance. Proceedings of International
accumulate in the queue to the main server and Conference on Soft Computing and
arrive at it for processing by several pieces at once. Measurements. SCM 2015, pp. 75-77
Such addition will allow to more accurately (2015).
simulate actual behavior of Zabbix monitoring [Ser15] Sergeev S.: Method for compilation of the
system when using distributed architecture and system of homogeneous differential
increase the non-stationarity of system. equations for calculation probability-time
characteristics which describing non
References stationary systems. Intellectual
Technologies on Transport 2015(2), pp.
[Sha18] Shardakov K..: Comparative analysis of 32-42, (2015). (in Russ)
the popular monitoring systems for [Sha18] Shardakov K., Bubnov V., Pavlov A.:
network equipment distributed under the Generating of the Coefficient Matrix of
GPL license. Intellectual Technologies on the System of Homogeneous Differential
Transport 2018(1), pp. 44–48 (2018). (in Equations. Workshop Computer Science
Russ) and Engineering in the framework of the
[Zeg12] Zegzhda P., Zegzhda D., Nikolskiy A.: 5th International Scientific-Methodical
Using graph theory for cloud system Conference "Problems of Mathematical
security modeling. Lecture Notes in and Natural-Scientific Training in
Computer Science (including subseries Engineering Education", pp. 42-47,
Lecture Notes in Arti-ficial Intelligence (2018).
and Lecture Notes in Bioinformatics), pp. [Wol14] Wolff R., Yao Y.: Little’s law when the
309–318 (2012). average waiting time is infinite. Queueing
[Oso13] Osogami T., Raymond R.: Analysis of Systems, vol. 76. pp. 267–281 (2014).
transient queues with semi definite [Sud13] R. Sudhesh, K.V. Vijayashree Stationary
optimization. Queueing Systems, vol. 73. and transient analysis of M/M/1 G-
pp. 195–234 (2013). queues. Int. J. of Mathematics in
[Upa16] Upadhyaya S.: Queueing systems with Operational Research, 2013. vol. 5. no 2.
vacation: an overview. International Pp. 282–299.
journal of mathematics in operational [Sud13] R. Sudhesh, L. Francis Raj Stationary and
research, vol. 9, issue 2. pp. 167–213 transient solution of Markovian queues —
(2016). an alternate approach. Int. J. of
[Bub11] Bubnov V., Khomonenko A., Tyrva A.: Mathematics in Operational Research,
Software reliability model with coxian 2013. vol. 5. no. 3. Pp. 407–421.
distribution of length of intervals between [Bub14] Bubnov V., Tyrva A., Eremin A.: A set of
errors detection and fixing moments. non-stationary queuing system models
International Computer Software and with phase-type distributions. SPIIRAS
Applications Conference, pp. 310-314 Proceedings, vol. 6, pp. 61–71 (2014).
(2011). [Feh70] Fehlberg E.: Low-order classical Runge—
[Bub99] Bubnov V., Safonov V.: Razrabotka Kutta formulas with step size control and
dinamicheskih modelej nestacionarnyh their application to some heat transfer
system obsluzhivaniya. [Developing problems. NASA Technical Report 315
dynamic modeling of non-stationary (1969), extract published in Computing,
systems.] Saint-Petersburg, (1999). (in vol. 6, pp. 61–71 (1970)
Russ)
34