Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_6 [2011/03/30 17:38] – [6.6-6.7 SEQUENCE ALIGNMENT] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_6 [2011/04/06 16:41] (current) – [6.9 Shortest Paths and Distance Vector Protocols] zhongc
@@ Line 319: / Line 319: @@
 Interesting/readable: 8/8
+====== 6.9 Shortest Paths and Distance Vector Protocols ======
+Problem Motivation:
+One important application of the Shortest-Path Problem is for routers in a
+communication network to determine the most efficient path to a destination.
+attempt:
+Dijkstra's algorithm requires global information of network- unrealistic
+we need to work with only local information.
+Bellman-Ford uses only local knowledge of
+neighboring nodes
+ Distribute algorithm: each node v maintains its
+value M[v]
+ Updates its value after getting neighbor’s values
+Problems with the Distance Vector Protocol
+One of the major problems with the distributed implementation of Bellman-
+Ford on routers (the protocol we have been discussing above) is that it’s derived
+from an initial dynamic programming algorithm that assumes edge costs will
+remain constant during the execution of the algorithm.
+That is, we might get into a situation where there is infinite looping of mutual dependancy.
+could fail if the other node is deleted.
+Solution:
+ Each router stores entire path Not just the distance and the first hop
+ Based on Dijkstra's algorithm
+ Avoids "counting-to-infinity" problem and related
+difficulties
+ Tradeoff: requires significantly more storage
+Interesting/readable: 5/5