And so, we're actually done with that example.
we don't have to continue anymore because it
has already found all the minimum cost paths.
And here's just a description, after three hops, what we see here.
so again, this is if we're going to destination F the cost that we would see.
so A could get there in a cost of 12, and he would forward to C.
B could get there at a cost of 13, he
would forward to E, C forward to D at a cost
of 10, and so on.
D would forward directly to F and E would forward to D to get there.
So these are the paths that the packets would take getting to F.
So, in general, suppose we have Num, we'll say NumNodes,
it could be eight, nine, in this case it's six.
but not counting destination, so sorry in this case it's five.
So this is, it's very important to say we're not counting the destination here.
so suppose we have in this case five nodes,
so if we had 20 nodes counting the
destination it would be 19 without the destination.
then we can guarantee actually to have found a solution after num hops, right?
So if we take away the destination, count the number of
nodes, and we've already gone that many hops or just the
number of total hops counting the destination minus one, then we
know that we're done and that we don't have to go anymore.
because otherwise we'd have to make a cycle back, right so in this case,
right, if I wanted to go five nodes, right, I'd
need to cover all the other nodes in the graph.
And because there is only five of them, so obviously you're not going to want to
loop back you're not going to want to go to A to D to C.
Which that's not even possible. But, a loop back here.
It's hard to actually see any loops, or A to B, to E to D, to A.
you would never do that because that would only add cost, right?
because the loop is just going to have a higher cost than without
looping, so, if you've already gone to all of the different nodes then obviously you
must've, or if you've already had enough hops
that you could have covered all the nodes
of the graph, then you much have found
the minimum cost, because the maximum number of
hops you'd use would be the number of
nodes on the graph without the destination present.
So, in general with six nodes we would need to go five hops, like here.
But we're actually done already, we don't need
to keep going, because the cost won't keep updating.
You can see, right, that nothing is going to change now.
B's cost is nine and nine plus four is 13.
And you can verify all the costs are all equalized now.
so, in a real life imitation we never know the real amount of routers, Right?
so, we have to rely on the lack of really new costs coming in.
Alright, so the routers themselves would say, okay well
the cost aren't updating, I'm not seeing anything new, right?
I'm not seeing you can get there quicker, I'm
not seeing that If I'm B, for instance, I'm not
seeing E or C can get there any quicker, until
that happens I'm not going to update anymore at all.
so because we don't know the number of nodes, we just have to rely
on the lack of new costs or updated cost to determine that we're first.
But again these costs are going to change
all the time depending on upon what happens.
You know, if links go out then these costs go to infinity.
If they have to re-converge the algorithm in each re-converge and so on.
so here's a, here's the routing table or basically what
would appear to be a routing table for each router.
A through E coming down here.
I'm going to destination F and again these are, these are names they would be in
the routing table with the IP addresses, right,
so each of these routers has an IP address.
That's how they're addressed.
so router A, B, C, D, E has one IP address, then but the
destination F, which is really just one
entry in each of these router's routing table.
So each
router has a separate routing table. A would have one for B, C, D, E, and F.
we only did just the case of going totally to F.
But then if A receives a packet destination to F, he knows
that he sends out the port this port right here, which would
go next hop of C and really this would be written in
C's IP address too and The cost is 12 to get there, right?
So here we're showing symbolically,
destination next top, really in a routing table this would be IP address, and
then port number, which port am I going out for that router to know that.
Christopher BrintonLecturer
Mung ChiangProfessor
