Optimal Routing in Binomial Graph Networks

A circulant graph with n nodes and jumps j₁, j₂,..., j_m is a graph in which each node i, 0 les i les n-1, is adjacent to all the vertices i plusmn j_k mod n, where 1 les k les m. A binomial graph network (BMG) is a circulant graph where jk is the power of 2 that is less than or equal to n. This paper presents an optimal (shortest path) two-terminal routing algorithm for BMG networks. This algorithm uses only the destination address to determine the next hop in order to stay on the shortest path. Unlike the original algorithms, it does not require extra space for routing tables or additional information in the packet. The experimental results show that the new optimal algorithm is significantly faster than the original optimal algorithm.