Bellmanford

Chapter 4 Network Layer Computer Networking: A Top Down Approach Featuring the Internet , 2 nd edition. Jim Kurose, Keith Ross Addison-Wesley, July 2002. ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

Distance Vector Routing Algorithm (Bellman Ford) ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],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 7 8 1 2 1 2 loop! loop! A E D C B 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 destination 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

Distance table gives routing table A B C D A,1 D,5 D,4 D,4 Outgoing link to use, cost destination Distance table 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 destination

Distance Vector Routing: overview ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],Each node: wait for (change in local link cost of msg from neighbor) recompute distance table if least cost path to any dest has changed, notify neighbors

Distance Vector Algorithm: 1 Initialization: 2 for all adjacent nodes v: 3 D (*,v) = infinity /* the * operator means "for all rows" */ 4 D (v,v) = c(X,v) 5 for all destinations, y 6 send min D (y,w) to each neighbor /* w over all X's neighbors */ X X X w At all nodes, X:

Distance Vector Algorithm (cont.): 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 12 if (c(X,V) changes by d) 13 /* change cost to all dest's via neighbor v by d */ 14 /* note: d could be positive or negative */ 15 for all destinations y: D (y,V) = D (y,V) + d 16 17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min DV(Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: D (Y,V) = c(X,V) + newval 22 23 if we have a new min D (Y,w)for any destination Y 24 send new value of min D (Y,w) to all neighbors 25 26 forever w X X X X X w w

Distance Vector Algorithm: example X Z 1 2 7 Y

Distance Vector Algorithm: example X Z 1 2 7 Y D (Y,Z) X c(X,Z) + min {D (Y,w)} w = = 7+1 = 8 Z D (Z,Y) X c(X,Y) + min {D (Z,w)} w = = 2+1 = 3 Y

Distance Vector: link cost changes ,[object Object],[object Object],[object Object],[object Object],1 4 50 1 algorithm terminates “ good news travels fast” X Z Y

Distance Vector: link cost changes ,[object Object],[object Object],[object Object],1 4 50 60 algorithm continues on! X Z Y

Distance Vector: poisoned reverse ,[object Object],[object Object],[object Object],1 4 50 60 algorithm terminates X Z Y

Comparison of LS and DV algorithms ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

Chapter 4 roadmap ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

Hierarchical Routing ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

Hierarchical Routing ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],gateway routers

Intra-AS and Inter-AS routing ,[object Object],[object Object],[object Object],inter-AS, intra-AS routing in gateway A.c network layer link layer physical layer a b a C A B d b a A.a A.c C.b B.a c b c

Intra-AS and Inter-AS routing Host h2 Intra-AS routing within AS A Intra-AS routing within AS B ,[object Object],a b b a a C A B d c A.a A.c C.b B.a c b Host h1 Inter-AS routing between A and B

Bellmanford

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to Bellmanford

Similar to Bellmanford (20)

Recently uploaded

Recently uploaded (20)

Bellmanford