Chapter 4 roadmap 4.1 Introduction and Network Service Models 4.2 Routing Principles o Link state routing o Distance vector routing 4. 3 Hierarchical routing 4. 4 The Internet(Ip) protocol 4.5 Routing in the Internet 4.6 What's Inside a Router 4.7 IPv6 4.8 Multicast Routing 4.9 Mobility Network Layer 4-11
Network Layer 4-11 Chapter 4 roadmap 4.1 Introduction and Network Service Models 4.2 Routing Principles Link state routing Distance vector routing 4.3 Hierarchical Routing 4.4 The Internet (IP) Protocol 4.5 Routing in the Internet 4.6 What’s Inside a Router 4.7 IPv6 4.8 Multicast Routing 4.9 Mobility
Routing Routing protocol Goal: determine"good"path (sequence of routers)thru network from source to dest <B3<C 2 A 2 Graph abstraction for routing algorithms SE2 O graph nodes are routers "good°path: o graph edges are o typically means minimum hysical links phy cost path o link cost: delay, $s cost o other defs possible or congestion level Network Layer 4-12
Network Layer 4-12 Routing Graph abstraction for routing algorithms: graph nodes are routers graph edges are physical links link cost: delay, $ cost, or congestion level Goal: determine “good” path (sequence of routers) thru network from source to dest. Routing protocol A D E B C F 2 2 1 3 1 1 2 5 3 5 “good” path: typically means minimum cost path other def’s possible
Routing Algorithm classification Global or decentralized Static or dynamic? information? Static Global: o all routers have complete 口 routes change slowly topology link cost info over time 0 link state"algorithms ynamIC Decentralized 口 routes change more o router knows physically uick connected neigh g bors link costs to neighbors o periodic update g iterative process of o in response to link computation exchange of cost changes info with neighbors o "distance vector algorithms Network Layer 4-13
Network Layer 4-13 Routing Algorithm classification Global or decentralized information? Global: all routers have complete topology, link cost info “link state” algorithms Decentralized: router knows physicallyconnected neighbors, link costs to neighbors iterative process of computation, exchange of info with neighbors “distance vector” algorithms Static or dynamic? Static: routes change slowly over time Dynamic: routes change more quickly periodic update in response to link cost changes
A Link-State Routing Algorithm Dijkstra s algorithm Notation o net topology, link costs o c(,)): link cost from node known to o‖ I nodes to j cost infinite if not o accomplished via"link direct neighbors state broadcast O D(v): current value of cost o all nodes have same into of path from source to o computes least cost paths dest. v from one node (source")to p(v):pr all other nodes predecessor node along path from source to o gives routing table for v. that is next v that node 口 iterative: after k 口N: set of nodes whose iterations know least cost least cost path definitively path to k dest. 's known Network Layer 4-14
Network Layer 4-14 A Link-State Routing Algorithm Dijkstra’s algorithm net topology, link costs known to all nodes accomplished via “link state broadcast” all nodes have same info computes least cost paths from one node (‘source”) to all other nodes gives routing table for that node iterative: after k iterations, know least cost path to k dest.’s Notation: c(i,j): link cost from node i to j. cost infinite if not direct neighbors D(v): current value of cost of path from source to dest. V p(v): predecessor node along path from source to v, that is next v N: set of nodes whose least cost path definitively known
Dijsktra's Algorithm initialization 3 for all nodes y 4 if v adjacent to a 5 then D(V)=C(A 6 else D(v=infinity 8 Loop 9 find w not in N such that d(w)is a minimum 10 add w to n 11 update D(v) for all v adjacent to w and not in N 2 D(v)=min( D(v), D(w)+ c(w, v) 13/ new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w toV*/ 15 until a∥ nodes in m Network le 4-15
Network Layer 4-15 Dijsktra’s Algorithm 1 Initialization: 2 N = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N