Chapter 4
Network Layer:
The Data 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: Computer
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!)
Networking: A Top
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
Down Approach
material.
7th edition
Thanks and enjoy! JFK/KWR
Jim Kurose, Keith Ross
All material copyright 1996-2016 Pearson/Addison Wesley
J.F Kurose and K.W. Ross, All Rights Reserved April 2016
Network Layer: Data 4-1
Plane
Chapter 4: outline
4.4 Generalized
4.1 Overview of Forward and SDN
Network
• match layer
• data
actionplane
• control
OpenFlowplane
examples of match-plus-action in
4.2 What’s
action inside a
router
4.3 IP: Internet Protocol
• datagram format
• fragmentation
• IPv4 addressing
• network address
translation
• IPv6
Network Layer: Data 4-2
Plane
Chapter 4: network layer
chapter goals:
understand principles behind network
layer services, focusing on data plane:
• network layer service models
• forwarding versus routing
• how a router works
• generalized forwarding
instantiation, implementation in the
Internet
Network Layer: Data 4-3
Plane
Network layer
transport segment
application
transport
network
from sending to data link
physical
network
receiving host
network
data link data link
network physical
physical
on sending side
data link
physical network network
data link data link
encapsulates physical physical
segments into network
data link
network
data link
datagrams physical
network
data link
physical
on receiving side, physical
application
delivers segments to network
data link
physical
network
transport
network
transport layer
network data link data link
data link physical physical
physical
network layer
protocols in every
host, router
router examines Network Layer: Data 4-4
Plane
Two key network-layer
functions
network-layer analogy: taking a trip
functions: forwarding: process
forwarding: move of getting through
packets from router’s single interchange
input to appropriate
router output routing: process of
routing: determine planning trip from
route taken by source to
packets from source destination
to destination
• routing algorithms
Network Layer: Data 4-5
Plane
Network layer: data plane, control
plane
Data plane Control plane
local, per-router network-wide logic
function determines how datagram
determines how is routed among routers
datagram arriving on along end-end path from
router input port is source host to destination
forwarded to router host
output port two control-plane
values
forwarding
in arriving function approaches:
packet header
• traditional routing
0111 1 algorithms:
3
2 implemented in routers
• software-defined
networking (SDN):
implemented in Layer: Data 4-6
Network
Plane
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: Control 5-7
Plane
Logically centralized control plane
A distinct (typically remote) controller interacts with local
control agents (CAs)
Remote Controller
control
plane
data
plane
CA
CA CA CA CA
values in arriving
packet header
0111 1
2
3
Network Layer: Control 5-8
Plane
Chapter 4: outline
4.4 Generalized
4.1 Overview of Forward and SDN
Network
• match layer
• data
actionplane
• control
OpenFlowplane
examples of match-plus-action in
4.2 What’s
action inside a
router
4.3 IP: Internet Protocol
• datagram format
• fragmentation
• IPv4 addressing
• network address
translation
• IPv6
Network Layer: Data 4-9
Plane
Router architecture overview
high-level view of generic router
architecture:
Might be different link
layers on input and routing, management
output sides control plane (software)
routing
processor operates in millisecond
time frame
forwarding data plane
(hardware) operates
in nanosecond
timeframe
high-seed
switching
fabric
router input ports router output ports
Network Layer: Data 4-10
Plane
Input port functions
lookup,
link forwarding
line layer switch
termination protocol fabric
(receive)
queueing
physical layer:
bit-level reception
data link layer: decentralized switching:
e.g., Ethernet using header field values, lookup
see chapter 5 output port using forwarding table
in input port memory (“match plus
action”)
goal: complete input port
processing at ‘line speed’
queuing: if datagrams arrive faster
than forwarding rate into switch
Network Layer: Data 4-11
Plane
Input port functions
lookup,
link forwarding
line layer switch
termination protocol fabric
(receive)
queueing
physical layer:
bit-level reception
decentralized switching:
data link layer: using header field values, lookup
e.g., Ethernet output port using forwarding table
see chapter 5 in input port memory (“match plus
action”)
destination-based forwarding:
forward based only on destination
IP address (traditional)
generalized forwarding: forward
based on any set of header field
Network Layer: Data 4-12
Plane
Destination-based
forwarding
forwarding table
Destination Address Range Link Interface
11001000 00010111 00010000 00000000
through 0
11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000
through 1
11001000 00010111 00011000 11111111
11001000 00010111 00011001 00000000
through 2
11001000 00010111 00011111 11111111
otherwise 3
: but what happens if ranges don’t divide up so nicely?
Network Layer: Data 4-13
Plane
Longest prefix matching
longest prefix matching
when looking for forwarding table entry
for given destination address, use longest
address prefix that matches destination
address.
Destination Address Range Link interface
11001000 00010111 00010*** ********* 0
11001000 00010111 00011000 ********* 1
11001000 00010111 00011*** ********* 2
otherwise 3
examples:
DA: 11001000 00010111 00010110 10100001 which interface?
DA: 11001000 00010111 00011000 10101010 which interface?
Network Layer: Data 4-14
Plane
Switching fabrics
transfer packet from input buffer to
appropriate output buffer
switching rate: rate at which packets
can be transfer from inputs to outputs
• often measured as multiple of input/output line rate
• N inputs: switching rate N times line rate desirable
three types of switching fabrics
memory
memory bus crossbar
Network Layer: Data 4-15
Plane
Switching via memory
first generation routers:
traditional computers with switching under
direct control of CPU
packet copied to system’s memory
speed limited by memory bandwidth (2 bus
crossings per datagram)
input output
port memory port
(e.g., (e.g.,
Ethernet) Ethernet)
system bus
Network Layer: Data 4-16
Plane
Switching via a bus
datagram from input port
memory
to output port memory via
a shared bus
bus contention: switching
speed limited by bus
bus
bandwidth
32 Gbps bus, Cisco 5600:
sufficient speed for access
and enterprise routers
Network Layer: Data 4-17
Plane
Switching via interconnection
network
overcome bus bandwidth
limitations
banyan networks, crossbar,
other interconnection nets
initially developed to connect
processors in multiprocessor
vertical bus interact crossbar
horizontal bus at a crosspoint,
which can be opened or
closed by the switch fabric
controller
Cisco 12000: switches 60
Gbps through the
interconnection network Network Layer: Data 4-18
Plane
Input port queuing
fabric slower than input ports combined ->
queueing may occur at input queues
• queueing delay and loss due to input buffer
overflow!
Head-of-the-Line (HOL) blocking: queued
datagram at front of queue prevents others in
queue from moving forward
switch switch
fabric fabric
output port contention: one packet time
only one red datagram can later: green
be transferred. packet
lower red packet is blocked experiences HOL
blocking
Network Layer: Data 4-19
Plane
Output ports This slide in HUGELY important!
datagram
switch buffer link
fabric layer line
protocol termination
queueing (send)
buffering required when (packets)
Datagram datagramscan be
arrive from fabriclost faster than thelack of
due to congestion,
transmission rate buffers
schedulingPriority
discipline chooses
scheduling – who gets best
among queued datagrams
performance, networkfor
neutrality
transmission Network Layer: Data 4-20
Plane
Output port queueing
switch
switch
fabric
fabric
at t, packets more one packet time later
from input to output
buffering when arrival rate via switch
exceeds output line speed
queueing (delay) and loss due to output
port buffer overflow!
Network Layer: Data 4-21
Plane
Scheduling mechanisms
scheduling: choose next packet to send on
link
FIFO (first in first out) scheduling: send in
order of arrival to queue
• real-world example?
• discard policy: if packet arrives to full queue:
who to discard?
• tail drop: drop arriving packet
• priority: drop/remove on priority basis
• random: drop/remove randomly
packet packet
arrivals queue link departures
(waiting area) (server)
Network Layer: Data 4-22
Plane
Scheduling policies:
priority
high priority queue
priority scheduling: (waiting area)
send highest arrivals departures
priority queued
packet classify link
multiple classes, low priority queue
(server)
with different (waiting area)
priorities 2
1 3 4 5
• class may depend arrivals
on marking or
packet
other header info, in 1 3 2 4 5
service
e.g. IP
source/dest, port departures
numbers, etc. 1 3 2 4 5
• real world
example?
Network Layer: Data 4-23
Plane
Scheduling policies: still
more
Round Robin (RR) scheduling:
multiple classes
cyclically scan class queues, sending
one complete packet from each class (if
available)
real world example?
2
1 3 4 5
arrivals
packet
in 1 3 2 4 5
service
departures
1 3 3 4 5
Network Layer: Data 4-24
Plane
Scheduling policies: still
more
Weighted Fair Queuing (WFQ):
generalized Round Robin
each class gets weighted amount of
service in each cycle
real-world example?
Network Layer: Data 4-25
Plane