程序代写代做代考 algorithm graph C flex distributed system database Chapter 5 Network Layer: The Control Plane

Chapter 5 Network Layer: The Control Plane
Chapter 5: network layer control plane
All material copyright 1996-2016
J.F Kurose and K.W. Ross, All Rights Reserved
Chapter 5: outline
Network-layer functions
5.1 introduction
5.5 5. 6
The SDN control plane
Recall: two network-layer functions:
5. 2 routing protocols
ICMP: The Internet Control Message Protocol
 forwarding: move packets from router’s input to appropriate router output
data plane
 link state
 distance vector
5.7
Network management and SNMP
 routing: determine route taken by packets from source to destination
control plane
5.3 intra-AS routing in the Internet: OSPF
5.4 routing among the ISPs: BGP
Two approaches to structuring network control plane:
Network Layer: Control Plane 5-1
Network Layer: Control Plane 5-2
Network Layer: Control Plane 5-3
Network Layer: Control Plane 5-4
chapter goals: understand principles behind network control plane
 traditional routing algorithms
 SDN controllers
 Internet Control Message Protocol  network management
and their instantiation, implementation in the Internet:
 OSPF, BGP, OpenFlow, ODL and ONOS controllers, ICMP, SNMP
 per-router control (traditional)
 logically centralized control (software defined networking)

Per-router control plane
Logically centralized control plane
Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding tables
A distinct (typically remote) controller interacts with local control agents (CAs) in routers to compute forwarding tables
Routing Algorithm
control plane
Chapter 5: outline
Routing protocols
5.1 introduction
5.5 5. 6
The SDN control plane
Routing protocol goal: determine “good” paths (equivalently, routes), from sending hosts to receiving host, through network of routers
5. 2 routing protocols
 link state
 distance vector
5.3 intra-AS routing in the
ICMP: The Internet Control Message Protocol
 path: sequence of routers packets will traverse in going from given initial source host to given final destination host
Internet: OSPF
5.4 routing among the ISPs: BGP
 “good”: least “cost”, “fastest”, “least congested”
5.7
Network management and SNMP
control plane
data plane
data plane
CA
Network Layer: Control Plane 5-5
Network Layer: Control Plane 5-6
Network Layer: Control Plane 5-7
 routing: a “top-10” networking challenge!
Network Layer: Control Plane 5-8
Remote Controller
CA CA CA CA

Graph abstraction of the network
Graph abstraction: costs
Q: global or decentralized information?
Q: static or dynamic? static:
5.1 introduction
5.5 The SDN control plane
global:
 routes change slowly over time
5.2 routing protocols
 link state
 distance vector
5.3 intra-AS routing in the
5.6 ICMP: The Internet Control Message Protocol
 all routers have complete topology, link cost info
dynamic:
 “link state” algorithms
 routes change more quickly
5.7 Network management and SNMP
decentralized:
Internet: OSPF
 router knows physically- connected neighbors, link costs to neighbors
• periodic update
• in response to link
5.4 routing among the ISPs: BGP
 iterative process of computation, exchange of info with neighbors
cost changes
 “distance vector” algorithms
5
2v 3 w 5
5
c(x,x’) = cost of link (x,x’) e.g.,c(w,z)=5
u231z
v 3 w 25
cost could always be 1, or inversely related to bandwidth, or inversely related to congestion
12 x 1 y
u21z 13
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) }
xy2 1
aside: graph abstraction is useful in other network contexts, e.g., P2P, where N is set of peers and E is set of TCP connections
key question: what is the least-cost path between u and z ? routing algorithm: algorithm that finds that least cost path
Routing algorithm classification
Chapter 5: outline
Network Layer: Control Plane 5-9
Network Layer: Control Plane 5-10
Network Layer: Control Plane 5-11
Network Layer: Control Plane 5-12
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

A link-state routing algorithm
Dijsktra’s algorithm
Dijkstra’s algorithm
 net topology , link costs
notation:
1 2 3 4 5
Initialization:
knowntoallnodes
• accomplished via “link state
 c(x,y): link cost from nodextoy; =∞ifnot direct neighbors
N’={u}
for all nodes v
broadcast”
• all nodes have same info
 D(v): current value of 6 cost of path from source 7 to dest. v 8
if v adjacent to u then D(v) = c(u,v)
 computes least cost paths from one node (‘source”) to all other nodes
 p(v): predecessor node 9 along path from source to 10 v 11
Loop
• gives forwarding table for that node
 N’: set of nodes whose 12 least cost path definitively 13 known 14
find w not in N’ such that D(w) is a minimum
add w to N’
update D(v) for all v adjacent to w and not in N’ :
 iterative: after k iterations, know least cost path to k dest.’s
/* new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v */
Dijkstra’s algorithm: example D(v) D(w) D(x) D(y) D(z)
Dijkstra’s algorithm: another example
Step N’ p(v) p(w) p(x) p(y) p(z) 0 u 7,u 3,u 5,u ∞ ∞ 1uw6,w 5,u11,w∞
Step N’ D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1ux2,u4,x 2,x
2 uwx 6,w 3 uwxv
4 uwxvy
5 uwxvyz
11,w 14,x 10,v 14,x 12,y
2,u 3,y 4,y 3,y 4,y x94uxyvw 4,y
notes: 547  construct shortest path tree by 8
5 v
3
w
1 z
tracing predecessor nodes 3
 ties can exist (can be broken u w y
2 z
2
5
arbitrarily)
u
2
3
Network Layer: Control Plane 5-13
Network Layer: Control Plane 5-14
15
until all nodes in N’
2 uxy 3 uxyv
5
uxyvwz
3 xy2 741
else D(v) = ∞
D(v) = min( D(v), D(w) + c(w,v) )
v
Network Layer: Control Plane 5-15 examples: http://gaia.cs.umass.edu/kurose_ross/interactive/ Network Layer: Control Plane 5-16
* Check out the online interactive exercises for more
1

Dijkstra’s algorithm: example (2) resulting shortest-path tree from u:
Dijkstra’s algorithm, discussion
u
vw xy
z
algorithm complexity: n nodes
 each iteration: need to check all nodes, w, not in N  n(n+1)/2 comparisons: O(n2)
 more efficient implementations possible: O(nlogn)
resulting forwarding table in u:
 e.g., support link cost equals amount of carried traffic:
1 A 1+e 2+e A 0 0 A 2+e 2+e A 0
destination
link
Chapter 5: outline
Distance vector algorithm
5.1 introduction
5.5 5. 6
The SDN control plane
Bellman-Ford equation (dynamic programming)
5. 2 routing protocols
ICMP: The Internet Control Message Protocol
 link state
let
dx(y) := cost of least-cost path from x to y
 distance vector
5.3 intra-AS routing in the Internet: OSPF
5.7
Network management and SNMP
then
5.4 routing among the ISPs: BGP
dx(y) = min {c(x,v) + dv(y) } v
v x
(u,v) (u,x)
D00B D1+e1B D00B D1+e1B
y w z
(u,x) (u,x) (u,x)
11 e
given these costs, find new routing…. 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: Control Plane 5-17
Network Layer: Control Plane 5-18
Network Layer: Control Plane 5-19
Network Layer: Control Plane 5-20
oscillations possible:
0 C e
0 C 0
1 C 1+e
0 C 0
initially
cost from neighbor v to destination y cost to neighbor v
min taken over all neighbors v of x

Bellman-Ford example
Distance vector algorithm
u 1
2 3
z
• knows cost to each neighbor v: c(x,v)
2
5 2
B-F equation says:
 node x:
5
v 3
w 1
clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
 Dx(y) = estimate of least cost from x to y
• x maintains distance vector Dx = [Dx(y): y є N ]
x
1
y
du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z),
• maintains its neighbors’ distance vectors. For each neighbor v, x maintains
Dv =[Dv(y):yєN]
node achieving minimum is next
hop in shortest path, used in forwarding table
Distance vector algorithm
Distance vector algorithm
key idea:
iterative, asynchronous:
each node:
 from time-to-time, each node sends its own distance vector estimate to neighbors
each local iteration caused by:
wait for (change in local link cost or msg from neighbor)
 when x receives new DV estimate from neighbor, it updates its own DV using B-F equation:
 local link cost change
 DV update message from
D(y)←min{c(x,v)+D(y)} foreachnodey N xvv
distributed:
recompute estimates if DV to any dest has
 under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y)
 each node notifies neighbors only when its DV changes
changed, notify neighbors
c(u,w) + dw(z) } =min{2+5,
1 + 3,
5 + 3} = 4
Network Layer: Control Plane 5-21
Network Layer: Control Plane 5-22
Network Layer: Control Plane 5-23
Network Layer: Control Plane 5-24
neighbor
•
neighbors then notify their neighbors if necessary

from from
from
from from
from
from from from
from
from from
from
node x cost to table x y z
cost to
node x
table x y z
cost to
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
x y z x027 x023 y∞∞∞ y201
cost to
x y z
cost to
z∞∞∞ z710
y∞∞∞ z∞∞∞
y201 z310
node y cost to table x y z
node y cost to table x y z
cost to
cost to
x∞∞∞ y201 z∞∞∞
2 y 1
x z x∞∞∞
xyz x027 y201
xyz 2y1
node z cost to table x y z
node z cost to table x y z
cost to
cost to
= min{2+1 , 7+0} = 3
= min{2+1 , 7+0} = 3
x∞∞∞ x∞∞∞
x027 x023 y201 y201
y∞∞∞ z710
time
y∞∞∞ z710
z310 z310 time
Distance vector: link cost changes
Distance vector: link cost changes
link cost changes: 1
y 1 50
link cost changes: 60
y 1 50
 node detects local link cost change
4
 node detects local link cost change 4
 updates routing info, recalculates x distance vector
z
 bad news travels slow – “count to x infinity” problem!
z
 if DV changes, notify neighbors
 44 iterations before algorithm stabilizes: see text
“good news travels fast”
t0 : y detects link-cost change, updates its DV, informs its neighbors.
poisoned reverse:
t1 : z receives update from y, updates its table, computes new least cost to x , sends its neighbors its DV.
 If Z routes through Y to get to X :
 Z tells Y its (Z’s) distance to X is infinite (so Y won’t route
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.
to X via Z)
 will this completely solve count to infinity problem?
7
y201
z∞∞∞ z710
x023 x z y201 7 z310
Network Layer: Control Plane 5-25
Network Layer: Control Plane 5-26
Network Layer: Control Plane 5-27
Network Layer: Control Plane 5-28
x027
x023 y201 z710
xyz x023
xyz xyz

Comparison of LS and DV algorithms
Chapter 5: outline
message complexity
robustness: what happens if router malfunctions?
5.1 introduction
5.5 The SDN control plane
 LS: with n nodes, E links, O(nE) msgs sent
LS:
5.2 routing protocols
5.6 ICMP: The Internet Control Message Protocol
 D V: exchange between neighbors only
• •
node can advertise incorrect link cost
 link state
• convergence time varies speed of convergence
each node computes only its own table
 distance vector
5.7 Network management and SNMP
 LS: O(n2) algorithm requires O(nE) msgs
D V:
5.3 intra-AS routing in the Internet: OSPF
• may have oscillations
 D V: convergence time varies • may be routing loops
• •
DV node can advertise incorrect path cost
5.4 routing among the ISPs: BGP
• count-to-infinity problem
• error propagate thru network
Making routing scalable
Internet approach to scalable routing
our routing study thus far – idealized  all routers identical
 network “flat”
… not true in practice
aggregate routers into regions known as “autonomous systems” (AS) (a.k.a. “domains”)
scale: with billions of destinations:
administrative autonomy
in same AS (“network”)
 all routers in AS must run
 gateways perform inter- domain routing (as well as intra-domain routing)
 can’t store all destinations in routing tables!
 internet = network of networks
same intra-domain protocol
 routers in different AS can run
 routing table exchange would swamp links!
 each network admin may want to control routing in its own network
different intra-domain routing protocol
each node’s table used by others
Network Layer: Control Plane 5-29
Network Layer: Control Plane 5-30
Network Layer: Control Plane 5-31
Network Layer: Control Plane 5-32
intra-AS routing
inter-AS routing
 routing among hosts, routers  routing among AS’es

gateway router: at “edge” of its own AS, has link(s) to router(s) in other AS’es

Interconnected ASes
Inter-AS tasks
3c 3a 2c destined outside of AS1:
1. learn which dests are reachable through AS2, which through AS3
3bAS3 2a2b •
router should forward packet to gateway router , but which one?
1c
1a 1d 1b
AS2
2. propagate this reachability info to all routers in AS1
Intra-AS Routing
OSPF (Open Shortest Path First)
Intra-AS Routing algorithm
Inter-AS Routing algorithm
• •
intra-AS routing determine entries for destinations within AS
3c 3b
Forwarding table
3a
AS3 1c
2c
other networks
AS1
 forwarding table configured by both intra- and inter-AS routing algorithm
 also known as interior gateway protocols (IGP)  most common intra-AS routing protocols:
 “open”: publicly available  uses link-state algorithm
• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First (IS-IS protocol
• link state packet dissemination
• topology map at each node
• route computation using Dijkstra’s algorithm
essentially same as OSPF)
 router floods OSPF link-state advertisements to all other routers in entire AS
• IGRP: Interior Gateway Routing Protocol (Cisco proprietary for decades, until 2016)
• carried in OSPF messages directly over IP (rather than TCP or UDP
inter-AS & intra-AS determine entries for external destinations
other networks
1a
AS1 1d 1b
2a 2b AS2
Network Layer: Control Plane 5-33
Network Layer: Control Plane 5-34
Network Layer: Control Plane 5-35
Network Layer: Control Plane 5-36
 suppose router in AS1 receives datagram
AS1 must:
• link state: for each attached link
 IS-IS routing protocol: nearly identical to OSPF
job of inter-AS routing!

OSPF “advanced” features
 security: all OSPF messages authenticated (to prevent
Hierarchical OSPF
malicious intrusion)
boundary router
backbone router
 multiple same-cost paths allowed (only one path in RIP)
backbone
 for each link, multiple cost metrics for different TOS (e.g., satellite link cost set low for best effort ToS; high for real-time ToS)
area border routers
 integrated uni- and multi-cast support:
• Multicast OSPF (MOSPF) uses same topology data
area 3
base as OSPF
 hierarchical OSPF in large domains.
area 1
internal routers
Hierarchical OSPF
Chapter 5: outline
 two-level hierarchy: local area, backbone.
5.1 introduction
5.5 5. 6
The SDN control plane
• link-state advertisements only in area
5. 2 routing protocols
ICMP: The Internet Control Message Protocol
• each nodes has detailed area topology; only know direction (shortest path) to nets in other areas.
 link state
 area border routers: “summarize” distances to nets in own area, advertise to other Area Border routers.
 distance vector
5.7
Network management and SNMP
 backbone routers: run OSPF routing limited to backbone.
5.3 intra-AS routing in the Internet: OSPF
 boundary routers: connect to other AS’es.
Network Layer: Control Plane 5-39
5.4 routing among the ISPs: BGP
Network Layer: Control Plane 5-37
Network Layer: Control Plane 5-38
area 2
Network Layer: Control Plane 5-40

Internet inter-AS routing: BGP
eBGP, iBGP connections
 BGP (Border Gateway Protocol): the de facto inter-domain routing protocol
2b
• “glue that holds the Internet together”  BGP provides each AS a means to:
1b 2a 1d
2c
• eBGP: obtain subnet reachability information from neighboring ASes
∂ 1a1c ∂
3b
3c
• iBGP: propagate reachability information to all AS- internal routers.
AS 2
3d
• determine “good” routes to other networks based on reachability information and policy
AS 1
eBGP connectivity
AS 3
 allows subnet to advertise its existence to rest of Internet: “I am here”
1c gateway routers run both eBGP and iBGP protools
BGP basics
Path attributes and BGP routes
 BGP session: two BGP routers (“peers”) exchange BGP messages over semi-permanent TCP connection:
 advertised prefix includes BGP attributes • prefix + attributes = “route”
AS 1
1b
AS 3
3b
 Policy-based routing:
• gateway receiving route advertisement uses import policy to
1a
1c
3a
3c
accept/decline path (e. g. , never route through AS Y).
• advertising paths to different destination network prefixes (BGP is a “path vector” protocol)
 two important attributes:
• AS-PATH: list of ASes through which prefix advertisement
 when AS3 gateway router 3a advertises path AS3,X to AS2 gateway router 2c:
has passed
• AS3 promises to AS2 it will forward datagrams towards X
• NEXT-HOP: indicates specific internal-AS router to next- hop AS
1d
AS2 2b 2a
3d
X
• ASpolicyalsodetermineswhethertoadvertisepathto other other neighboring ASes
2d
Network Layer: Control Plane 5-43
Network Layer: Control Plane 5-44
2c
BGP advertisement: AS3, X
Network Layer: Control Plane 5-41
Network Layer: Control Plane 5-42
2d
3a
iBGP connectivity

BGP path advertisement
BGP path advertisement
AS1 1b
1a 1c
AS3 3b
3a 3c
AS1 1b
1a 1c
AS3 3b
3a 3c
1d
AS2 2b AS2,AS3,X 2a
AS3,X
3d
X
1d
AS2 2b 2a
AS3,X
3d X
 BGP messages:
• OPEN: opens TCP connection to remote BGP peer and
1 1a 2
3a
3c
X
authenticates sending BGP peer
local link interfaces at 1a, 1d
2
1
AS2
2b
3d
• UPDATE: advertises new path (or withdraws old)
AS2,AS3,X
2a
2c
• KEEPALIVE: keeps connection alive in absence of UPDATES; also ACKs OPEN request
physical link
 recall: 1a, 1b, 1c learn about dest X via iBGP
2d
2d
 AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3 router 3a
gateway router may learn about multiple paths to destination:  AS1 gateway router 1c learns path AS2,AS3,X from 2a
 Based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates (via iBGP) to all AS2 routers
 AS1 gateway router 1c learns path AS3,X from 3a
 Based on policy, AS1 gateway router 1c chooses path AS3,X, and
 Based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2, AS3, X to AS1 router 1c
advertises path within AS1 via iBGP
BGP messages
BGP, OSPF, forwarding table entries
 BGP messages exchanged between peers over TCP connection
Q: how does router set forwarding table entry to distant prefix?
• NOTIFICATION: reports errors in previous msg; also used to close connection
dest
interface …
2d
from 1c: “path to X goes through 1c”
2c
AS2,AS3,X
2c
Network Layer: Control Plane 5-45
Network Layer: Control Plane 5-46
Network Layer: Control Plane 5-47
Network Layer: Control Plane 5-48
AS1
1b
1c
AS3
3b
…
X
1
 1d: OSPF intra-domain routing: to get to 1c, forward over outgoing local interface 1
……
1d
AS3,X

BGP, OSPF, forwarding table entries
BGP route selection
Q: how does router set forwarding table entry to distant prefix?
 router may learn about more than one route to destination AS, selects route based on:
AS1 1b 1
AS3
3b
3c
1a 2
1c
3a
2b 3d X
1. local preference value attribute: policy decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria
dest interface … …
 recall: 1a, 1b, 1c learn about dest X via iBGP from 1c: “path to X goes through 1c”
X 2
 1d: OSPF intra-domain routing: to get to 1c, forward over outgoing local interface 1
……
1d
Hot Potato Routing
BGP: achieving policy via advertisements
AS1
1b
3b
1a
1c
3a
3c
customer network:
1d
AS3,X
Y
AS2
2a
2c
2d
 1a: OSPF intra-domain routing: to get to 1c, forward over outgoing local interface 2
AS2 2b
152 112
3d
X
C
2a 201
 2d learns (via iBGP) it can route to X via 2a or 2c
AS1,AS3,X
263 2c
2d
OSPF link weights
Suppose an ISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs)
 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!
 B gets no “revenue” for routing CBAw, since none of C, A, w are B’s customers
AS3
B
legend:
provider network
Network Layer: Control Plane 5-49
Network Layer: Control Plane 5-50
Network Layer: Control Plane 5-51
Network Layer: Control Plane 5-52
W A
X
 A advertises path Aw to B and to C  B chooses not to advertise BAw to C:
 C does not learn about CBAw path
 C will route CAw (not using B) to get to w

BGP: achieving policy via advertisements
Why different Intra-, Inter-AS routing ?
W
A
X
 inter-AS: admin wants control over how its traffic routed, who routes through its net.
Chapter 5: outline
Software defined networking (SDN)
5.1 introduction
5.5 The SDN control plane
 Internet network layer: historically has been implemented via distributed, per-router approach
5. 2 routing protocols
5. 6 ICMP: The Internet Control Message Protocol
• 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)
 link state
 distance vector
5.7 Network management and SNMP
5.3 intra-AS routing in the Internet: OSPF
• different “middleboxes” for different network layer functions: firewalls, load balancers, NAT boxes, ..
5.4 routing among the ISPs: BGP
 ~2005: renewed interest in rethinking network control plane
B
legend:
provider network
policy:
C
customer network:
 intra-AS: single admin, so no policy decisions needed
Y
scale:
Suppose an ISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs)
 hierarchical routing saves table size, reduced update traffic
 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
performance:
 .. so X will not advertise to B a route to C
Network Layer: Control Plane 5-53
Network Layer: Control Plane 5-54
Network Layer: Control Plane 5-55
Network Layer: Control Plane 5-56
 intra-AS: can focus on performance
 inter-AS: policy may dominate over performance

Recall: per-router control plane
Recall: logically centralized control plane
Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding tables
A distinct (typically remote) controller interacts with local control agents (CAs) in routers to compute forwarding tables
Routing Algorithm
control plane
Software defined networking (SDN)
Analogy: mainframe to PC evolution*
Why a logically centralized control plane?
 easier network management: avoid router
Ap Ap Ap Ap Ap Ap Ap Ap Ap Ap
misconfigurations, greater flexibility of traffic flows
Open Interface
or Linux or Mac
 table-based forwarding (recall OpenFlow API)
Specialized
Operating (OS)
allows “programming” routers
OS
• centralized “programming” easier: compute tables centrally and distribute
System
• distributed “programming: more difficult: compute tables as result of distributed algorithm (protocol) implemented in each and every router
Microprocessor
 open (non-proprietary) implementation of control plane
Horizontal
control plane
data plane
data plane
CA
Network Layer: Control Plane 5-57
Network Layer: Control Plane 5-58
Network Layer: Control Plane 5-59
* Slide courtesy: N. McKeown
Network Layer: Control Plane 5-60
Specialized Applications
pppppppppp
Specialized Hardware
Open Interface
Remote Controller
CA CA CA CA
Vertically integrated
Closed, proprietary Open interfaces
Slow innovation Rapid innovation Small industry Huge industry
App
Windows

Traffic engineering: difficult traditional routing
Traffic engineering: difficult
u
1
21z 3z
control plane
55 2v3w5 2v3w5
u231z u231z 1x1y2 1x1y2
Q: what if network operator wants u-to-z traffic to flow along uvwz, x-to-z traffic to flow xwyz?
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)
A: need to define link weights so traffic routing algorithm computes routes accordingly (or need a new routing algorithm)!
Link weights are only control “knobs”: wrong!
Traffic engineering: difficult
Networking 401
Software defined networking (SDN)
2
v3w v w
5
Remote Controller
5
4. programmable control
routing
access control
… load balance
3. control plane functions
xy2 x1y
data plane
Q: what if w wants to route blue and red traffic differently?
CA
2. control, data plane separation
A: can’t do it (with destination based forwarding, and LS, DV routing)
1: generalized“ flow- based” forwarding (e.g., OpenFlow)
Network Layer: Control Plane 5-61
Network Layer: Control Plane 5-62
Network Layer: Control Plane 5-63
Network Layer: Control Plane 5-64
applications
external to data- plane switches
CA
CA CA
CA

SDN perspective: data plane switches
SDN perspective: SDN controller
Data plane switches
network-control applications
SDN controller (network OS): network-control applications  maintain network state routing …
 fast, simple, commodity switches implementing generalized data-plane forwarding (Section 4.4) in hardware
routing … access
load balance
information load
 switch flow table computed, installed by controller
northbound API
control plane
 interacts with network switches “below” via southbound API
northbound API
control plane
 API for table-based switch control (e.g., OpenFlow)
SDN Controller (network operating system)
SDN Controller (network operating system)
• defines what is controllable and what is not
southbound API
system for performance,
southbound API
 protocol for communicating with controller (e.g., OpenFlow)
scalability, fault-tolerance,
Network Layer: Control Plane 5-65
SDN-controlled switches
Network Layer: Control Plane 5-66
SDN-controlled switches
SDN perspective: control applications
Components of SDN controller
network-control apps:
network-control applications
routing access load control balance
 “brains” of control: implement control functions using lower-level services, API provided by SND controller
routing … access
load balance
Interface layer to network control apps: abstractions API
Interface, abstractions for network control apps
 unbundled: can be provided by
northbound API
control plane
Network-wide state management layer: state of networks links, switches, services: a distributed database
…
3
party: distinct from routing
rd
vendor, or SDN controller
SDN Controller (network operating system)
statistics
Network-wide distributed, robust state management SDN
Network Layer: Control Plane 5-67
SDN-controlled switches
Network Layer: Control Plane 5-68
control
 interacts with network control applications “above” via northbound API
access balance control
control
network graph
RESTful API
… intent flow tables
southbound API
communication layer: communicate between SDN controller and controlled switches
data plane
robustness data
data plane
 implemented as distributed
Link-state info
host info
switch info
… OpenFlow … SNMP
controller
Communication to/from controlled devices
plane

OpenFlow protocol
OpenFlow: controller-to-switch messages
OpenFlow Controller
 
operates between controller, switch
Key controller-to-switch messages
OpenFlow: switch-to-controller messages
SDN: control/data plane interaction example
Key switch-to-controller messages
Dijkstra’s link-state Routing
1 2
S1, experiencing link failure using OpenFlow port status message to notify controller
 packet-in: transfer packet (and its control) to controller. See packet- out message from controller
OpenFlow Controller
4 network
5
 flow-removed: flow table entry deleted at switch
3 statistics
 port status: inform controller of a change on a port.
2
…
Fortunately, network operators don’t “program” switches by creating/sending OpenFlow messages directly. Instead use higher-level abstraction at controller
s2 s1

three classes of OpenFlow messages:
TCP used to exchange messages
 features: controller queries switch features, switch replies
OpenFlow Controller
• optional encryption
 configure: controller queries/sets switch configuration parameters
• controller-to-switch
• asynchronous (switch
 modify-state: add, delete, modify flow entries in the OpenFlow tables
to controller)
• symmetric (misc)
 packet-out: controller can send this packet out of specific switch port
Network Layer: Control Plane 5-69
Network Layer: Control Plane 5-70
Network Layer: Control Plane 5-71
Network Layer: Control Plane 5-72
graph
…
intent flow tables
Link-state info OpenFlow
host info
…3 switch info
Dijkstra’s routing algorithm application has previously registered to be called when ever link status changes. It is called.
1
RESTful API
…
SDN controller receives OpenFlow message, updates link status info
s4 s3
SNMP
4
Dijkstra’s routing algorithm access network graph info, link state info in controller, computes new routes

SDN: control/data plane interaction example
OpenDaylight (ODL) controller
network graph
RESTful API
…
5
link state routing app interacts with flow-table-computation component in SDN controller, which computes new flow tables needed
REST API
 network apps may be contained within, or be external to SDN controller
3 statistics
…
intent flow tables
Network service apps
Basic Network Service Functions
Link-state info OpenFlow
host info
switch info SNMP
Network control apps
…

hardening the control plane: dependable, reliable, performance-scalable, secure distributed system
REST API
Intent
northbound abstractions, protocols
 
control apps separate from controller
• robustness to failures: leverage strong theory of reliable distributed system for control plane
hosts devices
paths links
flow rules topology
intent framework: high-level specification of service: what rather than how
• dependability, security: “baked in” from day one? networks, protocols meeting mission-specific
link OpenFlow
host Netconf
flow
packet southbound abstractions,
device
Internet-scaling
Dijkstra’s link-state Routing
Traffic … Engineering
 ODL Lithium controller
45
1
… SNMP
2
…
6
Controller uses OpenFlow to install new tables in switches that need updating
forwarding host
s2 s1
OpenFlow 1.0
OVSDB
s4 s3
ONOS controller
SDN: selected challenges
…
Access Control
topology manager
switch manager
stats manager
 Service Abstraction Layer: interconnects internal, external applications and services
statistics ONOS distributed
 
requirements
• e.g., real-time, ultra-reliable, ultra-secure
OVSDB protocols
core

considerable emphasis on distributed core: service reliability, replication performance scaling
Network Layer: Control Plane 5-73
Network Layer: Control Plane 5-74
Network Layer: Control Plane 5-75
Network Layer: Control Plane 5-76
manager
manager
Service Abstraction Layer (SAL)

Chapter 5: outline
ICMP: internet control message protocol
5.1 introduction
5.5 The SDN control plane
 used by hosts & routers to communicate network- level information
Type Code description
5.2 routing protocols
5.6
ICMP: The Internet Control Message Protocol
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
TTL expired
bad IP header
 link state
• error reporting: unreachable host, network, port, protocol
 distance vector
5.7
Network management and SNMP
5.3 intra-AS routing in the Internet: OSPF
• echo request/reply (used by ping)
5.4 routing among the ISPs: BGP
 network-layer “above” IP: • ICMP msgs carried in IP
8 0 9 0 10 0 11 0 12 0
Traceroute and ICMP
Chapter 5: outline
 source sends series of UDP segments to destination
 when ICMP message arrives, source records R T Ts
5.1 introduction
5.5 5. 6
The SDN control plane
• first set has TTL =1
• second set has TTL=2, etc. • unlikely port number
stopping criteria:
5. 2 routing protocols
ICMP: The Internet Control Message Protocol
 when datagram in nth set arrives to nth router:
 distance vector
5.7
Network management and SNMP
• router discards datagram and sends source ICMP message (type 11, code 0)
 destination returns ICMP “port unreachable” message (type 3, code 3)
5.3 intra-AS routing in the Internet: OSPF
• ICMP message include name of router & IP address
 source stops
5.4 routing among the ISPs: BGP
3 probes 3 probes 3 probes
Network Layer: Control Plane 5-77
Network Layer: Control Plane 5-78
 UDP segment eventually arrives at destination host
 link state
Network Layer: Control Plane 5-79
Network Layer: Control Plane 5-80
datagrams
 ICMP message: type, code plus first 8 bytes of IP datagram causing error

What is network management?
Infrastructure for network management
 autonomous systems (aka “network”): 1000s of interacting hardware/software components
definitions:
 other complex systems requiring monitoring, control: • jet airplane
managing entity
agent data managed device
• nuclear power plant • others?
managing entity
data
managed devices contain managed objects whose data is gathered into a Management Information Base (MIB)
“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.”
network management protocol
agent data managed device
SNMP protocol
SNMP protocol: message types
Two ways to convey MIB info, commands:
Message type
Function
request
InformRequest SetRequest
manager-to-manager: here’s MIB value manager-to-agent: set MIB value
managing entity
managing entity
GetRequest GetNextRequest GetBulkRequest
manager-to-agent: “get me data”
(data instance, next data in list, block of data)
response
agent data managed device
agent data managed device
Response Trap
Agent-to-manager: value, response to Request
request/response mode
trap mode
Agent-to-manager: inform manager of exceptional event
trap msg
Network Layer: Control Plane 5-81
Network Layer: Control Plane 5-82
Network Layer: Control Plane 5-83
Network Layer: Control Plane 5-84
agent data managed device
agent data
managed device
agent data managed device

SNMP protocol: message formats
Chapter 5: summary
PDU type (0-3)
Request Error ID Status
Error Index
Name Value
Name
Value
….
 approaches to network control plane
• per-router control (traditional)
• logically centralized control (software defined networking)
PDU type 4
Agent Enterprise Addr
Trap Type (0-7)
Specific Time code stamp
Name
Value
….
 traditional routing algorithms
• implementation in Internet: OSPF, BGP
Get/set header
Variables to get/set
we’ve learned a lot!
(0-5)
Trap header SNMP PDU
Trap info
 SDN controllers
• implementation in practice: ODL, ONOS
More on network management: see earlier editions of text!
Network Layer: Control Plane 5-85
next stop: link layer!
 Internet Control Message Protocol  network management
Network Layer: Control Plane 5-86