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.
