Convergence routing on disjoint spanning trees

This paper presents a new design and a performance study for convergence ro uting in a general network with multiple spanning trees. Such an arbitrary topology network is used in the design of a switch-based LAN/MAN architectu re. Convergence routing can be viewed as a variant of deflection? routing w hich combines, in a dynamic fashion, the on-line routing decision with the traffic load inside network. However, unlike other deflection techniques, c onvergence routing guarantees that packets will reach (or converge) to thei r destinations, In particular, a new algorithm for constructing two edge-disjoint spanning trees of a given network is presented, and the resulting trees are used for convergence routing. It is shown empirically that convergence routing on t wo edge-disjoint spanning trees yields a better bound than a single spannin g tree, on the maximum route length. The construction of the two edge-disjo int spanning trees is done with specific strategies for improving the fault -tolerance and performance of the system. (C) 1999 Elsevier Science B.V. Al l rights reserved.