A computation of the shortest paths in optimal two-dimensional circulant networks

E. A. Monakhova

Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 87-100

Résumé

A family of tight optimal two-dimensional circulant networks designed by analytical formulas has a description of the form $C(N;d,d+1)$, where $N$ is the order of a graph and the generator $d$ is the nearest integer to $(\sqrt {2N-1}-1)/2$. For this family, two new improved versions of a shortest-path routing algorithm with a complexity $O(1)$ are presented. Simple proofs for formulas used for routing algorithms based on the plane tessellation are received. In the routing algorithm, for a graph $C(N;d,d+1)$ the following formulas for the computing shortest routing vector $(x,y)$ from 0 to a node $k\le \lfloor N/2 \rfloor$ are used: if $k\bmod(d+1)=0$ or $\lfloor k/(d+1)\rfloor$, then $x=-k\bmod(d+1)$, $y=\lfloor k/(d+1)\rfloor -x$, else $x=-k\bmod(d+1)+d+1$, $y= =\lfloor k/(d+1)\rfloor-x+1$. The routing algorithms and their estimates are considered for using in topologies of networks-on-chip. For implementation in networks-on-chip the proposed routing algorithm requires $ \lceil \log_{2}N \rceil+ \lceil \log_{2}\lceil \sqrt{N/2} \rceil \rceil$ bits. New versions of the routing algorithm improve also the routing algorithm proposed early by the author for optimal generalized Petersen graphs with an analytical description of the form $P(N,a,a+1)$, where $2N$ is the order of a graph and $a = \lceil \sqrt{(N-1)/2} \rceil-1$.

Détail

Keywords: two-dimensional circulant networks, diameter, shortest paths, optimal generalized Petersen graphs, networks-on-chip.