Transcript Network Layer

Chapter 4
Network Layer
Computer Networking
A Top-Down Approach
6th edition
These slides are based on the slides
made available by Kurose and Ross.
Jim Kurose, Keith Ross
© All material copyright 1996-2012
Addison-Wesley
J.F Kurose and K.W. Ross, All Rights Reserved
March 2012
Network Layer
4-1
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer
4-2
Network Layer Functions
 network layer protocol in
every host and router
Consider transporting a
segment from sender to receiver
 sending side: encapsulates
segments into datagrams
 receiving side: delivers
segments to transport layer
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
 Path Determination: sum of
routes chosen by routers to
deliver packets from source to
destination.
 Forwarding: move packets from
router’s input to appropriate
router’s output
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
Network Layer
application
transport
network
data link
physical
4-3
Routing and Forwarding
routing algorithm
routing algorithm determines
path through network
local forwarding table
header value output link
forwarding table determines
local forwarding at this router
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
router examines header
fields in all datagrams
passing through it
Network Layer
4-4
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer
4-5
Network Service Model
What service model can be considered for a
network transporting packets from sender to
receiver?
example services for
individual datagrams:
example services for a
flow of packets:
 “best effort” delivery
 in-order delivery
 No constraints on delay or
 guaranteed minimum
bandwidth
bandwidth to flow
 restrictions on changes
in inter-packet timespacing
Network Layer
4-6
Connection-oriented & connectionless
 Virtual Circuit-network provides link or
network-layer connection-oriented service.
 Datagram-based network provides networklayer connectionless service.
 Analogous to the transport-layer services but:

Service: host-to-host packet delivery

Implementation: every router in the network
Network Layer
4-7
Virtual Circuit: VC
source-to-destination path behaves much like telephone
“circuit”

Performance-wise (but it is virtual circuit)

Network actions along the source-to-destination path
 Setup: for each connection before data packets can flow
 Each packet carries VC identifier (not destination
address)
 Every router on the path maintains “state” for each
passing connection.
Benefit: Link & router resources (bandwidth, buffers) may
be allocated to VC
(dedicated resources = predictable service)
Network Layer
4-8
VC: Signaling Protocols
 used to setup, maintain and teardown VC
 used in ATM, Frame-Relay, X.25
 not used in today’s Internet on network layer
application
transport
network
data link
physical
5. data flow begins
4. call connected
1. initiate call
application
transport
3. accept call
network
2. incoming call
data link
physical
6. receive data
Network Layer
4-9
VC: Forwarding Table
VC identifier
22
12
1
Forwarding table
in northwest router:
2
32
3
interface
number
Incoming interface
1
2
3
1
…
Incoming VC #
12
63
7
97
…
Outgoing interface
3
1
2
3
Outgoing VC #
22
18
17
87
…
…
Routers maintain connection state information!
Network Layer 4-10
Datagram Networks (Internet)
 no call setup to establish path through network
 routers: no state about end-to-end connections
 no network-level concept of “connection”
 packets forwarded using destination host address
 packets between same source-destination pair may take
different paths
application
transport
network 1. send datagrams
data link
physical
application
transport
2. receive datagrams network
data link
physical
Network Layer
4-11
Datagram: Forwarding Table
routing algorithm
local forwarding table
dest. address output link
address-range 1
address-range 2
address-range 3
address-range 4
4 billion IP addresses, so
rather than list individual
destination address
list range of addresses
(aggregate table entries)
3
2
2
1
IP destination address in
arriving packet’s header
1
3 2
Network Layer 4-12
Datagram or VC network: why?
Internet (datagram)
ATM (VC)
 data exchange among
 more complicated
computers
 evolved from telephony
 “elastic” service, no strict
 human conversation:
timing requirements.
 strict timing, reliability
 “smart” end systems
requirements
(computers)
 need for guaranteed
 can adapt, perform control,
service
error recovery
 “dumb” end systems
 simple inside network,
 telephones
complexity at “edge”
 moves complexity to
 many link types
inside network
 different characteristics
 uniform service difficult
Network Layer 4-13
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-14
Router Architecture: Overview
Two key router functions:
 run routing algorithms/protocols (RIP, OSPF, BGP)
 forwarding datagrams from incoming to outgoing link
forwarding tables computed,
pushed to input ports
routing
processor
routing, management
control plane (software)
forwarding packets
plane (hardware)
high-seed
switching
fabric
router input ports
router output ports
Network Layer 4-15
Input Port Functions
Physical layer:
bit-level reception
Data link layer:
e.g., Ethernet
Decentralized switching:
 given datagram destination address, lookup
output port using forwarding table in input
port memory
 goal: complete input port processing at ‘line
speed’
 queuing: if datagrams arrive faster than
forwarding rate into switch fabric
Network Layer 4-16
Three types of switching fabrics
 transfer packet from
input buffer to
appropriate output
buffer
 switching rate: rate
at which packets can
be transferred from
inputs to outputs


often measured as
multiple of input/output
line rates
N inputs: switching rate
N times line rate is
desirable
Network Layer 4-17
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
Network Layer 4-18
Switching via Bus
 datagram from input port memory
bus
to output port memory via a shared
bus, one packet at a time
 bus contention: switching speed
limited by bus bandwidth
 32 Gbps bus, Cisco 5600: sufficient
speed for access and enterprise
routers
Network Layer 4-19
Switching via Interconnection Network
 overcome bus bandwidth limitations
crossbar
 banyan networks, crossbar, other
interconnection networks initially developed
to connect processors in multiprocessor
 advanced design: fragmenting datagram into
fixed length cells, tag and switch cells through
the fabric.
 Cisco 12000: switches 60 Gbps through the
interconnection network
Network Layer 4-20
Output Ports
switch
fabric
datagram
buffer
queueing
link
layer
protocol
(send)
line
termination
 Buffering required when datagrams arrive from fabric
faster than the transmission rate of the outgoing link
 Scheduling discipline chooses among queued
datagrams for transmission
Network Layer 4-21
Output Port Queueing
switch
fabric
at t, packets more
from input to output
switch
fabric
one packet time later
 buffering when arrival rate via switch exceeds
output line speed
 delay due to queueing and loss due to output
port buffer overflow!
Network Layer 4-22
Input Port Queuing
 fabric slower (seldom!) than input ports combined →
queueing may occur at input port
 queueing delay and loss due to input buffer overflow!
 Head-Of-Line (HOL) blocking: queued datagram at front
of queue prevents others in queue from moving forward
switch
fabric
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
Network Layer 4-23
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-24
The Internet Network Layer
Host, router network layer functions:
Transport layer: TCP, UDP
Network
layer
Routing protocols
• path selection
• RIP/UDP, OSPF/IP, BGP/TCP
forwarding
table
ICMP protocol
• error reporting
• router “signaling”
IP protocol
• addressing conventions
• datagram format
• packet handling conventions
Link layer
Physical layer
Network Layer 4-25
IP datagram format
32 bits
IP protocol version = 4
header length 32-bits
blocks, 5 standard)
TOS (priority)
TTL: max number of
remaining hops
(decremented by one
at each router)
Upper layer protocol
to deliver payload to
6 for TCP
17 for UDP
how much overhead?
 20 bytes of TCP
 20 bytes of IP
 = 40 bytes + app
layer overhead
ver
head. type of
length service
total datagram
length (bytes)
length
fragment
16-bit identifier flags
offset
time to Protocol
Header Checksum
live
32-bit source IP address
32-bit destination IP address
Options (if any)
Data Field
Variable length
(typically a TCP or UDP segment)
for
fragmentation/
reassembly
Flags (3 bits):
Reserved (0)
DF= don’t frag.
MF= more frag.
e.g. timestamp,
security label,
record route
taken, specify
list of routers
to visit, etc
Network Layer 4-26
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-27
IP Addressing: Introduction
223.1.1.1
 interface: connection
between host/router
and physical link



223.1.2.1
223.1.1.2
routers typically have
multiple active interfaces
hosts typically have one
active interface (either
wired Ethernet or
wireless 802.11)
IP address associated
with each interface
 IP address: 32-bit
identifier for host,
router interface
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.3
223.1.2.2
223.1.3.1
223.1.3.2
223.1.3.1 = 11011111 00000001 00000011 00000001
Dotted Decimal Notation
223
1
3
1
Network Layer 4-28
Subnets
 IP address:
 subnet part (high order
bits)
 host part (low order bits)
 What’s a subnet ?
 device interfaces with
same subnet part of IP
address
 Contains hosts that can
physically reach each
other without intervening
router
 All other hosts are
reached by sending
datagrams to router
interface that works as
“default gateway”
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.3
223.1.2.2
subnet
223.1.3.1
223.1.3.2
network consisting of 3 subnets
Network Layer 4-29
Subnets
Subnet 1
223.1.1.0/24
 How long should the
Subnet 2
223.1.2.0/24
network prefix be?


Depends on number of
hosts on subnet
All hosts in subnet have
same subnetwork part of
the address.
Subnet 3
Typical info given to a host:
223.1.3.0/24
Your address is 223.1.3.1/24
Default route via 223.1.3.27
Subnet mask: /24
24 bits belong to the network
(called length of “CIDR” prefix)
Network Layer 4-30
Subnets
223.1.1.2
How many?
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
Network Layer 4-31
IP Addressing: CIDR
CIDR: Classless Inter-Domain Routing
subnet portion of address of arbitrary length
 address format: a.b.c.d/x, where x is # bits in subnet
portion of address

subnet
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
Network Layer 4-32
Subnets, masks, calculations
Example subnet: 192.168.5.0/24
Binary form
Dot-decimal
notation
IP address
11000000.10101000.00000101.10000010 192.168.5.130
Subnet mask
11111111.11111111.11111111.00000000
24 higher order bits set to 1
255.255.255.0
Network prefix:
(bitwise AND
11000000.10101000.00000101.00000000 192.168.5.0
of address,
mask)
Host part
(similar calculation,
with eg a ”wild
card” where the 32
– 24 lower order
bits set to 1)
00000000.00000000.00000000.10000010 0.0.0.130
Network Layer 4-33
IP Addressing:
Q: How does an ISP get block of addresses?
A: ICANN: http://www.icann.org/
Internet Corporation for Assigned Names and Numbers
 allocates addresses
 manages DNS
 assigns domain names, resolves disputes
 These services were originally performed under U.S.
Government contract by the Internet Assigned Numbers
Authority (IANA) and other entities.
 The IANA now is part of
ICANN.
Network Layer 4-34
IP Address Allocation:



ICANN is responsible for global coordination of the Internet Protocol
addressing systems and other naming and numbering standards.
Users are assigned IP addresses by Internet Service Providers (ISPs).
ISPs obtain allocations of IP addresses from a Local Internet Registry
(LIR) or National Internet Registry (NIR), or from their appropriate Regional
Internet Registry (RIR).
There are five RIRs :
AfriNIC, Africa
APNIC, Asia Pacific
ARIN, Canada, United States, Caribbean and North Atlantic Islands
LACNIC, Latin America and parts of the Caribbean region
RIPE NCC, Europe, Russia, Middle East, and Parts of Central Asia
(NIC Network Information Center)
Network
NetworkLayer
Layer 4-35
IP addresses: How to get one?
 Network (subnet) addresses are allocated from a
portion of its provider ISP’s address space.
20
3
9
bits
bits
bits
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
Network Layer 4-36
Hierarchical Addressing: Route Aggregation
 Hierarchical addressing allows efficient advertisement of routing information
 The “outside” does not need to know about subnets.
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
ISP #1
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISP #2
“Send me anything
with addresses
beginning
199.31.0.0/16”
Network Layer 4-37
Classless Address: example
 An ISP has an address block 122.211.0.0/16
 A customer needs max. 6 host addresses,
 ISP can e.g. allocate: 122.211.176.208/29
 3 bits enough for host part
 subnet mask 255.255.255.248
Dotted Decimal
Last 8 bits
Network
122.211.176.208
11010000
1st address
122.211.176.209
11010001
………….
…………………
…………
6th address
122.211.176.214
11010110
Broadcast
122.211.176.215
11010111
2013 Ali Salehson, Chalmers, CSE Networks and Systems
Reserved
Network Layer 4-38
CIDR Address Mask
CIDR Notation
Dotted Decimal
CIDR Notation
Dotted Decimal
/1
/2
/3
/4
/5
/6
/7
/8
/9
/10
/11
/12
/13
/14
/15
/16
128.0.0.0
192.0.0.0
224.0.0.0
240.0.0.0
248.0.0.0
252.0.0.0
254.0.0.0
255.0.0.0
255.128.0.0
255.192.0.0
255.224.0.0
255.240.0.0
255.248.0.0
255.252.0.0
255.254.0.0
255.255.0.0
/17
/18
/19
/20
/21
/22
/23
/24
/25
/26
/27
/28
/29
/30
/31
/32
255.255.128.0
255.255.192.0
255.255.224.0
255.255.240.0
255.255.248.0
255.255.252.0
255.255.254.0
255.255.255.0
255.255.255.128
255.255.255.192
255.255.255.224
255.255.255.240
255.255.255.248
255.255.255.252
255.255.255.254
255.255.255.255
2013 Ali Salehson, Chalmers, CSE Networks and Systems
Network Layer 4-39
Special IP Addresses
 Localhost and local loopback
 127.0.0.1 of the reserved 127.0.0.0
(127.0.0.0/8)
 Private IP-addresses
 10.0.0.0 – 10.255.255.255
 172.16.0.0 – 172.31.255.255
 192.168.0.0 – 192.168.255.255
(10.0.0.0/8)
(172.16.0.0/12)
(192.168.0.0/16)
 Link-local Addresses (stateless autoconfig)
 169.254.0.0 – 169.254.255.255
(169.254.0.0/16)
Network Layer 4-40
IP addresses: how to get one?
Q: How does host get IP address?
 manually hard-coded by system admin in a file

Windows:
Control Panel  Network Connections  Local Area Connection
 Properties  Internet Protocol (TCP/IP)  Properties
 UNIX: /etc/rc.config
 DHCP: Dynamic Host Configuration Protocol (RFC 2131)
dynamically gets address from a DHCP server
Network Layer 4-41
Dynamic Host Configuration Protocol
Goal: allows host to dynamically obtain its IP address from
network server when it joins network.



Host can renew its lease on address in use
Allows reuse of addresses (only hold address while connected)
Support for nomad users who want to join network (short time)
DHCP overview:
 host broadcasts “DHCP discover” message
 DHCP server responds with “DHCP offer” message
 host requests IP address: “DHCP request” message
 DHCP server sends address: “DHCP ACK” message
Network Layer 4-42
DHCP client-server scenario
DHCP
server
223.1.1.0/24
223.1.2.1
223.1.1.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
arriving DHCP
client needs
address in this
network
223.1.2.0/24
223.1.3.2
223.1.3.1
223.1.3.0/24
Network Layer 4-43
DHCP client-server scenario
DHCP server: 223.1.2.5
arriving
client
DHCP discover
src : 0.0.0.0, port 68
dest: 255.255.255.255, port 67
Your IPaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, port 67
dest: 255.255.255.255, port 68
Your IPaddr: 223.1.2.4
transaction ID: 654
Lease time: 3600 secs
DHCP request
src: 0.0.0.0, port 68
dest: 255.255.255.255, port 67
Req. IPaddr: 223.1.2.4
transaction ID: 654
DHCP ACK
time
src: 223.1.2.5, port 67
dest: 255.255.255.255, port 68
Your IPaddr: 223.1.2.4
transaction ID: 654
Lease time: 3600 secs
Network Layer 4-44
DHCP: more than an IP address
DHCP can return more than just allocated IP
address on subnet:



address of first-hop router (default gateway)
name and IP address of DNS sever
network mask (indicating network portion of
address)
Network Layer 4-45
DHCP: example
 Connecting laptop needs:
 its IP address, subnetmask
 address of first-hop router
 address of DNS server
DHCP
UDP
IP
Eth
Phy
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP

DHCP
UDP
IP
Eth
Phy
168.1.1.1
router with built-in
DHCP server

DHCP request encapsulated
in UDP, encapsulated in IP,
encapsulated in 802.3
Ethernet MAC frame
Ethernet frame broadcast
(FFFFFFFFFFFF) on LAN, received
at router running DHCP
server
Network Layer 4-46
DHCP: example
 DHCP server
formulates DHCP ACK
containing client’s IP
address, IP address of
first-hop router for
client, IP address of
DNS server
DHCP
UDP
IP
Eth
Phy
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
DHCP
UDP
IP
Eth
Phy

router with built-in
DHCP server

encapsulation of DHCP
server, frame forwarded
to client
client now knows its IP
address, IP address of
DNS server, IP address of
its first-hop router
Network Layer 4-47
NAT: Network Address Translation
 Router with NAT can translate network addresses
 Many internal (private) addresses translated to one (or few) external
(global) addresses.
 Gives freedom when configuring internal network
 fewer addresses needed from ISP or just one IP global 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
 can hide internal structure (devices not visible by outside world, a
security plus)
 Internal network should use non-routable (private)
addresses reserved for this purpose (RFC 1918)

10.0.0.0/8
172.16.0.0/12
192.168.0.0/16
Network Layer 4-48
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0.0/24
10.0.0.4
10.0.0.1
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source or destination (as usual)
Network Layer 4-49
NAT: network address translation
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 address
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
Network Layer 4-50
NAT: Network Address Translation
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40.186, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
10.0.0.1
1
2
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3: Reply arrives
dest. address:
138.76.29.7, 5001
3
10.0.0.4
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
10.0.0.2
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
Network Layer 4-51
NAT: Network Address Translation
 16-bit port-number field:
 65,000 simultaneous connections with a single
WAN-side address!
 NAT is controversial:
 routers should only process up to layer 3 ….
 violates end-to-end argument
• NAT possibility must be taken into account by application
designers, e.g., P2P applications
 address
shortage should instead be solved by
IPv6 ….
Network Layer 4-52
NAT: Traversal Problem
 client wants to connect to
server
server with address 10.0.0.1


server address 10.0.0.1 local to
LAN (client can’t use it as
destination addr)
only one externally visible
NATed address: 138.76.29.7
 solution1: statically configure
10.0.0.1
client
?
10.0.0.4
138.76.29.7
NAT
router
NAT to forward incoming
connection requests at given
port to server

e.g., (123.76.29.7, port 2500)
always forwarded to 10.0.0.1
port 2500
Network Layer 4-53
NAT: Traversal Problem
 solution 2: Universal Plug and
Play (UPnP) Internet Gateway
Device (IGD) Protocol. Allows
NATed host to:
 learn public IP address
(138.76.29.7)
 add/remove port mappings
(with lease times)
10.0.0.1
IGD
138.76.29.7
NAT
router
i.e., automate static NAT port
map configuration
Network Layer 4-54
NAT: Traversal Problem
 solution 3: relaying (used in p2p)



NATed host establishes connection to relay
external client connects to relay
relay bridges packets between two connections
2. connection to
relay initiated
by client
client
3. relaying
established
1. connection to
relay initiated
by NATed host
138.76.29.7
10.0.0.1
NAT
router
Network Layer 4-55
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-56
ICMP: Internet Control Message Protocol
 Control and error messages from network layer.
 All IP implementations must have ICMP support.
 ICMP messages carried in IP datagrams
 used by hosts & routers to communicate network-level
control information and error reporting
 Error reporting: e.g., unreachable network, host, ..
 Example: (used by ping command)
• Sends ICMP echo request
• Receives ICMP echo reply
 Any ICMP error message may never generate a new
one.
Network Layer 4-57
ICMP: message format
 ICMP message:
 type field: 1 byte
 code field: 1 byte
 Checksum: 2 bytes
 0s, (ID + Seq. #) or other
fields: 4 bytes
 Optional data or when
error reporting message
always include header of
IP datagram causing
error plus first 8 bytes of
its payload
Type Code description
0
0
echo reply (ping)
3
3
3
3
3
3
0
1
2
3
6
7
dest. network unreachable
dest. host unreachable
dest. protocol unreachable
dest. port unreachable
dest. network unknown
dest. host unknown
4
0
source quench
8
0
echo request (ping)
9
10
11
12
0
0
0
0
route advertisement
router discovery
TTL expired
bad IP header
Network Layer 4-58
Traceroute and ICMP
 Source sends series of UDP
segments to destination



First has TTL =1
Second has TTL=2, etc.
Unlikely port number
 When datagram sent with
TTL = n arrives to n:th
router:




TTL becomes 0
Router discards datagram
Router sends to source an
ICMP message “TTL
expired” (type 11, code 0)
Message is carried in IP
datagram with the router IP
address as source
 When ICMP message arrives,
source measures RTT
 Traceroute does this 3 times
Stop criteria
 UDP segment eventually
arrives at destination host
 Destination returns ICMP
message “destination port
unreachable” (type 3, code 3)
 When source gets this ICMP 3
times, traceroute stops.
Network Layer 4-59
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-60
IPv6: motivation
 initial motivation: 32-bit address space was
about 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
 128-bit addresses (2128 = 1038 numbers)
 Standard subnet size: 64 bits

Network Layer 4-61
IPv6 datagram format
priority: identify priority among datagrams in flow
flow Label: identify datagrams in same “flow.”
(concept of“flow” not well defined).
ver
pri
flow label
payload length next header hop limit
source address
(128 bits)
destination address
(128 bits)
data
32 bits
Network Layer 4-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”
 Neighbor and router discovery
 multicast group management functions

Network Layer 4-63
More slides
 IPv4 Fragmentation
 Datagram Forwarding Table
 Getting a datagram from source to destination
 IPv6-IPv4 Tunneling
Network Layer 4-64
IP Fragmentation & Reassembly
fragmentation:
 MTU (Maximum Transmission Unit)
reassembly
…
• More Fragments bit
• Datagram ID
• Fragment Offset (in 8-byte
units)
in: one large datagram
out: 3 smaller datagrams
…
largest possible data amount carried
by link-level frame.
 different link types, different
MTUs
 large IP datagrams will be divided
(“fragmented”) by host or router
 one datagram becomes several
datagrams
 “reassembled” only at final
destination
 IP header fields used to identify,
order related fragments
Network Layer 4-65
IP Fragmentation
Example
 4000 bytes datagram
 MTU = 1500 bytes
1480 bytes in data field
offset = 1480/8
length ID fragflag
=4000 =x
=0
offset
=0
One large datagram becomes
several smaller datagrams
length ID fragflag
=1500 =x
=1
offset
=0
length ID fragflag
=1500 =x
=1
offset
=185
length ID fragflag
=1040 =x
=0
offset
=370
Network Layer 4-66
Datagram forwarding table
Destination Address Range
Link Interface
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
0
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
1
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
2
otherwise
3
Q: but what happens if ranges don’t divide up nicely?
Network Layer 4-67
Longest prefix matching
longest prefix matching
when looking for forwarding table entry for given
destination address, use longest address prefix that
matches destination address (more on this coming soon)
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
DA: 11001000 00010111 00011000 10101010
which interface?
which interface?
Network Layer 4-68
Getting a datagram from source to dest.
forwarding table in A
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
IP datagram:
misc source
dest
fields IP addr IP addr
data
A
223.1.1.4
223.1.1.4
223.1.1.1
 Payload in datagram
remains unchanged, as it
travels source to
destination
 addr fields of interest here
1
2
2
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.1.3
223.1.3.1
223.1.3.27
223.1.2.2
E
223.1.3.2
Network Layer 4-69
Getting a datagram from source to dest.
Dest. Net. next router Nhops
misc
data
fields 223.1.1.1 223.1.1.3
223.1.1
223.1.2
223.1.3
Starting at A, given IP
datagram addressed to B:
 look up net. address of B
A
223.1.1.4
223.1.1.4
223.1.1.1
 find B is on same net. as A (B and
223.1.2.1
A are directly connected)
223.1.1.2
223.1.1.4
 link layer will send datagram
directly to B (inside link-layer
frame)
1
2
2
223.1.2.9
B
223.1.1.3
223.1.3.1
223.1.3.27
223.1.2.2
E
223.1.3.2
Network Layer 4-70
Getting a datagram from source to dest.
Dest. Net. next router Nhops
misc
data
fields 223.1.1.1 223.1.2.3
223.1.1
223.1.2
223.1.3
Starting at A, dest. E:
 look up network address of E
 E on different network
A
223.1.1.4
223.1.1.4
223.1.1.1
 routing table: next hop router to
E is 223.1.1.4
 link layer is asked to send
datagram to router 223.1.1.4
(inside link-layer frame)
 datagram arrives at 223.1.1.4
 continued…..
1
2
2
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.1.3
223.1.3.1
223.1.3.27
223.1.2.2
E
223.1.3.2
Network Layer 4-71
Getting a datagram from source to dest.
misc
data
fields 223.1.1.1 223.1.2.3
Arriving at 223.1.4, destined
for 223.1.2.2
 look up network address of E
Dest.
next
network router Nhops interface
223.1.1
223.1.2
223.1.3
A
 E on same network as router’s
interface 223.1.2.9
 router, E directly attached
 link layer sends datagram to
223.1.2.2 (inside link-layer
frame) via interface 223.1.2.9
 datagram arrives at 223.1.2.2!!!
(hooray!)
-
1
1
1
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.1.3
223.1.3.1
223.1.3.27
223.1.2.2
E
223.1.3.2
Network Layer 4-72
Transition from IPv4 to IPv6
 not all routers can be upgraded simultaneously
“flag days”
 how will network operate with mixed IPv4 and
IPv6 routers?
 tunneling: IPv6 datagram carried as payload in
IPv4 datagram among IPv4 routers
 no
IPv4 header fields
IPv4 source, dest addr
IPv6 header fields
IPv6 source dest addr
IPv4 payload
UDP/TCP payload
IPv6 datagram
IPv4 datagram
Network Layer 4-73
Tunneling (6in4 – static tunnel)
IPv4 tunnel
connecting IPv6 routers
A
B
IPv6
IPv6
A
B
C
IPv6
IPv6
IPv4
logical view:
E
F
IPv6
IPv6
D
E
F
IPv4
IPv6
IPv6
physical view:
flow: X
src: A
dest: F
data
A-to-B:
IPv6
src:B
dest: E
src:B
dest: E
Flow: X
Src: A
Dest: F
Flow: X
Src: A
Dest: F
data
data
B-to-C:
IPv6 inside
IPv4
B-to-C:
IPv6 inside
IPv4
flow: X
src: A
dest: F
data
E-to-F:
IPv6
Network Layer 4-74
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-75
Interplay between routing and forwarding
routing algorithm determines
end-end path through network
routing algorithm
forwarding table determines
local forwarding at this router
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
IP destination address in
arriving packet’s header
0111
1
3 2
Network Layer 4-76
Graph abstraction: costs
5
2
Graph: G = (N,E)
N = set of “Nodes” routers = { u, v, w, x, y, z }
u
v
2
1
x
3
w
3
1
5
z
1
y
2
E = set of “Edges” links = { (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Cost of link xw is c(x,w) = 3
Cost of link could be always 1 hop, or related directly
to delay or inversely to bandwidth, or any other metric
Question: What is the least-cost path between u and z?
Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Routing algorithm: is algorithm that finds least-cost path
Network Layer 4-77
Routing Algorithm Classification
Global or decentralized?
Static or dynamic routing?
Global:
 all routers have complete and
global knowledge about
topology, and all link-costs
 “link state” algorithms
Static:
 routes change slowly over
time, manually configured
Decentralized:
 router knows physicallyconnected neighbors, link costs
to neighbors
 exchange of info with neighbors
 Iteratively calculate the leastcost paths to other routers
 “distance vector” algorithms
Dynamic:
 routes change more quickly
 periodic update, or
 in response to link-cost
changes
Network Layer 4-78
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-79
A Link-State (LS) Routing Algorithm
Dijkstra’s algorithm
 link costs known to all nodes
Each node sends out “link
state multicasts” with
costs to its neighbors
 all nodes get same info
 Each node computes least
cost paths from itself to all
other nodes
 gives forwarding table for
that node
 iterative: after k iterations,
knows least cost path to k
destinations

Notation:
 c(x,y): link cost from node x to y.
Initially cost(x,y) = ∞ if not direct
neighbors
 D(v): Distance; current value of
cost of path from source to
destination v
 p(v): predecessor node, i.e.
previous node that is neighbor of v
along current path from the source
to node v
 N': set of Nodes whose least cost
path definitively known
Network Layer 4-80
Dijsktra’s Algorithm at node u
1 Initialization:
2 N' = {u}
3 for all nodes v
4
if v adjacent (directly attached neighbor) to u
5
then D(v) = c(u,v)
6
else D(v) = 
7
8 Loop
9
find node w not in N' such that D(w) is a minimum
10 add node 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 N in N'
Network Layer 4-81
Dijkstra’s algorithm: example
D(v) D(w) D(x) D(y) D(z)
Step
0
1
2
3
4
5
N'
p(v)
p(w)
p(x)
u
uw
uwx
uwxv
uwxvy
uwxvyz
7,u
6,w
6,w
3,u
∞
∞
5,u
∞
5,u 11,w
11,w 14,x
10,v 14,x
12,y
p(y)
p(z)
x
9
notes:


construct shortest path tree by
tracing predecessor nodes
ties can exist (can be broken
arbitrarily)
5
7
4
8
u
3
w
y
2
z
3
4
7
v
Network Layer
4-82
Dijkstra’s algorithm: example node u
v
Step
0
1
2
3
4
5
N'
u
ux
uxv
uxvy
uxvyw
uxvywz
w
D(v),p(v) D(w),p(w)
2,u
5,u
2,u
4,x
4,x
3,y
x
y
z
D(x),p(x)
1,u
D(y),p(y)

2,x
D(z),p(z)



4,y
4,y
2,x
5
2
u
v
2
1
x
3
w
3
1
5
z
1
y
2
Network Layer 4-83
Dijkstra’s algorithm: forwarding table
Resulting shortest-path tree from node u as root:
v
w
u
Root
z
x
y
Resulting forwarding table in u:
destination
via link
cost
v
x
(u,v)
(u,x)
2
y
(u,x)
2
w
(u,x)
3
z
(u,x)
4
1
Network Layer 4-84
Dijkstra’s algorithm, discussion
Algorithm complexity: n nodes (root node is excluded)
 each iteration: need to check all nodes, not in N’
 n(n+1)/2 comparisons: Order of (n2)
Oscillations possible:
 e.g., if link cost = delay-based or traffic-based, dynamically
variable metric
 must avoid these metrics
But:
 Good for small networks
 Link-cost changes are not frequent, more stable
network
 Faster to converge when changes in link-costs
Network Layer 4-85
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-86
Distance Vector (DV) Algorithm
Bellman-Ford Equation:
Define
dx(y) := cost of least-cost path from x to y
If v is any neighbor to x with link cost c(x,v) and has dv(y) as leastcost path to y
Then the DV estimate:
dx(y) = min { c(x,v) + dv(y) }
cost from neighbor v to destination y
cost to neighbor v
Network Layer 4-87
min taken over all neighbors v of x
Distance vector (DV) algorithm
Basic idea:
 distributed, asynchronous, iterative
 from time-to-time, each node sends to neighbors only
its own distance vector DV estimate
 When a node x receives new DV estimate from
neighbor v, it updates its own DV using Bellman-Ford
equation:
dx(y) ← minv {c(x,v) + dv(y)} for each node y ∊ N
 Under normal conditions, when information comes in
about new link costs:



The estimate dx(y) converge to the actual least cost
Routing table recalculated
New results sent out to all neighbors
Network Layer 4-88
Bellman-Ford: example
Nodes v, x & w are the neighbors of u
5
2
u
v
2
1
x
3
w
3
1
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
5
z
1
y
2
BF equation says:
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
Node x that achieves minimum is the next
hop in least-cost path to z ➜ forwarding table
Network Layer 4-89
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 7 1 0
2
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
from
from
x
x ∞∞ ∞
y ∞∞ ∞
z 7 1 0
y
7
1
z
time
Network Layer 4-90
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
x ∞∞ ∞
y ∞∞ ∞
z 7 1 0
x 0 2 3
y 2 0 1
z 7 1 0
x 0 2 3
y 2 0 1
z 3 1 0
from
cost to
x y z
cost to
x y z
cost to
x y z
x 0 2 7
y 2 0 1
z 7 1 0
x 0 2 3
y 2 0 1
z 3 1 0
from
from
cost to
x y z
cost to
x y z
x 0 2 7
y 2 0 1
z 3 1 0
2
x
y
7
1
z
cost to
x y z
from
from
from
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
from
node x table
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 3 1 0
time
Network Layer 4-91
DV: link cost changes (good news)
Link cost changes: decreased cost
 node detects local link cost change
1
4
 updates routing info, recalculates
distance vector
 if DV changes, notify neighbors
x
y
50
1
z
At time t0, y detects the link-cost change, updates its DV,
and informs its neighbors.
“good news
travels fast”
At time t1, z receives the update from y and updates its table.
It computes a new least cost to x and sends its neighbors its DV.
At time t2, y receives z’s update and checks its distance table.
y’s least costs do not change and hence y does not send any
update to z.
Network Layer 4-92
DV: link cost changes (bad news)
Link cost changes: increased cost
60
 bad news travels slow - “count to
infinity” problem!
 44 iterations before algorithm stabilizes!



x
y
50
1
z
y already knows z has cost 5 to reach x
y therefore announces cost 6 to reach x
z announces cost is now 7, etc..
Poisoned reverse:
 If z routes through y to get to x:

4
“bad news
travels slow”
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?
Network Layer 4-93
Comparison of LS and DV algorithms
Message complexity
 LS: with n nodes, E links,
O(nE) messages sent
 DV: exchange between
neighbors only
Convergence due changes
 LS:
may have oscillations
 fast convergence
 DV:
 may be routing loops
 count-to-infinity problem
 slow convergence

Robustness: what happens
if router malfunctions?
LS:



node can advertise
incorrect link cost
each node computes only
its own table
limited damage
DV:


node can advertise
incorrect path cost
each node’s table used by
others
• error propagates through
network
Network Layer 4-94
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-95
Hierarchical Routing
Our routing study thus far - idealization
 all routers identical
 network “flat”
… not true in practice
scale: millions of destinations!
administrative autonomy
 can’t store all destinations in
 Internet = network of networks
routing tables!
 LS routing info exchange would
swamp links!
 DV would never terminate
 each network administrator
may want to control routing in
its own network
Network Layer 4-96
Hierarchical Routing
 aggregate routers into regions, “autonomous systems” (AS)
 Internet: > 39,000 AS
 routers in same AS run same routing protocol
 “intra-AS” routing protocol
 routers in another AS can run different intra-AS routing protocol
border router
 at “edge” of its own AS
 with direct link to router in another AS
Network Layer 4-97
Interconnected ASs
3c
3b AS3
3a
2a
1c
AS1
1a


2b
AS2
1b
1d
Forwarding table
configured by both
intra- and inter-AS
routing algorithms
2c
Intra-AS
Routing
algorithm
Inter-AS
Routing
algorithm
Forwarding
table
intra-AS sets entries for internal destinations
inter-AS sets entries for external destinations
Network Layer 4-98
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-99
Intra-AS Routing
 also known as Interior Gateway Protocols (IGP)
 most common Intra-AS routing protocols:
RIP: Routing Information Protocol [DV]
 OSPF: Open Shortest Path First [LS]
 IS-IS: Intermediate System-Intermediate
System [LS]


EIGRP: Enhanced Interior Gateway Routing
Protocol (Cisco proprietary)
Network Layer 4-100
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-101
RIP ( Routing Information Protocol)
 distance vector algorithm
 included in BSD-UNIX Distribution 4.3 in 1982
 distance metric: number of hops (max = 15 hops)
 Version 1 classful and version 2 classless
From router A to subnets:
u
v
A
z
C
B
w
x
D
destination hops
u
0
v
1
w
1
x
2
y
2
z
1
y
Network Layer 4-102
RIP advertisements
 distance vectors are exchanged among neighbors
every 30 sec via Response Message (also called
advertisement)
 each advertisement: list of up to 25 destination
subnets within AS
 If no advertisement heard after 180 sec  neighbor
or link declared dead (unreachable).





Routes via neighbor invalidated
New advertisements sent to other neighbors
Link failure info propagates to entire network
Poisoned reverse used with max hop count 15
Infinite distance is 16 hops
 RIP v.2 also supports route aggregation (1998)
Network Layer 4-103
RIP Table processing
 RIP routing tables managed by application-level
process called routed (route daemon)
 advertisements periodically sent in UDP packets (port
520) using broadcast (or multicast, RIP v.2)
routed
routed
transport
(UDP)
network
(IP)
link
physical
transport
(UDP)
forwarding
table
forwarding
table
network
(IP)
link
physical
Network Layer 4-104
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-105
OSPF (Open Shortest Path First)
 “open”: just means publicly available (RFC 2328)
 uses Link State algorithm
 complete topology map built at each node
 route computation using Dijkstra’s algorithm
 works in larger networks (hierarchical structure with areas)
 OSPF advertisements sent within area via flooding.
 carried in OSPF messages directly over IP with protocol number
89 (no UDP- or TCP-transport)
 sent at least every 30 minutes
Network Layer 4-106
OSPF “advanced” features
 security: all OSPF messages can be authenticated (to
prevent malicious intrusion)
 multiple same-cost paths allowed
 Send HELLO messages to establish adjacencies with
neighbors to check operational links
 hierarchical OSPF in large domains.
Network Layer 4-107
Hierarchical OSPF
boundary router
backbone router
backbone
area
border
routers
Area 3
internal
routers
Area 1
Area 2
Network Layer 4-108
Hierarchical OSPF
 two-level hierarchy: local areas, one backbone (area 0).
Link-state advertisements only in area
 each node has detailed area topology; only knows
direction (shortest path) to subnets in other areas.
 area border routers: “summarize” subnets in own area,
advertise to other area border routers.
 backbone routers: run OSPF routing limited to backbone.
 boundary routers: connect to other AS’s.

Network Layer 4-109
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-110
Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol)



the de facto standard routing protocol on the Internet
Complex protocol
Communicates over TCP port 179 with authentication
 BGP provides each AS a means to:
o Obtain prefix reachability information from
neighboring ASs.
o Propagate reachability information to all ASinternal routers.
o Determine “good” routes to prefixes based on
reachability information and policy.
Network Layer 4-111
BGP basics
 pairs of routers (BGP peers) exchange routing info over
semi-permanent TCP connections: BGP sessions


BGP sessions need not correspond to physical links.
advertising paths to different destination network prefixes (“path
vector” protocol)
 when AS3 advertises a prefix to AS1:
 AS3 promises it will forward datagrams towards that prefix.
 AS3 can aggregate prefixes in its advertisement
3c
3b
other
networks
3a
BGP
message
AS3
2c
1c
1a
AS1
1d
2a
1b
2b
other
networks
AS2
Network Layer 4-112
Distributing Reachability Info
 With “external BGP” eBGP session between 3a and
1c, AS3 sends prefix reachability info to AS1.
 1c can then use “internal BGP” iBGP to distribute
new prefix info to all routers in AS1
 1b can then re-advertise new reachability info to
AS2 over 1b-to-2a eBGP session
 when router learns of new prefix, it creates entry for
prefix in its forwarding table.
eBGP session
3c
3b
other
networks
iBGP session
3a
BGP
message
AS3
2c
1c
1a
AS1
1d
2a
1b
2b
other
networks
AS2
Network Layer 4-113
Path attributes & BGP routes
 advertised prefix includes BGP attributes.

prefix + attributes = “route”
 two important attributes:


AS-PATH: contains ASs through which prefix can be reached:
e.g., AS 67, AS 17
NEXT-HOP: indicates specific AS router to next-hop AS.
 when gateway router receives route advertisement, uses
import policy to accept or decline.

May or may not accept/announce everything to/from peers
 Router may learn about more than 1 route to some prefix.
Router must select route based on:



Policy decision
Shortest AS_PATH
Closest NEXT_HOP router
Network Layer 4-114
BGP messages
 BGP messages exchanged using TCP.
 BGP messages:
OPEN: opens TCP connection to peer and
authenticates sender
 UPDATE: advertises new path (or withdraws old)
 KEEPALIVE: keeps connection alive in absence of
UPDATES; also ACKs OPEN request
 NOTIFICATION: reports errors in previous message;
also used to close connection

Network Layer 4-115
BGP routing policy (1)
legend:
B
W
provider
network
X
A
customer
network:
C
Y
 A,B,C are provider networks
 x,w,y are customers (of provider networks)
 x is dual-homed: attached to two networks
x does not want to route from B via x to C
 .. so x will not advertise to B a route to C

Network Layer 4-116
BGP routing policy (2)
legend:
B
W
provider
network
X
A
customer
network:
C
Y
 A advertises to B path A-w
 B advertises to x path B-A-w
 Should B advertise path B-A-w to C?
 No
way! B gets no “revenue” for routing C-B-A-w
since neither w nor C are B’s customers
 B wants to force C to route to w via A
 B wants to route only to/from its customers!
Network Layer 4-117
Why different Intra- & Inter-AS routing?
Policy:
 Inter-AS: admin wants control over how its traffic routed,
who routes through its net.
 Intra-AS: single admin, so no policy decisions needed
Scale:
 hierarchical routing saves routing table size, reduced
update traffic
Performance:
 Inter-AS: policy may dominate over performance
 Intra-AS: can focus on performance
Network Layer 4-118
Growth of the BGP table: 1994 to 2011
http://bgp.potaroo.net
Network Layer 4-119
Growth of the BGP table: 1994 to Present
http://bgp.potaroo.net
Network Layer 4-120
Chapter 4: Network Layer
 4.1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the
Internet



RIP
OSPF
BGP
 4.7 Broadcast and
multicast routing
Network Layer 4-121