PowerPoint Presentation
Computer Systems
Week 10a – Network Layer
Based on material and slides from
Computer Networking: A Top Down
Approach, 7th
Edition – Chapter 4
,
Pearson/
Slide# 2 of 48
Lecture Objective
The objective of this lecture is to understand the
conceptual aspects of network layer protocols &
services
Slide# 3 of 48
Lecture Outline
Introduction to Network Layer
Forwarding vs. Routing
Network Service Model
Router Architecture (Input, Output, Switching)
The Network Layer
IP Addressing (Subnets, CIDR)
DHCP & Network Address Translation
Summary
Slide# 4 of 48
Recap – Network Layers
Slide# 5 of 48
Introduction – Network Layer
Network layer implements the
host-to-host communication
service
On the sending side, it
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
Slide# 6 of 48
Two Key Network Layer Functions
Analogy:
Routing: process of
planning trip from source
to destination
Forwarding: process of
getting through single
interchange
Forwarding: move
packets from router’s input
to appropriate router
output
Routing: determine route
taken by packets from
source to destination
Routing Algorithms
Slide# 7 of 48
Interplay between Routing & Forwarding
routing algorithm determines
end-end-path through network
forwarding table determines
local forwarding at this router
Slide# 8 of 48
Connection Setup
3rd
important function in some network architectures:
ATM, frame relay, X.25
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 Virtual Circuits (VCs))
transport: between two processes
https://en.wikipedia.org/wiki/Asynchronous_transfer_mode
https://en.wikipedia.org/wiki/Frame_Relay
https://en.wikipedia.org/wiki/X.25
Slide# 9 of 48
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
Slide# 10 of 48
Network Service Model
The Internet’s Network Layer provides a single
service known as Best-Effort service.
With best-effort, packets are neither guaranteed
to be received in order, nor is their eventual
delivery guaranteed. Similarly, no guarantee for
end-to-end delay or minimal bandwidth.
Slide# 11 of 48
Router Architecture – Overview
Two key router functions:
run routing algorithms/protocol (RIP, OSPF, BGP)
forwarding datagrams from incoming to outgoing link
https://en.wikipedia.org/wiki/Routing_Information_Protocol
https://en.wikipedia.org/wiki/Open_Shortest_Path_First
https://en.wikipedia.org/wiki/Border_Gateway_Protocol
Slide# 12 of 48
Input Port Functions
Physical layer:
bit-level reception
Data link layer:
e.g., Ethernet
Decentralized Switching:
given datagram dest., 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
Slide# 13 of 48
Input Port – Forwarding Tables
Slide# 14 of 48
Input Port – Forwarding Tables
Q: What happens if ranges don’t divide up so nicely?
Destination
Address Range
Destination Address Range
(Binary)
Link
Interface
200.23.16.0
through
200.23.23.255
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
0
200.23.24.0
through
200.23.24.255
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
1
200.23.25.0
through
200.23.31.255
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
2
otherwise otherwise
3
Slide# 15 of 48
Longest Prefix Matching
DA: 11001000 00010111 00011000 10101010
Examples:
DA: 11001000 00010111 00010110 10100001
which interface?
When looking for forwarding table entry for given
destination address, use longest address prefix
that matches destination address.
Destination Address Range
11001000 00010111 00010*** *********
11001000 00010111 00011000 *********
11001000 00010111 00011*** *********
otherwise
Link interface
0
1
2
3
Slide# 16 of 48
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 of line rate is desirable
Three types of switching fabrics
1) Memory
2) Bus
3) Crossbar
Slide# 17 of 48
Switching Fabrics
Slide# 18 of 48
Switching Fabrics – 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)
Example: Cisco’s Catalyst 8500 switches
Slide# 19 of 48
Switching Fabrics – Bus
Datagram from input port memory to output port memory
via a shared bus, without intervention by the routing
processor.
Input port pre-pends a switch-internal label (header) and
transmits the packet onto the bus. Header matching at
output ports.
Bus Contention: switching speed limited by bus
bandwidth
32 Gbps bus, Cisco 6500: sufficient speed for access
(small LANs) and enterprise routers.
Slide# 20 of 48
Switching Fabrics – Crossbar
Overcome bus bandwidth limitations – 2N buses that
connect N input and N output ports.
Banyan networks, crossbar, other interconnection nets
initially developed to connect processors in
multiprocessor
Support for forwarding multiple packets in parallel i.e. a
crossbar switch is non-blocking.
Advanced Design: fragmenting datagram into fixed
length cells, switch cells through the multiple switching
fabrics.
Cisco 12000: switches 60 Gbps through the
interconnection network
Slide# 21 of 48
Output Ports
Buffering required when datagrams arrive from fabric faster
than the transmission rate
Scheduling discipline chooses among queued datagrams
for transmission
Datagram (packets) can be lost
due to congestion, lack of buffers
Priority scheduling – who gets best
performance, network neutrality
Slide# 22 of 48
Output Port Queueing
Buffering when arrival
rate via switch exceeds
output line speed
Queueing (delay) and
loss due to output port
buffer overflow!
Packet-dropping and
marking policies i.e.
Active Queue
Management (AQM)
algorithms e.g.
► Random Early
Detection (RED)
algorithm
Slide# 23 of 48
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 TCP flows, buffering equal
to:
Slide# 24 of 48
Input Port Queueing
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
Slide# 25 of 48
The Internet Network Layer
Host, router network layer functions:
Slide# 26 of 48
IP Datagram Format (IPv4)
How much overhead?
20 bytes of TCP
20 bytes of IP
= 40 bytes + app layer overhead
IP protocol version
number
header length
(bytes)
upper layer protocol
to deliver payload to
“type” of data
max number
remaining hops
(decremented at
each router)
Total datagram
length (bytes)
For
fragmentation/
reassembly
e.g. timestamp,
record route
taken, specify
list of routers
to visit.
Slide# 27 of 48
IP Fragmentation, Reassembly
Network links have MTU (Max. Transmission Unit) –
largest possible link-level frame
different link types (along the path) may have different MTUs
Large IP datagram divided (“fragmented”) within network
one datagram becomes several datagrams
“reassembled” only at final destination
IP header bits used to identify, order related fragments
Slide# 28 of 48
IP Fragmentation, Reassembly
Slide# 29 of 48
IP Fragmentation, Reassembly
Example:
4000 byte
datagram
MTU = 1500 bytes
ID
=x
offset
=0
fragflag
=0
length
=4000
ID
=x
offset
=0
fragflag
=1
length
=1500
ID
=x
offset
=185
fragflag
=1
length
=1500
ID
=x
offset
=370
fragflag
=0
length
=1060
one large datagram becomes
several smaller datagrams
1480 bytes in
data field
offset =
1480/8
Slide# 30 of 48
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)
Each interface is
associated with its own IP
address
223.1.1.1 = 11011111 00000001 00000001 00000001
223 1 11
Slide# 31 of 48
IP Addressing – 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
can physically reach
each other without
intervening router
Slide# 32 of 48
IP Addressing – Subnets
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
Slide# 33 of 48
IP Addressing – Subnets
How many subnets
are present in this
network?
Slide# 34 of 48
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
Slide# 35 of 48
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”
Slide# 36 of 48
DHCP: Dynamic Host Configuration Protocol
Goal: allow host to dynamically obtain its IP address from
network server when it joins the 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
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
Slide# 37 of 48
DHCP: Dynamic Host Configuration Protocol
Arriving DHCP
client needs
address in this
network
Slide# 38 of 48
DHCP
Client
Server
Scenario
Slide# 39 of 48
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)
Slide# 40 of 48
IP Addressing: How to get one?
Q: How does network get subnet part of IP address?
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
Slide# 41 of 48
IP Addressing: 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
Slide# 42 of 48
NAT: Network Address Translation
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, destination (as usual)
Slide# 43 of 48
NAT: Network Address Translation
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, or visible to the
outside world (a security plus)
Slide# 44 of 48
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.
Slide# 45 of 48
NAT: Network Address Translation
1: host 10.0.0.1
sends datagram to
128.119.40.186, 80
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
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
Slide# 46 of 48
NAT: Network Address Translation
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
►violates end-to-end argument
NAT possibility must be taken into account by app
designers, e.g., P2P applications
► address shortage should instead be solved by IPv6 (we
have approx 3.4×10³⁸ possible addresses in IPv6) e.g.
2001:0db8:0000:0000:0000:8a2e:0370:7334
https://en.wikipedia.org/wiki/IPv6
Slide# 47 of 48
Summary
In this lecture, we have seen:
The principles behind network layer services, network
layer service models and forwarding vs. routing functions.
How a router works, with its input/output ports, switching
fabric and routing processor.
The Network Layer, IP addressing, Subnets, CIDR, DHCP
and Network Address Translation.
Slide# 48 of 48
References / Links
Chapter #4: The Network Layer: Data Plane, Computer
Networking: A Top-Down Approach (7th
edition) by Kurose
& 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43
Slide 44
Slide 45
Slide 46
Slide 47
Slide 48