Performance progression of IPv6 route lookup on Linux

Vincent Bernat

In a previous article, I explained how Linux implements an IPv6 routing table. The following graph shows the performance progression of route lookups through Linux history:

IPv6 route lookup performance progression
IPv6 route lookup times for various Linux kernel versions. Lookup is done on a table with 40,000 routes. Notable performance changes are highlighted. The shaded surfaces represent the median absolute deviation.

All kernels are compiled with GCC 4.9 (from Debian Jessie). This version is able to compile older kernels as well as current ones. The kernel configuration is the default one with CONFIG_SMP, CONFIG_IPV6, CONFIG_IPV6_MULTIPLE_TABLES and CONFIG_IPV6_SUBTREES options enabled. Some other unrelated options are enabled to be able to boot them in a virtual machine and run the benchmark.

There are three notable performance changes:

  • In Linux 3.1, Eric Dumazet delays a bit the copy of route metrics to fix the undesirable sharing of route-specific metrics by all cache entries (commit 21efcfa0ff27). Each cache entry now gets its own metrics, which explains the performance hit for the non-/128 scenarios.
  • In Linux 3.9, Yoshifuji Hideaki removes the reference to the neighbor entry in struct rt6_info (commit 887c95cc1da5). This should have lead to a performance increase. The small regression may be due to cache-related issues.
  • In Linux 4.2, Martin KaFai Lau prevents the creation of cache entries for most route lookups. The most sensible performance improvement comes with commit 4b32b5ad31a6. The second one is from commit 45e4fd26683c, which effectively removes creation of cache entries, except for PMTU exceptions.

Mid-2018 update#

Here is a graph for more recent kernels. Measures were performed on an Intel Xeon Gold 61481 running at 2.4 GHz, with GCC 6.3 from Debian Stretch:

IPv6 route lookup performance with recent kernels
IPv6 route lookup times for various Linux kernel versions. Lookup is done on a table with 40,000 routes. The shaded surfaces represent the median absolute deviation.

Performance regressions in 4.4.147 and 4.9.119 are solely due to the Spectre mitigations.2 The small performance increase in Linux 4.14 is from my own commit feca7d8c135b which optimizes the case without custom routing rules. In Linux 4.15, the most notable improvement can be traced to commit 66f5d6ce53e6: Wei Wang replaces the read-write lock by an RCU and a spinlock. In Linux 4.18, David Ahern improved the data structures used by route lookup. While the gain is meager, this should bring more performance improvements in the future. This also allows a fairer comparison between IPv4 and IPv6.

  1. That’s the hardware we use to run hypervisors at Exoscale↩︎

  2. These LTS kernels received a backport of the mitigations found in more recent kernels. For IPv4, the impact was non-existent↩︎