Transcript 3rd Edition: Chapter 4 - Universidad de Sevilla

Departamento de
Tecnología Electrónica
Computer Networking
Chapter 4
Network layer
Some of these slides are
given as material with
copyright from:
Computer Networking:
A Top Down Approach ,
5th edition.
Jim Kurose, Keith Ross
Addison-Wesley, April
2009.
Chapter 4: Network Layer
Our goals:
 understand principles behind Network Layer services:
 Network Layer service models
 forwarding versus routing
 inside the router

Example: implementation on the Internet
Network Layer
4-2
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
IP functioning
Network Layer
4-3
Network Layer





transport segment (T_PDUs)
from sending to receiving
host
The sending side
encapsulates T_PDUs into
datagrams (N_PDU)
The receiving side delivers
T_PDUs to transport layer
Network Layer protocols in
every host, including routers
router examines header
fields (N_PCI) in all the IP
datagrams (N_PDU), that
pass through it
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
Network Layer
application
transport
network
data link
physical
4-4
Network Layer




All layers from application to network are
implemented in software.
Data Link and Physical are implemented in
hardware, known as network interface card
or NIC.
Each interface implements a particular Data
Link and Physical protocol, known as link
technology, network technology or just
technology.
Each interface has associated a link address,
known as physical address or MAC address
with 48 bits that identifies it.
Application
Transport
Software
Network
Data Link
Hardware
Physical
NIC
 For example, 00:BF:3C:23:45:30
More about physical addresses in the data
link layer…
Network Layer
4-5
Network Layer


In general, end systems usually use only one network
interface, although may have several ones (e.g., ethernet
and Wi-Fi).
Routers have several network interfaces.
 Each one is connected to other routers or end systems.
network
link
link
link
physical
physical
physical
application
transport
network
link
physical
Network Layer
4-6
Network Layer


Data Link Layer, through network interface, offers to Network
Layer a service of N_PDUs deliver between routers or end
systems connected by physical media and devices that
implements up to Data Link Layer.
Routers and end systems connected in this way are in the same
broadcast domain.
network
application
transport
network
link
physical
link
link
link
link
link
link
physical
physical
physical
physical
physical
physical
application
Transport
network
Link
physical
Network Layer
4-7
Addressing




Addressing enables identifying the devices that are connected to a
network in a unique way.
This identification is known as layer 3 address or IP address in the
TCP/IP architecture.
Every device having a network layer (end systems, routers…) has a
layer 3 address.
Hierarchical addressing schemes are used. (Network.Host)

Part of the N_PCI is used to identify the network - subnet - (Network
part)


It is the same for all the devices inside the same network.
The other part of the N_PCI identify the device, inside the network –
subnet -. (Host)

Usually called host part.
Network Layer
4-8
Two Key Network-Layer Functions


forwarding: move
packets (N_PDUs) from
the router’s input to the
appropriate router
output
analogy:

routing: process of
planning trip from source
to dest
routing: determine route
taken by packets
(N_PDUs) from source to
dest.

forwarding: process of
getting through a
crossroad.
 routing algorithms
Network Layer
4-9
Interaction between routing and forwarding
routing algorithm
routing table
N_PCI
output link
0100
0101
0111
1001
More about routing table soon...
3
2
2
1
value in arriving
packet’s header (N_PCI)
1
0111
3 2
Q: Which interface will it be forwarded for?
Network Layer
4-10
Connection setup



3rd important function in some network architectures:
 ATM, frame relay, X.25
before interchanging N_PDUs, two end hosts and the several
routers establish a virtual connection, known as virtual circuit
(VC)
 routers get involved (allocating resources)
network vs transport layer connection service:
 network: between two transport entities and network
layer of hosts and routers in the path are involved
 transport: between two application processes
Network Layer
4-11
Network service model
Q: What service model for “channel” transporting T_PDUs
from sender to receiver?
Example: services for
individual T_PDUs:
 guaranteed delivery
 guaranteed delivery with
less than 40 msec delay
Example: services for a flow
of T_PDUs:
 in-order T_PDU delivery
 guaranteed minimum
bandwidth to flow
 restrictions on changes in
inter-T_PDU spacing
Network Layer
4-12
Network Layer service models
Network
Architecture
Internet
Service
Model
Guarantees ?
Bandwidth
Loss
Order Timing
no
no
no
constant
yes
rate
guaranteed No
Minimum
yes
yes
Yes
No
best effort none
ATM
CBR
ATM
ABR
Congestion
feedback
no (inferred
via loss)
no
congestion
yes
CBR: Constant bit rate
ABR: Available bit rate
Network Layer
4-13
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-14
Network Layer connection and
connection-less service
datagram network (packet switching) provides
network-layer connectionless service
 VC network (circuit switching) provides networklayer connection service
 analogous to the transport-layer services, but:

 service: host-to-host
 no choice: network provides only one type of service
 implementation: in hosts and in network core
Network Layer
4-15
Virtual circuits
“source-to-dest path behaves much like telephone circuit”
 performance-wise
 network actions along source-to-dest path

There are three phases:
 call setup
 N_PDUs flow
 Call ending



each N_PDU carries VC identifier inside N_PCI (not destination host
address)
every router on source-dest path maintains “state” for each passing
connection
link, router resources (bandwidth, buffers) may be allocated to VC
(dedicated resources = predictable service)
Network Layer
4-16
VC implementation
a VC consists of:
1.
2.
3.


path from source to destination
VC numbers, one number for each link along path
entries in forwarding tables in routers along path that indicates
the path and the VC number to use in every case.
N_PDUs belonging to VC carries VC number (rather than
dest address)
VC number can be changed on each link.
VC number
22
12
1
2
32
3
interface
number
Network Layer
4-17
Virtual circuits: signaling protocols



used to setup, maintain and close VC
used in ATM, frame-relay, X.25
not used in today’s Internet
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
6. Receive data
3. Accept call
2. incoming call
application
transport
network
data link
physical
Network Layer
4-18
Datagram networks


no call setup at Network Layer
routers: no state about end-to-end connections
 no network-level concept of “connection”

N_PDUs forwarded using destination host address
 N_PDUs between same source-dest pair may take different paths
application
transport
network
data link
physical
1. Send N_PDU
application
transport
network
2. Receive N_PDU
data link
physical
Network Layer
4-19
Datagram or VC network: why?
Internet (datagram)



data exchange among computers
 “elastic” service, no strict
timing req.
“smart” end systems (computers)
 can adapt, perform control,
error recovery
 simple inside network,
complexity at “edge”
many link types
 different characteristics
 uniform service difficult
ATM (VC)



evolved from telephony
human conversation:
 strict timing, reliability
requirements
 need for guaranteed
service
“dumb” end systems
 telephones
 complexity inside network
Network Layer
4-20
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-21
Router interfaces

Technology used in each interface in the same
router is independent.
 Por example, the edge router in a domestic network
usually has an Ethernet/WI-FI interface and an ADSL
interface.

Router interfaces are identified by
 A letter depending on the technology and
• E.g.: E:Ethernet 10 Mbps, Fa:Fast Ethernet, Gi:Gigabit Ethernet,
To: Token Ring, Se:Serial…
 A number to distinguish interfaces with the same
technology
• E.g.: E0, E1, Fa0, Fa1, Se0..
Se0
E0
E1
Network Layer
4-22
Router and Logic Networks (I)

End systems or other routers may be connected to any
interface of a router. It is necessary to use the appropiate
transmission media.
 It is possible to use other devices that implements up to Data Link
Layer. For example, switches, access points or hubs.
 All of them are in the same broadcast domain, that is, they process all
frames (L_PDUs) that have a physical destination address (or
multicast) inside the L_PCI.
 In general, they all belong to the same logic network.
• They share the same network identifier in the IP address.
notes
1.- A broadcast physical address is for identifing a group of network interfaces.
2.- IP addresses are hierarchical. The bits that make them up have two parts: one identifies the
logical network (network identifier); and the other one identifies the end system or the router.
(host identifier) In general, we can say that IP address =NetworkX.HostY. More soon…
Network Layer
4-23
Router and Logic Networks (II)

Every interface in a router belongs to a a different logical
network.
 They have different IP addresses.
• The part that identifies the network will be different, e.g., Net1, Net2,…
Every interface in a router is in a different broadcast
domain.
 A router is not a transparent device.

 End systems must know some router’s IP address.
• E.g., it is necessary to know which the Ethernet or WI_FI interface IP
address of the edge router.
 Routers must know IP addresses of routers, in order to forward
N_PDUs (directly connected routers).
Network Layer
4-24
Example




Q. How many broadcast domains are there?
Q. How many logical networks are there? What happens if we assign Net1.Host3 and Net1.Host4 the
network identifier Net3?
Q. If Net1.Host1 wants to send data to Net2.Host2, who is the network layer delivering the N_PDU
that encapsulates this data to? Which source and destination are appearing in that N_PDU?
Q. Which source IP address is carrying the N_PDU (in its N_PCI) that the end system Net2.Host2 is
receiving?
Net1.Host1
SUP.
SUP.
NET.
Net2.Host2
NET.
NETWORK
Link
Link
Link
Link
Physical
Physical
Physical
Physical
Net1.Host4
Net1.Host2
Net 1
P0
Net2.Host1
Net2
P1
Router
…
Net1.HostN
Net1.Host3
Net1.Host5
Net2.Host3
Net2.HostN
Network Layer
4-25
Routing table (I)

The two key functions of the network layer use a routing
table (RT).
 Routing : in order to modify its content.
 Forwarding : in order to know which is the target interface to
forward a N_PDU to get to its destination.
End systems and routers have a routing table.
 In the forwarding process, RT entries are used to know
the next hop in the path.
 RT entries are used to know the path to follow in the
forwarding process. At least, the following info appears:

Network
Network identifier
Next hop
3-layer address of the next hop router
Interface
Output network interface
Network Layer
4-26
Routing table (II)

Q. How RT entries are filled?
 A1. Automatically
• When assigning an IP address to a network layer device, an entry is added for the
logical network to where the device belongs.
 A2. Manually
• By using management commands , it is possible to fill reachable networks in the RT.
 A3. Dinamically
• By the use of routing protocols. They implement some algorithms that set the best
path towards a particular logical network.
• It is specific for routers.
• Typical Internet routing protocols:
– RIP
– OSPF
– BGP

Besides, in the RT, a special entry is usually included: it is known as
default route. The default route is used in case there isn’t any specific
entry for a particular logical network. A reserved network identifier is
used.
Network Layer
4-27
Routing table use
When the Network Layer has a N_PDU to send, the only
necessary information in the N_PCI to guess next hop is
the destination IP address.
 The Network Layer looks for a matching entry in the RT.
The Network identifier for the destination network must
be the same as the Network identifier in the RT.

 In case there is an entry in the RT, the router delivers the
N_PDU (without modifying source and destination IP in the
N_PCI) to the next hop through the indicated interface.
• If destination is in the same network, known as directly connected,
router delivers the N_PDU through the indicated interface.
 If not, router discards N_PDU.
• That network is not reachable by the Network Layer.
Network Layer
4-28
Routing table example
RT Host Net1.Host1
Network
Next hop
Interface
RT Router 1
Network
Next hop
Net2.Host2
Interface
Net1.Host1
Net2.Host1
Net1.Host2
E0
NET 1
¿?
E1
NET 2
E2
Router 1
E0
Router 2
E1
Net3.HostN
Net2.Host3
…
Net1.Host3
…
Net2.HostN
NET 3
Net1.HostN
…
Net3.Host1
Net3.HostN-1
Network Layer
4-29
Routing table functioning
Every device implementing a network layer takes its own
decisions, based on the information kept in its routing
table.
 Not all the network devices have the same information in
their routing tables.
 The Routing information about a route does not provide
routing information about the return route.

Network Layer
4-30
Example
RT Router 1
RT Router 2
Net.
Next hop
Interface
Net.
Next hop
Interface
Net1
-
E0
Net4
-
E0
Net3
-
E2
Net2
-
E1
Net4
-
E1
Net3
Net4.Host2
E1
Net2
Net4.Host1
E1
Net1.Host1
Net2.Host2
Router 1
E0
NET 1
Router 2
Net4.Host2
Net1.Host2
E0
E1
Net3.HostN
E2
Net4.Host1
E1
NET 2
Net2.Host1
…
NET 3
Net2.Host3
…
Net1.Host3
Net2.HostN
Q1. Is it possible that Net1.Host3 sends
N_PDUs to Net3.Host1? and viceversa?
Net1.HostN
…
Net3.Host1
Q2. Is it possible that Net1.Host3 sends
N_PDUs to Net2.Host2? and viceversa?
Net3.HostN-1
Network Layer
4-31
Buffering
It allows routers to store arriving N_PDUs before
processing them.
 It allows routers to store N_PDUs before being
transmitted by any interface.
 When buffering?

 Heuristic rule (RFC 3439): the average space in a buffer should
be equal to RTT times the interface bandwidth (R)
• e.g., assuming RTT=250msec and R = 10 Gbps, the buffer needed in the
interface is 109x0,25 = 2,5 Gbit
 If taking into account the average TCP flows (N) going through
the interface , the following is recommended:
Buffer =
RTT. R
N
Network Layer
4-32
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-33
The Internet Network Layer


There are several Network protocols that work in host and routers.
Routing protocols are only in the routers. Not all the routing
protocols work in the Network Layer.
Routing protocols
•path selection
•RIP, OSPF, BGP
Transport layer: TCP, UDP
ICMP protocol
•error reporting
•router “signaling”
Network
layer
ARP protocol
• Matching physical addr
and IP addr
routing
table
IP protocol (RFC 791)
•addressing conventions
•Datagram (N_PDU) format
•Forwarding N_PDU
Link layer
physical layer
Network Layer
4-34
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-35
IP datagram format
IP protocol version
number
IP Header Length (IP_PCI)
in 32 bits words
(4 bytes)
“type” of N_UD
max number
remaining hops
(decremented at
each router) (1 byte)
Multiplexion/
Demultiplexion
how much overhead
(PCI) with TCP?
 20 bytes of TCP
 20 bytes of IP
 = 40 bytes + app layer
overhead (A_PCI)
total datagram
(IP_PDU)
length (bytes)
32 bits
ver
IHL type of
service
length
fragment
16-bit identifier flgs
offset
time to
header
protocol
live
checksum
for
fragmentation/
reassembly
IP_PCI
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
IP_UD
Network Layer
4-36
IPv4 Fragmentation & Reassembly (I)



network links have a MTU (Maximum
Transfer Unit) - largest possible linklevel frame (L_SDU or N_PDU).
 different link technology types,
different MTUs
If IP_PDU size > transmitting interface
MTU, large IP_PDU divided
(“fragmented”) within network
 one IP_PDU becomes several
IP_PDUs with appropriate size (<
original IP_PDU)
“reassembled” only at final destination
(destination Network Layer)
 IP header bits used to identify,
and order related fragments
fragmentation:
in: one large IP_PDU
out: 3 smaller IP_DPUs
reassembly
Network Layer
4-37
IPv4 Fragmentation & Reassembly (II)

IP_PCI is used for fragmentation: identifier, flags and fragment
offset.
 IP_PCI flags field has three bits, “0DfMf“, where:
• Df (Don´t fragment): if set to 1, indicates that fragmentation is not
allowed.
• Mf (More fragments): if set to 1, indicates there are more fragments.
There are no more fragments (or there was no fragmentation) if it is set
to 0.
 Identifier is used for labelling an IP_PDU and distinguishing it from the
rest. All the fragments of a IP_PDU have the same identifier.
 Segment offset is used to knowing the fragment order (measured in
bytes)
Network Layer
4-38
How fragmentation works

When the Network Layer fragments:
 It Checks bit Mf:
• If it was set to 0, it must set it to 1 in all the fragments but the last one, which
is set to 0.
• otherwise, all fragments have bit MF set to 1.
 Fragment offset indicates the relative position of the fragment IP_UD
(measured in 8 bytes blocks). It is zero for the first fragment only. The
reason for using 8 byte blocks is that the field is 13 bits width and
IP_PDUs are up to 216 bytes length.
 The number of bytes of IP_UD for all the fragments (but the last one)
must be a multiple of 8.
• The maximum number of bytes of the IP_UD is: (MTU – length in bytes of
the IP_PCI).
– If (MTU – length in bytes of the IP_PCI) is not a multiple of 8, some link capability
is wasted.
Network Layer
4-39
How reassembly works

If destination Network Layer receives an IP_PDU with the
bit MF set to 1, it knows that the IP_UD is not complete (it
has received a fragment). The Network layer has to wait
until receiving all the IP_PDUs with the same identifier
 Network Layer knows that it is finished when there is not any
gap between the segment offset of the received IP_PDUs
(fragments).

Reassembly consists of ordering IP_PDUs by segment
offset.
 IP_UD of each fragment is taken, put in order (indicated
by fragment offset) and delivered in a IP_SDU to the
upper layer when it is reassembled.
Network Layer
4-40
Example
IDENTIFIER= 111
IHL= 5
LENGTH= 2020
FLAG = 0, DF=0, MF=0
Offset = 0
TTL= 5
Protocol = 1
IDENTIFIER= 111
IHL= 5
LENGTH= 1500
FLAG = 0, DF=0, MF=1
Offset = 0
TTL= 4
Protocol = 1
MTU
1500 bytes
MTU
3000 bytes
IDENTIFIER= 111
IHL= 5
LENGTH= 540
FLAG = 0, DF=0, MF=0
Offset = 185
TTL= 4
Protocol = 1
Network Layer
4-41
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-42
IPv4 addressing

Known as IP address or IPv4 address

32 bits (4 bytes) with a hierarchical addressing scheme:
Network ID (NET)


Number of bits for network id and for host depends on the
addressing scheme.
Notation in a IPv4 address:

32 bits address



11001000001010001000000000100000
Grouped in bytes

11001000 00101000 10000000 00100000
Each byte in decimal and separated by a dot.


Host
200.40.128.32
Manual or dynamic setup


End systems has to set its IP address and the gateway IP address.
Routers have an IP address for every interface.
Network Layer 4-43
Types of IPv4 addresses

Three types of IPv4 addresses:

Unicast: For sending IP_PDUs to a single destination.


Broadcast: For sending IP_PDUs to all devices (hosts
and routers) in the same logical network.


All routers and end systems must have assigned at least one
IP address of this type.
Every logical network has an IP address of this type.
Multicast: For sending IP_PDUs to a group of devices
(hosts and routers) in the same or different logical
network.

All devices of the same group must have the same address of
this type.
Network Layer
4-44
Special addresses
This host: Used as source IP
address when this host doesn’t
have any (e.g. device without
configuration).
All 0s
Two meanings
Identifier for any network
(Default route in RT)
Network address
Network
All 0s
Identifier for the logic network
(used by RT)
Directed
Network
All 1s
Identifies all devices in a
network.
Broadcast
Limited
Loopback address
All 1s
127
Any digit
Identifies all devices in the
same network of the source
Used to check the network
layer in a device.
Network Layer
4-45
IPv4 addressing scheme

To fix which part of the IPv4 address is used for
identifying the network and which part is used for
identifying the host is used:
 Classful addressing
 Obsolete.
 Classless addressing
 Used currently.
Network Layer
4-46
Classful addressing (I)


It uses first byte of IP address to fix which part is for
network and which is for host.
There are 5 classes:
1st byte
Class A
Network
2nd byte
3rd byte
4th byte
Host
Host
Host
Network
Host
Host
Network
Network
Host
0 – 126
0xxxxxxx
Class B
Network
Unicast
128 – 191
10xxxxxx
Class C
Network
192 – 223
110xxxxx
Class D
Multicast
224 - 239
1110xxxx
Experimental
Class E
240 – 254
1111xxxx
Network Layer
4-47
Example of classful addressing


Class C; last byte identifies the host, the rest of bytes identifies the network.
Q. How many as maximum is it possible to identify in every logical network?
RT Router
223.1.1.1
Network
Next hop
Interface
223.1.1.0
-
E0
223.1.2.0
-
E1
223.1.3.0
-
E2
223.1.2.1
223.1.1.2
223.1.1.4
Network
223.1.1.0
223.1.2.9
E0
E1
223.1.1.255
223.1.3.27
Network
223.1.2.0
223.1.2.255
E2
223.1.1.3
223.1.2.2
IP_PDU to 255.255.255.255
Limited broadcast
Network
223.1.3.0
Network identifier
Directed broadcast
223.1.3.255
RT Host 223.1.1.3
Network
Next hop
Interface
223.1.1.0
-
E
0.0.0.0
223.1.1.4
E
IP_PDU to 223.1.2.255
223.1.3.1
223.1.3.2
Network Layer
4-48
Classful addressing summary

Network 1.0.0.0 – 126.0.0.0.- Class A.

Network 0 is not used.


0.0.0.0 is the address used if a device with network layer is not
configured.
0.0.0.0 is used for identifing any network.

It appears in the entry of the routing table that represent the default route.
Example of default route RT



Next hop
Interface
0.0.0.0
223.1.3.27
E0
Network 127 has a special use: internal communication.
27 – 2 networks with 224 -2 available addresses for devices
128.0.0.0 – 191.255.0.0.- Class B.


Network
214 networks of 216 -2 hosts
192.0.0.0 – 223.255.255.0.- Class C.

221 networks with 28 -2 availabe addresses for devices
Network Layer
4-49
Classless addressing (I)

To fix which part identifies host or network in a IP address,
a network prefix is used:

32 bit address followed by /x, where x indicates the number of
more significant bits of the IPv4 address. These bits identify the
network (the rest identify the host).


X can be 0 to 32.
For example, the identifier of a class B network could be
160.234.0.0/16.



Broadcast address would be 160.234.255.255.
We can assign any Network-layer address in the following range:
 160.234.0.1 to 160.234.255.254 .
Given a network identifier a.b.c.d/x, it is possible to address
(232-x – 2) network-layer devices.
Network Layer
4-50
Classless addressing (II)


Prefix notation is not usually used when configuring network-layer
devices.
/x is replaced by a netmask or subnet mask.
 It uses the same notation as IPv4 address, where



First X bits are set to 1.
Last 32-X bits are set to 0.
For example, a device with host prefix 160.234.0.25/16 is
configured by:
IP address: 160.234.0.25
 Netmask: 255.255.0.0
0.0.0.0/0 is the identifier for any network.


Netmask
notation
Example default route RT
Example default route RT
Network
Next hop
Interface
0.0.0.0 – 0.0.0.0
160.1.3.27
E0
Network idenfier - netmask
Prefix
notation
Network
Next hop
Interface
0.0.0.0/0
160.1.3.27
E0
Network Layer 4-51
Classless addressing (III)


This addressing scheme is known as CIDR (Classless
InterDomain Routing) (RFC 4692).
It allows assigning IPv4 address blocks, depending on the
actual needs. They are known as CIDR blocks.


Not many IPv4 addresses are “wasted”.
Example: a company needs 2000 IPv4 addresses.


With classfull addressing, it needs a whole class B network.
 216-2002 addresses are wasted.
With CIDR a network prefix X.X.X.X/21, it would be enough.
Network Layer
4-52
Example of classless addressing


Q. What is the Subnet mask to configure these devices?
Q. How many network-layer devices as maximum is it possible to identify in every logical network?
RT Router
223.1.4.1/22
223.1.1.4/22
Network
223.1.4.0/22
Network
Next hop
Interface
223.1.4.0/22
-
E0
223.1.8.0/22
-
E1
223.1.12.0/22
-
E2
223.1.4.4/22
223.1.8.9/22
E0
E1
223.1.8.1/22
Network
223.1.8.0/22
223.1.11.255
223.1.7.255
223.1.12.27/22
223.1.4.3/22
note
To know which is the right path to the
destination IP addr, the AND logic
operation between the netmask of a
particular RT entry and the destination IP
addr is held. If the network identifier
matches the correspondent entry in the
RT, that is the route to take.
E2
223.1.8.2/22
Network
223.1.12.0/22
223.1.15.255
IP_PDU to 223.1.8.2
223.1.12.1/22
223.1.12.2/22
Network identifier
Directed Broadcast
RT Host 223.1.3.2/22
Network
Next hop
Interface
223.1.12.0/22
-
E
0.0.0.0/0
223.12.3.27
E
Network Layer
4-53
Subnets



It allows to address smaller logical networks from a CIDR
block, fitting to the number of IP addresses needed.
Every subnet may have different number of network-layer
devices.
To create subnets, some bits are “borrowed” from the bits
that identify the host, in order to identify the subnetwork.

Given a network prefix with x bits to identify the network and 32x bits to identify the host, if n bits are borrowed, with n<32-x-1,
then:


2n subnets with 232-n-x -2 available IP addresses are created.
Where x+n is the number of bits that identify the network inside
every subnet.
Network Layer 4-54
Subnet examples

Let network identifier be 200.23.16.0/23
Host
part
Network
part
11001000 00010111 00010000 00000000

If 1 bit is borrowed, two subnets are created:
Network
part
Host
part
11001000 00010111 00010000 00000000
11001000 00010111 00010001 00000000

200.23.16.0/24
200.23.17.0/24
If 1 bit is borrowed again from one of them, e.g. 200.23.16.0/24, two new subnets
would be created.
Network
part
Host
part
11001000 00010111 00010000 00000000
11001000 00010111 00010000 10000000

200.23.16.0/25
200.23.16.128/25
So from the CIDR block 200.23.16.0/23 three subnets have been created:
200.23.16.0/25 and 200.23.16.128/25 with 27-2 available addresses and
200.23.17.0/24 with 28-2 available addresses.
Network Layer
4-55
Subnets advantages
They allow adding routes in routing tables.
When subnets are created from a CIDR block), if all those subnets are
reachable by the same interface, they can be summarised by the original
network prefix.
RT Internet
Company 0
200.23.16.0/23
Network
Next hop
Interface
223.1.16.0/20
194.13.17.1
E0
…
…
…
Company 2
200.23.17.0/23
194.13.17.1/30
Company 7
.
.
.
200.23.30.0/23
.
.
.
194.13.17.2/30
Fly-By-Night-ISP
Internet
E0
E1
note
The search in the routing table carries out by starting
with entries beginning by the network prefix /32 and
it ends with /0. The next hop will be the entry that
has more bits in common with the destination IP
addr from the IP_PDU.
Network Layer
4-56
How CIDR blocks are assigned?

Currently, there are no available blocks.
 The last one was assigned in February 2011.
 Why have they run out?
• Mobile devices.
• Non-efficient use of the available address space.
• Internet user demography.

ISPs distribute among their clients the assigned CIDR blocks that
they have.
 They do not usually assign fixed IPs any more.

If there are not any available IPv4 addresses, how are devices
identified?
 Private addressing and NAT
 IPv6
• Progresive migration.
Network Layer
4-57
Private addressing

In 1996, a set of addresses were reserved. They are called
private addresses (RFC 1918):

They belong to a reserved IP address range to be used only in
private networks (these IP addresses must not appear in the
network core of the Internet).


For example, to address a non-public Intranet, a laboratory, a domestic network....
Reserved range:
“Class”
A
Address range
10.0.0.0 –10.255.255.255
CIDR identifier
B
172.16.0.0 – 172.31.255.255
10.0.0.0 /8
172.16.0.0 /12
C
192.168.0.0 – 192.168.255.255
192.168.0.0 /16
Network Layer
4-58
Private addressing and NAT

Private addresses and NAT (Network Address Translation, RFC 3022)
are used to allow a network with a private IP addresses accessing to
the Internet.
 NAT is usually implemented in routers.
Rest of
the
Internet
Local network
(e.g., domestic network)
138.76.29.7
Internet
10.0.0.1
10.0.0.4
Network
10.0.0/24
10.0.0.2
10.0.0.3
All outgoing IP_PDUs have the same
source IP address: 138.76.29.7.
IP_PDUs with source or destination inside this
network have network addresses from network
10.0.0/24 as source or destination (as always)
Network Layer 4-59
Chapter 4. Overview
4. 1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-60
ICMP: Internet Control Message Protocol (RFC 792)
Ping 195.7.3.24

Used by end systems and routers
to communicate network-layer
information
 Error report: host unreachable,
(or network, or port, or protocol)

Works over IP (network layer):
 ICMP_PDUs (known as ICMP
messages) are encapsulated in
IP_PDUs (IP datagrams).

ICMP messages:
 Echo request/Reply (used by ping
command)
 TTL Exceeded (used by tracert
command)
ICMP
IP
Echo Request
ICMP
Echo Reply
IP
…
..
A
B
Internet
193.1.23.4
195.7.3.24
tracert 195.7.3.24
ICMP
IP
ICMP
TTL Exceeded
TTL=1
…
IP
195.7.3.24
..
A
193.1.23.4
B
Echo Request
Internet
193.1.23.1
Network Layer 4-61
Chapter 4. Overview
4.1 Introduction
4.2 Virtual circuit and datagram networks
4.3 Router in datagram networks
4.4 IP: Internet Protocol




Datagram format
IPv4 addressing
Basic ICMP
Functioning
Network Layer
4-62
IPv4 operation (I)

It is necessary that network-layer devices are configured
and have their routing table filled:

There are two mechanisms to configure end systems:

Manually: using the operative system interface.


At least IP address., subnet mask and default gateway (edge router) must be
configured
IP Address for one or several DNS servers


Dynamically: using some kind of protocol, e.g. DHCP (Dynamic Host
Configuration Protocol).


It is not necessary to know all the IP addresses.
Configuration is carried out automatically for a period of time. It is possible
to release and renew the configuration.
In routers, it is necessary to configure only IP and subnet mask
for every interface.
Network Layer 4-63
IPv4 operation (II)

It is necessary that network-layer devices are configured
and have their routing table filled:

End systems require, as minimum, two entries (included
automatically):



One for the logical network the end system belongs to (does not need
next hop).
Default route, whose next hop is the edge router.
Routers require one entry for every reachable network:

Introduced manually (static).



E.g: default route.
Learned dynamically by a routing protocol.
As minimum, table includes directly connected networks, that is, the
networks directly accessed by their interfaces (automatic).
Network Layer
4-64
IPv4 operation (III)

Before sending an IP_PDU, IP protocol checks if there is any
entry in the RT for the destination network:


If there is not any coincident entry, the IP_PDU will not be sent.
If there is a coincident entry, the IP_PDU will be sent through the
interface indicated in the RT entry. It uses data link layer services
to send it to:


the destination, if it is directly connected.
the device (router) whose IP address matches the one in the RT.

In the end systems it is the interface of the edge router, in most cases.
note
eBefore requesting the IP_PDU to be sent to the data link
layer, a mapping IP addr/MAC addr is needed. This is done by
means of the ARP protocol. More in next chapter…
Network Layer 4-65
IPv4 operation (IV)

When receiving an IP_PDU, network layer checks if the
destination network matches one of the configured ones:


If it matches, the network layer processes the IP_PDU.
If it does not match, then:


if it is an end system, the network layer discards the IP_PDU.
If it is a router, the network layer forwards it, if it knows how to reach
the destination network:

Checks and modify, if appropriate, the TTL value of the IP_PDU header.



If it is 1, it discards the IP_PDU (it does not forward it).
otherwise, it decreases the TTL value in 1.
Repeat the actions that network layer does to send a IP_PDU.
Network Layer 4-66
Example of sending IP_PDUs
RT Router 1
RT Router 2
1.- From 223.1.8.2 to 223.1.8.1
2.- From 223.1.8.1 to 223.1.16.1
Q. What is the TTL value that is received by 223.1.16.1 inside the IP_PDU?
Network
Next hop
223.1.3.0/24
-
223.1.0.0/24
-
223.1.16.0/22
-
Network
Next hop
223.1.3.0/24
-
223.1.1.0/24
-
223.1.1.0/24
223.1.3.1
223.1.2.0/24
223.1.1.1
223.1.8.0/22
223.1.3.1
223.1.8.0/22
223.1.1.1
0.0.0.0/0
223.1.0.1
223.1.16.0/22
223.1.3.2
0.0.0.0/0
223.1.3.2
223.1.3.1/24
RT Host 223.1.3.2/22
Network
Next hop
223.1.8.0/22
-
0.0.0.0/0
223.1.3.2/24
E0
223.1.3.0/24
223.1.1.1/24
223.1.16.0/22
223.1.1.0/24
223.1.0.1/24
E2
To: 223.1.8.1
223.1.1.2/24
R3
E0
E1
223.1.64.1/18
E0
E1
223.1.2.0/24
223.1.2.1/24
223.1.8.2/22
R4
223.1.2.2/24
INTERNET
E2
RT Router 4
RT Router 3
Note: Interfaces aren’t shown in RTs.
223.1.16.25 /22
223.1.16..1/22
To: 223.1.16.1
223.1.8.1/22
R2
E2
223.1.0.2/24
223.1.0.0/24
223.1.8.27
223.1.8.0/22
E1
E0
E1
R1
223.1.16.2/22
Network
Next hop
223.1.8.0/22
-
223.1.1.0/24
-
223.1.2.0/24
-
223.1.3.0/24
223.1.1.1
223.1.16.0/22
223.1.1.1
0.0.0.0/0
223.1.2.2
Network
Next hop
223.1.64.0/18
-
223.1.0.0/24
-
223.1.2.0/24
-
223.1.3.0/24
223.1.1.1
223.1.16.0/22
223.1.0.2
223.1.8.0/22
223.1.0.2
0.0.0.0/0
223.1.96.255
Network Layer
4-67
Departamento de
Tecnología Electrónica
Computer Networking – Chapter 4: The Network layer
PROBLEMS AND EXERCISES
Network Layer 4 - 68
Pr1: Fragmentation
Consider a router that has received a IP_PDU with 2400 bytes from
one of its interfaces. It must forward it through a 700 bytes MTU
interface. How many IP_PDUs is the router forwarding to its output
interface? Indicate values for fragment identifier, flags, fragment
offset, and length of every IP_PDU.
Network Layer
4-69
Pr2: Classful addressing
Next figure shows a router interconnecting two networks. Answer the questions assuming
that classful addressing is used:
a) What is the available address range and the broadcast address for each network?
What is the routing table of the router like? And the routing table of an end system
in each network? Give an example of a possible configuration of the router
interfaces and of the end systems A and B.
b) Suppose that an end system in network 150.0.0.0 sends an IP_PDU whose
destination address is 192.0.0.255. Who in the destination network is receiving the
IP_PDU?
c) Suppose that an end system in network 192.0.0.0 sends an IP_PDU whose
destination is 255.255.255.255. Who in the destination network is receiving the
IP_PDU?
Network Layer 4-70
Pr3: Classless addressing
Suppose that the CIDR block 200.1.0.0/24 was assigned to a
company. Every subnet must have 20 connected end
systems.
a)How many subnets could you create inside this company?
b)Which subnet mask, broadcast address and available IP
address range does every subnet have?
c)Would you change your answer if there were 30 end
systems per subnet?
Network Layer
4-71
Pr4: Classless addressing
Consider a router that interconnects three subnets: subnet
1, subnet 2, and subnet 3. Suppose that all the interfaces in
these subnets must be subnets of 223.1.17.0/24. Subnet 1
is required to have up to 63 end systems; Subnet 2, up to 95
end systems; and Subnet 3, up to 16 end systems. Check
out if it is possible to address these three subnets.
Network Layer
4-72
Pr5: NAT, interface configuration
Next figure shows a public institution network that accesses to the Internet via router R2. Answer these
questions:
a) How many end systems, as maximum, is it possible to connect to every subnet in this
institution?
b) Is it necessary that router R2 implements NAT?
c) Suppose R2 does not implement NAT. Which network prefix would appear in the routing table
in a router in the Internet, e.g. RI, to identify that institution?
d) Could this institution address a new subnet? How many end systems could there be connected,
as maximum?
e) Suppose that the interface E0 of R2 has the next configuration: IP address=223.14.15.1,
netmask=255.255.255.252. All the end systems have to be able to access to the Internet and
communicate to other end systems inside the institution. Indicate the configuration for
interfaces of the routers R1 and R2, the minimum content of their routing tables and the
Network Layer 4-73
minimum content of an end system in each subnet.
Pr6: Addressing
Next figure shows a public institution network that accesses to the Internet via router R2. Answer these
questions:
Network-2
12 PCs
Network-1
12 PCs
Internet
E3
E1
Network-3
12 PCs
R1
E2
E0
E0
Network
50 PCs
E1
R2
a) If classful addressing was used, how many networks would be necessary? Which class should
be used for a minimum address waste?
b) Would it be possible to address all the subnets of the institution with a CIDR block
200.1.1.0/25? In that case, assign the right network address for every institution subnet.
c) Would it be possible to connect a new subnet with 13 PCs through a free interface of R1? In
that case, indicate the content of the routing table of R2 for a minimum number of entries.
(Interface E0 of R2 has the following configuration: IP addr=223.14.15.1,
netmask=255.255.255.252. All PCs of this institution are able to access to the Internet).
d) Would you change your answer for question c) if the subnet connects to a free interface of R2
instead to R1?
Network Layer
4-74
Pr7: NAT
Figure shows two companies, X and Y, that access to the Internet through a router that implements NAT.
A and B are web servers that are on the Internet . All the devices are configured correctly, and classless
addressing is used. Answer reasonably to these questions:
Network Layer
4-75
Pr7: NAT
a) Is it possible that a PC of the Company X, e.g., the one that has IP address
172.16.1.2, opens a web page from server A in its browser? In that case, indicate
source and destination IP address for the IP_PDUs received by the server, and for the
IP_PDUs received by the client. Otherwise, explain what the problem is.
b) Is it possible that a PC of the Company Y, e.g. the one that has IP address
147.156.1.2, opens a web page from server A in its browser? In that case, indicate
source and destination IP address for the IP_PDUs received by the server, and for the
IP_PDUs received by the client. Otherwise, explain what the problem is.
c) Is it possible that a PC of the Company X, e.g. the one that has IP address 172.16.1.2,
opens a web page from server B in its browser? In that case, indicate source and
destination IP address for the IP_PDUs received by the server, and for the IP_PDUs
received by the client. Otherwise, explain what the problem is.
d) Is it possible that a PC of the Company Y, e.g. the one that has IP address
147.156.1.2, opens a web page from server B in its browser? In that case, indicate
source and destination IP address for the IP_PDUs received by the server, and for the
IP_PDUs received by the client. Otherwise, explain what the problem is.
Network Layer
4-76
Pr8: Addressing
Figure shows the network topology of a company, where hosts access to the Internet through a router (1) that supports
NAT. Router 1 is connected to the networks 150.214.141.0/24 and 192.168.1.0/24 through two different interfaces.
Router RTX is on the Internet and it is not part of the company network. Classless addressing (CIDR) is used.
a)
b)
c)
d)
How many broadcast domains are there in the company network?
Provide an address assignment for this network taking into account that you have to leave as maximum
vacant address as possible, for future extensions. Subnet A is required to have 125 PCs and subnet B is
required to have 61 PCs.
i. Indicate, reasonably, IP address and netmask for all the interfaces in routers 1,2 and 3.
ii. Which address range is remaining available for future extensions? Using all address the obtained
space, indicate the network prefixes that allow the most number of hosts.
Indicate, reasonably, the minimum content of the routing tables for all three routers (1, 2 y 3), so that all the
PCs in the company may interchange datagrams and are connected to the Interne. The less traffic as possible
must be generated.
Regarding router RTX, is it necessary to include any entry in the routing table to address the company?
Indicate why and, if it is the case, a possible IP address for next hop.
Network Layer 4-77
Pr9: IP configuration
Consider the network showed in the figure. It has access to the Internet, uses classless addressing, and all the routers interfaces are
configured as it is shown in the table (note: not all of them are shown).
Router (Interface)
R0 (E0)
R0 (E1)
R1 (E0)
R1(E1)
R2(E0)
Rext (E1)
Prefix notation
configuration
150.214.0.1/23
150.214.128.2/30
150.214.2.1/23
150.214.128.5/30
150.214.128.9/30
190.100.100.2/30
a) Indicate, reasonably, IP address and netmask for interfaces E1 and E2 of router R2.
b) Indicate, reasonably, if the following IP addresses are correct in the described context:
i. IP addr = 150.214.0.0 and netmask = 255.255.254.0 for a PC in network Alpha.
ii. IP addr = 150.214.0.255 and netmask = 255.255.254.0 for a PC in network Alpha.
iii. IP addr = 150.214.2.5 and netmask = 255.255.252.0 for a PC in network Bravo.
iv. IP addr = 150.214.1.2 and netmask = 255.255.254.0 for a PC in network Bravo.
c) Indicate, reasonably, the minimum content of the routing tables of router R2 and the exterior router (Rext), connected to
interface E0 of R2.
d) Imagine that routers R0, R1 and R2 are replaced by a switch that interconnects networks Alpha and Bravo directly to the exterior
router (Rext). That would make Alpha and Bravo being in the same broadcast domain. Which changes in the configuration of
routers are necessary to keep connectivity (among PCs and to the Internet). NOTE: Parameter “IP address” in nodes of Alpha and
Bravo cannot be modified.
Network Layer
4-78
Pr10: Fragmentation
Consider a router connecting two broadcast domains, 1 and 2. In each domain, there is only
one logical network. Broadcast domain 1 has an MTU=1500 bytes and broadcast domain 2
has an MTU = 760 bytes. PcA is in broadcast domain 1. It is running a process in port 49789.
This process implements the client side of an application-layer protocol called X. In the same
domain, PcB is running a process in the port 51345, implementing the server side of the X
protocol. If UDP in PcA receives a send request from port 49789 of an A_PDU of 1472 bytes,
for the port 51345 in PcB, determine reasonably:
a) How many UDP_PDU and IP_PDU are UDP and IP receiving, respectively, in PcB? And
which size, in bytes, are they?
b) Would you change your answer if PcB was in broadcast domain 2? Why? (Note: In
this case, PcB has been configured correctly in the corresponding logical network in
the broadcast domain)
Network Layer
4-79
Chapter 4: Summary



Network Layer characteristics in
datagram networks.
It works the same in hosts and routers
 Using routing tables.
IP protocol:




How it fragments and reassemblies.
How devices are addressed.
How it sends and receives IP_PDU.
How it uses routing tables.
Next:
 Leaving network
core and logical
network (Network
Layer)
 Incoming to
physical network
(broadcast
domain)
Network Layer
4-80
Network Layer 4-81
Routing table example
RT Host Net1.Host1
Network
Next hop
Interface
Net1
-
E
Net2
Net1.Host2
E
RT Router 1
Network
Next hop
Interface
Net1
-
E0
Net2
-
E1
Net2.Host2
Net1.Host1
Net2.Host1
Net1.Host2
E0
NET 1
¿?
E1
NET 2
E2
Router 1
E0
Router 2
E1
Net3.HostN
Net2.Host3
…
Net1.Host3
…
Net2.HostN
NET 3
Net1.HostN
…
Net3.Host1
Net3.HostN-1
Network Layer
4-82
Routing table example
RT Host Red1.Host1
Network
Next hop
Interface
Net1
-
E
Net2
Net1.Host2
E
Net3
Net1.Host2
E
Net4
Net1.Host2
E
RT Router 1
Net1.Host1
Network
Next hop
Interface
Net1
-
E0
Net2
-
E1
Net4
-
E2
Net3
Net4.Host1
E2
Net2.Host1
Net1.Host2
E0
NET 1
Net2.Host2
E1
NET 2
Net4.Host2 E2
Router 1
E0
Net4.Host1
Router 2
E1
Net3.HostN
Net2.Host3
…
Net1.Host3
…
Net2.HostN
NET 3
Net1.HostN
…
Net3.Host1
Net3.HostN-1
Network Layer
4-83
Routing table example
RT Host Red1.Host1
Network
Next hop
Interface
Net1
-
E
Default
Red1.Host2
RT Router 1
E
Net1.Host1
Network
Next hop
Interface
Net1
-
E0
Net2
-
E1
Net4
-
E2
Net3
Net4.Host1
E2
Net2.Host1
Net1.Host2
E0
NET 1
Net4.Host2
Net2.Host2
E1
NET 2
E2
Router 1
E0
Net4.Host1
Router 2
E1
Net3.HostN
Net2.Host3
…
Net1.Host3
…
Net2.HostN
NET 3
Net1.HostN
…
Net3.Host1
Net3.HostN-1
Network Layer
4-84