0:00

This is a Clos network.

Â It is a Clos network denoted with the following representation.

Â It is a three three four Clos network.

Â Three three four.

Â And in general Clos network is

Â represented by three numbers 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 they're also r of them.

Â 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 and 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.

Â Now what about the connectivity pattern among these small switches?

Â Basically each of the output,

Â here upper 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 E1 for each output port of each input switch.

Â And that is why each of these middle switches r by r

Â because you need all of 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 is 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 multi-staged dense connectivity.

Â A lot of rich connectivity patterns.

Â And of course in this case it is a three staged Clos network.

Â You can have actually any odd number.

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

Â otherwise I have five staged for example, seven, nine stages.

Â In fact in the example coming up we see a

Â recursively expanding a Clos network.

Â By adding more stages you can reduce the size of each stage switch so thats the tradeoff.

Â Again back to this example we've got a three staged of

Â three three four of Clos network and in general we have

Â a three stage and n m r and there recursively expand

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

Â This is such an 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,

Â without showing you the answer first,

Â what we really need is basically that there are

Â enough middle switches and they're m of them so we need m to be big enough.

Â We need m to be big enough compared to

Â basically the number of inputs that can be supported per switch.

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

Â So we want m to be sufficiently big.

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

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

Â N has to be greater than or equal to two n minus one.

Â Simple relationship.

Â In fact if it is perhaps more instructive to write down

Â this two n minus one as two times n minus one plus one.

Â Now of course algebraically these two expressions are the

Â same but this is actually the logic,

Â the reasoning, behind the derivation of this simplified answer.

Â Let's look an example.

Â This is a little weird Clos network but suffices to

Â illustrate the 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 input side,

Â two switches each is two by three.

Â on output side is three by two and therefore there are

Â three input middle switches each of which 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,

Â denoted by the blue lines,

Â already and then there's a new incoming traffic.

Â How can I make sure that I can connect that new incoming traffic

Â from its input port to the output port?

Â So again the terminology these are the ports.

Â These are the input ports.

Â 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 ports of the middle stage switch.

Â And same thing on the output stage switch too.

Â The blue line shows a particular configuration already.

Â For example suppose there is a traffic that arrives on input on this input port.

Â Okay. Altogether we've got four input ports which we can label them as one,

Â two, three, four, or following binary number notations zero, one, two, three.

Â Let's say zero, one, two, three.

Â So arrives at port one and 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 on the lower input port to the middle output port of this input 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 and the middle layer and the middle stage.

Â And now it needs to go to this output port and therefore it needs to

Â first arrive at this output switch and the way to arrive this output switch,

Â is there's only one way,

Â which is to connect over here instead of going down.

Â That would be go into 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 way.

Â 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.

Â And the way is to first connect it this way on the input side and

Â then it naturally leads to this middle switch, the top one,

Â you're connected doing across that will give you to

Â the correct output switch to another cross,

Â this gives you the correct output port.

Â Same story over here.

Â 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 and go from two to one and go from three to two.

Â This is quite 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 are all taken then there can be no arrivals so there's no problem.

Â But there is a vacant input port and there is a vacant output port.

Â And this arrival exactly wants to go from this vacant input to

Â that vacant output from input port zero to output port three.

Â So how do I go from here to here?

Â Well I can actually have a choice, right?

Â I can for example go

Â from here or here and then that will lead to me

Â here and then I can go down this way and then I can go down this way.

Â Now our point is not to show,

Â hey I can solve this puzzle.

Â This puzzle is too easy to solve.

Â The points that now illustrate a common thread and that is when

Â all the other input ports are already occupied they're basically n minus one of them,

Â you can't to this switch.

Â And all the output ports all the other ports are occupied.

Â And this at the other switch,

Â that's another n minus one.

Â These n minus one,

Â in this case is, only one,

Â and it's two could have gone through,

Â must have gone through some middle switches, okay.

Â Same thing here. And they could have gone to different input middle stage switches.

Â Indeed in this case this one has gone through

Â this middle stage switch this one through this middle stage switch.

Â 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 middle stage switch.

Â You have to use another one.

Â What if you don't have another one then you may be stuck.

Â You may be blocked but if you do have

Â another middle switch then you will always have degree of freedom to be non-blocking.

Â And that is to say if we have already got two times n minus one,

Â meaning n minus one from

Â the input ports of the input switch shared with this new traffic.

Â Same thing for the output.

Â They all go through different middle switches.

Â So you already got two times and 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 bond two times n

Â minus four in 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 n minus one for non-blocking.

Â Where is r? Right. I know that for the entire Clos network

Â there are basically n times r number of

Â input ports total and n times r output ports total.

Â So if I want to really build a Clos network to take in a lot and

Â connect to a lot on output side if n cannot be too big.

Â Okay because n must be small

Â enough so that two n minus one smaller than m. If n cannot be too big.

Â Maybe r can be big and indeed there is

Â nothing that prevents you from running really big r,

Â you can make r a thousand okay.

Â But then the problem with that as you can

Â see is that you're going to have really big middle switches.

Â Okay. Cause 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 at

Â the middle switch into in-turn multistaged switch network.

Â So we can recursively apply

Â Clos network ideas in order to tackle this large r by r middle switch.

Â So that's question number one, right.

Â Question number two is,

Â this is with non-blocking,

Â what about rearrangably non-blocking?

Â We should have a looser condition,

Â m that doesn't have to be as big as two n minus one anymore.

Â And indeed, as lies m is bigger than or equal to n.

Â This is almost basically a half a rate of

Â reduction in the how stringent this condition need to be.

Â As long as m is bigger than go to n,

Â as long there are as many input middle stage switches as

Â the number of input ports per input

Â switch then Clos network has rearrangably non-blocking.

Â And the way to prove this is through a constructive algorithm in the homework product.

Â 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 128 by 128 or something,

Â then well build it and then when say I can't do it anymore

Â then don't build bigger switches connect it into Clos network.

Â This is one of the commonly used architecture in cloud

Â called virtual layer two, VL2, recently developed.

Â And there are many other alternatives,

Â variants and alternatives, Clos network is

Â not the only kind of typology you can have for interconnection network.

Â In a vast material part we will say a few more words matters.

Â Now let's run through a particular example of building and then

Â expanding and rearranging and then folding Clos network.

Â Let's start with a three stage Clos network.

Â Okay? Suppose we want to build eventually eight by

Â eight and we only want to use a small two by two switches.

Â Okay? So how do we do that?

Â Well here is one starting point.

Â Lets 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 that 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. 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 say,

Â that's it, that's my answer.

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

Â Okay. Actually that was in practice four by four is still fine but

Â our numerical example would have to be small and therefore let's say four by

Â four is too big already and we want to replace it by two by two.

Â So how can we replace it with a bunch of two by twos.

Â Well we can recursively apply the idea of Clos network.

Â Let's now build a three staged Clos network.

Â That is actually two two two.

Â So each input is two by two each output switch

Â is two by two and the middle one is also two by two.

Â And then you get the full mesh connectivity

Â between input the middle and between middle and output stage switches.

Â Now you've got six two-by-two switches to get one four by four switch functionality.

Â So you're going to substitute

Â this thing back into each of these two middle stage switches.

Â And this is what you get.

Â It you just substitute this collection of

Â six two-by-two switches as one four-by-four 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 gist 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've got a five staged composed by

Â two three stage Clos networks and now everything is two by two,

Â two by two, two by two, and so on.

Â And you can see the connectivity pattern is quite rich right.

Â Within each 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 by rearranging

Â appropriately the position of the switches in stage two and stage four.

Â Okay. Now we can just use

Â input middle and output stages because there are five stages now.

Â Stages one, two, three, four, five.

Â If we rearrange the stages to four switches a little bit we receive the following path.

Â Okay, so basically what we do is to move this,

Â okay, up and move this down.

Â Then we have the following connectivity pattern.

Â And now we do the last the 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 are actually bidirectional?

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

Â hey the left hand side of the 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 and you can put this part,

Â it's kind of hard to illustrate this three dimension 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 bidirectional.

Â All these links bidirectional.

Â 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 pointing from left to right would be pointing from right to left.

Â Now that is the final simplified version that we have

Â this becomes a network with 12 two-by-two

Â switches making all together a one eight by

Â eight switches and we call this folded Clos network,

Â so-called fat tree not to be confused by the use of the terminology tree.

Â Fat tree is not a tree it can achieve what a tree cannot achieve.

Â Fat tree is just a folded Clos multi-stage interconnection network.

Â