Routing and theoretical properties of optimised degree six 3- modified chordal rings for large interconnection network topologies

This study aimed to develop a new degree six modified chordal ring, the optimised degree six 3-modified chordal ring CHR60, as a seed topology for large networks which is able to improve on the performance of existing degree six chordal rings by previous researchers. Its graph theoretical properties were analysed and its routing algorithm was proposed. The performance parameters of optimal diameter and optimal average path length in CHR60 were first analysed theoretically by the number of nodes in its tree visualisation. Formulae for these two performance parameters were then generated, which enabled their comparison with those of degree six chordal rings by previous researchers for network sizes from 1200 to 12000 nodes. Graph theoretical properties encompassing asymmetry, existence of Hamiltonian and Eulerian Circuits, bounds for chromatic numbers, and conditions for different chromatic indices CHR60 in were investigated. A suitable geometrical representation was constructed to illustrate its connectivity. An optimum free-table routing algorithm was developed and ran as a computer simulation to determine the shortest paths through which a message can travel through a network of CHR60.CHR60 was shown to have better performance in ranges of large networks compared to degree six chordal ring topologies proposed by preceding researchers, with diameter 8 at 12000 nodes. The results from the formulations of CHR60 were validated by comparing them to those from the computer simulation. Theorems regarding aforementioned graph theoretical properties were developed and successfully proven. A geometrical representation based on snowflakes was also developed to illustrate the connectivity CHR60 in a network. In conclusion, this research succeeded in improving over the performance of existing degree six chordal ring topologies proposed by preceding researchers, based on diameter and average path length in large networks. This implies that CHR60 is a seed topology that can be considered as a multiprocessor interconnection network.