Understanding Linux Network Internals

Lookups

As mentioned in the section "Routing Cache," Linux uses both a routing cache and a routing table. Figure 30-8 summarizes the steps in a routing table lookup. To keep the "Route/deliver packet" simple, it does not reflect the variety of routes described earlier in the section "Special Routes."

Lookups in the routing cache are based on an exact match in a simple hash table. Lookups in the potentially much bigger and more complex routing table are based on a Longest Prefix Match (LPM) algorithm , described in the following section. As we will see in Chapter 34, a routing table is organized as a complex mesh of data structures. This makes LPM faster and easier to implement, scales well with a large number of routes, and reduces the duplication of instances of data structures that can be shared.

Longest Prefix Match

If there were only one route toward each destination, routing lookups would be trivial. As soon as you found a route whose destination subnet included your destination address—the key of the lookup—you would be done. However, routing is a complex topic. Without going into detail on the network topologies or specific cases where this complexity occurs, suffice it to say that it is not uncommon to have multiple routes to the same destinations. The overlapping between the routes can be anywhere from one address to an entire subnet.

Figure 30-8. Routing lookup

In case of multiple ...