Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Grados
Certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Video on the Internet

Loading...

Networks: Friends, Money, and Bytes

Universidad de Princeton

4.8 (85 calificaciones) | 16K estudiantes inscritos

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. All the features of this course are available for free. It does not offer a certificate upon completion.

Revisiones

4.8 (85 calificaciones)

5 stars
72 ratings
4 stars
10 ratings
3 stars
1 ratings
2 stars
1 ratings
1 star
1 ratings

PS

Mar 12, 2016

It is really a exceptional course which illustrates networking problems and answers with real life examples.

M

Jan 31, 2016

thanks to get world class education at home, my name is Mutlu from turkey

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.

Video on the Internet9:33

IPTV and VoI13:48

Video Compression30:05

Impartido por:

Mung Chiang
Professor
Christopher Brinton
Lecturer

Transcripción

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.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados