Rearrangeable Networks The class of rearrangeable networks is here described, that is those networks in which it is always possible to set up a new connection between an idle inlet and an idle outlet by adopting, if necessary, a rearrangement of the connections already set up. The class of rearrangeable networks will be presented starting from the basic properties discovered more than thirty years ago (consider the Slepian–Duguid network) and going through all the most recent findings on network rearrangeability mainly referred to banyan-based interconnection networks | Switching Theory Architecture and Performance in Broadband ATM Networks Achille Pattavina Copyright 1998 John Wiley Sons Ltd ISBNs 0-471-96338-0 Hardback 0-470-84191-5 Electronic Chapter 3 Rearrangeable Networks The class of rearrangeable networks is here described that is those networks in which it is always possible to set up a new connection between an idle inlet and an idle outlet by adopting if necessary a rearrangement of the connections already set up. The class of rearrangeable networks will be presented starting from the basic properties discovered more than thirty years ago consider the Slepian Duguid network and going through all the most recent findings on network rearrangeability mainly referred to banyan-based interconnection networks. Section describes three-stage rearrangeable networks with full-connection FC interstage pattern by providing also bounds on the number of connections to be rearranged. Networks with interstage partial-connection PC having the property of rearrangeability are investigated in Section . In particular two classes of rearrangeable networks are described in which the self-routing property is applied only in some stages or in all the network stages. Bounds on the network cost function are finally discussed in Section . . Full-connection Multistage Networks In a two-stage FC network it makes no sense talking about rearrangeability since each I O connection between a network inlet and a network outlet can be set up in only one way by engaging one of the links between the two matrices in the first and second stage terminating the involved network inlet and outlet . Therefore the rearrangeability condition in this kind of network is the same as for non-blocking networks. Let us consider now a three-stage network whose structure is shown in Figure . A very useful synthetic representation of the paths set up through the network is enabled by the matrix notation devised by . Paull Pau62 . A Paull matrix has ri rows
