Section 13.3. Blocking Switch Fabrics

13.3. Blocking Switch Fabrics

Although, a crossbar can be deployed solely as a switch fabric, it may also be used to construct other multistage switch fabrics, with the trade-off of cost versus higher blocking. This section looks at types of blocking switches: Omega networks , Banyan networks , Delta networks , and Bene networks .

13.3.1. Omega Network

The Omega network , _{n , d} , is shown in Figure 13.2 (a). Using _{d , d} = X _{d , d} , we define the Omega network by

Equation 13.3

Figure 13.2. (a) An Omega network with an example of its routing; (b) a Banyan network with an example of its routing

In an Omega network , only one route exists between each input i _x and output o _x . This fact explains the potential for blocking. The path uniqueness in this network can be shown by the induction on the number of stages, s . The number of stages is exactly s = log _d n .

The Omega network has some useful unique properties. One is that the interconnection segment between each two consecutive stages is identical to that of all other segments. Each of these identical interconnection segments is configured with a shuffling property. The shuffling property is easy to understand: An interconnection link starting at the output number of a given crossbar stage ends at the input of the next crossbar stage with the same number but one step rotated to left. For example, consider the second interconnection segment between stages 1 and 2. In this segment, suppose that we are interested in finding the address of the crossbar input this link is connecting to. According to the rotation property, this address is obtained by one left rotation of 010, which results in 100.

The Omega network is also self-routing. The routing in this network is very simple and is achieved by comparing bit by bit between a source address and a destination address. At each stage, we look at the corresponding bits, starting at the most-significant bit (MSB) of the source and the destination addresses. If bits are the same, a message passes through; otherwise , it is crossed over. For example, consider a case with the source address 010 and the destination address 110, as shown in Figure 13.2. In the first stage, the message is crossed over, as the MSBs of the two addresses are different (0-1). In the second stage, the next corresponding bits are the same (1-1), so the message is sent straight along the crossbar. The case for the third stage is also the same as for the second stage but with corresponding bits of 0-0.

Using the method of blocking probability estimation presented in Section 7.6.4, we can easily obtain an estimation of blocking for the Omega network. Finding all the paths that connect any given input to a given output and assigning p to each and every link of paths as the blocking probability of that link, estimate the blocking probability for an Omega network, _{n , d} , to be 1 - (1 - p ) ^{s -1} , where s = log _d n .

13.3.2. Banyan Network

The Banyan network , Y _{n , d} , as shown in Figure 13.2 (b), is similar to the Delta network. Using Y _{d , d} = X _{d , d} , we define the Banyan network by

Equation 13.4

The Banyan network has some useful unique properties. Similar to the Omega network, the Banyan network also has the property of self-routing. Identical to Omega networks, the blocking probability for a Banyan network, B _{n , d} , is estimated to be 1 - (1 - p ) ^{s -1} , where s = log _d n .

13.3.3. Delta Networks

The Delta network consists of a network of crossbar switch elements with shared crosspoints, thus raising the possibility of blocking. The Delta network D _{n , d} , using d x d crossbars, X _{d , d} , and with n input/output ports, is defined by

Equation 13.5

In a Delta network, only one route between each input i _x and output o _x exists. This fact explains the fundamental reason for blocking. The path uniqueness in this network can be shown by the induction on the number of stages, s . The number of stages is exactly s = log _d n . As with Omega networks, the blocking probability for a Delta network, D _{n , d} , is estimated to be 1 - (1 - p ) ^{s -1} , where s = log _d n .

If s = 1, the network becomes D _{d , d} , or simply a crossbar. For s> 1, the output o _x belongs to one of d subnetworks denoted by D _{n/d , d} . Let s ₁ be the first-stage switch, in which i _x is an input. Since there is only one link connecting s ₁ to the subnetwork containing o _x , the only route connecting i _x to o _x is the route consisting of i _x , together with the route connecting to o _x , which is unique. As seen in Figure 13.3, the Delta network self-routing. A path from any input i _x to output o _y is performed by selecting links determined by successive digits of s label. This process is also reversible, so we can route from output o _y back to i _x by following the links determined by successive digits of s label.

Figure 13.3. (a) A D _8,2 Delta network with the realization of its routing; (b) extension of the Delta network to a B _8,2 Bene

13.3.4. Bene Networks

The Bene network consists of a combination of two networks: a Delta network and its mirrored overlapped in one stage, as shown in Figure 13.3. This network is capable of realizing all possible input/output permutations and is defined by B _{d , d} = X _{d , d} and expanded by

Equation 13.6

The recursive structure of the network leads us to decomposition of the routing problem into a set of smaller problems corresponding to each of the stages in the recursion. The top-level problem consists of selecting, for each connection, one of the d subnetworks B _{n/d , d} to route through. The routing problems for the d subnetworks can be solved independently. The following algorithm can be used to route a packet to a specific output port:

Define:

d	Crossbar switch element dimension
k	log d n
r	Number of stages, r = 2 log d n - 1
j	Stage number, j ˆˆ {1, 2, ..., r }
A	Output address of packet
a j	Address in stage j
v j	Bit vector specifying outputs that receive copies

Begin Bene Network Routing Algorithm

With this algorithm, packets in the routing network are guided to the requested outputs. As a result of its structure using Delta networks, we can derive the complexity of the Bene network by

Equation 13.7

knowing that is the number of crossbar switches per stage and that d ² is the complexity of d x d crossbars.