Distributed and Fault-Tolerant Routing for Borel Cayley Graphs

الملخص EN

We explore the use of a pseudorandom graph family, Borel Cayley graph family, as the network topology with thousands of nodes operating in a packet switching environment.

BCGs are known to be an efficient topology in interconnection networks because of their small diameters, short average path lengths, and low-degree connections.

However, the application of BCGs is hindered by a lack of size flexibility and fault-tolerant routing.

We propose a fault-tolerant routing algorithm for BCGs.

Our algorithm exploits the vertex-transitivity property of Borel Cayley graphs and relies on extra information to reflect topology change.

Our results show that the proposed method supports good reachability and a small End-to-End delay under various link failures scenarios.