12
2/18/21
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!)
§ 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 router’s 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
packet’s 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 we’ll 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! We’ll 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. It’s 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. We’re 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
Dijkstra’s 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
Dijkstra’s 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
Dijkstra’s 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(
Dijkstra’s 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
Dijkstra’s 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
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-17
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 (<1), 1 • link costs are directional, and volume-dependent
1 a 1+e d 0 0 b
2+e a 0 d 1+e1 b
0 a 2+e d 0 0 b
2+e a 0 d 1+e1 b
1 0 c 0 1 eeee
1 0 c e 1
initially find new routing....
1 1 c 1+e 1
1 0 c 0 1
given these costs, resulting in new costs
given these costs, find new routing.... resulting in new costs
given these costs, find new routing.... resulting in new costs
Network Layer: 5-18
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-19
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-20
19 20
5
2/18/21
Bellman-Ford Example
Suppose that u’s neighboring nodes, x,v,w, know that for destination z:
Dv(z) = 5
Dw(z) = 3
5 2v3w
5
Bellman-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} =4
node achieving minimum (x) is
u 1
1
y 2
z
2 x
3
1
Dx(z) = 3
next hop on estimated least- cost path to destination (z)
Network Layer: 5-21
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-22
21 22
Distance vector algorithm:
each node:
wait for (change in local link cost or msg from neighbor)
recompute DV estimates using DV received from neighbor
if DV to any destination has changed, notify neighbors
iterative, asynchronous: each local iteration caused by:
§ local link cost change
§DV update message from neighbor
distributed, 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) = ∞
b
8
1
e
1
c
f
t=0
§ All nodes have distance estimates to nearest neighbors (only)
§ All nodes send their local
distance vector to their neighbors
a
1
1
A few asymmetries: § missing link
§ larger cost
Network Layer: 5-24
d
1
1
i
g
11
1
1
h
23 24
6
Distance vector example: iteration
b
8
1
e
t=1
All nodes:
§ receive distance
vectors from
neighbors
§ compute their new local distance vector
§ send their new
local distance vector to neighbors
a
1
d
1
g
1
c
f
1
1
h
1
1
i
11
Network Layer: 5-25
25 26
Distance vector example: iteration a
b
8
1
e
t=1
All nodes:
§ receive distance vectors from neighbors
§ compute their new local distance vector
§ send their new
local distance vector to neighbors
1
d
1
g
1
c
f
1
1
h
1
1
i
11
Network Layer: 5-27
Distance vector example: iteration
b
8
1
e
t=2
All nodes:
§ receive distance
vectors from
neighbors
§ compute their new local distance vector
§ send their new
local distance vector to neighbors
a
1
d
1
g
1
c
f
1
1
h
1
1
i
11
Network Layer: 5-28
27 28
2/18/21
Distance vector example: iteration
comcpute
comapute 8 combpute 11
g h comipute compute 1 compute 1
t=1
All nodes:
§ receive distance vectors from neighbors
§ compute their new local distance vector
§ send their new
local distance vector to neighbors
d
1
comfpute 111
compute
e
1 compute 1
Network Layer: 5-26
7
2/18/21
Distance vector example: iteration
t=2
All nodes:
§ receive distance vectors from neighbors
§ compute their new local distance vector
§ send their new
local distance vector to neighbors
c o ma p u t e 2 c o mb p u t e 1 11
comepute 1 111
c o mc p u t e
compute
c o mg p u t e 8 c o mh p u t e 1 c o mi p u t e
comdpute 1
f
Network Layer: 5-29
Distance vector example: iteration a
b
8
1
e
t=2
All nodes:
§ receive distance vectors from neighbors
§ compute their new local distance vector
§ send their new
local distance vector to neighbors
1
d
1
g
1
c
f
1
1
h
1
1
i
11
Network Layer: 5-30
29 30
Distance vector example: iteration
.... and so on
Let’s next take a look at the iterative computations at nodes
Network Layer: 5-31
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
D
Db(b) = 0 Db(c) = 1 Db(d) = ∞ Db(e) = 1
b(a)
=8
Db(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) = ∞
b
8
1
e
t=1
§ b receives DVs from a, c, e
a
1
d
1
g
1
c
f
DVine:
De(a) = ∞ De(b) = 1 De(c) = ∞ De(d) = 1 De(e) = 0 De(f) = 1 De(g) = ∞ De(h) = 1 De(i) = ∞
1
1
h
1
1
i
11
Network Layer: 5-32
31 32
8
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) = 1
Db(f) = ∞ Db(g) = ∞ Db(h) = ∞ Db(i) = ∞
DVinb:
bc
8 compute 1 1
e
f
t=1
§ b receives DVs from a, c, e, computes:
ab 1
DVine:
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,∞,∞} = 8
Db(c) = min{cb,a+Da(c), cb,c +Dc(c), c b,e +De(c)} = min{∞,1,∞} = 1
Db(d) = min{cb,a+Da(d), cb,c +Dc(d), c b,e +De(d)} = min{9,2,∞} = 2
Db(e) = min{cb,a+Da(e), cb,c +Dc(e), c b,e +De(e)} = min{∞,∞,1} = 1
de
1
1
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{∞, ∞, ∞} = ∞
11
gh
Db(a) = 8 Db(c) = 1
Db(f) =2 Db(g) = ∞
DVinb:
1
i
Db(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) = 1
Db(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) = 1
Db(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) = ∞
b
8
1
e
t=1
§ c receives DVs from b
a
1
d
1
g
1
c
f
DVine:
De(a) = ∞ De(b) = 1 De(c) = ∞ De(d) = 1 De(e) = 0 De(f) = 1 De(g) = ∞ De(h) = 1 De(i) = ∞
1
1
h
1
1
i
11
Network Layer: 5-34
33 34
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) = 1
Db(f) = ∞ Db(g) = ∞ Db(h) = ∞ Db(i) = ∞
DVinb:
b
8
1
t=1
§ c receives DVs from b computes:
a
1
pute
* Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/
Network Layer: 5-35
1
comc
Dc(a) = min{cc,b+dDb(a}} = 1 + 8 = 9 e Dc(b) = min{cc,b+Db(b)} = 1 + 0 = 1
Dc(d) = min{cc,b+Db(d)} = 1+ ∞ = ∞
Dc(e) = min{cc,b+Db(e)} = 1 + 1 = 2
Dc(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) = 1
Db(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) = 1
DVind:
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, h
a
1
d1m1 1
8
b
coe 1
h
t=1?
1
c
Q: what is new DV computed in e at
1
pute
f
i
DVinh:
Dc(a) = ∞ Dc(b) = ∞ Dc(c) = ∞ Dc(d) = ∞ Dc(e) = 1 Dc(f) = ∞ Dc(g) = 1 Dc(h) = 0 Dc(i) = 1
g
11
1
Network Layer: 5-36
35 36
2/18/21
9
37 38
2/18/21
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
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
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
c’s state at t=0 may influence distance vector
t=3 computations up to 3 hops away, i.e., at b,a,e
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,
c, f, h and now at g,i as well
1
1
a1c t=1
b
8
1
e
d
t=2
t=3
t=4
1
1
h
f
1
1
i
g
1 1
Distance vector: link cost changes
link cost changes:
§node detects local link cost change §updates routing info, recalculates local DV §if DV changes, notify neighbors
1y 41
x 50 z
“good news travels fast”
t0 : 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 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-38
Distance vector: link cost changes
link cost changes:
60 y 41
x 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 change
§“bad 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 algorithms
message complexity
LS: n routers, O(n2) messages sent
DV: exchange between neighbors; convergence time varies
speed of convergence
LS: O(n2) algorithm, O(n2) messages
• may have oscillations
DV: convergence time varies • may have routing loops
• count-to-infinity problem
robustness: what happens if router malfunctions, or is compromised?
LS:
• router can advertise incorrect link cost • each router computes only its own
table
DV:
• DV router can advertise incorrect path cost (“I have a really low cost path to everywhere”): black-holing
• each router’s table used by others: error propagate thru network
Network Layer: 5-40
39 40
10
2/18/21
Network layer: “control plane” roadmap
§ introduction
§routing protocols §intra-ISP routing: OSPF §routing among ISPs: BGP §SDN control plane
§Internet Control Message Protocol
§network management, configuration
• SNMP
• NETCONF/YANG
Network Layer: 5-41
Making routing scalable
our routing study thus far - idealized § all routers identical
§ network “flat”
... not true in practice
scale: billions of destinations:
§ can’t store all destinations in routing tables!
§ routing table exchange would swamp links!
administrative autonomy:
§ Internet: a network of networks §each network admin may want to
control routing in its own network
Network Layer: 5-42
41 42
Internet approach to scalable routing
aggregate 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 different
intra-domain routing protocols
§ gateway router: at “edge” of its own AS,
has link(s) to router(s) in other AS’es
inter-AS (aka “inter-domain”):
routing among AS’es
§ gateways perform inter-domain routing (as well as intra-domain
routing)
Network Layer: 5-43
Interconnected ASes
inter-AS routing
1c AS3 1a intra-AS
routing 1b 1d
forwarding 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 destinations
Intra-AS Inter-AS Routing Routing
forwarding table
intra-AS
3c routing3a
int2rac-AS 2arouting
3b
2b AS1
AS2
Network Layer: 5-44
43 44
11
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 1c
AS3 1a 1d 1b
AS1 inter-domain routing must:
1. learn which destinations reachable through AS2, which through AS3
2. propagate this reachability info to all routers in AS1
3c 3a
2a
2c
other networks
other networks
2b
AS2
AS1
Network Layer: 5-45
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-46
45 46
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-47
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:
“summarize” distances to destinations in own area, advertise in backbone
local routers:
• flood LS in area only
• compute routing within
area
• forward packets to outside area 1
via area border router
backbone
area 2
boundary router:
connects to other ASes
area 3
backbone router:
runs OSPF limited to backbone
Network Layer: 5-48
internal routers
47 48
12
2/18/21
Network layer: “control plane” roadmap
§ introduction
§routing protocols §intra-ISP routing: OSPF §routing among ISPs: BGP §SDN control plane
§Internet Control Message Protocol
§network management, configuration
• SNMP
• NETCONF/YANG
Network 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 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-50
49 50
eBGP, iBGP connections
2b
1b 2a 2∂c 3b
1a 1c 2d 3∂a 3c AS2
1d 3d
AS1
eBGP connectivity AS 3 logical iBGP connectivity
1c
gateway routers run both eBGP and iBGP protocols
Network 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 X
AS1 1b
1a 1c
1d
3b
3a 3c
AS2 2b 3d
AS3
2a 2c 2d
BGP advertisement:
AS3, X
X
Network Layer: 5-52
51 52
13
2/18/21
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-53
BGP path advertisement
AS3
AS1 1b
1a 1c
1d
3b
3a 3c
AS2 2b 3d X
AS2,AS3,X
2a 2c 2d
AS3, 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 1c
Network Layer: 5-54
53 54
BGP path advertisement (more) AS3
AS1 1b AS3,X 1a AS3,X 1c
AS3,X
3b
3a 3c
AS2 2b 3d X
AS3,X
1d
2a 2c 2d
AS3, X
AS2,AS3,X
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-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 ACKs
OPEN request
• NOTIFICATION: reports errors in previous msg; also used to close connection
Network Layer: 5-56
55 56
14
BGP path advertisement
AS1 1b AS3,X AS3,X 1
AS3
3b
3a 3c
1aAS3,X1c AS2 3d X
local link interfaces at 1a, 1d
2
AS3,X
AS2,AS3,X
2b
2d
2 1d 1
2a
2c
AS3, X
dest
...
1c
X
...
interface
...
1
1
...
§ 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 1
Network Layer: 5-57
BGP path advertisement
AS1 1b 1
AS3
3b
3a 3c
1a2 1c AS2 2b 3d X
1d
2a 2c 2d
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 1
at 1a: OSPF intra-domain routing: to get to 1c, use interface 2
dest
...
1c
X
...
interface
...
2
2
...
§ § § § §
at 1a: to get to X, use interface 2
Network Layer: 5-58
57 58
2/18/21
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-59
Hot potato routing
AS3
AS1 1b
1a 1c
AS2 2b 112 2a 201 263 2c
3b
3a 3c
3d X
1d
AS1,AS3,X
AS3,X
2d
OSPF 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): don’t worry about inter-domain cost!
Network Layer: 5-60
59 60
15
61 62
2/18/21
BGP: achieving policy via advertisements
B x
Cy
ISP 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 B’s customers
A,w
w
provider network
legend:
customer
A
A,w
network:
§ C does not learn about CBAw path
§ C will route CAw (not using B) to get to w
Network Layer: 5-61
BGP: achieving policy via advertisements (more)
B x
provider network
legend:
customer
ISP 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)
w
A
Cy
§ 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 C
network:
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-PATH
3. closestNEXT-HOProuter:hotpotatorouting
4. additionalcriteria
Network Layer: 5-63
Network layer: “control plane” roadmap
§ introduction
§routing protocols §intra-ISP routing: OSPF §routing among ISPs: BGP §SDN control plane
§Internet Control Message Protocol
§network management, configuration
• SNMP
• NETCONF/YANG
Network Layer: 5-64
63 64
16
2/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 plane
Network Layer: 5-65
Per-router control plane
Individual routing algorithm components in each and every router interact in the control plane to computer forwarding tables
4.1
3
•
1
2
OVERVIEW OF NETWORK LAYER
309
Routing Algorithm Routing algorithm
Local forwarding table
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
control plane
data plane
Control plane Data plane
header
output
0100 0110 0111 1001
3 2 2 1
rriving ader
1101
0111
1 2
3
Values in a
values in arriving packet header
packet’s he
Network Layer: 4-66
65
66
forwarding and routing functions are contained within a router. As we’ll 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! We’ll 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. It’s 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. We’re 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 PM
Software defined networking (SDN)
Why a logically centralized control plane?
Software-Defined Networking (SDN) control plane
Remote controller computes, installs forwarding tables in routers
Remote Controller
control plane
data 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
values in arriving packet header
CA
CA
CA
CA
CA
67
68
0111
1
•
foster innovation: let 1000 flowers bloom
2
3
Network Layer: 4-67
Network Layer: 5-68
17
SDN analogy: mainframe to PC revolution
Specialized Applications
Specialized Operating System
Specialized Hardware
Vertically integrated Closed, proprietary Slow innovation Small industry
* Slide courtesy: N. McKeown
Ap
Ap p
Ap p
Ap p
Ap p
Ap p
Ap p
Ap p
Ap p
Ap p
Open Interface
or or Linux
Open Interface
App
p
Windows
MAC OS
Microprocessor
Horizontal Open interfaces Rapid innovation Huge industry
Network Layer: 5-69
Traffic engineering: difficult with traditional routing
5 2
w5
v
3 2
3
u1
z
2
1
x1y
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-70
69 70
Traffic engineering: difficult with traditional routing
5 2
w5
v
3 2
3
u1
z
2
1
x1y
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-71
Traffic engineering: difficult with traditional routing
5 2
w5
v
3 2
3
u1
z
2
1
x1y
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-72
71 72
2/18/21
18
73 74
Software 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 controller
network-control applications
routing
access control
...
load balance
2/18/21
Software defined networking (SDN)
4. programmable control
applications
routing
access control
... load balance
CA CA CA
3. control plane functions external to data-plane switches
control plane
data plane
2. control, data plane separation
Network Layer: 5-73
Remote Controller
CA
CA
1: generalized “flow-base forwarding (e.g., OpenFlow)
d”
Software 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 applications
routing
...
load balance
access control
control northbound API plane
SDN Controller (network operating system)
southbound API
data plane
SDN-controlled switches
Network 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, robustness
network-control applications
routing
...
access control
load balance
northbound API
southbound API
control plane
SDN Controller (network operating system)
data plane
SDN-controlled switches
Network Layer: 5-75
SDN Controller (network operating system)
southbound API
northbound API
control plane
data plane
75 76
SDN-controlled switches
Network Layer: 5-76
19
Components of SDN controller
routing
access load
control
balance
interface layer to network control apps: abstractions API
network-wide state management : state of networks links, switches, services: a distributed database
communication: communicate between SDN controller and controlled switches
SDN controller
Network Layer: 5-77
Interface, abstractions for network control apps
network RESTful ... graph API
intent
statistics ... flow tables Network-wide distributed, robust state management
Link-stateinfo hostinfo ... switchinfo
OpenFlow ... SNMP Communication to/from controlled devices
OpenFlow 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 actions
OpenFlow Controller
Network Layer: 5-78
77 78
OpenFlow: controller-to-switch messages
Key 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 port
OpenFlow Controller
Network Layer: 5-79
OpenFlow: switch-to-controller messages
Key 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 Controller
Fortunately, network operators don’t “program” switches by creating/sending OpenFlow messages directly. Instead use higher-level abstraction at controller
Network Layer: 5-80
79 80
2/18/21
20
SDN: control/data plane interaction example
Dijkstra’s link-state routing
1 2
... switch info 3 SNMP
S1, experiencing link failure uses OpenFlow port status message to notify controller
SDN controller receives OpenFlow message, updates link status info
Dijkstra’s routing algorithm application has previously registered to be called when ever link status changes. It is called.
Dijkstra’s routing algorithm access network graph info, link state info in controller, computes new routes
Network Layer: 5-81
4
network graph
3
statistics Link-state info
OpenFlow
1
s2 s1
s3
...
RESTful API
intent flow tables
...
2
host info
...
4
s4
SDN: control/data plane interaction example
Dijkstra’s link-state routing
45
RESTful ... intent 5
network graph
3
statistics Link-state info
OpenFlow
1
s2 s1
link state routing app interacts with flow-table-computation component in SDN controller, which computes new flow tables needed
API
...
flow tables ... switch info
SNMP
2
host info
...
s4 s3
6 controller uses OpenFlow to install new tables in switches that need updating
Network Layer: 5-82
81 82
2/18/21
OpenDaylight (ODL) controller
Firewalling Load Balancing ... REST/RESTCONF/NETCONF APIs
Traffic Engineering
Network Orchestrations and Applications Northbound API
Enhanced Services
AAA ... ...
OpenFlow NETCONF
Basic Network Functions
Topology Switch Stats processing mgr. mgr.
Forwarding Host rules mgr. Tracker
messaging SNMP OVSDB ...
Service Abstraction Layer (SAL)
Southbound API
Service Abstraction Layer: § interconnects internal, external applications
config. and operational data store
and services
Network Layer: 5-83
ONOS controller
Traffic Engineering
REST
hosts devices
Firewalling Load Balancing ...
Network Applications
Northbound API
Southbound API
API
Intent
flow rules statistics
northbound abstractions, protocols
topology
ONOS distributed core
§ §
§
control apps separate from controller
intent framework: high- level specification of service: what rather than how
considerable emphasis on distributed core: service reliability, replication performance scaling
Network Layer: 5-84
paths links
device link host flow packet southbound abstractions,
OpenFlow Netconf OVSDB protocols
83 84
21
6
85 86
2/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 networks
Network Layer: 5-85
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-86
Network layer: “control plane” roadmap
§ introduction
§routing protocols
§intra-ISP routing: OSPF §routing among ISPs: BGP §SDN control plane §Internet Control Message
Protocol
§network management, configuration
• SNMP
• NETCONF/YANG
Network 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 error
Type Code description
0 0 3 0 3 1 3 2 3 3 3 6 3 7 4 0
echo reply (ping)
dest. network unreachable dest host unreachable dest protocol unreachable dest port unreachable
dest network unknown dest host unknown
source quench (congestion control - not used)
echo request (ping)
route advertisement
router discovery
Network Layer: 4-88
8 0
9 0
10 0
110 TTL expired 120 bad IP header
87 88
22
89
90
91
92
Traceroute and ICMP
3 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/YANG
What 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 management
stopping criteria:
§ UDP segment eventually arrives at destination host
§ destination returns ICMP “port unreachable” message (type 3, code 3)
Network Layer: 4-89
§ introduction
§routing protocols §intra-ISP routing: OSPF §routing among ISPs: BGP §SDN control plane §Internet Control Message
Protocol
§network management, configuration
Network Layer: 5-91
Managing server:
application, typically with network managers (humans) in the loop
Network
management
managing server/controller
agent data managed device
agent data managed device
agent data managed device
Managed device:
equipment with manageable, configurable hardware, software components
Data: device “state” configuration data, operational data, device statistics
Network Layer: 5-92
protocol: used by managing server to query, configure, manage device; used by devices to inform managing server of data, events.
agent data
managed device
agent data managed device
data
Network Layer: 5-90
2/18/21
23
93 94
2/18/21
Network operator approaches to management
CLI (Command Line Interface)
• operator issues (types, scripts) direct to
individual 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 configuration
management.
• YANG: data modeling language
• NETCONF: communicate YANG-compatible
actions/data to/from/among remote devices
managing server/controller
agent data managed device
agent data managed device
agent data
managed device
Network Layer: 5-93
data
agent data
managed device
agent data managed device
SNMP protocol
Two ways to convey MIB info, commands:
managing data server/controller
agent data managed device
request/response mode
managing data server/controller
agent data managed device
trap mode
request
response
trap message
Network Layer: 5-94
SNMP protocol: message types
Message type
Function
GetRequest
GetNextRequest GetBulkRequest
manager-to-agent: “get me data”
(data instance, next data in list, block of data).
SetRequest
manager-to-agent: set MIB value
Response
Agent-to-manager: value, response to Request
Trap
Agent-to-manager: inform manager of exceptional event
Network Layer: 5-95
SNMP protocol: message formats
PDU type (0-3)
Ge
Request ID
t/set hea
Error Status (0-5)
der
Error Index
Name
Variable
Value
s to ge
Name
t/set
Value
....
message types 0-3
message type 4
Trap header
SNMP PDU
Trap info
PDU type 4
Enterprise
Agent Addr
Trap Type (0-7)
Specific code
Time stamp
Name
Value
....
Network Layer: 5-96
95 96
24
2/18/21
SNMP: Management Information Base (MIB)
§managed device’s operational (and some configuration) data agent data §gathered into device MIB module
• 400 MIB modules defined in RFC’s; many more vendor-specific MIBs §Structure of Management Information (SMI): data definition language §example MIB variables for UDP protocol:
Network Layer: 5-97
Object ID
1.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.5
Name
Type
Comments
total # datagrams delivered
# undeliverable datagrams (no application at port) # undeliverable datagrams (all other reasons)
UDPInDatagrams
UDPNoPorts
UDInErrors
UDPOutDatagrams 32-bit counter total # datagrams sent
udpTable SEQUENCE one entry for each port currently in use
32-bit counter 32-bit counter 32-bit counter
NETCONF overview
§goal: 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) protocol
Network Layer: 5-98
97 98
NETCONF initialization, exchange, close
managing server/controller
data
Session 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
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 we’ve 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