Rearrangeable nonblocking condition for multi-log\(_ 2 N\) multiconnection networks (Q1313749)

It is shown that by using multiple planes of a self-routing \(\log_ 2 N\) (\(N=2^ n\)) network in parallel a \(\text{multi-} \log_ 2 N\) network can be made rearrangeable nonblocking. In a \(\text{multi-} \log_ 2 N\) multiconnection network, multi-destination paths from an inlet can be set up on each \(\log_ 2 N\) network while, in a \(\text{multi-} \log_ 2 N\) one-to-one connection network each inlet can be connected to only one outlet. Up to now, the rearrangeable nonblocking condition has been investigated only for the \(\text{multi-} \log_ 2 N\) one-to-one connection network. And for the small-sized \((N\leq 16)\) \(\text{multi-} \log_ 2 N\) network, it was shown that the same rearrangeable nonblocking condition holds regardless of one-to-one connection or multiconnection. In this paper, the general rearrangeable nonblocking condition is derived for the \(\text{multi-} \log_ 2 N\) multiconnection networks. It is found that the general nonblocking condition is the same as that for the one- to-one connection. We have shown that the edge-coloring algorithm for the bipartite multigraph can be used for the nonblocking connection assignment (rearrangement) in the \(\text{multi-} \log_ 2 N\) multiconnection network. When combined with efficient edge-coloring algorithms, it is expected that the result of this paper will improve the practical design and operation of high-speed multicast switches in broadband networks.