Linux Kernel Architecture

Chapter 12: Networks

Routing

Routing is an important part of any IP implementation and is required not only to forward external

packets, but also to deliver data generated locally in the computer. The problem of finding the correct

path for data ‘‘out‘‘ of the computer is encountered not only with non-local addresses, but also if there are

several network interfaces. This is the case even if there is only one physical network adapter — because

there are also virtual interfaces such as the loopback device.

Each packet received belongs to one of the following three categories:

1. It is intended for the local host.


2. It is intended for a computer connected directly to the current host.


3. It is intended for a remote computer that can only be reached by way of intermediate
   systems.

The previous section discussed packets of the first category; these are passed to the higher protocol layers

for further processing (this type is discussed below because all arriving packets are passed to the routing

subsystem). If the destination system of a packet is connected directly to the local host, routing is usually

restricted to finding the corresponding network card. Otherwise, reference must be made to the routing

information to find a gateway system (and the network card associated with the gateway) via which the

packet can be sent.

The routing implementation has gradually become more and more comprehensive from kernel version

to kernel version and now accounts for a large part of the networking source code. Caches and lengthy

hash tables are used to speed up work because many routing tasks are time-critical. This is reflected in

the profusion of data structures. For reasons of space, we won’t worry what the mechanisms for finding

the correct routes in the kernel data structures look like. We look only at the data structures used by the

kernel to communicate the results.

The starting point of routing is theip_route_inputfunction, which first tries to find the route in the

routing cache (this topic is not discussed here, nor what happens in the case of multicast routing).

ip_route_input_slowis invoked to build a new route from the data structures of the kernel. Basically,

the routine relies onfib_lookup, whose implicit return value (via a pointer used as a function argument)

is an instance of thefib_resultstructure containing the information we want.fibstands forforwarding

information baseand is a table used to manage the routing information held by the kernel.

The routing results are linked with a socket buffer by means of itsdstelement that points to an instance

of thedest_entrystructure that is filled during lookup. The (very simplified) definition of the data

structure is as follows:

include/net/dst.h

struct dst_entry

{

struct net_device *dev;

int (*input)(struct sk_buff*);

int (*output)(struct sk_buff*);

struct neighbour *neighbour;

};