Shortest Path Problem

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

So now let's delve into some of the more specifics behind routing.

the first thing we're going to do is look at, graphs again.

Alright, so we've looked at graphs a few times, we looked at a graph of

webpages, first of all, and now we're going to look at a graph of routers.

Right, so when we look at a graph, it's

important again to note what the nodes and lengths are.

Whether it's direct or undirected.

Couple of other properties, here's the main ideas, that each of these

are routers, here, so those are obviously the nodes A, B, and C.

we have a source and a destination so we want to get the message

somewhere and the source may have come from, you know, some computer over here.

And the destination may actually be somewhere off this router.

Like some other computer this router's serving,

but the main idea is the same right.

Once it gets into the network, you have to

figure out how to get it to the other edge.

so the nodes are the routers in this graph.

the links are the physical connections

so we're not talking about hyperlinks anymore.

We're talking about physical connection from

source to Of wherever else we're going.

And again, there's many many different graphs of networking, obviously.

There's graphs of routers we can look at, we

can look at overlay networks, we can look at graphs

of webpages, we can also look at graphs of

social networks, which we didn't have time to look at.

in this course,

but there, you know, there's, there's just many different graphs, if you

look at the the related reading for this course, the Networks Illustrated book.

you see that there's just so many different types

of graphs, and we look at graphs a lot.

now the links are directed here,

and we said directed versus undirected, undirected

will mean that the links don't have arrows, so they can go either way.

But here they are actually directed, so the source can get to A

then, A might not be able to get back to the source, it depends.

then also to

depend upon the physical technology used and whether the

cables connecting the two routers can go in both directions.

and the links are weighted and so when we

looked at the graphs of the webpages we did.

We did have some weights, and we didn't weight them very specifically, we

just said that it would spread its outgoing importance across all the links.

But here we have the link weights, and those are costs.

So higher

link weight is a bad thing, right?

So cost, this is a cost of five, it means it costs five to go from the source to A,

or it costs two to go from the source to

B, it costs one to go from this source to C.

So, shortest path problem is really one of the main ideas

behind routing, or one of the ways to look at routing.

It's trying to find the shortest path in sort of your destination.

Actually shortest path is a little

bit slower, because what we're actually doing with shortest path is

we're finding the minimum cost path from one node to another.

The shortest path, you probably think least number

of hops, right, so you'd want to figure out

how many, what sleeves or times you can do this in order to get to the destination.

But it's actually the minimum cost path, so there

might be one that uses more hops, but just

has a, a lower cost because one of the

costs on the single hop pass might be extremely high.

so if we,

but if we had our link weights to be 1 or they were all

the same value, then it would reduce to a technical shortest path quote unquote.

Shortest path problem to minimize the number of hops.

But the idea, when we speak of, shortest path, really mean minimum cost

path and we're stick with that terminology because that's what's used, in this field.

So how do we find the shortest path?

Well, let's look at a simple example first.

Suppose we're starting at A and, we want to get, to D.

so, then you may look, okay, well A has two choices.

A can either go through B, or A can go through C.

Well, what's the cost from A to B, is two, and then from B to D is four.

So, the total cost here would be two plus four which is six.

Now, from A to C is three, and from C to D is five.

So the total cost here would be 3 plus 5, which is 8, so 6 is less than 8.

So clearly A would want to go to B in order to go to C, simple right?

Well it's not as simple as it looks, because

there's no way you could ever solve the graph

of routers in the internet like we just did

by inspection, because there's many more than four routers.

There's an enormous, enormous number of routers in the internet, so we need to

have somewhere of an automated scheme in order to do this shortest path problem.

And it is a lot of research that's gone into

finding algorithms to solve the shortest path problem as quick

as possible, to try to figure out what's the best

way to get from one node, or one router, to another.

It's been studied excessively since the 1950s.

there's been Dijkstra's Algorithm, there's the

Bellman-Ford Algorithm, there's many other algorithms, too.

We're going to focus on the Bellman-Ford Algorithm here because it

illustrates some of the main ideas behind routing and it's

relatively simple.

And it's used in some famous routing protocols, like the

original ARPANET did use the Bellman Ford Algorithm to do this.

and so the main ideas behind the Bellman Ford Algorithm is, the first one

is we want to find the minimum cost path for a different number of hops.

So we start with a 0 hops and we say, what's

the minimum cost to get from A to D in 0 hops.

Well, you can't get from A to C and C to D in 0 hops because is not D,

so it's infinite.

What's then the cost to get from A to D in one hop?

Then from, in one hop you also know you can't get

from directly A to D, but B can get to D in

one hop, and then that's a cost of four, and C can

get to D in one hop and that's a cost of five.

Right, and then you can do in two hops, and you

can say, okay, well A can get to D in two hops.

That's the way we build up on the previous number of

hops, and can go on to the next number of hops.

And it builds on itself, so it actually

does become iterative algorithm and we talked about iterative

algorithms before, that build on each other over time.

We talked about how DPC It's an iterative algorithm, and this is

the, another iterative algorithm that we're

looking at, is the Bellman-Ford algorithm.

And we'll illustrate its computation.

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