Scheduling length for switching element disjoint multicasting in Banyan-type switching networks

摘要

Due to the stringent bit-error requirement in fiber optics, preventing the forthcoming crosstalk at switching elements (SEs) is very crucial in the large-scale photonic switches. It this paper, we consider the SE-disjoint multicasting for a photonic Banyan-type switching network. This ensures that at most, one connection holds each SE in a given time thus, neither photonic crosstalk nor link blocking will arise in the switching network implemented with optical devices such as directional couplers, splitters and combiners. Routing a set of connections under such constraint usually takes several routing rounds hence, it is desirable to keep the number of rounds (i.e., scheduling length) to a minimum. Unfortunately, finding the optimal lengths is NP-complete in general, we propose an algorithm that seeks an approximation solution less than double of the optimal upper bound. The bound permits the Banyan-type multicasting network to be rear-rangeable nonblocking as well as crosstalk-free. It is given that the same bound guarantees wide-sense nonblocking for multicast connections, provided that the multicasting capability of the network is restricted to the second half of the whole stages, and strictly nonblocking for one-to-one connections, yet allowing to be free from the crosstalk. We also consider other crosstalk-free multicasting and the link-disjoint multicasting for the Banyan network. The theory developed in this paper gives a unified foundation on designing nonblocking and crosstalk-free photonic Banyan-type networks under the multicast connections.