Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter6 [2011/03/30 04:00] – [Section 8: Shortest Paths in a Graph] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter6 [2011/04/03 05:29] (current) – shangw
@@ Line 79: / Line 79: @@
 In addition, to save both time and space, we set a stopping signal: when we run into 2 same columns consecutively, it is time to stop because any further update will not change anything.
 The readability is 8.
+==== Section 9: Shortest Paths and Distance Vector Protocols=====
+This is section introduces an algorithm that improves the shortest paths algorithm from section 8.
+First we observe the shortage of the original algorithm: it is a pull-based algorithm, and in  each iteration, each node will contact all its neighbors and "pull" the new value from it; however, if a neighbor remains the same value, then there is no need to pull out the new value from it. The new algorithm is a push-based algorithm. That is, updates will not be provided until the value of a node changes; then the updates will be pushed to its surrounding neighbors, and the method is called the distance vector protocol. The book writes down the detailed algorithm, as usual.
+Then it continues to discuss some associated concerns with the distance vector protocol. In real life scenario, if one of the edges is deleted, which totally cut-off all the connections between a node a and the ending node b, the distance vector protocol will not cease updating M[a] and never realize there is no path available. And this, of course, can be problematic.
+The way to solve it is to keep track of the big picture: each node not only storing knowledge of its neighbor but the entire network to ensure there actually exists a path. The extra storage will take over more space but is indeed necessary.
+Readability is 7.