On the Existence of Unknown Rearrangeable Banyan-type Networks
Satoru Ohta, Naoki Tsuji · 2023
A banyan-type network is a multistage switching network, made up of unit switches with two inputs and two outputs. The network has been used as a component of various communication and computer systems. Banyan-type networks are categorized into blocking and rearrangeable networks. A rearrangeable network is significant for some applications because it can connect inputs and outputs for any request without blocking. However, previous studies have not completely defined and categorized the class of rearrangeable banyan-type networks. This study presents a systematic scheme for discovering previously unreported rearrangeable banyan-type networks. The presented scheme uses the conjunctive normal form–satisfiability (CNF–SAT) modeling of connection routing to test the rearrangeability. In addition, to find truly new rearrangeable networks, networks found to be rearrangeable are compared with known rearrangeable networks by a graph isomorphism algorithm. The scheme applies these processes to networks generated exhaustively by assigning link configuration rules expressed as bit permutations to interstage links. New rearrangeable networks will be discovered if they exist by performing the scheme. The results of performing the scheme are also presented. The result reveals previously unknown networks, which are highly probably rearrangeable and are not isomorphic to any known rearrangeable networks.