Distributed and Fault-Tolerant Routing for Borel Cayley Graphs

Abstract

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.

1. Introduction

Various graph-based interconnection networks have been applied to wavelength division multiplexed optical networks [1, 2], distributed parallel computation [3], distributed control [4], satellite constellations [5], chip design [6–9], and wireless sensor networks [10, 11]. In peer-to-peer overlay network schemes, various structure graphs are investigated compared to unstructured P2P overlay network [12]. For the example of structured P2P, k ring lattice is used in Chord [13] and de Bruijn graph is used in Koorde and Distance Halving [14, 15]. Also there are theoretic analyses to apply de Bruin and Cayley graphs to P2P [16, 17].

Deterministic characteristics for connections between nodes in structured graphs allow theoretical analysis and guarantee global properties such as a diameter and average path length [18]. Also graph-based networks can have symmetry, hierarchy, connectivity, and hamiltonicity, which are desired properties comparing random graph-based networks [17, 19].

Borel Cayley graphs (BCGs) have been shown to be efficient candidates for interconnection networks [20]. BCGs are known to have small diameters, average path lengths, and low-degree constant connections. The degree-diameter problem has been investigated in the contexts of interconnection networks [21, 22], wavelength division multiplexed optical networks [23], and VLSI layout design [24]. Also, BCGs are symmetric graphs, a property that enables distributed routing [25]. With consensus protocol [26], distributed node to node message exchange rule to drive nodes to an agreement for a quantity of interest, BCG showed better performance than mesh, torus, and small world networks [27]. Even though BCGs have such favorable properties, there are practical limitations in applying BCGs to networks. One of them is the lack of fault-tolerant routing algorithms: existing BCG routing algorithms do not account for node or communication link failures. Researchers have studied fault-tolerant routing on mesh, toroidal mesh, and de Bruijn graphs [28–30].

In this paper, we present a fault-tolerant routing algorithm for BCG, which accounts for communication link failures. For fault-tolerant routing, the routing tables of nodes are updated distributively in response to link failures. We quantify the performance of the routing algorithm by considering packet reachability and average hop count for different levels of communication link failures. Our simulation results show our proposed method to improve delivery performance by $\mathrm{20}\%$ to $\mathrm{350}\%$ . We also show packet congestion by proposed algorithms according to packet generation rate. We assume that contention is solved by the MAC layer. Thus, we abstract this case as a graph with point-to-point links and transform the problem into a graph.

This paper is organized as follows. Section 2 reviews basic concepts and definitions for BCGs and related terminology. Section 3 presents our network model and compares BCGs with other known graph topologies. Section 4 presents the data structures used by our proposed routing algorithm for BCGs. Section 5 describes behaviors of the proposed routing algorithm. Section 6 presents simulation results to estimate reachability and the average hop count of our proposed routing algorithm. Conclusions are presented in Section 7.

2. Preliminaries

In the following, we provide a definition of Cayley graphs, Borel subgroup, and Borel Cayley graphs.

Definition 1 (Cayley graph [20]).

A graph $C=ℂ(V,G)$ is a Cayley graph with vertex set V such that if two nodes $v_{\mathrm{1}},v_{\mathrm{2}}\in V$ are adjacent then $v_{\mathrm{1}}=v_{\mathrm{2}}*g$ for some $g\in G$ , where $(V,*)$ is a finite group and $G\subset V\setminus \{I\}$ . G is called the generator set of the graph and I is the identity element of the finite group $(V,*)$ .

The definition of a Cayley Graph requires vertices to be elements of a group but does not specify a particular group.

Definition 2 (Borel subgroup).

If V is a Borel subgroup of general linear $\mathrm{2}\mathrm{\hspace{0.17em}\hspace{0.17em}}\times \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{2}$ matrices set, then

$$\begin{array}{cc}& V=\left\{\left(\begin{array}{cc}x& y\\ \mathrm{0}& \mathrm{1}\end{array}\right):\mathrm{\hspace{0.17em}\hspace{0.17em}}x=a^t\left(\mathrm{mod}\hspace{0.17em}\mathrm{\hspace{0.17em}\hspace{0.17em}}p\right),y\in Z_p,t\in Z_k\mathrm{\hspace{0.17em}\hspace{0.17em}}\right\},\end{array}$$

(1)

where a is a fixed parameter $a\in Z_p\setminus \{\mathrm{0,1}\}$ , p is prime, and k is the order of a. That is, k is the smallest positive integer such that $a^k=\mathrm{1}$ (mod p).

Definition 3 (Borel Cayley graph (BCG) [20]).

Let V be a Borel subgroup and let G be a generator set such that $G\subseteq V\setminus \{I\}$ , then $B=ℬ(V,G)$ is a Borel Cayley graph with vertices $\mathrm{2}\mathrm{\hspace{0.17em}\hspace{0.17em}}\times \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{2}$ matrix elements of V. There exists a directed edge from v to u if only only if $u=v*g$ , where $u\ne v\in V$ , $g\in G$ and * is the modulo-p multiplication chosen as a group operation.

Definition 4 (GCR [20]).

A graph R is a generalized chordal ring (GCR) if nodes of R can be labeled with integers modulo number of nodes N, and there exists a divisor q of N such that node i is connected to node j if and only if node $i+q$ (mod N) is connected to node $j+q$ (mod N).

The connection rules of elements are defined by connection constants. Based on Definition 4, connection constants for i and $i+q$ are identical. When the graph is four regular, there are four connection constants. For example, Figure 1 shows a degree 4 GCR with 21 nodes and $q=\mathrm{3}$ classes. For $V=\mathrm{0,1},\mathrm{2},\dots ,\mathrm{20}$ and any $i\in V$ , the connection rules can be define as

$$\begin{array}{l}\text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}i(\mathrm{mod}\hspace{0.17em}\mathrm{3})=\\ \{\begin{array}{ll}“\mathrm{0}”:i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{connected}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}i+\mathrm{3},i-\mathrm{3},i+\mathrm{4},i-\mathrm{10}& \left(\mathrm{mod}\hspace{0.17em}\mathrm{21}\right)\\ “\mathrm{1}”:i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{connected}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}i+\mathrm{6},i-\mathrm{6},i+\mathrm{7},i-\mathrm{4}& \left(\mathrm{mod}\hspace{0.17em}\mathrm{21}\right)\\ “\mathrm{2}”:i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{connected}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}i+\mathrm{9},i-\mathrm{9},i-\mathrm{7},i+\mathrm{10}& \left(\mathrm{mod}\hspace{0.17em}\mathrm{21}\right).\end{array}\end{array}$$

(2)

Figure 1

A Borel Cayley graph in the GCR representation with $p=\mathrm{7}$ , $a=\mathrm{2}$ , $k=\mathrm{3}$ , $t_{\mathrm{1}}=\mathrm{0}$ , $t_{\mathrm{2}}=\mathrm{1}$ , $y_{\mathrm{1}}=\mathrm{1}$ , and $y_{\mathrm{2}}=\mathrm{1}$ .

Proposition 5.

For any finite Cayley graph with vertex set V and any $T\in V$ such that $T^m=I$ , there exists a GCR representation of C with divisor $q=N/m$ , where I is the identity element.

The proof of these propositions is given in [20] and not repeated here. T is referred to as the transform element. $a_i$ are class representing elements.

For simplicity of the GCR representation, we chose T and $a_i$ as follows [20]:

$$\begin{array}{cc}& T=\left(\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}\end{array}\right),\hspace{1em}\hspace{1em}{a}_i={\left(\begin{array}{cc}a& \mathrm{0}\\ \mathrm{0}& \mathrm{1}\end{array}\right)}^i.\end{array}$$

(3)

Any vertex $v\in V$ is represented with T and $a_i$ as follows [20]:

$$\begin{array}{cc}& v=T^j*a_i=\left(\begin{array}{cc}\mathrm{1}& j\\ \mathrm{0}& \mathrm{1}\end{array}\right)\left(\begin{array}{cc}{a}^i& \mathrm{0}\\ \mathrm{0}& \mathrm{1}\end{array}\right)=\left(\begin{array}{cc}{a}^i& j\\ \mathrm{0}& \mathrm{1}\end{array}\right).\end{array}$$

(4)

BCGs are defined over a group of matrices. The systematic representation of BCGs from the group domain to the integer domain is useful for routing because nodes are defined in the integer domain and the integer domain provides a systematic description of connections. The node ID representation in GCR ( $I{D}_g(v)$ ) is denoted as follows [20]:

$$\begin{array}{cc}& I{D}_g\left(v\right)=q*j+i,\end{array}$$

(5)

where q is the parameter k in Definition 2.

Symmetry or vertex transitivity is a preferable attribute for an efficient interconnection network topology. Informally, a symmetric or vertex-transitive graph looks the same from any node. This property allows to use an identical routing table at every node. Mathematically, this implies that for any two nodes a and b in the graph there exists an automorphism of the graph that maps a to b. This property is very useful for practical implementation of interconnection networks. Most of the well-known interconnection graphs, such as the toroidal mesh, hypercube, and cube-connected cycle, exhibit this property.

Proposition 6.

All Cayley graphs are vertex transitive [20].

Every Cayley graphs can be represented with integer node labels through a transformation into a generalized chordal ring topology. However, generally speaking, GCR graphs are not fully symmetric. In [20], the authors provide a framework for the formulation of the complete symmetry (or vertex transitivity) of Cayley graphs in the integer domain of GCR representations.

Proposition 7.

Assume a Borel Cayley graph in the GCR representation with transform element $T=\left(\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}\end{array}\right)$ and representing elements of each class i as $a_i=\left(\begin{array}{cc}{a}^i& \mathrm{0}\\ \mathrm{0}& \mathrm{1}\end{array}\right)$ . Let $i=m_{\mathrm{1}}q+c_{\mathrm{1}},j=m_{\mathrm{2}}q+c_{\mathrm{2}}$ , and $i^{\prime }=m^{\prime }q+c^{\prime }$ . If i is connected to j with a sequence of generators, then $i^{\prime }$ is connected to $j^{\prime }$ with the same sequence of generators, where $j^{\prime }=〈m^{\prime }+a^{〈c^{\prime }-c_{\mathrm{1}}{〉}_q}(m_{\mathrm{2}}-m_{\mathrm{1}}){〉}_{p}q+〈c^{\prime }-c_{\mathrm{1}}+c+\mathrm{2}{〉}_q$ [25].

Algorithm 1 shows Vertex-transitive routing (VT routing) algorithm that exploits the inherent symmetry of Cayley graphs and uses the identical routing table at any node [25].

Algorithm 1: Vertex-transitive routing algorithm for Borel Cayley graphs.

For a degree-4 Borel Cayley graph in the GCR representation with $T=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ and $a_i=\left(\begin{array}{cc}{a}^i& \mathrm{0}\\ \mathrm{0}& \mathrm{1}\end{array}\right)$ ,

we have $q=k$ classes, where $a^k=\mathrm{1}$ (mod p). Assume the generators to be $g_{\mathrm{1}}$ , $g_{\mathrm{2}}$ , $g_{\mathrm{1}}^{-\mathrm{1}}$ and $g_{\mathrm{2}}^{-\mathrm{1}}$ , where

              $g_{\mathrm{1}}=\left(\begin{array}{cc}{a}^{t_{\mathrm{1}}}& y_{\mathrm{1}}\\ \mathrm{0}& \mathrm{1}\end{array}\right),\hspace{1em}\hspace{1em}{g}_{\mathrm{2}}=\left(\begin{array}{cc}{a}^{t_{\mathrm{2}}}& y_{\mathrm{2}}\\ \mathrm{0}& \mathrm{1}\end{array}\right)$ .

Given the source $i=m_{\mathrm{1}}q+c_{\mathrm{1}}$ and the destination $j=m_{\mathrm{2}}q+c_{\mathrm{2}}$ .

While ( $i\ne j$ )

 Step 1: Identify new destination,

              $j\mathrm{\text{'}}={〈a^{q-c_{\mathrm{1}}}(m_{\mathrm{2}}-m_{\mathrm{1}})〉}_{p}q+{〈c_{\mathrm{2}}-c_{\mathrm{1}}〉}_q$ ,

  where ${〈\hspace{0.17em}〉}_p$ signifies the operation within the bracket $〈\hspace{0.17em}〉$ is modulo p.

 Step 2: From row $j^{\mathrm{\text{'}}}$ of a precalculated routing table, determine which link to take.

 Step 3: Identify new source, $i^{\mathrm{\text{'}}}=mq+c$ and

   $m=y_{\mathrm{1}}$ , $c=t_{\mathrm{1}}$ , if link $g_{\mathrm{1}}$ was chosen

   $m=y_{\mathrm{2}}$ , $c=t_{\mathrm{2}}$ , if link $g_{\mathrm{2}}$ was chosen

   $m=p-〈a^{q-t_{\mathrm{1}}}{y}_{\mathrm{1}}〉$ , $c=q-t_{\mathrm{1}}$ , if link $g_{\mathrm{1}}^{-\mathrm{1}}$ was chosen

   $m=p-〈a^{q-t_{\mathrm{2}}}{y}_{\mathrm{2}}〉$ , $c=q-t_{\mathrm{2}}$ , if link $g_{\mathrm{2}}^{-\mathrm{1}}$ was chosen

 Step 4: $i=i^{\mathrm{\text{'}}}$ and $j=j^{\mathrm{\text{'}}}$

3. Topology Comparison

3.1. Network Model

A network that consists of a set of nodes is connected by full duplex point-to-point links. The node model is depicted in Figure 2. Each node consists of an input queue for transit messages ( $Rx$ ), a packet generator, a switching fabric, and an output queue. Modules inside a node are connected by zero delay links. It takes a single time unit for a packet to move from an output queue to an input queue. Time is slotted and synchronized so that all nodes receive and transmit packets simultaneously.

Figure 2

Node model.

An input queue is FIFO served. In each time slot, the input queue accepts up to the number of packets, the degree of a node in the same time slot. Depending on the model, the input buffer size ranges from one to infinity. The output buffer size is one. The packet arrival module removes packets from the input queue if the current node is the destination node. The switching fabric determines the next node of the packet taken from the input queue by a routing algorithm. Every node in the network can be a source, a destination, or a relay. We assume that nodes generate information at a constant average rate of R packets per time slot (Packet generator).

Three traffic patterns are considered in this paper: All-to-All traffic pattern (Pattern $\mathrm{0}$ ), All-to-one traffic pattern (Pattern $\mathrm{1}$ ), and All-to-M traffic pattern (Pattern $\mathrm{2}$ ). In Pattern $\mathrm{0}$ , all nodes are the source and destination nodes, which generate packets to uniformly randomly selected destination node. The probability of any source node communicating to any destination node in the network is constant and equal to $\mathrm{1}/n$ where n is the number of destination nodes. In Pattern $\mathrm{1}$ , nodes send packets to node $\mathrm{0}$ , the only destination node. That is, the one node (sink) gathers the information generated by all other nodes in the network [31]. In Pattern $\mathrm{2}$ , nodes send packets to a group of nodes, $\mathrm{5}\%$ of the total nodes in this case. This network model depicts a situation arising in integrated devices. Nodes located on the borders can be connected to high-capacity transmission lines.

3.2. Topologies

Toroidal mesh networks and de Bruijn graphs are popular topologies for interconnection networks [1, 5, 16]. In the following, we provide a definition for toroidal mesh networks and de Bruijn graphs. Then we show simulation results comparing Borel Cayley graphs with the aforementioned traffic patterns.

3.2.1. Toroidal Mesh Network

Figure 3(a) shows a toroidal mesh network (torus) which consists of R rows by C columns. When a node is represented by $rC+c$ , neighboring nodes are defined as follows: $((r-\mathrm{1})\mathrm{mod}\hspace{0.17em}R)C+c$ , $rC+(c-\mathrm{1})\mathrm{mod}\hspace{0.17em}C$ , $((r+\mathrm{1})\mathrm{mod}\hspace{0.17em}R)C+c$ , and $rC+(c+\mathrm{1})\mathrm{mod}\hspace{0.17em}C$ . We use a Greedy row-first routing algorithm on the torus mesh network. If a packet is not in the destination column, then the packet is routed along the row towards the destination column. Otherwise the packet is routed along the column toward the destination node [32].

Figure 3

Toroidal mesh network and de Bruijn graph.

3.2.2. De Bruijn

The undirected de Bruijn graph (UDB) has $N=d^k$ nodes of degree $\mathrm{2}d$ [1]. We use binary de Bruijn graphs $DG(\mathrm{2},k)$ of $N={\mathrm{2}}^k$ nodes. A node of the network with binary address $a_{k-\mathrm{1}}{a}_{k-\mathrm{2}}\cdots a_{\mathrm{1}}{a}_{\mathrm{0}}$ has neighbors: $a_{k-\mathrm{2}}{a}_{k-\mathrm{3}}\cdots a_{\mathrm{0}}{a}_{k-\mathrm{1}}$ , $a_{k-\mathrm{2}}{a}_{k-\mathrm{3}}\cdots a_{\mathrm{0}}{\bar{a}}_{k-\mathrm{1}}$ , $a_{\mathrm{0}}{a}_{k-\mathrm{1}}\cdots a_{\mathrm{2}}{a}_{\mathrm{1}}$ , and ${\bar{a}}_{\mathrm{0}}{a}_{k-\mathrm{1}}\cdots a_{\mathrm{2}}{a}_{\mathrm{1}}$ . Figure 3(b) shows an undirected de Bruijn graph for $k=\mathrm{3}$ and $d=\mathrm{2}$ where self-loops are removed.

Algorithm 2 corresponds to the routing algorithm for UDB. The routing algorithm consists of transmitting a packet to either its left or right neighbors [33]. Algorithm 2 defines the Forward Path (FP) as the path taken by a packet when a left neighbor is chosen as the next node and the Backward Path (BP) when a right neighbor is chosen. From de Bruijn graph's properties, it is easy to calculate the number of hops that it needs to reach the destination using FP or BP. This is done by matching the postfix portion of the source address with the prefix portion of the destination address. The more digits are matched; the shorter is the path between source and destination. For example, in Figure 3(b), assume node $\mathrm{011}$ needs to transmit a packet to node $\mathrm{110}$ . Since $\mathrm{11}$ is the postfix of the source and the prefix of the destination, node $\mathrm{011}$ will reach node $\mathrm{110}$ in one hop. In [33], it defined $match\_fwd(cur,dst)$ to be an operation which returns the number of hops required to reach the destination along a FP. Similarly, $match\_bwd(cur,dst)$ returns the number of hops along a BP.

Algorithm 2: Undirected de Bruijn graph routing algorithm.

(1)  procedure Routing Algorithm For UDB (cur, dst)   $▹$ cur: the current node, dst: the destination node

(2)   $i⟵match\_fwd(cur,dst)$

(3)   $j⟵match\_bwd(cur,dst)$

(4)  if   $i<j$   then

(5)    using FP sent to the particular left neighbor

(6)  else  if   $i=j$   then

(7)    randomly using FP or BP

(8)  else

(9)    using BP sent to the particular right neighbor

(10) end  if

(11)  end  procedure

3.2.3. Performance Comparison

The parameters for the mesh networks we used for performance comparison are described in Table 1. BCG and Torus are degree $\mathrm{4}$ graphs. Most nodes of $\text{UDB}$ have degree $\mathrm{4}$ except the few nodes, with self-loops. Table 2 shows our benchmark mesh networks topological properties such as the diameter and the average path length. The diameter is the greatest distance between any two nodes. The average path length is the average number of edges between all possible node pairs. Constrained by degree $\mathrm{4}$ , BCG has the smallest diameter and the shortest average path length.

Table 1

Mesh networks parameters.

	N	Parameters
BCG	1081	$P=47$ , $k=23$ , $a=2$ , $t_1=1$ , $t_2=7$ , $y_1=1$ , $y_2=1$
Torus	1088	$R=32$ , $C=34$
UDB	1024	$d=2$ , $k=10$

Table 2

Static Property.

	AVG. path length	Diameter
BCG	5.54	7
Torus	16.52	33
UDB	6.77	10

We also considered the performance of our network models. We used two metrics for comparison: (a) End-to-End delay and (b) reachability. We define End-to-End delay as the time required by packets to travel from a source to a destination and the reachability as the number of packets reaching destination over the number of generated packets. When running our simulations, we used the three types of traffic patterns presented in 3.1. We set the input buffer length to infinite, $\mathrm{5}$ , and $\mathrm{10}$ . Our simulation running time is $\mathrm{100000}$ ticks.

Figure 4 shows End-to-End delay (ETE delay) as a function of packet generation rate for our three traffic patterns. BCG exhibits the smallest End-to-End delay across all traffic patterns. Each network shows that End-to-End delay increases rapidly above a certain traffic generation rate called traffic congestion point. An efficient network topology should consider both End-to-End delay and network saturation. BCG shows a small End-to-End delay and a more robust traffic congestion point than UDB and Torus.

Figure 4

End-to-End delay with infinite buffer.

When a buffer at each node is finite, packets can be overflowed for large packet generation rates and thus reachability is not achieved as $\mathrm{100}\%$ . Figures 5 and 6 show reachabilities with buffer length $\mathrm{10}$ and $\mathrm{5}$ , respectively. Reachability with finite buffer decreases above certain packet generation rate. Decreasing reachability packet generation rate of BCG is larger than others even though they have almost the same number of nodes and edges. UDB and Torus show similar reachabilities with traffic pattern $\mathrm{1}$ because End-to-End delays of traffic pattern $\mathrm{1}$ increase rapidly together at the similar packet generation rate.

Figure 5

Reachability with buffer length $\mathrm{10}$ .

Figure 6

Reachability with buffer length $\mathrm{5}$ .

4. Data Structure of Exhaustive Routing

A conventional routing algorithm for Borel Cayley graphs, Vertex-transitive routing, exploits the graphs vertex-transitive property. That property allows to use an identical routing table in every node. The routing table is created for node $\mathrm{0}$ only; and for other nodes to use that table, a simple node ID translation is applied to the destination node ID. The Vertex-transitive routing algorithm guarantees the shortest path between any source-destination pair. However, Vertex-transitive routing only applies to a static network and cannot account for node/link failures. The goal of our proposed routing algorithm (Exhaustive routing) is to route messages in the presence of link failures.

Exhaustive routing has two phases. In Phase $\mathrm{1}$ , packets are routed through the shortest path according to the Static Routing Table. If there is a link failure making the shortest path unavailable, a Dynamic Routing Table for Type $\mathrm{1}$ packets is updated and other shortest paths (following the Static Routing Table) will be used. However, when all shortest paths from the BCG are disconnected, there can still be a path between the source and destination. In that case, Phase $\mathrm{2}$ of Exhaustive routing is used.

Phase $\mathrm{2}$ exploits the path length information in the Static Routing Table to search for possible routes besides the shortest paths from BCG. A Dynamic Routing Table for Type $\mathrm{2}$ packets is created to indicate “next best” paths as well as any unusable link due to failures. Basically, in Phase $\mathrm{2}$ , packets are routed according to the path length information and update unusable links in the Dynamic Routing Table.

We define two types of routing tables according to whether or not the table changes in response to link failures: (a) a Static Routing Table and (b) a Dynamic Routing Table. The following provides a more detailed description of the two types of routing tables.

4.1. Static Routing Table

The Static Routing Table is pre-calculated and identical across all nodes. The Static Routing Table is defined for a reference source node, node $\mathrm{0}$ . Each time a message needs to be routed from a node different than node $\mathrm{0}$ . So the destination ID is mapped from absolute ID (Global ID of the destination in a network) to relative ID (ID of the destination in the view of the current node regarded as a reference node) as follows, referring to Algorithm 1:

$$\begin{array}{cc}& j^{\prime }={〈a^{q-c_{\mathrm{1}}}\left(m_{\mathrm{2}}-m_{\mathrm{1}}\right)〉}_{p}q+{〈c_{\mathrm{2}}-c_{\mathrm{1}}〉}_q,\end{array}$$

(6)

where the current node's absolute ID is $m_{\mathrm{1}}q+c_{\mathrm{1}}$ , the destination node's absolute ID is $m_{\mathrm{2}}q+c_{\mathrm{2}}$ , and $j^{\prime }$ is the relative destination ID. We denote the absolute ID of node u by $a\text{ID}(u)$ and the relative ID of node u at node v by $r\text{ID}(u,v)$ . Row indexes of Static Routing Table are relative IDs.

The number of rows in the Static Routing Table is the number of nodes minus one and the number of columns is the number of generators (nodal degree). In Figure 7(a), a number $\mathrm{1}$ in the routing table for Vertex-transitive routing indicates the shortest path through that generator link. For instance, for the relative destination ID $\mathrm{4}$ , the shortest path at node u is through generator $g_{\mathrm{2}}$ .

Figure 7

Original vertex-transitive routing table and Static Routing Table of BCG in Figure 1. Note that some parts of routing tables are omitted for brevity.

The Static Routing Table for Exhaustive routing (SRTBL) includes the shortest path lengths to destination through an indicated generator. The shortest path lengths are calculated from Dijkstra's algorithm [34]. The first row of the Vertex-transitive routing table in Figure 7(a) shows an entry of $\mathrm{1}$ in the generator $g_{\mathrm{1}}^{-\mathrm{1}}$ cell. On the other hand, in the first row of SRTBL in Figure 7(b), the shortest path is though generator $g_{\mathrm{1}}^{-\mathrm{1}}$ and is two hops away from destination. If we choose the generator $g_{\mathrm{2}}$ not $g_{\mathrm{1}}^{-\mathrm{1}}$ , it would take four hops to reach destination. We denote the routing data to node v from node u by SRTBL $(r\text{ID}(v,u))$ and the hop count through generator g from node u to node v by $\text{SRTBL}(r\text{ID}(v,u),g)$ . For example, SRTBL $(r\text{ID}(\mathrm{3,0}))=(\mathrm{1,3},\mathrm{3,3})$ and SRTBL $(r\text{ID}(\mathrm{3,0}),g_{\mathrm{2}})=\mathrm{3}$ .

4.2. Dynamic Routing Table

The Dynamic Routing Table (DRTBL) is generated or updated based on route availability. From the contents of a received packet, a node can determine whether or not certain shortest path links are no longer available. We will explain how to determine when links are no longer available in Section 5. DRTBL is generated for each destination node, hence the size of DRTBL will vary. For example, node u detects that the $g_{\mathrm{2}}$ link for node v is no longer available. If there is no DRTBL for node v, node u generates a new DRTBL for node v. Otherwise, it sets the $g_{\mathrm{2}}$ link to zero in existing DRTBL for node v. DRTBLs are unique at each node. So the relative ID is no longer needed. The index of DRTBL is the absolute ID. We denote routing data for node v at node u by $\text{DRTBL}(a\text{ID}(v),a\text{ID}(u))$ and data indicated by generator g for node v at node u by $\text{DRTBL}(a\text{ID}(v),a\text{ID}(u),g)$ .

The Exhaustive routing algorithm has two phases during which Type $\mathrm{1}$ and Type $\mathrm{2}$ packets are forwarded in the first phase and the second phase, respectively. We denote DRTBL for Type $\mathrm{1}$ packets by D1RTBL and DRTBL for Type $\mathrm{2}$ packets by D2RTBL. Table 3 summarizes routing tables for Exhaustive routing.

Table 3

Summary of routing tables for Exhaustive routing.

SRTBL	Precalculated
	Data are not changed
	Data are path lengths via generator
	For Phase 1 and Phase 2
D1RTBL	Generated dynamically
D2RTBL	Data are bits indicating the available links
	Data are updated when node/link failures occur
D1RTBL	For Phase 1
	Initialized with data indicating shortest path links
D2RTBL	For Phase 2
	Initialized with data indicating all links are to be explored

5. Phases of Exhaustive Routing

5.1. Phase 1

Phase $\mathrm{1}$ of Exhaustive routing exploits all the shortest paths extracted from BCG with SRTLB and D1RTBL.

5.1.1. Forwarding Rule of Phase 1

In Phase $\mathrm{1}$ of Exhaustive routing, the goal of forwarding a packet is to identify links corresponding to the shortest paths for the destination in SRTBL. Then packets are forwarded to a randomly selected link among the identified shortest path links. When a node can no longer forward a packet using the SRTBL, the shortest path links are disconnected, and the node forwards the packet to the previous node using the packet's Path history. Path history is an ordered list of nodes traversed by the packet being routed. The Path history is included in the Packet frame as follows:

$$\begin{array}{ll}& \text{Packet}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{frame}\\ \hspace{1em}\hspace{1em}=\left\{\text{Source},\text{Destination},\text{Packet}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Type},\text{Path}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{history}\right\}.\end{array}$$

(7)

5.1.2. Generating Dynamic Routing Table of Phase 1

Once a node receives a packet, it uses the Path history of the packet to determine whether or not the packet is a returned packet. If the node ID is found at the position before the last in the Path history, the received packet is a returned packet. When a node receives a returned packet, its D1RTBL is generated or updated. The SRTBL consists of path lengths via each generator. The links in SRTBL with smallest cell for a given $r\text{ID}$ are used. For example, in Figure 7(b), when node a determines the packet whose destination is node b ( $r\text{ID}(b,a)=\mathrm{5}$ ) is a returned packet via generator $g_{\mathrm{1}}$ ; it generates the D1RTBL for node b. we get D1RTBL $(a\text{ID}(b))=(\mathrm{1,1},\mathrm{1,0})$ since the smallest number is $\mathrm{3}$ in the SRTBL $(r\text{ID}(b,a)=\mathrm{5})=(\mathrm{3,3},\mathrm{3,4})$ . It sets the entry indicated by generator $g_{\mathrm{1}}$ to zero. Finally, node a has D1RTBL $(a\text{ID}(b))=(\mathrm{0,1},\mathrm{1,0})$ .

The generator link used by a returned packet is set to zero in the D1RTBL. Upon receiving a returned packet, if another shortest path exits (D1RTBL entry for the destination is $\mathrm{1}$ ), the node forwards the packet to a node indicated by the generator link. Otherwise the node removes the last node ID from the Path history and forwards the packet to the previous node. If the packet goes back all the way to the source node and the source node does not have any shortest path to the destination from D1RTBL, the node changes the packet type from Type $\mathrm{1}$ to Type $\mathrm{2}$ . Phase $\mathrm{1}$ of Exhaustive routing supports routing delivery as long as there is at least one shortest path extracted from BCG. Algorithm 3 shows Phase $\mathrm{1}$ of our Exhaustive routing algorithm.

Algorithm 3: Phase 1 of Exhaustive routing.

(1)  procedure Packet forwarding ( $pkt$ )

(2)  if   $pkt.dst=curID$   then          $▹$ $pkt.dst$ : destination of packet

(3)    Packet delivery is successful       $▹$ $curID$ : node ID of current node

(4)    Return

(5)  end  if

(6)  if $pkt.dst$ is a returned packet Table then

(7)    Update Dynamic Routing Table      $▹$ Case: node in path history

(8)  end  if

(9)  if $pkt.dst$ Dynamic Routing Table then

(10)   if There is an available link in row of destination in Dynamic Routing Table then

(11)     Forward the packet to randomly selected available generator link in Dynamic Routing Table  

(12)     Return

(13)   else  if $pkt.src=curID$   then

(14)     Change a type of $pkt$ from Type $\mathrm{1}$ to Type $\mathrm{2}$    $▹$ There is no available shortest path from BCG

(15)     Go to Phase $\mathrm{2}$ of Exhaustive routing

(16)   else

(17)     Update Path history and forward the packet to the previous node

(18)   end  if

(19)  else  if Row of destination in Static Routing Table then  

(20)    Forward the packet to randomly selected available generator link, which has the smallest path length within the

same row, in Static Routing Table

(21)    Return

(22)   end  if

(23) end  procedure

5.2. Phase 2

Table generation rules and packet forwarding rules for Type $\mathrm{1}$ and Type $\mathrm{2}$ packets are different. A Type $\mathrm{1}$ packet returns to source when there is no shortest path within D1RTBL. Then the source node changes the packet type from Type $\mathrm{1}$ to Type $\mathrm{2}$ . The Type $\mathrm{2}$ packet is forwarded via a communication link having the smallest value in the SRTBL when a node does not have a D2RTBL of the destination.

A packet gets stuck at a node having no available shortest path in Phase $\mathrm{1}$ . In Phase $\mathrm{2}$ , the node receiving Type $\mathrm{2}$ packet updates or generates a D2RTBL of the destination node. The D2RTBL is initialized to $\mathrm{1}$ at all edges when generated. Type $\mathrm{2}$ packets directly refer to all path lengths information from the SRTBL. The node chooses the link having the smallest path length in SRTBL and an entry of one in the corresponding D2RTBL. When no outgoing link can be identified, a node forwards the packet back to the previous node in the Path history. From this, Exhaustive routing exploits more routes to destination. This mechanism improves the reachability exploiting more available paths to destination. Figure 8 shows our Exhaustive routing algorithm flow.

Figure 8

Exhaustive routing algorithm flow.

The phase $\mathrm{2}$ of Exhaustive routing can have loops as shown in Figure 9. Assume node s sends a packet to node d via a. The packet reaches to node e via c but the communication link is disconnected. Then except the incoming link, the packet is forwarded to node f. The packet follows in a circle like $a\to b\to c\to e\to f\to h\to a\to b$ . To prevent loops, Phase $\mathrm{2}$ uses a different method to check whether a packet is a returned packet. In the case of Phase $\mathrm{1}$ , a node checks whether the previous node of the last node in the Path history is itself. However, in the case of Phase $\mathrm{2}$ of Exhaustive routing, the node checks all the Path history node IDs. Then node a is a returned packet referring to the Path history $(s,a,b,c,e,f,h)$ . Node a sets to zero at the generator link to node b in D2RTBL $(d,a)$ . The generator to h also sets to zero through the same method. Finally, node a delivers the packet via node m with Path history $(s,a)$ .

Figure 9

Network to illustrate a loop of Exhaustive routing. The dot line between nodes indicates that the communication is disconnected.

6. Simulation

We have designed simulators and performed experiments to evaluate our proposed fault-tolerant routing algorithm. We simulated BCG networks with $N=\mathrm{1081}$ (N is the number of nodes). We list the parameter values for BCGs used in Table 1. Parameters p and a determine N and BCG parameter k. Parameters $t_{\mathrm{1}}$ and $y_{\mathrm{1}}$ were used to construct the first generator. Parameters $t_{\mathrm{2}}$ and $y_{\mathrm{2}}$ were used to construct the second generator. Using two different generators and their inverse generators, we construct undirected degree $\mathrm{4}$ BCGs. We arbitrary chose parameters ts and ys for generators.

6.1. Static Property Performance

First, we simulated network disconnection by edge eliminations on BCG. We randomly select edges to be eliminated. For each simulated case, we generated $\mathrm{100}$ networks. The BCG is originally a connected graph. When we eliminate some edges, the network can consist of multiple network components (components are not connected each other). We measured packet delivery performance to the largest component only if the largest component has over $\mathrm{95}\%$ of the total nodes. Figure 10 shows the percentage of connected graphs among the $\mathrm{100}$ network samples for each edge elimination rate. From those results, we simulated BCG ranging from $\mathrm{5}\%$ to $\mathrm{35}\%$ elimination of edges.

Figure 10

Connected graph in case with edge elimination.

We showed two metrics for comparison of proposed routing algorithms: (a) routability and (b) the average hop count. We define the routability as the number of reachable source and destination pairs among all pairs of nodes in the largest component of a network and the average hop count as the average number of nodes traversed by a packet between its source and destination. In this subsection, the simulator does not generate a packet before the previous sent packet is dropped by a routing algorithm or reached to the destination (only one packet exists in the network), which helps to measure the routing algorithm performance regardless of packet congestion and buffer length.

We compared Exhaustive routing with Exhaustive routing with only Phase $\mathrm{1}$ routing (Phase $\mathrm{1}$ routing) and vertex-transitive routing (VT routing). Results of the Exhaustive routing are acquired after dynamic routing tables are stabilized. For comparison purpose, in our implementation of the original VT routing, a random optimal link is chosen in cases where multiple optimal links exist. When there is no available link, the packet is discarded.

6.1.1. Routability

Figure 11 shows routability of BCG with $\mathrm{1081}$ nodes after eliminating edges. Phase $\mathrm{1}$ routing shows larger routability than Vertex-transitive routing because Phase $\mathrm{1}$ routing exploits all shortest paths between source and destination. Exhaustive routing shows the largest routability.

Figure 11

Routability with $\mathrm{1081}$ BCG after edges are eliminated.

6.1.2. Average Hop Count

Figure 12 shows the average hop counts of BCG with $\mathrm{1081}$ nodes with $\mathrm{35}\%$ edge elimination. Comparing the average hop counts of our proposed algorithms is unfair when routability is not the same. For example, one routing algorithm supports packet delivery to only nodes within a short distance from their sources and another routing algorithm supports packet delivery to all the nodes. In this case, average hop count of the second algorithm is larger than the former. So we compared only average hop count of Exhaustive routing with the results of Optimal routing in which the shortest path from the current network between the source and destination node is used. When a packet is not delivered to the destination, we exclude it from the average hop count.

Figure 12

Average hop count with $\mathrm{1081}$ BCG after edges are eliminated.

6.1.3. Distribution of Hop Counts

We investigated frequency of hop counts when nodes are eliminated. Figure 13 shows hop counts distribution. The histogram of hop counts exhibits a right-skewed distribution with a high frequency of short hop counts.

Figure 13

Hop count distribution of BCG with $\mathrm{1081}$ nodes after $\mathrm{35}\%$ edge elimination. Note that hop counts exceeding $\mathrm{40}$ are not shown for brevity.

6.2. Dynamic Property Performance

We show dynamic properties of our routing algorithms, which means measuring performance when multiple packets are flowing simultaneously in the network, as opposed to the case of static properties. In this case, packet generation rate and buffer length are important parameters. We used the network model described in Section 3 and removed a randomly chosen edge each time unit according to the edge failure rate. Simulation running time is $\mathrm{1000000}$ ticks that is ten times longer than previous one because more time is needed to observe the effects of link failures. The evaluation was done in terms of the reachability according to packet generation rate, edge failure rate, and buffer length.

Table 4 shows reachability, the average ETE delay, and average occupied buffer length with infinite buffer and $\mathrm{0.0005}$ edge failure rate. Exhaustive routing produced the highest reachability but also the longest End-to-End delay. End-to-End delay does not consider nonreached packets.

Table 4

Routing comparison with infinite buffer, 0.05 packet generation rate, and 0.0005 edge failure rate.

	Reachability	ETE delay	Buffer length
VT	56.97%	6.14	0.23
Phase 1	60.7175%	6.23	0.19
Exhaustive	92.75%	9.19	0.43

Figure 14 shows reachability as a function of packet generation rate from $\mathrm{0.05}$ to $\mathrm{0.25}$ . With $\mathrm{0.05}$ packet generation rate, Exhaustive routing produced $\mathrm{56}\%$ and $\mathrm{47}\%$ better reachability than VT routing and Phase $\mathrm{1}$ , respectively. However, as packet generation rate increases, the performance becomes similar because of network capacity and overflowed packets. With $\mathrm{0.25}$ packet generation rate, Phase $\mathrm{1}$ routing shows $\mathrm{26}\%$ better reachability than Exhaustive routing because Exhaustive routing has a longer average hop count to support higher reachability in static analysis. It increases occupied buffer length and packets are dropped. Phase $\mathrm{1}$ routing shows better reachability than VT routing even at high packet generation rate. Phase $\mathrm{1}$ routing does not try to send packets by Dynamic Routing Table when there is no shortest path extracted from BCG. So packets guaranteed shortest path length existing in the network. Also, the occupied buffer length of Phase $\mathrm{1}$ is smaller than one of VT.

Figure 14

Comparison of fault-tolerant routing reachability with buffer length $\mathrm{5}$ and $\mathrm{0.0005}$ edge failure rate according to packet generation rate.

We investigated reachability in response to edge failure rate with $\mathrm{0.05}$ packet generation rate as shown in Figure 15. We changed edge failure rate, which means that frequent of edge failure changes and the number of fault edges is changed at the end of simulation. The total edge number of a degree- $\mathrm{4}$ BCG with $\mathrm{1081}$ nodes is $\mathrm{2162}$ and at the edge failure rate of $\mathrm{0.0005}$ , $\mathrm{0.00075}$ , $\mathrm{0.001}$ , $\mathrm{0.00125}$ , and $\mathrm{0.0015}$ , the expected number of eliminated edges at the end of simulation are $\mathrm{500}$ , $\mathrm{750}$ , $\mathrm{1000}$ , $\mathrm{1250}$ , and $\mathrm{1500}$ , respectively. Regardless of edge failure rate, Exhaustive routing shows $\mathrm{50}\%$ to $\mathrm{100}\%$ better reachability. Reachabilities of VT routing, Phase $\mathrm{1}$ routing, and Exhaustive routing are decreased by $\mathrm{42}\%$ , $\mathrm{47}\%$ , and $\mathrm{56}\%$ , respectively, as edge failure rate increases from $\mathrm{0.0005}$ to $\mathrm{0.0015}$ .

Figure 15

Comparison of fault-tolerant routing reachability with buffer length $\mathrm{5}$ and $\mathrm{0.05}$ packet generation rate according to edge failure rate.

7. Conclusions

In networks, communication failures are possible scenarios. The existing vertex-transitive routing for Borel Cayley graphs, described in Section 2, cannot efficiently tolerate node/link failures. We proposed a fault-tolerant routing algorithm, the “Exhaustive routing,” that uses an identical routing table at each node and exploits multiple shortest paths.

Exhaustive routing has two phases. In Phase $\mathrm{1}$ , packets are routed through the shortest path existing in the Borel Cayley graph. When all shortest paths from the BCG are disconnected, Phase $\mathrm{2}$ of Exhaustive routing is used to exploit possible paths besides the shortest paths in the Borel Cayley graph. Through simulation, we found that the proposed Exhaustive routing showed $\mathrm{20}\%$ to $\mathrm{350}\%$ better routability than that of the vertex-transitive routing with various amount of link failures. Regarding the average hop count, Exhaustive routing showed just $\mathrm{30}\%$ longer than the Optimal routing. We also showed good network topology properties of Borel Cayley graph comparing with torus and de Bruijn graphs with various traffic patterns.

When we consider simultaneous multiple packets flowing, Exhaustive routing showed over $\mathrm{50}\%$ better reachability with certain packet generation rate. However, with high packet generation rate, Phase $\mathrm{1}$ routing showed better reachability because it sends packets along the guaranteed shortest paths of the original Borel Cayley graph. In summary, Exhaustive routing has good reachability and small average hop counts. Our proposed fault-tolerant routing algorithm makes it possible for Borel Cayley graphs to be deployed in realistic network scenarios.