A Generalized Routing Algorithm for a Family of Optimal 2D Circulant Networks Based on Relative Addressing
Emilia A. Monakhova, Oleg G. Monakhov · 2021
The problem of the organization of optimal communications in circulant networks is considered. For a family of optimal two-dimensional circulant networks with the minimum diameter and average distance, the relative addressing of nodes of a network is introduced as shortest paths vectors from a fixed node. On its basis, a constant complexity pair routing algorithm using a set of shortest paths is proposed. This algorithm reduces the execution time in comparison with known routing algorithms due to the elimination of division operations and reduces the required memory to few words. The new algorithm is an analytical generalization to any number of nodes in a network of the method proposed for the family of Gaussian networks. This generalization is based on the proposed scheme of transformations on the plane of geometrical patterns of graphs of the family. The routing algorithm can be applied in networks-on-chip with a two-dimensional circulant topology.