3.8 Classful Routing Operations
Before we proceed to the principles of classful IP routing, an important detail about routing table entries needs to be discussed. The routing table structure defined in the previous section specified that each route describes a set of destinations in the form of a network prefix with its value and length. However, all examples given before showed routes in the routing tables just as network addresses (10.0.0.0) instead of as network prefixes (10.0.0.0/8). Indeed, when they install routes in the routing table, Cisco routers provide the corresponding route mask as well. This discussion of the idea behind the route mask was intentionally delayed until the topic of routing table lookup functionality. For better understanding of why routing table entries need masks, let's consider several examples.
Suppose that a summary route to major network 10.0.0.0 with mask 255.0.0.0 and a route to subnet 10.0.0.0 255.255.0.0 (zero subnet) are installed in the routing table as shown in the following example. Note that if routes did not have associated masks, these two routes would be indistinguishable.
10.0.0.0/8 via 10.2.0.1 10.0.0.0/16 via 10.2.0.3
The number after / in the routes represents the number of significant bits in the prefix value; the number is equal to the number of bits in the route mask. So, /8 implies a mask of 255.0.0.0, and /16 means a mask of 255.255.0.0. The route mask specifies the portion of the route's network address that must be compared with the destination address in the packet. A route is declared matching a destination address if the bits in the address corresponding to the bits set to 1 in the route mask are equal to the bits in the same positions in the route's prefix value. In our example, both routes would match address 10.0.0.15 because the 10.0.0.0/8 route matches the first octet of the address, and the 10.0.0.0/16 route matches the first two octets of it. In this situation, 10.0.0.0/8 is said to be a less specific route, and 10.0.0.0/16 is said to be a more specific one. When multiple matching routes are available to the same destination, routers choose the longest matching route to forward the packets. So, for a packet to IP address 10.0.0.15, the 10.0.0.0/16 route would be used. The other route, 10.0.0.0/8, would be used to forward packets to all other, unknown subnets of major network 10.0.0.0. This is an example of a so-called network default route.
Now let's move on to the classful routing topic. The principles of classful addressing discussed in Chapter 2 state that the whole major network must use a single subnet mask. Moreover, the routing protocols designed for classful environments do not send the route masks in their updates. The route mask is determined on the basis of the address masks configured on the interfaces on which the updates are received. Indeed, routers do not have any other source of information about the subnet mask used on remote subnets. Let's see how dynamic routing protocols work in a classful environment.
An update message of a classful protocol can carry routes of the following types.
- Host routes
- Subnet routes
- Network routes
- Default routes
Consider two routers connected to subnets of the same major networkR1 to 10.1.0.0, 10.2.0.0 and 10.3.0.0 and R2 to 10.3.0.0, 10.4.0.0, and 10.5.0.0 (see Figure 3-10). The subnet mask used on the interfaces of the routers is 255.255.0.0. When it receives the update from router R2 about subnets 10.4.0.0 and 10.5.0.0, router R1 installs the routes to these subnets in the routing table with the subnet mask taken from its own interface connected to subnet 10.3.0.0, that is, mask 255.255.0.0. Provided that all hosts and routers in major network 10.0.0.0 use this subnet maska basic rule of classful addressingthis approach works.
Figure 3-10. Example of classful routing
Now imagine that R2 is connected to another major network, say, 22.214.171.124, which uses a different subnet mask255.255.255.0. One of R2's interfaces is attached to subnet 126.96.36.199. If R2 sent information about this subnet to R1, R1 would make a wrong decision about the route mask. It would use its own, 255.255.0.0, and it would see that the network address is 188.8.131.52 and that the host part of the route is 0.0.1.0. If it saw that the host part was not all zeros, R1 would assume that the route was a host route and would insert it with the route mask of 255.255.255.255, which is wrong.
To prevent this misunderstanding, routers connected to multiple major networks do not send subnet information about one major network into another. Instead, they send summary network routes. The receiving routers are supposed to install these routes in the routing tables with the default class address masks. A route from any major network with a nonzero host part of the address is considered a host route. (Some implementations ignore host routes coming from remote major networks.)
The behavior when subnet routing information is not propagated from one major network to another is called automatic route summarization. It has its own pros and cons. On the one hand, autosummarization decreases the size of the routing tables. On the other hand, it can cause routing problems when discontiguous networks are used. For example, consider a situation in which major network 10.0.0.0 is geographically divided by major network 184.108.40.206 (Figure 3-11). The border router R1 sends only a summary route, 10.0.0.0, to routers in major network 220.127.116.11. Border router R2 does the same. So, the router in major network 18.104.22.168 has no information about subnets of network 10.0.0.0 and hence cannot properly route packets going there. In the worst case, routers inside major network 22.214.171.124 choose only the best route to network 10.0.0.0 and install it. This leads to a situation in which a router can see only one partition of the network and cannot send packets to the other. In the best case, when the routers have routes with equal metrics, the routers use both and load-balance the traffic between them. This is still not good, as packets can be sent in a wrong direction. In both cases, the routing is not functional.
Figure 3-11. Classful routing when one major network is split by another
Another interesting subject is how the routing table lookup operation is performed when routers are working in a classful environment. The algorithm follows.
If the routing table contains a route to a destination in the major network that the destination address belongs to, including a route to the major network itself, perform the following steps.
Look up the longest matching route limiting the set of routes to those describing the destinations in that major network.
If no route is found, do not consider the supernet routes or the default route; indicate a route lookup failure, and stop the algorithm.
Otherwise, look up the best matching route among the supernet routes. If a route is found and it is not a route to pseudonetwork 0.0.0.0, use the route for packet forwarding.
Otherwise, if the default route is available, use it to forward the packet.
Otherwise (no matching route and no default route is available), indicate a route lookup failure.
The behavior of the lookup algorithm depends on the result of the first step. If the router has any route for a network in the destination major networkthat is, the router is assumed to have attachments to the major network, the only routes considered are those describing address ranges in the same major network: subnet and network default routes. If no route belongs to the destination major net, a simple best-matching route is chosen. Note that the default route is used only if the router is not attached to the destination major network. (We discuss the reason for this later in this section.)
The following example illustrates how the routing table lookup algorithm works. Suppose that a router needs to forward a packet with the destination address 126.96.36.199. The routing table contains the following routes:
1: Network 10.0.0.0/8 is directly connected to the interface Ethernet 0 2: Network 188.8.131.52/8 is accessible via 10.1.1.1 3: Subnet 184.108.40.206/24 is directly connected to the interface Ethernet 1 4: Subnet 220.127.116.11/24 is accessible via 10.1.1.2
Following is the log of the steps taken by the algorithm.
The destination address is 18.104.22.168, and the destination major network is 22.214.171.124.
The router has routes in the destination major networkroutes 2, 3, and 4so the algorithm branches to step 1.a.
All routes in major network 126.96.36.199 are processed as follows.
Route 188.8.131.52/8. The route's mask is applied to the destination address, which gives 184.108.40.206. This value is the same as the network address part of the route, so the route matches. So far, this route is the best, but the router proceeds to the next route, as there may be better ones.
Route 3220.127.116.11/24. The binary AND between the route mask and the destination address results in 18.104.22.168, which is different from this route's network address (22.214.171.124). This route does not match, so it is skipped.
Route 4126.96.36.199/24. The result of 188.8.131.52 AND 255.255.255.0 is 184.108.40.206, which is equal to the network address portion of the route. The current best route is route 2 (220.127.116.11/8). The route mask of route 4 (255.255.255.0) is longer than that of route 2 (255.0.0.0), so 18.104.22.168/24 is better and is selected as the current best route.
Because no other routes are in the routing table belonging to the destination major network, the algorithm stops, and the 22.214.171.124/24 route is considered the best.
Consider a situation in which a router has somewhat different routing information, the presence of the default route:
1: Network 10.0.0.0/8 is directly connected to the interface Ethernet 0 2: Subnet 126.96.36.199/24 is directly connected to the interface Ethernet 1 3: Subnet 188.8.131.52/24 is accessible via 10.1.1.2 4: Network 0.0.0.0/0 is accessible via 10.1.1.3 (Default route)
The router finds out that the destination (184.108.40.206) belongs to the same major network but cannot find a matching route. Now, because the destination address is in the same major network as the router, the algorithm does not try to find a default route and the route lookup fails, causing the packet to be dropped.
The idea behind treating the default route this way in classful routing is that if a router does not know about some subnet of a "known" major networkthe administrator didn't configure a static route or a routing protocol didn't send any information about itit considers this subnet either nonexistent or down. If the packet were destined for another major network that the router is not connected to, it would take the default route and send the packet to the corresponding router (10.1.1.3).
For better understanding, let's consider another example (Figure 3-12).
Figure 3-12. Use of default in classful routing
Routers R1 and R2 are boundary routers. Router R1 has announced the summary route to its major network (10.0.0.0) to R2, as has R2 (route 220.127.116.11 in R1's routing table). Now assume that the administrator of network 10.0.0.0 configured a default route pointing to R2. Consider a situation in which a station from network 18.104.22.168 sends an IP packet with the destination address 10.4.1.1. R2 routes the packet to R1. Looking through the routing table, R1 does not find a route to the destination subnet. Assume that R1 takes the default route, sending the packet back to R2, which in turn sends it to R1 again. The packet is looped until the TTL field in the header reaches 0 and the packet is dropped by one of the routers.
In other words, because a default route is used to describe destinations in other networks, sending a packet along a default route is equivalent to sending a packet in the direction of the exit from the local major network and, finally, out of it. Because major networks must be contiguous in classful routing, forwarding a packet out of its destination major network doesn't make much sense and leads to routing loops because routers in other major networks believe that a given subnet can be found in the major network the subnet belongs to.
This concept also applies to the supernet routes: routes installed in the routing table with route masks shorter than the default class masks. The only difference is that a supernet route aggregates information about several major networks, whereas the default route aggregates information about the rest of the world.
A router's behavior in a classful environment can be summarized as follows:
Classful routing protocols do not include subnet masks in routing updates.
Classful routing protocols hide subnet information from other major networks by announcing only summary network routes into them.
Classful routing protocols can announce host routes, which are used when hosts do not reside on the same segment as the rest of the subnet.
Each classful router can have the following types of routing information in its table:
Host routesRoutes received with nonzero host address parts and implicitly assigned the network mask of 255.255.255.255 or static routes with explicitly configured masks.
Subnet routesRoutes to subnets within the major network to which a router has an attachment. These routes are inserted into the routing table with subnet masks on the interface the update is received from used as route masks, unless it is a static route and was configured with different subnet mask.
Network summary routesRoutes to other major networks. These routes are inserted into the routing table with the default classful address mask (without subnets) and represent other major networks if they are provided by routing protocols. This type of route can also be used to represent the rest of the local major network (the network default route). Such a route must be statically configured by the administrator.
Default routesEither a 0.0.0.0/0 route, which is marked as default by the router automatically, or other routes to any networks explicitly marked as default by the administrator or a routing protocol (see Chapter 4 for a detailed explanation).
While routing packets, routers pay attention to whether the destination major network is local (some of its subnets are directly connected).
If the destination major network is local, the router needs to have either a host route with a /32 mask or an explicit route to the subnet or a summary network route describing the rest of the local major network. If this condition is not met, the packet is dropped, and the default and supernet routes are not considered.
If the destination major network is not local, the routing table lookup algorithm is changed. The router looks for the best-matching route, paying attention to the length of the route masks; supernet routes may be taken. If no match was found, the router checks the default route. If there's no default route, the packet is dropped.
Following are some problems that can be seen in classful environments.
Variable-length subnet masks cannot be used, as routing updates do not contain route masks.
Automatic summarization to classful networks prevents use of noncontiguous addressing plans, such as private IP addresses for WAN links.
Use of default routes is limited, which can be a problem in very large networks because the only type of summarized route that can be distributed within one major network by routing protocols is the default. This occurs because if the routing protocol sends a network summary route for a local major network, this route is considered an update for zero subnet, not a network summary. So, every router must have either a full routing table or a network summary route representing the rest of the local major network configured manually.
These problems are addressed by the classless routing approach, discussed in the next section.