Shortest-Path Routing: Link-State & Distance-VectorDijkstra’s Shortest-Path AlgorithmDijsktra’s AlgorithmDijkstra’s Algorithm ExampleSlide 5Shortest-Path TreeDistance Vector AlgorithmDistance Vector Example: Step 1Distance Vector Example: Step 2Distance Vector Example: Step 31Shortest-Path Routing:Link-State & Distance-VectorEE 122: Intro to Communication Networks Fall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortiz http://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford2Dijkstra’s Shortest-Path Algorithm•Iterative algorithm–After k iterations, know least-cost path to k nodes•S: nodes whose least-cost path definitively known–Initially, S = {u} where u is the source node–Add one node to S in each iteration•D(v): current cost of path from source to node v–Initially, D(v) = c(u,v) for all nodes v adjacent to u–… and D(v) = ∞ for all other nodes v–Continually update D(v) as shorter paths are learned3Dijsktra’s Algorithm1 Initialization: 2 S = {u} 3 for all nodes v 4 if v adjacent to u {5 D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in S with the smallest D(w)10 add w to S 11 update D(v) for all v adjacent to w and not in S: 12 D(v) = min{D(v), D(w) + c(w,v)} 13 until all nodes in S4Dijkstra’s Algorithm Example32211414533221141453322114145332211414535Dijkstra’s Algorithm Example32211414533221141453322114145332211414536Shortest-Path Tree•Shortest-path tree from u•Forwarding table at u3221141453uvwxyzstv (u,v)w (u,w)x(u,w)y (u,v)z(u,v)links (u,w)t(u,w)7Distance Vector Algorithm •c(x,v) = cost for direct link from x to v–Node x maintains costs of direct links c(x,v)•Dx(y) = estimate of least cost from x to y–Node x maintains distance vector Dx = [Dx(y): y є N ]•Node x maintains its neighbors’ distance vectors–For each neighbor v, x maintains Dv = [Dv(y): y є N ]•Each node v periodically sends Dv to its neighbors–And neighbors update their own distance vectors–Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N•Over time, the distance vector Dx converges8Distance Vector Example: Step 1AEFCDB23641113Table for ADst Cst HopA 0 AB 4 BC–D–E 2 EF 6 FTable for BDst Cst HopA 4 AB 0 BC–D 3 DE–F 1 FTable for CDst Cst HopA–B–C 0 CD 1 DE–F 1 FTable for DDst Cst HopA–B 3 BC 1 CD 0 DE–F–Table for EDst Cst HopA 2 AB–C–D–E 0 EF 3 FTable for FDst Cst HopA 6 AB 1 BC 1 CD–E 3 EF 0 FOptimum 1-hop paths9Distance Vector Example: Step 2Table for ADst Cst HopA 0 AB 4 BC 7 FD 7 BE 2 EF 5 ETable for BDst Cst HopA 4 AB 0 BC 2 FD 3 DE 4 FF 1 FTable for CDst Cst HopA 7 FB 2 FC 0 CD 1 DE 4 FF 1 FTable for DDst Cst HopA 7 BB 3 BC 1 CD 0 DE–F 2 CTable for EDst Cst HopA 2 AB 4 FC 4 FD–E 0 EF 3 FTable for FDst Cst HopA 5 BB 1 BC 1 CD 2 CE 3 EF 0 FOptimum 2-hop pathsAEFCDB2364111310Distance Vector Example: Step 3Table for ADst Cst HopA 0 AB 4 BC 6 ED 7 BE 2 EF 5 ETable for BDst Cst HopA 4 AB 0 BC 2 FD 3 DE 4 FF 1 FTable for CDst Cst HopA 6 FB 2 FC 0 CD 1 DE 4 FF 1 FTable for DDst Cst HopA 7 BB 3 BC 1 CD 0 DE 5 CF 2 CTable for EDst Cst HopA 2 AB 4 FC 4 FD 5 FE 0 EF 3 FTable for FDst Cst HopA 5 BB 1 BC 1 CD 2 CE 3 EF 0 FOptimum 3-hop
View Full Document
Unlocking...