0:49

And each middle switch, is of course by dimensionality R by R and there are M of

Â them. So, if you give me three numbers I can

Â then draw a Clos network. Now, no wonder in this specific case we

Â have three, three, four, each input N output switch is three by three and there

Â are four of them. Each middle switch is four by four and

Â there are three of them, okay? Now, what about the connectivity pattern

Â among these small switches? Basically each of the output here,

Â output port from each input switch is connected to each of the middle switches.

Â And that's why there are M of these middle switches because you need E one

Â for each output port of each input switch.

Â And that is why each of these middle switches is R by R because we need all of

Â the them in order to face all of these input switches.

Â And that is exactly symmetrical on the side facing the output.

Â So this is a very dense connection. Now of course, it's not full mesh, okay?

Â I'm not connecting every switch with every other switch for example, input

Â output switch are not directly connected. But it is staged, okay?

Â It is a multistage. Dense connectivity, a lot of rich

Â connectivity patterns and of course in this case it is a three stage Clos

Â network. You can have actually any odd number.

Â Okay not one would be too much of a trivial case.

Â Other working at have five stage for example seven, nine stages.

Â In fact in the example coming up we'll see a recursive hopefully expanding a

Â Clos network. By adding more stages you can reduce the

Â size of each stage switch. So that's the trade off.

Â Again, back to this example, we've got a three stage 3, 3, 4 Clos network.

Â And in general tab a three stage NMR, and then recursively expand that.

Â So that it starts to use smaller and smaller switches.

Â This is such a rich connectivity pattern that has become a very useful tool in all

Â kinds of study around interconnection network.

Â 3:40

For example, what kind of condition can guarantee non-blocking properties in a

Â Clos network? Well, if you think about it, okay?

Â Without showing you the answer first, what we really need is basically that

Â there are enough middle switches, and there are M of them, so we need M to be

Â big enough. Need M to be big enough compared to

Â basically the number of inputs that can be supported for switch or by symmetry

Â the number of outputs that can be supported by each output switch.

Â So we want M to be sufficiently big, okay?

Â M should be bigger than some kind of function, of n.

Â It turns out that there's a very simple answer.

Â And needs to be greater than or equal to 2 N minus 1,

Â simple relationship. In fact, it is perhaps more instructive

Â to write out 2N minus one as two times N minus one plus what.

Â Now, of course, algebraically, these two expressions are the same but this is

Â actually the logic, the reasoning behind the duration of this simplified answer

Â here. Let's look at example, this is a little

Â weird Clos network that suffices to illustrate a point with a very small

Â graph. So this is a graph of a three stage

Â interconnection network following Clos topology.

Â You've got, on the M plus side two switches.

Â Each is 2 by 3, okay? On the opposite side it's three by two.

Â And therefore there are three input of middle switches each of which is,

Â is two by two, okay?

Â So, now what we want to do is to say that, if

Â I configure this Clos network in a certain way.

Â You know, by the blue lines are ready. And then there's a new incoming traffic,

Â how can I make sure that I can connect the new incoming traffic from its input

Â port to the output port. Okay?

Â So, again, the terminology these are the ports.

Â 6:07

These are the input port, these are the output ports.

Â This is a switch, so they are of the input stage switch.

Â This is input port, output port, input port, output port okay.

Â So they are the input and output port of the middle stage switch and same thing on

Â the output stage switch two. The blue line shows a particular

Â configuration already for example suppose there is a traffic that comes arrives on

Â input, this input port, okay? All together we've got four input

Â ports which we can label them as one, two, three, four, or following binary

Â number notation zero, one, two, three. Okay?

Â And let's say zero, one, two, three. So it arrives at input port one, and

Â let's say its intention is to go to output port zero.

Â So how can I go from here to there through this maze?

Â Well, one possibility is I can connect it by connecting input port one, the lower

Â input port, to the middle output port of this input ses, switch A.

Â Okay? And then, since it's connected to the

Â middle output port of switch A, it's going to naturally go into the middle,

Â switch at the middle layer in the middle stage, okay?

Â And now, it needs to go to this output port.

Â And therefore, needs to first arrive at this output switch.

Â And the way to arrive at this output switch is, there's only one way, which is

Â to connect over here. Instead of going down.

Â That would be going to the wrong switch. So it goes to the correct output stage

Â switch. And now I just need to get to the correct

Â output port. And that is accomplished by connecting

Â this one. Okay.

Â So now you see this connectivity. And then similarly there are two other

Â existing end to end traffic already established.

Â From this input port to going to this output port,

Â okay? And the ways to first connect it this on

Â the input side, and then it naturally leads to this.

Â Middle switch the top one. You connect doing a cross.

Â And that will give you to the correct output switch to another cross.

Â This gives you the correct output port. Same story over here.

Â Okay. In fact you see that,

Â the total input port counted from zero to three basically shows this pattern.

Â You go from one to the output port which is zero.

Â You go from two to one. You go from three to two.

Â This is called a permutation. If you write them in binary notation, you

Â will see. But, that's not the point here.

Â The point is now there's a new arrival, okay?

Â Arriving at a vacant input port. If they're all taken then there no can be

Â no arrivals. But there is a vacant input port and

Â there's a vacant output port. And this arrival exactly wants to go from

Â this vacant input or that vacant output from input for a 0 to out for 3.

Â 9:12

So how do I go from here to here? Well, I can actually have a choice,

Â right? I can for example go from here over here,

Â and then that would lead to me here, and then I could go down this way, and then I

Â could go down this way, right?

Â Now, our point is not to show, hey I can solve this puzzle.

Â This puzzle is too easy to solve. The point is to now illustrate a common

Â thread. And that is, when all the other input

Â ports are already occupied, okay? And there are basically N minus one of

Â them, okay add this switch.

Â And all the output ports, all the other output ports are occupied, and this, at

Â the other switch, okay? That's another n minus one.

Â These n-1, in this case it's only one because n is 2 could have gone through,

Â must have gone through some middle switches, okay, same thing here.

Â And, they could have gone through different input middle stage switches.

Â Indeed, in this case this one gone through this middle stage switch, this

Â gone through this middle stage switch. Okay, so both switch B and C in the

Â middle stage are occupied and you could have an input pattern where in order to

Â reach from this to that point you have to, you cannot reuse any of these

Â existing little stage switch. You have to use another one.

Â Well if you don't have another one you may be stuck, you may be blocked.

Â But if you do have another middle switch then you will always have a degree of

Â freedom to be non-blocking. And that is to say, if we have already

Â got two times N minus one, meaning the N minus one from the in ports of the input

Â switch shared with this new traffic. Same thing with the output.

Â They all go through the middle switches. So you've already got two times N minus

Â one bracket middle switches. All you need is to have just one more

Â middle switch, and you'll be okay with non blocking.

Â And that is where we get this lower band. Two times m minus one bracket plus one,

Â which simplifies to two n minus one. If you have that many middle stage

Â switches. If you are M in Clos network

Â specification is at least as big as this number, then you have non blocking.

Â 13:38

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,

Â