Page 413 - Discrete Mathematics and Its Applications

392 6 / Counting

Bit Number 0 1 2 3 4 8 16 24 31
Class A 0 netid hostid
Class B 1 0 netid hostid
Class C 1 1 0 netid hostid
Class D 1 1 1 0 Multicast Address
Class E 1 1 1 1 0 Address

FIGURE 1 Internet Addresses (IPv4).

an address is a string of 32 bits. It begins with a network number (netid ). The netid is followed
by a host number (hostid), which identifies a computer as a member of a particular network.
Three forms of addresses are used, with different numbers of bits used for netids and hostids.
Class A addresses, used for the largest networks, consist of 0, followed by a 7-bit netid and a
24-bit hostid. Class B addresses, used for medium-sized networks, consist of 10, followed by
a 14-bit netid and a 16-bit hostid. Class C addresses, used for the smallest networks, consist
of 110, followed by a 21-bit netid and an 8-bit hostid. There are several restrictions on addresses
because of special uses: 1111111 is not available as the netid of a Class A network, and the
hostids consisting of all 0s and all 1s are not available for use in any network. A computer
on the Internet has either a Class A, a Class B, or a Class C address. (Besides Class A, B,
and C addresses, there are also Class D addresses, reserved for use in multicasting when mul-
tiple computers are addressed at a single time, consisting of 1110 followed by 28 bits, and
Class E addresses, reserved for future use, consisting of 11110 followed by 27 bits. Neither
Class D nor Class E addresses are assigned as the IPv4 address of a computer on the Internet.)
The lack of available
IPv4 address has Figure 1 illustrates IPv4 addressing. (Limitations on the number of Class A and Class B netids
become a crisis! have made IPv4 addressing inadequate; IPv6, a new version of IP, uses 128-bit addresses to
solve this problem.)
How many different IPv4 addresses are available for computers on the Internet?
Solution: Let x be the number of available addresses for computers on the Internet, and let x A ,
x B , and x C denote the number of ClassA, Class B, and Class C addresses available, respectively.
By the sum rule, x = x A + x B + x C .
7
To find x A , note that there are 2 − 1 = 127 Class A netids, recalling that the netid
1111111isunavailable.Foreachnetid,thereare2 24 − 2 = 16,777,214hostids,recallingthatthe
hostids consisting of all 0s and all 1s are unavailable. Consequently, x A = 127 · 16,777,214 =
2,130,706,178.
To find x B and x C , note that there are 2 14 = 16,384 Class B netids and 2 21 = 2,097,152
Class C netids. For each Class B netid, there are 2 16 − 2 = 65,534 hostids, and for each
8
Class C netid, there are 2 − 2 = 254 hostids, recalling that in each network the hostids
consisting of all 0s and all 1s are unavailable. Consequently, x B = 1,073,709,056 and x C =
532,676,608.
We conclude that the total number of IPv4 addresses available is x = x A + x B + x C =
2,130,706,178 + 1,073,709,056 + 532,676,608 = 3,737,091,842. ▲

The Subtraction Rule (Inclusion–Exclusion for Two Sets)

Suppose that a task can be done in one of two ways, but some of the ways to do it are common
to both ways. In this situation, we cannot use the sum rule to count the number of ways to do
the task. If we add the number of ways to do the tasks in these two ways, we get an overcount
Overcounting is perhaps
the most common of the total number of ways to do it, because the ways to do the task that are common to the two
enumeration error. ways are counted twice. To correctly count the number of ways to do the two tasks, we must
subtract the number of ways that are counted twice. This leads us to an important counting rule.