Improving System Survivability by Path Duplication

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee 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

  1. 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.
  2. Harary F. Graph Theory, Boulder, CO: Westview Press, 1994.
  3. 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
  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
  5. 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
  6. 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
  7. 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

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences