528 PART IV NETWORK LAYER
Choke Packet A choke packet is a packet sent by a node to the source to inform it of
congestion. Note the difference between the backpressure and choke-packet methods.
In backpressure, the warning is from one node to its upstream node, although the warn-
ing may eventually reach the source station. In the choke-packet method, the warning is
from the router, which has encountered congestion, directly to the source station. The
intermediate nodes through which the packet has traveled are not warned. We will see
an example of this type of control in ICMP (discussed in Chapter 19). When a router in
the Internet is overwhelmed with IP datagrams, it may discard some of them, but it
informs the source host, using a source quench ICMP message. The warning message
goes directly to the source station; the intermediate routers do not take any action. Fig-
ure 18.15 shows the idea of a choke packet.
Figure 18.15 Choke packet
-
Choke
packet
I II III IV
Source Congestion Destination
Data flow
Implicit Signaling In implicit signaling, there is no communication between the
congested node or nodes and the source. The source guesses that there is congestion
somewhere in the network from other symptoms. For example, when a source sends
several packets and there is no acknowledgment for a while, one assumption is that the
network is congested. The delay in receiving an acknowledgment is interpreted as con-
gestion in the network; the source should slow down. We saw this type of signaling
when we discuss TCP congestion control in Chapter 24.
Explicit Signaling The node that experiences congestion can explicitly send a signal
to the source or destination. The explicit-signaling method, however, is different from
the choke-packet method. In the choke-packet method, a separate packet is used for this
purpose; in the explicit-signaling method, the signal is included in the packets that carry
data. Explicit signaling can occur in either the forward or the backward direction. This
type of congestion control can be seen in an ATM network, discussed in Chapter 14.
18.4 IPV4 ADDRESSES
The identifier used in the IP layer of the TCP/IP protocol suite to identify the connec-
tion of each device to the Internet is called the Internet address or IP address. An IPv4
address is a 32-bit address that uniquely and universally defines the connection of a
host or a router to the Internet. The IP address is the address of the connection, not the
CHAPTER 18 INTRODUCTION TO NETWORK LAYER 529
host or the router, because if the device is moved to another network, the IP address
may be changed.
IPv4 addresses are unique in the sense that each address defines one, and only one,
connection to the Internet. If a device has two connections to the Internet, via two
networks, it has two IPv4 addresses. IPv4 addresses are universal in the sense that the
addressing system must be accepted by any host that wants to be connected to the
Internet.
18.4.1 Address Space
A protocol like IPv4 that defines addresses has an address space. An address space is
the total number of addresses used by the protocol. If a protocol uses b bits to define an
address, the address space is 2b because each bit can have two different values (0 or 1).
IPv4 uses 32-bit addresses, which means that the address space is 232 or 4,294,967,296
(more than four billion). If there were no restrictions, more than 4 billion devices could
be connected to the Internet.
Notation
There are three common notations to show an IPv4 address: binary notation (base 2),
dotted-decimal notation (base 256), and hexadecimal notation (base 16). In binary
notation, an IPv4 address is displayed as 32 bits. To make the address more readable, one
or more spaces are usually inserted between each octet (8 bits). Each octet is often
referred to as a byte. To make the IPv4 address more compact and easier to read, it is usu-
ally written in decimal form with a decimal point (dot) separating the bytes. This format is
referred to as dotted-decimal notation. Note that because each byte (octet) is only 8 bits,
each number in the dotted-decimal notation is between 0 and 255. We sometimes see an
IPv4 address in hexadecimal notation. Each hexadecimal digit is equivalent to four bits.
This means that a 32-bit address has 8 hexadecimal digits. This notation is often used in
network programming. Figure 18.16 shows an IP address in the three discussed notations.
Figure 18.16 Three different notations in IPv4 addressing
Binary 10000000 00001011 00000011 00011111
Dotted decimal 128 . 11 . 3 . 31
Hexadecimal 80 0B 03 1F
Hierarchy in Addressing
In any communication network that involves delivery, such as a telephone network or a
postal network, the addressing system is hierarchical. In a postal network, the postal
address (mailing address) includes the country, state, city, street, house number, and the
530 PART IV NETWORK LAYER
name of the mail recipient. Similarly, a telephone number is divided into the country
code, area code, local exchange, and the connection.
A 32-bit IPv4 address is also hierarchical, but divided only into two parts. The first
part of the address, called the prefix, defines the network; the second part of the
address, called the suffix, defines the node (connection of a device to the Internet). Fig-
ure 18.17 shows the prefix and suffix of a 32-bit IPv4 address. The prefix length is
n bits and the suffix length is (32 − n) bits.
Figure 18.17 Hierarchy in addressing
32 bits
n bits (32 – n) bits
Prefix Suffix
Defines network Defines connection
to the node
Network
A prefix can be fixed length or variable length. The network identifier in the IPv4
was first designed as a fixed-length prefix. This scheme, which is now obsolete, is
referred to as classful addressing. The new scheme, which is referred to as classless
addressing, uses a variable-length network prefix. First, we briefly discuss classful
addressing; then we concentrate on classless addressing.
18.4.2 Classful Addressing
When the Internet started, an IPv4 address was designed with a fixed-length prefix, but
to accommodate both small and large networks, three fixed-length prefixes were
designed instead of one (n = 8, n = 16, and n = 24). The whole address space was
divided into five classes (class A, B, C, D, and E), as shown in Figure 18.18. This
scheme is referred to as classful addressing. Although classful addressing belongs to
the past, it helps us to understand classless addressing, discussed later.
In class A, the network length is 8 bits, but since the first bit, which is 0, defines
the class, we can have only seven bits as the network identifier. This means there are
only 27 = 128 networks in the world that can have a class A address.
In class B, the network length is 16 bits, but since the first two bits, which are
(10)2, define the class, we can have only 14 bits as the network identifier. This means
there are only 214 = 16,384 networks in the world that can have a class B address.
All addresses that start with (110)2 belong to class C. In class C, the network
length is 24 bits, but since three bits define the class, we can have only 21 bits as the
network identifier. This means there are 221 = 2,097,152 networks in the world that can
have a class C address.
CHAPTER 18 INTRODUCTION TO NETWORK LAYER 531
Figure 18.18 Occupation of the address space in classful addressing
Address space: 4,294,967,296 addresses
A B C D E
50% 25% 12.5% 6.25%6.25%
8 bits 8 bits 8 bits 8 bits
Class Prefixes First byte
Class A 0 Prefix Suffix A n = 8 bits 0 to 127
Class B 10 Prefix Suffix B n = 16 bits 128 to 191
Class C 110 Prefix Suffix C n = 24 bits 192 to 223
Class D 1110 Multicast addresses D Not applicable 224 to 239
Class E 1111 Reserved for future use E Not applicable 240 to 255
Class D is not divided into prefix and suffix. It is used for multicast addresses. All
addresses that start with 1111 in binary belong to class E. As in Class D, Class E is not
divided into prefix and suffix and is used as reserve.
Address Depletion
The reason that classful addressing has become obsolete is address depletion. Since the
addresses were not distributed properly, the Internet was faced with the problem of the
addresses being rapidly used up, resulting in no more addresses available for organiza-
tions and individuals that needed to be connected to the Internet. To understand the prob-
lem, let us think about class A. This class can be assigned to only 128 organizations in
the world, but each organization needs to have a single network (seen by the rest of the
world) with 16,777,216 nodes (computers in this single network). Since there may be
only a few organizations that are this large, most of the addresses in this class were
wasted (unused). Class B addresses were designed for midsize organizations, but many
of the addresses in this class also remained unused. Class C addresses have a completely
different flaw in design. The number of addresses that can be used in each network (256)
was so small that most companies were not comfortable using a block in this address
class. Class E addresses were almost never used, wasting the whole class.
Subnetting and Supernetting
To alleviate address depletion, two strategies were proposed and, to some extent,
implemented: subnetting and supernetting. In subnetting, a class A or class B block is
divided into several subnets. Each subnet has a larger prefix length than the original
network. For example, if a network in class A is divided into four subnets, each subnet
has a prefix of nsub = 10. At the same time, if all of the addresses in a network are not
used, subnetting allows the addresses to be divided among several organizations. This
idea did not work because most large organizations were not happy about dividing the
block and giving some of the unused addresses to smaller organizations.
While subnetting was devised to divide a large block into smaller ones, supernet-
ting was devised to combine several class C blocks into a larger block to be attractive to
532 PART IV NETWORK LAYER
organizations that need more than the 256 addresses available in a class C block. This
idea did not work either because it makes the routing of packets more difficult.
Advantage of Classful Addressing
Although classful addressing had several problems and became obsolete, it had one
advantage: Given an address, we can easily find the class of the address and, since the
prefix length for each class is fixed, we can find the prefix length immediately. In other
words, the prefix length in classful addressing is inherent in the address; no extra infor-
mation is needed to extract the prefix and the suffix.
18.4.3 Classless Addressing
Subnetting and supernetting in classful addressing did not really solve the address
depletion problem. With the growth of the Internet, it was clear that a larger address
space was needed as a long-term solution. The larger address space, however, requires
that the length of IP addresses also be increased, which means the format of the IP
packets needs to be changed. Although the long-range solution has already been
devised and is called IPv6 (discussed later), a short-term solution was also devised to
use the same address space but to change the distribution of addresses to provide a fair
share to each organization. The short-term solution still uses IPv4 addresses, but it is
called classless addressing. In other words, the class privilege was removed from the
distribution to compensate for the address depletion.
There was another motivation for classless addressing. During the 1990s, Internet
Service Providers (ISPs) came into prominence. An ISP is an organization that pro-
vides Internet access for individuals, small businesses, and midsize organizations that
do not want to create an Internet site and become involved in providing Internet ser-
vices (such as electronic mail) for their employees. An ISP can provide these services.
An ISP is granted a large range of addresses and then subdivides the addresses (in
groups of 1, 2, 4, 8, 16, and so on), giving a range of addresses to a household or a
small business. The customers are connected via a dial-up modem, DSL, or cable
modem to the ISP. However, each customer needs some IPv4 addresses.
In 1996, the Internet authorities announced a new architecture called classless
addressing. In classless addressing, variable-length blocks are used that belong to no
classes. We can have a block of 1 address, 2 addresses, 4 addresses, 128 addresses, and so on.
In classless addressing, the whole address space is divided into variable length
blocks. The prefix in an address defines the block (network); the suffix defines the node
(device). Theoretically, we can have a block of 20, 21, 22, . . . , 232 addresses. One of the
restrictions, as we discuss later, is that the number of addresses in a block needs to be a
power of 2. An organization can be granted one block of addresses. Figure 18.19 shows
the division of the whole address space into nonoverlapping blocks.
Figure 18.19 Variable-length blocks in classless addressing
Block 1 Block 2 Block i Block (m – 1) Block m
Address space
CHAPTER 18 INTRODUCTION TO NETWORK LAYER 533
Unlike classful addressing, the prefix length in classless addressing is variable. We
can have a prefix length that ranges from 0 to 32. The size of the network is inversely
proportional to the length of the prefix. A small prefix means a larger network; a large
prefix means a smaller network.
We need to emphasize that the idea of classless addressing can be easily applied to
classful addressing. An address in class A can be thought of as a classless address in
which the prefix length is 8. An address in class B can be thought of as a classless
address in which the prefix is 16, and so on. In other words, classful addressing is a spe-
cial case of classless addressing.
Prefix Length: Slash Notation
The first question that we need to answer in classless addressing is how to find the pre-
fix length if an address is given. Since the prefix length is not inherent in the address,
we need to separately give the length of the prefix. In this case, the prefix length, n, is
added to the address, separated by a slash. The notation is informally referred to as
slash notation and formally as classless interdomain routing or CIDR (pronounced
cider) strategy. An address in classless addressing can then be represented as shown in
Figure 18.20.
Figure 18.20 Slash notation (CIDR)
Examples:
byte byte byte byte n [Link]/8
/
[Link]/12
Prefix [Link]/25
length
In other words, an address in classless addressing does not, per se, define the block
or network to which the address belongs; we need to give the prefix length also.
Extracting Information from an Address
Given any address in the block, we normally like to know three pieces of information
about the block to which the address belongs: the number of addresses, the first address
in the block, and the last address. Since the value of prefix length, n, is given, we can
easily find these three pieces of information, as shown in Figure 18.21.
1. The number of addresses in the block is found as N = 232 − n.
2. To find the first address, we keep the n leftmost bits and set the (32 − n) rightmost
bits all to 0s.
3. To find the last address, we keep the n leftmost bits and set the (32 − n) rightmost
bits all to 1s.
Example 18.1
A classless address is given as [Link]/27. We can find the above three pieces of infor-
mation as follows. The number of addresses in the network is 232 − n = 25 = 32 addresses.
534 PART IV NETWORK LAYER
Figure 18.21 Information extraction in classless addressing
n bits (32 – n) bits
Any address Prefix Suffix
Prefix 000 ... 0 Prefix 111 ... 1
First address Last address
Number of addresses: N = 232 – n
The first address can be found by keeping the first 27 bits and changing the rest of the bits to 0s.
Address: [Link]/27 10100111 11000111 10101010 01010010
First address: [Link]/27 10100111 11000111 10101010 01000000
The last address can be found by keeping the first 27 bits and changing the rest of the bits
to 1s.
Address: [Link]/27 10100111 11000111 10101010 01011111
Last address: [Link]/27 10100111 11000111 10101010 01011111
Address Mask
Another way to find the first and last addresses in the block is to use the address mask.
The address mask is a 32-bit number in which the n leftmost bits are set to 1s and the
rest of the bits (32 − n) are set to 0s. A computer can easily find the address mask
because it is the complement of (232 − n − 1). The reason for defining a mask in this way
is that it can be used by a computer program to extract the information in a block, using
the three bit-wise operations NOT, AND, and OR.
1. The number of addresses in the block N = NOT (mask) + 1.
2. The first address in the block = (Any address in the block) AND (mask).
3. The last address in the block = (Any address in the block) OR [(NOT (mask)].
Example 18.2
We repeat Example 18.1 using the mask. The mask in dotted-decimal notation is
[Link]. The AND, OR, and NOT operations can be applied to individual bytes using
calculators and applets at the book website.
Number of addresses in the block: N = NOT (mask) + 1= [Link] + 1 = 32 addresses
First address: First = (address) AND (mask) = [Link]
Last address: Last = (address) OR (NOT mask) = [Link]
CHAPTER 18 INTRODUCTION TO NETWORK LAYER 535
Example 18.3
In classless addressing, an address cannot per se define the block the address belongs to. For
example, the address [Link] can belong to many blocks. Some of them are shown below
with the value of the prefix associated with that block.
Prefix length:16 → Block: [Link] to [Link]
Prefix length:20 → Block: [Link] to [Link]
Prefix length:26 → Block: [Link] to [Link]
Prefix length:27 → Block: [Link] to [Link]
Prefix length:29 → Block: [Link] to [Link]
Prefix length:31 → Block: [Link] to [Link]
Network Address
The above examples show that, given any address, we can find all information about
the block. The first address, the network address, is particularly important because it
is used in routing a packet to its destination network. For the moment, let us assume
that an internet is made of m networks and a router with m interfaces. When a packet
arrives at the router from any source host, the router needs to know to which network
the packet should be sent: from which interface the packet should be sent out. When the
packet arrives at the network, it reaches its destination host using another strategy that
we discuss later. Figure 18.22 shows the idea. After the network address has been
Figure 18.22 Network address
Network 1 Network 2 Network m
2
1 m
Router
Routing Process Forwarding table
Network address Interface
b1 c1 d1 e1 1
Destination Find b2 c2 d2 e2 Interface
address network address 2 number
bm c m d m e m m
found, the router consults its forwarding table to find the corresponding interface from
which the packet should be sent out. The network address is actually the identifier of
the network; each network is identified by its network address.
536 PART IV NETWORK LAYER
Block Allocation
The next issue in classless addressing is block allocation. How are the blocks allocated?
The ultimate responsibility of block allocation is given to a global authority called the
Internet Corporation for Assigned Names and Numbers (ICANN). However, ICANN
does not normally allocate addresses to individual Internet users. It assigns a large
block of addresses to an ISP (or a larger organization that is considered an ISP in this
case). For the proper operation of the CIDR, two restrictions need to be applied to the
allocated block.
1. The number of requested addresses, N, needs to be a power of 2. The reason is that
N = 232 − n or n = 32 − log2N. If N is not a power of 2, we cannot have an integer
value for n.
2. The requested block needs to be allocated where there is an adequate number of
contiguous addresses available in the address space. However, there is a restric-
tion on choosing the first address in the block. The first address needs to be
divisible by the number of addresses in the block. The reason is that the first
address needs to be the prefix followed by (32 − n) number of 0s. The decimal
value of the first address is then
first address = (prefix in decimal) × 232 − n = (prefix in decimal) × N.
Example 18.4
An ISP has requested a block of 1000 addresses. Since 1000 is not a power of 2, 1024 addresses
are granted. The prefix length is calculated as n = 32 − log21024 = 22. An available block,
[Link]/ 22 , is granted to the ISP. It can be seen that the first address in decimal is
302,910,464, which is divisible by 1024.
Subnetting
More levels of hierarchy can be created using subnetting. An organization (or an ISP)
that is granted a range of addresses may divide the range into several subranges and
assign each subrange to a subnetwork (or subnet). Note that nothing stops the organization
from creating more levels. A subnetwork can be divided into several sub-subnetworks.
A sub-subnetwork can be divided into several sub-sub-subnetworks, and so on.
Designing Subnets
The subnetworks in a network should be carefully designed to enable the routing of pack-
ets. We assume the total number of addresses granted to the organization is N, the prefix
length is n, the assigned number of addresses to each subnetwork is Nsub, and the prefix
length for each subnetwork is nsub. Then the following steps need to be carefully followed
to guarantee the proper operation of the subnetworks.
❑ The number of addresses in each subnetwork should be a power of 2.
❑ The prefix length for each subnetwork should be found using the following formula:
nsub = 32 − log2Nsub
CHAPTER 18 INTRODUCTION TO NETWORK LAYER 537
❑ The starting address in each subnetwork should be divisible by the number of
addresses in that subnetwork. This can be achieved if we first assign addresses to
larger subnetworks.
Finding Information about Each Subnetwork
After designing the subnetworks, the information about each subnetwork, such as first
and last address, can be found using the process we described to find the information
about each network in the Internet.
Example 18.5
An organization is granted a block of addresses with the beginning address [Link]/24. The
organization needs to have 3 subblocks of addresses to use in its three subnets: one subblock of 10
addresses, one subblock of 60 addresses, and one subblock of 120 addresses. Design the subblocks.
Solution
There are 232 – 24 = 256 addresses in this block. The first address is [Link]/24; the last address
is [Link]/24. To satisfy the third requirement, we assign addresses to subblocks, starting
with the largest and ending with the smallest one.
a. The number of addresses in the largest subblock, which requires 120 addresses, is not a
power of 2. We allocate 128 addresses. The subnet mask for this subnet can be found as
n1 = 32 − log2128 = 25. The first address in this block is [Link]/25; the last address is
[Link]/25.
b. The number of addresses in the second largest subblock, which requires 60 addresses, is not
a power of 2 either. We allocate 64 addresses. The subnet mask for this subnet can be found
as n2 = 32 − log264 = 26. The first address in this block is [Link]/26; the last address
is [Link]/26.
c. The number of addresses in the smallest subblock, which requires 10 addresses, is not a
power of 2 either. We allocate 16 addresses. The subnet mask for this subnet can be found as
n3 = 32 − log216 = 28. The first address in this block is [Link]/28; the last address is
[Link]/28.
If we add all addresses in the previous subblocks, the result is 208 addresses, which
means 48 addresses are left in reserve. The first address in this range is [Link]. The
last address is [Link]. We don’t know about the prefix length yet. Figure 18.23
shows the configuration of blocks. We have shown the first address in each block.
Address Aggregation
One of the advantages of the CIDR strategy is address aggregation (sometimes called
address summarization or route summarization). When blocks of addresses are com-
bined to create a larger block, routing can be done based on the prefix of the larger
block. ICANN assigns a large block of addresses to an ISP. Each ISP in turn divides its
assigned block into smaller subblocks and grants the subblocks to its customers.
Example 18.6
Figure 18.24 shows how four small blocks of addresses are assigned to four organizations by an
ISP. The ISP combines these four blocks into one single block and advertises the larger block to
the rest of the world. Any packet destined for this larger block should be sent to this ISP. It is the
responsibility of the ISP to forward the packet to the appropriate organization. This is similar to
538 PART IV NETWORK LAYER
Figure 18.23 Solution to Example 18.5
N = 256 addresses
n = 24
[Link]/24 [Link]/24
First address Last address
a. Original block
N = 128 64 16 48
n = 25 n = 26 28 Unused
[Link]/25 [Link]/26 [Link]/28
b. Subblocks
Figure 18.24 Example of address aggregation
[Link]/26
Block 1 to
[Link]/26 All packets with
destination addresses
[Link]/24
[Link]/26
ISP to
Block 2 to
[Link]/24
[Link]/26
are sent to ISP.
Internet
[Link]/26
Block 3 to Larger
[Link]/26 block
[Link]/26
Block 4 to
[Link]/26
routing we can find in a postal network. All packages coming from outside a country are sent first
to the capital and then distributed to the corresponding destination.
Special Addresses
Before finishing the topic of addresses in IPv4, we need to mention five special
addresses that are used for special purposes: this-host address, limited-broadcast
address, loopback address, private addresses, and multicast addresses.
This-host Address
The only address in the block [Link]/32 is called the this-host address. It is used when-
ever a host needs to send an IP datagram but it does not know its own address to use as
the source address. We will see an example of this case in the next section.
CHAPTER 18 INTRODUCTION TO NETWORK LAYER 539
Limited-broadcast Address
The only address in the block [Link]/32 is called the limited-broadcast address.
It is used whenever a router or a host needs to send a datagram to all devices in a network.
The routers in the network, however, block the packet having this address as the destina-
tion; the packet cannot travel outside the network.
Loopback Address
The block [Link]/8 is called the loopback address. A packet with one of the
addresses in this block as the destination address never leaves the host; it will remain in
the host. Any address in the block is used to test a piece of software in the machine. For
example, we can write a client and a server program in which one of the addresses in the
block is used as the server address. We can test the programs using the same host to see
if they work before running them on different computers.
Private Addresses
Four blocks are assigned as private addresses: [Link]/8, [Link]/12, [Link]/16,
and [Link]/16. We will see the applications of these addresses when we discuss
NAT later in the chapter.
Multicast Addresses
The block [Link]/4 is reserved for multicast addresses. We discuss these addresses
later in the chapter.
18.4.4 Dynamic Host Configuration Protocol (DHCP)
We have seen that a large organization or an ISP can receive a block of addresses
directly from ICANN and a small organization can receive a block of addresses from an
ISP. After a block of addresses are assigned to an organization, the network administra-
tion can manually assign addresses to the individual hosts or routers. However, address
assignment in an organization can be done automatically using the Dynamic Host
Configuration Protocol (DHCP). DHCP is an application-layer program, using the
client-server paradigm, that actually helps TCP/IP at the network layer.
DHCP has found such widespread use in the Internet that it is often called a plug-
and-play protocol. In can be used in many situations. A network manager can configure
DHCP to assign permanent IP addresses to the host and routers. DHCP can also be con-
figured to provide temporary, on demand, IP addresses to hosts. The second capability
can provide a temporary IP address to a traveller to connect her laptop to the Internet
while she is staying in the hotel. It also allows an ISP with 1000 granted addresses to
provide services to 4000 households, assuming not more than one-forth of customers
use the Internet at the same time.
In addition to its IP address, a computer also needs to know the network prefix (or
address mask). Most computers also need two other pieces of information, such as the
address of a default router to be able to communicate with other networks and the address
of a name server to be able to use names instead of addresses, as we will see in Chapter 26.
In other words, four pieces of information are normally needed: the computer address, the
prefix, the address of a router, and the IP address of a name server. DHCP can be used to
provide these pieces of information to the host.