=Paper=
{{Paper
|id=Vol-2577/paper7
|storemode=property
|title=Implementation of combined method in constructing a trajectory for structure reconfiguration of a computer system with reconstructible structure and programmable logic
|pdfUrl=https://ceur-ws.org/Vol-2577/paper7.pdf
|volume=Vol-2577
|authors=Volodymyr Tokariev,Vitalii Tkachov,Iryna Ilina,Stanislav Partyka
|dblpUrl=https://dblp.org/rec/conf/its2/TokarievTIP19
}}
==Implementation of combined method in constructing a trajectory for structure reconfiguration of a computer system with reconstructible structure and programmable logic==
https://ceur-ws.org/Vol-2577/paper7.pdf
71
Implementation of combined method in constructing a
trajectory for structure reconfiguration of a computer
system with reconstructible structure and programmable
logic
© Volodymyr Tokariev, © Vitalii Tkachov, © Iryna Ilina, © Stanislav Partyka
Kharkiv National University of Radio Electronics, Kharkiv, Ukraine
tkachov@ieee.org, tokarev@ieee.org, ilirvi_71@ukr.net,
stanislav.partyka@nure.ua
Abstract. In modern conditions providing the continuity of technological pro-
cesses as well as increasing the reliability and survivability of operation of com-
puter systems with configurable structure and programmable logic is one of the
main strategic directions of modern social-economic and technical complexes.
This is conditioned by the need to maintain the resilience and stability in the op-
eration of computer systems with a reconstructible structure and programmable
logic under various conditions of adverse effects of external and internal factors,
both natural and technogenic, as well as those human-induced. It has been found
that neutralizing threats and minimizing losses caused by abnormal, critical,
emergency and catastrophic situations leading to an avalanche-like increase in
degradation processes and destruction of computer systems with a reconstructible
structure and programmable logic, requires the development of new principles,
approaches, ways and methods of operational monitoring, analysis and forecast-
ing of situations, development of options for control decisions, procedures for
their selection and implementation in the framework of theory of structural dy-
namics control. To solve the optimization problem of constructing scenarios for
the structural reconfiguration of computer systems with a reconstructible struc-
ture and programmable logic, a method and an algorithm that implements this
method are proposed. The novelty of the method is the combined use of the ran-
dom guided search method and the method of cutting -off unpromising variants
of structural reconfiguration of computer systems with a reconstructible structure
and programmable logic such as « branch and bound». The proposed approach
allows to solve the optimization problems of constructing scenarios for the struc-
tural reconfiguration of computer systems with a reconstructible structure and
programmable logic, both unconditional and conditional, that can be described
using various structural and topological indicators.
Keywords: combined method, reconfiguration, functional element, structure,
computer system, survivability, graph.
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
72
1 Introduction
The analysis of existing and predicted critical and emergency situations that are cur-
rently occurring everywhere in various subject areas shows that they stop being sec-
toral, and develop into accidents and disasters that are already intersectoral in nature.
Under these conditions, it is necessary to investigate and solve the problems of increas-
ing the reliability and survivability of computer systems with a reconstructible structure
and programmable logic within the framework of the interdisciplinary approach. The
causes that lead to the emergence of critical situations, accidents and disasters, which
have natural-ecological, technical-industrial or anthropogenic-social causes, are of par-
ticular danger to modern computer systems with a reconstructible structure and pro-
grammable logic. Moreover, the range of threats to economic, physical and information
security, as well as the list of vulnerabilities in the hardware-software and information
structures of computer systems with a reconstructible structure and programmable logic
is constantly growing [1-4]. Thus, in real life, situations are possible when these threats
are combined and lead to an avalanche-like occurrence and development of negative
events, ultimately resulting in catastrophic consequences. Under these conditions, en-
suring the continuity of technological processes and increasing the reliability and sur-
vivability of the corresponding production systems is one of the most important strate-
gic directions in the development of modern socio-economic and technical complexes.
This is caused by the need to maintain the resilience and stability in the functioning of
computer systems with a reconstructible structure and programmable logic under vari-
ous conditions of adverse effects of external and internal factors, which can be anthro-
pogenic and/or natural.
2 Analysis of known solutions
In practice, when solving the problems of ensuring survivability, computer systems
with a reconstructible structure and programmable logic have received such an option
for managing the structures of computer systems as reconfiguration. The standard (clas-
sical) technology for reconfiguring computer systems with a reconstructible structure
and programmable logic in case of failure of one of its resources includes the following
main steps [5-7].
Step 1. Determination and analysis of the time and place of a resource failure; re-
moval of the function (task) performed on this resource from the solution; transfer of
the function (task) to another resource (with/without saving the obtained intermediate
results).
Step 2. Exclusion of a failed resource from the configuration of computer systems
with a reconstructible structure and programmable logic; an attempt to replace it with
a backup (of the same type), or a backup of a different type with similar functionality.
Step 3. Exclusion of links to a failed resource, denial of access to it and for the
failed resource itself – an attempt to restore it. In case if a high-priority function (task)
has been solved on a failed resource, which, when transferred to other resources, begins
73
to conflict with functions (tasks) assigned to this resource, then, depending on the ser-
vice discipline, the execution of less priority functions (tasks) is interrupted; or simple
removal from the solution. Thus, in the framework of the standard reconfiguration in
case of failures and violations of the correct functioning of the corresponding node in
the computer system in order to maintain the highest priority functions of the specified
object or acceptable operating conditions, they “sacrifice” other functions or part of the
operable elements. In some cases, this reconfiguration is called a “blind” reconfigura-
tion, since during its implementation, as a rule, the following operations are not carried
out: accounting and analysis of the current characteristics of tasks and functions per-
formed in the computer system; analysis and assessment of the current state of the com-
puter system as a whole; operative calculation, evaluation and analysis of the target and
information-technical capabilities of the computer system for a reasonable redistribu-
tion of the functions of a computer system between its operable elements and subsys-
tems. A prerequisite for the implementation of standard reconfiguration technology is
the presence of a multi-level model of the computer system. operability. A possible
graphical description of this model for one of the subsystems (structures) is shown in
Figure 1. In Figure 1, the vertices of the graph are associated with the technical states
(TSs) of a computer system. During operation, its elements can fall into various types
of TSs: a functioning TS, a faulty TS, an operative TS, an inoperative TS, as well as
correct and incorrect functioning. Figure 1 shows the main classes of the computer sys-
tem TSs:
- the class of fully operative and functioning states:
S (u ) {S( u ) }, 1,..., N (u )
.
Elements of this class differ from each other in the level of accumulated deviations
from the norm of performance parameters in certain elements of the computer system;
- the class of partially operative states with the Вth level of efficiency and the yth
number of accumulated deviations. At the same time, it is believed that with an increase
in the index number, the( p )Bth level of the computer system operability will decrease:
S {S By ( p)
}, B 1,..., N1( p ) , y 1,..., N 2( p )
.
In the graph, operability levels are separated by horizontal dashed lines;
- the class of inoperative (failure) states of the computer system caused by the ap-
pearance of the Cth type with the Nth amount of losses:
S ( o ) {SCN
(o)
}, C 1,..., N1( O ) , N 1,..., N 2( O )
.
In Figure, 1 SL is the limit state, i.e. the state, in which all elements of the computer
system are inoperative and the level of losses is maximum.
In this Figure, the arcs of the graph correspond to transitions of the computer system
from one state to another. These transitions, as noted earlier, have a different nature:
some are structurally functional, others are not structurally functional. There exists the
following classification:
- D-transitions, which are caused by failures of elements of a computer system and
its transition into a state with a lower level of performance or a higher amount of losses;
- A-transitions, which are caused by the achievement of the established threshold
values of the accumulated deviations number;
74
- R-transitions, which are caused by partial or complete recovery of the computer
system operability;
- C-transitions, which are caused by compensation of the accumulated deviations in
the parameters of both the elements and the computer system as a whole.
Fig. 1. The graph of evolution of computer system performance with a reconstructible
structure and programmable logic
In Figure 1, D-transitions are depicted by arcs directed from top to bottom; A-tran-
sitions are given by horizontal arcs going from left to right; R-transitions are shown by
arcs going from bottom to top; C-transitions are the arcs from right to left. The dashed
line in Figure 1 marks the boundary between the operational and failure states of a
computer system. Given the above, the dynamics of the computer system operability in
the general case assumes the simultaneous implementation of the following processes
of changing the technical state of both elements of the computer system and the system
as a whole:
- degradation processes (D-processes);
- recovery processes (R-processes); - processes of accumulating parameter devia-
tions (A-processes);
75
- compensation processes of accumulated parameter deviations (C-processes).
In this case, one of the goals of controlling the structural dynamics of computer
systems with a reconstructible structure and programmable logic is to provide the high-
est possible level of operability of a computer system and its elements at every moment
in time. This goal is achieved by two complementary processes. First, by influencing
(controlling) the D-process (degradation) the possibility (probability) of transitions of
the computer system to the least desirable states is eliminated or reduced. Second, it is
done by using the organization (management) of the R-process (recovery) and the C-
process (compensation). To implement these processes both in the computer system
itself and in each of its elements (subsystems), a structural control loop is formed. Due
to this loop, the scheduling processes are realized by reconfiguring computer systems
with a reconstructible structure and programmable logic. Speaking about the possible
classes of tasks for reconfiguring computer systems, one should, first of all, proceed
from the so-called functional-structural approach (FSA) to the description of objects of
any nature (including computer systems). Characteristic of FSA features are:
- considering the dialectical relationship of functions and structure of objects with
the decisive role of the function in relation to the structure;
- a holistic approach to the analysis and synthesis of multi-level systems;
- considering material, energy and information links between elements of the system;
- considering the relationship of the investigated (created) system with the external
environment.
The analysis of problems of reconfiguring computer systems taking into account the
FSA allowed to identify the basic concepts and definitions that are shown in Figure 2.
At the same time, considering various combinations of independent branches of the
given morphological tree, we can obtain a kaleidoscopic set of reconfiguration tasks for
computer systems with a reconstructible structure and programmable logic.
These systems operate in conditions of significant non-stationarity and uncertainty
associated with changes in the content of goals and tasks, which computer systems with
a reconstructible structure and programmable logic face, the influence of disturbing
factors from the external environment and factors having a purposeful and/or unfocused
nature. Moreover, in real life, disturbing environmental factors can be deterministic or
unknown, described using probability-statistical or fuzzy-probable formalisms. In the
process of reconfiguring computer systems with a reconstructible structure and pro-
grammable logic, the following main goals are pursued: preservation, implementation
and restoration of the target and information-technological capabilities of the system.
The implementation of reconfiguration can be carried out simultaneously in several
directions.
76
Fig. 2. The classification of reconfiguration tasks for computer systems with a recon-
structible structure and programmable logic
The "vertical" direction implies the implementation of a reconfiguration of a com-
puter system when it affects two complementary processes. The first one is the process
of computer system degradation in order to eliminate or reduce the possibility of a com-
puter system transferring to the least desirable states. The second one is the recovery
process in order to partially or fully achieve an operable state. The "horizontal" direc-
tion is the impact on the process of accumulating deviations of FE parameters (or the
77
computer system as a whole) and the impact on the process of compensating for accu-
mulated deviations. In addition, the following can be considered as the most essential
morphological features of the process of a computer system reconfiguration: space,
time, resource allocation mode and the formation of control actions. According to the
"space" feature, the variants for reconfiguring a computer system can be distinguished
into local and global. A local variant of reconfiguration of a computer system deals with
individual FEs, sets of FEs and/or individual subsystems of a computer system. In the
case of global reconfiguration, the process relates generally to the entire computer sys-
tem. The "time" classification feature is closely related to the state of the computer
system and its objects during reconfiguration. Static reconfiguration is performed after
the computer system has been interrupted. The main disadvantages of this type of re-
configuration are: - demand to stop the computer system, which entails not only the
shutdown of the computer system, but also the shutdown of the associated service ob-
jects; - reconfiguration of the computer system should be carried out by external means
since in these conditions the internal resources of the computer system cannot be used.
The advantages of the dynamic reconfiguration, which is performed during the opera-
tion of a computer system, are the ability to maintain the operability of its service sub-
systems during the reconfiguration of a computer system and the ability to use its inter-
nal resources and reserves [8-10]. The development of control actions during reconfig-
uration of a computer system can be based on both a priori and a posteriori information
about the behavior of individual FEs and subsystems of a computer system. As for the
options for reallocating the resources of a computer system in the process of its recon-
figuration, the following modes can be distinguished: centralized, decentralized, or a
combination of these modes. In the centralized mode, the allocation of resources is car-
ried out using a unified model that includes both the initial state of the computer system
and all kinds of (most likely) intermediate states caused by destructive influences. In
the decentralized mode, the selection of a resource allocation plan for the initial state
of a computer system is carried out in such a way that subsequent reallocation caused
by adverse effects will allow the rational use of computer system resources. The deter-
mination of optimal control programs for the main elements and subsystems of a com-
puter system can be performed only after the list of functions and algorithms for infor-
mation processing and control becomes known, which should be implemented in these
elements and subsystems [11-16]. In turn, the distribution of functions and algorithms
by elements and subsystems of a computer system depends on the structure and param-
eters of the laws of managing these elements and subsystems. The evolving situation is
closely connected with the principle of the duality of the past and the future. This means
that you can have knowledge about the past, but you cannot control it, and you can
design the future without knowing it.
78
3 Algorithm for solving the problem of constructing a
trajectory for structural reconfiguration of computer systems
with a reconstructible structure and programmable logic
The task of constructing a trajectory for the structure reconfiguration during the deg-
radation or recovery of a computer system with a reconstructible structure and program-
N
mable logic can be represented as the
F following
( x ) optimization
failure min problem:
aj
xa j X ( xa j 1 )
j 0
xa0 x0 , xaN x f ,
l ( xa j ) 0, l 1,2,... L
{Q , Q ,..., Q } Qˆ
j1 j2 jN
. (1)
To solve the considered problem of structural reconfiguration of a computer system,
we use a combined method, which includes the method of random guided search and
cutting off unpromising trajectories for structural reconfiguration of a computer system
using the "branch and bound" method. The random guided search in solving the prob-
lem of scheduling the structural reconfiguration of a computer system can be imple-
mented as follows. When building a random sequence:
( k ) [ xa0 , xa(1k ) , xa(2k ) ,..., xa(Nk )1 , xaN ]
. (2)
of the intermediate states of the trajectory for structural reconfiguration,
we are in some
x (k )
intermediate structural state, which is characterized by the genome a j from which we
can go to one of the states of the next level of the computer system structure degradation
{Q , Q ,..., Qi p } Qˆ
through the failure of one of the operable FE sets: i1 i2 . Moreover, the
a Ffailure ( xir ), r 1,..., p
values r characterize the contributions to the structural failure
upon failure of these FEs. In the general case, ar [ 1,1] . To carry out the guided
search, the interval [0,1] is divided into subintervals so that the coordinates of the ends
of the subintervals form the sequence
0, 1 b1 , 2 1 b2 ,..., p p 1 b p 1
. (3)
p
1 ar (1 a )
br r
where ; r 1 . Here, the smaller the contribution ar to the value
Qir Qˆ
of the structural failure index when the FE is removed , the greater the length
br Q
of the sub-interval is assigned to this element, i.e. the element ir is "encouraged"
by the large sub-interval. For random selection of the FE removed from the structure, a
random number is generated that is distributed uniformly in the interval from 0 to 1,
79
which falls into a certain sub-interval ( r 1 , r ) and thereby determines the selec-
tion of the FE removed from the structure of the computer system. Thus, in accordance
with the constructed probabilistic hypothesis, a search for a global extremum is orga-
nized. In addition, in the vicinity of the global extremum, the density of randomly se-
lected trajectories for a reconfigurable computer system will be the highest. To increase
the efficiency of random guided search, it is proposed for each test to compare the in-
termediate values of the total structural failure indicator obtained on this trajectory of
the computer system reconfiguration with the record value and stop the started test as
soon as the intermediate value of this indicator exceeds the record one. If the specified
number of tests has been carried out, then the calculation is considered complete. The
calculation can be considered complete even if subsequent tests do not provide an im-
provement in the result. Using the proposed approach allows to guarantee the reception
of the trajectory of the computer system structural reconfiguration in a sufficiently
small vicinity of the optimal trajectory. At the same time, the process of finding a so-
lution can be limited both by the time allocated for making a decision, by the produc-
tivity of the used computing tools, and by analyzing the nature of the process of taken
decisions convergence to the optimum. The proposed approach can be implemented in
the form of an algorithm consisting of the following steps.
Step 0. The initial state. We set the number of statistical tests M; the number of tests
d record
that does not give an improvement in the result; current test k = 0; the record
Ffailure
.
Step 1. The beginning of the next test. List of deleted critical FEs
Qˆ {Qi1 , Qi2 ,..., QiN } F 0
; intermediate total structural failure failure .
Step 2. Random selection of the deleted FE. One of the FEs is randomly selected
Q̂ Q
from the list in the manner described above, ( k )let it be ir . The intermediate structural
x ( x ( k ) xa( kj ) )
state of the current trajectory is determined a j a j1 .
xa( kj )
Step#3. Analysis of the intermediate structural state . The structural failure
Ffailure ( xa( kj ) ) Ffailure Ffailure ( xa( kj ) )
and the change in the current total structural failure
F Ffailure
record record
( Ffailure
are calculated. If - failure is the current record), then proceed to Step 5.
Q Q̂
Step 4. Analysis of the list of deleted FEs. FE ir is excluded from the list . If
Q̂ F Ffailure
record
F record
Ffailure
, then the test is over. Moreover, if failure , then failure . If
Q̂
, go to Step 2.
Step 5. record Analysis of test results. If the number of consecutive tests with no results
Ffailure Ffailure
is greater than d, then the procedure ends. If k> M, then the procedure
ends. Otherwise, go to Step 1. The finiteness of the algorithm constructed according to
Qˆ {Qi1 , Qi2 ,..., QiN }
this scheme follows from the finiteness of the set , the finiteness
ofˆ the number of tests M and the sequential deletion of the FEs from the set
Q {Qi1 , Qi2 ,..., QiN }
.
80
4 Conclusions and recommendations
The analysis of the optimization problem features in constructing scenarios for the
structural reconfiguration of computer systems with a reconstructible structure and pro-
grammable logic was carried out. The results have shown that methods and algorithms
of the theory of search engine optimization of evolutionary type should be used to solve
the considered problem. To solve the given problem, the method and the algorithm that
implements this method are proposed, the novelty of which is the combined use of the
random guided search method and the method of cutting off unpromising structural
reconfiguration options for computer systems with a reconstructible structure and pro-
grammable logic such as “branch and bound”. The proposed approach allows solving
the optimization problems of constructing scenarios for the structural reconfiguration
of computer systems with a reconstructible structure and programmable logic, both un-
conditional and conditional, that can be described using various structural and topolog-
ical indicators. At the same time, modification of the proposed method allows the con-
struction of a series of optimistic and pessimistic scenarios for the structural reconfig-
uration of computer systems with a reconstructible structure and programmable logic.
The research has been carried out on the basis of the Educational and Scientific Labor-
atory of “Reconfigurable and Mobile Systems” at the Department of Electronic Com-
puters in Kharkov National University of Radio Electronics.
References
1. Churyumov, G., Tkachov, V., Tokariev, V., Diachenko, V.: Method for Ensuring Surviva-
bility of Flying Ad-hoc Network Based on Structural and Functional Reconfiguration. In:
XVIII International Scientific and Practical Conference «Information Technologies and Se-
curity» (ITS 2018), pp. 64-76. Kyiv, Ukraine (2018).
2. Tkachov, V., Tokariev, V., Dukh, Ya., Volotka, V.: Method of Data Collection in Wireless
Sensor Networks Using Flying Ad Hoc Network. In 5th International Scientific-Practical
Conference Problems of Infocommunications. Science and Technology, pp 197-201,
Kharkiv, Ukraine (2018).
3. Dodono,v A., Gorbachyk, O., Kuznietsova, M.: Management organization of mobile
technical objects group / In: XVII International Scientific and Practical Conference «Infor-
mation Technologies and Security» (ITS 2017), pp. 1-7. Kyiv, Ukraine (2017).
4. Dodonov, A., Gorbachyk, O., Kuznietsova, M.: Increasing the survivability of automated
systems of organizational management as a way to security of critical infrastructures. In:
XVIII International Scientific and Practical Conference «Information Technologies and Se-
curity» (ITS 2018), pp. 261-270. Kyiv, Ukraine (2018).
5. Barabash, O., Kravchenko, Y., Mukhin, V., Kornaga, Y., Leshchenko, O.: Optimization of
Parameters at SDN Technologie Networks. International Journal of Intelligent Systems and
Applications. 9 (9), 1-9 (2017).
6. Lemeshko, O., Yeremenko, O., Tariki, N.: Solution for the Default Gateway Protection
within Fault-Tolerant Routing in an IP Network. International Journal of Electrical and
Computer Engineering Systems. 8 (1), 19–26 (2017).
81
7. Bielievtsov, S., Ruban, I., Smelyakov, K., Sumtsov, D.: Network technology for transmis-
sion of visual information // In: XVIII International Scientific and Practical Conference «In-
formation Technologies and Security» (ITS 2018), pp. 161-275. Kyiv, Ukraine (2018).
8. Pavlov, A.N.: Metodologicheskiye osnovy resheniya problemy planirovaniya struktur-no-
funktsional'noy rekonfiguratsii slozhnykh ob"yektov. Izvestiya Vysshikh Uchebnykh
Zavedeniy. Priborostroyeniye, 55 (11), 7-13.
9. Dodonov, A.G., Kuznetsova, M.G., Gorbachik, Ye.S.: Vvedeniye v Teoriyu Zhivuchesti
Vychis-litel'nykh Sistem, Nauk. Dumka, Kyiv (1990).
10. Dodonov, A.G., Lande, D.V.: Zhivuchest' Informatsionnykh Sistem. Nauk. Dumka, Kyiv
(2011).
11. Dodonov, A.G., Kuznetsova, M.G.: O nekotoroj strategii rekonfiguracii zhivuchih vychis-
litelnyh sistem. Gibridnye vychislitelnye mashiny i kompleksy, 11, 31-35 (1988).
12. Dodonov, A.G., Kuznetsova, M.G.: Raspredelenie resursov v zhivuchih vychislitelnyh siste-
mah. Gibridnye vychislitelnye mashiny i kompleksy, 7, 20-23 (1984).
13. Westmark, V. R.: A definition for information system survivability. In 37th Annual Hawaii
International Conference on System Sciences, p. 10 (2004).
14. Romashkova, O.N., Dedova Ye.V.: Zhivuchest' besprovodnykh setey svyazi v usloviyakh
chrezvychaynoy si-tuatsii. T-Comm: Telekommunikatsii i Transport, 6, 40-43 (2014).
15. Lande, D.V.: Metodi pidvishennya zhivuchosti informacijnoyi skladovoyi korporativnih
informacijno-analitichnih sistem pidtrimki prijnyattya rishen. Reyestraciya, zberigannya i
obrobka danih, 14 (2), 48-58 (2012).
16. Dodonov, A.G., Lande, D.V., Putyatin V.G. Informacijni potoki v globalnih komp'yuternih
merezhah. Naukova dumka, Kyiv (2009).