Signal flow graphs for path enumeration and deflection routing analysis in multihop networks
- 13 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1022-1029
- https://doi.org/10.1109/glocom.1989.64114
Abstract
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 Author(s) Ayanoglu, E. AT&T Bell Lab., Holmdel, NJ, USAKeywords
This publication has 3 references indexed in Scilit:
- Multihop lightwave networks: a new approach to achieve terabit capabilitiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Sharp approximate models of deflection routing in mesh networksIEEE Transactions on Communications, 1993
- Regular Mesh Topologies in Local and Metropolitan Area NetworksAT&T Technical Journal, 1985