Dijkstra's algorithm: example stepstartND(B),pB)D(C),p(c)D(D),p(D)D(E,p(E)D(F,p() 0 A 2.A 5.A 1.A infinity infinity AD 2.A 4.D 2, D infinity 2 ADE 2.A 3.E 4.E ADEB 3,E 4.E 4 ADEBC 4,E 5 ADEBCF <B3< 5 DE2 Network Layer 4-16
Network Layer 4-16 Dijkstra’s algorithm: example Step 0 1 2 3 4 5 start N A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) infinity 2,D D(F),p(F) infinity infinity 4,E 4,E 4,E A D E B C F 2 2 1 3 1 1 2 5 3 5
Dijkstra's algorithm, discussion Algorithm complexity: n nodes g each iteration: need to check all nodes w. not in n O n*(n+1)/2 comparisons: O(n**2) o more efficient implementations possible: O(nlogn) Oscillations possible D e.g., link cost amount of carried traffic A A BSD 0 621+20 te recompute initially recompute recompute routing Network Layer 4-17
Network Layer 4-17 Dijkstra’s algorithm, discussion Algorithm complexity: n nodes each iteration: need to check all nodes, w, not in N n*(n+1)/2 comparisons: O(n**2) more efficient implementations possible: O(nlogn) Oscillations possible: e.g., link cost = amount of carried traffic A D C B 1 1+e 0 e e 1 1 0 0 A D C B 2+e 0 0 0 1+e 1 A D C B 0 2+e 1 1+e 0 0 A D C B 2+e 0 0 e 1+e 1 initially … recompute routing … recompute … recompute
Distance Vector Routing Algorithm iterative: Distance Table data structure 口 continues until no nodes exchange into g each node has its own o self-terminating: no o row for each possible destination signal" TO STop 口 column for each directly attached neighbor to node asynchronous 口 nodes need not o example: in node x, for dest y exchange info/iterate via neighbor Z in lock step distributed: distance from x to g each node Y, via Z as next hop communicates only with (Y,Z) directly-attached cX, 2)+ min [-(Y, w) neighbors Network Layer 4-18
Network Layer 4-18 Distance Vector Routing Algorithm iterative: continues until no nodes exchange info. self-terminating: no “signal” to stop asynchronous: nodes need not exchange info/iterate in lock step! distributed: each node communicates only with directly-attached neighbors Distance Table data structure each node has its own row for each possible destination column for each directlyattached neighbor to node example: in node X, for dest. Y via neighbor Z: D (Y,Z) X distance from X to Y, via Z as next hop c(X,Z) + min {D (Y,w)} Z w = =
Distance Table: example <B31<C cost to destination via DOA B D A38 2 ASE A 145 D B78(5) D(C, D)=C(E, D)+ min [D (C, w)] 2+2=4 C|69(4 E D (A, D)= C(E,D)+min (DD(A, W)) 2+3=5 E oop D (A, B)=C(E, B)+min (DB(A, W)) 8+6=14 loop! Network Layer 4-19
Network Layer 4-19 Distance Table: example A E D B C 7 8 1 2 1 2 D () A B C D A 1 7 6 4 B 14 8 9 11 D 5 5 4 2 E cost to destination via D (C,D) E c(E,D) + min {D (C,w)} D w = = 2+2 = 4 D (A,D) E c(E,D) + min {D (A,w)} D w = = 2+3 = 5 D (A,B) E c(E,B) + min {D (A,w)} B w = = 8+6 = 14 loop! loop!
Distance table gives routing table cost to destination via DOA B D Outgoing link to use cost A 145 AA, 78(5) B|D,5 0 8C|69(4 C|D,4 D|411 D|D,2 Distance table Routing table Network le 4-20
Network Layer 4-20 Distance table gives routing table D () A B C D A 1 7 6 4 B 14 8 9 11 D 5 5 4 2 E cost to destination via A B C D A,1 D,5 D,4 D,2 Outgoing link to use, cost Distance table Routing table