1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96)
Establishing switch-disjoint connections in stage-controlled Banyans
Beijing, CHINA
June 12-June 14
ISBN: 0-8186-7460-1
Chunming Qiao, Dept. of Electr. & Comput. Eng., State Univ. of New York, Buffalo, NY, USA
Luying Zhou, Dept. of Electr. & Comput. Eng., State Univ. of New York, Buffalo, NY, USA
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.
Index Terms:
computational complexity; multiprocessor interconnection networks; parallel algorithms; switch-disjoint connections; stage-controlled Banyans; Banyan networks; photonic switching; polynomial time complexity; parallel algorithms
Citation:
Chunming Qiao, Luying Zhou, "Establishing switch-disjoint connections in stage-controlled Banyans," ispan, pp.110, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996