Module 4

Network Layer: Control Plane

Network layer control plane: our goals
▪understand principles ▪ instantiation, implementation
behind network control in the Internet:
plane: • OSPF, BGP
• traditional routing algorithms • OpenFlow, ODL and ONOS
• SDN controllers controllers
• network management, • Internet Control Message
configuration Protocol: ICMP
• SNMP, YANG/NETCONF

Network Layer: 5-2

 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ link state
▪ distance vector
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP
▪ network management,
▪ SDN control plane configuration
▪ Internet Control Message • SNMP
Protocol • NETCONF/YANG

Network Layer: 5-3

Network-layer functions
▪ forwarding: move packets from router’s
input to appropriate router output
data plane
▪ routing: determine route taken by
packets from source to destination control plane

Two approaches to structuring network control plane:

▪ per-router control (traditional)
▪ logically centralized control (software defined networking)

Network Layer: 5-4

Per-router control plane
Individual routing algorithm components in each and every
router interact in the control plane

Routing
Algorithm
control
plane

data
plane

values in arriving
packet header
0111 1
2
3

Network Layer: 5-5

Software-Defined Networking (SDN) control plane
Remote controller computes, installs forwarding tables in routers

Remote Controller

control
plane

data
plane

CA
CA CA CA CA
values in arriving
packet header

0111 1
2
3

Network Layer: 5-6

Per-router
SDN control plane
control plane
 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ link state
▪ distance vector
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP ▪ network management,
▪ SDN control plane configuration
▪ Internet Control Message • SNMP
Protocol • NETCONF/YANG

Network Layer: 5-8

Routing protocols mobile network
national or global ISP
Routing protocol goal: determine
“good” paths (equivalently, routes),
from sending hosts to receiving host, application
transport

through network of routers network

link
physical

▪ path: sequence of routers packets network

link
physical
network
link

traverse from given initial source host

physical

to final destination host network

link
physical
network
link
physical

▪ “good”: least “cost”, “fastest”, “least

network
link datacenter
physical network

congested”
application
▪ routing: a “top-10” networking transport
network

challenge! enterprise
network
link
physical

Network Layer: 5-9

Graph abstraction: link costs
5
ca,b: cost of direct link connecting a and b
v 3
w e.g., cw,z = 5, cu,z = ∞
2 5
u 2 1 z
3 cost defined by network operator:
1
x y 2 could always be 1, or inversely related
1
to bandwidth, or inversely related to
congestion
graph: G = (N,E)
N: set of routers = { u, v, w, x, y, z }
E: set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Network Layer: 5-10

 Routing algorithm classification
global: all routers have complete
topology, link cost info
• “link state” algorithms
How fast
dynamic: routes change
do routes static: routes change more quickly
change? slowly over time • periodic updates or in
response to link cost
changes
decentralized: iterative process of
computation, exchange of info with neighbors
• routers initially only know link costs to
attached neighbors
• “distance vector” algorithms
global or decentralized information? Network Layer: 5-11
 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ link state
▪ distance vector
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP ▪ network management,
▪ SDN control plane configuration
▪ Internet Control Message • SNMP
Protocol • NETCONF/YANG

Network Layer: 5-12

Dijkstra’s link-state routing algorithm
▪ centralized: network topology, link notation
costs known to all nodes
• accomplished via “link state
▪ cx,y: direct link cost from
node x to y; = ∞ if not direct
broadcast” neighbors
• all nodes have same info
▪ D(v): current estimate of cost
▪ computes least cost paths from one of least-cost-path from source
node (“source”) to all other nodes to destination v
• gives forwarding table for that node ▪ p(v): predecessor node along
path from source to v
▪ iterative: after k iterations, know
▪ N': set of nodes whose least-
least cost path to k destinations cost-path definitively known

Network Layer: 5-13

Dijkstra’s link-state routing algorithm
1 Initialization:
2 N' = {u} /* compute least cost path from u to all other nodes */
3 for all nodes v
4 if v adjacent to u /* u initially knows direct-path-cost only to direct neighbors */
5 then D(v) = cu,v /* but may not be minimum cost! */
6 else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for all v adjacent to w and not in N' :
12 D(v) = min ( D(v), D(w) + cw,v )
13 /* 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-14
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1
2
3
4
5

5 Initialization (step 0):

For all a: if a adjacent to u then D(a) = cu,a
3
v w 5
2
u 2 1 z
3
1 2
x 1
y
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux
2
3
4
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5
u 2 1 z
3
1 2
x 1
y
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2
3
4
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5 11 update D(b) for all b adjacent to a and not in N' :
u 2 1 z D(b) = min ( D(b), D(a) + ca,b )
3
1 2 D(v) = min ( D(v), D(x) + cx,v ) = min(2, 1+2) = 2
x 1
y
D(w) = min ( D(w), D(x) + cx,w ) = min (5, 1+3) = 4
D(y) = min ( D(y), D(x) + cx,y ) = min(inf,1+1) = 2
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy
3
4
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5
u 2 1 z
3
1 2
x 1
y
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3
4
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5 11 update D(b) for all b adjacent to a and not in N' :
u 2 1 z D(b) = min ( D(b), D(a) + ca,b )
3
1
x y 2 D(w) = min ( D(w), D(y) + cy,w ) = min (4, 2+1) = 3
1 D(z) = min ( D(z), D(y) + cy,z ) = min(inf,2+2) = 4
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv
4
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5
u 2 1 z
3
1 2
x 1
y
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5 11 update D(b) for all b adjacent to a and not in N' :
u 2 1 z D(b) = min ( D(b), D(a) + ca,b )
3
1
x y 2 D(w) = min ( D(w), D(v) + cv,w ) = min (3, 2+3) = 3
1
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5
u 2 1 z
3
1 2
x 1
y
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5 11 update D(b) for all b adjacent to a and not in N' :
u 2 1 z D(b) = min ( D(b), D(a) + ca,b )
3
1
x y 2 D(z) = min ( D(z), D(w) + cw,z ) = min (4, 3+5) = 4
1
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5
u 2 1 z
3
1 2
x 1
y
Dijkstra’s algorithm: an example
v w x y z
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz
8 Loop
5 9 find a not in N' such that D(a) is a minimum
v 3
w
10 add a to N'
2 5 11 update D(b) for all b adjacent to a and not in N' :
u 2 1 z D(b) = min ( D(b), D(a) + ca,b )
3
1 2
x 1
y
 Dijkstra’s algorithm: an example
5
3
v w 5
2
u 2 1 z
3
1 2
x 1
y

resulting least-cost-path tree from u: resulting forwarding table in u:

destination outgoing link
v w
v (u,v) route from u to v directly
u z x (u,x)
y (u,x) route from u to all
x y w (u,x) other destinations
x (u,x) via x
Network Layer: 5-27
 Dijkstra’s algorithm: another example
v w x y z
D(v), D(w), D(x), D(y), D(z), x
9
Step N' p(v) p(w) p(x) p(y) p(z)

0 u 7,u 3,u 5,u ∞ ∞ 5 7

4
1 uw 6,w 5,u 11,w ∞ 8
2 uwx 6,w 11,w 14,x 3 w z
u y
2
3 uwxv 10,v 14,x
3
4 uwxvy 12,y 7 4

5 uwxvyz v

notes:
▪ construct least-cost-path tree by tracing predecessor nodes
▪ ties can exist (can be broken arbitrarily)
Network Layer: 5-28
Dijkstra’s algorithm: discussion
algorithm complexity: n nodes
▪ each of n iteration: need to check all nodes, w, not in N
▪ n(n+1)/2 comparisons: O(n2) complexity
▪ more efficient implementations possible: O(nlogn)
message complexity:
▪ each router must broadcast its link state information to other n routers
▪ efficient (and interesting!) broadcast algorithms: O(n) link crossings to disseminate a
broadcast message from one source
▪ each router’s message crosses O(n) links: overall message complexity: O(n2)

Network Layer: 5-29

 Dijkstra’s algorithm: oscillations possible
▪ when link costs depend on traffic volume, route oscillations possible
▪ sample scenario:
• routing to destination a, traffic entering at d, c, e with rates 1, e (<1), 1
• link costs are directional, and volume-dependent

a 2+e
a a 2+e a
1 1+e 0 0 2+e 0
d b d 1+e 1 b d 0 0
b d 1+e 1 b
0 0
e 1 0 1 1 1 1 0
1 0
c c 0
c 1+e 1 c 0 1
1
e e e
e

given these costs, given these costs, given these costs,

initially find new routing…. find new routing…. find new routing….
resulting in new costs resulting in new costs resulting in new costs

Network Layer: 5-30

 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ link state
▪ distance vector
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP ▪ network management,
▪ SDN control plane configuration
▪ Internet Control Message • SNMP
Protocol • NETCONF/YANG

Network Layer: 5-31

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-32
Bellman-Ford Example
Suppose that u’s neighboring nodes, x,v,w, know that for destination z:
Dv(z) = 5 Dw(z) = 3 Bellman-Ford equation says:
5
Du(z) = min { cu,v + Dv(z),
3 w
v 5 cu,x + Dx(z),
2
u 2 1 z cu,w + Dw(z) }
3
1 2
= min {2 + 5,
x 1
y 1 + 3,
5 + 3} = 4
Dx(z) = 3
node achieving minimum (x) is
next hop on estimated least-
cost path to destination (z)
Network Layer: 5-33
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-34

Distance vector algorithm:
each node: iterative, asynchronous: each local
iteration caused by:
wait for (change in local link ▪ local link cost change
cost or msg from neighbor) ▪ DV update message from neighbor

recompute DV estimates using distributed, self-stopping: each

node notifies neighbors only when
DV received from neighbor its DV changes
▪ neighbors then notify their
if DV to any destination has neighbors – only if necessary
changed, notify neighbors ▪ no notification received, no
actions taken!

Network Layer: 5-35

 Distance vector: example
DV in a:
Da(a)=0
Da(b) = 8
Da(c) = ∞ a b c
Da(d) = 1 8 1
Da(e) = ∞
t=0 Da(f) = ∞
1 1
Da(g) = ∞
Da(h) = ∞
▪ All nodes have
Da(i) = ∞
distance estimates
to nearest A few asymmetries:
d e f ▪ missing link
neighbors (only) 1 1
▪ larger cost
▪ All nodes send
their local
distance vector to 1 1 1
their neighbors

g h i
1 1

Network Layer: 5-36

 Distance vector example: iteration

a b c
8 1

t=1 1 1
All nodes:
▪ receive distance
vectors from
neighbors d e f
▪ compute their new 1 1
local distance
vector
▪ send their new 1 1 1
local distance
vector to neighbors

g h i
1 1

Network Layer: 5-37

 Distance vector example: iteration

a
compute compute
b compute
c
8 1

t=1 1 1
All nodes:
▪ receive distance
vectors from
neighbors d
compute compute
e compute
f
▪ compute their new 1 1
local distance
vector
▪ send their new 1 1 1
local distance
vector to neighbors

g
compute h
compute compute
i
1 1

Network Layer: 5-38

 Distance vector example: iteration

a b c
8 1

t=1 1 1
All nodes:
▪ receive distance
vectors from
neighbors d e f
▪ compute their new 1 1
local distance
vector
▪ send their new 1 1 1
local distance
vector to neighbors

g h i
1 1

Network Layer: 5-39

 Distance vector example: iteration

a b c
8 1

t=2 1 1
All nodes:
▪ receive distance
vectors from
neighbors d e f
▪ compute their new 1 1
local distance
vector
▪ send their new 1 1 1
local distance
vector to neighbors

g h i
1 1

Network Layer: 5-40

 Distance vector example: iteration

compute
a compute
b compute
c
2 1

t=2 1 1
All nodes:
▪ receive distance
vectors from
neighbors compute
d compute
e compute
f
▪ compute their new 1 1
local distance
vector
▪ send their new 1 1 1
local distance
vector to neighbors

g
compute compute
h compute
i
8 1

Network Layer: 5-41

 Distance vector example: iteration

a b c
8 1

t=2 1 1
All nodes:
▪ receive distance
vectors from
neighbors d e f
▪ compute their new 1 1
local distance
vector
▪ send their new 1 1 1
local distance
vector to neighbors

g h i
1 1

Network Layer: 5-42

Distance vector example: iteration

…. and so on

Let’s next take a look at the iterative computations at nodes

Network Layer: 5-43

 Distance vector example: computation DV in b:
Db(a) = 8 Db(f) = ∞
DV in c:
Dc(a) = ∞
Dc(b) = 1
Db(c) = 1 Db(g) = ∞
Db(d) = ∞ Db(h) = ∞ Dc(c) = 0
DV in a: Dc(d) = ∞
Db(e) = 1 Db(i) = ∞
Da(a)=0
Dc(e) = ∞
Da(b) = 8
Dc(f) = ∞
Da(c) = ∞ a b c Dc(g) = ∞
Da(d) = 1 8 1
Dc(h) = ∞
Da(e) = ∞
t=1 Da(f) = ∞
1 1
Dc(i) = ∞
Da(g) = ∞
▪ b receives DVs Da(h) = ∞ DV in e:
from a, c, e Da(i) = ∞ De(a) = ∞
De(b) = 1
d e f De(c) = ∞
1 1 De(d) = 1
De(e) = 0
De(f) = 1
1 1 1 De(g) = ∞
De(h) = 1
De(i) = ∞

g h i
1 1

Network Layer: 5-44

 Distance vector example: computation DV in b:
Db(a) = 8 Db(f) = ∞
DV in c:
Dc(a) = ∞
Dc(b) = 1
Db(c) = 1 Db(g) = ∞
Db(d) = ∞ Db(h) = ∞ Dc(c) = 0
DV in a: Dc(d) = ∞
Db(e) = 1 Db(i) = ∞
Da(a)=0
Dc(e) = ∞
Da(b) = 8
Dc(f) = ∞
Da(c) = ∞ a b c
Da(d) = 1 8 compute 1 Dc(g) = ∞
Dc(h) = ∞
Da(e) = ∞
t=1 Da(f) = ∞
1 1
Dc(i) = ∞
Da(g) = ∞
▪ b receives DVs Da(h) = ∞ DV in e:
from a, c, e, Da(i) = ∞ De(a) = ∞
computes: e
De(b) = 1
d e f De(c) = ∞
1
Db(a) = min{cb,a+Da(a), cb,c +Dc(a), cb,e+De(a)} = min{8,∞,∞} =8 1 De(d) = 1
Db(c) = min{cb,a+Da(c), cb,c +Dc(c), c b,e +De(c)} = min{∞,1,∞} = 1 De(e) = 0
Db(d) = min{cb,a+Da(d), cb,c +Dc(d), c b,e +De(d)} = min{9,2,∞} = 2 De(f) = 1
1 1 1 De(g) = ∞
Db(e) = min{cb,a+Da(e), cb,c +Dc(e), c b,e +De(e)} = min{∞,∞,1} = 1
De(h) = 1
Db(f) = min{cb,a+Da(f), cb,c +Dc(f), c b,e +De(f)} = min{∞,∞,2} = 2
DV in b:
De(i) = ∞
Db(g) = min{cb,a+Da(g), cb,c +Dc(g), c b,e+De(g)} = min{∞, ∞, ∞} = ∞ Db(a) = 8 Db(f) =2
g h D (c) = 1 Db(g)
i =∞
1 ∞, 2} = 2
Db(h) = min{cb,a+Da(h), cb,c +Dc(h), c b,e+De(h)} = min{∞, 1Db(d) = 2 Db(h) = 2
b
Db(i) = min{cb,a+Da(i), cb,c +Dc(i), c b,e+De(i)} = min{∞, ∞, ∞} = ∞ Db(e) = 1 Db(i) = ∞
Network Layer: 5-45
 Distance vector example: computation DV in b:
Db(a) = 8 Db(f) = ∞
DV in c:
Dc(a) = ∞
Dc(b) = 1
Db(c) = 1 Db(g) = ∞
Db(d) = ∞ Db(h) = ∞ Dc(c) = 0
DV in a: Dc(d) = ∞
Db(e) = 1 Db(i) = ∞
Da(a)=0
Dc(e) = ∞
Da(b) = 8
Dc(f) = ∞
Da(c) = ∞ a b c Dc(g) = ∞
Da(d) = 1 8 1
Dc(h) = ∞
Da(e) = ∞
t=1 Da(f) = ∞
1 1
Dc(i) = ∞
Da(g) = ∞
▪ c receives DVs Da(h) = ∞ DV in e:
from b Da(i) = ∞ De(a) = ∞
De(b) = 1
d e f De(c) = ∞
1 1 De(d) = 1
De(e) = 0
De(f) = 1
1 1 1 De(g) = ∞
De(h) = 1
De(i) = ∞

g h i
1 1

Network Layer: 5-46

 Distance vector example: computation DV in b:
Db(a) = 8 Db(f) = ∞
DV in c:
Dc(a) = ∞
Dc(b) = 1
Db(c) = 1 Db(g) = ∞
Db(d) = ∞ Db(h) = ∞ Dc(c) = 0
Db(e) = 1 Db(i) = ∞ Dc(d) = ∞
Dc(e) = ∞
Dc(f) = ∞
a b c
compute Dc(g) = ∞
8 1
Dc(h) = ∞

t=1 1 1
Dc(i) = ∞

▪ c receives DVs
from b computes:

d b(a}} = 1 + 8 = 9
Dc(a) = min{cc,b+D e f
DV in c:
Dc(b) = min{cc,b+Db(b)} = 1 + 0 = 1
Dc(a) = 9
Dc(d) = min{cc,b+Db(d)} = 1+ ∞ = ∞ Dc(b) = 1
Dc(e) = min{cc,b+Db(e)} = 1 + 1 = 2 Dc(c) = 0
Dc(d) = 2
Dc(f) = min{cc,b+Db(f)} = 1+ ∞ = ∞
Dc(e) = ∞
Dc(g) = min{cc,b+Db(g)} = 1+ ∞ = ∞ * Check out the online interactive
Dc(f) = ∞ exercises for more examples:
Dc(h) = min{cbc,bg+Db(h)} = 1+ ∞ = ∞ h Dc(g) = ∞ i [Link]
Dc(i) = min{cc,b+Db(i)} = 1+ ∞ = ∞ Dc(h) = ∞
Dc(i) = ∞
Network Layer: 5-47
 Distance vector example: computation DV in b:
Db(a) = 8 Db(f) = ∞
Db(c) = 1 Db(g) = ∞
Db(d) = ∞ Db(h) = ∞ DV in e:
DV in d: Db(e) = 1 Db(i) = ∞
De(a) = ∞
Dc(a) = 1 De(b) = 1
Dc(b) = ∞ a De(c) = ∞
b c
Dc(c) = ∞ 8 1 De(d) = 1
Dc(d) = 0 De(e) = 0
t=1 Dc(e) = 1
Dc(f) = ∞ 1
Q: what is new DV computed in e at
1t=1?
De(f) = 1
De(g) = ∞
▪ e receives DVs Dc(g) = 1 De(h) = 1
from b, d, f, h Dc(h) = ∞ De(i) = ∞
Dc(i) = ∞
d compute
e
1
f DV in f:
DV in h: 1
Dc(a) = ∞
Dc(a) = ∞ Dc(b) = ∞
Dc(b) = ∞ Dc(c) = ∞
Dc(c) = ∞ 1 1 1 Dc(d) = ∞
Dc(d) = ∞ Dc(e) = 1
Dc(e) = 1 Dc(f) = 0
Dc(f) = ∞ Dc(g) = ∞
Dc(g) = 1 g h i Dc(h) = ∞
1 1
Dc(h) = 0 Dc(i) = 1
Dc(i) = 1 Network Layer: 5-48
Distance vector: state information diffusion
Iterative communication, computation steps diffuses information through network:
t=0 c’s state at t=0 is at c only
a b c
8 1
c’s state at t=0 has propagated to b, and
t=1 may influence distance vector computations
up to 1 hop away, i.e., at b 1 1 t=1
t=2
c’s state at t=0 may now influence distance
t=2 vector computations up to 2 hops away, i.e.,
d e f
at b and now at a, e as well 1 1

c’s state at t=0 may influence distance vector

t=3
computations up to 3 hops away, i.e., at d, f, h 1 1 1 t=3

c’s state at t=0 may influence distance vector

t=4 g
computations up to 4 hops away, i.e., at g, i 1
h 1
i
t=4
 Distance vector: link cost changes
link cost changes: 1
y
4 1
▪ node detects local link cost change x z
50
▪ updates routing info, recalculates local DV
▪ if DV changes, notify neighbors

t0 : y detects link-cost change, updates its DV, informs its neighbors.

“good news t1 : z receives update from y, updates its DV, computes new least cost
travels fast” to x , sends its neighbors its DV.
t2 : y receives z’s update, updates its DV. y’s least costs do not
change, so y does not send a message to z.
Distance vector: link cost changes
link cost changes: 60
y
4 1
▪ node detects local link cost change x z
50
▪ “bad news travels slow” – count-to-infinity
•problem:
y sees direct link to x has new cost 60, but z has said it has a path at cost of 5. So
y computes “my new cost to x will be 6, via z); notifies z of new cost of 6 to x.
• z learns that path to x via y has new cost 6, so z computes “my new cost to
x will be 7 via y), notifies y of new cost of 7 to x.
• y learns that path to x via z has new cost 7, so y computes “my new cost to
x will be 8 via y), notifies z of new cost of 8 to x.
• z learns that path to x via y has new cost 8, so z computes “my new cost to
x will be 9 via y), notifies y of new cost of 9 to x.
…
▪ see text for solutions. Distributed algorithms are tricky!
Comparison of LS and DV algorithms
message complexity robustness: what happens if router
LS: n routers, O(n2) messages sent malfunctions, or is compromised?
DV: exchange between neighbors; LS:
convergence time varies • router can advertise incorrect link cost
• each router computes only its own
speed of convergence table
LS: O(n2) algorithm, O(n2) messages DV:
• may have oscillations
• DV router can advertise incorrect path
DV: convergence time varies cost (“I have a really low-cost path to
• may have routing loops everywhere”): black-holing
• count-to-infinity problem
• each router’s DV is used by others:
error propagate thru network
Making routing scalable
our routing study thus far - idealized
▪ all routers identical
▪ network “flat”
… not true in practice
scale: billions of destinations: administrative autonomy:
▪ can’t store all destinations in ▪ Internet: a network of networks
routing tables! ▪ each network admin may want to
▪ routing table exchange would control routing in its own network
swamp links!

Network Layer: 5-53

Internet approach to scalable routing
aggregate routers into regions known as “autonomous
systems” (AS) (a.k.a. “domains”)

intra-AS (aka “intra-domain”): inter-AS (aka “inter-domain”):

routing among routers within same routing among AS’es
AS (“network”) ▪ gateways perform inter-domain
▪ all routers in AS must run same intra- routing (as well as intra-domain
domain protocol routing)
▪ routers in different AS can run different
intra-domain routing protocols
▪ gateway router: at “edge” of its own AS,
has link(s) to router(s) in other AS’es
Network Layer: 5-54
Interconnected ASes
forwarding table configured by intra-
and inter-AS routing algorithms
Intra-AS Inter-AS
Routing Routing ▪ intra-AS routing determine entries for
forwarding destinations within AS
table
▪ inter-AS & intra-AS determine entries
for external destinations

intra-AS
3c
routing3a inter-AS routing intra-AS
2c
3b 2a routing
2b
1c
intra-AS
AS3
1a routing 1b AS2
1d
AS1

Network Layer: 5-55

 Inter-AS routing: a role in intradomain forwarding
▪ suppose router in AS1 receives AS1 inter-domain routing must:
datagram destined outside of AS1: 1. learn which destinations reachable
• router should forward packet to through AS2, which through AS3
gateway router in AS1, but which 2. propagate this reachability info to all
one? routers in AS1

3c other
3a 2c
3b 2a networks
2b
1c
AS3
other 1a 1b AS2
networks
1d
AS1

Network Layer: 5-56

Intra-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-57

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-58

 Hierarchical OSPF
▪ two-level hierarchy: local area, backbone.
• link-state advertisements flooded only in area, or backbone
• each node has detailed area topology; only knows direction to reach
other destinations
area border routers: boundary router:
“summarize” distances to connects to other ASes
backbone
destinations in own area, backbone router:
advertise in backbone runs OSPF limited
to backbone
local routers:
• flood LS in area only area 3
• compute routing within
area
internal
• forward packets to outside routers
area 1
via area border router
area 2 Network Layer: 5-59
 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP
▪ SDN control plane
▪ Internet Control Message ▪ network management,
Protocol configuration
• SNMP
• NETCONF/YANG

Network Layer: 5-60

Interconnected ASes

intra-AS
3c
routing3a inter-AS routing intra-AS
2c
3b 2a routing
2b
1c
intra-AS
AS3
1a routing 1b AS2
1d
AS1

intra-AS (aka “intra-domain”): routing among routers within same

AS (“network”)
inter-AS (aka “inter-domain”): routing among AS’es
Network Layer Control Plane: 5-61
Internet inter-AS routing: BGP
▪ BGP (Border Gateway Protocol): the de facto inter-domain routing
protocol
• “glue that holds the Internet together”
▪ allows subnet to advertise its existence, and the destinations it can
reach, to rest of Internet: “I am here, here is who I can reach, and how”
▪ BGP provides each AS a means to:
• obtain destination network reachability info from neighboring ASes
(eBGP)
• determine routes to other networks based on reachability information
and policy
• propagate reachability information to all AS-internal routers (iBGP)
• advertise (to neighboring networks) destination reachability info
Network Layer Control Plane: 5-62
BGP protocol messages
▪ BGP messages exchanged between peers over TCP connection
▪ BGP messages [RFC 4371]:
• 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
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-64

BGP path advertisement
AS 3 3b
AS 1 1b 3a 3c
1a 1c AS 2 3d X
2b
1d AS3, X
AS2,AS3,X 2a 2c

2d

▪ AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3 router 3a
▪ based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates (via iBGP) to all
AS2 routers
▪ based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2, AS3, X to
AS1 router 1c
Network Layer: 5-65
BGP path advertisement: multiple paths
AS 3 3b
AS 1 1b AS3,X 3a 3c
AS3,X
AS3,X
1a 1c AS 2 3d X
2b
AS3,X
1d AS3, X
AS2,AS3,X 2a 2c

2d

gateway router may learn about multiple paths to destination:

▪ AS1 gateway router 1c learns path AS2,AS3,X from 2a
▪ AS1 gateway router 1c learns path AS3,X from 3a
▪ based on policy, AS1 gateway router 1c chooses path AS3,X and advertises path
within AS1 via iBGP
Network Layer: 5-66
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-67

 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP
▪ SDN control plane
▪ Internet Control Message ▪ network management,
Protocol configuration
• SNMP
• NETCONF/YANG

Network Layer: 5-68

 Network layer: “control plane” roadmap
▪ introduction
▪ routing protocols
▪ intra-ISP routing: OSPF
▪ routing among ISPs: BGP
▪ SDN control plane
▪ Internet Control Message ▪ network management,
Protocol configuration
• SNMP
• NETCONF/YANG

Network Layer: 5-69

ICMP: internet control message protocol
▪ used by hosts and routers to
Type Code description
communicate network-level 0 0 echo reply (ping)
information 3 0 dest. network unreachable
3 1 dest host unreachable
• error reporting: unreachable host, 3 2 dest protocol unreachable
network, port, protocol 3 3 dest port unreachable
• echo request/reply (used by ping) 3 6 dest network unknown
3 7 dest host unknown
▪ network-layer “above” IP: 4 0 source quench (congestion
• ICMP messages carried in IP control - not used)
8 0 echo request (ping)
datagrams 9 0 route advertisement
▪ ICMP message: type, code plus 10
11
0
0
router discovery
TTL expired
first 8 bytes of IP datagram causing 12 0 bad IP header
error
Network Layer: 4-70
Traceroute and ICMP
3 probes 3 probes

3 probes

▪ source sends sets of UDP segments to

stopping criteria:
destination
▪ UDP segment eventually
• 1st set has TTL =1, 2nd set has TTL=2, etc. arrives at destination host
▪ datagram in nth set arrives to nth router: ▪ destination returns ICMP
• router discards datagram and sends source “port unreachable”
ICMP message (type 11, code 0) message (type 3, code 3)
• ICMP message possibly includes name of ▪ source stops
router & IP address
▪ when ICMP message arrives at source: record RTTs
Network Layer: 4-71
 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-72
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."

Network Layer: 5-73

 Components of network management
Managed device:
Managing server: agent data equipment with manageable,
application, typically managing configurable hardware,
with network server/controller software components
managers (humans) in data managed device
the loop Data: device “state”
agent data configuration data,
Network agent data
operational data,
management managed device device statistics
protocol: used by managed device
managing server to query,
agent data
configure, manage device;
used by devices to inform agent data

managing server of data, managed device

events. managed device

Network Layer: 5-74

Network operator approaches to management
CLI (Command Line Interface)
• operator issues (types, scripts) direct to agent data
individual devices (e.g., vis ssh) managing
server/controller
SNMP/MIB data managed device

• operator queries/sets devices data

(MIB) using Simple Network agent data
Management Protocol (SNMP)
agent data
managed device
NETCONF/YANG managed device
• more abstract, network-wide, holistic
• emphasis on multi-device configuration agent data

management. agent data

• YANG: data modeling language managed device
• NETCONF: communicate YANG-compatible managed device

actions/data to/from/among remote devices

Network Layer: 5-75
Distance vector: another example
cost to cost to
Dx() x y z x y z
x 0 2 7 x 0 2 3

from
y ∞∞ ∞ y 2 0 1
from

Dx(z) = min{cx,y+ Dy(z), cx,z+ Dz(z)}

z ∞∞ ∞ z 7 1 0
= min{2+1 , 7+0} = 3

cost to y
Dy() x y z 2 1
Dx(y) = min{cx,y + Dy(y), cx,z+ Dz(y)}
x ∞ ∞ ∞ = min{2+0 , 7+1} = 2 x z
7
from

y 2 0 1
z ∞∞ ∞

cost to
Dz() x y z
x ∞∞ ∞
from

y ∞∞ ∞
z 7 1 0
time Network Layer: 5-76
Distance vector: another example
cost to cost to
Dx() x y z x y z
cost to
x y z
x 0 2 7 x 0 2 3 x 0 2 3

from
y ∞∞ ∞ y 2 0 1
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0

cost to cost to cost to y

Dy() x y z x y z x y z 2 1
x ∞ ∞ ∞ x 0 2 7 x 0 2 3
x z
7
from

y 2 0 1 y 2 0 1
from
y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0

cost to cost to cost to

Dz() x y z x y z x y z
x ∞∞ ∞ x 0 2 7 x 0 2 3
from

from
y 2 0 1 y 2 0 1
from

y ∞∞ ∞
z 7 1 0 z 3 1 0 z 3 1 0
time Network Layer: 5-77