=Paper=
{{Paper
|id=Vol-2590/paper23
|storemode=property
|title=Timely Redundant Service of Requests by a Sequence of Cluster
|pdfUrl=https://ceur-ws.org/Vol-2590/paper23.pdf
|volume=Vol-2590
|authors=Vladimir Bogatyrev,Stanislav Bogatyrev,Anatoly Bogatyrev
|dblpUrl=https://dblp.org/rec/conf/micsecs/BogatyrevBB19
}}
==Timely Redundant Service of Requests by a Sequence of Cluster==
https://ceur-ws.org/Vol-2590/paper23.pdf
Timely Redundant Service of Requests by a
Sequence of Cluster
Vladimir Bogatyrev1,2,3[0000−0003−0213−0223] , Stanislav
1[0000−0003−0836−8515]
Bogatyrev , and Anatoly Bogatyrev1[0000−0001−5447−7275]
1
JSC NEO Saint Petersburg Competence Center, St. Petersburg, Russia
{info,stanislav,anatoly}@nspcc.ru
https://www.nspcc.ru/en
2
ITMO University, Saint Petersburg, Russia
vabogatyrev@corp.ifmo.ru
3
Saint-Petersburg State University of Aerospace Instrumentation, Russia
Abstract. The possibilities of increasing the efficiency of the redundant
service of latency-critical requests by a sequence of nodes of a multilevel
cluster have been investigated. The analytic model is proposed, and the
effectiveness of the option of redundant request servicing shown for which
a copy of the request, executed first, is transferred for redundant service
to the next cluster level, the remaining copies are destroyed.
The novelty of the proposed model is that it allows to taking into ac-
count the requirements of not exceeding the maximum permissible total
accumulated waiting time for sequential redundant request servicing at
all levels of the system.
A variant for which a certain number of copies are created during the
formation of the request, for each of which a path is predefined as a se-
quence of nodes of different levels involved in maintenance, is considered
as a prototype.
Keywords: Redundant service · Criticality of latency requests· Multi-
level cluster· Distribution of requests.
1 Introduction
For multi-level cluster systems operating in real-time (especially in the cyber-
physical systems), the reliability of operation is determined not only by the
reliability of the system structure but also by the probability of timely execu-
tion of requests that are critical to service delay [1-4]. Providing timely execution
of critical requests can be based on traffic prioritization [5-7] and load balancing
[8-9].
Copyright c 2019 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
2 V. Bogatyrev, S. Bogatyrev. A. Bogatyrev
Transport coding [10, 11] reduces the average network delay of message trans-
missions, in which message fragments are transmitted along different routes, and
as a result of encoding (information redundancy), even with the loss or delivery
of part of the message with errors, it is possible to recover the entire message
without retransmissions.
Reliability and timeliness of query execution can be improved as a result of
redundant servicing of copies of queries with the issuance of the first serviced
copy [12,14], the study of these capabilities in clusters, and multi-path transmis-
sion systems with redundant communication channels [15].
The redundant service of the request is considered successful if at least one
copy of it is executed correctly without exceeding the maximum permissible
total waiting time in the queues of the nodes that successively execute it. The
effectiveness of redundant maintenance for multi-level systems is estimated by
the probability of the timeliness of multi-stage maintenance (passing through all
nodes making up the path) of at least one copy of the request [12-14].
By a path is meant a set of nodes whose operability ensures the fulfillment
of a functional task of sequentially servicing a request. The path is active if the
nodes included in it are involved in servicing the request or its copies. Potentially
possible paths that are not used in executing generated copies of the request
relate to backup paths.
The aim of the article is research the possibility of increasing the probability
of timely servicing of redundant requests during their successful passage through
the nodes of the cluster at all levels, taking into account the accumulation of the
waiting time at each level. Reducing delays is achieved as a result of redundant
servicing of copies of delay-critical requests.
The scientific novelty of this study is to build an analytic model of redundant
query servicing by a sequence of clusters, with the requirement not to exceed
the maximum permissible total waiting time in the queues of the nodes of the
copies of the requests, the first in time performed at each level of the cluster.
The relevance of the research of the guaranteed stability of the functioning
of distributed computer systems in real time is due to the active implementation
of the technology of cyberphysical systems at the present stage of development,
including those built on the basis of the Internet of Things technology [16-19].
2 Options for the formation of the path for redundant
requests service in a multi-level cluster
As the object of research consider m levels computer cluster comprising at i-th
level of ni parallel-connected servers, each of them can be represented as single-
channel queuing systems of the M / M / 1 type with infinite queues [20, 21].
In a multi-level cluster, the request is serviced sequentially by servers of all
levels included in the request service path. With redundant maintenance at each
level, multiple copies of the request are executed.
The following options for organizing redundant services in a multi-level clus-
ter are researched:
Timely Redundant Service of Requests by a Sequence of Cluster 3
Option S1 : k copies of request (replicas) are created in the node of the request
source, and for each copy, the service path (route) is specified with the servers
that execute the request (copy of the request) at each level [14].
Option S2 : When a request is generated by a source, it’s k1 copies are created,
distributed for services in k1 first-level servers. When one of the copies is serviced
at the first level, k2 copies of requests are created, which are transferred to
services in selected k2 next-level servers, and so on, until the request is serviced
all m levels of the cluster [14].
For option S1 : k paths of request execution are generated from the source,
the change of which, as well as the multiplicity of backup copies, does not occur
during sequential servicing of the request. The number of copies of requests
(redundancy ratio) at different levels is the same. If the number of redundant
service paths generated when a request arrives in the system is greater than the
multiplicity of structural reservation of nodes at any level, then several copies of
the request are sequentially serviced.
For option S2 : request servicing paths are dynamically formed during the
transfer of a request between cluster levels. The multiplicity of backup copies at
different levels of the cluster may vary [14].
From [14], an analytic model of redundant request servicing by a sequence of
clusters is known, when the maximum allowable waiting time is set for nodes at
each level. Copies of requests whose waiting time is longer than the maximum
set for server nodes at each level are destroyed.
In this paper, we set the task of constructing a new model that allows us
to take into account the requirements of not exceeding the maximum allowable
accumulated waiting time for sequential redundant request servicing at all levels
of the system, including for service option S2 , when generating replica requests
distributed for servicing to cluster servers (i + 1) level is implemented by the
first completed copy of the request at the i-th level.
3 Redundant service in a cluster of n parallel-connected
servers
The probability that the queue request is shorter than the time t is calculated as
[16, 17] in a cluster of n parallel connected servers with an input stream intensity
Λ and average query execution time v:
Λv ( Λ − 1 )t
P =1− e n v ,
n
The probability of the first completion of waiting in the queue of one of the
copies in a time not exceeding t is calculated as [14] for redundant servicing of
requests with multiplicity k (formations of k copies of requests sent to different
servers in the cluster):
Λkv ( Λk − 1 )t k
P =1−[ e n v ] .(1)
n
4 V. Bogatyrev, S. Bogatyrev. A. Bogatyrev
and the average time of the first time to complete waiting for a copy of a
request in at least one of the k cluster servers that receive copies of the request
in the queue is defined as [14]:
Z ∞
Λvk ( Λk1 − 1 )t k
T0 = [ e n v ] dt,
0 n
and the average residence time of the request in the cluster until the first
copy of the request arrives from the queue of one of the nodes is calculated as:
Z ∞
Λvk ( Λk1 − 1 )t k
T =v+ [ e n v ] dt,
0 n
it should be noted that the average residence time of a selected (specific)
copy of the request in the server node is as [20, 21]
v
T = .
(1 − Λkv/n)
The probability of a server failure or failure during the waiting time t is
estimated as r = e−(λ+λc )t , where λ, λc are intensity of server failures and errors.
Then the probability of timely execution of an unreserved request, taking into
account the impact of failures and errors of nodes we calculate as:
Λv ( Λ − 1 )t −(λ+λc )t
P = (1 − e n v )e ,
n
The probability of timely execution of an unreserved request, taking into ac-
count the possibility of failures, node errors, and calculation errors, is calculated
as:
Λv ( Λ − 1 )t −(λ+λc )t −(λ+λc +λo )v
P = (1 − e n v )e e ,
n
where λo is the error rate over time v the server executes the requests.
For the initial state of readiness of all n nodes of the cluster, the probability
of waiting for at least one of k reserved copies of the request in the server queue
for a time less than t will be found as:
Λv ( Λ − 1 )t −(λ+λc )t k
P = 1 − [1 − (1 − e n v )e ] .
n
The probability of timely and error-free redundant service in a cluster of at
least one of k formed copies of the request is calculated as:
Λv ( Λ − 1 )t −(λ+λc )t −(λ+λc +λo )v k
P = 1 − [1 − (1 − e n v )e e ] .
n
The example of calculating the probability of timely execution of reserved
requests and the average time for their waiting is presented below. In the calcu-
lations, we assume that the average time of request execution v = 4 · 10−4 s−1 ,
n = 5, and the maximum allowable waiting time is 8 · 10−4 s−1 . The dependence
of the probability of timely execution P and average time waiting until the first
Timely Redundant Service of Requests by a Sequence of Cluster 5
execution of at least one of k copies of requests from the input stream intensity
Λ is presented in Fig. 5 and Fig. 6, respectively. In the graphs below, curves 1,
2, 3 correspond to the multiplicity of reservation requests k = 1, 2, 3.
Fig. 1. The dependence of the probability of the timely execution of P on the intensity
of the input stream Λ.
The dependence of the probability of the timely execution P and the average
wait time until the first execution of at least one of the k copies of the request
from the multiplicity of reservation requests is shown in Fig. 3 and Fig. 4 are
presented in Fig. 1 and Fig. 2, respectively. In the presented graphs, curves 1,2,3
correspond to the input flow intensity Λ = 1500, 2000, 2200 1/s
The presented dependencies allow us to conclude that there is an area of
expediency of redundant servicing of requests, depending on the intensity of
their receipt.
4 Redundant service with the preliminary formation of
service paths according to option S1
The servers will be presented in the form of single-channel queuing systems of
the M / M / 1 type with endless queues [20, 21]. The probability of a request
in a multi-level cluster is determined in accordance with [12] for the option of
redundant service S1 . Maximum allowable total time of waiting requests in the
queues of nodes at all levels of the system t0 is divided into N intervals, the
6 V. Bogatyrev, S. Bogatyrev. A. Bogatyrev
Fig. 2. Dependence of the average waiting time before the first execution of at least
one of the k copies of the request on the input stream intensity Λ.
Fig. 3. Dependence of the probability of timely execution of the request P on its
reservation ratio.
Timely Redundant Service of Requests by a Sequence of Cluster 7
Fig. 4. Dependence of the average waiting time before the first execution of at least
one of the k copies of the request on the multiplicity of reservation requests.
duration of which is equal to t = t0 /N . Let us single out the moments of the
beginning of the countdown of the waiting intervals i = 0, 1, ..., N −1. For the first
level, the intervals i = 0, 1, .., N −1 are counted, for the second level, the intervals
j = 0, 1, .., N − 1 − i are counted (taking into account the already accumulated
expectations), for the third level - intervals d = 0, 1, .., N − 1 − i1 − i2 and so on
[12]. Thus, the remaining acceptable wait time in the queue of the node serving
the request will be th = t0 − (i0 + i1 + ... + ih−1 )t0 /N . For a two-level system, we
assume that given are the average query execution time as v1 , v2 in nodes n1 , n2
of the corresponding levels.
The probability of not exceeding the maximum permissible total waiting time
in queues of all levels t0 for each of k assigned paths of redundant execution of
one copy of the request for a two-level cluster is calculated as:
N −1
X t0 −1
p= {[1 − {(kΛ/n1 )v1 exp(−i (v − (kΛ/n1 )))}]−
i=1
N 1
t0
−bi [1 − {(kΛ/n1 )v1 exp(− (i − 1)(v1−1 − (kΛ/n1 )))}]×
N
t0
×[1 − {(kΛ/n2 )v2 exp([t0 − i ](v2−1 − (kΛ/n2 )))}]},
N
where
8 V. Bogatyrev, S. Bogatyrev. A. Bogatyrev
(
1, if i > 1,
bi =
0, if i = 1.
A request is considered to be completed in a timely manner if the total
waiting time in queues during the sequential passage of all servers for at least one
assigned path does not exceed the maximum permissible time t0 for redundant
request servicing with reservation ratio k according to service option S1 . Thus,
the probability of timely redundant service according to option S1 is calculated
as [12]
P = 1 − (1 − p)k .
5 Redundant service with the formation of copies of
requests at each cluster level according to option S2
The probability of fulfilling the request in a time not exceeding the specified t0 ,
taking into account the variation in the accumulation of service time at different
levels of the cluster when organizing redundant service according to option S2 ,
will be estimated below.
For redundant service according to option S2 , in contrast to S1 , service repli-
cation is carried out at each level and according to the first result obtained,
the specified number of copies of the request for execution is generated and dis-
tributed to the servers of the next cluster level. Considering that the probability
of tinning for a time not exceeding t for at least one of k replicas of a request
is calculated according to (1), we find the probability of timely execution of
requests for a two-level cluster as:
N −1
X t0 −1
P = {[1 − {(k1 Λ/n1 )v1 exp(−i (v − (ki Λ/n1 )))}k1 ]−
i=1
N 1
t0
−bi [1 − {(k1 Λ/n1 )v1 exp(− (i − 1)(v1−1 − (k1 Λ/n1 )))}k1 ]×
N
t0
×[1 − {(k2 Λ/n2 )v2 exp([t0 − i ](v2−1 − (k2 Λ/n2 )))}k1 ]}.
N
For option S2 of the redundant service of the m level cluster, the servers of
which are structurally redundant at the i-th level (i = 1, 2, ..., m) with multi-
plicity ni , the average residence time of the request when creating ki copies of
the request when serving it on the i-th as:
m Z ∞
X Λvi ki ( Λk i − 1 )t
T = {vi + [ e ni vi ]ki dt}.
i=1 0 ni
Timely Redundant Service of Requests by a Sequence of Cluster 9
6 The results of calculations and comparison of
redundant service options
In the calculations, we assume that the number of reserved servers at each level
is the same and equal to n = 8, the average request execution times for servers
of the first and second level are v1 = v2 = 0.4s, and the total allowable wait
time is t0 = 0.2s.
In Fig. 5 shows the dependences of the probabilities of timely service in a
two-level cluster on the intensity of the input request stream Λ. In Fig. 1, curve
1 corresponds to non-redundant service k = 1, curves 2-3 correspond to service
option S1 with a request reservation ratio of k = 2, 3, and curves 4, 5 correspond
to option S2 with a reservation ratio of k = 2, 3.
Fig. 6 shows the dependences of the probability of timely service of requests
on the multiplicity of their reservation (number of generated copies) k. In Fig.
2, curves 1-3 represent service option S1 , and curves 4-6 option S2 for request
flow intensities corresponding to = 3.3; 3; 3.5 1/s.
Fig. 5. Dependences of the probabilities of timely service in a two-level cluster on the
intensity of the input request stream Λ.
The above graphs allow concluding that there is an optimal multiplicity of
redundant service, and the smaller the system load and the permissible total
waiting time, the greater the redundancy rate at which the maximum probability
of multi-stage service timeliness is achieved. The calculations show that the
option of redundant service S2 allows increasing the probability of timely service
requests.
10 V. Bogatyrev, S. Bogatyrev. A. Bogatyrev
Fig. 6. shows the dependences of the probability of timely service requests on the
frequency of their reservation.
7 Conclusion
An analytic model is proposed for multi-level cluster systems involving the exe-
cution of queries by a sequence of redundant nodes, and the effectiveness of the
options for redundant query servicing critical for queue latency is determined.
The novelty of the proposed model is that it allows you to take into account
the requirements of not exceeding the maximum allowable accumulated waiting
time for sequential redundant request servicing at all levels of the system, in-
cluding for the service option when generating replicas of the request distributed
to the redundant service in the cluster servers each level, is implemented by a
copy of the request made by the servers of the previous level first in time.
The influence of the redundant service multiplicity on the probability of
timely query execution, taking into account sequential redundant execution in
servers at all levels of the cluster, is analyzed.
The existence of the efficiency domain of redundant request servicing and
the optimal frequency of their reservation depending on the system load and
restrictions on the allowable waiting time in queues is shown. The efficiency of
redundant maintenance with the formation of copies of requests at each cluster
level is shown.
The efficiency of redundant maintenance with the formation of a given num-
ber of copies of requests and their distribution in the server queue at each level
of the cluster is shown.
References
1. Sorin D. Fault Tolerant Computer Architecture. Morgan & Claypool 2009. 103 p.
Timely Redundant Service of Requests by a Sequence of Cluster 11
2. Koren I.Fault tolerant systems. Morgan Kaufmann publications, visit our San Fran-
cisco 2009. 378 p.
3. Kutuzov O. I., Tatarnikova T. M. Model of a self-similar traffic generator and evalu-
ation of buffer storage for classical and fractal queuing system. In Moscow Workshop
on Electronic and Networking Technologies, MWENT 2018 - Proceedings 1, pp. 1-3
(2018).
4. Tatarnikova, T. M., Dziubenko, I. N. Wireless Sensor Network Clustering Model. In
2018 Wave Electronics and its Application in Information and Telecommunication
Systems (WECONF), pp. 14 (2018).
5. Astakhova, T., Verzun, N., Kolbanev, M., Shamin, A. A model for estimatingenergy
consumption seen when nodes of ubiquitous sensor networks communicate informa-
tion to each other. In Proceedings of the 10th Majorov International Conference on
Software Engineering and Computer Systems, Saint Petersburg, Russia, December
20-21 (2018).
6. Astakhova, T. N., Verzun, N. A., Kasatkin, V. V., Kolbanev, M. O., Shamin, A. A.
Sensor network connectivity models. Informatsionno-upravliaiushchie sistemy, no.
5, pp. 3850 (2019). https://doi.org/: (10.31799/1684- 8853-2019-5-38-50).
7. Aliev, T.I.: The synthesis of service discipline in systems with limits. Communica-
tions in Computer and Information Science, IET, vol. 601, pp. 151-156 (2016).
8. Dudin, A.N., Sun, B.: A multiserver MAP/PH/N system with controlled broad-
casting by unreliable servers. Automatic Control and Computer Sciences, No. 5, pp.
3244 (2009).
9. Prasenjit Chanak, Tuhina Samanta, Indrajit Banerjee Fault-tolerant multipath
routing scheme for energy efficient wireless sensor networks. International Journal
of Wireless & Mobile Networks (IJWMN) Vol. 5, No.2,April 2013 p 33-45.
10. Kabatiansky G., Krouk E., Semenov S. Error Correcting Coding and Security for
Data Networks. Analysis of the Superchannel Conc ept. Wiley, 2005. 288 .
11. Krouk E., SemenovS. Application of Coding at the Network Transport Level to
Decrease the Message Delay // Proc. of 3rd Intern. Symp. on Communication Sys-
tems Networks and Digital Signal Processing. Staffordshire University, UK, 2002.
P. 109112.
12. 12. Bogatyrev A.V., Bogatyrev S.V., Bogatyrev V.A. Analysis of the Timeliness of
Redundant Service in the System of the Parallel-Series Connection of Nodes with
Unlimited Queues // 2018 Wave Electronics and its Application in Information and
Telecommunication Systems (WECONF) 2018.
13. A. V. Bogatyrev, V. A. Bogatyrev and S. V. Bogatyrev, Multipath Redundant
Transmission with Packet Segmentation, 2019 Wave Electronics and its Applica-
tion in Information and Telecommunication Systems (WECONF), Saint-Petersburg,
Russia, 2019, pp. 1-4. doi: 10.1109/WECONF.2019.8840643.
14. V. A. Bogatyrev, S. V. Bogatyrev and A. V. Bogatyrev, Model and Interac-
tion Efciency of Computer Nodes Based on Transfer Reservation at Multipath
Routing,2019 Wave Electronics and its Appli-cation in Information and Telecom-
munication Systems (WECONF), Saint-Petersburg, Russia, 2019, pp. 1-4. doi:
10.1109/WE-CONF.2019.8840647.
15. Bogatyrev V.A., Parshutina S.A. Redundant Distribution of Requests Through
the Network by Transferring Them Over Multiple Paths // Communications in
Computer and Information Science - 2016, Vol. 601, pp. 199-207.
16. Zakoldaev, D.A., Korobeynikov, A.G., Shukalov, A.V., Zharinov, I.O. Work-
stations Industry 4.0 for instrument manufacturing //IOP Conf. Series: Mate-
rials Science and Engineering665 (2019) 012015IOP Publishingdoi:10.1088/1757-
899X/665/1/012015.
12 V. Bogatyrev, S. Bogatyrev. A. Bogatyrev
17. Zakoldaev D.A., Korobeynikov A.G., Shukalov A.V., Zharinov I.O. Cyber and
physical systems technology classification for production activity of the Industry
4.0 smart factory//IOP Conference Series: Materials Science and Engineering, 2019,
Vol. 582, No. 1, pp. 012007.
18. Zakoldaev D.A., Gurjanov A.V., Shukalov A.V., Zharinov I.O. Classification of cy-
ber and physical systems of Industry 4.0//IOP Conference Series: Materials Science
and Engineering, 2019, Vol. 582, No. 1, pp. 012008.
19. Bogatyrev V.A. Increasing the fault tolerance of a multi-trunk channel by means
of inter-trunk packet forwarding (1999) Automatic Control and Computer Sciences,
33 (2) , pp. 70- 76.
20. Kleinrock, L). Queueing Systems: Volume I Theory. New York: Wiley Interscience.
1975 p. 417. ISBN 978-0471491101.
21. Kleinrock, L. Queueing Systems: Volume II Computer Applications. New York:
Wiley Interscience. 1976 p. 576. ISBN 978-0471491118.