Signal flow graphs for path enumeration and deflection routing analysis in multihop networks

The method of signal flow graphs is applied to path enumeration and deflection routing performance analysis in multihop networks. The method uses a labeling of the edges of the network graph and the subsequent solution for the transfer function of the resulting signal flow graph. A Taylor series expansion of the transfer function yields the number of paths of a given length between the source and the destination. 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. On the other hand, the derivative of the transfer function yields the average number of hops in the network as a rational function of the probability of deflection of a packet. A fixed-point algorithm is used to solve for the probability of deflection as a function of the arrival rate of packets. Combining the two results permits the average number of hops to be obtained as a function of the packet arrival rate. Analysis examples chosen from proposed multihop network architectures are given.