Chapter_4 v 7 network layer Dr. Yaser.ppt

layer

1. Computer
Networking: A Top
Down Approach
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:
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!)
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
material.
Thanks and enjoy! JFK/KWR
All material copyright 1996-2016
J.F Kurose and K.W. Ross, All Rights Reserved
7
th
edition
Jim Kurose, Keith Ross
Pearson/Addison Wesley
April 2016
Chapter 4
Network Layer:
The Data Plane
4-1Network Layer: Data Plane

2. 4.1 Overview of Network
layer
•data plane
•control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
•datagram format
•fragmentation
•IPv4 addressing
•network address
translation
•IPv6
4.4 Generalized Forward and
SDN
•match
•action
•OpenFlow examples
of match-plus-action in
action
Chapter 4: outline
4-2Network Layer: Data Plane

3. 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
4-3Network Layer: Data Plane

4. Network layer
transport segment from
sending to receiving host
on sending side
encapsulates segments
into datagrams
on receiving side, delivers
segments to transport
layer
network layer protocols in
every host, router
router examines header
fields in all IP datagrams
passing through it
application
transport
network
data link
physical
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
4-4Network Layer: Data Plane

5. Two key network-layer functions
Network-layer functions:
Forwarding: (local in router)move
packets from router’s input
to appropriate router output
Routing(global): determine
route taken by packets from
source to destination
•routing algorithms
Analogy: taking a trip
Forwarding: process
of getting through
single interchange
Routing: process of
planning trip from
source to destination
4-5Network Layer: Data Plane

6. Network layer: data plane, control plane
Data plane(
رتوارلا لخاد
)
local, per-router function
determines how datagram
arriving on router input port
is forwarded to router
output port
forwarding function
Control plane(
زرتوارلا نيب
)
network-wide logic
determines how datagram is routed
among routers along end2end path
from source host to destination host
two control-plane approaches:
•traditional routing algorithms:
implemented in routers (douting
tables)
•software-defined networking
(SDN):
implemented in (remote) servers
(cloud)
1
2
3
0111
values in arriving
packet header
4-6Network Layer: Data Plane

7. Per-router control plane
Individual routing algorithm components in each
and every router interact in the control plane
5-7Network Layer: Control
Plane
Routing
Algorithm
data
plane
control
plane
1
2
0111
values in arriving
packet header
3
Port address is 16 bit
Control plane is the
logic that control
forwarding behavior
like routing protocol
( like OSPF, BGP, RIP)
Data plane is
forwarding packets
according to
Control plane
Why separate?
For better network
mangmnt, for
software control
and debugging
like security
magmnt

8. data
plane
control
plane
Logically centralized control plane
A distinct (typically remote) controller interacts with local
control agents (CAs)
Remote Controller
CA
CA CA CA CA
5-8Network Layer: Control
Plane
1
2
0111
3
values in arriving
packet header

9. Network service model
Q: What service model for “channel” transporting
datagrams from sender to receiver?
example services for
individual datagrams:
guaranteed delivery
guaranteed delivery with
less than 40 msec delay
example services for a flow
of datagrams:
in-order datagram delivery
guaranteed minimum
bandwidth to flow
restrictions on changes in
inter-packet spacing
4-9Network Layer: Data Plane
before datagrams flow, two end hosts and intervening routers establish virtual
connection → routers get involved
network vs transport layer connection service:
network: between two hosts (may also involve intervening routers in case of
VCs)
transport: between two processes

10. Network layer service models:
Network
Architecture
Internet
ATM
ATM
ATM
ATM
Service
Model
best effort
CBR
VBR
ABR
UBR
Bandwidth
none
constant
rate
guaranteed
rate
guaranteed
minimum
none
Loss
no
yes
yes
no
no
Order
no
yes
yes
yes
yes
Timing
no
yes
yes
no
no
Congestion
feedback
no (inferred
via loss)
no
congestion
no
congestion
yes
no
Guarantees ?
4-10Network Layer: Data Plane

11. 4.1 Overview of Network
layer
•data plane
•control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
•datagram format
•fragmentation
•IPv4 addressing
•network address
translation
•IPv6
4.4 Generalized Forward and
SDN
•match
•action
•OpenFlow examples
of match-plus-action in
action
Chapter 4: outline
4-11Network Layer: Data Plane

12. Router architecture overview
high-seed
switching
fabric
routing
processor
router input ports router output ports
forwarding data plane
(hardware) operttes
in nanosecond
timeframe
routing, management
control plane (software)
operates in millisecond
time frame
high-level view of generic router architecture:
4-12Network Layer: Data Plane
SDN is the merge of
data and control plane

13. line
termination
link
layer
protocol
(receive)
lookup,
forwarding
queueing
Input port functions
decentralized switching:
using header field values, lookup 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 fabric
physical layer:
bit-level reception
data link layer:
e.g., Ethernet
see chapter 5
switch
fabric
4-13Network Layer: Data Plane

14. line
termination
link
layer
protocol
(receive)
lookup,
forwarding
queueing
Input port functions
decentralized switching:
using header field values, lookup output port
using forwarding table 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 values
physical layer:
bit-level reception
data link layer:
e.g., Ethernet
see chapter 5
switch
fabric
4-14Network Layer: Data Plane

15. Q: but what happens if ranges don’t divide up so nicely?
Destination-based forwarding
Link
Interface
0
1
2
3
Destination Address Range
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
otherwise
forwarding table
4-15Network Layer: Data Plane
200.23.16.0
-200 . 23.23.255
200.23.24.0
-200 . 23.24.255
200.23.25.0
-200 . 23.31.255

16. Longest prefix matching
DA: 11001000 00010111 00011000 10101010
examples:
DA: 11001000 00010111 00010110 10100001 which interface?->0
which interface?->1
when looking for forwarding table entry for given
destination address, use longest address prefix that
matches destination address.
longest prefix matching
Destination Address Range
11001000 00010111 00010*** *********
11001000 00010111 00011000 *********
11001000 00010111 00011*** *********
otherwise
Link interface
0
1
2
3
4-16Network Layer: Data Plane
200.23.
200.23.24
200.23.

17. Longest prefix matching
we’ll see why longest prefix matching is used
shortly, when we study addressing
longest prefix matching: often performed using
ternary content addressable memories (TCAMs)
•content addressable: present address to TCAM: retrieve
address in one clock cycle, regardless of table size
•Cisco Catalyst: can up ~1M routing table entries in
TCAM
4-17Network Layer: Data Plane

18. 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
4-18Network Layer: Data Plane

19. 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
port
(e.g.,
Ethernet)
memory
output
port
(e.g.,
Ethernet)
system bus
4-19Network Layer: Data Plane

20. Switching via a bus
datagram from input port memory
to output port memory via a
shared bus
bus contention: switching speed
limited by bus bandwidth
32 Gbps bus, Cisco 5600: sufficient
speed for access and enterprise
routers
Each packet must cross the bus
one time
bus
4-20Network Layer: Data Plane

21. Switching via interconnection network
overcome bus bandwidth limitations
banyan networks, crossbar, other
interconnection nets initially
developed to connect processors in
multiprocessor
advanced design: fragmenting
datagram into fixed length cells,
switch cells through the fabric.
Cisco 12000: switches 60 Gbps
through the interconnection network
crossbar
4-21Network Layer: Data Plane

22. 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
output port contention:
only one red datagram can be
transferred.
lower red packet is blocked
switch
fabric
one packet time later:
green packet
experiences HOL
blocking
switch
fabric
4-22Network Layer: Data Plane

23. Output ports
buffering required when datagrams arrive from fabric faster than the
transmission rate
scheduling discipline chooses among queued datagrams for transmission
line
termination
link
layer
protocol
(send)
switch
fabric
datagram
buffer
queueing
This slide in HUGELY important!
Datagram (packets) can be lost
due to congestion, lack of
buffers
Priority scheduling – who gets best
performance, network neutrality`
4-23Network Layer: Data Plane

24. Output port queueing
buffering when arrival rate via switch exceeds output line
speed
queueing (delay) and loss due to output port buffer overflow!
at t, packets more
from input to output
one packet time later
switch
fabric
switch
fabric
4-24Network Layer: Data Plane

25. How much buffering?
RFC 3439 rule of thumb: average buffering equal
to “typical” RTT (say 250 msec) times link
capacity C
•e.g., C = 10 Gpbs link: 2.5 Gbit buffer
recent recommendation: with N flows, buffering
equal to
2.5*10G/√4=125Gbit
RTT C.
N
4-25Network Layer: Data Plane

26. 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
queue
(waiting area)
packet
arrivals
packet
departureslink
(server)
4-26Network Layer: Data Plane

27. Scheduling policies: priority
priority scheduling: send
highest priority
queued packet
multiple classes, with
different priorities
•class may depend on
marking or other
header info, e.g. IP
source/dest, port
numbers, etc.
•real world example?
high priority queue
(waiting area)
low priority queue
(waiting area)
arrivals
classify
departures
link
(server)
1324 5
5
5
2
2
1
1
3
3 4
4
arrivals
departures
packet
in
service
4-27Network Layer: Data Plane

28. 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?
1 23 4 5
5
5
2
3
1
1
3
34
4
arrivals
departures
packet
in
service
4-28Network Layer: Data Plane

29. Weighted Fair Queuing (WFQ):
generalized Round Robin
each class gets weighted amount of service in
each cycle
real-world example?
Scheduling policies: still more
4-29Network Layer: Data Plane

30. 4.1 Overview of Network
layer
•data plane
•control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
•datagram format
•fragmentation
•IPv4 addressing
•network address
translation
•IPv6
4.4 Generalized Forward and
SDN
•match
•action
•OpenFlow examples
of match-plus-action in
action

Chapter 4: outline
4-30Network Layer: Data Plane

31. The Internet network layer
forwarding
table
host, router network layer functions:
routing protocols
• path selection
• RIP, OSPF, BGP
IP protocol
• addressing conventions
• datagram format
• packet handling conventions
ICMP protocol
• error reporting
• router “signaling”
transport layer: TCP, UDP
link layer
physical layer
network
layer
4-31Network Layer: Data Plane
RIP(Routing Information Protocol)
OSPF(Open Shortest Path First )
BGP(Border Gateway Protocol)
ICMP(Internet control messaging protocol)

32. Network Layer 4-32
IP datagram format
header length
(bytes)=20
≈datagram width(32/8)*5 items(blue levels) for
fragmentation/
reassembly
e.g. timestamp,
record route
taken, specify
list of routers
to visit.
how much overhead?
20 bytes of TCP
20 bytes of IP
= 40 bytes + app
layer overhead
ver
length
32 bits
data
(variable length,
typically a TCP
or UDP segment)
16-bit identifier
header
checksum
time to
live
32 bit source IP address
head.
len
type of
service
flgs
fragment
offset
upper
layer
32 bit destination IP address
options (if any)
IP protocol version
Number V4
upper layer protocol
to deliver payload to
total datagram
length (bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
datagram width(32/8)=4
header length
IP v6 IP v6 (bytes)=40 &
no fragmentation

33. IP fragmentation, reassembly
network links have MTU
(max.transfer size) -
largest possible link-level
frame
•different link types,
different MTUs
large IP datagram divided (
“fragmented”) within net
•one datagram becomes
several datagrams
•“reassembled” only at
final destination
•IP header bits used to
identify, order related
fragments
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
…
…
4-33Network Layer: Data Plane

34. Network Layer
4-34
ID
=x
offset
=0
fragflag
=0
length
=4000
ID
=x
offset
=0
fragflag
=1
length
=1500
ID
=x
offset
=1480/8=185
fragflag
=1
length
=1500
ID
=x
offset
=370=185*2
fragflag
=0
length
=1040
one large datagram becomes
several smaller datagrams
example:
4000 byte datagram
MTU = 1500 bytes
1480+20 header(4BYTE*5SEGMENTS)=1480 bytes in
data field
offset(DATA field/8) =
1480/8
IP fragmentation, reassembly
fragflag=1ةريخلاا تسيل
fragflag= مارجاتادلا
0ةريخلاا نشيتنمجرف

35. 4.1 Overview of Network
layer
•data plane
•control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
•datagram format
•fragmentation
•IPv4 addressing
•network address
translation
•IPv6
4.4 Generalized Forward and
SDN
•match
•action
•OpenFlow examples
of match-plus-action in
action
Chapter 4: outline
4-35Network Layer: Data Plane

36. IP addressing: introduction
IP address: 32-bit
identifier for host, router
interface
interface: connection
between host/router and
physical link
•router’s typically have
multiple interfaces
•host typically has one or
two interfaces (e.g., wired
Ethernet, wireless 802.11)
IP addresses associated
with each interface
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
223.1.1.1 = 11011111 00000001 00000001 00000001
223 1 11
4-36Network Layer: Data Plane

37. IP addressing: introduction
Q: how are interfaces
actually connected?
A: we’ll learn about that in
chapter 5, 6.
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A: wired Ethernet interfaces
connected by Ethernet switches
A: wireless WiFi interfaces
connected by WiFi base station
For now: don’t need to worry
about how one interface is
connected to another (with no
intervening router)
4-37Network Layer: Data Plane

38. Subnets
IP address:
•subnet part - high order
bits
•host part - low order
bits (MSB)
what’s a subnet ?
•device interfaces with
same subnet part of IP
address
•can physically reach
each other without
intervening router network consisting of 3 subnets
223.1.1.1
223.1.1.3
223.1.1.4223.1.2.9
223.1.3.2
223.1.3.1
subnet
223.1.1.2
223.1.3.27
223.1.2.2
223.1.2.1
4-38Network Layer: Data Plane
11001000 00010111 00010000 00000000
subnet
part
host
part
200.23.16.0/23

39. recipe
to determine the
subnets, detach each
interface from its host
or router, creating
islands of isolated
networks
each isolated network
is called a subnet
subnet mask: /24
Subnets
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
223.1.1.1
223.1.1.3
223.1.1.4223.1.2.9
223.1.3.2
223.1.3.1
subnet
223.1.1.2
223.1.3.27
223.1.2.2
223.1.2.1
4-39Network Layer: Data Plane

40. how many?
223.1.1.1
223.1.1.3
223.1.1.4
223.1.2.2223.1.2.1
223.1.2.6
223.1.3.2223.1.3.1
223.1.3.27
223.1.1.2
223.1.7.0
223.1.7.1
223.1.8.0223.1.8.1
223.1.9.1
223.1.9.2
Subnets
4-40Network Layer: Data Plane

41. IP addressing: CIDR
CIDR: Classless InterDomain Routing
•subnet portion of address of arbitrary length
•address format: a.b.c.d/x, where x is # bits in
subnet portion of address
11001000 00010111 00010000 00000000
subnet
part
host
part
200.23.16.0/23
4-41Network Layer: Data Plane

42. IP addresses: how to get one?
Q: How does a host get IP address?
hard-coded by system admin in a file
•Windows: control-panel->network->configuration->tcp/ip->properties
•UNIX: /etc/rc.config
DHCP: Dynamic Host Configuration Protocol: dynamically get
address from as server
•“plug-and-play”
•DHCP is a protocol called from Application layer
4-42Network Layer: Data Plane

43. DHCP: Dynamic Host Configuration Protocol
goal: allow host to dynamically obtain its IP address from network server when
it joins network
•can renew its lease on address in use
•allows reuse of addresses (only hold address while connected/“on”)
•support for mobile users who want to join network (more shortly)
DHCP overview:
•host broadcasts “DHCP discover” msg [optional]
•DHCP server responds with “DHCP offer” msg [optional]
•host requests IP address: “DHCP request” msg
•DHCP server sends address: “DHCP ack” msg
4-43Network Layer: Data Plane

44. DHCP client-server scenario
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
223.1.1.1
223.1.1.3
223.1.1.4223.1.2.9
223.1.3.2223.1.3.1
223.1.1.2
223.1.3.27
223.1.2.2
223.1.2.1
DHCP
server
arriving DHCP
client needs
address in this
network
4-44Network Layer: Data Plane

45. DHCP server: 223.1.2.5 arriving
client
DHCP discover
src : 0.0.0.0, 68
dest.: 255.255.255.255,67
yiaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 654
lifetime: 3600 secs
DHCP request
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
yiaddrr: 223.1.2.4
transaction ID: 655
lifetime: 3600 secs
DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 655
lifetime: 3600 secs
DHCP client-server scenario
Broadcast: is there a
DHCP server out there?
Broadcast: I’m a DHCP
server! Here’s an IP
address you can use
Broadcast: OK. I’ll take
that IP address!
Broadcast: OK. You’ve
got that IP address!
4-45Network Layer: Data Plane

46. DHCP: more than IP addresses
DHCP can return more than just allocated IP
address on subnet:
•address of first-hop router for client
•name and IP address of DNS sever
•network mask (indicating network versus host portion
of address)
4-46Network Layer: Data Plane

47. connecting laptop needs
its IP address, addr of
first-hop router, addr of
DNS server: use DHCP
router with DHCP
server built into
router
DHCP request encapsulated
in UDP, encapsulated in IP,
encapsulated in 802.1
Ethernet
Ethernet frame broadcast
(dest: FFFFFFFFFFFF) on LAN,
received at router running
DHCP server
Ethernet demuxed to IP
demuxed, UDP demuxed to
DHCP
168.1.1.1
DHCP
UDP
IP
Eth
Phy
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
UDP
IP
Eth
Phy
DHCP
DHCP
DHCP
DHCPDHCP
DHCP: example
4-47Network Layer: Data Plane

48. DCP server formulates DHCP
ACK containing client’s IP
address, IP address of first-hop
router for client, name & IP
address of DNS server
encapsulation of DHCP
server, frame forwarded
to client, demuxing up to
DHCP at client
DHCP: example
router with DHCP
server built into
router
DHCP
DHCP
DHCP
DHCP
DHCP
UDP
IP
Eth
Phy
DHCP
DHCP
UDP
IP
Eth
Phy
DHCP
DHCP
DHCP
DHCP
client now knows its IP
address, name and IP
address of DSN server, IP
address of its first-hop
router
4-48Network Layer: Data Plane

49. DHCP: Wireshark
output (home LAN)
Message type: Boot Reply (2)
Hardware type: Ethernet
Hardware address length: 6
Hops: 0
Transaction ID: 0x6b3a11b7
Seconds elapsed: 0
Bootp flags: 0x0000 (Unicast)
Client IP address: 192.168.1.101 (192.168.1.101)
Your (client) IP address: 0.0.0.0 (0.0.0.0)
Next server IP address: 192.168.1.1 (192.168.1.1)
Relay agent IP address: 0.0.0.0 (0.0.0.0)
Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a)
Server host name not given
Boot file name not given
Magic cookie: (OK)
Option: (t=53,l=1) DHCP Message Type = DHCP ACK
Option: (t=54,l=4) Server Identifier = 192.168.1.1
Option: (t=1,l=4) Subnet Mask = 255.255.255.0
Option: (t=3,l=4) Router = 192.168.1.1
Option: (6) Domain Name Server
Length: 12; Value: 445747E2445749F244574092;
IP Address: 68.87.71.226;
IP Address: 68.87.73.242;
IP Address: 68.87.64.146
Option: (t=15,l=20) Domain Name = "hsd1.ma.comcast.net."
reply
Message type: Boot Request (1)
Hardware type: Ethernet
Hardware address length: 6
Hops: 0
Transaction ID: 0x6b3a11b7
Seconds elapsed: 0
Bootp flags: 0x0000 (Unicast)
Client IP address: 0.0.0.0 (0.0.0.0)
Your (client) IP address: 0.0.0.0 (0.0.0.0)
Next server IP address: 0.0.0.0 (0.0.0.0)
Relay agent IP address: 0.0.0.0 (0.0.0.0)
Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a)
Server host name not given
Boot file name not given
Magic cookie: (OK)
Option: (t=53,l=1) DHCP Message Type = DHCP Request
Option: (61) Client identifier
Length: 7; Value: 010016D323688A;
Hardware type: Ethernet
Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a)
Option: (t=50,l=4) Requested IP Address = 192.168.1.101
Option: (t=12,l=5) Host Name = "nomad"
Option: (55) Parameter Request List
Length: 11; Value: 010F03062C2E2F1F21F92B
1 = Subnet Mask; 15 = Domain Name
3 = Router; 6 = Domain Name Server
44 = NetBIOS over TCP/IP Name Server
……
request
4-49Network Layer: Data Plane

50. IP addresses: how to get one?
Q: how does network get subnet part of IP addr?
A: gets allocated portion of its provider ISP’s address
space
ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20
Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23
Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23
Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23
... ….. …. ….
Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23
4-50Network Layer: Data Plane

51. Hierarchical addressing: route aggregation
“Send me anything
with addresses
beginning
200.23.16.0/20”
200.23.16.0/23
200.23.18.0/23
200.23.30.0/23
Fly-By-Night-ISP
Organization 0
Organization 7
Internet
Organization 1
ISPs-R-Us
“Send me anything
with addresses
beginning
199.31.0.0/16”
200.23.20.0/23
Organization 2
.
.
.
.
.
.
hierarchical addressing allows efficient advertisement of routing
information:
4-51Network Layer: Data Plane

52. ISPs-R-Us has a more specific route to Organization 1
“Send me anything
with addresses
beginning
200.23.16.0/20”
200.23.16.0/23
200.23.18.0/23
200.23.30.0/23
Fly-By-Night-ISP
Organization 0
Organization 7
Internet
Organization 1
ISPs-R-Us
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
200.23.20.0/23
Organization 2
.
.
.
.
.
.
Hierarchical addressing: more specific routes
4-52Network Layer: Data Plane

53. IP addressing: the last word...
Q: how does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers http://www.icann.org/
•allocates addresses
•manages DNS
•assigns domain names, resolves disputes
4-53Network Layer: Data Plane

54. NAT: network address translation
10.0.0.1
10.0.0.2
10.0.0.3
10.0.0.4
138.76.29.7
local network
(e.g., home network)
10.0.0/24
rest of
Internet
datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
all datagrams leaving local
network have same single
source NAT IP address:
138.76.29.7,different source
port numbers
4-54Network Layer: Data Plane

55. motivation: local network uses just one IP address as far
as outside world is concerned:
range of addresses not needed from ISP: just one IP
address for all devices
can change addresses of devices in local network
without notifying outside world
can change ISP without changing addresses of
devices in local network
devices inside local net not explicitly addressable,
visible by outside world (a security plus)
NAT: network address translation
4-55Network Layer: Data Plane

56. implementation: NAT router must:
outgoing datagrams: replace (source IP address, port #) of
every outgoing datagram to (NAT IP address, new port #)
. . . remote clients/servers will respond using (NAT IP
address, new port #) as destination addr
remember (in NAT translation table) every (source IP address,
port #) to (NAT IP address, new port #) translation pair
incoming datagrams: replace (NAT IP address, new port #) in
dest fields of every incoming datagram with corresponding
(source IP address, port #) stored in NAT table
NAT: network address translation
4-56Network Layer: Data Plane

57. 10.0.0.1
10.0.0.2
10.0.0.3
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
1
10.0.0.4
138.76.29.7
1: host 10.0.0.1
sends datagram to
128.119.40.186, 80
NAT translation table
WAN side addr LAN side addr
138.76.29.7, 5001 10.0.0.1, 3345
…… ……
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
4
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
2
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3
3: reply arrives
dest. address:
138.76.29.7, 5001
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
NAT: network address translation
4-57Network Layer: Data Plane
* Check out the online interactive exercises for more
examples: http://gaia.cs.umass.edu/kurose_ross/interactive/

58. 16-bit port-number field:
•60,000 simultaneous connections with a single
LAN-side address!
NAT is controversial:
•routers should only process up to layer 3
•address shortage should be solved by IPv6
•violates end-to-end argument
•NAT possibility must be taken into account by app
designers, e.g., P2P applications
•NAT traversal: what if client wants to connect
to server behind NAT?
NAT: network address translation
4-58Network Layer: Data Plane

59. 4.1 Overview of Network
layer
•data plane
•control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
•datagram format
•fragmentation
•IPv4 addressing
•network address
translation
•IPv6
4.4 Generalized Forward and
SDN
•match
•action
•OpenFlow examples
of match-plus-action in
action
Chapter 4: outline
4-59Network Layer: Data Plane

60. IPv6: motivation
initial motivation: 32-bit address space soon to be
completely allocated.
additional motivation:
•header format helps speed processing/forwarding
•header changes to facilitate QoS
IPv6 datagram format:
•fixed-length 40 byte header
•no fragmentation allowed
4-60Network Layer: Data Plane

61. IPv6 datagram format
priority: identify priority among datagrams in flow
flow Label: identify datagrams in same “flow.”
(concept of“flow” not well defined).
next header: identify upper layer protocol for data
data
destination address
(128 bits)
source address
(128 bits)
payload len next hdrhop limit
flow labelpriver
32 bits
4-61Network Layer: Data Plane
IP protocol version
Number V6
Was 32 bit in IP V4
Was option in IP V4

62. Other changes from IPv4
checksum: removed entirely to reduce processing
time at each hop
options: allowed, but outside of header, indicated
by “Next Header” field
ICMPv6: new version of ICMP
•additional message types, e.g. “Packet Too Big”
•multicast group management functions
4-62Network Layer: Data Plane

63. Transition from IPv4 to IPv6
not all routers can be upgraded simultaneously
•no “flag days”
•how will network operate with mixed IPv4 and
IPv6 routers?
tunneling: IPv6 datagram carried as payload in IPv4
datagram among IPv4 routers
IPv4 source, dest addr
IPv4 header fields
IPv4 datagram
IPv6 datagram
IPv4 payload
UDP/TCP payload
IPv6 source dest addr
IPv6 header fields
4-63Network Layer: Data Plane

64. Tunneling
physical view:
IPv4 IPv4
A B
IPv6 IPv6
E
IPv6 IPv6
FC D
logical view:
IPv4 tunnel
connecting IPv6 routers
E
IPv6 IPv6
FA B
IPv6 IPv6
4-64Network Layer: Data Plane

65. flow: X
src: A
dest: F
data
A-to-B:
IPv6
Flow: X
Src: A
Dest: F
data
src:B
dest: E
B-to-C:
IPv6 inside
IPv4
E-to-F:
IPv6
flow: X
src: A
dest: F
data
B-to-C:
IPv6 inside
IPv4
Flow: X
Src: A
Dest: F
data
src:B
dest: E
physical view:
A B
IPv6 IPv6
E
IPv6 IPv6
FC D
logical view:
IPv4 tunnel
connecting IPv6 routers
E
IPv6 IPv6
FA B
IPv6 IPv6
Tunneling
IPv4 IPv4
4-65Network Layer: Data Plane

66. IPv6: adoption
Google: 8% of clients access services via IPv6
NIST: 1/3 of all US government domains are IPv6
capable
Long (long!) time for deployment, use
•20 years and counting!
•think of application-level changes in last 20 years: WWW,
Facebook, streaming media, Skype, …
•Why?
4-66Network Layer: Data Plane

67. 5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
5.7 Network management
and SNMP
Chapter 5: outline
5-67Network Layer: Control
Plane

68. Network-layer functions
forwarding: move packets
from router’s input to
appropriate router output
data plane
control plane
Two approaches to structuring network control plane:
per-router control (traditional)
logically centralized control (software defined networking)
Recall: two network-layer functions:
5-68Network Layer: Control
Plane
routing: determine route
taken by packets from
source to destination

69. Per-router control plane
Routing
Algorithm
Individual routing algorithm components in each and every
router interact with each other in control plane to compute
forwarding tables
data
plane
control
plane
5-69Network Layer: Control
Plane
Routing
protocol
Forward
rules

70. data
plane
control
plane
Logically centralized control plane
A distinct (typically remote) controller interacts with local
control agents (CAs) in routers to compute forwarding tables
Remote Controller
CA
CA CA CA CA
5-
70
Network Layer: Control
Plane

71. 5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs: BGP
5.5 The SDN control plane
5.6 ICMP: The Internet Control
Message Protocol
5.7 Network management and
SNMP
Chapter 5: outline
5-71Network Layer: Control
Plane
 
An

autonomoussystem
 
: AS

, isassignedagloballyuniquenumber

 sometimescalledan

  AutonomousSystemNumber
(ASN.
) An
AS
is

aconnectedgroupofoneormoreInternetProtocolprefixesrunby

 oneormore
network 
operatorswhichhasaSINGLEand
 
CLEARLY
  DEFINEDroutingpolicy.

InternetProtocolprefixes

4 1 forIPV isthe#of ’sinsubnetmask

72. Routing protocols
Routing protocol goal: determine “good” paths
(equivalently, routes), from sending hosts to
receiving host, through network of routers
path: sequence of routers 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!
5-72Network Layer: Control
Plane

73. u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
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) }
Graph abstraction of the network
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
5-73Network Layer: Control
Plane

74. Graph abstraction: costs
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
cost could always be 1, or
inversely related to bandwidth,
or inversely related to
congestion
cost of path (x
1
, x
2
, x
3
,…, x
p
) = c(x
1
,x
2
) + c(x
2
,x
3
) + … + c(x
p-1
,x
p
)
key question: what is the least-cost path between u and z ?
routing algorithm: algorithm that finds that least cost path
5-74Network Layer: Control
Plane

75. Routing algorithm classification
Q: global or decentralized information?
global: LS
all routers have complete
topology, link cost info
“link state” algorithms
decentralized: DV
router knows physically-
connected neighbors, link costs
to neighbors
iterative process of computation,
exchange of info with neighbors
“distance vector” algorithms
Q: static or dynamic?
static:
routes change slowly over
time
dynamic:
routes change more
quickly
•periodic update
•in response to link cost
changes
5-75Network Layer: Control
Plane

76. 5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
5.5 The SDN control plane
5.6 ICMP: The Internet Control
Message Protocol
5.7 Network management and
SNMP
Chapter 5: outline
5-76Network Layer: Control
Plane

77. A link-state routing algorithm (Global)
Dijkstra’s algorithm
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
iterative: after k iterations,
know least cost path to k
dest.’s
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 dest. v
p(v): predecessor node
along path from source to
v
N': set of nodes whose
least cost path definitively
known
5-77Network Layer: Control
Plane

78. Dijsktra’s algorithm
1 Initialization:
2 N' = {u} = ةيادبلا ةطقن نزو0
3 for all nodes v فارجلاب دقعلا لكل
4 if v adjacent to u اردصملل ةرواجم دقعلا تنا
+ك اذ
5 then D(v) = c(u,v) طبارلا ةفلك يه دقعلل لوصولا ةفلكف
اهل رواجملا رشابملا
•else D(v) = ∞ ةياهنلا ام اه
+عض لااو
•
8 Loop ةيراركتلا ةيلمعلا ةيادب
9 find w not in N' such that D(w) is a minimum لا ةدقع برقا دجوا
ةفلك لقا اهلو ةيادبلا ةطقنب لصتت
10 add w to N‘ ةفوف
+صملا يلا ةدق+علا هذه فضا
(ةيساسلأا1)
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'
5-78Network Layer: Control
Plane

79. w
3
4
v
x
u
5
3
7 4
y
8
z
2
7
9
Dijkstra’s algorithm: example
StepN'
D(v)
p(v)
0
1
2
3
4
5
D(w)
p(w)
D(x)
p(x)
D(y)
p(y)
D(z)
p(z)
u ∞ ∞ 7,u3,u5,u
uw ∞ 11,w 6,w 5,u
14,x 11,w 6,wuwx
uwxv 14,x 10,v
uwxvy 12,y
notes:
construct shortest path tree by
tracing predecessor nodes
ties can exist (can be broken
arbitrarily)
uwxvyz
5-79Network Layer: Control
Plane
ةيمزراوخلاب رطس لوا
ةفوفصملاب عضن مث)شاد نا( ةدقعلا ويلباد
نوكت ضورفملا3+4=7 رغصلأا ةميقلا انرتخا اننكل
دومعلا سفنب ةدوجوملا
D(v) = min( D(v), D(w) + c(w,v) )
3,u
5,u
6,w
10,v

80. Dijkstra’s algorithm: another example
Step
0
1
2
3
4
5
N'
u
ux
uxy
uxyv
uxyvw
uxyvwz
D(v),p(v)
2,u
2,u
2,u
D(w),p(w)
5,u
4,x
3,y
3,y
D(x),p(x)
1,u
D(y),p(y)
∞
2,x
D(z),p(z)
∞
∞
4,y
4,y
4,y
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
5-80Network Layer: Control
Plane
* Check out the online interactive exercises for more
examples: http://gaia.cs.umass.edu/kurose_ross/interactive/

81. Network Layer
4-81
Shortest path is
A-C-D-E-G-F-H=11

82. Network Layer
4-82

83. Dijkstra Animated Example-2
12

84. Dijkstra Animated Example-2
13

85. Dijkstra Animated Example-2
14

86. Dijkstra Animated Example-2
15

87. Dijkstra Animated Example-2
16

88. Dijkstra Animated Example-2
17

89. Dijkstra Animated Example-2
18

90. Dijkstra Animated Example-2
19

91. Dijkstra Animated Example-2
Shortest Path from A to H,
A to C, C to D, D to E, E to G, G to F, F to H
20

92. Network Layer
4-92
Shortest path is
A-C-F-G=9

93. Network Layer
4-93
Shortest path is
A-B-E-F=6

94. Network Layer
4-94
Shortest path is
A-B-C-E-F=12

95. 4-95
#Suppose there are three routers between a source host and a destination host. Ignoring
fragmentation, an IP datagram sent from the source host to the destination host will travel
over how many interfaces? How many forwarding tables will be indexed to move the
datagram from the source to the destination?
Interfaces=(Number of routers) * (2 per router) + 2 = 6 + 2 = 8
3 routers means three forwarding tables will be indexed
An IP datagram sent from a source host to a destination host will travel through 8 interfaces.
3 forwarding tables will be indexed to move the datagram from source to destination.
FT FT FT
#Consider sending a 2400-Byte datagram into a link that has an MTU of 700 Bytes. Suppose
the original datagram is stamped with the identification number 422. How many fragments are
generated? What are the values in the various fields in the IP datagram(s) generated related to
fragmentation
The maximum size of data field in each fragment = 680 (because there are 20 bytes IP
header). Thus the number of required fragments =(2400-20)/680=4
Each fragment will have Identification number 422. Each fragment except the last one will be
of size 700 bytes (including IP header). The last datagram will be of size 360 bytes (including
IP header). =2400-(3*680)=360, offset 680/8=85 bit
The offsets of the 4 fragments will be 0, 85, 170, 255. Each of the first 3 fragments will have
flag=1; the last fragment will have flag=0.

96. Network Layer
4-96

97. Network Layer
4-97
- A datagram of 3000 bytes arrives to a router and must forward it to a link with an
MTU of 1200 byte.
i- How many fragments must be allocated for the datagram?
ii- List the fragment size by filling below table:

Fragment #Size of IP headerSize of IP payload
0 20 1180
1 20 1180
2 20 620

98. Dijkstra’s algorithm: example (2)
u
yx
wv
z
resulting shortest-path tree from u:
v
x
y
w
z
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
destinationlink
resulting forwarding table in u:
5-98Network Layer: Control
Plane

99. 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(n
2
)
more efficient implementations possible: O(nlogn)
oscillations possible:
e.g., support link cost equals amount of carried traffic:
A
D
C
B
1 1+e
e0
e
1
1
00
initially
A
D
C
B
given these costs,
find new routing….
resulting in new costs
2+e 0
0
0
1+e1
A
D
C
B
given these costs,
find new routing….
resulting in new costs
0 2+e
1+e
1
00
A
D
C
B
given these costs,
find new routing….
resulting in new costs
2+e 0
0
0
1+e1
5-99Network Layer: Control
Plane

100. 5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
5.7 Network management
and SNMP
Chapter 5: outline
5-
100
Network Layer: Control
Plane

102. Network Layer 4-102
Detecting Topology Changes
•Beaconing
–Periodic “hello” messages in both directions
–Detect a failure after a few missed “hellos”
•Performance trade-offs
–Detection speed
–Overhead on link bandwidth and CPU
–Likelihood of false detection
“hello”

103. Network Layer
4-103
Broadcasting the Link State
•Flooding
–Node sends link-state information out its links
–And then the next node sends out all of its links
–… except the one where the information arrived
X A
C B D
(a)
X A
C B D
(b)
X A
C B D
(c)
X A
C B D
(d)

104. Distance vector algorithm
Bellman-Ford equation (dynamic programming)
let
d
x
(y) := cost of least-cost path from x to y
then
d
x(y) = min {c(x,v) + d
v(y) }

v
cost to neighbor v
min taken over all neighbors v of x
cost from neighbor v to destination y
5-
104
Network Layer: Control
Plane

105. Bellman-Ford example
clearly, d
v
(z) = 5, d
x
(z) = 3, d
w
(z) = 3
d
u
(z) = min { c(u,v) + d
v
(z),
c(u,x) + d
x
(z),
c(u,w) + d
w
(z) }
= min {(2 + 5),
(1 + 3),
(5 + 3)} = 4
node achieving minimum is next
hop in shortest path, used in forwarding table
B-F equation says:
5-
105
Network Layer: Control
Plane
2
1
5
d
x
(y) = min {c(x,v) + d
v
(y) }

106. Distance vector algorithm
D
x(y) = estimate of least cost from x to y
•x maintains distance vector D
x = [D
x(y): y є N ]
node x:
•knows cost to each neighbor v: c(x,v)
•maintains its neighbors’ distance vectors. For
each neighbor v, x maintains
D
v = [D
v(y): y є N ]
5-
106
Network Layer: Control
Plane

107. key idea:
from time-to-time, each node sends its own
distance vector estimate to neighbors
when x receives new DV estimate from neighbor,
it updates its own DV using B-F equation:
D
x
(y) ← min
v
{c(x,v) + D
v
(y)} for each node y ∊ N
under minor, natural conditions, the estimate
D
x
(y) converge to the actual least cost d
x
(y)
Distance vector algorithm DV
5-
107
Network Layer: Control
Plane

108. iterative, asynchronous:
each local iteration
caused by:
local link cost change
DV update message from
neighbor
distributed:
each node notifies
neighbors only when its
DV changes
•neighbors then notify their
neighbors if necessary
راظتنا رتوارلا موقي ةرتف لك يف
تاراسملا ةفلك رابخا
wait for (change in local link cost or
msg from neighbor)
راسملل ةفلكلا نيمختب موقي
recompute estimates
رشن رتوارلا يلع ريي
+غت يأ ثدح اذاو
ربخلا
if DV to any dest has changed,
notify neighbors
each node:
Distance vector algorithm
5-
108
Network Layer: Control
Plane

109. x y z
x
y
z
0 2 7
∞∞∞
∞∞∞
f
r
o
m
cost to
f
r
o
m
f
r
o
m
x y z
x
y
z
0
x y z
x
y
z
∞∞
∞∞∞
cost to
x y z
x
y
z
∞∞∞
710
cost to
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
time
node x
table
D
x
(y) = min{c(x,y) + D
y
(y), c(x,z) + D
z
(y)}
= min{2+0 , 7+1} = 2
D
x(z) = min{c(x,y) +
D
y
(z), c(x,z) + D
z
(z)}
= min{2+1 , 7+0} = 3
32
node y
table
node z
table
cost to
f
r
o
m
5-
109
Network Layer: Control
Plane

110. x y z
x
y
z
0 2 3
f
r
o
m
cost to
x y z
x
y
z
0 2 7
f
r
o
m
cost to
x y z
x
y
z
0 2 3
f
r
o
m
cost to
x y z
x
y
z
0 2 3
f
r
o
m
cost to
x y z
x
y
z
0 2 7
f
r
o
m
cost to
2 0 1
7 1 0
2 0 1
3 1 0
2 0 1
3 1 0
2 0 1
3 1 0
2 0 1
3 1 0
time
x y z
x
y
z
0 2 7
∞∞∞
∞∞∞
f
r
o
m
cost to
f
r
o
m
f
r
o
m
x y z
x
y
z
0
x y z
x
y
z
∞∞
∞∞∞
cost to
x y z
x
y
z
∞∞∞
710
cost to
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
time
x z
12
7
y
node x
table
D
x
(y) = min{c(x,y) + D
y
(y), c(x,z) + D
z
(y)}
= min{2+0 , 7+1} = 2
D
x(z) = min{c(x,y) +
D
y
(z), c(x,z) + D
z
(z)}
= min{2+1 , 7+0} = 3
32
node y
table
node z
table
cost to
f
r
o
m
5-
110
Network Layer: Control
Plane
ط
ق
ف

ه
ن
ا
ر
ي
ج

ف
ر
ع
ي

ر
ت
و
ا
ر

ل
ك

لا
و
أ
ة
د
ي
د
ج
ل
ا

ة
ف
ل
ك
ل
ا

ب
س
ح
ي
ل

ن
ا
ر
ي
ج
ل
ا

ن
م

ت
ا
ر
ا
س
م
ل
ا

ر
ا
ب
خ
ا

ى
ق
ل
ت
ي

م
ث

111. Distance vector: link cost changes
link cost changes:
node detects local link cost change
updates routing info, recalculates
distance vector
if DV changes, notify neighbors
“good
news
travels
fast”
x z
14
50
y
1
t
0 : y detects link-cost change, updates its DV, informs its
neighbors.
t
1 : z receives update from y, updates its table, computes new
least cost to x , sends its neighbors its DV.
t
2
: 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.
5-
111
Network Layer: Control
Plane
* Check out the online interactive exercises for more
examples: http://gaia.cs.umass.edu/kurose_ross/interactive/

112. Distance vector: link cost changes
link cost changes:
node detects local link cost change
bad news travels slow - “count to
infinity” problem!
44 iterations before algorithm
stabilizes: see text
x z
14
50
y
60
poisoned reverse:
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
to X via Z)
will this completely solve count to infinity problem?
5-
112
Network Layer: Control
Plane
تقؤم لكشب لحت فوس

113. Comparison of LS and DV algorithms
message complexity
LS: with n nodes, E links, O(nE)
msgs sent
DV: exchange between neighbors
only
•convergence time varies
speed of convergence
LS: O(n
2
) algorithm requires
O(nE) msgs
•may have oscillations
DV: convergence time varies
•may be routing loops
•count-to-infinity problem
robustness: what happens if
router malfunctions?
LS: اماعون لضفا
•node can advertise incorrect
link cost
•each node computes only its
own table
DV:
•DV node can advertise
incorrect path cost
•each node’s table used by
others
•error propagate thru
network
5-
113
Network Layer: Control
Plane

114. 5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the
Internet: OSPF
5.4 routing among the ISPs:
BGP
5.5 The SDN control plane
5.6 ICMP: The Internet
Control Message
Protocol
5.7 Network management
and SNMP
Chapter 5: outline
5-
114
Network Layer: Control
Plane

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

116. Traceroute and ICMP
source sends series of UDP
segments to destination
•first set has TTL =1
•second set has TTL=2, etc.
•unlikely port number نلا
ةعبارلا ةقبطلاب تروبلا
when datagram in nth set
arrives to nth router:
•router discards datagram and
sends source ICMP message
(type 11, code 0)
•ICMP message include name
of router & IP address
when ICMP message
arrives, source records
RTTs
stopping criteria:
UDP segment eventually
arrives at destination host
destination returns ICMP
“port unreachable”
message (type 3, code 3)
source stops
3 probes
3 probes
3 probes
5-
116
Network Layer: Control
Plane