Abstract: In this study, a simple method for optimal design of switch sizes in strictly non-blocking Clos three-stage interconnection network is presented. The numerical results show that the switch sizes of optimal multistage interconnection networks can be calculated very fast for any practical multistage interconnection network sizes. In other words, computes the optimal parameters that are required for selecting the switch sizes for all sizes of practical multistage interconnection networks. Because of the optimal selection of the switch sizes, the final results show a decrease in the crosspoints as well as the complexity of the internal connections of the interconnection network. It is also shown that when the number of inputs and outputs in the network changes, the number of inputs for the first stage and of the outputs for the third stage become equal. So the only parameter that undergoes changes is the number of switches. Therefore, the size of switches in a network proves to be independent from the total number of inputs and outputs in a network. In other words, if the total number of inputs changes, the size of switches will be fixed whereas the number of them will change.
INTRODUCTION
The Optimization of strictly non-blocking multi-stage interconnection networks has proved as an area of extensive research issues after the introduction and publication paper of Charles Clos (Hwang et al., 2003; Clos, 1953). Multi-stage Clos interconnection networks have been chosen because of their economically, technicality, regularity and having other capabilities such as modularity, scalability, fault-tolerance (Liotopoulos, 2001), having multipath tracking and routing, low latency and high efficiency (Liotopoulos and Logothetis, 2000). Tree-Hypercube (Almobaideen et al., 2007) and Mesh-Hypercube (Al-Mahadeen and Omari, 2004), are two types of this networks used extensively in telephone switching, optical fiber networks and parallel processing systems (Ngo, 2003).
One criterion for the complexity of multi-stage interconnection networks is the number of crosspoints for network switches; especially for networks which include various stages that are organized as a chain of switch elements in a network structure. Consequently to have the minimum complexity, the selection of switch sizes in multi-stage interconnection networks becomes very important. The conditions of blocking, rearrangeable non-blocking and strictly non-blocking have been theorized by V.E. Benes (Lee and Liew, 2002). Furthermore, in Hwang and Liaw (2000) have defined various modes of multi-stage interconnection networks such as blocking and rearrangeable non-blocking and strictly non-blocking. They have also described the conditions governing these modes.
In this study, the method for optimal designation of the switch sizes in strictly non-blocking Clos three-stage interconnection network, will be depicted by mathematical equations governing them. The numeral examples of the final optimal amounts will be explained for each number of practical interconnection networks. In other words, a discrete optimization method, based on the dynamic programming approach, is presented.
CLOS THREE-STAGE INTERCONNECTION NETWORKS
An MxN switching network simultaneously connects up to N input and M output pairs, which form a I/O permutation, using conflict-free paths within the network. A switching network is strictly non-blocking if there always exists a connection path from any idle input to any idle output in the presence of existing connections, regardless of how the existing connection paths were selected.
| Fig. 1: | Structure of a clos three-stage interconnection network C (n1, r1, m, r2, n2) |
A switching network is rearrangeable non-blocking if connections for any I/O permutation can be established under the condition that rearrangement of existing connections is allowed. Strictly non-blocking switching networks are suitable to be used as switches in circuit switching networks, whereas rearrangeable non-blocking networks are more cost effective for implementing packet switches for packet switching networks. A three-stage Clos network can be constructed from smaller crossbar switches arranged in three stages so that it can be rearrangeable non-blocking or strictly non-blocking depending on the number of middle-stage modules (Fig. 1). It is presented as C (n1, r1, m, r2, n2) and is called Clos three-stage interconnection network (Chang et al., 2006).
A Clos three-stage interconnection network is composed of three stages of switching elements. First stage includes r1 numbers of n1xm switches, the second stage has m numbers of r1xr2 and the third stage has r2 numbers of mxn2 switches. In its symmetrical form, this network includes N = M and r1 = r2 and n1 = n2 which is presented as C (n, r, m ) (Liaw et al., 1998).
THE SUGGESTED METHOD AND RESULTS
The complexity of multi-stage interconnection networks depends on the number of crosspoints in the structure of switches and generally the overall cost of interconnection networks is expressed by the number of crosspoints. Thus in this article a method for calculating the optimal size of the switches is proposed. In this network, the elements of switches are serially placed in various stages. The number of crosspoints in the general mode, i.e., C (n1, r1, m, r2, n2), in a Clos three-stage interconnection network is computed as follows:
(1) |
On the other hand, in Chang et al. (2004) the premise of non-blocking Clos three-stage interconnection networks is proved like this:
(2) |
Furthermore, with the premise of having N inputs and M outputs in Clos three-stage interconnection network we will have:
(3) |
(4) |
By placing the relations Eq. 2-4 in relation Eq. 1, we will come to this:
(5) |
In order to find the minimum crosspoints, the partial derivatives of relationship Eq. 5 should be equaled to zero in proportion to n1, n2:
(6) |
(7) |
The amounts of n1 and n2 are computed by solving the 6, 7 of equations. They, based the fixed amounts of M, N are shown in Table 1.
Since the number of inputs in each switch must be round at a Clos interconnection network, thus a program is written in C++ for finding the round amounts of n1(optimal) and n2 (optimal). This program shows the crosspoints in the minimum possible amount, which are shown in the Table 1.
Similarly if the Clos three-stage interconnection networks is symmetrical, i.e., presented as C (n, r ,m), the number of crosspoints equals with:
(8) |
The minimum crosspoints is computed by solving the following equation
(9) |
| Table 1: | The amounts of n1 (optimal) and n2 (optimal) in C (n1, r1, m, r2, n2) |
| Table 2: | The amounts of n(optimal) in C (n, r, m) |
| Fig. 2: | The amounts of n, n(optimal) and N in C (n, r, m) |
Table 2 and Fig. 2 shows the amounts of N, n and n (optimal), according to Eq. 9 and the fixed amount of N.
The amount of n (optimal), like the amounts of n1(optimal) and n2 (optimal), is computed by a program written in C++, in which for each N input and M output of the network, all the crosspoints to switches are computed and the minimum possible mode is derived and depicted in the above tables. Algorithm of this program begins with the local optimal amounts and moves toward finding the absolute optimal amounts. These optimal amounts have been described for each size of practical networks.
CONCLUSION
In this study, a simple method for optimal designation of input numbers and suitable size for each switch in Clos strictly non-blocking three-stage interconnection network was presented. The numeral examples represent the calculation of optimal input and output parameters for switches in Clos multi-stage interconnection networks for each size of practical networks. According to the final results, while the input and output amounts change, n1 and n2 are equal to each other and it is possible to depict the Clos three-stage interconnection network in general mode as C (n, r1, m, r2). Furthermore, for all the amounts of N = M, the amounts of n1 and n2 are fixed. In other words, if the total number of inputs changes, the size of switches will be fixed whereas the number of them will change. The results lead to making optimal switches with standard sizes. Similarly, in addition to Clos interconnection networks with more stages, one can compute the above-mentioned optimal amounts for blocking and arrangeable non-blocking Clos three-stage interconnection networks.