) 4 (100) 4 (100) 5 (101) 5 (101) 6 (110) 6 (110) 7 (111) 7 (111) FIGURE 7.12 An example of perfect shuffle permutation. Switching Systems: Architecture and Performances First-stage Banyan FIGURE 7.13 Scheme of the 8 X 8 Banyan network built starting from two 4 X 4 basic elements. The input and output ports of the building blocks are tagged with the numbers from 0 to p - 1 (0 and 1 in our case). The first step of the Banyan switch creation generates a 4x4 Banyan switch by connect- ing a stack of two building blocks (the first stage) with a stack of two building blocks (the second stage) with a perfect shuffle connection. The scheme of the 4x4 Banyan network is reported in Figure 7.13 inside the circle. After the first stage, the procedure can be iteratively repeated building at stage kth a 2(k+1) x2(k+1) Banyan switch by connecting with a perfect shuffle a first stage composed by 2(k-1) building blocks and a second stage composed by two Banyan switches that have 2k x 2k ports. The result of the second step of this procedure is also reported in Figure 7.13. 7.2.3.1 Routing through a Banyan Network Automatic routing is one of the most useful characteristics of a Banyan network [20]. Let us imagine that the address of a connection request arriving at an input port is expressed as a number of k elements in base p (k bits in our particular case). The routing through the switch fabric happens in this way: the building block of the stage ith reads only the ith bit of the address and switches the connection up if this is 0 and down if it is 1 (in case p>2, the only thing to remember is that the building block would have p outputs). The scheme of the obtained routing is reported in Figure 7.14. In a dynamic application, the arbiter is always needed to solve conflicts and to assign local priorities, but no calculation is needed to solve the routing problem. This property makes Banyan networks among the faster switch fabrics. The automatically calculated route, however, is the only route existing between the input and the o