Establishing switch-disjoint connections in stage-controlled Banyans

In this paper, we study the problem of establishing switch-disjoint connections in Banyan networks under stage control, which is especially applicable to photonic switching technology. Since a set of arbitrary connections may not be established simultaneously, one may have to establish them in several rounds. It is desirable to use as a few rounds as possible. Three algorithms called Greedy, Odd-Even and Optimal are studied. The first two algorithms perform well when the number of connections to be established is small and large, respectively, but perform poorly when otherwise. The third algorithm is derived from the Odd-Even algorithm and can establish any set of connections in a minimal number of rounds with a polynomial time complexity. Both analysis and simulations are conducted to evaluate these three algorithms and the results are presented.