Computer Networks

Chapter IV: Network Layer

Dr. Gattal Elhachemi

Department of Computer Science
University of Tamanrasset

Academic Year 2025–2026

Chapter Objectives
By the end of this chapter, students will be able to:

• Explain the role of the Network Layer and end-to-end packet delivery across multiple
networks.

• Understand IPv4 addressing (classes, CIDR) and perform subnetting.

• Compare IPv4 and IPv6 (address format, header structure, key features).

• Describe packet fragmentation and the impact of MTU.

• Understand packet switching and store-and-forward operation.

• Distinguish centralized vs. distributed routing techniques.

• Differentiate static vs. dynamic routing.

• Explain hierarchical routing and inter-domain (external) routing concepts.

Contents

1 Network Layer 4
1.1 IPv4 Addressing: Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Types of IPv4 Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 IPv4 Address Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Network Mask . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Broadcast Address . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 IP Address Classes (Historical) . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Dividing a Class into Subnets (Subnetting) . . . . . . . . . . . . . . . . . . 8
1.5 Classless Inter-Domain Routing (CIDR) . . . . . . . . . . . . . . . . . . . 10
1.5.1 Why CIDR was introduced . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.2 From subnetting to supernetting (CIDR + VLSM) . . . . . . . . . 10
1.5.3 Route summarization example . . . . . . . . . . . . . . . . . . . . . 11
1.5.4 VLSM example (address planning) . . . . . . . . . . . . . . . . . . 11
1.5.5 CIDR notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Practical Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Private Networks and Address Translation (NAT) . . . . . . . . . . . . . . 15
1.7.1 NAT in home networks (“router/box” example) . . . . . . . . . . . 16
1.7.2 NAT on GNU/Linux: netfilter/iptables . . . . . . . . . . . . . . . . 16
1.7.3 SNAT and DNAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7.4 Two typical traffic directions . . . . . . . . . . . . . . . . . . . . . . 17
1.8 IP Protocol: IPv4 and IPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.8.1 IPv4 overview and header fields . . . . . . . . . . . . . . . . . . . . 17
1.8.2 IPv6 Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.9 Packet Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.9.1 MTU and why fragmentation occurs . . . . . . . . . . . . . . . . . 35
1.10 Packet Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.10.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.10.2 Packet switching vs circuit switching (idea) . . . . . . . . . . . . . . 41
1.11 Routing: Centralized and Distributed Techniques . . . . . . . . . . . . . . 41
1.11.1 Static Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2
Computer Networks Chapter IV: Network Layer

1.11.2 Dynamic Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . 44

1.11.3 Hierarchical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.11.4 Broadcast Routing and Multicast Routing . . . . . . . . . . . . . . 47
1.11.5 Routing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.11.6 Static and Dynamic routing table . . . . . . . . . . . . . . . . . . . 56
1.11.7 Example: Static Routing Table . . . . . . . . . . . . . . . . . . . . 57
1.12 Questions and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3
Chapter 1 Network Layer

1.1 IPv4 Addressing: Fundamentals

The fundamental role of the Network Layer (Layer 3 of the OSI model) is to determine
the route that packets must follow. This path-search function requires identifying all
hosts connected to the network. In the same way that we locate a building by its city,
street, and number, we identify a network host using an address that contains similar
information.
The TCP/IP model uses a specific addressing system that shares the name of this
layer: IPv4 addressing. This section presents how IPv4 addressing works.
In a classical and academic approach, we begin with the IPv4 address format. Then
we define the IPv4 address classes, which correspond to the earliest method used to
partition the address space. Since this class-based method did not fit the growth of the
Internet, we briefly review the improvements introduced since the 1980s: subnetting,
Network Address Translation (NAT), and finally classless inter-domain routing
(CIDR).

1.1.1 Types of IPv4 Traffic

Before studying addressing mechanisms, note that IPv4 carries three distinct types of
traffic:

Unicast Communication between one unique source host and one unique destination
host.

Multicast Communication between one unique source host and a group of hosts that
have chosen to receive the stream. A common analogy is TV broadcasting: the
transmission is continuous, but only televisions tuned to that channel display it.

Broadcast A flow sent by one host to all other hosts within the same broadcast domain.
This exists only on broadcast networks such as Ethernet. For example, the ARP
protocol uses a broadcast frame to ask all hosts on the local network which MAC
address corresponds to a known IPv4 address.

4
Computer Networks Chapter IV: Network Layer

1.2 IPv4 Address Format

IPv4 addresses are made of 4 octets (32 bits). By convention, they are written as four
decimal numbers from 0 to 255 separated by dots (dotted-decimal notation).
The originality of this addressing format lies in associating:

• a network part, shared by all hosts in the same network,

• a host part, unique within that network.

Table 1.1: Example: IPv4 address [Link]

Field Value

Full address [Link]

Network mask [Link]
Network part 192.168.1._
Host part _._._.1
Network address [Link]
Broadcast address [Link]

1.2.1 Network Mask

The network mask separates the network and host parts of an address. The network
address is obtained by performing a bitwise logical AND between the full address and
the network mask.

1.2.2 Broadcast Address

Each network has a special address called the broadcast address. All packets sent to
this destination address are processed by all hosts on the local network.

1.3 IP Address Classes (Historical)

Originally, several groups of addresses were defined to optimize packet forwarding (rout-
ing) between different networks. These groups were called IP address classes. They
correspond to partitions into networks of fixed sizes. Networks belonging to the same
class have the same maximum number of hosts.

5
Computer Networks Chapter IV: Network Layer

Figure 1.1: Classes of IP Addresses

Class A
The first octet is in the range 1 to 126, meaning the most significant bit is 0. The first
octet identifies the network number, and the remaining three octets identify the host
address.

Special reservation

The network [Link]/8 is reserved for loopback communications (local host).

Class B
The first octet is in the range 128 to 191, meaning the two most significant bits are
10. The first two octets identify the network number, and the remaining two octets
identify the host address.

Class C
The first octet is in the range 192 to 223, meaning the three most significant bits are
110. The first three octets identify the network number, and the last octet identifies
the host address.

Class D
The first octet is in the range 224 to 239. This range is dedicated to multicast services
for groups of hosts (host groups). (In classful terms, the high-order bits start with 1110.)

6
Computer Networks Chapter IV: Network Layer

Class E
The first octet is in the range 240 to 255. This range is reserved for experimental
purposes and must not be used to address hosts or groups of hosts. (High-order bits start
with 1111.)

Table 1.2: IPv4 classful addressing space (summary)

Default # # Hosts /
Class Network Address
Mask Networks Network
Range

A [Link] [Link] – [Link] 126 16,777,214

B [Link] [Link] – [Link] 16,384 65,534
C [Link] [Link] – [Link] 2,097,152 254
Unique Unique
D [Link] [Link] – [Link]
addresses addresses
Unique Unique
E Not defined [Link] – [Link]
addresses addresses

Limitations of Classful Addressing

The table above shows that the distribution of the address space is not well balanced.
There is no intermediate class between A and B, even though the difference in the number
of hosts per network is extremely large.
A common representation of the IPv4 address space distribution is:

• Class A: 50%

• Class B: 25%

• Class C: 12.5%

• Class D: 6.25%

• Class E: 6.25%

In addition to this poor distribution, many criticisms were made about how IPv4
classes were allocated during the early years of the Internet. Since classes were often
assigned on request without matching real needs, this resulted in significant waste of
address space.
Over time, several generations of solutions were introduced to compensate for these
distribution problems. The following sections present these solutions in chronological
order.

7
Computer Networks Chapter IV: Network Layer

1.4 Dividing a Class into Subnets (Subnetting)

To compensate for the poor distribution of the IPv4 address space, the first solution used
was to split an IPv4 class A, B, or C network into smaller subnets. This technique,
called subnetting, was formalized in 1985 in RFC 950.
Even though subnetting is an old technique, it is still effective for operating modern
networks. Dividing a network into subnets allows us to isolate broadcast domains.
The benefits of limiting broadcast traffic are numerous:

• In daily operations, we reduce link congestion by limiting service announcements to a

geographical (or logical) area. Microsoft™ services based on NetBIOS over TCP/IP
(NetBT) are particularly broadcast-intensive. Many actions that are transparent
to users rely on general broadcast announcements. Without broadcast discovery,
the user must explicitly specify which service to use. Printing services are a typical
example.

• Many worms and/or viruses spread by discovering targets using broadcast mecha-
nisms. The Sasser worm is a classic example. By segmenting a network into multiple
broadcast domains, the spread of malicious code is naturally limited. Subnetting
therefore becomes part of the network security toolbox.

Practical Example: Subnetting a Class C Network

To illustrate how subnetting works, consider the Class C network [Link] whose
default mask is [Link]. Without subnetting, the maximum number of hosts is
254. Assuming a single broadcast domain for 254 hosts is too large, we decide to subdivide
this Class C address space.
We reserve 3 additional bits from the 4th octet by extending the network mask. This
increases the network portion of the IPv4 address and reduces the host portion.

Subnetting math (3 borrowed bits)

Default: /24. Borrow 3 bits ⇒ new prefix: /27.

New mask: [Link].
Number of subnets: 23 = 8.
Hosts per subnet: 2(32−27) − 2 = 25 − 2 = 30 hosts.

8
Computer Networks Chapter IV: Network Layer

Figure 1.2: Class C network mask

Table 1.3: Network [Link] with 3-bit subnetting (/27)

Network Broadcast
Subnet Usable Host Range
Address Address

0 [Link] [Link] – [Link] [Link]

1 [Link] [Link] – [Link] [Link]
2 [Link] [Link] – [Link] [Link]
3 [Link] [Link] – [Link] [Link]
4 [Link] [Link] – [Link] [Link]
5 [Link] [Link] – [Link] [Link]
6 [Link] [Link] – [Link] [Link]
7 [Link] [Link] – [Link] [Link]

All-zeros and All-ones Subnets (Historical Rule)

According to RFC 950, subnets whose subnet bits were all 0 (all-zeros) or all 1 (all-ones)
were originally not supposed to be used. This was to avoid interpretation issues with
classful routing protocols such as RIPv1. Those first-generation protocols did not
carry subnet mask information, because the mask was assumed from the leftmost octet
(class A/B/C). In our example, ambiguity could occur:

• The subnet address [Link] could be interpreted as the network address for
two different networks:

– the original Class C network with mask [Link], and

– the subnetted network with mask [Link].

• Similarly, the broadcast address [Link] could be the broadcast address for
two different networks: [Link]/24 and [Link]/27.

9
Computer Networks Chapter IV: Network Layer

Modern Routing Protocols and CIDR

Since the publication of RFC 950 (1985), routing protocols have evolved. Modern pro-
tocols follow classless rules (CIDR) and explicitly carry subnet mask (prefix length)
information. Protocols such as RIPv2, OSPF, and BGP support subnet masks and can
even summarize routes to reduce routing table size.
To reinforce this point, RFC 1878 (1995) clearly states that excluding all-zeros and
all-ones subnets is now obsolete.

1.5 Classless Inter-Domain Routing (CIDR)

1.5.1 Why CIDR was introduced

Classless Inter-Domain Routing, or CIDR, was discussed by the IETF starting in 1992.
At that time, some Internet growth projections predicted a complete exhaustion of the
IPv4 address space by 1994 or 1995.
The deployment of this technique began in 1994 after the publication of several RFC
documents (e.g., RFC 1517, RFC 1518, RFC 1520, and later updates such as RFC 4632).
The main proposal was to move away from the rigid class-based (classful) addressing
model and rely instead on the network prefix length (subnet mask), which was already
widely used.

Historical note (optional for accuracy)

The original CIDR specification was published in the early RFC 1518/1519/1520
series (1993). RFC 4632 is a later update that consolidates and replaces earlier
CIDR RFCs.

1.5.2 From subnetting to supernetting (CIDR + VLSM)

CIDR allows network administrators to go beyond simple subnetting by enabling super-
netting (route aggregation). By using any valid subnet mask / prefix length, we
are no longer limited to the default class masks:

[Link], [Link], [Link]

Supernetting, combined with Variable Length Subnet Masking (VLSM), helped

solve:

• the inefficiency of IPv4 address allocation (no more forced “full class” blocks),

10
Computer Networks Chapter IV: Network Layer

• the rapid growth of Internet routing tables (aggregation reduces the number of
routes).
CIDR reduced IPv4 allocation problems because the Internet Assigned Numbers Au-
thority (IANA) was no longer forced to allocate entire classful blocks. Instead of reserving
half of the IPv4 space for huge Class A networks, that space could be split into smaller
blocks that are easier to allocate.
CIDR, together with Network Address Translation (NAT), helped IPv4 remain
usable far beyond the limits predicted in the early 1990s.

1.5.3 Route summarization example

Supernetting is based on identifying the common leading bits among the networks to
be summarized. Consider the following four /24 networks:

[Link]/24 10101100.00010000.00001100.00000000
[Link]/24 10101100.00010000.00001101.00000000
[Link]/24 10101100.00010000.00001110.00000000
[Link]/24 10101100.00010000.00001111.00000000

In these four networks, the first 22 bits are identical. Therefore, a single summary
route can represent all four entries:

Address: [Link]
Netmask: [Link] (= /22)

/22 ⇒ 11111111.11111111.11111100.00000000

1.5.4 VLSM example (address planning)

Figure 1.3:

11
Computer Networks Chapter IV: Network Layer

VLSM is not only useful for major Internet Service Providers (ISPs). Any administrator
managing multiple subnets can use VLSM to use an assigned address block more efficiently.
Suppose the ISP assigns the network [Link] with mask [Link], i.e.:

[Link]/25

So we have half of the original [Link]/24 network.

The figure 1.3 indicates multiple perimeters to be addressed. Each router interface
defines a separate IP network (broadcast domain). For each LAN perimeter, we plan for
future growth by choosing a subnet size that is about twice the current number of hosts.

Table 1.4: Table 4. VLSM subdivision of network [Link]/25

Name Subnet CIDR Mask Usable ad- Hosts
(Network) dress range

ISP1 Link [Link] /30 [Link] [Link] 2

–
[Link]
ISP2 Link [Link] /30 [Link] [Link] 2
–
[Link]
Internet Services [Link] /28 [Link] [Link] 14
–
[Link]
Administration [Link] /27 [Link] [Link] 30
–
[Link]
Engineering [Link] /27 [Link] [Link] 30
–
[Link]
Manufacturing [Link] /27 [Link] [Link] 30
–
[Link]

Note that the maximum number of usable host addresses equals the subnet size minus
two:

• the first address is the network address,

• the last address is the broadcast address.

12
Computer Networks Chapter IV: Network Layer

When planning VLSM addressing, it is often recommended to allocate a subnet that

provides room for future growth (for example, by doubling the expected number of hosts
for LAN segments).

1.5.5 CIDR notation

To avoid writing full dotted-decimal masks, CIDR notation writes the number of 1-bits
in the mask after a slash:
[Link]/27

The notation /27 means 27 network bits set to 1, which corresponds to:

[Link]

CIDR and VLSM techniques have been used to optimize IPv4 addressing across the entire
Internet.

1.6 Practical Example

To configure a host interface on an existing network, we are given:

[Link]/21

Q1: What is the subnet mask?

The condensed notation /21 means the network part occupies 21 bits. We decompose 21
bits as:
8+8+5

So the mask is:

[Link]

Q2: How many bits were borrowed for private subnets relative to
the historical class definition?
Since the first octet value is between 128 and 191, the address belongs historically to
Class B. The default Class B mask is:

[Link] (= /16)

13
Computer Networks Chapter IV: Network Layer

Therefore, the number of borrowed bits is:

21 − 16 = 5 bits

Q3: How many private subnets are available?

With 5 subnet bits, the number of possible values is:

25 = 32

Two different rules may apply depending on routing protocol generation:

• Historical rule (RFC 950, classful routing): exclude the first (all-zeros) and
last (all-ones) subnet ⇒ 32 − 2 = 30 usable subnets.

• Modern rule (classless routing / CIDR): all subnets are usable ⇒ 32 usable
subnets.

Q4: How many hosts can each subnet contain?

Host addresses use the 0-bits of the mask. With a /21 mask, remaining host bits are:

32 − 21 = 11

Total addresses per subnet:

211 = 2048

Usable hosts per subnet:

2048 − 2 = 2046

Q5: What is the subnet (network) address?

The first two octets remain unchanged (they are fully in the network part): 172.16.
The third octet is partially network and partially host. Convert 19 to binary:

19 = 000100112

For /21, the third octet uses 5 network bits, so the mask bits in that octet are:

111110002

Bitwise AND:
00010011 & 11111000 = 000100002 = 16

14
Computer Networks Chapter IV: Network Layer

The fourth octet is in the host part, so it becomes 0 for the network address. Thus the
subnet address is:
[Link]

Q6: What is the broadcast address of the subnet?

The first two octets remain unchanged: 172.16.
The fourth octet becomes 255 (all host bits set to 1).
In the third octet, set the 3 host bits to 1 (since 8 bits total and 5 are network bits).
Host bits mask:
000001112

Bitwise OR:
00010011 | 00000111 = 000101112 = 23

Therefore, the broadcast address is:

[Link]

1.7 Private Networks and Address Translation (NAT)

Private networks were mainly introduced as a reaction to the inefficient use of the IPv4
address space. When the Internet started to grow, network prefixes were assigned to many
entities without strict control or accurate matching to real needs.
When addressing a private network, we distinguish two cases:

• If the private network is never connected to the Internet, it may use any IPv4
addresses.

• If the private network is connected to the Internet, it must use addresses

reserved for private use and deploy an address translation solution between
private addresses and one or more public addresses. Only public addresses are
visible on the Internet.

RFC 1918 defines the network prefixes reserved for private use. The three ranges
shown in Table 1.5 are not routed on the public Internet. In practice, if a public router
receives a packet whose source or destination IPv4 address belongs to one of these private
ranges, it is dropped.
In real deployments, the second case (private network connected to the Internet) is by
far the most common.

15
Computer Networks Chapter IV: Network Layer

Table 1.5: Table 5. Private IPv4 networks (RFC 1918)

CIDR
Class Default Mask Address Range
Notation

A [Link] [Link] – [Link] [Link]/8

B [Link] [Link] – [Link] [Link]/12
C [Link] [Link] – [Link] [Link]/16

1.7.1 NAT in home networks (“router/box” example)

In a typical home network, the Internet Service Provider (ISP) dynamically assigns one
(or more) public IP addresses to the WAN interface of the home router (the “box”).
All hosts inside the home network receive private IPv4 addresses. The source address
of each outgoing packet sent by a private host is translated to the public address of the
router.
Regardless of how many hosts (and private IPv4 addresses) exist inside the private
network, only one public IPv4 address may be used externally. This is how NAT
significantly reduces IPv4 address consumption from the Internet point of view.

Limitation of NAT
NAT is not perfect: hosts inside the private network are not directly reachable from
the public Internet. Additional mechanisms are required to manage transport-layer
port multiplexing (e.g., port forwarding, NAT traversal tools).

1.7.2 NAT on GNU/Linux: netfilter/iptables

On GNU/Linux systems, address translation mechanisms are integrated with packet filter-
ing through the netfilter/iptables framework. By design, NAT functions are commonly
used for two purposes:

• sharing a single public Internet interface among all hosts in a private network,

• making a server inside the private network accessible from the Internet.

1.7.3 SNAT and DNAT

Two main NAT types are distinguished:

• Source NAT (SNAT): the source IPv4 addresses of packets sent by private
hosts are rewritten using a public IPv4 address.

16
Computer Networks Chapter IV: Network Layer

• Destination NAT (DNAT): a public destination IPv4 address is rewritten

into a private IPv4 address depending on the requested destination (host/service).

The general mechanism of “IP address reuse” is standardized in RFC 3022.

1.7.4 Two typical traffic directions

• Access from the private network to the Internet: private host addresses are
translated to the address of the interface connected to the Internet.

• Access from the Internet to the private network: requests to services (HTTP,
DNS, mail, etc.) are translated to the corresponding server address inside the private
network (often through port forwarding / DNAT).

1.8 IP Protocol: IPv4 and IPv6

1.8.1 IPv4 overview and header fields

Figure 1.4: IP header format

IP is an unreliable and connectionless (best-effort) datagram protocol. Packets at the

IP layer are called datagrams. An IPv4 datagram is a variable-length packet made of:

• Header (20 to 60 bytes)

• Data (payload)

17
Computer Networks Chapter IV: Network Layer

Sizes to remember
• Minimum IPv4 header = 20 bytes

• Maximum IPv4 header = 60 bytes (with options)

• Total IPv4 datagram length field is 16 bits ⇒ max = 65 535 bytes

IPv4 Header Fields (explanation of each field)

Version (4 bits) Indicates the IP version. For IPv4, the value is 4.

IHL / HLEN (4 bits) Internet Header Length = header size expressed in 32-bit words
(multiples of 4 bytes).
Header bytes = IHL × 4

Minimum IHL = 5 ⇒ 20 bytes. Maximum IHL = 15 ⇒ 60 bytes.

DS / ToS (8 bits) Today this field is split into:

• DSCP (6 bits): QoS/priority marking (e.g., voice vs. data)

• ECN (2 bits): Explicit Congestion Notification (signals congestion without
dropping)

Total Length (16 bits) Total size of the IPv4 datagram in bytes:

Total Length = Header + Data

Range: 20 to 65 535 bytes.

Identification (16 bits) Used for fragmentation. All fragments of the same original
datagram share the same Identification value so the destination can reassemble
them.

Flags (3 bits) Fragmentation control bits:

• Bit 0: reserved (must be 0)

• DF (Don’t Fragment): if 1, routers must not fragment the packet
• MF (More Fragments): if 1, more fragments follow; last fragment has MF = 0

Fragment Offset (13 bits) Indicates where this fragment belongs in the original data-
gram. It is measured in units of 8 bytes. Example: offset = 185 means fragment
data starts at 185 × 8 = 1480 bytes.

18
Computer Networks Chapter IV: Network Layer

TTL (Time To Live) (8 bits) Prevents infinite loops. Decremented by 1 at each router
hop. When TTL reaches 0, the packet is dropped (usually with an ICMP Time Ex-
ceeded message).

Protocol (8 bits) Identifies the upper-layer protocol carried in the payload:

• 1 = ICMP 6 = TCP 17 = UDP

Header Checksum (16 bits) Checksum of the IPv4 header only (not the data). It
must be recomputed at each hop because fields like TTL change.

Source IP Address (32 bits) IPv4 address of the sender.

Destination IP Address (32 bits) IPv4 address of the receiver.

Options (0–40 bytes) + Padding Optional fields (rare in modern networks) used for
special functions (e.g., record route, timestamp). If options are present, padding is
added so the header length remains a multiple of 4 bytes (consistent with IHL).

Data (Payload)
The Data part contains the upper-layer segment (TCP/UDP/ICMP, etc.) and applica-
tion data. Its maximum size depends on the MTU of the path; large datagrams may
require fragmentation (IPv4) or should be avoided using Path MTU Discovery.

Why TTL matters

The TTL (Time To Live) field is decreased by 1 at each router. When it reaches
0, the packet is dropped, preventing infinite loops.

1.8.2 IPv6 Addressing

Reasons for Introducing IPv6

When IPv4 was first deployed, its exhaustion was not expected.
However, due to the major advancement of new technologies and the continuous growth
of the Internet, the world moved toward a shortage of IPv4 addresses.
More and more devices require IP addresses, which significantly increases the demand
for IPv4 addressing.
This address shortage is the main reason that pushed the IETF to launch a new version
of the IP protocol.
Several solutions were introduced to reduce this problem, namely: dividing a network
into multiple subnets (the CIDR principle: Classless Inter-Domain Routing) and address
translation (NAT: Network Address Translation).

19
Computer Networks Chapter IV: Network Layer

But these solutions are only short-term.

There are also other reasons that strongly supported the introduction of IPv6: the
rapid growth of routing tables and the emergence of new classes of applications (audio,
video, etc.).

General Format of an IPv6 Packet

The general format of an IPv6 packet consists of two parts: the base header, which has
a fixed size of 40 bytes, and the payload, which contains optional extension headers
and the data from upper layers.

Figure 1.5: the basic header of the package

Header structure:

Figure 1.6: Header structure

The header of an IPv6 packet consists of:

• Version (4 bits): this represents the IP protocol version number (here 6). Same
field as in IPv4 (value 4).

• Traffic Class (8 bits): this field is used for Quality of Service to identify traffic
classes; it replaces the IPv4 ToS field (to be verified ).

• Flow Label (20 bits): it allows marking special flows for differentiated processing.

• Payload Length (16 bits): this represents, in bytes, the size of the packet payload
after the header. It allows packets larger than 64 KB. It replaces the Total Length
field in IPv4.

20
Computer Networks Chapter IV: Network Layer

• Next Header (8 bits): indicates the type of header that immediately follows the
IPv6 header. Same idea as the Protocol field in IPv4 and the same values are used
(TCP=6, UDP=17, ICMP=1). Other IPv6-specific values are added (Hop-by-Hop
Option=0, Source routing=43, Fragmentation=44, etc.). This field is what enables
encoding optional extension headers.

• Hop Limit (8 bits): same as TTL in IPv4; it is decremented at each hop. If its
value reaches 0, the packet is destroyed. It helps eliminate routing loops.

• Source Address (128 bits) and Destination Address (128 bits): represent
respectively the address of the sender of the packet and the address of a destination
that may be different from the final destination address if the Routing Header option
is present.

N.B.: it is important to note that the fields ID, Flag, Fragment Offset, Checksum,
Header Length present in IPv4 are removed in IPv6.

Figure 1.7: ipv4 header and IPv6 header

IPv6 Optional Extension Headers :

IPv6 optional extension headers are identified by the Next Header field. Common values
include:

• 0: Hop-by-Hop Options (extension)

• 2: ICMP (payload)

• 6: TCP (payload)

21
Computer Networks Chapter IV: Network Layer

• 17: UDP (payload)

• 43: Routing Header (extension)

• 44: Fragment Header (extension)

• 50: ESP – Encapsulating Security Payload (IPsec)

• 51: AH – Authentication Header (IPsec)

• 59: No Next Header

• 60: Destination Options (extension)

Hop-by-Hop and Destination Options

Hop-by-Hop Options carry information that must be examined by every node along
the path. Destination Options carry information examined only by the destination
node(s).
Both share the same basic structure:

• Next Header (8 bits)

• Header Extension Length (8 bits): number of 8-byte units (excluding the first
8 bytes)

• Options (variable)

Each option can be described (conceptually) by:

• Action (2 bits) if the option is unknown:

– 00: skip the option

– 01: discard the packet
– 10: discard the packet and send ICMP
– 11: discard the packet and send ICMP if not multicast

• C (1 bit): whether the option may change in transit (0: no, 1: yes)

• Type / Option kind: e.g., Pad1, PadN, Jumbo Payload

• Length: size of the Data field (type and length not included)

• Data: option-specific content

22
Computer Networks Chapter IV: Network Layer

Routing Header
The Routing Header lets the source list intermediate nodes to visit on the way to the
destination. Key fields:

• Next Header (8 bits), Header Length (8 bits)

• Type (8 bits): routing header variant

• Segments Left (8 bits): number of listed nodes still to visit

Fragment Header
Used by the source when a packet is larger than the path MTU. (Routers do not fragment
in IPv6.) Key fields:

• Next Header (8 bits)

• Fragment Offset (13 bits): in 8-byte units

• M flag (1 bit): 1 = more fragments, 0 = last fragment

• Identification (32 bits): unique value for reassembly

Authentication Header (AH)

Provides source authentication and data integrity. Key fields:

• SPI (32 bits): identifies the Security Association (SA)

• Sequence Number (32 bits): increments per datagram

• Authentication Data (variable): integrity/authentication result

Encapsulating Security Payload (ESP)

Provides confidentiality (encryption) and can complement AH. Key fields:

• SPI (32 bits), Sequence Number (32 bits)

• Encrypted Payload Data (variable)

• Padding (variable) + Pad Length (8 bits)

• Next Header (8 bits)

23
Computer Networks Chapter IV: Network Layer

IV. Notation and Address Types

IV.1 Notation
The size of IP addresses has increased from 32 bits in IPv4 to 128 bits in IPv6; that is,
four times larger than IPv4.
With this size, it is possible to assign up to 5 × 1028 IP addresses per person, which is
currently impossible to exhaust.
Like IPv4 addresses, IPv6 addresses need an efficient notation for good presentation
and use by humans.

IV.1.1 Dotted Decimal Notation

The idea here is to reuse the same notation as in IPv4.

This consists of representing the address as 16 bytes (since 16 × 8 bits = 128 bits),
whose values are expressed in decimal and separated by dots (.).
Example:

[Link].[Link].[Link].[Link]

It is clearly evident that this representation is cumbersome, which is why it is rarely

used.
It has been improved by reducing the number of blocks and replacing “.” with “:” :
hexadecimal notation.

IV.1.2 Colon-Hexadecimal Notation (Colon Hex)

This consists of dividing the 128 bits into 8 blocks of 2 bytes each. Each block is repre-
sented by 4 hexadecimal digits. The blocks are separated by colons “:”.
General format (X represents a 4-bit portion):

XXXX1 : XXXX2 : XXXX3 : XXXX4 : XXXX5 : XXXX6 : XXXX7 : XXXX8

Example:

5F 06 : B500 : 89C2 : A100 : 0000 : 0800 : 200A : 3F F 7

This type of representation can be abbreviated for better simplicity and readability.

IV.1.3 Abbreviated Colon-Hex Notation

The idea is to try to reduce the length of IPv6 address writing.

24
Computer Networks Chapter IV: Network Layer

To do this, one must rely on a few rules.

Rule 1: Omission of leading zeros (0) in a block. Zeros that begin a block can be
omitted.
Example:

Figure 1.8:

Rule 1: Omission of leading zeros (0) in a block

05F 0 : 00B5 : 89C2 : 00A1 : 0000 : 0800 : 200A : 0000 becomes 5F 0 : B5 : 89C2 : A1 : 0 : 800 : 200A :

Rule 2: Compression of consecutive zero blocks A sequence of contiguous blocks

containing only zeros can be replaced by the symbol “::”.
However, this can be done only once in an address, and it is preferable to apply it to
the longest sequence of zero blocks.
Examples:

• For 2031:0000:130F:0000:0000:09C0:876A:130B

– 2031:0:130F::9C0:876A:130B is correct;
– 2031::130F::9C0:876A:130B is not correct;

• For 05F0:00B5:89C2:00A1:0000:0800:200A:0000

– 5F0:B5:89C2:A1::800:200A:0 is correct;
– 5F0:B5:89C2:A1:0:800:200A:: is correct;
– 5F0:B5:89C2:A1::800:200A:: is not correct;

25
Computer Networks Chapter IV: Network Layer

IV.1.4 Mixed Notation

This consists of using dotted-decimal notation for the last two blocks of an IPv6 address:

XXXX1 : XXXX2 : XXXX3 : XXXX4 : XXXX5 : XXXX6 : A.B.C.D

Example:
FEDC:14AB:2311:BBFE:AAAA:BBBB:[Link]

This notation is often used in:

• IPv4-compatible IPv6 address: This is the case of 6to4 tunnels (connecting

IPv4 networks to IPv6 networks); this type of notation is no longer used.

Figure 1.9:

• IPv4-mapped IPv6 address: This is the case of an IPv6 host that is able to
communicate with both an IPv4 host and an IPv6 host:

0::FFFF:[Link]/96

IV.1.5 Prefix Notation

Prefix representation is done like CIDR notation in IPv4. In this notation, the prefix
length is written as /number.
Examples:

• In IPv4: [Link]/16.

• In IPv6: 2001:DB8::12/40.

IV.2 Address Types

There are only three (3) types of IPv6 addresses:

• Unicast (Global, Unique Local, Link-Local): one-to-one;

• Multicast: one-to-many (to a group);

• Anycast: one-to-the-nearest (allocated from a Unicast address).

26
Computer Networks Chapter IV: Network Layer

With IPv6, there is no Broadcast (multicast is used instead).

Figure 1.10:

IV.2.1 Unicast Address

It designates one and only one network interface.
It is the most common communication mode.
It is composed of:

• A network part (prefix) encoded on 64 bits: 48 public bits “Global Routing Prefix”
and 16 site bits defining the subnet.

• A host part (suffix) also encoded on 64 bits: it is often built from the MAC address
of the interface and makes it possible to identify a machine in a given network.

Figure 1.11:

We distinguish three types of Unicast address: Link-Local, Unique Local, and Global.

IV.2.1.1 Link-Local Unicast Address (Link Local)

A Link-Local address has link-level scope (works only on a given link). It identifies only
machines that are in the same Layer 2 domain (same LAN).

27
Computer Networks Chapter IV: Network Layer

It is identified by the prefix FE80::/10 (the first 10 bits are fixed and equal in binary
to 1111111010).

Figure 1.12:

IV.2.1.2 Unique Local Unicast Address (ULA)

ULA addresses make it possible to identify all machines accessible within a site of the
same organization containing several local networks. They are intended for private use
and can be reused by other organizations without conflict. Their usage is similar to that
of private networks under IPv4, but without NAT. They are therefore not routable on the
Internet.
These addresses use the prefix FC00::/7 (binary value 11111100 or 11111101).

Figure 1.13:

IV.2.1.3 Global Unicast Address

A Global Unicast address makes it possible to identify all equipment accessible from the
Internet. It has global scope.
These types of addresses are the only unicast routable on the Internet.
They use the prefix 2000::/3 (binary value 0010).

IV.2.2 Multicast Address

A multicast address designates a given group of interfaces. An interface is free to subscribe
to a group or leave it at any time.
In IPv6, multicast is used instead of broadcast (the latter being a special case of
multicast).
Multicast addresses use the prefix FF00::/8.

28
Computer Networks Chapter IV: Network Layer

They have a field:

• Lifetime, encoded on 4 bits, following the prefix: one of its bits makes it possible to
distinguish permanent groups from temporary groups.

• Scope, on 4 bits: this field allows limited diffusion over an area (node, site, link,
organization, global).

• Group identifier, on 112 bits.

Figure 1.14:

Examples of some Multicast addresses:

• FF01: designates a local node, packets do not leave the interface.

• FF02: designates a local link, packets do not leave the link.

• FF05: designates a local site, packets do not leave the site.

• FF02::9: designates all RIPng routers.

• FF02::5: designates all OSPF routers.

• FF02::6: designates all designated routers.

• FF02::A: designates all EIGRP routers.

IV.2.3 Anycast Address

Its technique is similar to multicast in the sense that the destination address is a group
address. But the packet is delivered to only one member of the group (the closest according
to the routing protocols metric) instead of delivering it to all members.

29
Computer Networks Chapter IV: Network Layer

Figure 1.15:

Anycast addresses are defined to provide redundancy and load balancing.

IV.2.4 Other Address Types

There are other address types, namely:

• Reserved addresses:

– The unspecified address (::/128): it can be used as a source address during a

network address acquisition phase;
– The localhost address (::1/128), equivalent to [Link] in IPv4.

• Distinguished 2000::/3 addresses:

– Permanent addresses (2001::/16) open to reservation since 1999:

∗ 2001::/32 is used by Teredo;
∗ 2001:DB8::/32 is reserved for documentation by RFC 3849;
– 6to4 addresses (2002::/16) used to route IPv6 traffic through one or more
IPv4 networks;
– All other routable addresses (more than 3/4) are currently reserved for future
use.

IV.3 Allocation of Address Ranges

An IP address makes it possible to identify, on one side, a network and, on the other side,
a host within that network.

IV.3.1 Prefix Format

Out of the 128 bits of an IPv6 address, 10 bits are reserved to define the address type.
These bits are called the Prefix Format.

30
Computer Networks Chapter IV: Network Layer

Figure 1.16:

IV.3.2 Assigned Spaces

Within the IPv6 address space, there are blocks whose use is defined (3/8) and others
that are not assigned (5/8).

Figure 1.17:

IV.3.2.1 Allocation of the First Eighth

The first eighth is partially assigned:

Figure 1.18:

Within this space:

• The first block (1/256) is allocated for IPv4-compatible addresses and special ad-
dresses such as Loopback.

• The third block (1/128) is reserved for NSAP address allocation.

Block values table:

Figure 1.19:

31
Computer Networks Chapter IV: Network Layer

Let us focus on the use of the first block: 0000::/8.

This block has been allocated for unspecified, loopback, IPv4-compatible, and IPv4-
mapped addresses.

• Unspecified address:
It is an address whose 128 bits are all 0:

Figure 1.20:

It is widely used by a device that does not know its IP address and requests one.
It cannot be used as a destination address.
Notation: ::/128 or 0:0:0:0/128

• Loopback address:
This address provides network functionalities on a single device.
IPv6 allocates only one IP address, unlike IPv4 which allocates the whole network
[Link].
All the first 127 bits are 0 and the last bit is 1:

Figure 1.21:

This type of address is used to test application- or transport-layer software.

Notation: ::1/128 or 0:0:0:1/128

• IPv4-compatible address:
With this type of address, within the last 120 bits, 96 are 0 and the remaining 32
bits are occupied by the IPv4 address:

Figure 1.22:

This address is used to allow two IPv6 machines to communicate across an IPv4
network.
Notation: ::[Link]/96

32
Computer Networks Chapter IV: Network Layer

• IPv4-mapped IPv6 address:

It is an address whose first 88 bits are 0, the following 16 bits are 1, and the remaining
32 bits are occupied by the IPv4 address:

Figure 1.23:

This type of address is used by an IPv6 device that wants to communicate with an
IPv4 device.
Notation: 0::FFFF:[Link]/96

IV.3.2.2 Allocation of the Last Eighth

This space is partially assigned and contains Unique Local Unicast, Link-Local, and Mul-
ticast addresses.

Figure 1.24:

Block values table:

Figure 1.25:

33
Computer Networks Chapter IV: Network Layer

IV.3.2.3 Allocation of the Global Unicast Space

Figure 1.26:

With this type of address, we distinguish 3 aggregation levels:

Figure 1.27:

• Allocation process:
The first 48 bits of the Global Unicast space, which represent the Global Routing
Prefix, follow a very specific allocation process.
In the block 2000::/3, the IANA (Internet Assigned Numbers Authority) assigns
each registry (AfriNIC, APNIC, LACNIC, ARIN and RIPE NCC) a /12 prefix.
The registry allocates a /32 prefix or more to each IPv6 Internet Service Provider
(ISP).
Now, the strategy recommends that ISPs assign a /48 prefix to each end user.
For the 16 bits of the Subnet ID part, this allows end customers to have up to
216 = 65536 subnets.
The Interface ID part, on 64 bits, allows up to 264 hosts on each subnet. This part
makes it possible to create a relationship between the IPv6 address and the MAC
address.
Indeed, it is possible to integrate the MAC address, which is 48 bits, into the
Interface ID part of the IPv6 address using a mapping.

34
Computer Networks Chapter IV: Network Layer

1.9 Packet Fragmentation

1.9.1 MTU and why fragmentation occurs

In modern networking, data often needs to be transmitted across different networks with
varying maximum transmission unit (MTU) sizes. When a packet exceeds the MTU of a
network segment, it must be broken into smaller pieces called fragments. This process,
known as packet fragmentation, is a fundamental concept in network communications
that ensures data can traverse networks with different capabilities. What is Packet Frag-
mentation?
Packet fragmentation is the process of breaking a large packet into smaller pieces
(fragments) when the original packet is too large to be transmitted over a particular
network link. Each fragment becomes an independent packet that contains a portion
of the original data along with necessary header information to allow reassembly at the
destination.

Figure 1.28:

I-Key Components of IP Fragmentation :

1. Fragment Identification Fields
In IPv4, the IP header contains several fields specifically for managing fragmentation:

35
Computer Networks Chapter IV: Network Layer

Figure 1.29:

• Identification: A 16-bit value that is the same for all fragments of a packet.

• Flags: 3 bits where:

– Bit 0: Reserved.
– Bit 1: DF (Don’t Fragment) – when set, packet cannot be fragmented.
– Bit 2: MF (More Fragments) – when set, more fragments follow.

• Fragment Offset: Indicates where in the original packet this fragment belongs (in
8-byte units).

2. Fragmentation Process

Figure 1.30:

Practical Example: Tracing a Fragmented Packet

Let’s trace a 4KB packet being sent through a network with a 1500-byte MTU:

36
Computer Networks Chapter IV: Network Layer

FRAGMENTATION EXAMPLE
Original Packet: 4000 bytes + 20 byte IPv4 header = 4020B
MTU = 1500 bytes
Maximum payload per fragment = 1500 - 20 = 1480 bytes
Fragment 1:
– IP Header (20B) with MF=1, Offset=0
– Data: 1480 bytes (0–1479)
Fragment 2:
– IP Header (20B) with MF=1, Offset=185 (1480/8=185)
– Data: 1480 bytes (1480–2959)
Fragment 3:
– IP Header (20B) with MF=0, Offset=370 (2960/8=370)
– Data: 1040 bytes (2960–3999)
Problem. An IPv4 router with a Maximum Transmission Unit (MTU) of 200 bytes
receives an IPv4 packet of total size 520 bytes. The IPv4 header length is 20 bytes.
Determine the fragmentation and the values of the relevant IPv4 header fields for each
fragment.

Given

MTU = 200 bytes, Header length = 20 bytes, Original total length = 520 bytes

Step 1: Compute the original payload size

Payload = 520 − 20 = 500 bytes

Step 2: Maximum payload per fragment (MTU constraint)

Each fragment must fit within the MTU including its own IPv4 header:

Max data = MTU − Header = 200 − 20 = 180 bytes

Step 3: Enforce 8-byte alignment for the Fragment Offset

The Fragment Offset is measured in units of 8 bytes, so all fragments except the last
should carry a data size that is a multiple of 8.

180 ̸≡ 0 (mod 8) ⇒ use 176 bytes (nearest multiple of 8 below 180)

Thus:
Data per full fragment = 176 bytes

37
Computer Networks Chapter IV: Network Layer

Step 4: Number of fragments

500
≈ 2.84 ⇒ need 3 fragments
176
Data carried:
Fragment 1 data = 176
Fragment 2 data = 176
Fragment 3 data = 500 − (176 + 176) = 148

Step 5: Fragment Offset values

Offsets are in 8-byte units, counting from the start of the original payload:

Frag 1 offset = 0/8 = 0

Frag 2 offset = 176/8 = 22
Frag 3 offset = (176 + 176)/8 = 352/8 = 44

Relevant IPv4 header fields (per fragment)

Assume IPv4 with no options:

Version = 4, IHL = 5 (⇒ 20 bytes)

The Identification field is the same for all fragments (router copies it). The DF flag is
0 (since fragmentation occurs). The MF flag is 1 for all but the last fragment.

Fragment Header(B) Data(B) Total Length(B) Offset(8B units) Flags(DF,MF)

1 20 176 20 + 176 = 196 0 (0, 1)
2 20 176 20 + 176 = 196 22 (0, 1)
3 20 148 20 + 148 = 168 44 (0, 0)

The packet is fragmented into 3 fragments. The relevant header values are summa-
rized in the table above: total lengths (196, 196, 168) bytes, fragment offsets (0, 22, 44)
in 8-byte units, and MF set for the first two fragments only.
II-Challenges with Fragmentation
a. Performance Impact:
Fragmentation can impact network performance in several ways:

38
Computer Networks Chapter IV: Network Layer

Figure 1.31:

b. Fragmentation in IPv6:
IPv6 handles fragmentation differently from IPv4:

• Routers do not fragment packets in IPv6.

• Only the source node can fragment packets.

• Path MTU Discovery is mandatory.

• Fragment headers are extension headers.

c. Fragmentation Attacks:
Fragmentation can be exploited for various attacks:

• Tiny Fragment Attack: Using small fragments to bypass security filters.

• Overlapping Fragment Attack: Creating fragments that overlap in confusing

ways.

• Fragment Exhaustion Attack: Sending many fragments to exhaust reassembly

resources.

III-Mitigating Fragmentation Issues

a. Path MTU Discovery (PMTUD)
PMTUD helps avoid fragmentation by discovering the smallest MTU along a path:

39
Computer Networks Chapter IV: Network Layer

Figure 1.32:

b. MSS Clamping
MSS (Maximum Segment Size) clamping adjusts the TCP MSS to prevent fragmen-
tation:

Figure 1.33:

1.10 Packet Switching

1.10.1 Principle
Packet switching breaks messages into packets that are forwarded independently:

• each packet can take a different route,

• links are shared statistically among flows,

• routers perform store-and-forward: receive, store briefly, then forward.

40
Computer Networks Chapter IV: Network Layer

1.10.2 Packet switching vs circuit switching (idea)

• Circuit switching: reserves resources, stable delay, but inefficient when idle.

• Packet switching: efficient resource sharing, but variable delay under congestion.

R1
Packet 1 Packet 1

Host A Host B

Packet 2 Packet 2
R2

Figure 1.34: Example: packets may follow different routes

1.11 Routing: Centralized and Distributed Techniques

Figure 1.35:

Routing is the process of forwarding packets from one network to another by choosing
the best path from the routing table.
A routing table contains only the best routes to each destination.

41
Computer Networks Chapter IV: Network Layer

Types of Routing
There are three ways a router can learn a route to a destination:

1. Static Routing

• It is configured manually by the administrator.

• It requires the destination network ID.

• It is secure and fast.

• It is used in small organizations that have networks of about 10 to 15 routers.

2. Dynamic Routing

• It means automatic routing.

• In dynamic routing, the router learns paths to destinations by receiving periodic

updates from other routers.

• It automatically chooses the best and shortest path.

• It is done using routing protocols.

3. Default Routing

• It is configured for unknown destinations.

• When there is no entry for the destination network in the routing table, the router
forwards the packet to its default router.

• It is the least preferred type of routing.

Two Key Network-Layer Functions

1. Forwarding: moving a packet from a router’s input to the appropriate router
output.

2. Routing: determining the route taken by packets from source to destination.

42
Computer Networks Chapter IV: Network Layer

Routing Algorithm
The main function of the network layer is to route packets from source to destination.
A routing algorithm is the part of the network-layer software responsible for deciding
which output line an incoming packet should be transmitted on.
Routing algorithms can be grouped into two major classes:

• Static (non-adaptive)

• Dynamic (adaptive)

Non-Adaptive and Adaptive Algorithms

Non-Adaptive Algorithms (Static Routing)

• They do not base their routing decisions on measurements or estimates of the current
traffic and topology.

• They are called static algorithms.

Adaptive Algorithms (Dynamic Routing)

• They change their routing decisions to reflect changes in the topology and usually
the traffic as well.

• They are called dynamic algorithms.

1.11.1 Static Algorithms

1. Flooding routing

2. Shortest path routing

Flooding
• Flooding is a simple local technique in which each router makes decisions based only
on local knowledge, not on the complete picture of the network.

• It is a simple algorithm that sends a packet along all paths.

• Every incoming packet is sent out on every outgoing line except the one on which
it arrived.

• It generates an infinite number of duplicate packets unless some measures are taken
to limit the process.

43
Computer Networks Chapter IV: Network Layer

• One such measure is to include a hop counter in the header of each packet. This
counter is decremented at each hop, and the packet is discarded when the counter
reaches zero.

Shortest Path Routing

• Shortest path routing was first developed using Dijkstra’s algorithm.

• It finds the shortest path from a specified source to all other destinations in the
network.

• In the general case, the labels on the links can be computed as a function of distance,
bandwidth, average traffic, communication cost, measured delay, and other factors.

1.11.2 Dynamic Routing Algorithm

1. Distance Vector Routing

2. Link State Routing

1-Distance Vector Routing

• Distance vector routing is an intra-domain protocol, which means it is used
inside an Autonomous System (AS), not between Autonomous Systems.

• Distance vector routing is based on the least-cost objective.

• It was developed using the Bellman-Ford algorithm.

• The Bellman equation is used to find the least cost, or shortest distance, between
a source and a destination.

• In a distance vector routing algorithm, each router maintains a table, or vector, that
gives the best known distance to each destination.

• These tables are updated by exchanging information with neighboring routers.

• Every router knows the best link to reach each destination.

• A distance vector router tells only its neighbors about all routes.

• RIP is based on distance vector routing. Each router shares, at regular intervals,
its knowledge about the entire Autonomous System with its neighbors.

• It is slow and does not take bandwidth into consideration when choosing the route.

44
Computer Networks Chapter IV: Network Layer

2-Link State Routing

The main problem with distance vector routing is that the algorithm often takes too long
to converge after the network topology changes, mainly because of the count-to-infinity
problem. Therefore, it was replaced by a new algorithm called link state routing.
The idea behind link state routing is simple and can be summarized in five steps. Each
router must:

1. Discover its neighbors and learn their network addresses.

2. Measure the delay or cost to each of its neighbors.

3. Construct a packet containing everything it has just learned.

4. Send the packet to all other routers.

5. Compute the shortest path to every other router.

Note that a link-state router tells all other routers only about its own neighbors
and links.
Compared with distance vector routing, link state routing requires more memory and
more computation. Also, the computation time grows faster.
Nevertheless, in many practical situations, link state routing works well because it
does not suffer from slow convergence problems.

OSPF
OSPF (Open Shortest Path First) is a link-state routing protocol used within
an Autonomous System. It exchanges link-state information among routers, builds a
complete view of the network topology, and uses Dijkstra’s algorithm to calculate the
shortest path tree and determine the best route to each destination.

45
Computer Networks Chapter IV: Network Layer

Distance Vector Link State

[leftmargin=*,nosep] [leftmargin=*,nosep]

• Entire routing table is sent as an • Updates are incremental, and the

update. entire routing table is not sent as
an update.
• Distance vector protocol sends pe-
riodic updates every 30 or 90 sec- • Updates are triggered, not periodic.
onds.
• Updates are sent throughout the
• Updates are sent only to directly network, not just to directly con-
connected neighbors. nected neighbors.

• Routers do not have end-to-end vis- • Routers have visibility of the entire
ibility of the entire network. network within that area only.

• Suffers from the count-to-infinity • No routing loops.

problem.
• Convergence is fast because of trig-
• Slow convergence after network gered updates.
topology changes due to the count-
• Examples: OSPF, IS-IS.
to-infinity problem.
• More difficult to configure.
• Examples: RIP, BGP.

• Easy to configure.

1.11.3 Hierarchical Routing

As networks grow in size, router routing tables grow proportionally.

• Not only is router memory consumed by ever-increasing tables, but more CPU time
is also needed to scan them, and more bandwidth is required to send status reports
about them.

• Therefore, a router cannot maintain a table for the entire network.

• When hierarchical routing is used, routers are divided into regions.

• Each router knows all the details needed to route packets to destinations within its
own region, but it knows nothing about the internal structure of other regions.

46
Computer Networks Chapter IV: Network Layer

Figure 1.36:

1.11.4 Broadcast Routing and Multicast Routing

For some applications, hosts need to send messages to many or all other hosts. Broadcast
routing is used for this purpose.

• The source should send the packet to all the required destinations.

• One problem with this method is that the source has to maintain the complete list
of destinations.

• A better broadcast routing technique is flooding.

Sending a message to a specific group is called multicasting, and the routing algo-
rithm used is called multicast routing.

• All multicasting schemes require a way to create and delete groups.

• They also require a mechanism to identify which routers are members of a group.

1.11.5 Routing Protocols

A routing protocol is a combination of rules and procedures that allows routers on the
Internet to inform each other about network changes.

• Routing metric: a method used by routing algorithms to determine that one route
is better than another.

• Common metrics include hop count, bandwidth, delay, and load.

47
Computer Networks Chapter IV: Network Layer

Interior versus Exterior Routing Protocols

An Autonomous System (AS), also known as a domain, is a collection of routers

under a common administration, such as a company’s internal network or an Internet
Service Provider’s (ISP’s) network.
Because the Internet is based on the AS concept, two types of routing protocols are
required:

1. Interior Gateway Protocols (IGPs): handle routing within an Autonomous

System. IGPs determine how to move packets between routers inside the same AS.

2. Exterior Gateway Protocols (EGPs): handle routing outside an Autonomous

System. EGPs move packets from one AS to another through external networks.

Interior Gateway Protocols (IGP)

• IGPs are intra-AS (inside an AS) routing protocols.

• Examples of IGPs include:

– Routing Information Protocol (RIP), including RIPv2

– Open Shortest Path First (OSPF)
– Enhanced Interior Gateway Routing Protocol (EIGRP)

• They use less complicated metrics to simplify configuration and speed up decisions
about the best routing paths, which leads to faster convergence.

Exterior Gateway Protocols (EGP)

• EGPs are inter-AS (between Autonomous Systems) routing protocols.

• Border Gateway Protocol (BGP) is the only widely used EGP on the Internet.

• BGP version 4 (BGP-4) is the standard version used on the Internet.

• EGPs are generally slower to converge and more complex to configure.

48
Computer Networks Chapter IV: Network Layer

Figure 1.37:

Popular Routing Protocols

Figure 1.38:

I-Routing Information Protocol (RIP)

• RIP is a routing protocol used for exchanging routing table information between
routers.

• It is a very simple protocol based on distance vector routing.

• It is a simple intra-domain routing protocol.

• RIP uses hop count as a path selection metric.

• RIP prevents routing loops by implementing a limit on the number of hops allowed
in a path from the source to a destination.

• The maximum number of hops allowed in RIP is 15.

49
Computer Networks Chapter IV: Network Layer

• This hop limit also limits the size of networks that RIP can support.

• A hop count of 16 is considered an infinite distance; in other words, the route is

considered unreachable.

Figure 1.39:

• There are three types of timers in RIP routing protocol, these are:

Figure 1.40:

1. Routing-Update Timer (Periodic Timer): The periodic timer controls the

advertisement of regular update messages. Routers send updates every 30 seconds.

2. Route Timeout (Expiration Timer): If there is a problem in the network and

no update is received within the allotted 180 seconds, the route is considered
expired, and the hop count of the route is set to 16, which means the destination is
unreachable.

3. Route-Flush Timer (Garbage Collection Timer): After the route timeout

expires, the route-flush timer eventually expires, deleting the route from the routing
table.

50
Computer Networks Chapter IV: Network Layer

Drawbacks of RIP

• RIP has slow convergence and suffers from the count-to-infinity problem.

• The hop count cannot exceed 15; otherwise, the route is dropped.

Figure 1.41:

Figure 1.42:

Figure 1.43:

51
Computer Networks Chapter IV: Network Layer

Figure 1.44:

II-Open Shortest Path First (OSPF)

The most important features of OSPF are as follows:

1. This protocol is open, which means that anyone can implement it without paying
license fees.

2. OSPF uses a link-state routing algorithm and belongs to the group of interior
routing protocols, operating within a single Autonomous System (AS). OSPF
is one of the most widely used Interior Gateway Protocols (IGPs) in large
enterprise networks.

3. Each node maintains a topology map.

4. Route computation is performed using Dijkstra’s algorithm.

5. Advertisements are flooded throughout the entire AS.

6. The OSPF metric calculation is based on cost. Cost indicates the overhead required
to send packets across a certain interface.

7. Security: all OSPF messages are authenticated to prevent malicious intrusion.

8. OSPF supports a hierarchical design in large domains.

Hierarchical OSPF

To minimize processing and memory requirements, OSPF can divide the routing topology
of an Autonomous System into a two-layer hierarchy called the local area (standard area)
and the backbone area (referred to as Area 0 or the Transit Area).
The main advantages of this division are:

1. It localizes the impact of a topology change within an area.

52
Computer Networks Chapter IV: Network Layer

2. Detailed Link-State Advertisement (LSA) flooding occurs only within an area

and stops at the area boundary.

3. Each router within an area has a detailed view of the area’s topology and knows
only the direction (shortest path) to networks in other areas.

OSPF Router Types

OSPF routers may function as either:

• Internal Router: operates entirely within a single area.

• Backbone Router: runs OSPF routing limited to the backbone area.

• Area Border Router (ABR): connects local areas to the backbone area. It
summarizes distances to networks in its own area and advertises them to other Area
Border Routers.

• Autonomous System Boundary Router (ASBR): connects the OSPF Au-

tonomous System to other Autonomous Systems.

Figure 1.45:

Advantages of OSPF over RIP

OSPF is superior to RIP in many aspects, including the following:

• It converges much faster.

• It supports hierarchical structures.

• It provides improved metric calculation for better path selection.

• It does not have hop-count limitations.

• From its inception, OSPF was designed to support large networks.

53
Computer Networks Chapter IV: Network Layer

• Compared with RIP, OSPF has no hop limitation. In RIP, the maximum hop count
is 15, so any network requiring more than 15 hops cannot be reached using RIP.

III-Enhanced Interior Gateway Routing Protocol (EIGRP)

• EIGRP is a routing protocol used for both IPv4 and IPv6.

• EIGRP is a hybrid routing protocol; it is primarily a distance vector protocol

with additional link-state features.

• It uses triggered updates, which means it does not send periodic updates.

• It provides fast convergence, which helps minimize network traffic.

• EIGRP uses the minimum bandwidth along the path to the destination network
and calculates the route using the total delay metric.

IIII-Border Gateway Protocol (BGP)

• BGP is an inter-domain routing protocol used for routing between Autonomous

Systems (ASs).

• It is considered the protocol that holds the Internet together.

• BGP is neither a link-state protocol nor a distance vector protocol.

• Routing messages in BGP contain complete routes.

• Network administrators can specify routing policies, which gives BGP a high
degree of flexibility.

• Paths may be selected according to provider or administrative policy, not necessarily

only by shortest distance.

• The main goal of BGP is to find any valid path, not necessarily the optimal one.

Internal and External BGP Sessions

iBGP eBGP
Used to connect routers within the Used to connect routers in different
same Autonomous System (AS). Autonomous Systems (ASs).
Used inside the same company or or- Used between different companies or
ganization. service providers.
Propagates reachability information Obtains subnet reachability informa-
to all routers inside the AS. tion from neighboring ASs.

54
Computer Networks Chapter IV: Network Layer

Figure 1.46:

BGP Basics

1. BGP Session: Two BGP routers, called peers, exchange BGP messages.

• They advertise paths to different destination network prefixes.

• For example, when AS3 advertises a prefix to AS1, AS3 promises that it will
forward datagrams toward that prefix.
• BGP is therefore called a path-vector protocol.
• These messages are exchanged over semi-permanent TCP connections.
• AS3 can also aggregate prefixes in its advertisement.

Figure 1.47:

2. Distributing Path (Reachability) Information:

• Using an eBGP session between routers 3a and 1c, AS3 sends prefix reacha-
bility information to AS1.
• Router 1c can then use iBGP to distribute the new prefix information to all
routers inside AS1.
• Router 1b can then re-advertise the new reachability information to AS2 over
the 1b-to-2a eBGP session.
• When a router learns a new prefix, it creates an entry for that prefix in its
forwarding table.

55
Computer Networks Chapter IV: Network Layer

Figure 1.48:

BGP Route Selection

A router may learn more than one route to the same destination Autonomous System
(AS). In such cases, BGP selects the best route based on the following criteria:

1. Local Preference Value: the route with the preferred local policy is selected first.

2. Shortest AS-PATH: the route with the shortest AS path is preferred.

3. Closest NEXT-HOP Router: the route with the nearest next-hop router is
selected.

4. Additional Criteria: if needed, BGP applies other tie-breaking rules.

BGP Messages

BGP messages are exchanged between peers over a TCP connection. BGP has four
types of messages:

• OPEN: establishes a connection with a BGP peer.

• UPDATE: advertises new routes or withdraws routes to a destination.

• KEEPALIVE: informs a peer that the sender is still active, even if it has no new
information to send.

• NOTIFICATION: indicates that an error has been detected and is also used to
close the connection.

1.11.6 Static and Dynamic routing table

i- Static Routing Table

The following static routing tables are based on the topology shown in the figure.

56
Computer Networks Chapter IV: Network Layer

Figure 1.49:

1.11.7 Example: Static Routing Table

Known Addressing

• Link between Router 1 and Router 2: [Link]/30

– Router 1 = [Link]
– Router 2 = [Link]

• Link between Router 1 and Router 3: [Link]/30

– Router 1 = [Link]
– Router 3 = [Link]

• Link between Router 2 and Router 3: [Link]/30

– Router 2 = [Link]
– Router 3 = [Link]

• LAN behind Router 3: [Link]/24

– Router 3 = [Link]

57
Computer Networks Chapter IV: Network Layer

Router 1 Routing Table

Destination Mask Next Hop Route Type

Network
[Link] [Link] — Connected
[Link] [Link] — Connected
[Link] [Link] [Link] Static
[Link] [Link] [Link] Static

Table 1.6: Static routing table for Router 1

Router 2 Routing Table

Destination Mask Next Hop Route Type

Network
[Link] [Link] — Connected
[Link] [Link] — Connected
[Link] [Link] [Link] Static
[Link] [Link] [Link] Static

Table 1.7: Static routing table for Router 2

Router 3 Routing Table

Destination Mask Next Hop Route Type

Network
[Link] [Link] — Connected
[Link] [Link] — Connected
[Link] [Link] — Connected
[Link] [Link] [Link] Static

Table 1.8: Static routing table for Router 3

Explanation

In static routing, the administrator manually configures routes to remote networks.

• Router 1 is directly connected to [Link]/30 and [Link]/30.

• Router 2 is directly connected to [Link]/30 and [Link]/30.

• Router 3 is directly connected to [Link]/30, [Link]/30, and [Link]/24.

• Remote networks are reached through manually configured next-hop addresses.

58
Computer Networks Chapter IV: Network Layer

ii- Dynamic Routing Table

The following routing example is derived only from the addresses shown in the figure.

Figure 1.50:

Known Addressing from the Figure

• Link between Router 1 and Router 2: [Link]/30

– Router 1 = [Link]
– Router 2 = [Link]

• Link between Router 1 and Router 3: [Link]/30

– Router 1 = [Link]
– Router 3 = [Link]

• Link between Router 2 and Router 3: [Link]/30

– Router 2 = [Link]
– Router 3 = [Link]

• LAN behind Router 2: [Link]/26

– Router 2 = [Link]
– Host = [Link]

• LAN behind Router 3: [Link]/26

59
Computer Networks Chapter IV: Network Layer

– Router 3 = [Link]
– Host = [Link]

Important Note

The exact routing table depends on the dynamic routing protocol used (RIP, OSPF,
or EIGRP) and on the metric values. Also, the links connected to Router 4 are not
labeled in the figure, so its full routing table cannot be determined exactly from the image
alone.

Router 1

Destination Type Next Hop Explanation

[Link]/30 Connected — Directly connected to
Router 2
[Link]/30 Connected — Directly connected to
Router 3
[Link]/30 Dynamic [Link] or Reached through Router 2
[Link] or Router 3, depending on
protocol and metric
[Link]/26 Dynamic [Link] LAN behind Router 2
[Link]/26 Dynamic [Link] LAN behind Router 3

Table 1.9: Example routing table for Router 1

Router 2

Destination Type Next Hop Explanation

[Link]/30 Connected — Directly connected to
Router 1
[Link]/30 Connected — Directly connected to
Router 3
[Link]/26 Connected — Local LAN of Router 2
[Link]/30 Dynamic [Link] or Reached through Router 1
[Link] or Router 3, depending on
protocol and metric
[Link]/26 Dynamic [Link] LAN behind Router 3

Table 1.10: Example routing table for Router 2

Router 3

Explanation

In dynamic routing, routers learn remote networks automatically from neighboring routers.

60
Computer Networks Chapter IV: Network Layer

Destination Type Next Hop Explanation

[Link]/30 Connected — Directly connected to
Router 1
[Link]/30 Connected — Directly connected to
Router 2
[Link]/26 Connected — Local LAN of Router 3
[Link]/30 Dynamic [Link] or Reached through Router 1
[Link] or Router 2, depending on
protocol and metric
[Link]/26 Dynamic [Link] LAN behind Router 2

Table 1.11: Example routing table for Router 3

• Router 1 directly knows [Link]/30 and [Link]/30.

• Router 1 learns [Link]/26 from Router 2.

• Router 1 learns [Link]/26 from Router 3.

• Router 2 directly knows [Link]/30, [Link]/30, and [Link]/26.

• Router 3 directly knows [Link]/30, [Link]/30, and [Link]/26.

1.12 Questions and Exercises

1. Explain the difference between physical addressing (MAC) and logical address-
ing (IP).

2. For the network [Link]/24, propose a subdivision into 8 subnets and provide:

• the new prefix length,

• the usable host range of the 3rd subnet,
• the broadcast address of the last subnet.

3. Why does IPv6 avoid router fragmentation?

4. An IPv4 datagram is 3000 bytes (20-byte header). MTU = 1000. Compute the
number of fragments and offsets.

5. Compare Distance-Vector and Link-State (exchanged info, convergence, complex-

ity).

6. Give one practical example for static routing and one for dynamic routing.

7. Explain the concept of an AS and why BGP is needed on the Internet.

61
Computer Networks Chapter IV: Network Layer

References (optional)
• IPv4 fundamentals and fragmentation concepts.

• IPv6 basics, extension headers, and Path MTU Discovery.

• Routing protocols overview: RIP, OSPF, BGP (principles).

62