COMP 3234B
Computer and Communication Networks
2nd semester 2020-2021
Network Layer (I)
Prof. C Wu
Department of Computer Science The University of Hong Kong
Roadmap
Network layer
Principles behind network-layer services (ILO1) forwarding vs. routing
network service models
Router (ILO1)
IP (ILO2,5) DHCP
NAT
ICMP (ILO2)
Routing algorithms (ILO3) Routing in the Internet (ILO2,3)
application
transport
network
network
link
physical
Network layer
Deliver segments from sending host to receiving host
sending side: encapsulates segments into datagrams
receiving side: delivers segments to transport layer
Ann
application
ttrransport
network
network
link
physical
Where are network-layer protocols implemented?
Network-layer protocols implemented in every host and router
router examines header fields in all datagrams passing through it
application
transport
network
data link
physical
network
network
data link
data link
network
physical
physical
data link
physical
network
network
data link
data link
physical
physical
network
network
data link
data link
physical
physical
network
data link
physical
application
transport
network
data link
physical
network
data link
network
physical
network
data link
data link
physical
physical
Two key network-layer functions
Forwarding: move datagrams from an incoming link to an outgoing link within a
router
Routing: determine route/path taken by datagrams from source to destination
involves all of a network’s routers, collective interactions (routing algorithm)
Analogy
routing: process of planning trip from Kennedy Town to Tai Po
forwarding: process of getting through a single interchange on the trip
application
transport
network
data link
physical
network
network
data link
data link
network
physical
data link
physical
physical
physical
network
network
data link
data link
physical
network
network
data link
data link
physical
physical
network
data link
physical
application
transport
network
data link
physical
network
data link
network
physical
network
data link
data link
physical
physical
Data plane and control plane at each router
Data plane:
carries out local/per router forwarding function: determining how
datagram arriving on router input port is forwarded to router output port
Every router has a forwarding table Header:
destination address (datagram network)
Routing algorithm decides the values to be inserted into forwarding tables
3
1
2
Data plane and control plane at each router (cont’d)
Control plane:
carries out network-wide logic, e.g., routing algorithms which determine how datagram is routed among routers along end-end path from source host to destination host
routing algorithm components in every router interact in the control plane
4.1
•
OVERVIEW OF NETWORK LAYER
309
Routing Algorithm
Routing algorithm
control plane
data plane
Control plane Data plane
Local forwarding table
header
0100
0110
0111
1001
output
3 2 2 1
Values in arriving packet’s header
values in arriving packet header
1101
1 2
0111
3
1
2
3
Figure 4.2 ♦ Routing algorithms determine values in forward tables
Network service models
Service model: characteristics of a channel transporting packet from sender to receiver
Internet’s network layer provides best-effort connectionless service no guarantees for bandwidth, no-loss, in-order delivery, delivery delay
datagram network — which provides network-layer connectionless service
There are other types of networks providing these guarantees
virtual-circuit (VC) network — which provides network-layer
connection service
e.g., ATM (Asynchronous Transfer Mode) network
but still packet switching, instead of circuit switching!
Datagram network
Packet forwarded at the network layer according to the destination address contained in packet header
packets between same source-dest pair may take different paths
No call setup/teardown at the network layer at all
routers: no state about any end-to-end connections
Example
Internet
Router
Two key router functions:
running routing algorithms
forwarding datagrams from incoming link(s) to outgoing link(s)
Architecture overview:
routing, management control plane (software) operates in millisecond time frame
forwarding data plane
(hardware) operates in nanosecond timeframe
routing processor
high-speed
high-seed switching
fabric
router input ports
router output ports
Input ports
Physical layer function:
bit level reception
Data link layer function, e.g., Ethernet
link layer
protocol (receive)
lookup, forwarding
queueing
line termination
switchin
switch fabric
g
Network layer forwarding function:
using header field values, look up 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 switching fabric, buffer datagrams
Forwarding table in a router
maps destination addresses to link interfaces
4 billion possible IPv4 addresses (entries)=>use ranges instead!
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
Link Interface
0
1
2
3
Longest prefix matching
When looking for forwarding table entry for given destination address, use longest address prefix that matches destination address
Destination Address Range
Link interface
11001000 00010111 00010*** *********
0
11001000 00010111 00011000 *********
1
11001000 00010111 00011*** *********
2
otherwise
3
Examples
DA: 11001000 00010111 00010110 10100001
Which interface? Which interface?
DA: 11001000 00010111 00011000 10101010
Switching fabrics
Transfer packet from input buffer to appropriate output buffer
Switching rate: rate at which packets can be transferred from inputs to outputs
if there are N input ports, desirable switching rate is N times line rate
Three types of switching fabrics:
Switching via memory
– datagram copied to processor memory
– speed limited by memory
bandwidth
i.e., how many bytes per second
can be written into or read from memory
Switching via a bus
Switching via an interconnection network
cross bar switch: 2N buses connecting N input ports to N output ports
– datagram copied from input
port memory to output port memory via a shared bus –
– bus contention: switching speed limited by bus speed
memory
memory
bus
crossbar
Input port queueing
Fabric slower than input ports combined => queueing may occur at input queues (buffer)
queueing delay, and loss due to input buffer overflow!
Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forward
switch fabric
switch fabric
output port contention: only one red datagram can be transferred;
lower red packet is blocked
one packet time later: green packet
experiences HOL blocking
Output ports
Datalinklayer Physicallayer function function
datagram buffer
queueing
link layer
protocol (send)
line termination
Network layer functions:
switching
switch fabric
buffering: required when datagrams arrive from fabric faster than the transmission rate
scheduling: choose among queued datagrams the next datagram to send on link
queueing delay, and loss due to output buffer overflow!
Output port scheduling policies
FIFO (first in first out): send in order of arrival to queue
discard policy: if datagram arrives to full queue, which datagram to
discard?
tail drop: drop arriving packet priority: drop/remove on priority basis random: drop/remove randomly
packet arrivals
queue (waiting area)
packet link departures
(server)
Output port scheduling policies (cont’d)
Priority scheduling: send highest priority queued datagram
multiple classes with different priorities
class may depend on marking or other header info, e.g. IP source/dest, port numbers, etc.
high priority queue (waiting area)
arrivals
departures
classify link
low priority queue (server) (waiting area)
2
134
5
arrivals
packet in service
departures
1
3
2
4
5
1324 5
Output port scheduling policies (cont’d)
Round Robin (RR):
multiple classes
cyclically scan class queues, sending one datagram from each class (if available)
1
2
4
5
3
arrivals
packet in service
departures
1
3
2
4
5
1324 5
Output port scheduling policies (cont’d)
Weighted Fair Queueing (WFQ):
generalized Round Robin
each class gets weighted amount of service in each cycle
Network-layer protocols
transport layer: TCP, UDP
IP protocol
• addressing conventions
• datagram format
• packet handling conventions
routing protocols
• path selection
• RIP, OSPF, BGP
forwarding table
ICMP protocol
• error reporting
• router “signaling”
link layer
physical layer
network layer
IP (Internet Protocol)
Datagram format (IPv4)
IP protocol version number
header length (bytes)
32 bits
total datagram length (bytes)
for fragmentation/ reassembly
Recomputed by each router
e.g. timestamp, record route taken.
ver
head. len
16-bit identifier
time to live
type of service
upper layer
flgs
length
fragment offset
32 bit source IP address
header checksum
32 bit destination IP address
options (if any)
data (variable length,
typically a TCP or UDP segment)
6 bits used for indicating differentiated
“type” of data services and 2 bits used for ECN
TTL: max number of remaining hops (decremented at
each router)
upper layer protocol to deliver payload to
how much overhead?
v 20 bytes of TCP
v 20 bytes of IP
v =40bytes+app layer overhead
IP datagram fragmentation & reassembly
Network links have MTU (Maximum Transmission Unit)
maximum amount of data a link-layer frame can carry
different link types, different MTUs MSS=MTU-40 (for IPv4)
Large IP datagram divided (fragmented) at routers
one large datagram becomes several small datagrams (‘‘fragments”)
Reassembled only at final destination host
IP header bits used to identify, order related fragments
fragmentation:
in: one large datagram out: 3 smaller datagrams
reassembly
…
…
IP datagram fragmentation & reassembly (cont’d)
Example:
a 4000-byte datagram MTU = 1500 bytes
(typical MTU for Ethernet)
length =4000
ID =x
One large datagram becomes several smaller datagrams
length =1500
fragflag =0
offset =0
ID =x
fragflag =1
offset =0
1480 bytes in data field
offset = 1480/8
length ID fragflag offset =1500 =x =1 =185
length ID fragflag offset =1040 =x =0 =370
specified in units of 8-byte chunks
IP addressing (IPv4)
Interface: boundary between host/router and physical link
router typically has multiple interfaces
host typically has one interface
How are interfaces connected (with no intervening router)
wired Ethernet interfaces connected by Ethernet switches
wireless WiFi interfaces connected by WiFi base station (switch)
223.1.1.1
223.1.1.2
223.1.1.4
223.1.2.1 223.1.2.9
223.1.1.3
223.1.3.27
223.1.3.1
223.1.2.2
223.1.3.2
IP addressing (IPv4)
223.1.1.1
223.1.1.2
223.1.1.4
223.1.2.1 223.1.2.9
IP address: 32-bit identifier for host/router
223.1.3.27
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223.1.1.3
223.1.2.2
223.1.3.2
1
1
223
1
IP address is indeed associated with each interface
Subnet
IP address contains
subnet part (high-order bits) host part (low-order bits)
What’s a subnet ?
a network in which device interfaces can physically reach each other without intervening router
interfaces in a subnet have same subnet part of IP address
e.g., 200.23.16.0/23
/23: shows the leftmost 23 bits define the subnet address
223.1.1.1
223.1.1.2
223.1.1.4 223.1.2.9
223.1.2.1
223.1.1.3
223.1.3.1
223.1.2.2 223.1.3.27
subnet
223.1.3.2
subnet part
host part
network consisting of 3 subnets
11001000 00010111 00010000 00000000 200.23.16.0/23
Subnet (cont’d)
Subnet mask: a 32-bit number that identifies the subnet/network address part in an IPv4 address
it is decided by setting the network bits to all 1’s and host bits to all 0’s
IP#address# Subnet#mask#
Network## address#
Host## address#
11011111##00000001##00000001##00000010#
(#Decimal:#223.1.1.2#)#
11111111##11111111##11111111##00000000#
(#Decimal:#255.255.255.0)#
11011111##00000001##00000001##00000000# (#Decimal:#223.1.1.0#)#
00000000##00000000##00000000##00000010#
Subnet (cont’d)
223.1.1.0/24
223.1.1.1
223.1.1.2
223.1.1.4 223.1.2.9
223.1.2.0/24
223.1.1.1
223.1.1.2
223.1.1.4 223.1.2.9
223.1.2.1
223.1.2.1
223.1.1.3
223.1.3.1
223.1.2.2 223.1.3.27
223.1.1.3
223.1.3.1
223.1.2.2 223.1.3.27
subnet
223.1.3.2
subnet
223.1.3.2
<=
subnet mask: /24
or 255.255.255.0
or 255.255.255.0/24
223.1.3.0/24
network consisting of 3 subnets
Subnet (cont’d)
How many subnets?
“Recipe” to decide subnets
detach each interface from host/router each of the isolated networks is a subnet
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4
223.1.9.2
223.1.7.0
223.1.9.1
223.1.2.6 223.1.2.1
223.1.8.1
223.1.2.2
223.1.8.0
223.1.3.1
223.1.7.1
223.1.3.27 223.1.3.2
Required reading
Computer Networking: A Top-Down Approach (7th Edition) Ch 4.1, 4.2, 4.3.1, 4.3.2, 4.3.3