Understanding Linux Network Internals

Chapter 34. Routing: Routing Tables

Given the central role of routing in the network stack and how big routing tables can be, it is important to have efficiently designed routing tables to speed up operations, particularly lookups. This chapter describes how Linux organizes routing tables, and how the data structures that compose a routing table are accessed with different hash tables, each one specialized for a different kind of lookup.

Organization of Routing Hash Tables

To support the key goal of returning information quickly for a wide variety of operations, Linux defines a number of different hash tables that point to the same data structures describing routes:

• A set of hash tables that access routes based on their netmask length (described in the section "Organization of Per-Netmask Tables“)

• A set of hash tables that search fib_info structures directly (described in the section "Organization of fib_info Structures“)

• One hash table, indexed on the network device, used to quickly search the next hops of the configured routes (described in the section "Organization of Next-Hop Router Structures“).

• One hash table that, indegiven a route and a device, quickly identifies the gateway used by the route’s next hop

Organization of Per-Netmask Tables

At the highest level, routes are organized into different hash tables based on the lengths of their netmasks. Because IPv4 uses 32-bit addresses, 33 different netmask lengths (ranging from /0 to /32, where /0 represents default routes) can be associated ...