This chapter is from the book
This chapter is from the book
This chapter is from the book
3.9 Classless Routing Operations
Let's try to understand what enhancements should be made to the routing process and routing protocols to guarantee normal routing of classless addressing schemes. Because classless routing assumes use of VLSMs, routes in the routing updates should be augmented with route masks. Once this condition has been met, the problem with mandatory summarization is automatically canceled; even if information about subnets is sent into another major network, the routers have explicit information about the corresponding route mask in the update. This is not enough, however.
Even though automatic route summarization can cause problems, the technique in general is necessary to scale the networks. Without route summarization, every router would have to know about every prefix in the network. One of the problems that stimulated deployment of CIDR in the Internet was the growing size of the routing tables in the backbone routers. At that time, every backbone router had to know every major network in the Internet, and because the number of networks connected to the Internet grew at an exponential rate, the growth of the routing table size followed the same trend. There had to be a method that would stop this. Route aggregation, a part of CIDR, is a technique similar to classful summarization and allows routes to be aggregated at an arbitrary boundary and hence permits aggregation of major networks. Arbitrary aggregation also helps reduce the size of routing tables within major networks.
The principle of route aggregation states that routes to specific subnets or networks can be represented by a smaller number of aggregate routes. The route masks of the aggregate routes do not need to equal the default classful mask or the subnet mask used in the major network. To illustrate this, consider an example in which a network is geographically split in three parts (Figure 3-13).
){kind=link}
Figure 3-13. Classless routing—a sample network
The first remote site is assigned subnets 10.1.1.0–10.1.14.0; the second one uses subnets 10.1.17.0–10.1.30.0. All other subnets are located in the central site. The classful routing approach requires either a full routing table or network default routes on each router in this network. With classless routing, another method can be used.
Look at the first three address bytes of the subnets in remote site 1; the third byte is represented in binary notation in Table 3-1. Only the four lowest-order bits change in the third byte; the highest-order four bits do not. This means that all subnets in the site do not have to be announced, provided that all outside routers know that subnets with the four highest-order bits in the third byte, set to 0, and the first two bytes, set to 10 and 1, can be reached via router R1. This can be achieved by propagating only an aggregate route, 10.1.0.0/20, to R2 and R3. In this case, the route represents not a real subnet but a group of subnets. The routing tables in the routers could be as shown in Figure 3-14.
){kind=link}
Table 3-1. Aggregation of Subnet Routes
|
Subnet |
First Byte |
Second Byte |
Third Byte |
Fourth Byte |
|
10.1.1.0 |
10 |
1 |
0000 0001 |
0 |
|
10.1.2.0 |
10 |
1 |
0000 0010 |
0 |
|
10.1.3.0 |
10 |
1 |
0000 0011 |
0 |
|
10.1.4.0 |
10 |
1 |
0000 0100 |
0 |
|
.... |
|
|
|
|
|
10.1.14.0 |
10 |
1 |
0000 1110 |
0 |
Figure 3-14. Classless routing—route aggregation
Note that networks in remote site 2 are also represented by an aggregate route: 10.1.16.0/20. Another interesting detail is that all subnets in the central site are described in R1 and R3 via a network summary route. Also, pay attention to the fact that router R3 has two routes with the same address parts but different route masks. Because the routing table lookup algorithm selects the most specific—the longest matching—route for the destination address, routing is unambiguous. This rule can be demonstrated by the forwarding decision that router R3 makes.
Suppose that R3 receives a packet destined for address 10.1.2.10. The router starts looking through the routing table. In its first iteration, the best route it finds is 10.1.0.0/16, but when R3 looks at the second one—10.1.0.0/20—it finds that this route also matches and has a longer route mask. So, route 10.1.0.0/20 is selected as the best and the packet is forwarded to R1. If it had to route a packet destined for one of the subnets within the central site, R3 would see that the second route doesn't match, and the first one would remain the best.
The same principle works in aggregating routes describing classful networks. Consider an example of a small Internet provider that is given eight class C networks, 190.150.16.0–190.150.23.0. The method used to aggregate subnet routes is used to aggregate class C networks to a supernet (Table 3-2).
Table 3-2. Building a Supernet Route
|
Network |
First Byte |
Second Byte |
Third Byte |
Fourth Byte |
|
190.150.16.0 |
190 |
150 |
00010 000 |
0 |
|
190.150.17.0 |
190 |
150 |
00010 001 |
0 |
|
190.150.18.0 |
190 |
150 |
00010 010 |
0 |
|
190.150.19.0 |
190 |
150 |
00010 011 |
0 |
|
.... |
|
|
|
|
|
190.150.23.0 |
190 |
150 |
00010 111 |
0 |
Note that only the three rightmost bits change. This means that all these networks can be announced with one aggregate route, 190.150.16.0/21, so we have only one route instead of eight. Note that this aggregate route uses an arbitrary address mask, which is shorter than the default classful mask. This makes it a supernet route in contrast to a subnet route having the mask longer than the default. Note that supernet routes could not be used with classful routing protocols, because routes in the updates are not accompanied by the route masks. It is the route mask announced in the updates that allows classless routing protocols to announce supernet routes or arbitrary aggregate routes in general.
In classful routing, default routes are used very carefully. Classless routing principles state that default routes must be taken every time a router doesn't know where to route the packet. This is easily understood because in classless routing, there are no classes and therefore no major networks. In classless routing, the whole network address is not divided into network, subnet, and host portions but rather is considered as a combination of a network prefix and a host part, where the network prefix is derived by using the mask of a given route. A router looks through the routing table for a route whose network prefix matches the destination address best, that is, the longest matching route. If no matching route is available, the default route is used.
This treatment of the default route seems to be acceptable, unless we recall why classful routing restricted use of the default route. This restriction prevents routing loops caused by sending packets out of the local major network if they are destined for one of its unknown subnets. Consider the same network similar to the one in the previous example, but assume that it uses default routes instead of network summary routes (see Figure 3-15).
){kind=link}
Figure 3-15. Use of default route in classless routing
Suppose that router R2 receives a packet with destination address 10.1.2.15 and that subnet 10.1.2.0 is down. Router R2 follows the aggregate route 10.1.0.0/20 and forwards the packet to R1. R1 does not have information about subnet 10.1.2.0 (because it is down), takes the least specific route in the routing table—the default route (0.0.0.0/0)—and sends the packet back to R2. The routers keep ping-ponging until the packet's TTL field is decreased to zero, when the packet is dropped. This situation represents the simplest two-hop routing loop.
To remedy this problem, classless routing requires that every router that announces an aggregate route drops a received packet if it's destined for one of the aggregated networks and the router has no information about the destination. In our example, when router R1 receives the packet from R2 and sees that it has no information about the destination subnet in the routing table, it must drop it. Analyzing which routes have been announced could be time consuming, and in any case, the aggregate route in R2 could be configured statically, so R1 would never know about it. This is why so-called discard routes are installed in the routers, announcing aggregates (R2 in the example). While looking for a route in the table, routers should consider the discard route as a normal one, but packet delivery along such a route must result in a packet drop. It may seem that having a route like 10.1.0.0/20–>Discard on R1 would cause the router to drop every packet that matches this route, but this is not what happens. Remember that the best-matching route is always picked up. So if the router has a more specific route to the destination, it will route the packet properly; only if the destination is not explicitly listed in the routing table will the router take the discard route and drop the packet.
The algorithm of the classless routing table lookup operation is really simple—look up the longest matching route in the routing table; if no matching route is available, use the default route. (If the default route is announced as 0.0.0.0/0, the last step is not needed, as this route matches all addresses.) As we will see in the following chapters, the exact details of the router operation are slightly different, but the behavior follows the principles described here.