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.
Video on the Internet
Loading...
Del curso dictado por Princeton University
Networks: Friends, Money, and Bytes
59 calificaciones
De la lección
Which Way to Watch Video on the Internet?
We have seen that the Internet provides a "best effort" service. In this lecture, we will look at how it supports video distribution, which often imposes stringent demands on throughput and delay.
Conoce a los instructores
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
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.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
