Outline Distance∨ ector Link State Routing Hierarchy 9/28/2006 Lecture 10: Intra-Domain routing 6
9/28/2006 Lecture 10: Intra-Domain Routing 6 Outline • Distance Vector • Link State • Routing Hierarchy
Distance-Vector method Initial Table for a Dest Cost Next p A 0 A F CDEF D o A 4 E B 6 F dea At any time, have cost/next hop of best known path to destination Use cost oo when no path known Initially Only have entries for directly connected nodes 9/28/2006 Lecture 10: Intra-Domain routing 7
9/28/2006 Lecture 10: Intra-Domain Routing 7 Distance-Vector Method • Idea • At any time, have cost/next hop of best known path to destination • Use cost when no path known • Initially • Only have entries for directly connected nodes A E F C D B 2 3 6 4 1 1 1 3 Initial Table for A Dest Cost Next Hop A 0 A B 4 B C – D – E 2 E F 6 F
Distance-Vector Update (z,y) c(x, z) d(x,y) Update(x, y, z) d <c(x, Z)+d(z, y cost of path from x to y with first hop z if d< d(x,y) Found better path return d Updated cost/next hop else return d(x, y), nexthop(x,y)#Existing cost/next hop 9/28/2006 Lecture 10: Intra-Domain routing 8
9/28/2006 Lecture 10: Intra-Domain Routing 8 Distance-Vector Update • Update(x,y,z) d c(x,z) + d(z,y) # Cost of path from x to y with first hop z if d < d(x,y) # Found better path return d,z # Updated cost / next hop else return d(x,y), nexthop(x,y) # Existing cost / next hop x z y c(x,z) d(z,y) d(x,y)
Algorithm Bellman-Ford algorithm Repeat For every node X For every neighbor Z For every destination y d(xy)← Update(Xy,z) Until converge 9/28/2006 Lecture 10: Intra-Domain routing 9
9/28/2006 Lecture 10: Intra-Domain Routing 9 Algorithm • Bellman-Ford algorithm • Repeat For every node x For every neighbor z For every destination y d(x,y) Update(x,y,z) • Until converge
Start Optimum 1-hop paths Table for a Table for B Dst Cst Hop Dst Cst Hop 3 A 0 A A 4 B 0B 6 C D 3 D 4 E 2 E E B F F F Table for c Table for d Table for e Table for f Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst A A 2 6 A B b3 B B B C 0 C C C D D 0 D D D E E E E E 3 F F F F F F 0 9/28/2006 Lecture 10: Intra-Domain routing 10
9/28/2006 Lecture 10: Intra-Domain Routing 10 Start A E F C D B 2 3 6 4 1 1 1 3 Table for A Dst Cst Hop A 0 A B 4 B C – D – E 2 E F 6 F Table for B Dst Cst Hop A 4 A B 0 B C – D 3 D E – F 1 F Table for C Dst Cst Hop A – B – C 0 C D 1 D E – F 1 F Table for D Dst Cst Hop A – B 3 B C 1 C D 0 D E – F – Table for E Dst Cst Hop A 2 A B – C – D – E 0 E F 3 F Table for F Dst Cst Hop A 6 A B 1 B C 1 C D – E 3 E F 0 F Optimum 1-hop paths