Automatization of deadlock-free routs tracking process for networks with redundancy and wormhole routing

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.