zbMATH — the first resource for mathematics

Crosstalk-free rearrangeable multistage interconnection networks. (English) Zbl 1107.68019
Summary: The notion of Crosstalk-Free rearrangeability (CF-rearrangeability) of multistage interconnection networks is formally defined. Using the concept of line digraphs from graph theory, we show that the problem of crosstalk-free routing on any Bit Permutation Network (BPN) is always equivalent to the classical permutation routing problem on a BPN of smaller size and with fewer stages. We also show the CF-rearrangeability and minimality (in stage number) of three families of BPNs, including the dilated Benes network. Some necessary conditions for a BPN to be CF-rearrangeable are given, and a brief discussion of CF-rearrangeable networks with dilation in time or space is included.
68M10 Network design and communication in computer systems
68M07 Mathematical problems of computer architecture
90B18 Communication networks in operations research
Full Text: DOI