×

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.
MSC:
68M10 Network design and communication in computer systems
68M07 Mathematical problems of computer architecture
90B18 Communication networks in operations research
PDF BibTeX Cite
Full Text: DOI