Multicast in wormhole-switched torus networks using edge-disjoint spanningtrees

A tree-based multicast algorithm for wormhole-switched networks which makes use of multiple edge-disjoint spanning trees is presented. The disjoint sp anning-tree multicast, or DSTM, algorithm provides deadlock-free Multicast routing that is fully compatible with unicast. The application of the DSTM algorithm to 2-dimensional torus networks is considered. A family of constr uctions of two spanning trees in the torus is given along with it formal pr oof of their edge-disjointness. Two constructions from this family are sele cted and shown to produce diameters no greater than twice that of the torus . Flit-level simulation results are presented to show that DSTM Outperforms the best single spanning tree multicast approach by LIP to it factor of tw o. The DSTM algorithm is also simulated for different spanning tree constru ctions. The results show that our novel tree construction is significantly better for multicast than those produced by I general tree construction met hod that applies to arbitrary-topology networks (J. Roskind and R. Tarjan, Math. Oper. Res. 10 (Nov. 1985), 701-708). Finally, two approaches to provi ding single link fault tolerance with DSTM are presented and evaluated. (C) 2001 Academic Press.