This lesson starts discussions on shortest path routing. Many routing are based on variants of shortest path routing. In datagram packet switch networks, there are often many possible paths connecting any given source to any given destination. Typically, it is possible to attach a cost or distance to a link connecting two routers. Therefore, shortest path routing tries to determine the shortest path according to some cost criteria. Many metrics can be used to assign a cost to each link connecting to routers. Depending on the objective to be optimized, possible metrics include the hop count, that is, a rough measure of resources used. Delay, that is, sum of delays along selected path. Bandwidth, that is, available capacity in a selected path. And cost, that is, proportional to some measure. There are two general approaches to shortest path routing. One is based on distance vector, and the other is based on link state, today's class focuses on distance vector approach. In the distance vector routing, each router exchanged with its neighbors the list of distance to the destination, so asked to create a distance vector. So at best the next hop is the terminal for each destination, based on. The routing table for each destination lists the next node, and the distance. Neighbor routers exchange table entries, and determine the current best next hop. The intention is, if router Di is the shortest path to the destination from router i, and if router j is a neighbor on the shortest path. We have Di = Cij + Dj, where Cij is the shortest distance between router i to router j. And Dj is the shortest distance from router j to the destination. But the problem is, we don't know the shortest distance path from the beginning. For router i, it only has local information on the distance to its neighbors. Let's use a few view graphs to illustrate how distance vector works. Consider our routers want to know their shortest distance to the destination at San Jose. These routers are one hop, two hops, or three hops to the destination. In the first step, the destination node at San Jose sends accurate distance information to its one hop neighbors. In the second step, the one hop neighbors calculate the current shortest distance to the destination, and send that information to their neighbors. In the third step, the two hub neighbors calculate the current shortest distance to the destination, and then send the information to their neighbors too. By doing so hop by hop, eventually the current shortest information about distance to the destination is rippled across the whole network. And the the shortest path from each router to the destination is calculated. The Bellman-Ford algorithm is based on a principle, if each neighbor of node A knows the shortest distance to node Z. Then node A can determine that the shortest path to node Z by calculating the distance to node Z, so each of his neighbors end up picking the minimum. The algorithm can be written in pseudocode, but let's use an example to understand how it works. The network in this figure has six nodes, and their connections with distance are given. Consider nodes 1 to 5 want to build a shortest distance to the destination node of 6. Initially, the routing table entries in the five nodes are initialized as pair of -1, infinity. Which means the next hub is unknown and the distance is infinite. In iteration 1, node 3 finds that it's connected to node 6, with distance of 1. Node 5 finds it's connected to node 6 at a distance of 2. Node 3 and 5 update their entries and inform their neighbors. In iteration 2, node 1 finds that it can reach node 6 by node 3, with distance 3. Node 2 finds it can reach node 6 by node 5, with distance 6. Node 4 finds it has a path by node 3 and 5, with distance 3 and 7, respectively. Node 4 compares total distance, and selects the path via node 3. Nodes 1, 2, and 4 update their routing tables, and inform their neighbors. In iteration 3, node 2 finds that it can reach node 6 via node 4, with distance 4. Node 2 changes its entry, and informs its neighbors. Finally, nodes 1, 4, 5 process the new entry from node 2, but don't find any new shortest path. The process has converged, the result in a tree, is called shortest-path tree, to the destination 6, that is the tree root. Note that if a link in the tree breaks, re-computation of the shortest distance is required. We leave this to you readers
