B-----C / / | / / D---E F-----G | | | H | | / | I--------J | / | | K----------L-----M In the above, the shortest path from A to M could be A-B-C-E-M, A-B-D-H-M, or A-G-J-L-M. There are two algorithms that find the shortest path: the Bellman-Ford or Dijkstra algorithms. Once one of these algorithms are run, each node in the network will know the shortest path from itself to each other node in the network. The algorithm uses fixed "metrics" for route comparisons. The fixed metrics could be time delay, cost, or some other value used to compare routes. In the following network, the numbers represent the cost to transverse the link. A ---- 1 ---- B ----- 2 ----- C | | | || 3 2 1| || |3 D ---- 3 ---- E -- 2 -- F| /| 1| / G ---------- 3 ---------- HIn the above network the following would be: Route Cost -------------------- ------------- A-D-E-F-H 3+3+2+1 = 9 A-G-H 3+3 = 6 A-B-E-F-H 1+2+2+1 = 6 A-B-C-F-H 1+2+1+1 = 5So the "best" route would be the last one, which has a cost of 5. PROTOCOL:The above algorithms work well based on some assumptions. That the nodes never fail, the cost of "hopping" never changes, you have the space to store all of the data and that you have the ability to collect the data. However, in practice, these assumptions are not valid. Nodes crash, costs change, and there is a limit on how much inforamtion can be kept. This is where protocols come in. Not o...
