Routing and IPSEC Lookup Scaling in the Linux Kernel

A Presentation by David S. Miller

Finding the appropriate path for a packet is the single most important task the
kernel networking stack partakes in for every frame sent. For sockets, we can
be smart and only do a lookup once for that socket when a new connection is
created. But for general routing and IPSEC traffic we must incur a lookup for
every packet.

Therefore it is crucial that the lookup of this path be as efficient as possible.
The goal is to incur the minimum possible number of cpu memory references
during this lookup operation.

On the other hand, it is also important to make sure that route and IPSEC rule
changes are efficient as well, and that such changes do not have adverse
effects upon the lookup engine under normal circumstances.

The author will discuss his work on the scaling of the IPSEC subsystem data
structures. Interesting work on "active garbage collection" in the IPv4 routing
cache by Robert Olsson will be presented as well. Finally, the ongoing work
investigating a move to a "grand unified flow cache" for all packet path lookups
will also be presented. In fact, the lessons learned from the IPSEC scaling
and active garbage collection work provide important theoretical groundwork
for any unified flow cache scheme.

The ancilliary topic of the impliciation that highly multithreaded cores, such as
Sun's Niagara, have upon routing lookup performance will be touched upon as well.

Direct link to video