CS118 Discussion Week 7: The Network Layer (Control Plane)
Questions?
• From this week or about the HW/Midterm
This week
• Review the two main types of traditional routing algorithms • Dijkastra’s/Link-State
• Bellman-Ford/Distance-Vector
• Vagrant/Mininet Tutorial
The Network Layer (The Control Plane)
• Two Key Features to the Network Layer as a whole:
• Forwarding (move packets from a router’s input link to appropriate router
output link)
• Routing (determine route taken by packets from source to destination)
Two approaches to structuring network control plane:
• per-router control (traditional)
• logically centralized control (software defined networking)
• Can anyone give some guesses as to advantages/disadvantages?
1/21/2021 4
Per-router control plane
Individual routing algorithm components in each and every router interact in the control plane – aka each router runs something like Dijkstra’s
values in arriving packet header
0111
1
Routing Algorithm
control plane
data plane
3
2
Network Layer: 5-5
Software-Defined Networking (SDN) control plane
Remote controller computes, installs forwarding tables in routers
control plane
data plane
values in arriving packet header
Remote Controller
CA
CA
CA
CA
CA
0111
3
1
2
Network Layer: 5-6
What is a Routing Protocol?
• The purpose of a routing protocol is to find a ‘good’ (where good can mean least cost, fewest hops, least congested, etc) path from the sender to receiver, through the network.
• The path is the sequence of routers the packet traverses on this journey.
• Non-trivial problem!
Formalizing the Problem
• Definitions: A graph G(V, E) is composed of a set V or vertices and a set E of edges between these vertices. Let e(v1, v2) denote the presence of an edge between vertices v1 and v2. Each edge e in E has a weight w(e). Let distG(v1, v2) denote the length of the shortest path between vertices v1 and v2 in the graph
• The problem, then, is finding the path with value distG(v1, v2) for each pair of nodes/vertices.
• This is the simple version of the problem, where we don’t worry about anything like ‘this type of packet must go along this route’.
Routing algorithm classification
How fast do routes change?
global: all routers have complete topology, link cost info
• “link state” algorithms static: routes change
dynamic: routes change more quickly
• periodic updates or in response to link cost changes
slowly over time
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-9
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-10
Dijkstra’s algorithm: an example
5 v3w5
231z x1y2
resulting forwarding table in u:
route from u to v directly
route from u to all other destinations via x
u2 1
resulting least-cost-path tree from u:
destination
outgoing link
vx
wy x
(u,v) (u,x) (u,x) (u,x) (u,x)
vw u
z xy
Network Layer: 5-11
Dijkstra’s algorithm: discussion
Alg Complexity: n nodes
each of n iteration: need to check all nodes not already in the completed set n(n+1)/2 comparisons: O(n2) complexity (where n is the number of nodes)
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-12
Distance Vector Routing
• Key idea is that each node communicates with each other, sending their own distance vector estimates to neighbors
when x receives new DV estimate from any neighbor, it updates its own DV using Bellman-Ford equation:
min taken over all neighbors v of x
D (y) ← min {c + D (y)} for each node y ∊ N x vx,vv
direct cost of link from x to v
v’s estimated least-cost-path cost to y
under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y)
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-14
Distance Vector Discussion
Distance vector: example
DV in a:
Da(a)=0 Da(b) = 8 Da(c) = ∞ Da(d) = 1 Da(e) = ∞ Da(f) = ∞ Da(g) = ∞ Da(h) = ∞ Da(i) = ∞
a
81 1
1
1
g
b
e
h
c
f
i
t=0
All nodes have distance estimates to nearest neighbors (only)
All nodes send their local
distance vector to their neighbors
1
1 11
11
A few asymmetries: missing link
larger cost
d
Network Layer: 5-16
Distance vector example: iteration
a
d
81 1
1
1
g
b
e
h
c
f
i
t=1
All nodes:
receive distance
vectors from
neighbors
compute their new local distance vector
send their new local distance vector to neighbors
1
1 11
11
Network Layer: 5-17
Distance vector example: iteration
t=1
All nodes:
receive distance vectors from neighbors
compute their new local distance vector
send their new local distance vector to neighbors
a compute compute compute 8 b 1 c
11
d
1 comfpute 111
compute
1 comepute
g
compute 1 comhpute 1 comipute
Network Layer: 5-18
Distance vector example: iteration
a
d
81 1
1
1
g
b
e
h
c
f
i
t=1
All nodes:
receive distance vectors from neighbors
compute their new local distance vector
send their new local distance vector to neighbors
1
1 11
11
Network Layer: 5-19
Distance vector example: iteration
a
d
81 1
1
1
g
b
e
h
c
f
i
t=2
All nodes:
receive distance
vectors from
neighbors
compute their new local distance vector
send their new local distance vector to neighbors
1
1 11
11
Network Layer: 5-20
Distance vector example: iteration
compute compute compute
a
t=2
All nodes:
receive distance vectors from neighbors
compute their new local distance vector
send their new local distance vector to neighbors
2b1c 11
compute
compute
comdpute 111
g compute compute compute 8 h 1 i
1e1f
Network Layer: 5-21
Distance vector example: iteration
a
d
81 1
1
1
g
b
e
h
c
f
i
t=2
All nodes:
receive distance vectors from neighbors
compute their new local distance vector
send their new local distance vector to neighbors
1
1 11
11
Network Layer: 5-22
Distance vector example: iteration
…. and so on
Let’s next take a look at the iterative computations at nodes
Network Layer: 5-23
Distance vector example:
DV in a:
Da(a)=0 Da(b) = 8 Da(c) = ∞ Da(d) = 1 Da(e) = ∞ Da(f) = ∞ Da(g) = ∞ Da(h) = ∞ Da(i) = ∞
a
b
computation
c
DV in c:
DV in b:
Db(a) = 8 Db(c) = 1 Db(d) = ∞ Db(e) = 1
Db(f) = ∞ Db(g) = ∞ Db(h) = ∞ Db(i) = ∞
Dc(a) = ∞ Dc(b) = 1 Dc(c) = 0 Dc(d) = ∞ Dc(e) = ∞ Dc(f) = ∞ Dc(g) = ∞ Dc(h) = ∞ Dc(i) = ∞
8
1
e
1
d
DV in e:
De(a) = ∞ De(b) = 1 De(c) = ∞ De(d) = 1 De(e) = 0 De(f) = 1 De(g) = ∞ De(h) = 1 De(i) = ∞
g
1
1
h
1
1
f
i
t=1
b receives DVs from a, c, e
1
1
11
Network Layer: 5-24
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-25
Mininet and Vagrant