=Paper=
{{Paper
|id=Vol-2744/short50
|storemode=property
|title=Inter-Machine Exchange of Real Time in Distributed Computer Systems (short paper)
|pdfUrl=https://ceur-ws.org/Vol-2744/short50.pdf
|volume=Vol-2744
|authors=Vladimir Bogatyrev,Stanislav Bogatyrev,Anatoy Bogatyrev
}}
==Inter-Machine Exchange of Real Time in Distributed Computer Systems (short paper)==
https://ceur-ws.org/Vol-2744/short50.pdf
Inter-Machine Exchange of Real Time in Distributed
Computer Systems*
Vladimir Bogatyrev 1,2,3[0000-0003-0213-0223], Stanislav Bogatyrev1[0000-0003-0836-8515],
and Anatoly Bogatyrev1[0000-0001-5447-7275]
1JSC NEO Saint Petersburg Competence Center, St. Petersburg, Russia
anatolyg@nspcc.ru
https://www.nspcc.ru/en
2ITMO University, Saint Petersburg, Russia
vabogatyrev@corp.ifmo.ru
3
Saint-Petersburg State University of Aerospace Instrumentation, Russia
Abstract. The possibilities of increasing the likelihood of timely service and re-
ducing the average waiting time for requests for inter-machine exchange in dis-
tributed real-time computer systems are investigated. The analyzed effect is
achieved as a result of redundant multi-way transmissions of packets that are crit-
ical to delays, which provide for the replication of transmitted packets with the
task for each replica of the path (route) of the sequential passage of network
nodes. The condition for the timeliness of the reserved transmissions is that the
accumulated waiting in the queues of the nodes making up the path, at least for
one of the replicas, does not exceed the maximum permissible time. An analytical
model is proposed for estimating the average delays of multi-path redundant
transmissions, when determined by the average delivery time of the first of the
replicas transmitted in different ways. For requests critical to service delays, the
influence of the frequency of reservation (replication) of requests on the proba-
bility of their timely service and the average waiting time accumulated at the
nodes of the path for the replica delivered first was analyzed.
Keywords: Reservation, Multipath Transfers, Real-time, Average Waiting
Time
1 Introduction
Currently, great interest is shown in ensuring reliability and low latency in data ex-
change networks, these tasks are being addressed, including in the framework of the
concept of Ultrareliable and Low-Latency Wireless Communication [1-4]. The need to
ensure these requirements for distributed processing and data transfer systems,
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).
* Publication supported by RFBR grant №19-07-00844
2 V. Bogatyrev, S. Bogatyrev, A. Bogatyrev
including real-time images, is key. The problem of ensuring reliability and security is
an acute problem for the currently developing cyberphysical systems [5,6].
To reduce the average transmission delays in the network allows transport coding
[7, 8], in which the message is fragmented with the transfer of fragments along different
routes. As a result of encoding fragments with distortion or non-delivery of their parts,
the message can be restored, which allows to reduce the costs associated with organiz-
ing retransmissions of undelivered fragments (but requires complicating the processing
process associated with decoding and restoration of the message).
To reduce the negative impact of failures on the continuity of the computing pro-
cess, reconfiguration is aimed at combining it with the migration of virtual machines
[9,10] in cluster data processing systems [11,12] and multi-path routing in networks
[13,14]. Both of these technologies provide for the creation of reserve resources in order
to quickly restore functioning during reconfiguration after failures. So with multi-path
routing, the main and backup paths (routes) of data transmission are prescribed. After
failures of the nodes of the main path, switching to a predefined backup path is carried
out.
To reduce the average transmission delays in the network allows transport coding
[7, 8], in which the message is fragmented with the transfer of fragments along different
routes. As a result of encoding fragments with distortion or non-delivery of their parts,
the message can be restored, which allows to reduce the costs associated with organiz-
ing retransmissions of undelivered fragments (but requires complicating the processing
process associated with decoding and restoration of the message).
To reduce the negative impact of failures on the continuity of the computing pro-
cess, reconfiguration is aimed at combining it with the migration of virtual machines
[9,10] in cluster data processing systems [11,12] and multi-path routing in networks
[13,14]. Both of these technologies provide for the creation of reserve resources in order
to quickly restore functioning during reconfiguration after failures. So with multi-path
routing, the main and backup paths (routes) of data transmission are prescribed. After
failures of the nodes of the main path, switching to a predefined backup path is carried
out.
A feature of the transmission of images in real time is the provision of delays in
their delivery that do not exceed a certain maximum permissible value, as well as the
fight against the spread of transmission delays (jitter) and their errors, which signifi-
cantly reduce the reliability of communication and the quality of image perception, in-
cluding video streams. To combat transmission errors, various methods are used, the
main of which are noise-immune coding and retransmission schemes, however, the lat-
ter lead to an increase in delays, which leads to the use of protocols in real time without
confirmation of delivery, increasing the timeliness of image transmission by reducing
it reliability.
Real-Time Transport Protocol (RTP) and Resource Reservation Protocol (RSVP)
are aimed at ensuring timely transmissions. RTP supports the timely delivery of data in
real time to one or more subscribers. RSVP allows you to reserve network resources
for the required quality of real-time transmissions over the RTP protocol.
Taking into account the specified specificity of image transmission, its quality is
characterized by such indicators as average delivery delays, variance of delivery delays,
Inter-Machine Exchange of Real Time in Distributed Computer Systems 3
delivery probability, taking into account bit errors of transmissions. For real-time trans-
missions, the key quality indicator is the probability of delivery within the maximum
allowable time.
Reliability and timeliness of query execution in a redundant information and com-
munication system (server cluster or switching nodes) can be improved as a result of
redundant service of copies (replicas) of requests with the issuance of one completed
copy (for example, the first issued in time) [15,16].
Multipath backup service, provides for replication of requests) with the task for each
replica of the path (route) of the sequential passage of nodes, systems [15].
The concept of ensuring the timeliness and reliability of the service under consid-
eration is based on multi-path routing technologies [13,14], multicast transmissions,
and broadcast services [17], dynamic query distribution [18, 19] and clustering [20].
The condition for the success of redundant transmissions is that the accumulated
total waiting in the queues of the nodes making up the path does not exceed the maxi-
mum permissible time for at least one of the copies. The quality indicator of real-time
transmission systems is the probability of timely service of requests for inter-machine
exchange and the average time of implementation of such an exchange [15].
The purpose of the article is to create an analytical model for estimating the average
delays of multi-path redundant transmissions through a sequence of nodes that make
up the paths when determining the required time for delivery of the first of the replicas
transmitted over different paths.
The developed model is designed to assess the effectiveness and determine the fea-
sibility of redundant multi-way transmissions depending on the frequency of their res-
ervation, the intensity of the flow of requests and their criticality to delays in the queues
of nodes making up the reserved paths. Similar problems must be solved in the model-
oriented design of distributed computer systems [21-23], which function in real time,
including distributed image processing and image streaming.
2 Multipath Redundant Transmission Model
Consider a system in which k replicas are created when generating requests for the
transmission of a packet through the network. For each replica, the path of sequential
passage of m network nodes is registered. All paths include the same number of nodes.
When assigning a node to be included in the i-th path, one of the ni nodes is selected.
We represent the nodes of the infocommunication system as single-channel queuing
systems with an infinite queue of type M/M/1 [24, 25]. To simplify the model, we as-
sume that the i-th nodes of all paths are identical as queuing systems.
Taking into account the fact that when passing a certain replica of the next node
included in the path, the margin of the acceptable waiting time decreases on average by
the total average waiting time in the queues of the previous nodes, the probability of
timely delivery when passing all m nodes of the path specified for the replica will be
calculated as
4 V. Bogatyrev, S. Bogatyrev, A. Bogatyrev
k 1 i
wj
kvi ni − vi t0 −
m
P = 1 − e j =1
i =1 ni
where vi is the average transmission time of the packet replica of the i-th node of the
path, t0 -maximum allowed total waiting time for query replicas in the list of all nodes
on the path, Λ is the intensity of the input stream of requests for packet transmission,
kΛ is the intensity of the reserved input stream of requests for transmission of packet
replicas, j = k n j is the intensity of the stream of requests arriving at the j-th node,
and wj is the average timeout for request replicas in it.
jvj2
wj =
1− jvj
The probability of not exceeding the permissible travel time t of all m nodes of the
path, at least for one of the k replicas, provided that the number of nodes included in all
the paths and their characteristics are the same, we calculate as
R = 1 − (1 − P) k
The average delays of multi-path redundant transmissions through a sequence of
communication nodes that make up the paths when determining the desired time for the
first replica delivered from different paths in time
k
− t − w
k 1
i
kvi n v
W = 1 − 1 −
m j
j =1
dt
i i
e
0 i =1 n
i
.
3 Calculation of the Probability-Time Characteristics of
Redundant Transmissions
In the calculations, we will assume that the average request service time at each node
is v = 0.1 s, and the maximum allowable total waiting time in the queues of all nodes
making up the path is t0 = 0.5 s.
In Fig. 1 shows the dependence of the probability of timely reserved service on the
intensity of the input request stream Λ, and Fig. 2 on the multiplicity of reservation
requests. In Fig. 1, with the reservation factor k = 1, 2, 3, curves 1-3 correspond to the
path passing through m = 5 nodes, and curves 4-6 through m = 10 nodes. In Fig. 2,
curves 1-5 represent the intensity of the input request stream Λ = 500, 600, 700, 900,
1000 1/s, respectively, at m = 10. The calculations were performed for ni = n = 5 nodes.
The presented calculations confirm the existence of an optimal multiplicity of
packet reservation critical to the total delay in the queues of the nodes transmitting
them. It can be seen from the graphs that with a reduced load on the system, the recom-
mended multiplicity of reservation of critical to expect packets, at which the maximum
probability of timely delivery of at least one of the packet replicas is achieved, in-
creases.
Inter-Machine Exchange of Real Time in Distributed Computer Systems 5
In Fig. 3 shows the dependence of the average total waiting time in queues of nodes
included in the path, counted until the first replica is delivered along one of the paths,
on the intensity of the input request stream Λ. Fig. 4 shows the dependence of the indi-
cated time on the multiplicity of reservation requests. In Fig. 3, when the request reser-
vation ratio is k = 1, 2, 3, curves 1-3 correspond to the path passing through m = 5
nodes, and curves 4-6 through m = 10 nodes. In Fig. 4, curves 1–5 correspond to path
lengths equal to m = 9, 10, 11, 12, 15 nodes at an input request stream intensity Λ = 1
(1/s). The calculations were performed for ni = n = 5 nodes.
Fig. 1. Dependence of the probability of timely reserved service on the intensity of the input re-
quest stream
Fig. 2. The dependence of the probability of timely redundant service on the frequency of reser-
vation requests
6 V. Bogatyrev, S. Bogatyrev, A. Bogatyrev
Fig. 3. Dependence of the average total waiting time on the intensity of the input request stream
Fig. 4. Dependence of the average total waiting time on the frequency of reservation of requests
The established dependencies confirm the existence of an optimal multiplicity of reser-
vation critical to the total delay in the request queues. The graphs show that with a
decrease in the system load, the recommended redundancy rate at which the maximum
probability of timely service and the minimum total average wait time in queues of
nodes counted until the first replica is delivered along one of the paths is increased.
4 Conclusion
For multi-path redundant transmission systems, an analytical model is proposed for es-
timating the average total waiting time, counted until the first replica is delivered along
one of the paths.
For requests critical to delays in queues, the influence of the frequency of reserva-
tion (replication) of requests on the probability of their timely service and on the aver-
age total delay in waiting for delivery of the first replica of time is analyzed.
The existence of an optimal multiplicity of reservation critical to the total delay in
the request queues is shown.
Inter-Machine Exchange of Real Time in Distributed Computer Systems 7
References
1. Siddiqi1, M., Yu, H., Joung, J. 5G Ultra-Reliable Low-Latency Communication Implemen-
tation Challenges and Operational Issues with IoT Devices Electronics 2019, 8, 981;
doi:10.3390/electronics8090981 www.mdpi.com/journal/electronics
2. Ji, H., Park, S., Yeo, J., Kim, Y., Lee, J., Shim, B. Ultra-Reliable and Low-Latency Com-
munications in 5G Downlink: Physical Layer Aspects. IEEE Wirel. Commun. 2018, 25,
124–130.
3. Sachs, J., Wikström, G., Dudda, T., Baldemair, R., Kittichokechai, K. 5G Radio Network
Design for Ultra-Reliable Low-Latency Communication. IEEE Netw. 2018, 32, 24–31.
4. Bennis, M., Debbah, M., Poor, H.V. Ultrareliable and Low-Latency Wireless Communica-
tion: Tail, Risk and Scale. Proc. IEEE 2018, 106, 1834–1853
5. Zakoldaev, D.A., Gurjanov, A.V., Shukalov, A.V., Zharinov, I.O. Functional safety of
cyber-physical production of the Industry 4.0//IOP Conference Series: Materials Science
and Engineering, 2020, Vol. 734, No. 1, pp. 012110
6. Gurjanov, A.V., Shukalov, A.V., Zakoldaev, D.A., Zharinov, I.O. Develop of reconfigurable
manufacturing plant//Journal of Physics: Conference Series, 2020, Vol. 1515, No. 4, pp.
042060
7. Krouk, E., Semenov, S. Application of Coding at the Network Transport Level to Decrease
the Message Delay // Proc. of 3rd Intern. Symp. on Communication Systems Networks and
Digital Signal Processing. Staffordshire University, UK, 2002. pp. 109—112
8. Kabatiansky, G., Krouk, E., Semenov, S. Error Correcting Coding and Security for Data
Networks. Analysis of the Superchannel Concept. Wiley, 2005. 288 р
9. Sahni, S., Varma, V. A hybrid approach to live migration of virtual machines Proc. IEEE
Int. Conf. on Cloud Computing for Emerging Markets (CCEM 2012) Bengalore India pp
12–16 doi: 10.1109/CCEM.2012.6354587
10. Jin, H, Li, D., Wu, S., Shi, X,, Pan X. Live virtual machine migration with adaptive memory
compression Proc. IEEE International Conference on Cluster Computing (CLUSTER '09).
New Orleans, USA, 2009. Art. 5289170. doi: 10.1109/CLUSTR.2009.5289170
11. Machida, F., Kawato, M., Maeno, Y: Redundant virtual machine placement for fault-toler-
ant consolidated server clusters. In: IEEE Network Operations and Management Sympo-
sium, pp. 32–39. IEEE Press, Osaka (2010), doi: 10.1109/NOMS.2010.5488431.
12. 2020 71-85 Kim, S., Choi, Y. Constraint-aware VM placement in heterogeneous computing
clusters. Cluster Comput 23, 71–85 (2020). https://doi.org/10.1007/s10586-019-02966-6
13. Merindol, P. Improving Load Balancing with Multipath Routing / P. Merindol, J. Pansiot,
S. Cateloin // Proc. of the 17-th International Conference on Computer Communications and
Networks, IEEE ICCCN 2008. – 2008. – P. 54-61.
14. Prasenjit, C., Tuhina, S., Indrajit, B. Fault-tolerant multipath routing scheme for energy ef-
ficient wireless sensor networksInternational Journal of Wireless & Mobile Networks
(IJWMN) Vol. 5, No.2,April 2013 pp 33-45
15. Bogatyrev, V.A., Bogatyrev, S.V., Bogatyrev, A.V. Model and Interaction Efficiency of
Computer Nodes Based on Transfer Reservation at Multipath Routing // Wave Electronics
and its Application in Information and Telecommunication Systems (WECONF 2019) -
2019, pp. 8840647 . doi: 10.1109/WE-CONF.2019.8840647
16. 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
17. Dudin, A.N., Sun, B.: A multiserver MAP/PH/N system with controlled broadcasting by
unreliable servers. Automatic Control and Computer Sciences, No. 5, pp. 32–44 (2009).
8 V. Bogatyrev, S. Bogatyrev, A. Bogatyrev
18. Bogatyrev, V.A. An interval signal method of dynamic interrupt handling with load balanc-
ing Automatic Control and Computer Sciences 2000, 34(6), pp. 51-57
19. Bogatyrev, V.A., Bogatyrev, S.V., Golubev, I.Yu. Optimization and the process of task dis-
tribution between computer system clusters / Automatic Control and Computer Sciences
2012, 46(3), pp. 103-111
20. Bogatyrev, V.A. Fault Tolerance of Clusters Configurations with Direct Connection of Stor-
age Devices // Automatic Control and Computer Sciences - 2011, Vol. 45, No. 6, pp. 330-
337
21. Poymanova, E.D., Tatarnikova, T. M. Models and Methods for Studying Network Traffic.
In 2018 Wave Electronics and its Application in Information and Telecommunication Sys-
tems (WECONF), pp. 1-5 (2018). doi:10.1109 / WECONF.2018.8604470
22. Kutuzov, O., Tatarnikova, T. On the acceleration of simulation modeling. Proceedings of
22nd International Conference on Soft Computing and Measurements, SCM 2019 (2019)
p.45-47. DOI: 10.1109/SCM.2019.8903785
23. Astakhova, T., Verzun, N., Kolbanev, M., Shamin, A. A. Model for estimatingenergy
consumption seen when nodes of ubiquitous sensor networks communicate information to
each other. In Proceedings of the 10th Majorov International Conference on Software
Engineering and Computer Systems, Saint Petersburg, Russia, December 20-21 (2018)
24. Kleinrock, L. Queueing Systems: Volume I – Theory. New York: Wiley Interscience. 1975
p. 417. ISBN 978-0471491101.
25. Kleinrock, L. Queueing Systems: Volume II – Computer Applications. New York: Wiley
Interscience. 1976 p. 576. ISBN 978-0471491118.