Cost Updates

Loading...

Do curso por Princeton University

Networks Illustrated: Principles without Calculus

40 classificações

Princeton University

Networks Illustrated: Principles without Calculus

40 classificações

What makes WiFi faster at home than at a coffee shop? How does Google order its search results from the trillions of webpages on the Internet? Why does Verizon charge $15 for every GB of data we use? Is it really true that we are connected in six social steps or less? These are just a few of the many intriguing questions we can ask about the social and technical networks that form integral parts of our daily lives. This course is about exploring the answers, using a language that anyone can understand. We will focus on fundamental principles like “sharing is hard”, “crowds are wise”, and “network of networks” that have guided the design and sustainability of today’s networks, and summarize the theories behind everything from the social connections we make on platforms like Facebook to the technology upon which these websites run. Unlike other networking courses, the mathematics included here are no more complicated than adding and multiplying numbers. While mathematical details are necessary to fully specify the algorithms and systems we investigate, they are not required to understand the main ideas. We use illustrations, analogies, and anecdotes about networks as pedagogical tools in lieu of detailed equations. All the features of this course are available for free. It does not offer a certificate upon completion.

Na lição

Routing Traffic through the Internet

It is hard to overstate the impact that the Internet has had on society. In this lesson, we will overview the fundamental concepts behind the way the Internet is designed. We will also take a look at routing, which is the process of determining how packets of information are transported.

Conheça os instrutores

Christopher Brinton
Lecturer
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

Alright, so now here's the crucial point

in the development of development forward algorithm.

You know, when we talk about cost updates.

So after one hop, a router has the following information.

It has the cost it takes to get to each of its neighbors.

And it has the cost it takes each of its

neighbors to get to the destination in at most one hop.

So, the question is, can we generalize this and can we use this information

to try to figure out how long it'll this

router to get to the destination in two hops.

'Kay?

because we already computed for one hop and we said okay well some of

the nodes I know that I can get to the destination in one hop.

We said DNE can get there in one hop.

So can we use that information, then, to backtrack and say, okay

for the other nodes can we use the fact that DNE can

get there in one hop and they're cost to be able to

figure out what the cost is going to be for the rest of them?

Rather than have it construct an entire view of

the network for the router which would be basically impossible.

So the real, real key here though is that adding each

of these is going to give the node the two-hop cost right.

So we have the cost that it takes each node to get to its neighbors, and then we

have the cost that it takes each of the neighbors to get to the destination.

Right, like in this example right here. And stored as S right, it takes S cost

of W to get to A, we're going to say in general.

say W is 3 and Y is 5, you don't want to deal with symbols here.

so then we know, S is going to know it's path cost to get to A.

And it's going to, S make that somehow.

It's just knows it's a number. It knows that it's 3.

And S knows how, what the cost is to get to B, it knows that it's 5.

And then, if A has already figured out how,

what the cost is to get to N in, let's say, three hops, just as an example.

So, we're doing the three hop case right here for X or for A to N, and we know that

in three hops the cost to get from A to N is 16, say.

well then, if A can get to N and it costs 16 three hops, then

W should be, or then S should be able to get to N And the cost

of 3 plus 16 in 4 hops.

So really we're just adding this link on

to As path already, because we're going to go

to A and then A already knows how to get to N and his minimum call.

So we'll just use A's minimum cause to get to N in order to go from S and

again we're blurring this here because there could be

so many routers in between, but it wouldn't matter.

That's the whole beauty of this, this is, it doesn't matter what's in between.

S doesn't need to know what's past A.

He just needs to know the cost to get to A,

and he needs to know what A is saying the cost to

get to N is, or what, not, A doesn't have to

be saying it necessarily, just needs to know what the cost is.

So, that's the power of the Bellman-Ford algorithm.

So that we can do this dynamically, it's like a dynamic programming problem.

So, from source F to N, as we said through A it's going to cost

W plus X and through, B it's going to cost then Y plus Z, right?

And this could maybe be,

maybe with the three hop case again, so three hops.

And again, three hops is going to be what we're saying.

It's, it's in at most three hops, so the, the cost could be

lowest for two hops, in which case we're not going to add another hop in.

but it's just giving us more information, so, in three hops B can get to N in

cost Z, so then Y plus Z is going to give this cost, Y plus Z, whatever that is.

And then this is W plus X.

So whichever of the two is smaller, that's the one you're going to choose.

So, if Y plus Z is smaller than W plus X, then S is going to

say, okay, whenever I have something destined for

N, I'm going to choose to forward to B.

That's how I'm going to populate routing table.

If something is going to N, in my IP address table.

'Kay?

if, if somethings going to end, if something comes to

me, then I know I'm going to forward to B next.

Or, likewise, if it was

the opposite and A was the minimum cost and if say if something comes

from N you would change the entry in the round table and say A.

So you'd build again a whole table based upon different destinations.

And then you can say which road you're going to go to next.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play