CLASS-CONGRUENCE PROPERTY AND 2-PHASE ROUTING OF BOREL CAYLEY-GRAPHS

Dense, symmetric graphs are useful interconnection models for multicom puter systems. Borel Cayley graphs, the densest degree-4 graphs for a range of diameters [1], are attractive candidates, However, the group- theoretic representation of these graphs makes the development of effi cient 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 [2], [3]. In this paper, we pres ent the class-congruence property and use this property to develop the two-phase routing algorithm for Borel Cayley graphs in a special GCR representation. The algorithm requires a small space complexity of O(p + k) for n = p x k nodes. Although suboptimal, the algorithm finds pa ths with length bounded by 2D, where D is the diameter. Furthermore, o ur computer implementation of the algorithm on networks with 1,081 and 15,657 nodes shows that the average path length is on the order of th e diameter. The performance of the algorithm is compared with that of existing optimal and suboptimal algorithms.