Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:camille:chapter6 [2011/04/03 00:18] – [Chapter 5: Divide and Conquer] cobbc
+++ courses:cs211:winter2011:journals:camille:chapter6 [2011/04/03 00:40] (current) – [Section 8: Shortest Paths in a Graph] cobbc
@@ Line 93: / Line 93: @@
     * **Readability:**
 Awesome! I really enjoyed this section!
+===== Section 9: Shortest Paths and Distance Vector Protocols =====
+    * **Summary:**
+Routers in a communication network are an important application for the Shortest-Path problem. Nodes correspond to routers, and there is an edge between v and w if the two routers are connected directly. The cost is the delay on the link from one node to another. The problem is to find a path with minimum delay from a source node s to a destination t. Since the delays are definitely nonnegative, you could theoretically use Dijkstra's Algorithm, but that requires global knowledge of the network. The Bellman-Ford Algorithm doesn't ... each node just needs info from its neighbor (i.e. the length of the path to t from each node). To improve on Bellman-Ford, they propose switching from a pull-based algorithm (in each iteration, the nodes "pull" the value from their neighbors) to a push-based algorithm (none of those values "pulled" in the earlier algorithm change unless the node they're being pulled from has changed, so we will update the connected nodes when we change a value). Not all values need to be pushed each time, so running time is improved (a little). They give a concrete version of this algorithm and then discuss the real situation, where routers update at different speeds, so the algorithm runs asynchronously (a node that's values is changed becomes "active" until it has updated all of its values). The asynchronous version works, too. This algorithm computes shortest paths from a single source to a single destination, but in real life you'd be interested in distances from and to everything else, so they keep track of a distance vector protocol, which maintains a vector of distances to every other node in the network. There are a few problems with this approach. The algorithm assumes that edge costs remain the same and that edges are never deleted, but that's not true in real life. If an edge gets deleted, then cycles in the graph can just keep updating their information based on what's around them and never notice that the edge has been deleted (see the example from the slides). It's hard to tell if paths are just "down" or if they're really just disconnected. To avoid this problem, designers of network routing schemes used path vector protocols (store the whole path to everything else) instead of distance vector protocols. That way nodes can avoid the counting to infinity problem, but they require a lot more storage. The path vector protocol is used in the Border Gateway Protocol in the Internet core.
+    * **Insights and Questions:**
+How do nodes/paths get "added" in this algorithm? If we initially "know" which nodes are connected in order to figure out what needs to be "pushed" to, then, if something is added later, how do we tell the nodes that they need to push to this one? I guess we just update their list of things to push to ...
+    * **Readability:**
+As always, very easy to read :)