We should have a loser condition, and it doesn't have to be as big as 2N minus one

anymore. And, indeed, as long as M is bigger than

equal to N. This is almost basically a half of

reduction in the stringent, how stringent his condition need to be as long as N is

bigger than go to N. As long they are as many input middle

stage switches as the number of input ports per input

switch. Then, the Clos network is rearrange-ably

non blocking and the way to prove this is through a constructive algorithm in the

homework problem. Now, there are also many different

combinations. For example, you can first build a tree.

And then you can hook into a Clos network, to the point where you can build

a large enough switch. For example, you know, you know 128 by

128 or something, then we'll build it and then when say, I can't do it anymore,

then don't build bigger switches connected into Clos network.

This is one of the commonly used architecturing cloud, called virtual

layer two, okay? VR2 recently developed.

And there are many other alternatives, variants and alternatives.

Clos network is not the only kind of topology you can have for interconnection

network. In the advanced material part we will say

a few more words about those. Now let's run through a particular

example of building, and then expanding, and rearranging, and then folding a Clos

network. Let's start with a three stage Clos

network. Okay?

Suppose we want to build eventually eight by eight,

okay? And we'll only want to use small two by

two switches. Okay?

So how do we do that? Well here's one starting point.

And let's build a Clos network, where n is two, m is two and r is four.

So you got two by two switches on the input.

Two by two on the output. There are four of them, so you get eight

total input output ports. And therefore that means each input

middle switch is actually four by four, and there are two of them,

okay? That's fine.

You provide. All the connectivity possible between

input and middle switch and then between middle and output switches.

This is the Clos network and you can just stop here.

And you can say that's it that's my answer.

But suppose you say I don't want to build a four by four, okay.

Actually I've practice four by four is still fine but our numerical example will

have to be small. Therefore let's say four by four is too

big already. And we want to replace it by 2 by 2.

So how can we replace it with a bunch of 2 by 2s? Well, we can recursively apply

the idea of Clos network, less now, be it our stage three Clos network,

okay? That is actually 2. 2. 2 so each input is 2 by 2 each output switch is 2

by 2 and the middle one is also, 2 by 2. And then you get the full mesh

connectivity between input and middle and between middle and output stage switches.

Now you got 6 2 by 2 switches to get one 4 by 4 switch functionality.

So youre are going to substitute this thing,

okay? Back into each of these two middle stage

switches, and this is what you get, okay? you just substitute this collection

of six, 2 by 2 switches as one, 4 by 4 switch into the original.

So, this is combination of one Clos network, here with another Clos network,

a composition of two Clos networks. And now you get the jist that I can keep

recursively expanding from three to five stage, five to seven, seven to nine

stages, to make the middle stages small. Okay.

So now, we got a five stage composited by two, three stage Clos networks.

And now, everything is 2 by 2, 2 by 2 and so on.

And you can see the connectivity pattern is quite rich, alright, within each of

this inner loop Clos network and in the outer loop, too.

Now we can also stop here but we're going to do a little transformation.

Rearranging appropriately the position of the switches in stage two and stage 4,

okay? Now we can just use input middle and output stages cause they're five

stages now. So they just one, two, three, four, five.

If we rearrange the stages to 4 switches just a little bit we receive the

following pattern. Okay, so basically what we do is to move

this, okay, up and this down. Then we have the following connectivity

pattern. And now, we do the last step, which is

folding. We're going to do folding to say that,

you know what, so far we assume, up to this point, that all these links are

directional links. They flow from left to right,

from input to output, right? So all these are directional.

Now what if these links actually bi-directional?

Then, by symmetry, around the middle of stage three switches you can see that

hey, the left and side and right hand side are mirror images of each other,

right? The connectivity pattern, you can fold

them. In fact, if you really cut this out on a

piece of paper, you can fold it exactly, literally in the middle,

okay? You can put this part, it's kind of hard

to illustrate this 3-dimensional operation.

Fold it over here, okay?

Then what you end up with is actually something simpler.

You basically delete this part and you make all these links bi-directional,