ECE 4436A Networking: Principles, Protocols, and Architectures PDF

ECE 4436A NETWORKING: PRINCIPLES, PROTOCOLS, AND ARCHITECTURES Dr. Fang (Fiona) Fang Department of Electrical and Computer Engineering University of Western Ontario SOME SLIDES ADAPTED FROM KUROSE AND ROSS NOTES PROVIDED THROUGH PUBL...

ECE 4436A NETWORKING: PRINCIPLES, PROTOCOLS, AND ARCHITECTURES Dr. Fang (Fiona) Fang Department of Electrical and Computer Engineering University of Western Ontario SOME SLIDES ADAPTED FROM KUROSE AND ROSS NOTES PROVIDED THROUGH PUBLISHER. THE AUTHOR’S AND PUBLISHER’S COPYRIGHT HOLDS THROUGHOUT. Introduction: 1-2 Network layer control plane: our goals §understand principles § instantiation, implementation behind network control in the Internet: plane: OSPF, BGP traditional routing algorithms OpenFlow, ODL and ONOS SDN controllers controllers network management, Internet Control Message configuration Protocol: ICMP SNMP, YANG/NETCONF Network Layer: 5-3  Network layer: “control plane” roadmap § introduction § routing protocols § link state § distance vector § intra-ISP routing: OSPF § routing among ISPs: BGP § network management, § SDN control plane configuration § Internet Control Message SNMP Protocol NETCONF/YANG Network Layer: 5-4 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 destination control plane Two approaches to structuring network control plane: § per-router control (traditional) § logically centralized control (software defined networking) Network Layer: 5-5 Per-router control plane Individual routing algorithm components in each and every router interact in the control plane 4.1 OVERVIEW OF NETWORK LAYER 309 Routing Algorithm Routing algorithm control Control plane plane Data plane Local forwarding data table header output plane 0100 3 0110 2 0111 2 1001 1 Values in arriving values in arriving packet’s header 1 packet header 1101 2 3 0111 1 2 3 Figure 4.2 ♦ Routing algorithms determine values in forward tables Network Layer: 4-6 tables. In this example, a routing algorithm runs in each and every router and both 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-7  Network layer: “control plane” roadmap § introduction § routing protocols § link state § distance vector § intra-ISP routing: OSPF § routing among ISPs: BGP § network management, § SDN control plane configuration § Internet Control Message SNMP 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 host, application transport through network of routers network link physical § path: sequence of routers packets network network link link physical traverse from given initial source host physical to final destination host network link physical network link § “good”: least “cost”, “fastest”, “least physical network link datacenter physical network congested” § routing: a “top-10” networking application transport network challenge! enterprise network link physical Network Layer: 5-9 Graph abstraction: link costs 5 ca,b: cost of direct link connecting a and b v 3 w e.g., cw,z = 5, cu,z = ∞ 2 5 u 2 1 z 3 cost defined by network operator: 1 x y 2 could always be 1, or inversely related 1 to bandwidth, or inversely related to congestion 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: 5-10  Routing algorithm classification global: all routers have complete topology, link cost info “link state” algorithms How fast dynamic: routes change do routes static: routes change more quickly change? slowly over time periodic updates or in response to 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 management, § SDN control plane configuration § Internet Control Message SNMP Protocol NETCONF/YANG Network Layer: 5-12 Dijkstra’s link-state routing algorithm § centralized: network topology, link notation costs known to all nodes § cx,y: direct link cost from accomplished via “link state node x to y; = ∞ if not direct broadcast” neighbors all nodes have same info § D(v): current estimate of cost § computes least cost paths from one of least-cost-path from source node (“source”) to all other nodes to destination v gives forwarding table for that node § p(v): predecessor node along path from source to v § iterative: after k iterations, know § N': set of nodes whose least- least cost path to k destinations cost-path definitively known Network Layer: 5-14 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: 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 3,y 4,y 4 uxyvw 4,y 5 uxyvwz Initialization (step 0): For all a: if a adjacent to then D(a) = cu,a 5 3 find a not in N' such that D(a) is a minimum v w add a to N' 2 5 u 2 1 z update D(b) for all b adjacent to a and not in N' : 3 D(b) = min ( D(b), D(a) + ca,b ) 1 2 x y 1 Network Layer: 5-16  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 to all x y w (u,x) other destinations x (u,x) via x Network Layer: 5-17  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 u 3 w y z 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-18 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-19  Network layer: “control plane” roadmap § introduction § routing protocols § link state § distance vector § intra-ISP routing: OSPF § routing among ISPs: BGP § network management, § SDN control plane configuration § Internet Control Message SNMP Protocol NETCONF/YANG Network Layer: 5-21 Distance vector algorithm Based on Bellman-Ford (BF) equation (dynamic programming): Bellman-Ford equation Let Dx(y): cost of least-cost path from x to y. Then: Dx(y) = minv { cx,v + Dv(y) } v’s estimated least-cost-path cost to y min taken over all neighbors v of x direct cost of link from x to v Network Layer: 5-22 Bellman-Ford Example Suppose that u’s neighboring nodes, x,v,w, know that for destination z: Dv(z) = 5 Dw(z) = 3 Bellman-Ford equation says: 5 Du(z) = min { cu,v + Dv(z), 3 w v 5 cu,x + Dx(z), 2 u 2 1 z cu,w + Dw(z) } 3 1 2 = min {2 + 5, x y 1 + 3, 1 5 + 3} = 4 Dx(z) = 3 node achieving minimum (x) is next hop on estimated least- cost path to destination (z) Network Layer: 5-23 Distance vector algorithm key idea: § from time-to-time, each node sends its own distance vector estimate to neighbors § when x receives new DV estimate from any neighbor, it updates its own DV using B-F equation: Dx(y) ← minv{cx,v + Dv(y)} for each node y ∊ N § under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y) Network Layer: 5-24 Distance vector algorithm: each node: iterative, asynchronous: each local iteration caused by: wait for (change in local link § local link cost change cost or msg from neighbor) § DV update message from neighbor recompute DV estimates using distributed, self-stopping: each node notifies neighbors only when DV received from neighbor its DV changes § neighbors then notify their if DV to any destination has neighbors – only if necessary changed, notify neighbors § no notification received, no actions taken! Network Layer: 5-25  Distance vector: example DV in a: Da(a)=0 Da(b) = 8 Da(c) = ∞ a b c Da(d) = 1 8 1 Da(e) = ∞ t=0 Da(f) = ∞ 1 1 Da(g) = ∞ Da(h) = ∞ § All nodes have Da(i) = ∞ distance estimates to nearest A few asymmetries: d e f § missing link neighbors (only) 1 1 § larger cost § All nodes send their local distance vector to 1 1 1 their neighbors g h i 1 1 Network Layer: 5-26  Distance vector example: iteration a b c 8 1 t=1 1 1 All nodes: § receive distance vectors from neighbors d e f § compute their new 1 1 local distance vector § send their new 1 1 1 local distance vector to neighbors g h i 1 1 Network Layer: 5-27  Distance vector example: iteration a compute compute b compute c 8 1 t=1 1 1 All nodes: § receive distance vectors from neighbors d compute compute e compute f § compute their new 1 1 local distance vector § send their new 1 1 1 local distance vector to neighbors g compute h compute compute i 1 1 Network Layer: 5-28  Distance vector example: iteration a b c 8 1 t=1 1 1 All nodes: § receive distance vectors from neighbors d e f § compute their new 1 1 local distance vector § send their new 1 1 1 local distance vector to neighbors g h i 1 1 Network Layer: 5-29  Distance vector example: iteration a b c 8 1 t=2 1 1 All nodes: § receive distance vectors from neighbors d e f § compute their new 1 1 local distance vector § send their new 1 1 1 local distance vector to neighbors g h i 1 1 Network Layer: 5-30  Distance vector example: iteration compute a compute b compute c 2 1 t=2 1 1 All nodes: § receive distance vectors from neighbors compute d compute e compute f § compute their new 1 1 local distance vector § send their new 1 1 1 local distance vector to neighbors g compute compute h compute i 8 1 Network Layer: 5-31  Distance vector example: iteration a b c 8 1 t=2 1 1 All nodes: § receive distance vectors from neighbors d e f § compute their new 1 1 local distance vector § send their new 1 1 1 local distance vector to neighbors g h i 1 1 Network Layer: 5-32 Distance vector example: iteration …. and so on Let’s next take a look at the iterative computations at nodes Network Layer: 5-33  Distance vector example: computation DV in b: Db(a) = 8 Db(f) = ∞ DV in c: Dc(a) = ∞ Db(c) = 1 Db(g) = ∞ Dc(b) = 1 Db(d) = ∞ Db(h) = ∞ Dc(c) = 0 DV in a: Dc(d) = ∞ Db(e) = 1 Db(i) = ∞ Da(a)=0 Dc(e) = ∞ Da(b) = 8 Dc(f) = ∞ Da(c) = ∞ a b c 8 1 Dc(g) = ∞ Da(d) = 1 Dc(h) = ∞ Da(e) = ∞ t=1 Da(f) = ∞ 1 1 Dc(i) = ∞ Da(g) = ∞ § b receives DVs Da(h) = ∞ DV in e: from a, c, e Da(i) = ∞ De(a) = ∞ De(b) = 1 d e f De(c) = ∞ 1 1 De(d) = 1 De(e) = 0 De(f) = 1 1 1 1 De(g) = ∞ De(h) = 1 De(i) = ∞ g h i 1 1 Network Layer: 5-34  Distance vector example: computation DV in b: Db(a) = 8 Db(f) = ∞ DV in c: Dc(a) = ∞ Db(c) = 1 Db(g) = ∞ Dc(b) = 1 Db(d) = ∞ Db(h) = ∞ Dc(c) = 0 DV in a: Dc(d) = ∞ Db(e) = 1 Db(i) = ∞ Da(a)=0 Dc(e) = ∞ Da(b) = 8 Dc(f) = ∞ Da(c) = ∞ a b c 8 compute 1 Dc(g) = ∞ Da(d) = 1 Dc(h) = ∞ Da(e) = ∞ t=1 Da(f) = ∞ 1 1 Dc(i) = ∞ Da(g) = ∞ § b receives DVs Da(h) = ∞ DV in e: from a, c, e, Da(i) = ∞ De(a) = ∞ computes: e De(b) = 1 d e f De(c) = ∞ 1 Db(a) = min{cb,a+Da(a), cb,c +Dc(a), cb,e+De(a)} = min{8,∞,∞} =8 1 De(d) = 1 Db(c) = min{cb,a+Da(c), cb,c +Dc(c), c b,e +De(c)} = min{∞,1,∞} = 1 De(e) = 0 Db(d) = min{cb,a+Da(d), cb,c +Dc(d), c b,e +De(d)} = min{9,2,∞} = 2 De(f) = 1 1 1 1 De(g) = ∞ Db(e) = min{cb,a+Da(e), cb,c +Dc(e), c b,e +De(e)} = min{∞,∞,1} = 1 De(h) = 1 Db(f) = min{cb,a+Da(f), cb,c +Dc(f), c b,e +De(f)} = min{∞,∞,2} = 2 DV in b: De(i) = ∞ Db(g) = min{cb,a+Da(g), cb,c +Dc(g), c b,e+De(g)} = min{∞, ∞, ∞} = ∞ Db(a) = 8 Db(f) =2 g h D (c) = 1 Db(g) i =∞ 1 ∞, 2} = 2 Db(h) = min{cb,a+Da(h), cb,c +Dc(h), c b,e+De(h)} = min{∞, 1Db(d) = 2 Db(h) = 2 b Db(i) = min{cb,a+Da(i), cb,c +Dc(i), c b,e+De(i)} = min{∞, ∞, ∞} = ∞ Db(e) = 1 Db(i) = ∞ Network Layer: 5-35  Distance vector example: computation DV in b: Db(a) = 8 Db(f) = ∞ DV in c: Dc(a) = ∞ Db(c) = 1 Db(g) = ∞ Dc(b) = 1 Db(d) = ∞ Db(h) = ∞ Dc(c) = 0 DV in a: Dc(d) = ∞ Db(e) = 1 Db(i) = ∞ Da(a)=0 Dc(e) = ∞ Da(b) = 8 Dc(f) = ∞ Da(c) = ∞ a b c 8 1 Dc(g) = ∞ Da(d) = 1 Dc(h) = ∞ Da(e) = ∞ t=1 Da(f) = ∞ 1 1 Dc(i) = ∞ Da(g) = ∞ § c receives DVs Da(h) = ∞ DV in e: from b Da(i) = ∞ De(a) = ∞ De(b) = 1 d e f De(c) = ∞ 1 1 De(d) = 1 De(e) = 0 De(f) = 1 1 1 1 De(g) = ∞ De(h) = 1 De(i) = ∞ g h i 1 1 Network Layer: 5-36  Distance vector example: computation DV in b: Db(a) = 8 Db(f) = ∞ DV in c: Dc(a) = ∞ Db(c) = 1 Db(g) = ∞ Dc(b) = 1 Db(d) = ∞ Db(h) = ∞ Dc(c) = 0 Db(e) = 1 Db(i) = ∞ Dc(d) = ∞ Dc(e) = ∞ Dc(f) = ∞ a b c compute Dc(g) = ∞ 8 1 Dc(h) = ∞ t=1 1 1 Dc(i) = ∞ § c receives DVs from b computes: d b(a}} = 1 + 8 = 9 Dc(a) = min{cc,b+D e f DV in c: Dc(b) = min{cc,b+Db(b)} = 1 + 0 = 1 Dc(a) = 9 Dc(d) = min{cc,b+Db(d)} = 1+ ∞ = ∞ Dc(b) = 1 Dc(e) = min{cc,b+Db(e)} = 1 + 1 = 2 Dc(c) = 0 Dc(d) = 2 Dc(f) = min{cc,b+Db(f)} = 1+ ∞ = ∞ Dc(e) = ∞ Dc(g) = min{cc,b+Db(g)} = 1+ ∞ = ∞ * Check out the online interactive Dc(f) = ∞ exercises for more examples: Dc(h) = min{cbc,bg+Db(h)} = 1+ ∞ = ∞ h Dc(g) = ∞ i http://gaia.cs.umass.edu/kurose_ross/interactive/ Dc(i) = min{cc,b+Db(i)} = 1+ ∞ = ∞ Dc(h) = ∞ Dc(i) = ∞ Network Layer: 5-37  Distance vector example: computation DV in b: Db(a) = 8 Db(f) = ∞ Db(c) = 1 Db(g) = ∞ Db(d) = ∞ Db(h) = ∞ DV in e: DV in d: Db(e) = 1 Db(i) = ∞ De(a) = ∞ Dc(a) = 1 De(b) = 1 Dc(b) = ∞ a De(c) = ∞ Dc(c) = ∞ b c 8 1 De(d) = 1 Dc(d) = 0 De(e) = 0 t=1 Dc(e) = 1 Dc(f) = ∞ 1 Q: what is new DV computed in e at 1t=1? De(f) = 1 De(g) = ∞ § e receives DVs Dc(g) = 1 De(h) = 1 from b, d, f, h Dc(h) = ∞ De(i) = ∞ Dc(i) = ∞ d compute e 1 f DV in f: DV in h: 1 Dc(a) = ∞ Dc(a) = ∞ Dc(b) = ∞ Dc(b) = ∞ Dc(c) = ∞ Dc(c) = ∞ 1 1 1 Dc(d) = ∞ Dc(d) = ∞ Dc(e) = 1 Dc(e) = 1 Dc(f) = 0 Dc(f) = ∞ Dc(g) = ∞ Dc(g) = 1 g h i Dc(h) = ∞ 1 1 Dc(h) = 0 Dc(i) = 1 Dc(i) = 1 Network Layer: 5-38 Distance vector: state information diffusion Iterative communication, computation steps diffuses information through network: t=0 c’s state at t=0 is at c only a b c 8 1 c’s state at t=0 has propagated to b, and t=1 may influence distance vector computations up to 1 hop away, i.e., at b 1 1 t=1 t=2 c’s state at t=0 may now influence distance t=2 vector computations up to 2 hops away, i.e., at b and now at a, e as well d e f 1 1 c’s state at t=0 may influence distance vector t=3 computations up to 3 hops away, i.e., at b,a,e 1 1 1 t=3 and now at c,f,h as well c’s state at t=0 may influence distance vector t=4 computations up to 4 hops away, i.e., at b,a,e, g 1 h 1 i c, f, h and now at g,i as well t=4  Distance vector: link cost changes link cost changes: 1 y 4 1 § node detects local link cost change x z 50 § updates routing info, recalculates local DV § if DV changes, notify neighbors t0 : y detects link-cost change, updates its DV, informs its neighbors. “good news t1 : z receives update from y, updates its table, computes new least travels fast” cost to x , sends its neighbors its DV. t2 : y receives z’s update, updates its distance table. y’s least costs do not change, so y does not send a message to z. Network Layer: 5-40 Distance vector: link cost changes link cost changes: 60 y 4 1 § node detects local link cost change x z 50 § “bad news travels slow” – count-to-infinity problem: y sees direct link to x has new cost 60, but z has said it has a path at cost of 5. So y computes “my new cost to x will be 6, via z); notifies z of new cost of 6 to x. z learns that path to x via y has new cost 6, so z computes “my new cost to x will be 7 via y), notifies y of new cost of 7 to x. y learns that path to x via z has new cost 7, so y computes “my new cost to x will be 8 via y), notifies z of new cost of 8 to x. z learns that path to x via y has new cost 8, so z computes “my new cost to x will be 9 via y), notifies y of new cost of 9 to x. … § see text for solutions. Distributed algorithms are tricky! Network Layer: 5-41 Comparison of LS and DV algorithms message complexity robustness: what happens if router LS: n routers, O(n2) messages sent malfunctions, or is compromised? DV: exchange between neighbors; LS: convergence time varies router can advertise incorrect link cost each router computes only its own speed of convergence table LS: O(n2) algorithm, O(n2) messages DV: may have oscillations DV router can advertise incorrect path DV: convergence time varies cost (“I have a really low cost path to may have routing loops everywhere”): black-holing count-to-infinity problem each router’s table used by others: error propagate thru network Network Layer: 5-42  Network layer: “control plane” roadmap § introduction § routing protocols § intra-ISP routing: OSPF § routing among ISPs: BGP § SDN control plane § Internet Control Message § network management, Protocol configuration SNMP NETCONF/YANG Network Layer: 5-43 Making routing scalable our routing study thus far - idealized § all routers identical § network “flat” … not true in practice scale: billions of destinations: administrative autonomy: § can’t store all destinations in § Internet: a network of networks routing tables! § each network admin may want to § routing table exchange would control routing in its own network swamp links! Network Layer: 5-44 Internet approach to scalable routing aggregate routers into regions known as “autonomous systems” (AS) (a.k.a. “domains”) intra-AS (aka “intra-domain”): inter-AS (aka “inter-domain”): routing among within same AS routing among AS’es (“network”) § gateways perform inter-domain § all routers in AS must run same intra- routing (as well as intra-domain domain protocol routing) § routers in different AS can run different intra-domain routing protocols § gateway router: at “edge” of its own AS, has link(s) to router(s) in other AS’es Network Layer: 5-45 Interconnected ASes forwarding table configured by intra- and inter-AS routing algorithms Intra-AS Inter-AS Routing Routing § intra-AS routing determine entries for forwarding destinations within AS table § inter-AS & intra-AS determine entries for external destinations intra-AS 3c routing3a inter-AS routing intra-AS 2c 3b 2a routing 2b 1c intra-AS AS3 1a routing 1b AS2 1d AS1 Network Layer: 5-46  Inter-AS routing: a role in intradomain forwarding § suppose router in AS1 receives AS1 inter-domain routing must: datagram destined outside of AS1: 1. learn which destinations reachable router should forward packet to through AS2, which through AS3 gateway router in AS1, but which 2. propagate this reachability info to all one? routers in AS1 3c 3a 2c other 3b 2a networks 2b 1c AS3 other 1a 1b AS2 networks 1d AS1 Network Layer: 5-47 Inter-AS routing: routing within an AS most common intra-AS routing protocols: § RIP: Routing Information Protocol [RFC 1723] classic DV: DVs exchanged every 30 secs no longer widely used § EIGRP: Enhanced Interior Gateway Routing Protocol DV based formerly Cisco-proprietary for decades (became open in 2013 [RFC 7868]) § OSPF: Open Shortest Path First [RFC 2328] link-state routing IS-IS protocol (ISO standard, not RFC standard) essentially same as OSPF Network Layer: 5-48 OSPF (Open Shortest Path First) routing § “open”: publicly available § classic link-state each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in entire AS multiple link costs metrics possible: bandwidth, delay each router has full topology, uses Dijkstra’s algorithm to compute forwarding table § security: all OSPF messages authenticated (to prevent malicious intrusion) Network Layer: 5-49  Hierarchical OSPF § two-level hierarchy: local area, backbone. link-state advertisements flooded only in area, or backbone each node has detailed area topology; only knows direction to reach other destinations area border routers: boundary router: “summarize” distances to connects to other ASes backbone destinations in own area, backbone router: advertise in backbone runs OSPF limited to backbone local routers: flood LS in area only area 3 compute routing within area internal forward packets to outside routers via area border router area 1 area 2 Network Layer: 5-50  Network layer: “control plane” roadmap § introduction § routing protocols § intra-ISP routing: OSPF § routing among ISPs: BGP § SDN control plane § Internet Control Message § network management, Protocol configuration SNMP NETCONF/YANG Network Layer: 5-51 Internet inter-AS routing: BGP § BGP (Border Gateway Protocol): the de facto inter-domain routing protocol “glue that holds the Internet together” § allows subnet to advertise its existence, and the destinations it can reach, to rest of Internet: “I am here, here is who I can reach, and how” § BGP provides each AS a means to: eBGP: obtain subnet reachability information from neighboring ASes iBGP: propagate reachability information to all AS-internal routers. determine “good” routes to other networks based on reachability information and policy Network Layer: 5-52 eBGP, iBGP connections 2b 2a 2c ∂ 1b 3b 2d 1a 1c ∂ 3a 3c AS 2 1d 3d AS 1 eBGP connectivity AS 3 logical iBGP connectivity 1c gateway routers run both eBGP and iBGP protocols Network Layer: 5-53 BGP basics § BGP session: two BGP routers (“peers”) exchange BGP messages over semi-permanent TCP connection: advertising paths to different destination network prefixes (BGP is a “path vector” protocol) § when AS3 gateway 3a advertises path AS3,X to AS2 gateway 2c: AS3 promises to AS2 it will forward datagrams towards X AS 3 3b AS 1 1b 3a 3c 1a 1c AS 2 3d 2b 1d BGP advertisement: 2a 2c X AS3, X 2d Network Layer: 5-54 Path attributes and BGP routes § BGP advertised route: prefix + attributes prefix: destination being advertised two important attributes: AS-PATH: list of ASes through which prefix advertisement has passed NEXT-HOP: indicates specific internal-AS router to next-hop AS § policy-based routing: gateway receiving route advertisement uses import policy to accept/decline path (e.g., never route through AS Y). AS policy also determines whether to advertise path to other other neighboring ASes Network Layer: 5-55 BGP path advertisement AS 3 3b AS 1 1b 3a 3c 1a 1c AS 2 3d X 2b 1d AS3, X AS2,AS3,X 2a 2c 2d § AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3 router 3a § based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates (via iBGP) to all AS2 routers § based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2, AS3, X to AS1 router 1c Network Layer: 5-56 BGP path advertisement (more) AS 3 3b AS 1 1b AS3,X 3a 3c AS3,X AS3,X 1a 1c AS 2 3d X 2b AS3,X 1d AS3, X AS2,AS3,X 2a 2c 2d gateway router may learn about multiple paths to destination: § AS1 gateway router 1c learns path AS2,AS3,X from 2a § AS1 gateway router 1c learns path AS3,X from 3a § based on policy, AS1 gateway router 1c chooses path AS3,X and advertises path within AS1 via iBGP Network Layer: 5-57 BGP messages § BGP messages exchanged between peers over TCP connection § BGP messages: OPEN: opens TCP connection to remote BGP peer and authenticates sending BGP peer UPDATE: advertises new path (or withdraws old) KEEPALIVE: keeps connection alive in absence of UPDATES; also ACKs OPEN request NOTIFICATION: reports errors in previous msg; also used to close connection Network Layer: 5-58  BGP path advertisement AS 3 3b AS 1 1b AS3,X 3a 3c AS3,X 1 AS3,X 1a 1c AS 2 3d X 2 2b local link AS3,X 2 1 interfaces 1d AS3, X at 1a, 1d AS2,AS3,X 2a 2c 2d dest interface § recall: 1a, 1b, 1d learn via iBGP from 1c: “path to X goes through 1c” … … 1c 1 § at 1d: OSPF intra-domain routing: to get to 1c, use interface 1 X 1 § at 1d: to get to X, use interface 1 … … Network Layer: 5-59  BGP path advertisement AS 3 3b AS 1 1b 3a 3c 1 1a 1c AS 2 3d X 2 2b 1d 2a 2c 2d dest interface … … § recall: 1a, 1b, 1d learn via iBGP from 1c: “path to X goes through 1c” 1c 2 § at 1d: OSPF intra-domain routing: to get to 1c, use interface 1 X 2 … … § at 1d: to get to X, use interface 1 § at 1a: OSPF intra-domain routing: to get to 1c, use interface 2 § at 1a: to get to X, use interface 2 Network Layer: 5-60 Why different Intra-, Inter-AS routing ? policy: § inter-AS: admin wants control over how its traffic routed, who routes through its network § intra-AS: single admin, so policy less of an issue scale: § hierarchical routing saves table size, reduced update traffic performance: § intra-AS: can focus on performance § inter-AS: policy dominates over performance Network Layer: 5-61  Network layer: “control plane” roadmap § introduction § routing protocols § intra-ISP routing: OSPF § routing among ISPs: BGP § SDN control plane § Internet Control Message § network management, Protocol configuration SNMP NETCONF/YANG Network Layer: 5-66 Software defined networking (SDN) § Internet network layer: historically implemented via distributed, per-router control approach: monolithic router contains switching hardware, runs proprietary implementation of Internet standard protocols (IP, RIP, IS-IS, OSPF, BGP) in proprietary router OS (e.g., Cisco IOS) different “middleboxes” for different network layer functions: firewalls, load balancers, NAT boxes,.. § ~2005: renewed interest in rethinking network control plane Network Layer: 5-67 Per-router control plane Individual routing algorithm components in each and every router interact in the control plane 4.1 OVERVIEW OF NETWORK LAYER 309 Routing Algorithm Routing algorithm control Control plane plane Data plane Local forwarding data table header output plane 0100 3 0110 2 0111 2 1001 1 Values in arriving values in arriving packet’s header 1 packet header 1101 2 3 0111 1 2 3 Figure 4.2 ♦ Routing algorithms determine values in forward tables Network Layer: 4-68 tables. In this example, a routing algorithm runs in each and every router and both 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: 4-69 Software defined networking (SDN) Why a logically centralized control plane? § easier network management: avoid router misconfigurations, greater flexibility of traffic flows § table-based forwarding (recall OpenFlow API) allows “programming” routers centralized “programming” easier: compute tables centrally and distribute distributed “programming” more difficult: compute tables as result of distributed algorithm (protocol) implemented in each-and-every router § open (non-proprietary) implementation of control plane foster innovation: let 1000 flowers bloom Network Layer: 5-70 Traffic engineering: difficult with traditional routing 5 3 2 v w 5 u 2 3 1 z 1 2 x 1 y Q: what if network operator wants u-to-z traffic to flow along uvwz, rather than uxyz? A: need to re-define link weights so traffic routing algorithm computes routes accordingly (or need a new routing algorithm)! link weights are only control “knobs”: not much control! Network Layer: 5-72 Traffic engineering: difficult with traditional routing 5 3 2 v w 5 u 2 3 1 z 1 2 x 1 y Q: what if network operator wants to split u-to-z traffic along uvwz and uxyz (load balancing)? A: can’t do it (or need a new routing algorithm) Network Layer: 5-73 Traffic engineering: difficult with traditional routing 5 3 2 v w 5 u 2 3 1 z 1 2 x 1 y Q: what if w wants to route blue and red traffic differently from w to z? A: can’t do it (with destination-based forwarding, and LS, DV routing) We learned in Chapter 4 that generalized forwarding and SDN can be used to achieve any routing desired Network Layer: 5-74  Software defined networking (SDN) 3. control plane functions 4. programmable routing access … load control balance external to data-plane control switches applications Remote Controller control plane data plane CA 2. control, data CA CA CA CA plane separation 1: generalized “flow-based” forwarding (e.g., OpenFlow) Network Layer: 5-75 Software defined networking (SDN) network-control applications Data-plane switches: … routing § fast, simple, commodity switches load access implementing generalized data-plane control balance forwarding (Section 4.4) in hardware control plane § flow (forwarding) table computed, northbound API installed under controller supervision SDN Controller § API for table-based switch control (network operating system) (e.g., OpenFlow) southbound API defines what is controllable, what is not § protocol for communicating with data plane controller (e.g., OpenFlow) SDN-controlled switches Network Layer: 5-76 Software defined networking (SDN) network-control applications SDN controller (network OS): … routing § maintain network state access load information control balance § interacts with network control northbound API control plane applications “above” via northbound API SDN Controller (network operating system) § interacts with network switches “below” via southbound API southbound API § implemented as distributed system data for performance, scalability, fault- plane tolerance, robustness SDN-controlled switches Network Layer: 5-77 Software defined networking (SDN) network-control applications network-control apps: … routing § “brains” of control: access load implement control functions control balance using lower-level services, API northbound API control plane provided by SDN controller SDN Controller § unbundled: can be provided by (network operating system) 3rd party: distinct from routing vendor, or SDN controller southbound API data plane SDN-controlled switches Network Layer: 5-78 Components of SDN controller routing access load control balance interface layer to network Interface, abstractions for network control apps control apps: abstractions API network graph RESTful API … intent network-wide state statistics … flow tables SDN management : state of networks links, switches, Network-wide distributed, robust state management controller services: a distributed database Link-state info host info … switch info communication: communicate OpenFlow … SNMP between SDN controller and Communication to/from controlled devices controlled switches Network Layer: 5-79 OpenFlow protocol § operates between controller, switch OpenFlow Controller § TCP used to exchange messages The picture can't be optional encryption displayed. § three classes of OpenFlow messages: controller-to-switch asynchronous (switch to controller) symmetric (misc.) § distinct from OpenFlow API API used to specify generalized forwarding actions Network Layer: 5-80 OpenFlow: controller-to-switch messages Key controller-to-switch messages OpenFlow Controller § features: controller queries switch The picture can't be displayed. features, switch replies § configure: controller queries/sets switch configuration parameters § modify-state: add, delete, modify flow entries in the OpenFlow tables § packet-out: controller can send this packet out of specific switch port Network Layer: 5-81 OpenFlow: switch-to-controller messages Key switch-to-controller messages OpenFlow Controller § packet-in: transfer packet (and its The picture can't be control) to controller. See packet-out displayed. message from controller § flow-removed: flow table entry deleted at switch § port status: inform controller of a change on a port. Fortunately, network operators don’t “program” switches by creating/sending OpenFlow messages directly. Instead use higher-level abstraction at controller Network Layer: 5-82 SDN: control/data plane interaction example Dijkstra’s link-state routing 1 S1, experiencing link failure uses 4 OpenFlow port status message to network graph RESTful API … intent notify controller statistics 3 … flow tables 2 SDN controller receives OpenFlow message, updates link status info Link-state info host info … switch info 2 3 Dijkstra’s routing algorithm OpenFlow … SNMP application has previously registered to be called when ever link status changes. It is called. 1 4 Dijkstra’s routing algorithm s2 access network graph info, link s1 s4 state info in controller, computes s3 new routes Network Layer: 5-83 SDN: control/data plane interaction example Dijkstra’s link-state routing 4 5 network graph RESTful API … intent 5 link state routing app interacts 3 … with flow-table-computation statistics flow tables component in SDN controller, Link-state info host info … switch info which computes new flow tables 2 needed OpenFlow … SNMP 6 controller uses OpenFlow to 6 install new tables in switches 1 that need updating s2 s1 s4 s3 Network Layer: 5-84 OpenDaylight (ODL) controller Traffic Engineering Firewalling Load Balancing … Network Orchestrations and Applications Northbound API REST/RESTCONF/NETCONF APIs Enhanced Basic Network Functions Services Topology Switch Stats AAA … processing mgr. mgr. Forwarding Host … rules mgr. Tracker Service Abstraction Layer: config. and operational data messaging Service Abstraction § interconnects internal, store Layer (SAL) external applications … Southbound API and services OpenFlow NETCONF SNMP OVSDB Network Layer: 5-85 SDN: selected challenges § hardening the control plane: dependable, reliable, performance- scalable, secure distributed system robustness to failures: leverage strong theory of reliable distributed system for control plane dependability, security: “baked in” from day one? § networks, protocols meeting mission-specific requirements e.g., real-time, ultra-reliable, ultra-secure § Internet-scaling: beyond a single AS § SDN critical in 5G cellular networks Network Layer: 5-87 SDN and the future of traditional network protocols § SDN-computed versus router-computer forwarding tables: just one example of logically-centralized-computed versus protocol computed § one could imagine SDN-computed congestion control: controller sets sender rates based on router-reported (to controller) congestion levels How will implementation of network functionality (SDN versus protocols) evolve? Network Layer: 5-88  Network layer: “control plane” roadmap § introduction § routing protocols § intra-ISP routing: OSPF § routing among ISPs: BGP § SDN control plane § Internet Control Message § network management, Protocol configuration SNMP NETCONF/YANG Network Layer: 5-89 ICMP: internet control message protocol § used by hosts and routers to Type Code description communicate network-level 0 0 echo reply (ping) information 3 0 dest. network unreachable 3 1 dest host unreachable error reporting: unreachable host, 3 2 dest protocol unreachable network, port, protocol 3 3 dest port unreachable echo request/reply (used by ping) 3 6 dest network unknown 3 7 dest host unknown § network-layer “above” IP: 4 0 source quench (congestion ICMP messages carried in IP control - not used) 8 0 echo request (ping) datagrams 9 0 route advertisement § ICMP message: type, code plus 10 11 0 0 router discovery TTL expired first 8 bytes of IP datagram causing 12 0 bad IP header error Network Layer: 4-90 Traceroute and ICMP 3 probes 3 probes 3 probes § source sends sets of UDP segments to stopping criteria: destination § UDP segment eventually 1st set has TTL =1, 2nd set has TTL=2, etc. arrives at destination host § datagram in nth set arrives to nth router: § destination returns ICMP router discards datagram and sends source “port unreachable” ICMP message (type 11, code 0) message (type 3, code 3) ICMP message possibly includes name of § source stops router & IP address § when ICMP message arrives at source: record RTTs Network Layer: 4-91