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.
||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:
On the other hand, in Chang et al. (2004) the premise of non-blocking
Clos three-stage interconnection networks is proved like this:
Furthermore, with the premise of having N inputs and M outputs in Clos
three-stage interconnection network we will have:
By placing the relations Eq. 2-4 in relation Eq.
1, we will come to this:
In order to find the minimum crosspoints, the partial derivatives of
relationship Eq. 5 should be equaled to zero in proportion
to n1, n2:
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
Similarly if the Clos three-stage interconnection networks is symmetrical,
i.e., presented as C (n, r ,m), the number of crosspoints equals with:
The minimum crosspoints is computed by solving the following equation
||The amounts of n1 (optimal) and n2
(optimal) in C (n1, r1, m, r2, n2)
||The amounts of n(optimal) in C (n, r, m)
||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.
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.