Class-Congruence Property and Two-Phase Routing of Borel Cayley Graphs

Dense, symmetric graphs are useful interconnection models for multicomputer systems. Borel Cayley graphs, the densest degree4 graphs for a range of diameters [I], are attractive candidates. However, the group-theoretic representation of these graphs makes the development of efficient routing algorithms difficult. In earlier reports, we showed that all degree-4 Borel Cayley graphs have generalized chordal ring (GCR) and chordal ring (CR) representations [Z], [3]. In this paper, we present the class-congruence prciperty and use this property to develop the two-phase routing algorithm for Borel Cayfey graphs in a special GCR representation. The algorithm requires a small space complexity of Ob + k) for n = p x k nodes. Although suboptimal, the aigorithm finds paths with length bounded by 20, where D is the diameter. Furthermore, our computer implementation of the algorithm on networks with 1,081 and 15,657 nodes shows that the average path lengh is on the order of the diameter. The performance of the algorithm is compared with that of existing optimal and suboptimal algorithms.