Chapter 5: Network Layer: The Control Plane PDF

Chapter 5 Network Layer: The Control Plane A note on the use of these Powerpoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide conten...

Chapter 5 Network Layer: The Control Plane A note on the use of these Powerpoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: Computer § If you use these slides (e.g., in a class) that you mention their source (after all, we’d like people to use our book!) Networking: A Top § If you post any slides on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this Down Approach material. 7th edition Thanks and enjoy! JFK/KWR Jim Kurose, Keith Ross All material copyright 1996-2016 Pearson/Addison Wesley J.F Kurose and K.W. Ross, All Rights Reserved April 2016 Network Layer: Control Plane 5-1 Network-layer functions Recall: two network-layer functions: § forwarding: move packets from router’s input to data plane appropriate router output § routing: determine route taken by packets from control plane source to destination Network Layer: Control Plane 5-4 Routing protocols Routing protocol goal: determine “good” paths (equivalently, routes), from sending hosts to receiving host, through network of routers § path: sequence of routers packets will traverse in going from given initial source host to given final destination host § “good”: least “cost”, “fastest”, “least congested” § routing: a “top-10” networking challenge! Network Layer: Control Plane 5-5 Graph abstraction of the network 5 3 v w 5 2 u 2 1 z 3 1 2 x 1 y graph: G = (N,E) N = set of routers = { u, v, w, x, y, z } E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Network Layer: Control Plane 5-6 Graph abstraction: costs 5 c(x,x’) = cost of link (x,x’) 3 e.g., c(w,z) = 5 v w 5 2 u 2 1 z cost could always be 1, or 3 1 inversely related to bandwidth, 2 x 1 y or related to congestion cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) key question: what is the least-cost path between u and z ? routing algorithm: algorithm that finds that least cost path Network Layer: Control Plane 5-7 Routing algorithm classification Q: global or decentralized Q: static or dynamic? information? static: global: § routes change slowly over § all routers have complete time topology, link cost info dynamic: § “link state” algorithms § routes change more decentralized: quickly § router knows physically- periodic update connected neighbors, link costs to neighbors in response to link cost changes § iterative process of computation, exchange of info with neighbors § “distance vector” algorithms Network Layer: Control Plane 5-8  A link-state routing algorithm Dijkstra’s algorithm notation: § centralized: net topology, link § c(x, y): direct link cost costs known to all nodes from node x to y; accomplished via “link state broadcast” = ∞ if not direct neighbors all nodes have same info § D(v): current value of cost § computes least cost paths of path from source to from one node (“source”) to destination v all other nodes get forwarding table for that § p(v): predecessor node node along path from source to v § iterative: after k iterations, know least cost paths to k § N': set of nodes whose destinations least cost path definitively known Network Layer: Control Plane 5-9 Dijkstra’s link-state routing algorithm 1 Initialization: 2 N' = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = cu,v 6 else D(v) = ∞ 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) + cw,v ) 13 15 until all nodes in N' Network Layer: Control Plane 5-10 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 2 3 4 5 5 Initialization (step 0): For all a: if a adjacent to u then D(a) = cu,a v 3 w 2 5 u 2 1 z 3 1 2 x y 1 Network Layer: Control Plane 5-11 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2 3 4 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 u 2 1 z 3 1 2 x y 1 Network Layer: Control Plane 5-12 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 3 4 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 11 update D(b) for all b adjacent to a and not in N' : u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 2 D(v) = min ( D(v), D(x) + cx,v ) = min(2, 1+2) = 2 x y 1 D(w) = min ( D(w), D(x) + cx,w ) = min (5, 1+3) = 4 D(y) = min ( D(y), D(x) + cx,y ) = min(inf,1+1) = 2 Network Layer: Control Plane 5-13 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 3 4 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 u 2 1 z 3 1 2 x y 1 Network Layer: Control Plane 5-14 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 4 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 11 update D(b) for all b adjacent to a and not in N' : u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 x y 2 D(w) = min ( D(w), D(y) + cy,w ) = min (4, 2+1) = 3 1 D(z) = min ( D(z), D(y) + cy,z ) = min(inf,2+2) = 4 Network Layer: Control Plane 5-15 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 4 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 u 2 1 z 3 1 2 x y 1 Network Layer: Control Plane 5-16 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 11 update D(b) for all b adjacent to a and not in N' : u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 x y 2 D(w) = min ( D(w), D(v) + cv,w ) = min (3, 2+3) = 3 1 Network Layer: Control Plane 5-17 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 u 2 1 z 3 1 2 x y 1 Network Layer: Control Plane 5-18 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 4,y 5 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 11 update D(b) for all b adjacent to a and not in N' : u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 x y 2 D(z) = min ( D(z), D(w) + cw,z ) = min (4, 3+5) = 4 1 Network Layer: Control Plane 5-19 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 4,y 5 uxyvwz 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 u 2 1 z 3 1 2 x y 1 Network Layer: Control Plane 5-20 Dijkstra’s algorithm: an example v w x y z Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 4,y 5 uxyvwz 8 Loop 5 9 find a not in N' such that D(a) is a minimum v 3 w 10 add a to N' 2 5 11 update D(b) for all b adjacent to a and not in N' : u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 2 x y 1 Network Layer: Control Plane 5-21  Dijkstra’s algorithm: an example 5 v 3 w 2 5 u 2 1 z 3 1 2 x y 1 resulting least-cost-path tree from u: resulting forwarding table in u: destination outgoing link v w v (u,v) route from u to v directly u z x (u,x) y (u,x) route from u x y w (u,x) to all other x (u,x) destinations via x Network Layer: Control Plane 5-22 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(n2) § more efficient implementations possible: O(nlogn) Network Layer: Control Plane 5-23  Dijkstra’s algorithm, discussion § When link costs depend on traffic volume, route oscillations possible § Sample scenario: routing to destination a traffic entering at d, c, e with rates 1, e (