Interconnection Networks of Degree Three Obtained by Pruning Two-Dimensional Tori
Iain A. Stewart · IEEE Transactions on Computers · 2013
We study an interconnection network that we call$3Torus(m,n)$obtained by pruning the$4m \times 4n$torus (of links) so that the resulting network is regular of degree 3. We show that$3Torus(m,n)$retains many of the useful properties of tori (although, of course, there is a price to be paid due to the reduction in links). In particular, we show that$3Torus(m,n)$is node-symmetric; we establish closed-form expressions on the length of a shortest path joining any two nodes of the network; we calculate the diameter precisely; we obtain an upper bound on the average inter-node distance; we develop an optimal distributed routing algorithm; we prove that$3Torus(m,n)$has connectivity 3 and is Hamiltonian; we obtain a precise expression for (an upper bound on) the wide-diameter; and we derive optimal one-to-all broadcast and personalized one-to-all broadcast algorithms under both a one-port and all-port communication model. We also undertake a preliminary performance evaluation of our routing algorithm. In summary, we find that$3Torus(m,n)$compares very favourably with tori.