Summarizable Address Blocks
Last month's article discussed basic OSPF. I want to say that with OSPF you should "summarize, summarize, summarize", so we need to discuss what that might mean. And it gives me the chance to sound off about addressing while we're at it. We'll start by reviewing subnetting, since I have a somewhat different perspective on it.
Let's start with a very basic point of view. Routing tells a router how to deliver a packet. The packet being routed has a specific IP address in it. Usually routers don't track every address (host routing), because it isn't necessary or appropriate. Instead, routers (and routing protocols) track subnets, which I like to think of as the names of the "wires" in a network. Of course, what we mean by "wires" is getting more abstract all the time. We used to have thick Ethernet (now that's a solid, definite, no-doubt-about-it wire). Now we have hubs (well, some of us do). And we have VLAN's, which are virtual wires. But the routers still track them: the logic is no different than in the days of 10Base5 cabling.
When TCP/IP version 4 was invented, computers (and routers) were scarce (and expensive). The original routing only was able to direct packets based on the Class A, B, C IP addresses everyone knows about. The routers assumed they knew how much of the address was significant for routing, as summarized in the following table.
||Default Subnet Mask
|22.214.171.124 - 126.96.36.199
|188.8.131.52 - 184.108.40.206
|192.0.0.0 - 220.127.116.11
(127 is class A but reserved for loopback). So a class A address by default has 8 bits significant for routing, class B 16, and class C 24. This is indicated with a slant as shown in the right column. The remaining bits are the host part of the address, assigned to various computers by the administrator. The one bits in the mask (255 is 8 one bits in binary) indicate the network portion of the address, used for routing, and the zero bits indicate the host portion of the address. Internally, the router uses the network mask to select out the bits from a packet to look up in its routing table, by doing a LOGICAL AND operation on the packet address and the mask.
As time went on, it became clear that using new network numbers to route to additional Ethernet segments (wires, if you will) was going to use up addresses at a prodigious rate. A network administrator is at liberty to assign host addresses as they wish. So if the administrator assigns addresses so that the first bits in the host part of the address indicate the wire the host is on, and if there is some way to clue the router in on this, more flexible routing is gained. Allowing the administrator to specify the subnet mask was how the router was clued in to this scheme.
The following approach is the official approach you'll find in almost every book on the subject.
Subnets, the Official Way
Let's look at how the router figures out how to route a packet in the presence of subnetting. First we'll do a simple version, then fancier versions.
A packet arrives at the router with destination 18.104.22.168, default subnet mask 255.255.0.0 (since it's Class B). The router does a LOGICAL AND in binary:
(A programmer thinks of LOGICAL AND as keeping the bits above a '1' in the mask, and producing '0' as the result wherever there is '0' in the mask). The result, translated back to decimal, is 22.214.171.124.
All we (or the router) have done is extracted the Class B network part of the address, the 131.108 part, the name of the company or organization that was assigned the address. The LOGICAL AND has extracted the first two octets (bytes) of the address. For simplicity, note that where the mask is 255, we keep the corresponding octet of the address. Where the mask is 0, we have a zero octet in the result.
Suppose the router is using a subnet mask of 255.255.255.0. You can think of the '1' bits in the mask, as measuring how much of the address to use for routing. (The mask is always 1's on the left, 0's on the right: that's a rule, the mask must have contiguous one bits).
The result is then 126.96.36.199. Now let's try it with the same address, but a mask of 255.255.255.224.
The result is 188.8.131.52. So host .67 is in subnet .64. The router looks for a route to subnet 184.108.40.206.
There's another way to reach the same result. We know what happens with mask octets of 255 and 0. If that's all that's in the mask, you've got subnetting on a byte boundary, the whole byte (or multiple bytes) form the subnet, and you can just read the subnet off.
Here's the trick: if there's a byte in the mask like 224, then subtract it from 256: 256 - 224 = 32. It turns out that the subnets will be multiples of the result, 32, in the appropriate octet (the one that the 224 was in). Each subnet starts with the multiple of 32, and ends just before the next subnet (multiple of 32). The figure to the left shows this.
Each subnet is shown in a box. The number at the top is the name of the subnet, the multiple of 32. The last number in each box is the subnet directed broadcast address, one before the next subnet. These two addresses are in red since they are not valid host addresses within that subnet. The remaining addresses are shown in green, as valid host addresses for the subnet.
So to determine the subnet of 220.127.116.11 for mask 255.255.255.224, we need to figure out what is the nearest multiple of 32 that's less than 67, since that's the name of the subnet. This gives us 64 as the subnet.
Did you notice? We just figured out the subnet without having to do binary!
Let's try another. Say a packet is bound for 10.17.35.185 with mask 255.255.240.0. Then we calculate 256-240 = 16, so our subnet is a multiple of 16 in the third octet, or 32. But this is a class A address, so only the 10 is the given network address. That means the 17 is also part of the name of the subnet. In this case, the subnets look like 10.anything.multiple of 16.0: 10.0.0.0, 10.0.16.0, 10.0.32.0, ..., 10.1.0.0, 10.1.32,0, ..., up to 10.255.240.0.
Summarizable Ranges of Addresses
Suppose we look at the addresses 18.104.22.168, 22.214.171.124, 126.96.36.199, up through 188.8.131.52. You can tell at a glance that this block of addresses is suitable for summarization with a routing protocol. That's because if you count the numbers 80, 81, ... 95, there are 16 numbers there, and 16 is a power of two. Furthermore, the first number, 80, is also a multiple of that number 16. Whenever this pattern holds, the addresses are suitable.
So 184.108.40.206, 220.127.116.11, through 18.104.22.168 will summarize, since from 72 through 79 there are 8 numbers starting with a multiple of 8 (and 8 is a power of two). But 22.214.171.124, 126.96.36.199, through 188.8.131.52 will not summarize (at least not as one routing entry), since 119 through 139 amounts to 20 numbers, and 20 is not a power of two. Similarly, 119 through 126 do not summarize, since there are 8 numbers but they don't start with a multiple of 8.
Now comes the tie-in with subnetting as done above. Before, we calculated 256 - mask = multiples of number. We can swap the mask and the "multiples of number". In our first example, we're dealing with 16 numbers and multiples of 16, so we calculate 256 - 16 = 240. The numbers 80 through 95 were in the third octet, so we use mask 255.255.240.0. The claim is then that 184.108.40.206 with mask 255.255.240.0 represents the adresses in the range 220.127.116.11 through the end of 18.104.22.168, namely 22.214.171.124.
The figure shows how this is working. If you look at it in binary, the 240 mask is saying that only the left 4 bits of the third octet are significant for routing purposes. In effect, we've tuned out the right 4 bits. The gray box in the figure shows the bits that are "tuned out". But notice that this range of numbers counts in binary through all the possible combinations in those 4 bits. That's because we started with a multiple of 16 and, in effect, counted from 0 to 15 in binary. As long as our address matches the left bits, the 0101, the routing table entry will apply.
Another way of saying this: suppose a packet arrives with an address drawn from the range 126.96.36.199 through 188.8.131.52. We mask with 255.255.240.0, which tunes out the right four bits of octet three, and all of octet four. We're left with 184.108.40.206.
So 220.127.116.11 with mask 255.255.240.0 indicates how to route for the entire range of addresses 18.104.22.168 through 22.214.171.124! The new way of writing this routing table entry is 126.96.36.199 /20. (Since 20 is 8 + 8 + 4, the number of 1 bits in the mask).
In our second example above, 72 through 79 is 8 numbers starting with a multiple of 8, so we calculate 256 - 8 = 248. All the numbers 72 to 79 are in the third octet again, and hence our summary is 188.8.131.52 with mask 255.255.248.0. Any address in the range 184.108.40.206 through 220.127.116.11, when logically ANDed with mask 255.255.248.0, will match 245.123.72.0. So one routing table entry for the latter, with mask 255.255.248.0, suffices to route to all the addresses in this range. The new notation for this routing entry: 18.104.22.168 / 21. (Since 21 is 8 + 8 + 5, the number of 1 bits in the mask).
Next month we'll look at how to think about the size of a /23, and then we'll see how this applies to OSPF.
Copyright (C) 1998, Peter J. Welcher