A scalable approach to co-design of topologies and routing algorithms for families of optimal degree-four circulant networks

O. G. Monakhov, È. A. Monakhova

Institute of Computational Mathematics and Mathematical Geophysics, 6 Acad. Lavrentyev Avenue, 630090 Novosibirsk, Russia

Abstract: This paper presents a new approach to the joint construction of topologies for diameter-optimal circulant networks $C(N; 1, s_2)$ and optimal routing algorithms of complexity $O(1)$ implemented for them. New routing algorithms are based on the use of scalable parameters of $L$-shaped patterns in a dense packing of graphs on the plane for families of optimal networks. The scalability of the parameters of $L$-shaped patterns for a set of families of optimal networks $C(N; 1, s_2)$ is shown. We obtain analytical formulas for the dependence of these parameters on the graph diameter, reducing the time for setting up the routing algorithm at the preliminary stage from $O(\log N)$ to $O(1).$ A comparison of the new routing algorithm with the optimal one known in the literature demonstrates its greater efficiency, on average, by more than $10\%$ in terms of routing time in families of optimal graphs. Due to their good scalability and ease of routing, optimal degree-four circulant networks are of interest as efficient and reliable communication networks for networks-on-chip, multiprocessor supercomputer systems, telecommunications network structures, and neural communication networks. Tab. 1, illustr. 6, bibliogr. 20.

Keywords: undirected circulant network, optimal routing algorithm, family of optimal circulant networks, diameter, dense packing of graphs on a plane.

UDC: 519.176+519.8+519.7

Received: 19.07.2024
Revised: 11.08.2024
Accepted: 22.09.2024

DOI: 10.33048/daio.2025.32.808