The possibilities of increasing the e ciency 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 e ectiveness of the option of redundant request servicing shown for which a copy of the request, executed rst, 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 account 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 prede ned as a sequence of nodes of di erent levels involved in maintenance, is considered as a prototype.
For multi-level cluster systems operating in real-time (especially in the
cyberphysical systems), the reliability of operation is determined not only by the
reliability of the system structure but also by the probability of timely
execution of requests that are critical to service delay [
Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Transport coding [
Reliability and timeliness of query execution can be improved as a result of
redundant servicing of copies of queries with the issuance of the rst serviced
copy [
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
e ectiveness 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 [
By a path is meant a set of nodes whose operability ensures the ful llment 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 scienti c 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 rst 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 [
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
singlechannel queuing systems of the M / M / 1 type with in nite queues [
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 cluster are researched:
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 speci ed with the servers
that execute the request (copy of the request) at each level [
Option S2: When a request is generated by a source, it's k1 copies are created,
distributed for services in k1 rst-level servers. When one of the copies is serviced
at the rst 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 [
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 di erent 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
di erent levels of the cluster may vary [
From [
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 rst 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
[
P = 1 v e( n v1 )t; n
The probability of the rst completion of waiting in the queue of one of the
copies in a time not exceeding t is calculated as [
T0 =
Z 1 [ vk e( nk1 v1 )t]kdt;
n 0 and the average residence time of the request in the cluster until the rst copy of the request arrives from the queue of one of the nodes is calculated as: T = v +
Z 1 0 [ vk e( nk1 v1 )t]kdt;
n T =
v
(1
kv=n)
:
it should be noted that the average residence time of a selected (speci c)
copy of the request in the server node is as [
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: P = (1 v e( n v1 )t)e ( + c)t;
n
The probability of timely execution of an unreserved request, taking into account the possibility of failures, node errors, and calculation errors, is calculated as:
P = (1 v e( n v1 )t)e ( + c)te ( + c+ o)v;
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:
P = 1 [1 (1 v e( n v1 )t)e ( + c)t]k:
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:
P = 1 [1 (1 v e( n v1 )t)e ( + c)te ( + c+ o)v]k:
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 calculations, we assume that the average time of request execution v = 4 10 4s 1, n = 5, and the maximum allowable waiting time is 8 10 4s 1. The dependence of the probability of timely execution P and average time waiting until the rst 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.
The dependence of the probability of the timely execution P and the average wait time until the rst 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 ow 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.
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 [
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 p = X f[1 i=1
t f(k =n1)v1exp( i 0 (v1 1
N bi[1
f(k =n1)v1exp( [1 f(k =n2)v2exp([t0 bi = (1; if i > 1;
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 [
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 ful lling the request in a time not exceeding the speci ed t0, taking into account the variation in the accumulation of service time at di erent 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 replication is carried out at each level and according to the rst result obtained, the speci ed number of copies of the request for execution is generated and distributed 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 nd the probability of timely execution of requests for a two-level cluster as:
N 1 P = X f[1 i=1
t f(k1 =n1)v1exp( i 0 (v1 1
N bi[1
f(k1 =n1)v1exp( [1 f(k2 =n2)v2exp([t0
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 multiplicity ni, the average residence time of the request when creating ki copies of the request when serving it on the i-th as:
m T = Xfvi + 0 [ viki e( nkii v1i )t]ki dtg:
ni
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 rst 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 ow intensities corresponding to = 3.3; 3; 3.5 1=s.
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. An analytic model is proposed for multi-level cluster systems involving the execution of queries by a sequence of redundant nodes, and the e ectiveness 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, including 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 rst in time.
The in uence 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 e ciency 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 e ciency of redundant maintenance with the formation of copies of requests at each cluster level is shown.
The e ciency of redundant maintenance with the formation of a given number of copies of requests and their distribution in the server queue at each level of the cluster is shown.