Optimal Reservation Scheme Routing for Two-Rate Wide-Sense Nonblocking Three-Stage Clos Networks

The well-known Clos network has been widely employed for data communications and parallel computing systems, while the symmetric three-stage Clos network

C

(

n,m,r

) is considered the most basic and popular multistage interconnection network. A lot of efforts have been put on the research of the three-stage Clos network. Let us first introduce some related concepts.

The

three-stage Clos network C

(

n,m,r

) is a three-stage interconnection network symmetric with respect to the center stage. The network consists of

r

(

n × m

)-crossbars (switches) in the first stage (or

input stage

),

m

(

r × r

)-crossbars in the second stage (or

central stage

),

r

(

m × n

)-crossbars in the third stage (or

output stage

). The

n

inlets (outlets) on each input (output) crossbar are the

inputs

(

outputs

) of the network. Thus the total number the

inputs

(

outputs

) of

C

(

n,m,r

) is

rn

. There exists exactly one link between every center crossbar and every input (output) crossbar. These links are the

internal links

while the inputs and outputs are the

external links

of the network.