Understanding Linux Network Internals

Chapter 35. Routing: Lookups

In Chapter 33, we saw how lookups are triggered by both ingress and egress traffic. The cache is always searched first, and when there is a miss, the routing tables are consulted through the ip_route_input_slow and ip_route_output_slow functions. In this chapter, we will analyze these functions; in particular, we will cover:

• How ingress and egress routing differ

• How a routing table is searched with fib_lookup

• How policy routing lookups differ from normal lookups

• When and how multipath routing is handled

• How the selection of a default gateway works

High-Level View of Lookup Functions

Regardless of the direction of the traffic, a routing table lookup is made with fib_lookup. However, as mentioned in the section "Double Definitions for Functions" in Chapter 34, there are two versions of fib_lookup, one used when the kernel has support for Policy Routing (net/ipv4/fib_rules.c) and one when that support is not included (include/net/ip_fib.h). The selection of the right routine is made at compile time, so when ip_route_input_slow and ip_route_output_slow call fib_lookup, they transparently invoke the right one.

Let’s briefly see the key functions used to make a route lookup. You will find it helpful to refer to Figure 34-1 in Chapter 34 during this discussion.

The fib_lookup routine is a wrapper around the lookup function provided by each routing table. The version provided when there is no policy routing simply runs the lookup function for the local and main tables, ...