Multipath routing in networks with accelerated message delivery

Kolesov N.V., Gruzlikov A.M., Litunenko E.G., Tiulnikov V.S. Multipath routing in networks with accelerated message delivery. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2026, vol. 26, no. 1, pp. 207–213 (in Russian). doi: 10.17586/2226-1494-2026-26-1-207-213

This article examines the geography-aware class of telecommunication networks with mobile nodes. Their defining feature is that each network device knows the geographic coordinates of all other devices and, consequently, is fully aware of the network graph. The aim of this work is to develop a technique for constructing a set of message transmission paths with subsequent placement of messages across these paths. A multipath routing technique is introduced, featuring a procedure for finding a set of paths within the network that connect the message source to the target node. This procedure is based on a modified Dijkstra’s algorithm for determining the shortest path in a directed graph. A method for constructing additional paths is described, which utilizes both the minimum path length criterion and the criterion of minimum intersections with the original shortest path. To accelerate message delivery, the proposed routing technique involves a preliminary ordering of the output message queue based on optimal scheduling rules. The optimality criterion is the minimization of total message delivery time. These rules are formulated for various scenarios involving the presence of pre-partially ordered and unordered message groups within the queue. The process concludes with a procedure for placing the ordered queue onto the set of information transmission paths. The proposed technique is exemplified by transmitting a message queue containing three pre-ordered groups. The difference in the resulting orderings is demonstrated for cases where preemptions are prohibited and where they are allowed. The feasibility of applying the proposed technique is determined by the performance of the device onboard processor, which is assumed to be a priori sufficient in the case of an autonomous unmanned underwater vehicle.

1. Hentati A.I., Fourati L.C. Comprehensive survey of UAVs communication networks. Computer Standards and Interfaces, 2020, vol. 72, pp. 103451. https://doi.org/10.1016/j.csi.2020.103451

2. Inzartcev A.V., Kiselev L.V., Kostenko V.V., Matvienko Iu.V., Pavin A.M., Shcherbatiuk A F Underwater Robotics: Systems, Technologies, Application. Vladivostok, FGBUN Institut problem morskih tehnologij DVO RAN, 2018, 368 p. (in Russian)

3. Frank M., Ovchinnikov K. Design parameters of unmanned vessels: retrospective analysis. Transactions of the Krylov state research centre, 2020, no. S2, pp. 160–164. (in Russian). https://doi.org/10.24937/2542-2324-2020-2-S-I-160-164

4. Kulagin G.I. Analysis of features and methods for data delivery routes determination in the wireless self-organizing networks based on the unmanned aerial vehicles. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering, 2023, no. 1 (142), pp. 60--82 (in Russian). https://doi.org/10.18698/0236-3933-2023-1-60-82

5. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. McGraw-Hill, 2001, 1056 p.

6. Kuznetsov K.A., Paramonov A.I., Muthanna A.S.A., Kucheryavy A.E. Model and methods of traffic routing in a communication network using UAVs. Proceedings of Telecommunication Universities, 2024, vol. 10, no. 4, pp. 62-72. (in Russian). https://doi.org/10.31854/1813-324X-2024-10-4-62-72

7. Eremenko A.S. A flow-oriented model of multipath routing along disjoint paths in a telecommunications network. Problems of Telecommunications, 2015, no. 1 (16), pp. 85–93. (in Russian)

8. Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Control of multipath transmissions in the nodes of switching segments of reserved paths. Proc. of the International Conference on Information, Control, and Communication Technologies (ICCT), 2022, pp. 1–5. https://doi.org/10.1109/icct56057.2022.9976839

9. Zuo Y., Ling Z., Yuan Y. A hybrid multi-path routing algorithm for industrial wireless mesh networks. Eurasip Journal on Wireless Communications and Networking, 2013, vol. 2013, pp. 82. https://doi.org/10.1186/1687-1499-2013-82

10. Venkatesh K., Srinivas L.N.B., Krishnan M.B., Shanthini A. QoS improvisation of delay sensitive communication using SDN based multipath routing for medical applications. Future Generation Computer Systems, 2019, vol. 93, pp. 256–265. https://doi.org/10.1016/j.future.2018.10.032

11. Ducatelle F., Di Caro G., Gambardella L.M. Ant agents for hybrid multipath routing in mobile ad hoc networks. Proc. of the 2^ndAnnual Conference on Wireless On-demand Network Systems and Services, 2005, pp. 44–53. https://doi.org/10.1109/wons.2005.3

12. Sahhaf S., Tavernier W., Colle D., Pickavet M. Adaptive and reliable multipath provisioning for media transfer in SDN-based overlay networks. Computer Communications, 2017, vol. 106, pp. 107–116. https://doi.org/10.1016/j.comcom.2017.03.002

13. Koryachko V.P., Perepelkin D.A. Development and research of the mathematical model multipath adaptive routing in telecommunication networks with load balancing. Elektrosvjaz', 2014, no. 12, pp. 27–31. (in Russian)

14. Rajasekaran K., Balasubramanian K. Energy conscious based multipath routing algorithm in WSN. International Journal of Computer Network and Information Security (IJCNIS), 2016, vol. 8, no. 1, pp. 27–34. https://doi.org/10.5815/ijcnis.2016.01.04

15. Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Skorodumov Y.M. Optimization of information exchange in a network of autonomous participants.Journal of Computer and Systems Sciences International, 2022, vol. 61, no. 6, pp. 935–943. https://doi.org/10.1134/S1064230722060107

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License