Example: Two Hops

Loading...

Из курса от партнера Princeton University

Networks Illustrated: Principles without Calculus

43 оценки

Princeton University

Networks Illustrated: Principles without Calculus

43 оценки

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.

Из урока

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.

Познакомьтесь с преподавателями

Christopher Brinton
Lecturer
Electrical Engineering
Mung Chiang
Professor
Electrical Engineering

Okay, so now using the information that we got,

for one hop before, let's try to see if we

can use what we just learned, to move up

to see what the cost would be for two hops.

so again, we're going to consider one router at a time, but we're going

to use the case of one hop to try to build up to two hops.

So, let's start with router A, see what we're talking about here.

'Kay so we'll, we'll have A say, let's, let's let

A go and look at each of its outgoing neighbors, okay.

So again D has a cost of eight after one hop, because you

know D, D, D's cost is eight to get to F in one hop.

E's cost is ten to get to F in one hop

and those are just again over the direct links right there.

So now A is going to look and A will see D, A sees C and A sees B.

Okay, let's start with B for a second okay, well A

can get to B in four hops but B can't get

to the destination F in one hop.

So that cost would still be infinity, because four plus infinity is infinity.

So for B if you tried to go to B the cost would still be infinity.

if you tried to go to C again C can't get there because the cost is still infinity.

So the cost would be two plus infinity which is still infinity.

Now for D on the other hand, D can get to F in one hop, and that cost is eight.

So, the cost then becomes, the cost from A to D, which is six,

plus the cost from D to F, which is eight. So, this cost becomes 14.

So now, let's move on to router B.

So now.

But just to backtrack for a second, now we know that A can get to

F in two hops, and the cost to get to F in two hops is 14.

So we say the cost of A is 14.

Now, for B, B can look at his neighbors, B has two.

B can get to C and B can get to E.

And remember the, the links are not bidirectional.

So you, B can't get to A.

Just because A can get to B doesn't mean that B is going to

be able to get to A, and here B cannot get to A.

So now from B, if B tried to go to C, C doesn't have a direct path like to F.

So that costed B infinite.

We tried to go to E on the other hand.

E can get to F in one hop with that cost of ten.

So this cost becomes four which is from B to

E plus ten, so four plus ten which is also 14.

And, so, then we'd say the cost of B, in two hops, is gong to be 14.

Now, for C, we move on to C, C has two neighbors it

can go to. C can go to D, and C can go to E.

for D, each of these can get to F, to, for D the cost is two, which

is the cost from C to D, and then eight, which is the cost from D to get to F.

So this becomes for, for C going to D, that cost becomes

two plus eight, which is 10. And then for C going E, the direct

cost, the direct path cost to E is three, so it gets three

plus, and then 10 is that advertised cost, plus ten, which is 13.

So now this is the first time we actually have to make a decision here.

We have to choose the smaller of the two.

Clearly 10 is smaller than 13, so we're going to go with the D.

So we would say that the cost for C right now

is ten, and we can also write just the path links here.

So A is going to go and forward directly to D in this case.

B is going to forward to E.

And, the cost of c is 10.

And C would be forwarding to, D, in this case.

Alright. So now, let's look at, D and E.

This, again, is, it's pretty trivial because, for

D what was just, analyzed there for completeness.

D can only choose either A or F.

Right, so D would look and say okay well I can get to A in

cost of seven and then plus infinity, so that's through A would just be infinity.

So I'm going to stick with what I'm currently doing,

and say the cost of D is still eight, right.

So, because nothing's better than that cost, yet at least.

And the same thing for E.

E is going

to say a little, something a little different now because even

though this is going to be the first time that we're going

to see this decision happening where we can actually change in

the path links to change when consider multiple different types of hops.

And so writing this down again, for D the path

is from D D is going to go directly to F still.

So now, for E, let's think about this and look at this for a second.

Okay. E, has a cost

of one to get to D. Okay, and then D can get to F in one

hop with a cost of eight. So if it goes through D, the cost becomes

8 plus 1 or 1 plus 8, which is 9.

And, if he goes directly to F, then the cost is going to be 10.

But now 9 is less than 10, so he is going to go to choose to go

to D.

So that we say, the cost of E now is going to be nine, which is less.

And this is indicating that E is going to go to D, rather than going directly to F.

So, again, we're not choosing the shortest, the shortest path

in terms of the the, nu-, mu-, minimum number of hops.

It's the shortest path in terms of the cost.

And this cost is less than this cost to go here, so that's going

to be the choice that we make.

[BLANK_AUDIO]

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play