MULTICAST ROUTING IN 3-STAGE CLOS ATM SWITCHING-NETWORKS

An approach to building a large ATM switch is to simply set up a regul arly-structured network in which smaller switch modules are interconne cted. Routing is an issue if there are multiple paths from any input t o any output in such a network. We focus on the 3-stage Clos network, not only because it is the architecture of choice for several potentia l switch manufacturers, but also because its high connectivity poses a stringent test on routing algorithms. One optimal and two heuristic a lgorithms have been designed and tested. Our results show that the heu ristic algorithms can find multicast routes that are close to optimal within a response time that is significantly lower than that of the op timal algorithm. Further analysis of the experimental data suggests a hybrid implementation in which the optimal and heuristic algorithms ar e run in parallel with a set time limit. Finally, although this paper is motivated by the Clos switching network, the algorithms and the dis cussion here also apply to communications networks with a two-hop stru cture.