Bellman-Ford Example

Loading...

Del curso dictado por Princeton University

Networks Illustrated: Principles without Calculus

43 calificaciones

Princeton University

Networks Illustrated: Principles without Calculus

43 calificaciones

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.

De la lección

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.

Conoce a los instructores

Christopher Brinton
Lecturer
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

And so to illustrate the Bellman-Ford algorithm let's walk

through an example and see some of the steps.

The example we're going to be considering is a graph of six routers and

we have one common destination, F, which is where we want to get to.

We want to try and find the minimum cost from each of the other routers to F.

And, so, the routers, again, we're going to

notate A through F, and, we want to

figure out the minimum cost path ,um, to F from each of A through E.

And,

so, we want to choose the shortest path at each iteration, right?

So, an iteration is really the number of hops, right?

So, we start with zero hops.

We say, what's the shortest path?

Then we move onto one hop, and we say, what's the shortest path?

Then we move up to two hops. We say, what's the shortest path?

And it may not sound, intuitive to you, but

it will be come obvious how it can build

upon itself in a minute, when we get to after we do zero on one hop, we'll see.

So let's start with zero hops, it's really a trivial case.

A through E cannot get to F, right so,

in zero hops you can't because, they're not F itself

and the only way you can get to a node in zero hops is if you are that node.

Right, so A, B, C, D and E can't get to F in zero hops, so we, we

denote that cost as infinity, so there's an infinite

cost really, which means that you just can't get there.

F can get to F though, obviously, and the cost from F to get to F is zero.

So, the path costs right now, are infinity,

from A through E and zero for F, right?

And again, we're finding a path cost to get to F.

We could choose another router as the destination.

We could choose E, D, C, whatever which one we want and typically we

would do all of them at the same time and build a routing table.

But really we're just focusing on one element of the routing table,

here, so we're trying to build a routing table, for entry F.

Like how do we get to F, from each of the other guys.

So, now, let's move onto one hop.

again, by inspection, we see A through C still can't get to

F in one hop, right, because they're more than one hop away.

any one of them would have to either go through D or E to get to F, right.

But, so, we, those costs are still infinity, but now let's look at D and E.

OK, D and E can get to F in one hop because it's

just, one step away, and, so the path here would be, link DF.

For D to get to F and

the path here would be E F, for E to get to F.

And the costs accordingly.

for D the cost is going to be eight, and we'll just say cost

D to be rid of the cost to get from D to F.

We're not going to input F in there

because everything's assumed to be going to F.

so that cost is eight, and it's just from D to F, and the cost

to get from E to F is 10 and the link the path is EF.

Just just one link here.

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