Chapter 5 Network Layer Control Plane PDF

Chapter 5 Network Layer: 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...

Chapter 5 Network Layer: 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:  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!) Computer  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 material. Networking: A Top- For a revision history, see the slide note for this page. Down Approach Thanks and enjoy! JFK/KWR 8th edition Jim Kurose, Keith Ross All material copyright 1996-2023 Pearson, 2020 J.F Kurose and K.W. Ross, All Rights Reserved Network layer control plane: our goals  understand principles  instantiation, behind network implementation in the control plane: Internet: traditional routing OSPF, BGP algorithms OpenFlow, ODL and ONOS SDN controllers controllers network management, Internet Control Message configuration Protocol: ICMP SNMP, YANG/NETCONF Network Layer: 5-2  Network layer: “control plane” roadmap  introduction  routing protocols  link state  distance vector  intra-ISP routing: OSPF  routing among ISPs: BGP  network  SDN control plane management,  Internet Control configuration SNMP Message Protocol NETCONF/YANG Network Layer: 5-3 Network-layer functions  forwarding: move packets from router’s input to appropriate router output data plane  routing: determine route taken by packets from source to control plane destination Two approaches to structuring network control plane:  per-router control (traditional)  logically centralized control (software defined networking) Network Layer: 5-4 Per-router control plane Individual routing algorithm components in each and every router interact in the control plane Routing Algorithm control plane data plane values in arriving packet header 0111 1 2 3 Network Layer: 5-5 Software-Defined Networking (SDN) control plane Remote controller computes, installs forwarding tables in routers Remote Controller control plane data plane CA CA CA CA CA values in arriving packet header 0111 1 2 3 Network Layer: 5-6 Per-router SDN control control plane plane Network layer: “control plane” roadmap  introduction  routing protocols  link state  distance vector  intra-ISP routing: OSPF  routing among ISPs: BGP  network  SDN control plane management, configuration  Internet Control SNMP Message Protocol NETCONF/YANG Network Layer: 5-8 Routing protocols mobile network national or global ISP Routing protocol goal: determine “good” paths (equivalently, routes), from sending hosts to receiving applicati on host, through network of routers transpor t network  path: sequence of routers packets physical link networ k link networ k link traverse from given initial source physica physica l l host to final destination host networ k link networ k link  “good”: least “cost”, “fastest”, physica networ l physica k datacenter l link network physica “least congested” l applicati  routing: a “top-10” networking on transpor enterprise challenge! network t network link physical Network Layer: 5-9  Graph abstraction: link costs 5 ca,b: cost of direct link connecting a 3 v w 5 and b 2 u e.g., cw,z = 5, cu,z = ∞ 2 3 1 z 1 2 x 1 y cost defined by network operator: could always be 1, or inversely related to bandwidth, graph: G = (N,E) or inversely related to N: set of routers = { u, v, w, x,congestion y, z } E: set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y Network Layer: 5-10  Routing algorithm classification global: all routers have complete topology, link cost info “link state” algorithms How fast dynamic: routes do static: routes change more quickly routes change slowly periodic updates change? or in response to over time link cost changes decentralized: iterative process of computation, exchange of info with neighbors routers initially only know link costs to attached neighbors “distance vector” algorithms global or decentralized information? Network Layer: 5-11 Network layer: “control plane” roadmap  introduction  routing protocols  link state  distance vector  intra-ISP routing: OSPF  routing among ISPs: BGP  network  SDN control plane management, configuration  Internet Control SNMP Message Protocol NETCONF/YANG Network Layer: 5-12 Dijkstra’s link-state routing algorithm  centralized: network notation topology, link costs known to all nodes  cx,y: direct link cost accomplished via “link state from node x to y; = ∞ if broadcast” not direct neighbors all nodes have same info  D(v): current estimate  computes least cost paths of cost of least-cost- from one node (“source”) to path from source to all other nodes destination v gives forwarding table for that  p(v): predecessor node node along path from source  iterative: after k iterations, to v know least cost path to k  N': set of nodes whose destinations least-cost-path definitively knownNetwork Layer: 5-13 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 8 6Loopelse D(v) = ∞ 9find 7 w not in N' such that D(w) is a minimum add w to N' 10 update D(v) for all v adjacent to w and not in N' : 11 12 D(v) = min ( D(v), D(w) + cw,v ) 13 15 until all nodes in N' Network Layer: 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 2 3 4 5 5 Initialization (step 0): For all a: if a adjacent to u then 3 v w 5 D(a) = cu,a 2 u 2 1 z 3 1 2 x 1 y 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 u 2 1 z 3 1 2 x 1 y 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 update D(b) for all b adjacent to a and not in N' 11 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 1 y 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 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 u 2 1 z 3 1 2 x 1 y 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 update D(b) for all b adjacent to a and not in N' 11 u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 2 x 1 y D(w) = min ( D(w), D(y) + cy,w ) = min (4, 2+1) = 3 D(z) = min ( D(z), D(y) + cy,z ) = min(inf,2+2) = 4 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 u 2 1 z 3 1 2 x 1 y 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 update D(b) for all b adjacent to a and not in N' 11 u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 2 x 1 y D(w) = min ( D(w), D(v) + cv,w ) = min (3, 2+3) = 3 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 u 2 1 z 3 1 2 x 1 y 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 update D(b) for all b adjacent to a and not in N' 11 u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 2 x 1 y D(z) = min ( D(z), D(w) + cw,z ) = min (4, 3+5) = 4 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 u 2 1 z 3 1 2 x 1 y 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 9find a not in N' such that D(a) is a minimum 3 add a to N' 10 v w 5 2 update D(b) for all b adjacent to a and not in N' 11 u 2 1 z D(b) = min ( D(b), D(a) + ca,b ) 3 1 2 x 1 y  Dijkstra’s algorithm: an example 5 3 v w 5 2 u 2 1 z 3 1 2 x 1 y resulting forwarding table in u: resulting least-cost-path tree from u: destinationoutgoing link v w v (u,v) route from u to v directly u z x (u,x) y (u,x) route from u to x y w (u,x) all other x (u,x) destinations via x Network Layer: 5-27  Dijkstra’s algorithm: another example v w x y z D(v), D(w), D(x), D(y), D(z), x 9 Step N' p(v) p(w) p(x) p(y) p(z) 0 u 7,u 3,u 5,u ∞ ∞ 5 7 4 1 uw 6,w 5,u 11,w ∞ 8 2 uwx 6,w 11,w 14,x 3 w z u y 2 3 uwxv 10,v 14,x 3 4 uwxvy 12,y 7 4 5 uwxvyz v notes:  construct least-cost-path tree by tracing predecessor nodes  ties can exist (can be broken arbitrarily) Network Layer: 5-28 Dijkstra’s algorithm: discussion algorithm complexity: n nodes  each of n iteration: need to check all nodes, w, not in N  n(n+1)/2 comparisons: O(n2) complexity  more efficient implementations possible: O(nlogn) message complexity:  each router must broadcast its link state information to other n routers  efficient (and interesting!) broadcast algorithms: O(n) link crossings to disseminate a broadcast message from one source  each router’s message crosses O(n) links: overall message complexity: O(n2) Network Layer: 5-29  Dijkstra’s algorithm: oscillations possible  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 (