Fault-Tolerant Routing on Borel Cayley Graph

In this paper, the authors explore the use of a pseudo-random graph family, Borel Cayley graph family, as the network topology in an NGN (Next Generation Network) with thousands of nodes operated in a packet switching environment asynchronously. BCGs are known to be an efficient topology in interconnection networks because of its small diameters, short average path lengths, and low-degree connections. However, the application of BCGs in NGN are hindered by a lack of size flexibility and fault tolerant routing. They propose a fault-tolerant routing algorithm for BCGs. Their algorithm exploits the vertex-transitivity property of Borel Cayley graphs and relies on extra information to reflect topology change.