New methods for using Cayley graphs in interconnection networks

A number of researchers have proposed Cayley graphs and Schreier coset graphs as models for interconnection networks. New algorithms are presented for generating Cayley graphs in a more time-efficient manner than was previously possible. Alternatively, a second algorithm is provided for storing Cayley graphs in a space-efficient manner (log2 (3) bits per node), so that copies could be cheaply stored at each node of an interconnection network. The second algorithm is especially useful for providing a compact encoding of an optimal routing table (for example, a 13 kilobyte optimal table for 64000 nodes). The algorithm relies on using a compact encoding of group elements known from computational group theory. Generalizations of all of the above are presented for Schreier coset graphs.