Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:41] – [6.9 Shortest Paths and Distance Vector Protocols] gouldc | courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:52] (current) – [6.9 Shortest Paths and Distance Vector Protocols] gouldc |
|---|
| |
| ===== 6.9 Shortest Paths and Distance Vector Protocols ===== | ===== 6.9 Shortest Paths and Distance Vector Protocols ===== |
| Outline: An instance of the shortest-path problem on an undirected graph for which all edge costs are positive. Dijkstra's is possible, but we don't want to use it (we can think of something better) because we are talking about routers here and we prefer to work with local information. The BF Algorithm from 6.8 has a local property that can be utilized in a parallel programming solution. If we maintained each node's value in a memoized array, we could update it by simply looking at the values of all of its neighbors and computing the total cost of that value and an edge to that node. This section proposes a change in the BF Algorithm from a "pull-based" implementation to a "push-based" implementation. | Outline: An instance of the shortest-path problem on an undirected graph for which all edge costs are positive. Dijkstra's is possible, but we don't want to use it (we can think of something better) because we are talking about routers here and we prefer to work with local information. The BF Algorithm from 6.8 has a local property that can be utilized in a dynamic programming solution. If we maintained each node's value in a memoized array, we could update it by simply looking at the values of all of its neighbors and computing the total cost of that value and an edge to that node. This section proposes a change in the BF Algorithm from a "pull-based" implementation to a "push-based" implementation: this means we will only update the values in the memoized array for nodes that have been affected by a recent change, saving a lot of computation time. |
| | |
| | Problems: Assumes edge costs will remain constant during runtime, which for many reasons will probably not be the case in practice. Also, there is the potential "problem of counting to infinity" which we talked about in class - two nodes constantly update one another and tell the other that they have been updated, which leads to an infinite number of operations. |
