Understanding Linux Network Internals

Main Data Structures

The routing code uses a huge number of different data structures that reference each other. To understand the current routing code and any future improvements, it is important to see the relationships between them clearly.

Any code's performance can be significantly affected by the data structures used and the overall code design. This is especially true for kernel code. A kernel subsystem such as routing, which is the core of the network stack, therefore needs to make sure that it not only provides robust functionality, but also considers performance. We will see in the following chapters how the data structures listed in this section come together to make it easier to implement algorithms that are optimized from the point of view of CPU and RAM consumption, as well as caching.

The following list explains the main data structures defined and used by the routing code. The most important ones have dedicated sections with field-by-field descriptions in Chapter 36. The rt, fib, and fn prefixes in the data structures' names stand for route, Forwarding Information Base, and function, respectively.

struct ip_rt_acct

Used by the routing table based classifier (see the section "Routing Table Based Classifier" in Chapter 31) to keep statistics , expressed in both bytes and number of packets, about the traffic for routes that have been associated with a tag. The structure contains an array of counters, with 256 elements for each processor.^[*] The size is 256 because route ...