This is a Clos network. It is a Clos network, donated with the following representation, okay? It is a 3, 3, 4 Clos network. Okay, 3,3,4 and in general Clos networks represented by three numbers. All are specified by three numbers N, M and R. These are all positive integers and each input switch is N by M and there are R of them. Each output switch by symmetry is M by N and there also R. 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. 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. 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. 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. Now, a couple of remarks. First of all. Say, M greater than or equal to 2 N-1 is for non blocking. Where is R? I, I know that for the entire Clos network. There are basically N times R number of input ports, total in it. N times R output ports total. So if I want to really get a Clos network to take in a lot and connect to a lot on other side, N cannot be too big, okay? Because you know N must be smaller, small enough so that 2 N-1 is smaller than N, if N cannot be too big, may be R can be big and indeed there is nothing that prevents you from running a really big R, you can make R a 1000 okay, but then the problem with that. As you can see is that, you're going to have really big middle switches. Okay because the middle switches are R by R. So, true you can make R really big but then you've got really big r by r middle switches. Maybe you can do something about it. And, indeed, in a minute, we'll see how we can recursively expand the input of the middle switch into, inter multi stage switch network. So it can recursively apply Clos network ideas. And too in order to tackle this large R by R middle switch, so that's question number one, right. Question number two is, this is for non-blocking. What about rearrangably non-blocking? 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, okay? All these links bi-directional. Then you actually get back to three stages because whatever goes out here, you can just view that as the folded version, except the arrows instead of pointing from left to right will be pointing from right to left. Now that is the final simplified version that we have. This becomes a network with twelve 2 by 2 switches, making all together a one 8 by 8 switches. And we call this folded Clos network, so called, fat tree. Not to be confused by the use of the terminology tree. Fair tree is not a tree. It can achieve what a tree cannot achieve. That tree is just a folded Clos multi-stage interconnection network.
