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.