Publication details for Professor Iain StewartStewart, I.A. (2014). Interconnection networks of degree three obtained by pruning two-dimensional tori. IEEE Transactions on Computers 63(10): 2473-2486.
- Publication type: Journal Article
- ISSN/ISBN: 0018-9340
- DOI: 10.1109/TC.2013.139
- Keywords: Graphs, Networks, Computer Systems, Organization, Communication, Information, Technology, Design, Data.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We study an interconnection network that we call 3Torus(m,n) obtained by pruning the 4m x 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 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.