Cayley-Graph-Based Data Centers and Space Requirements of a Routing Scheme Using Automata

Modern data centers connect tens of thousands of computers by an interconnection network. The design of such networks implies the selection of an appropriate routing scheme for them. Those schemes need to be efficient with respect to time and space requirements. Cayley Graphs (CG) has been proposed as models for large-scale interconnection networks with excellent properties and very efficient routing schemes. In a previous work, we presented a fast general-purpose shortest path routing scheme for CG with compact routing tables. The scheme uses the concept the Automatic Structures (AS) of a group. However, the size of such structures was not considered into the complexity analysis. Therefore, this paper evaluates the required space to keep such structures and the several intermediate finite state automata that arise during the process of constructing such AS. We perform the evaluation on six well-known families of CG. The results show which structures are space-efficient to implement the scheme, and how the size of such structures depends on the so-called k-fellow traveler property.