j ? ? ? 66 cost 3 j m cost 2 cost 2 k I am 4 n cost 7 distance vector rcvd from cable j cost 3 12 3 15 3 12 5 3 18 0 7 15 distance vector rcvd from cable k cost 2 5 8 3 2 10 7 4 20 5 distance vector rcvd from cable m 0 15 cost 2 0 5 3 2 19 9 5 22 2 4 7 distance vector rcvd from cable n cost 7 6 2 0 7 8 5 8 12 11 3 2 your own calculated distance vector 6 your own calculated forwarding table k/j 2 6 5 0 12 8 m j m 0 k j 19 n 3 ? j ? ? ? 67 A Looping Problem B C 68 A 2 Looping Problem B 1 C 0 Cost to C 69 Looping Problem direction towards C direction towards C A B 2 1 C 0 Cost to C 70 A 2 Looping Problem

B 1 What is Bs cost to C now? C 0 Cost to C 71 A 2 Looping Problem B 1 3 C 0 Cost to C 72 Looping Problem direction towards C direction towards C A B 2 1 3 C 0 Cost to C 73 Looping Problem direction towards C direction towards C A B 2 1 4 3 C 0 Cost to C 74 Looping Problem direction towards C direction towards C A B 2 1 4 3 5 C 0 Cost to C 75 Looping Problem worse with high connectivity Q Z B A C N M V H 76 Split Horizon: one of several optimizations Dont tell neighbor N you can reach D if youd forward to D through N A B C A B C D 77 Link State Routing meet nbrs Construct Link State Packet (LSP) who you are list of (nbr, cost) pairs Broadcast LSPs to all rtrs (a miracle occurs) Store latest LSP from each rtr Compute Routes (breadth first, i.e., shortest path firstwell known and efficient algorithm) 78 A B/6 D/2 A 2 D B A/6 C/2 E/1 6 2 B 1 E C B/2 F/2 G/5 2 4 C 2 F D A/2 E/2 5 1 G

E B/1 D/2 F/4 F C/2 E/4 G/1 G C/5 F/1 79 Computing Routes Edsgar Dijkstras algorithm: calculate tree of shortest paths from self to each also calculate cost from self to each Algorithm: step 0: put (SELF, 0) on tree step 1: look at LSP of node (N,c) just put on tree. If for any nbr K, this is best path so far to K, put (K, c +dist(N,K)) on tree, child of N, with dotted line step 2: make dotted line with smallest cost solid, go to step 1 80 Look at LSP of new tree node A B C D E F B/6 A/6 B/2 A/2 B/1 C/2 D/2 C/2 F/2 E/2 D/2 E/4 E/1 G/5 F/4 G/1 C(0) B(2) F(2) G(5) G C/5 F/1 81 A B/6 D/2 Make shortest TENT solid B C D E F A/6 B/2 A/2 B/1 C/2 C/2 F/2 E/2 D/2 E/4 E/1 G/5 F/4 G/1 C(0) B(2) F(2) G(5) G C/5 F/1 82 Look at LSP of newest tree node A B C D E F G B/6 A/6 B/2 A/2 B/1 C/2 C/5 D/2 C/2 F/2 E/2 D/2 E/4 F/1 E/1 G/5 F/4 G/1 C(0) B(2) F(2) G(5) E(4) G(3) 83 A B/6 D/2

Make shortest TENT solid B C D E F A/6 B/2 A/2 B/1 C/2 C/2 F/2 E/2 D/2 E/4 E/1 G/5 F/4 G/1 C(0) B(2) F(2) E(4) G(3) G C/5 F/1 84 Look at LSP of newest tree node A B C D E F G B/6 A/6 B/2 A/2 B/1 C/2 C/5 D/2 C/2 F/2 E/2 D/2 E/4 F/1 E/1 G/5 F/4 G/1 C(0) B(2) F(2) A(8) E(3) G(3) 85 A B/6 D/2 Make shortest TENT solid B C D E F A/6 B/2 A/2 B/1 C/2 C/2 F/2 E/2 D/2 E/4 E/1 G/5 F/4 G/1 C(0) B(2) F(2) A(8) E(3) G(3) G C/5 F/1 86 Look at LSP of newest tree node A B C D E F G B/6 A/6 B/2 A/2 B/1 C/2 C/5 D/2 C/2 F/2 E/2 D/2 E/4 F/1 E/1 G/5 F/4 G/1 C(0) B(2) F(2) A(8) E(3) G(3) D(5) 87 A B/6 D/2 Make shortest TENT solid B C D E F A/6 B/2 A/2 B/1 C/2 C/2 F/2 E/2 D/2 E/4 E/1 G/5 F/4 G/1 C(0) B(2) F(2) A(8) E(3) G(3) D(5) G C/5 F/1 88 Look at newest tree nodes LSP A B C D E