V.L. Olenev1

1 Saint-Petersburg State University of Aerospace Instrumentation (Saint-Petersburg, Russia)

1 Valentin.Olenev@guap.ru

Introduction. Automated routing in networks significantly simplifies and speeds up the designer's work. At present, there are approaches to routing in classical networks, but these methods are not applicable to networks with wormhole routing. A number of methods have been created for forming route lists, but they are not suitable for networks with redundant elements, and wormhole routing is mostly used in fault-tolerant networks.

Purpose of the work is to develop a method for automated routing of deadlock-free routes in networks with wormhole routing, taking into account the main and reserved parts of the network. It is proposed to refine the author's methods used for onboard computer networks. The method is based on the use of graph theory, set theory, algorithms for partitioning cyclic dependencies in a graph, as well as the principles of routing in communication networks.

Results. The route tracking method is an original sequence of actions presented for the first time, and automates the process of tracking of deadlock-free routes in networks with wormhole routing and structural redundancy, moreover, routing tables are automatically built for network configuration. Part of the method is the author's edge orientation algorithm that solves problems with tracking of routes through nodes and the absence of non-functional switches, as well as an original algorithm for constructing acyclic deadlock-free routes, which is distinguished by a simpler implementation and taking into account the "up/down" rules.

Practical relevance. The use of the developed method for tracking of deadlock-free routes in networks with wormhole routing and redundancy simplifies and accelerates the design of specialized networks, due to working with the structure and settings of the network already at the design stage. Automated route tracking is implemented by simple software functions.

Scope of application: The created method is applied within the framework of the SANDS software package for automated design and modeling of on-board networks, and has been tested in real projects for the development of on-board networks of aircraft.

The work was carried out with the financial support of the Ministry of Science and Higher Education of the Russian Federation, agreement No. FSRF-2023-0003, “Fundamental principles for the construction of noise-resistant systems for space and satellite communications, relative navigation, technical vision and aerospace monitoring.”

Olenev V.L. Automatization of deadlock-free routs tracking process for networks with redundancy and wormhole routing. Radiotekhnika. 2026. V. 90. № 1. P. 157−168. DOI: https://doi.org/10.18127/j00338486-202601-15 (In Russian)

1. Bajgutlina I. A., Bojarov M. E., Zamjatin A. Ju. Ispol'zovanie resursov perspektivnoj nizkoorbital'noj sputnikovoj sistemy svjazi «Marafon IoT» dlja organizacii informacionnogo vzaimodejstvija geterogennyh robototehnicheskih kompleksov. Slavjanskij forum. 2024. № 1(43), S. 266-283 (in Russian).
2. Karandashev A. A., Olenev V. L. Jeffektivnye raspredelenija potokov dannyh v bortovyh setjah, Sozvezdie Roskosmosa: traektorija nauki: Materialy II Otraslevoj nauchno-prakticheskoj konferencii. 2023, S. 24-25 (in Russian).
3. Karandashev A. A. Modeli funkcionirovanija special'nyh vychislitel'nyh setej vida (m x n)-reshetki. Naukoemkie tehnologii v kosmicheskih issledovanijah Zemli. 2024. T. 16. № 4. S. 12-23. DOI: 10.36724/2409-5419-2024-16-4-12-23 (in Russian).
4. Olenev V. L. Metodologija formalizovannogo proektirovanija kommunikacionnyh protokolov na osnove setej Petri. Informacija i kosmos. 2022. № 4(2). S. 37-45 (in Russian).
5. Olenev V. L. Avtomaticheskoe postroenie otkazoustojchivyh bortovyh setej. Naukoemkie tehnologii v kosmicheskih issledovanijah Zemli. 2023. T. 15. № 4. S. 4-13. DOI: 10.36724/2409-5419-2023-15-4-4-13 (in Russian).
6. Olenev V. L. Avtomatizirovannoe prokladyvanie bestupikovyh marshrutov v setjah s chervjachnoj kommutaciej. Naukoemkie tehnologii v kosmicheskih issledovanijah Zemli. 2024. T. 16. № 4. S. 41-49. DOI: 10.36724/2409-5419-2024-16-4-41-49 (in Russian).
7. Bal'zhanova B. M., Velikanova L. O. Osnovnye zadachi sozdanija otkazoustojchivyh sistem. Sb. materialov VII Mezhdunar. nauch.-praktich. konf. «Sovremennye strategii i cifrovye transformacii ustojchivogo razvitija obshhestva, obrazovanija i nauki» (Moskva, 10 marta 2023 g.). M.: Izd-vo ALEF. 2023. S. 199-202 (in Russian).
8. Ferrandiz T., Frances F., Fraboul C. Worst-case end-to-end delays evaluation for SpaceWire networks. Discrete Event Dynamic Systems. 2011. V. 21. № 3. P. 339-357.
9. Kobljakova L. V., Gorbachev S. V. Zadachi signalov zhestkogo real'nogo vremeni vo vstroennyh sistemah i bortovyh setjah. Sb. dokl «Nauchnaja sessija GUAP» (Sankt-Peterburg, 12 aprelja 2016 g.). V 3-h chastjah. Ch. 1. Tehnicheskie nauki. SPb: GUAP. 2016. S. 79-87 (in Russian).
10. Shnurenko O.E. Tehnologija MPLS i ee prakticheskoe primenenie. Sborniki konferencij NIC «Sociosfera». 2013. № 23. S. 50-54 (in Russian).
11. SNA Network Implementation Guide Version 2 Release 3. Официальный сайт IBM [Jelektronnyj resurs]. 2014. URL: https://www.ibm.com/docs/en/SSLTBW_2.3.0/pdf/istimp0_v2r3.pdf (data obrashhenija 16.03.2025).
12. Trigub S.N. Rukovodstvo po tehnologijam ob’edinennyh setej. Izd. 4-e. Per. s angl. M.: ID «Vil'jams». 2005. 1040 s. (in Russian).
13. Warnakulasuriya S., Pinkston T. M. Characterization of deadlocks in interconnection networks. 11th International Parallel Processing Symposium. IEEE. 1997. P. 80-86.
14. Duato J., Yalamanchili S., Ni L. M. Interconnection networks: an engineering approach. Morgan Kaufmann. 2003. 600 p.
15. Sancho J., Robles A., Duato J. A new methodology to compute deadlock-free routing tables for irregular networks. Network-Based Parallel Computing. Communication, Architecture, and Applications. 2000. С. 45-60.
16. Rajkumar K. A. Optimizing Up*/Down* Routing By Minimal Paths. International Journal of Computer Applications. 0975–8887. 2010.
    V. 5. № 1, P. 17-20.
17. Camarero C., Cano A., Martínez C., Beivide R. Achieving High-Performance Fault-Tolerant Routing in HyperX Interconnection Networks. Proceedings of the SC'24 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis. 2024. P. 472–483. DOI: 10.1109/SCW63240.2024.00069.
18. Olenev V. L. Analysis of requirements for modern spacecraft onboard network protocols. Informacionno-upravljajushhie sistemy. 2021. № 1. S. 8–16. DOI: 10.31799/1684-8853-2021-1-8-16 (in Russian).
19. Lavrovskaja I. Ja., Olenev V. L. Transformacija seti dlja povyshenija otkazoustojchivosti v bortovyh setjah Spacewire. Sb. dokladov «Nauchnaja sessija GUAP» Sankt-Peterburg (9–13 aprelja 2018 g.). V 3-h chastjah. T. 1. SPb: GUAP. 2018. S. 157-167 (in Russian).
20. Krishnan P. Design and Analysis of a Dynamic Spacewire Routing Protocol for Reconfigurable and Distributed on-Board Computing Systems. 2019. 69 p.
21. Parkes S., Ferrer Florit A., Gonzalez-Villafranca A., McClements C., McLaren D. SpaceFibre Network and Routing Switch. 2017 IEEE Aerospace Conference. 2017. P. 1-7. DOI: 10.1109/AERO.2017.7943805.