[SOLVED] CS algorithm flex distributed system database 12

12
2/18/21
Chapter 5
Network Layer:
Control Plane
A note on the use of these PowerPoint slides:
Were making these slides freely available to all (faculty, students, readers). Theyre 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, wed like people to use our book!)
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.
For a revision history, see the slide note for this page. Thanks and enjoy! JFK/KWR
All material copyright 1996-2020
J.F Kurose and K.W. Ross, All Rights Reserved
Computer Networking: A
Top-Down Approach
8th edition
Jim Kurose, Keith Ross Pearson, 2020
Network layer control plane: our goals
understand principles behind network control plane:
traditional routing algorithms SDN controllers
network management,
configuration
instantiation, implementation in the Internet:
OSPF, BGP
OpenFlow, ODL and ONOS
controllers
Internet Control Message
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 SDN control plane
Internet Control Message Protocol
network management, configuration
SNMP
NETCONF/YANG
Network Layer: 5-3
Network-layer functions
forwarding: move packets from routers input to appropriate router output
routing: determine route taken by packets from source to destination
data plane
control plane
Two approaches to structuring network control plane:
per-router control (traditional)
logically centralized control (software defined networking)
Network Layer: 5-4
34
1

5
6
Per-router control plane
Individual routing algorithm components in each and every router interact in the control plane
309
Software-Defined Networking (SDN) control plane
Remote controller computes, installs forwarding tables in routers
Control plane Data plane
Routing Algorithm Routing algorithm
Local forwarding table header output 0100 3
0110 2
0111 2
1001 1
control plane
data plane
control plane
data plane
values in arriving packet header
Values in arriving
values in arriving packet header
packets header
1101
0111
1 2
3
1
Figure 4.2 Routing algorithms determine values in forward tables
tables. In this example, a routing algorithm runs in each and every router and both forwarding and routing functions are contained within a router. As well see in Sec- tions 5.3 and 5.4, the routing algorithm function in one router communicates with the routing algorithm function in other routers to compute the values for its forward- ing table. How is this communication performed? By exchanging routing messages containing routing information according to a routing protocol! Well cover routing algorithms and protocols in Sections 5.2 through 5.4.
The distinct and different purposes of the forwarding and routing functions can be further illustrated by considering the hypothetical (and unrealistic, but technically feasible) case of a network in which all forwarding tables are configured directly by human network operators physically present at the routers. In this case, no routing protocols would be required! Of course, the human operators would need to interact with each other to ensure that the forwarding tables were configured in such a way that packets reached their intended destinations. Its also likely that human configu- ration would be more error-prone and much slower to respond to changes in the net- work topology than a routing protocol. Were thus fortunate that all networks have both a forwarding and a routing function!
M04_KURO4140_07_SE_C04.indd 309
Network Layer: 5-5
Network Layer: 5-6
introduction routing protocols
link state
distance vector
intra-ISP routing: OSPF
routing among ISPs: BGP
SDN control plane
Internet Control Message Protocol
Routing protocol goal: determine good paths (equivalently, routes), from sending hosts to receiving host, through network of routers
national or global ISP
4.1

OVERVIEW OF NETWORK LAYER
Remote Controller
CA CA CA CA
3
2
3
2
0111
1
Network layer: control plane roadmap
Routing protocols
mobile network
network management, configuration
SNMP
NETCONF/YANG
Network Layer: 5-7
78
network
link physical
enterprise network
network
link physical
network
link physical
network
link datacenter
11/02/16
3:14 PM
path: sequence of routers packets traverse from given initial source host to final destination host
good: least cost, fastest, least congested
routing: a top-10 networking challenge!
application transport network link physical
network
link physical
CA
physical
network
application transport network link physical
Network Layer: 5-8
2/18/21
2

9 10
2/18/21
Graph abstraction: link costs
u 1
5
2 v 3 w
1 y
5
2
z
ca,b: cost of direct link connecting a and b e.g., cw,z = 5, cu,z =
cost defined by network operator: could always be 1, or inversely related to bandwidth, or inversely related to congestion
2 x
3
1
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-9
Routing algorithm classification
How fast do routes change?
global: all routers have complete topology, link cost info
link state algorithms
static: routes change slowly over time
dynamic: routes change more quickly
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-10
Network layer: control plane roadmap
introduction routing protocols
link state
distance vector intra-ISP routing: OSPF routing among ISPs: BGP SDN control plane
Internet Control Message Protocol
network management, configuration
SNMP
NETCONF/YANG
Network Layer: 5-11
Dijkstras link-state routing algorithm
centralized: network 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 forwarding table for that node
iterative: after k iterations, know least cost path to k destinations
notation
cx,y: direct link cost from nodextoy; =ifnotdirect neighbors
D(v): current estimate of cost of least-cost-path from source to destination v
p(v): predecessor node along path from source to v
N: set of nodes whose least- cost-path definitively known
Network Layer: 5-12
11 12
3

13 14
2/18/21
Dijkstras link-state routing algorithm
1 Initialization:
2 3 4 5 6 7
N = {u}
for all nodes v
if v adjacent to u then D(v) = cu,v
else D(v) =
/* compute least cost path from u to all other nodes */
/* u initially knows direct-path-cost only to direct neighbors */
/* but may not be minimum cost!
*/
8 Loop
9 find w not in N such that D(w) is a minimum
10 addwtoN
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 /* new least-path-cost to v is either old least-cost-path to v or known
14 least-cost-path to w plus direct-cost from w to v */
15 until all nodes in N
Network Layer: 5-13
Dijkstras algorithm: an example
Step 0 1 2 3 4 5
u 1
N
u ux uxy uxyv uxyvw uxyvwz
5 v3w
vwxyz
D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 2,u 5,u 1,u
2,u 4,x
2,x 4,y 4,y 4,y
2,u
5
2
3,y 3,y
2
Initialization (step 0): For all a: if a adjacent to then D(a) = cu,a
find a not in N such that D(a) is a minimum
add a to N
update D(b) for all b adjacent to a and not in N :
2 xy
1
z
D(b) = min ( D(b), D(a) + ca,b )
3
1
Network Layer: 5-14
D(
Dijkstras algorithm: an example
5
v3w 2
u 1
resulting least-cost-path tree from u:
5 1z
2 1
resulting forwarding table in u:
route from u to v directly
route from u to all other destinations via x
Network Layer: 5-15
2 xy
3
vw u
destination
v x y w x
outgoing link
(u,v) (u,x) (u,x) (u,x) (u,x)
z xy
Dijkstras algorithm: another example
Step N
vwxyz
D(v), D(w), D(x), D(y), D(z), p(v) p(w) p(x) p(y) p(z)
x
5 4 7 8
9
0 u 7,u 3,u 5,u
1 uw 6,w 5,u 11,w D(w),p(w)
2uwx6,w 11,w14,x 3wyz
5,u
u
2
Network Layer: 5-16
3 4u,xwxv 10,v 14,x 3,y
3
v
4
4 uwxvy 12,y 3,y
7
5 uwxvyz
notes:
construct least-cost-path tree by tracing predecessor nodes ties can exist (can be broken arbitrarily)
15 16
4
w),p(w) 5,u 4,x 3,y 3,y

17 18
2/18/21
Dijkstras 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 routers message crosses O(n) links: overall message complexity: O(n2)
Network Layer: 5-17
Dijkstras 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 (<1), 1 link costs are directional, and volume-dependent1 a 1+e d 0 0 b2+e a 0 d 1+e1 b0 a 2+e d 0 0 b2+e a 0 d 1+e1 b 1 0 c 0 1 eeee1 0 c e 1initially find new routing….1 1 c 1+e 11 0 c 0 1given these costs, resulting in new costsgiven these costs, find new routing…. resulting in new costsgiven these costs, find new routing…. resulting in new costsNetwork Layer: 5-18 Network layer: control plane roadmap introduction routing protocolslink statedistance vector intra-ISP routing: OSPF routing among ISPs: BGP SDN control planeInternet Control Message Protocolnetwork management, configuration SNMP NETCONF/YANGNetwork Layer: 5-19 Distance vector algorithmBased on Bellman-Ford (BF) equation (dynamic programming): Bellman-Ford equationLet Dx(y): cost of least-cost path from x to y. Then:Dx(y) = minv { cx,v + Dv(y) }vs estimated least-cost-path cost to y min taken over all neighbors v of x direct cost of link from x to vNetwork Layer: 5-2019 205 2/18/21 Bellman-Ford ExampleSuppose that us neighboring nodes, x,v,w, know that for destination z:Dv(z) = 5Dw(z) = 35 2v3w5Bellman-Ford equation says:Du(z) = min { cu,v + Dv(z), cu,x + Dx(z),cu,w + Dw(z) } = min {2 + 5,1 + 3, 5+3} =4node achieving minimum (x) isu 11y 2z 2 x3 1 Dx(z) = 3 next hop on estimated least- cost path to destination (z)Network Layer: 5-21 Distance vector algorithmkey 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-2221 22 Distance vector algorithm:each node:wait for (change in local link cost or msg from neighbor)recompute DV estimates using DV received from neighborif DV to any destination has changed, notify neighborsiterative, asynchronous: each local iteration caused by: local link cost changeDV update message from neighbordistributed, self-stopping: each node notifies neighbors only when its DV changes neighbors then notify their neighbors only if necessary no notification received, no actions taken!Network Layer: 5-23 Distance vector: example DVina:Da(a)=0 Da(b) = 8 Da(c) = Da(d) = 1 Da(e) = Da(f) = Da(g) = Da(h) = Da(i) = b81e1cft=0 All nodes have distance estimates to nearest neighbors (only) All nodes send their localdistance vector to their neighborsa11A few asymmetries: missing link larger costNetwork Layer: 5-24d11ig1111h 23 246Distance vector example: iterationb81et=1All nodes: receive distancevectors fromneighbors compute their new local distance vector send their newlocal distance vector to neighborsa1d1g1cf 11h11i 11Network Layer: 5-2525 26 Distance vector example: iteration ab81et=1All nodes: receive distance vectors from neighbors compute their new local distance vector send their newlocal distance vector to neighbors1d1g1cf 11h11i 11Network Layer: 5-27 Distance vector example: iterationb81et=2All nodes: receive distancevectors fromneighbors compute their new local distance vector send their newlocal distance vector to neighborsa1d1g1cf 11h11i 11Network Layer: 5-2827 282/18/21 Distance vector example: iterationcomcpute comapute 8 combpute 11g h comipute compute 1 compute 1 t=1All nodes: receive distance vectors from neighbors compute their new local distance vector send their newlocal distance vector to neighborsd1comfpute 111computee1 compute 1Network Layer: 5-267 2/18/21 Distance vector example: iterationt=2All nodes: receive distance vectors from neighbors compute their new local distance vector send their newlocal distance vector to neighborsc o ma p u t e 2 c o mb p u t e 1 11comepute 1 111c o mc p u t ecomputec o mg p u t e 8 c o mh p u t e 1 c o mi p u t e comdpute 1f Network Layer: 5-29 Distance vector example: iteration ab81et=2All nodes: receive distance vectors from neighbors compute their new local distance vector send their newlocal distance vector to neighbors1d1g1cf 11h11i 11Network Layer: 5-3029 30 Distance vector example: iteration…. and so onLets next take a look at the iterative computations at nodesNetwork Layer: 5-31DVinc:Dc(a) = Dc(b) = 1 Dc(c) = 0 Dc(d) = Dc(e) = Dc(f) = Dc(g) = Dc(h) = Dc(i) = Distance vector example: computation DDb(b) = 0 Db(c) = 1 Db(d) = Db(e) = 1b(a)=8Db(f) = Db(g) = Db(h) = Db(i) = DVinb:DVina: Da(a)=0 Da(b) = 8 Da(c) = Da(d) = 1 Da(e) = Da(f) = Da(g) = Da(h) = Da(i) = b81et=1 b receives DVs from a, c, ea1d1g1cf DVine:De(a) = De(b) = 1 De(c) = De(d) = 1 De(e) = 0 De(f) = 1 De(g) = De(h) = 1 De(i) = 11h11i 11Network Layer: 5-3231 328DVinc:Dc(a) = Dc(b) = 1 Dc(c) = 0 Dc(d) = Dc(e) = Dc(f) = Dc(g) = Dc(h) = Dc(i) = Distance vector example: computation Db(a) = 8 Db(c) = 1 Db(d) = Db(e) = 1Db(f) = Db(g) = Db(h) = Db(i) = DVinb: bc 8 compute 1 1ef t=1 b receives DVs from a, c, e, computes:ab 1DVine:De(a) = De(b) = 1 De(c) = De(d) = 1 De(e) = 0 De(f) = 1 De(g) = De(h) = 1 De(i) = DVina: Da(a)=0 Da(b) = 8 Da(c) = Da(d) = 1 Da(e) = Da(f) = Da(g) = Da(h) = Da(i) = Db(a) = min{cb,a+Da(a), cb,c +Dc(a), cb,e+De(a)} = min{18,,} = 8Db(c) = min{cb,a+Da(c), cb,c +Dc(c), c b,e +De(c)} = min{,1,} = 1Db(d) = min{cb,a+Da(d), cb,c +Dc(d), c b,e +De(d)} = min{9,2,} = 2Db(e) = min{cb,a+Da(e), cb,c +Dc(e), c b,e +De(e)} = min{,,1} = 1de 11 Db(f) = min{cb,a+Da(f), cb,c +Dc(f), c b,e +De(f)} = min{,,2} = 2 Db(g) = min{cb,a+Da(g), cb,c +Dc(g), c b,e+De(g)} = min{, , } = 11ghDb(a) = 8 Db(c) = 1Db(f) =2 Db(g) = DVinb: 1iDb(h) = min{cb,a+Da(h), cb,c +Dc(h), c b,e+De(h)} = min1{, , 2} = 2 Db(i) = min{cb,a+Da(i), cb,c +Dc(i), c b,e+De(i)} = min{, , } = Db(d) = 2 Db(e) = 1Db(h) = 2 Db(i) = Network Layer: 5-33 DVinc:Dc(a) = Dc(b) = 1 Dc(c) = 0 Dc(d) = Dc(e) = Dc(f) = Dc(g) = Dc(h) = Dc(i) = Distance vector example: computation Db(a) = 8 Db(c) = 1 Db(d) = Db(e) = 1Db(f) = Db(g) = Db(h) = Db(i) = DVinb: DVina:Da(a)=0 Da(b) = 8 Da(c) = Da(d) = 1 Da(e) = Da(f) = Da(g) = Da(h) = Da(i) = b81e t=1 c receives DVs from ba1d1g1cfDVine:De(a) = De(b) = 1 De(c) = De(d) = 1 De(e) = 0 De(f) = 1 De(g) = De(h) = 1 De(i) = 11h11i 11Network Layer: 5-3433 34DVinc:Dc(a) = Dc(b) = 1 Dc(c) = 0 Dc(d) = Dc(e) = Dc(f) = Dc(g) = Dc(h) = Dc(i) = Distance vector example: computation Db(a) = 8 Db(c) = 1 Db(d) = Db(e) = 1Db(f) = Db(g) = Db(h) = Db(i) = DVinb:b81 t=1 c receives DVs from b computes:a1pute* Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/Network Layer: 5-351comcDc(a) = min{cc,b+dDb(a}} = 1 + 8 = 9 e Dc(b) = min{cc,b+Db(b)} = 1 + 0 = 1Dc(d) = min{cc,b+Db(d)} = 1+ = Dc(e) = min{cc,b+Db(e)} = 1 + 1 = 2Dc(f) = min{cc,b+Db(f)} = 1+ = Dc(g) = min{cc,b+Db(g)} = 1+ = Dc(h) = min{cbc,bg+Db(h)} = 1+ = h Dc(i) = min{cc,b+Db(i)} = 1+ = DVinc: f Dc(a) = 9 Dc(b) = 1 Dc(c) = 0 Dc(d) = 2 Dc(e) = Dc(f) = Dc(g) = i Dc(h) = Dc(i) = Distance vector example: computation Db(a) = 8 Db(c) = 1 Db(d) = Db(e) = 1Db(f) = Db(g) = Db(h) = Db(i) = DVinb: DVine:De(a) = De(b) = 1 De(c) = De(d) = 1 De(e) = 0 De(f) = 1 De(g) = De(h) = 1 De(i) = DVinf:Dc(a) = Dc(b) = Dc(c) = Dc(d) = Dc(e) = 1 Dc(f) = 0 Dc(g) = Dc(h) = Dc(i) = 1DVind:Dc(a) = 1 Dc(b) = Dc(c) = Dc(d) = 0 Dc(e) = 1 Dc(f) = Dc(g) = 1 Dc(h) = Dc(i) = t=1 e receives DVs from b, d, f, ha1d1m1 18bcoe 1ht=1?1c Q: what is new DV computed in e at1 putefi DVinh:Dc(a) = Dc(b) = Dc(c) = Dc(d) = Dc(e) = 1 Dc(f) = Dc(g) = 1 Dc(h) = 0 Dc(i) = 1g111 Network Layer: 5-3635 362/18/219 37 382/18/21 Distance vector: state information diffusionIterative communication, computation steps diffuses information through network: t=0 cs state at t=0 is at c onlycs state at t=0 has propagated to b, andt=1 may influence distance vector computationsup to 1 hop away, i.e., at bcs state at t=0 may now influence distancet=2 vector computations up to 2 hops away, i.e.,at b and now at a, e as wellcs state at t=0 may influence distance vectort=3 computations up to 3 hops away, i.e., at b,a,eand now at c,f,h as wellcs state at t=0 may influence distance vectort=4 computations up to 4 hops away, i.e., at b,a,e,c, f, h and now at g,i as well11a1c t=1 b81e dt=2t=3t=4 11hf11ig1 1 Distance vector: link cost changeslink cost changes:node detects local link cost change updates routing info, recalculates local DV if DV changes, notify neighbors1y 41x 50 z good news travels fastt0 : y detects link-cost change, updates its DV, informs its neighbors.t1 : z receives update from y, updates its table, computes new least cost to x , sends its neighbors its DV.t2 : y receives zs update, updates its distance table. ys least costs do not change, so y does not send a message to z.Network Layer: 5-38 Distance vector: link cost changeslink cost changes:60 y 41x 50 z yseesdirectlinktoxhasnewcost60,butzhassaidithasapathatcostof5.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. node detects local link cost changebad news travels slow count-to-infinity problem: 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-39 Comparison of LS and DV algorithmsmessage complexityLS: n routers, O(n2) messages sentDV: exchange between neighbors; convergence time variesspeed of convergenceLS: O(n2) algorithm, O(n2) messages may have oscillationsDV: convergence time varies may have routing loops count-to-infinity problemrobustness: what happens if router malfunctions, or is compromised?LS: router can advertise incorrect link cost each router computes only its owntableDV: DV router can advertise incorrect path cost (I have a really low cost path to everywhere): black-holing each routers table used by others: error propagate thru networkNetwork Layer: 5-4039 4010 2/18/21 Network layer: control plane roadmap introductionrouting protocols intra-ISP routing: OSPF routing among ISPs: BGP SDN control planeInternet Control Message Protocolnetwork management, configuration SNMP NETCONF/YANGNetwork Layer: 5-41 Making routing scalableour routing study thus far – idealized all routers identical network flat… not true in practicescale: billions of destinations: cant store all destinations in routing tables! routing table exchange would swamp links!administrative autonomy: Internet: a network of networks each network admin may want tocontrol routing in its own networkNetwork Layer: 5-4241 42 Internet approach to scalable routingaggregate routers into regions known as autonomous systems (AS) (a.k.a. domains)intra-AS (aka intra-domain):routing among within same AS (network) all routers in AS must run same intra-domain protocol routers in different AS can run differentintra-domain routing protocols gateway router: at edge of its own AS,has link(s) to router(s) in other ASesinter-AS (aka inter-domain):routing among ASes gateways perform inter-domain routing (as well as intra-domainrouting)Network Layer: 5-43 Interconnected ASesinter-AS routing1c AS3 1a intra-ASrouting 1b 1dforwarding table configured by intra- and inter-AS routing algorithms intra-AS routing determine entries for destinations within AS inter-AS & intra-AS determine entries for external destinationsIntra-AS Inter-AS Routing Routing forwarding tableintra-AS 3c routing3aint2rac-AS 2arouting3b 2b AS1AS2Network Layer: 5-4443 4411 2/18/21 Inter-AS routing: a role in intradomain forwarding suppose router in AS1 receives datagram destined outside of AS1: router should forward packet to gateway router in AS1, but which one?3b 1cAS3 1a 1d 1bAS1 inter-domain routing must:1. learn which destinations reachable through AS2, which through AS32. propagate this reachability info to all routers in AS1 3c 3a2a2cother networks other networks2bAS2 AS1 Network Layer: 5-45 Inter-AS routing: routing within an ASmost common intra-AS routing protocols: RIP: Routing Information Protocol [RFC 1723] classic DV: DVs exchanged every 30 secs no longer widely usedEIGRP: 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 OSPFNetwork Layer: 5-4645 46 OSPF (Open Shortest Path First) routingopen: publicly availableclassic link-state each router floods OSPF link-state advertisements (directly over IPrather than using TCP/UDP) to all other routers in entire AS multiple link costs metrics possible: bandwidth, delay each router has full topology, uses Dijkstras algorithm to compute forwarding tablesecurity: all OSPF messages authenticated (to prevent malicious intrusion)Network Layer: 5-47 Hierarchical OSPFtwo-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 destinationsarea border routers:summarize distances to destinations in own area, advertise in backbonelocal routers: flood LS in area only compute routing withinarea forward packets to outside area 1via area border routerbackbonearea 2boundary router:connects to other ASesarea 3backbone router:runs OSPF limited to backboneNetwork Layer: 5-48 internal routers47 4812 2/18/21 Network layer: control plane roadmap introductionrouting protocols intra-ISP routing: OSPF routing among ISPs: BGP SDN control planeInternet Control Message Protocolnetwork management, configuration SNMP NETCONF/YANGNetwork Layer: 5-49 Internet inter-AS routing: BGP BGP (Border Gateway Protocol): the de facto inter-domain routing protocol gluethatholdstheInternettogether allows subnet to advertise its existence, and the destinations it canreach, 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 informationand policyNetwork Layer: 5-5049 50 eBGP, iBGP connections2b1b 2a 2c 3b1a 1c 2d 3a 3c AS2 1d 3dAS1eBGP connectivity AS 3 logical iBGP connectivity1cgateway routers run both eBGP and iBGP protocolsNetwork Layer: 5-51 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 XAS1 1b1a 1c1d 3b3a 3cAS2 2b 3dAS3 2a 2c 2dBGP advertisement:AS3, XXNetwork Layer: 5-52 51 5213 2/18/21 Path attributes and BGP routesBGP 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 ASpolicy-based routing: gateway receiving route advertisement uses import policy toaccept/decline path (e.g., never route through AS Y). AS policy also determines whether to advertise path to other other neighboring ASesNetwork Layer: 5-53 BGP path advertisementAS3 AS1 1b1a 1c1d3b3a 3cAS2 2b 3d X AS2,AS3,X2a 2c 2dAS3, X 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 1cNetwork Layer: 5-5453 54 BGP path advertisement (more) AS3 AS1 1b AS3,X 1a AS3,X 1cAS3,X3b3a 3cAS2 2b 3d X AS3,X1d2a 2c 2dAS3, X AS2,AS3,Xgateway 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 pathwithin AS1 via iBGPNetwork Layer: 5-55 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 ACKsOPEN request NOTIFICATION: reports errors in previous msg; also used to close connectionNetwork Layer: 5-5655 5614 BGP path advertisementAS1 1b AS3,X AS3,X 1AS3 3b3a 3c1aAS3,X1c AS2 3d X local link interfaces at 1a, 1d2AS3,XAS2,AS3,X2b2d2 1d 12a2cAS3, X dest…1cX…interface…11… recall: 1a, 1b, 1d learn via iBGP from 1c: path to X goes through 1c at 1d: OSPF intra-domain routing: to get to 1c, use interface 1 at 1d: to get to X, use interface 1Network Layer: 5-57 BGP path advertisementAS1 1b 1AS3 3b3a 3c 1a2 1c AS2 2b 3d X 1d2a 2c 2drecall: 1a, 1b, 1d learn via iBGP from 1c: path to X goes through 1c at 1d: OSPF intra-domain routing: to get to 1c, use interface 1at 1d: to get to X, use interface 1at 1a: OSPF intra-domain routing: to get to 1c, use interface 2dest…1cX…interface…22… at 1a: to get to X, use interface 2Network Layer: 5-5857 582/18/21 Why different Intra-, Inter-AS routing ?policy:inter-AS: admin wants control over how its traffic routed, who routes through its networkintra-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 performanceNetwork Layer: 5-59 Hot potato routingAS3 AS1 1b1a 1cAS2 2b 112 2a 201 263 2c3b3a 3c3d X 1dAS1,AS3,XAS3,X 2dOSPF link weights 2d learns (via iBGP) it can route to X via 2a or 2c hot potato routing: choose local gateway that has least intra-domain cost (e.g., 2d chooses 2a, even though more AS hops to X): dont worry about inter-domain cost!Network Layer: 5-6059 6015 61 622/18/21 BGP: achieving policy via advertisementsB xCyISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs a typical real world policy) A advertises path Aw to B and to C B chooses not to advertise BAw to C! B gets no revenue for routing CBAw, since none of C, A, w are Bs customersA,wwprovider networklegend:customer A A,wnetwork: C does not learn about CBAw path C will route CAw (not using B) to get to wNetwork Layer: 5-61 BGP: achieving policy via advertisements (more)B xprovider networklegend:customerISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs a typical real world policy)wACy A,B,C are provider networks x,w,y are customer (of provider networks) x is dual-homed: attached to two networks policy to enforce: x does not want to route from B to C via x.. so x will not advertise to B a route to Cnetwork:Network Layer: 5-62 BGP route selection router may learn about more than one route to destination AS, selects route based on:1. localpreferencevalueattribute:policydecision 2. shortestAS-PATH3. closestNEXT-HOProuter:hotpotatorouting4. additionalcriteriaNetwork Layer: 5-63 Network layer: control plane roadmap introductionrouting protocols intra-ISP routing: OSPF routing among ISPs: BGP SDN control planeInternet Control Message Protocolnetwork management, configuration SNMP NETCONF/YANGNetwork Layer: 5-6463 64162/18/21 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 planeNetwork Layer: 5-65 Per-router control planeIndividual routing algorithm components in each and every router interact in the control plane to computer forwarding tables 4.1312OVERVIEW OF NETWORK LAYER309Routing Algorithm Routing algorithmLocal forwarding tableFigure 4.2 Routing algorithms determine values in forward tablestables. In this example, a routing algorithm runs in each and every router and bothcontrol planedata plane Control plane Data planeheaderoutput0100 0110 0111 1001 3 2 2 1 rriving ader110101111 23Values in avalues in arriving packet headerpackets heNetwork Layer: 4-666566forwarding and routing functions are contained within a router. As well see in Sec- tions 5.3 and 5.4, the routing algorithm function in one router communicates with the routing algorithm function in other routers to compute the values for its forward- ing table. How is this communication performed? By exchanging routing messages containing routing information according to a routing protocol! Well cover routing algorithms and protocols in Sections 5.2 through 5.4.The distinct and different purposes of the forwarding and routing functions can be further illustrated by considering the hypothetical (and unrealistic, but technically feasible) case of a network in which all forwarding tables are configured directly by human network operators physically present at the routers. In this case, no routing protocols would be required! Of course, the human operators would need to interact with each other to ensure that the forwarding tables were configured in such a way that packets reached their intended destinations. Its also likely that human configu- ration would be more error-prone and much slower to respond to changes in the net- work topology than a routing protocol. Were thus fortunate that all networks have both a forwarding and a routing function!M04_KURO4140_07_SE_C04.indd 309 11/02/16 3:14 PMSoftware defined networking (SDN)Why a logically centralized control plane?Software-Defined Networking (SDN) control planeRemote controller computes, installs forwarding tables in routers Remote Controller control planedata plane easier network management: avoid router misconfigurations,greater flexibility of traffic flowstable-based forwarding (recall OpenFlow API) allows programming routers centralized programming easier: compute tables centrally and distribute distributed programming more difficult: compute tables as result ofdistributed algorithm (protocol) implemented in each-and-every router open (non-proprietary) implementation of control plane values in arriving packet headerCACACA CACA676801111foster innovation: let 1000 flowers bloom23Network Layer: 4-67Network Layer: 5-6817SDN analogy: mainframe to PC revolutionSpecialized ApplicationsSpecialized Operating SystemSpecialized HardwareVertically integrated Closed, proprietary Slow innovation Small industry* Slide courtesy: N. McKeownApAp pAp pAp pAp pAp pAp pAp pAp pAp pOpen Interfaceor or LinuxOpen InterfaceApp p WindowsMAC OSMicroprocessorHorizontal Open interfaces Rapid innovation Huge industry Network Layer: 5-69 Traffic engineering: difficult with traditional routing 5 2w5 v3 23u1z21x1y 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-7069 70 Traffic engineering: difficult with traditional routing 5 2w5 v3 23u1z21x1y Q: what if network operator wants to split u-to-z traffic along uvwz and uxyz (load balancing)?A: cant do it (or need a new routing algorithm)Network Layer: 5-71 Traffic engineering: difficult with traditional routing 5 2w5 v3 23u1z21x1yQ: what if w wants to route blue and red traffic differently from w to z? A: cant 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 desiredNetwork Layer: 5-7271 722/18/2118 73 74Software defined networking (SDN)network-control apps: brains of control: implement control functions using lower-level services, API provided by SDN controller unbundled: can be provided by 3rd party: distinct from routing vendor, or SDN controllernetwork-control applicationsroutingaccess control…load balance2/18/21 Software defined networking (SDN)4. programmable controlapplicationsroutingaccess control… load balanceCA CA CA3. control plane functions external to data-plane switchescontrol planedata plane2. control, data plane separationNetwork Layer: 5-73Remote ControllerCA CA 1: generalized flow-base forwarding (e.g., OpenFlow)dSoftware defined networking (SDN)Data-plane switches: fast, simple, commodity switches implementing generalized data-plane forwarding (Section 4.4) in hardware flow (forwarding) table computed, installed under controller supervision API for table-based switch control (e.g., OpenFlow) defines what is controllable, what is not protocol for communicating with controller (e.g., OpenFlow)network-control applicationsrouting…load balanceaccess controlcontrol northbound API planeSDN Controller (network operating system)southbound APIdata planeSDN-controlled switchesNetwork Layer: 5-74 Software defined networking (SDN)SDN controller (network OS): maintain network state information interacts with network control applications above via northbound API interacts with network switches below via southbound API implemented as distributed system for performance, scalability, fault- tolerance, robustnessnetwork-control applicationsrouting…access controlload balance northbound APIsouthbound APIcontrol plane SDN Controller (network operating system)data planeSDN-controlled switchesNetwork Layer: 5-75 SDN Controller (network operating system)southbound APInorthbound APIcontrol planedata plane75 76SDN-controlled switchesNetwork Layer: 5-7619Components of SDN controller routingaccess loadcontrolbalanceinterface layer to network control apps: abstractions APInetwork-wide state management : state of networks links, switches, services: a distributed databasecommunication: communicate between SDN controller and controlled switchesSDN controllerNetwork Layer: 5-77Interface, abstractions for network control apps network RESTful … graph APIintent statistics … flow tables Network-wide distributed, robust state managementLink-stateinfo hostinfo … switchinfoOpenFlow … SNMP Communication to/from controlled devicesOpenFlow protocol operates between controller, switch TCP used to exchange messages optionalencryption three classes of OpenFlow messages: controller-to-switch asynchronous(switchtocontroller) symmetric(misc.) distinct from OpenFlow API API used to specify generalized forwarding actionsOpenFlow ControllerNetwork Layer: 5-7877 78 OpenFlow: controller-to-switch messagesKey controller-to-switch messages features: controller queries switch 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 portOpenFlow ControllerNetwork Layer: 5-79 OpenFlow: switch-to-controller messagesKey switch-to-controller messages packet-in: transfer packet (and its control) to controller. See packet-out message from controller flow-removed: flow table entry deleted at switch port status: inform controller of a change on a port.OpenFlow ControllerFortunately, network operators dont program switches by creating/sending OpenFlow messages directly. Instead use higher-level abstraction at controllerNetwork Layer: 5-8079 802/18/2120SDN: control/data plane interaction example Dijkstras link-state routing1 2… switch info 3 SNMPS1, experiencing link failure uses OpenFlow port status message to notify controllerSDN controller receives OpenFlow message, updates link status infoDijkstras routing algorithm application has previously registered to be called when ever link status changes. It is called.Dijkstras routing algorithm access network graph info, link state info in controller, computes new routesNetwork Layer: 5-814network graph3statistics Link-state infoOpenFlow1s2 s1s3…RESTful APIintent flow tables… 2host info… 4s4 SDN: control/data plane interaction example Dijkstras link-state routing45RESTful … intent 5network graph3statistics Link-state infoOpenFlow1s2 s1link state routing app interacts with flow-table-computation component in SDN controller, which computes new flow tables needed API…flow tables … switch infoSNMP2host info… s4 s36 controller uses OpenFlow to install new tables in switches that need updatingNetwork Layer: 5-8281 822/18/21 OpenDaylight (ODL) controllerFirewalling Load Balancing … REST/RESTCONF/NETCONF APIs Traffic EngineeringNetwork Orchestrations and Applications Northbound APIEnhanced ServicesAAA … …OpenFlow NETCONFBasic Network FunctionsTopology Switch Stats processing mgr. mgr.Forwarding Host rules mgr. Trackermessaging SNMP OVSDB …Service Abstraction Layer (SAL)Southbound APIService Abstraction Layer: interconnects internal, external applicationsconfig. and operational data store and services Network Layer: 5-83 ONOS controller Traffic EngineeringRESThosts devicesFirewalling Load Balancing …Network ApplicationsNorthbound APISouthbound APIAPIIntentflow rules statisticsnorthbound abstractions, protocolstopologyONOS distributed core control apps separate from controllerintent framework: high- level specification of service: what rather than howconsiderable emphasis on distributed core: service reliability, replication performance scalingNetwork Layer: 5-84 paths links device link host flow packet southbound abstractions,OpenFlow Netconf OVSDB protocols83 84216 85 862/18/21 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 networksNetwork Layer: 5-85 SDN and the future of traditional network protocolsSDN-computed versus router-computer forwarding tables: just one example of logically-centralized-computed versus protocolcomputedone could imagine SDN-computed congestion control: controller sets sender rates based on router-reported (tocontroller) congestion levelsHow will implementation of network functionality (SDN versus protocols) evolve?Network Layer: 5-86 Network layer: control plane roadmap introductionrouting protocolsintra-ISP routing: OSPF routing among ISPs: BGP SDN control plane Internet Control MessageProtocolnetwork management, configuration SNMP NETCONF/YANGNetwork Layer: 5-87 ICMP: internet control message protocol used by hosts and routers to communicate network-level information error reporting: unreachable host, network, port, protocol echo request/reply (used by ping) network-layer above IP: ICMP messages carried in IP datagrams ICMP message: type, code plus first 8 bytes of IP datagram causing errorType Code description 0 0 3 0 3 1 3 2 3 3 3 6 3 7 4 0echo reply (ping)dest. network unreachable dest host unreachable dest protocol unreachable dest port unreachabledest network unknown dest host unknownsource quench (congestion control – not used)echo request (ping)route advertisementrouter discoveryNetwork Layer: 4-888 09 010 0110 TTL expired 120 bad IP header87 8822 89909192Traceroute and ICMP3 probes 3 probes 3 probes source sends sets of UDP segments to destination 1st set has TTL =1, 2nd set has TTL=2, etc. datagram in nth set arrives to nth router: router discards datagram and sends source ICMP message (type 11, code 0)Network layer: control plane roadmap source stops when ICMP message arrives at source: record RTTs ICMP message possibly includes name of router & IP address SNMP NETCONF/YANGWhat is network management? autonomous systems (aka network): 1000s of interacting hardware/software components other complex systems requiring monitoring, configuration, control: jet airplane, nuclear power plant, others?”Network management includes the deployment, integration and coordination of the hardware, software, and human elements to monitor, test, poll, configure, analyze, evaluate, and control the network and element resources to meet the real-time, operational performance, and Quality of Service requirements at a reasonable cost.”Components of network managementstopping criteria: UDP segment eventually arrives at destination host destination returns ICMP port unreachable message (type 3, code 3)Network Layer: 4-89 introductionrouting protocols intra-ISP routing: OSPF routing among ISPs: BGP SDN control plane Internet Control MessageProtocolnetwork management, configurationNetwork Layer: 5-91Managing server:application, typically with network managers (humans) in the loopNetworkmanagementmanaging server/controlleragent data managed deviceagent data managed deviceagent data managed deviceManaged device:equipment with manageable, configurable hardware, software componentsData: device state configuration data, operational data, device statisticsNetwork Layer: 5-92protocol: used by managing server to query, configure, manage device; used by devices to inform managing server of data, events.agent datamanaged deviceagent data managed devicedataNetwork Layer: 5-902/18/2123 93 942/18/21 Network operator approaches to managementCLI (Command Line Interface) operator issues (types, scripts) direct toindividual devices (e.g., vis ssh)SNMP/MIB operator queries/sets devices data (MIB) using Simple Network Management Protocol (SNMP)NETCONF/YANG more abstract, network-wide, holistic emphasis on multi-device configurationmanagement. YANG: data modeling language NETCONF: communicate YANG-compatibleactions/data to/from/among remote devices managing server/controlleragent data managed deviceagent data managed deviceagent datamanaged deviceNetwork Layer: 5-93 data agent datamanaged deviceagent data managed device SNMP protocolTwo ways to convey MIB info, commands:managing data server/controlleragent data managed devicerequest/response modemanaging data server/controlleragent data managed devicetrap mode request response trap messageNetwork Layer: 5-94 SNMP protocol: message types Message typeFunctionGetRequestGetNextRequest GetBulkRequestmanager-to-agent: get me data(data instance, next data in list, block of data).SetRequestmanager-to-agent: set MIB valueResponseAgent-to-manager: value, response to RequestTrapAgent-to-manager: inform manager of exceptional event Network Layer: 5-95 SNMP protocol: message formatsPDU type (0-3)GeRequest IDt/set heaError Status (0-5) derError IndexNameVariableValues to geNamet/setValue ….message types 0-3message type 4Trap headerSNMP PDUTrap infoPDU type 4 EnterpriseAgent AddrTrap Type (0-7) Specific code Time stamp Name Value ….Network Layer: 5-9695 9624 2/18/21 SNMP: Management Information Base (MIB)managed devices operational (and some configuration) data agent data gathered into device MIB module 400 MIB modules defined in RFCs; many more vendor-specific MIBs Structure of Management Information (SMI): data definition language example MIB variables for UDP protocol:Network Layer: 5-97 Object ID1.3.6.1.2.1.7.1 1.3.6.1.2.1.7.2 1.3.6.1.2.1.7.3 1.3.6.1.2.1.7.4 1.3.6.1.2.1.7.5NameTypeCommentstotal # datagrams delivered# undeliverable datagrams (no application at port) # undeliverable datagrams (all other reasons)UDPInDatagramsUDPNoPortsUDInErrorsUDPOutDatagrams 32-bit counter total # datagrams sentudpTable SEQUENCE one entry for each port currently in use32-bit counter 32-bit counter 32-bit counter NETCONF overviewgoal: actively manage/configure devices network-wide operates between managing server and managed network devices actions: retrieve, set, modify, activate configurations atomic-commit actions over multiple devices query operational data and statistics subscribe to notifications from devices remote procedure call (RPC) paradigm NETCONF protocol messages encoded in XML exchanged over secure, reliable transport (e.g., TLS) protocolNetwork Layer: 5-9897 98 NETCONF initialization, exchange, closemanaging server/controllerdataSession initiation, capabilities exchange:




Sessionclose:
agent data
Network Layer: 5-99
Selected NETCONF Operations
NETCONF
Operation Description


,
,
Retrieve all or part of a given configuration. A device may have multiple configurations.
Retrieve all or part of both configuration state and operational state data.
Change specified (possibly running) configuration at managed device. Managed device contains or with rollback.
Lock (unlock) configuration datastore at managed device (to lock out NETCONF, SNMP, or CLIs commands from other sources).
Enable event notification subscription from managed device
Network Layer: 5-100
99 100
25

101 102
2/18/21
Sample NETCONF RPC message
note message id change a configuration
change the running configuration
change MTU of Ethernet 0/0 interface to 1500
Network Layer: 5-101
YANG
data modeling language used to specify structure, syntax, semantics of NETCONF network management data
built-in data types, like SMI
XML document describing device, capabilities can be generated from YANG description
can express constraints among data that must be satisfied by a valid NETCONF configuration
ensure NETCONF configurations satisfy correctness, consistency constraints
managing data server/controller
NETCONF RPC message
agent data
YANG generated
Network Layer: 5-102

YANG-generated XML

Network layer: Summary weve learned a lot!
approaches to network control plane
per-router control (traditional)
logically centralized control (software defined networking)
traditional routing algorithms
implementation in Internet: OSPF , BGP
SDN controllers
implementation in practice: ODL, ONOS
Internet Control Message Protocol network management
next stop: link layer!
Network Layer: 5-103
Network layer, control plane: Done!
introduction routing protocols
link state
distance vector intra-ISP routing: OSPF routing among ISPs: BGP SDN control plane
Internet Control Message Protocol
network management, configuration
SNMP
NETCONF/YANG
Network Layer: 5-104
103 104
26

105 106
2/18/21
Additional Chapter 5 slides
Network Layer: 5-105
Distance vector: another example
cost to cost to Dx() x y z x y z
x027 x023
y y 2 0 1 Dx(z) = min{cx,y+ Dy(z), cx,z+ Dz(z)}
x
z z710
= min{2+1 , 7+0} = 3 Dy() x y z Dx(y) = min{cx,y + Dy(y), cx,z+ Dz(y)}
y 7
cost to
2
1
x =min{2+0,7+1}=2 y201
z
z
Network Layer: 5-106
Dz()x y z x
y z710
time
cost to
Distance vector: another example
Dx() x y z x027 y
z
y z710
x y z x023 y201 z710
xyz x027 y201
z710
cost to
cost to
cost to
cost to
Dy()x y z x y201 z
x023 y201 z310
cost to
x 7 z
Network Layer: 5-107
cost to
cost to
xyz x023 y201 z310
cost to y xyz21
Dz()x y z x
xyz xyz x027 x023 y201 y201 z310 z310
cost to
time
107
27
from from from
from from from
from
from from
from from from
from