Understanding Linux Network Internals

Routing Table

The routing table is the core of the routing sysbsystem. In its simplest definition, it consists of a database of routes that is available to other subsystems—IPv4, for example—through various functions, the most important being the one used to do lookups.

As you may already imagine, routes do not consist only of the basic information shown in the section "Routers, Routes, and Routing Tables." Over time, due both to code optimizations and to the introduction of new features, the amount of information that makes up an entry in the routing table has grown quite a bit. We will look at those details in Chapter 34.

In the following subsections, we will briefly see:

• How Linux routes packets addressed to local addresses

• What algorithm is used to look up addresses in the routing table

• What administrative actions can be applied to traffic matching a route besides the default forwarding action

• What extra information is stored in a route by upper protocols for their convenience

Special Routes

When a packet is received, a router needs to determine whether to deliver it locally to the next-higher layer (because the local host is the final destination) or to forward it. A simple way to accomplish this is to store all the local addresses in a list and scan the list for each packet as part of the routing lookup. Of course, a list would not be the best choice; there are better data structures that can provide faster lookup time. Linux uses a separate hash-based routing table where it stores ...