Bài giảng Mạng máy tính - Chapter 5: Network layer - The control plane - Nguyễn Lê Duy Lai
Computer Networks
Lectured by:
Nguyen Le Duy Lai
(lai@hcmut.edu.vn)
Computer
Networking: A Top
Down Approach
7th Edition, Global Edition
Jim Kurose, Keith Ross
Pearson
April 2016
Network Layer: The Control Plane 5-1
Chapter 5
Network Layer:
The Control Plane
Computer
Networking: A Top
Down Approach
7th Edition, Global Edition
Jim Kurose, Keith Ross
Pearson
April 2016
Network Layer: Control Plane 5-2
Chapter 5: network layer control plane
chapter goals: understand principles behind network
control plane
▪ traditional routing algorithms
▪ SDN controllers
▪ Internet Control Message Protocol (ICMP)
▪ network management
and their instantiation, implementation in the Internet:
• OSPF, BGP
• OpenFlow, ODL and ONOS controllers
• ICMP, SNMP
Network Layer: Control Plane 5-3
Chapter 5: outline
5.1 introduction
5.2 routing protocols
▪ link state
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
▪ distance vector
5.7 Network management
and SNMP
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
Network Layer: Control Plane 5-4
Network-layer functions
Recall: two network-layer functions:
▪ forwarding: move packets
data plane
from router’s input to
appropriate router output
▪ 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: Control Plane 5-5
Per-router control plane
Individual routing algorithm components in each and every
router interact with each other in control plane to compute
forwarding tables
Routing
Algorithm
control
plane
data
plane
Network Layer: Control Plane 5-6
Logically centralized control plane
A distinct (typically remote) controller interacts with local
control agents (CAs) in routers to compute forwarding tables
Remote Controller
control
plane
data
plane
CA
CA
CA
CA
CA
Network Layer: Control Plane 5-7
Chapter 5: outline
5.1 introduction
5.2 routing protocols
▪ link state
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
▪ distance vector
5.7 Network management
and SNMP
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
Network Layer: Control Plane 5-8
Routing protocols
Routing protocol goal: determine “good” paths
(equivalently, routes), from sending hosts to
receiving host, through network of routers
▪ path: sequence of routers that packets will
traverse in going from given initial source host to
given final destination host
▪ “good”: least “cost”, “fastest”, “least congested”
▪ routing: a “top-10” networking challenge!
Network Layer: Control Plane 5-9
Graph abstraction of the network
5
3
v
w
5
2
u
z
2
1
3
1
2
x
y
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) }
aside: graph abstraction is also useful in other network contexts (e.g., P2P,
where N is set of peers and E is set of TCP connections)
Network Layer: Control Plane 5-10
Graph abstraction: costs
5
c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
3
v
w
5
2
cost could always be 1 (hop count),
or inversely related to bandwidth,
or inversely related to congestion
u
2
z
1
3
1
2
x
y
1
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
key question: what is the least-cost path between u and z?
routing algorithm: algorithm finds that least cost path
Network Layer: Control Plane 5-11
Routing algorithm classification
Q: static or dynamic?
static:
▪ routes change slowly over
time
dynamic:
Q: global or decentralized
information?
global:
▪ all routers have the complete
topology, link cost info
▪ “link state” algorithms
▪ routes change more
decentralized:
quickly
▪ router knows physically-
connected neighbors, link costs
to neighbors
• periodic update in
response to link cost
changes
▪ iterative process of
computation, exchange of
info with neighbors
▪ “distance vector” algorithms
Network Layer: Control Plane 5-12
Chapter 5: outline
5.1 introduction
5.2 routing protocols
▪ link state
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
▪ distance vector
5.7 Network management
and SNMP
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
Network Layer: Control Plane 5-13
A link-state routing algorithm
Dijkstra’s algorithm
notation:
▪ c(x,y): link cost from
node x to y; = ∞ if not
direct neighbors
▪ D(v): current value of
cost of path from source
to destination v
▪ p(v): predecessor node
along path from source
to destination v
▪ net 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
▪ N': set of nodes whose
least cost path
▪ iterative: after k
definitively known
iterations, know least cost
path to k destinations
Network Layer: Control Plane 5-14
Dijsktra’s algorithm
1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v adjacent to u
5
then D(v) = c(u,v)
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) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N'
Network Layer: Control Plane 5-15
Dijkstra’s algorithm: example (1)
D(v),
D(w), D(x), D(y),
D(z),
p(v)
p(w) p(x) p(y)
Step
p(z)
N'
u
uw
∞
11,w
∞
∞
3,u 5,u
7,u
6,w
6,w
0
1
2
3
4
5,u
uwx
uwxv
uwxvy
11,w 14,x
10,v 14,x
12,y
x
uwxvyz
5
9
7
5
7
notes:
4
❖ construct shortest path tree by
8
tracing predecessor nodes
3
w
v
❖ ties can exist (can be broken
z
y
u
2
arbitrarily)
3
4
Network Layer: Control Plane 5-16
Dijkstra’s algorithm: example (2)
D(v),p(v)
2,u
D(x),p(x)
1,u
D(w),p(w)
5,u
D(y),p(y)
Step
N'
u
D(z),p(z)
∞
∞
∞
0
1
2
3
4
5
2,u
4,x
2,x
ux
4,y
4,y
4,y
2,u
3,y
3,y
uxy
uxyv
uxyvw
uxyvwz
5
3
v
w
5
z
2
2
u
2
1
3
1
x
y
1
* Check out the online interactive exercises for more
Network Layer: Control Plane 5-17
Dijkstra’s algorithm: example (2)
resulting shortest-path tree from u:
v
w
u
z
x
y
resulting forwarding table in u:
destination
link
(u,v)
(u,x)
v
x
y
w
z
(u,x)
(u,x)
(u,x)
Network Layer: Control Plane 5-18
Dijkstra’s algorithm, discussion
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)
oscillations possible:
▪ e.g., support link cost equals amount of carried traffic:
A
C
A
A
A
1
1+e
2+e
D
2+e
D
0
2+e
0
0
D
D
B
B
B
B
0
0
1
1
1+e
1+e
0
0
e
0
0
0
0
1
0
1+e
C
C
C
1
1
e
given these costs,
find new routing….
resulting in new costs
given these costs,
given these costs,
initially
find new routing…. find new routing….
resulting in new costs resulting in new costs
Network Layer: Control Plane 5-19
Chapter 5: outline
5.1 introduction
5.2 routing protocols
▪ link state
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
▪ distance vector
5.7 Network management
and SNMP
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
Network Layer: Control Plane 5-20
Tải về để xem bản đầy đủ
88 trang
11780
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính - Chapter 5: Network layer - The control plane - Nguyễn Lê Duy Lai", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mang_may_tinh_chapter_5_network_layer_the_control.pdf
