Fault-tolerant routing on Borel Cayley graph

In this paper, we 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. 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 short average hop count.

I. Introduction

In the next generation of networks (NGNs), it is envisioned that net-centric technology will provide an unprecedented level of capacity and efficiency to support large numbers (millions and billions) of network nodes with heterogeneous services (voice, data, video, etc). These NGNs are packet-based multi-hop networks with a vast number of nodes and varying capabilities, operating asynchronously. In this research, we explore the use of a graph based network, the Borel Cayley graphs, as an interconnection networks for the core of an NGNs. The use of graph base networks has found applications in WDM optical networks [1], peer to peer networks [2], [3], satellite constellations [4], chip design [5], and wireless sensor networks [6], [7]. It allows for a theoretical analysis and guarantees global properties such as a diameter and average path length from the deterministic characteristics for connections between nodes [8]. Also, graph based networks can have symmetry, hierarchy, connectivity, and hamiltonicity which are desired properties comparing random graph based networks [9], [10], [11].