You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions.
Clos Network and Non-blocking
Loading...
来自 Princeton University 的课程
网络：朋友、金钱和比特
59 个评分
从本节课中
What's Inside the Cloud?
The Cloud is another rapidly growing Internet service, allowing users to rent storage and computation resources inside the network. In this lecture, we will see how the large data centers operated by Cloud providers can be constructed from a multitude of small switches.
与讲师见面
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
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.
