Email this article Improving System Survivability by Path Duplication
- Authors: Burdonov I.B.1, Yevtushenko N.V.1,2, Kossatchev A.S.1
-
Affiliations:
- Institute for System Programming of the Russian Academy of Sciences
- National Research University Higher School of Economics
- Issue: No 4 (2025)
- Pages: 11-32
- Section: PARALLEL AND DISTRIBUTED SOFTWARE
- URL: https://journal-vniispk.ru/0132-3474/article/view/349250
- DOI: https://doi.org/10.7868/S3034584725040027
- ID: 349250
Cite item
Open Access
Access granted
Subscription Access
Abstract
In this paper, the problem of the distributed network survivability is investigated. A distributed system is modeled by a finite connected undirected graph whose nodes are divided into two types: hosts and switches. Hosts perform computational functions, while switches are utilized for providing the message delivery between hosts. The system survivability is considered as the system ability to perform the main functions of message transmission after graph edges’ failures. The solution for the system survivability is provided by duplicating the paths for message transmitting. The main condition for the correct solution is the absence of message looping in the network for any set of selected paths. The four-path theorem is proved for the case of two recipient hosts: if for each recipient host there are two paths from the sending host and the edge sets traversed by these paths are disjoint, then there is no message looping for this set of the paths.
About the authors
I. B. Burdonov
Institute for System Programming of the Russian Academy of Sciences
Email: igor@ispras.ru
25 Alexander Solzhenitsyn st., Moscow, 109004, Russia
N. V. Yevtushenko
Institute for System Programming of the Russian Academy of Sciences; National Research University Higher School of Economics
Email: evtushenko@ispras.ru
25 Alexander Solzhenitsyn st., Moscow, 109004, Russia; 20 Myasnitskaya st., Moscow, 101000, Russia
A. S. Kossatchev
Institute for System Programming of the Russian Academy of Sciences
Email: kos@ispras.ru
25 Alexander Solzhenitsyn st., Moscow, 109004, Russia
References
- Golub B.V., Kuznetsov E.M., Maksimov R.V. Method for estimation of vitality of allocated information systems, Vestn. Samar. Gos. Univ., Estestvennonauchn. Ser., 2014, no. 7, pp. 221–232.
- Harary F. Graph Theory, Boulder, CO: Westview Press, 1994.
- Burdonov I.B., Evtushenko N.V., Kossatchev A.S. Testing switch rules in software defined networks, Trudy Instituta Sistemnogo Programmirovaniya Rossiiskoi Akademii Nauk, 2018, vol. 30, no. 6, pp. 69–88. https://doi.org / 10.15514 / ispras-2018-30(6)-4
- Burdonov I.B., Kossachev A., Yevtushenko N., López J., Kushik N., Zeghlache D. Verifying SDN data path requests, arXiv Preprint, 2019. https://doi.org / 10.48550 / arXiv.1906.03101
- Burdonov I., Yevtushenko N., Kossachev A. Implementing a virtual network on the SDN data plane, Proceedings 2020 IEEE East-West Design & Test Symposium (EWDTS), Varna, Bulgaria, 2020, IEEE, 2020, pp. 279–283. ISBN: 978-1-7281-9898-9. https://doi.org / 10.1109 / EWDTS50664.2020.9224987I
- Burdonov I., Kossachev A., Yevtushenko N., López J., Kushik N., Zeghlache D. Preventive modelbased verification and repairing for SDN requests, Proceedings of the 16th International Conference on Evaluation of Novel Approaches to Software Engineering – ENASE, Ali, R., Kaindl H., and Maciaszek L., Eds., 2021, vol. 1, pp. 421–428. https://doi.org / 10.5220/0010494504210428 ISBN: 978-989-758-508-1
- Nash-Williams C.St.J.A. Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 1961, vols. s1–36, no. 1, pp. 445–450. https://doi.org / 10.1112 / jlms / s1-36.1.445
Supplementary files
