Signal Flow Graphs for Path Enumeration in Multihop Networks: A Comparison of the Perfect Shuffle and the Manhattan Street Networks.

For the analysis of adaptive routing (in particular, hot-potato routing) in packet-switched networks, it is important to know the number of paths of length k from any one node to another. It is desirable that this number be large so that routing strategies can provide alternate paths to reach a node in case of congestion or link failure, with increased reliability, recoverability, and reduced delay. This problem is similar to calculating the number of erroneous paths of length k in the decoder state trellis in convolutional channel coding. To calculate path lengths in networks we use a signal flow graph method, similar to that used for calculating distance properties of convolutional codes. The technique only uses topological information about a network, and is independent of whether the network uses datagrams or virtual circuits. Using this method to compare 64-node Manhattan Street and Perfect Shuffle networks, we derive the following conclusions: in the Perfect Shuffle network, (i) there exist more paths to reach a node from any other in k hops, (ii) there exist a larger number of distinct nodes reachable from a node in k hops, and (iii) in most cases, there are more paths to reach each of those distinct nodes in k hops than the Manhattan Street network. In addition, the Perfect Shuffle has smaller maximum and average distance between nodes, and is more symmetric, as measured by the number of distinct transfer functions, than the Manhattan Street network.