Rearrangeable

Rearrangeable is a term used in the theory of multistage interconnection networks (MINs) to describe a network's ability to realize any permutation of its inputs to outputs by choosing appropriate internal connections, potentially requiring reconfiguration of existing connections.

In practice, a rearrangeable network can implement any specified mapping from inputs to outputs, but achieving a given permutation may require reconfiguring the crosspoints between stages. This contrasts with strictly nonblocking networks, where a new connection can be established without altering existing ones, and with blocking networks, where some permutations may be impossible without rearrangements.

A key distinction is between rearrangeable and rearrangeable nonblocking networks. A rearrangeable nonblocking network can realize any permutation by rearranging internal connections while guaranteeing that a new request can be accommodated without blocking after reconfiguration. Classic examples of rearrangeable, and often nonblocking, networks include the Benes network and the Clos network, both of which are designed to support scalable permutation routing with a fixed hardware size. The Benes network is specially structured to be rearrangeable nonblocking, allowing any input-output permutation to be realized with a feasible reconfiguration. The Clos construction provides rearrangeable nonblocking properties under appropriate sizing of its stages.

Waksman networks are another family of permutation networks known for being rearrangeable with a minimal number of switching elements. In telecommunications and parallel computing, rearrangeable networks underpin flexible, high-capacity routing, though they require control logic to determine an appropriate reconfiguration sequence.

Overall, rearrangeable networks offer a balance between routing flexibility and structural efficiency, enabling complete permutation routing through reconfiguration.