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.