## 5 Use Case  
### Routing Problem in Bipartite Circulant Graphs  
As shown earlier, circulant graphs have a wide range of applications. They are especially promising for communication networks for supercomputer systems and NoCs. The fact is that in wired communication networks, the classic are various tree-like topologies [42] (formally, combination of bus and star network topologies). This is due to the hierarchical structure of such networks, where routers of different levels are connected, and end devices are leaves of such a tree. Such topologies are also convenient in that they can contain a predetermined number of nodes that can dynamically connect and disconnect. However, at the same time, trees also have many disadvantages, such as a long path between nodes, the congestion of connections located closer to the root nodes, etc. In closed networks (such as communication subsystem of a supercomputer), the topology and the number of nodes are usually predetermined. Therefore, they normally use much more efficient, more connected topologies, such as mesh and torus [43]. They areconvenient in that they have a flat shape and a regular structure, so that network nodes can be easily networked. At the same time, routers are also quite simple, and they are of the same type. It can be noted that NoCs are (to some extent) analogous to supercomputer networks; the only difference is the processing nodes are placed inside one chip; there is also the problem of finding new regular topologies to connect nodes. With the development of technology, topological characteristics (such as diameter and mean path length) are becoming even more important; mesh and torus are most effective when they are square-shaped, i.e., this way, they limit the set of nodes that the network can consist of. It is known [44] that circulant topologies have better topological characteristics and also endure any number of nodes, i.e., they are a promising replacement for the classical regular topologies. An important requirement for routers in the networks considered is their simplicity; so, there is no need to implement the whole OSI [42; 45] networking model and multi-layer communication protocols. Ideally, the router should contain a finite-state machine that, based on the known destination address and its own address, calculates which port to forward the packet to. On the other hand, such simplicity leads to the fact that the communication subsystem becomes vulnerable to various destructive phenomena, such as deadlocks, livelocks, failures, and starvation [46; 47]. Deadlocks occur due to the presence of cyclic dependencies in packet transmission routes, when the tail of one packet blocks the head of another packet, whose tail (in turn) blocks another packet, and so on. For mesh and torus, many different methods of dealing with deadlocks have been developed, many of which are based on the use of virtual channels and sets of rules for switching between channels and bypassing blocked links [46]. However, for circulant topologies, there are few such approaches, since it is not entirely clear which rule should be used to switch virtual channels. To handle deadlocks, we propose to divide the graph using edge decomposition into a set of simpler subgraphs that do not have cyclic dependencies (see Figures 2 and 3). The following rule can be introduced: if a packet moves from one subgraph to another, it has to change the virtual channel. At the same time, at the beginning of moving through the network, a packet is always in virtual channel 1. This approach is primarily applicable for local distributed routing, when the entire path is not calculated in advance, and the decision to switch the packet to the appropriate port is made at the router level and only 1 hop ahead. Thus, adding an additional virtual channel selection rule will lead to a slightly more complicated routing procedure and the need to store 1-2 additional bits denoting the subgraph label to which the corresponding router belongs.