The route cache is a Linux ker­nel com­po­nent en­abling route lookups to be faster by caching the re­sults in some ta­ble and check­ing it be­fore is­su­ing a reg­u­lar lookup in the route ta­bles. When us­ing Linux as a router, the in­ef­fi­ciency of the route cache can hin­der the per­for­mance of your box.

The doc­u­men­ta­tion on this com­po­nent is scarce and it is dif­fi­cult to find up-to-date bits on how the route cache works and how to tune it. The book Un­der­stand­ing Linux Net­work In­ter­nals from O’Reilly is an ex­cep­tion and con­tains valu­able in­for­ma­tion on how the route cache works. Even if the book is tar­geted at 2.6.12, the part on the route cache is still quite ac­cu­rate. Un­for­tu­nately, it fails to pro­vide ap­pro­pri­ate tips on how to mon­i­tor and tune the route cache.

I hope to pro­vide here a con­cise view of the route cache, as it is im­ple­mented in Linux 3.1.¹ It is pro­to­col-de­pen­dent² and I will cover only the IPv4 ver­sion here.

Overview of the route cache subsystem#

To han­dle an in­com­ing or out­go­ing IP data­gram, the ker­nel needs to is­sue a lookup in the route ta­bles. While it seems to be quite triv­ial, sev­eral ques­tions need to be answered:

• Do the source ad­dress and the des­ti­na­tion ad­dress ap­pear to be valid?
• Is the source ad­dress a mar­tian address?³
• Is the des­ti­na­tion ad­dress mine or should I for­ward the packet?
• Which route ta­ble should I use?
• Does the des­ti­na­tion ad­dress match this route? And this one?
• Can I cur­rently con­tact the gate­way that I should use?

These checks can be a bit time con­sum­ing, even for small route ta­bles. To avoid them for each packet, Linux main­tains a route cache which is queried be­fore do­ing a reg­u­lar lookup and up­dated af­ter each one. You can dump it with ip -s route show cache:

$ ip -s route show cache
198.51.100.7 from 203.0.113.2 via 192.0.2.1 dev eth1
  cache used 7 age 2sec ipid 0x1fce rtt 131ms rttvar 45ms cwnd 10
198.51.100.17 from 203.0.113.15 via 192.0.2.1 dev eth1
  cache used 3 age 0sec ipid 0xc3bd
local 192.0.2.18 from 203.0.113.15 dev lo src 192.0.2.18
  cache <local> used 154 age 1sec iif eth0

Here are two examples:

• If Linux re­ceives a packet from 203.0.113.15 to 198.51.100.17, it will find this flow in the route cache. There­fore, it al­ready knows that it should for­ward the packet to 192.0.2.1. No checks needed.
• If it re­ceives a packet from 203.0.113.16 to 198.51.100.17, there is no ap­pro­pri­ate en­try in the route cache and there­fore, the sys­tem will have to look at the route ta­bles. It is likely to use the ex­act same en­try as if the source was 203.0.113.15 but maybe there is some pol­icy rout­ing re­quest­ing the use of a spe­cial route ta­ble or 203.0.113.16 is a lo­cal ad­dress and the packet will there­fore be clas­si­fied as martian.

The schema be­low shows how this cache is im­ple­mented.⁴ It uses a sep­a­rate hash ta­ble (BSD sys­tems keep the cache in the rout­ing ta­ble). Each bucket is a chained list of route cache entries.

Once an en­try has been added to the route cache, there are sev­eral ways to re­move it. Most en­tries are re­moved by the garbage col­lec­tor which will scan the route cache and re­move in­valid and older en­tries. It will be trig­gered when the route cache is full or at reg­u­lar in­ter­val, once a cer­tain thresh­old has been met.

Available knobs#

There are sev­eral val­ues you can tune. Most of them are avail­able in sysctl.

• rhash_​entries is the size of the hash ta­ble.⁵ If you do not spec­ify it on the ker­nel com­mand line, it is com­puted dy­nam­i­cally based on the mem­ory avail­able on your sys­tem. You can view its value by look­ing at some­thing like IP route cache hash table entries: 262144 (order: 9, 2097152 bytes) in the ker­nel logs.
• net.​ipv4.​route.​max_​size is the max­i­mum num­ber of en­tries in the route cache. Ex­cept un­der ex­cep­tional cir­cum­stances, this value is never exceeded.
• net.​ipv4.​route.​gc_​elasticity is the tar­get av­er­age length of a chain in the route cache. The garbage col­lec­tor will work harder if this value is ex­ceeded. This means that if you mul­ti­ply this value by the value of rhash_​entries, you will get the tar­get av­er­age num­ber of en­tries in the route cache.
• net.​ipv4.​route.​gc_​min_​interval_ms is the min­i­mum de­lay be­tween two runs of the garbage col­lec­tor, ex­cept when the cache is full. The de­fault value should be fine.
• net.​ipv4.​route.​gc_​thresh is a thresh­old trig­ger­ing the garbage col­lec­tor ev­ery net.​ipv4.​route.​gc_​min_​interval_ms mil­liseconds.
• net.​ipv4.​route.​gc_​timeout is the base value to de­ter­mine if an en­try is old enough to be re­moved or not. What­ever its value, the garbage col­lec­tor will at­tempt to re­move the same num­ber of en­tries. How­ever, this value could po­ten­tially in­flu­ence its ef­fi­ciency. See be­low for more de­tails on this.

You may find doc­u­men­ta­tion about these ob­so­lete sysctl values:

• net.​ipv4.​route.​secret_​interval has been re­moved in Linux 2.6.35; it was used to trig­ger an asyn­chro­nous flush at fixed in­ter­val to avoid to fill the cache.
• net.​ipv4.​route.​gc_​interval has been re­moved in Linux 2.6.38. It is still present un­til Linux 3.2 but has no ef­fect. It was used to trig­ger an asyn­chro­nous cleanup of the route cache. The garbage col­lec­tor is now con­sid­ered ef­fi­cient enough for the job.

Statistics & monitoring#

Linux main­tains some sta­tis­tics about the use of the route cache. You can find them in /proc/​net/​stat/​rt_​cache. The com­mand lnstat can print them nicely for you:

$ lnstat -s1 -i1 -c-1 -f rt_cache
rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|rt_cache|
 entries|  in_hit|in_slow_|in_slow_|in_no_ro|  in_brd|in_marti|in_marti| out_hit|out_slow|out_slow|gc_total|gc_ignor|gc_goal_|gc_dst_o|in_hlist|out_hlis|
        |        |     tot|      mc|     ute|        |  an_dst|  an_src|        |    _tot|     _mc|        |      ed|    miss| verflow| _search|t_search|
 3096848|   42309|     686|       0|       0|       0|       0|       0|       3|       0|       0|     674|     672|       0|       0|   27644|       8|
 3096984|   41405|     636|       0|       0|       0|       0|       0|       3|       0|       0|     623|     621|       0|       0|   28189|       8|
 3097160|   42483|     700|       0|       0|       0|       0|       0|       5|       0|       0|     694|     692|       0|       0|   29506|      12|

Ex­cept for the first col­umn, lnstat out­puts val­ues in units per sec­ond. Let’s re­view some of these values:

• rt_​cache_​entries is the num­ber of en­tries in the route cache. You should com­pare it with net.​ipv4.​route.​max_​size and en­sure that the cache is never full to avoid trig­ger­ing the garbage col­lec­tor too often.
• rt_​cache_​in_​hit and rt_​cache_​out_​hit are the num­ber of reg­u­lar lookups avoided be­cause the re­sult was found in the cache for in­com­ing and out­go­ing pack­ets, re­spec­tively. When the sys­tem is a router, most lookups only hap­pen on the in­com­ing side. You should com­pare this value with rt_​cache_​in_​slow_​tot and rt_​cache_​in_​out_​slow_​tot which are the num­ber of lookups in the route ta­bles. On this sys­tem, the ef­fi­ciency of the route cache is more than 98% which is quite good.
• rt_​cache_​gc_​total is how of­ten the garbage col­lec­tor was re­quested to be trig­gered while rt_​cache_​gc_​ignored cor­re­sponds to how of­ten it was fi­nally not run be­cause it has al­ready been trig­gered shortly be­fore­hand (less than net.​ipv4.​route.​gc_​min_​interval_ms mil­lisec­onds). The dif­fer­ence be­tween these two val­ues should be very small to en­sure that the garbage col­lec­tor does not run more than a hand­ful of times per second.
• rt_​cache_​gc_​goal_​miss is how of­ten the garbage col­lec­tor was not able to ful­fill its goal. This value should rarely be dif­fer­ent from 0.
• rt_​cache_​gc_​dst_​overflow is how of­ten the route cache is big­ger than the al­lowed max­i­mum size. This should never hap­pen ex­cept when you try to shrink the cache.
• rt_​cache_​in_​hlist_​search and rt_​cache_​out_​hlist_​search is how of­ten a lookup in the cache had to look at the next en­try in the chain for the com­puted bucket: each time Linux has to fol­low the next pointer in a cache en­try, it in­cre­ments one of these coun­ters. It is a clue on the av­er­age length of chains in the route cache hash ta­ble. Com­pare these val­ues with the num­ber of cache lookups (hit and miss).

As an il­lus­tra­tion, here is a plot of the var­i­ous sta­tis­tics ex­posed above for a router whose route cache re­ceives about 1000 routes per second:

rhash_​entries is 1,048,576, as is net.​ipv4.​route.​gc_​thresh. There­fore, the garbage col­lec­tor was re­quested to be run when the num­ber of en­tries goes above this level. Be­cause the cache is not full, it is only re­ally run twice per sec­onds (the value of net.​ipv4.​route.​gc_​interval_ms is 500). net.​ipv4.​route.​gc_​elasticity is set to 3. This ex­plains why the garbage col­lec­tor is ag­gres­sive when the num­ber of en­tries reached 3,145,728.

As you can see, the ef­fi­ciency is near 100% all the time. The per­cent­age of col­li­sions is rt_​cache_​in_​hlist_​search ra­tio to the sum of rt_​cache_​in_​hit and rt_​cache_​in_​slow_tot.

Up­date (2011-12)

The plot above was with a 2.6.39 ker­nel. For a ker­nel be­tween 2.6.35 and 2.6.37 (in­cluded) or a 3.2 ker­nel or more re­cent, the cleanup trig­gered ev­ery net.​ipv4.​route.​gc_​interval sec­onds will ex­pire up to rhash_​entries en­tries. If the pace at which routes are added to the cache is less than this rate, the num­ber of en­tries may stop climb­ing, even when net.​ipv4.​route.​gc_​threshold is not met. For ex­am­ple, here are the same sta­tis­tics with a 2.6.35 ker­nel for a router with about 2,500 new en­tries per sec­ond but with net.​ipv4.​route.​gc_​interval en­abled; the thresh­old of 1,048,576 is never met:

Tuning#

Do you need to mod­ify any of these val­ues? You have two ques­tions to ask yourself:

1. How much ef­fi­ciency do you want to get from the route cache?
2. How much mem­ory do you want to ded­i­cate to the route cache?

As a rule of thumb, two mil­lion en­tries eat about 500 MiB of mem­ory on a 64-bit sys­tem. You should be able to com­pute the av­er­age mem­ory us­age and the max­i­mum mem­ory us­age from the val­ues of net.​ipv4.​route.​max_​size, rhash_​entries and net.​ipv4.​route.​gc_​elasticity. For ex­am­ple, if the route cache hash ta­ble has 262,144 buck­ets, the max­i­mum al­lowed num­ber of en­tries in the cache is 4,194,304 and net.​ipv4.​route.​gc_​elasticity is set to 8, the mem­ory us­age will be 500 MiB on av­er­age and 1 GiB max. If this is too much, you will need to lower some values.

Look at the pre­vi­ous sec­tion to com­pute the cur­rent ef­fi­ciency of your route cache. It should be above 90%. If you are dis­sat­is­fied with that, you could in­crease the cache size.

If you want to dou­ble the num­ber of en­tries, dou­ble net.​ipv4.​route.​max_​size, net.​ipv4.​route.​gc_​thresh and rhash_​entries but keep net.​ipv4.​route.​gc_​elasticity to 8.

For the garbage col­lec­tor to be ef­fi­cient, the route cache should not be filled too fast. The garbage col­lec­tor should be able to cope with this sit­u­a­tion but this may im­pact per­for­mance be­cause it needs to walk sev­eral times the route cache to find en­tries to ex­pire. Watch­ing gc_​goal_​miss may give you a hint about this: if this value starts to be dif­fer­ent from 0, lower net.​ipv4.​route.​gc_​timeout.

In-depth look into the garbage collector#

These dif­fer­ent pieces of ad­vice may have puz­zled you. We need to un­der­stand how the garbage col­lec­tor works to bet­ter cope with them. The garbage col­lec­tor is trig­gered when a new en­try needs to be added to the cache and the num­ber of en­tries is su­pe­rior to net.​ipv4.​route.​gc_​thresh. It is im­ple­mented in rt_​garbage_​collect() func­tion. It will do noth­ing if it has been called less than net.​ipv4.​route.​gc_​interval_ms mil­lisec­onds and the cache is not full (more than net.​ipv4.​route.​max_​size entries).

Setting a goal#

The garbage col­lec­tor will first as­sess the sit­u­a­tion. It will look how the num­ber of en­tries cur­rently in the cache com­pares to the prod­uct of rhash_​entries and net.​ipv4.​route.​gc_​elasticity:

1. Above this limit, it will try to re­move at least rhash_​entries entries.
2. Oth­er­wise, it will try to re­move no more than half the dif­ference.

If you look at the pre­vi­ous plot, you can eas­ily see the dif­fer­ence when the garbage col­lec­tor is not ag­gres­sive (above 1,048,576 en­tries but be­low 3,145,728) and when it is (above 3,145,728 en­tries). If we as­sume the garbage col­lec­tor is able to meet its goal, we can eas­ily sim­u­late its al­gorithm:

The first plot shows what would hap­pen if about 2000 routes are added per sec­ond with rhash_​entries equal to 262,144 and net.​ipv4.​route.​gc_​elasticity set to 8. When net.​ipv4.​route.​gc_​threshold is met, the garbage col­lec­tor has al­most no ef­fect. How­ever, when the num­ber of en­tries reaches 2,097,152, the garbage col­lec­tor sets its goal to 262,144. From this point, the num­ber of en­tries os­cil­lates around 2 mil­lions entries.

On the sec­ond plot, rhash_​entries is now equal to 1,048,576 but net.​ipv4.​route.​gc_​elasticity has been set to 2. There­fore, the ag­gres­sive part of the garbage col­lec­tor kicks at the same thresh­old as for the pre­vi­ous plot. How­ever, its goal is now four times larger and the os­cil­la­tions have a larger am­pli­tude. The fact that the ag­gres­sive part of the garbage col­lec­tor kicks less of­ten is nul­li­fied by the fact that it needs to re­move more en­tries each time. Be­cause of the slight im­pact on cache ef­fi­ciency, it seems bet­ter to keep net.​ipv4.​route.​gc_​elasticity around 8, or 4 if we want to keep shorter chains (but there seems to be no im­prove­ment to do so).

The other plots show what hap­pens when there is a sud­den surge in the num­ber of routes added or when there is a pause.

Meeting the goal#

Now that we un­der­stand how rhash_​entries, net.​ipv4.​route.​gc_​elasticity and net.​ipv4.​route.​gc_​threshold in­ter­act, let’s look at net.​ipv4.​route.​gc_​timeout. Once the garbage col­lec­tor has set its goal and if it is pos­i­tive, it needs to choose which en­tries to re­move from the cache.

It walks the hash ta­ble from the po­si­tion of its last run and re­move en­tries un­til its goal is met. If the en­try is not cur­rent any­more (for ex­am­ple, the net­work in­ter­face as­so­ci­ated to it has changed its IP con­fig­u­ra­tion), it is re­moved. Oth­er­wise, the sys­tem looks at the age of the en­try and its po­si­tion in the chain. If the en­try is the first in the chain, it is kept only if its age is be­low net.​ipv4.​route.​gc_​timeout. If it is sec­ond, it is kept only if its age is be­low half of net.​ipv4.​route.​gc_​timeout. If it is third, the thresh­old is a quar­ter of net.​ipv4.​route.​gc_​timeout, and so on. The garbage col­lec­tor will fa­vor short chains.

If af­ter a full run of the hash ta­ble, the garbage col­lec­tor was not able to meet its goal, it will start again but will be­have more ag­gres­sively, as if net.​ipv4.​route.​gc_​timeout is set to half of its value. It will do as many passes as nec­es­sary un­til its goal is met or un­til there is no way to re­move any en­try (or un­til it has spent too much time). Once the garbage col­lec­tor has switched to this more ag­gres­sive be­hav­ior, it will keep be­ing ag­gres­sive for a few cy­cles (a bit less for each cycle).

With a very large value of net.​ipv4.​route.​gc_​timeout, the garbage col­lec­tor will have a hard time to find en­tries to ex­pire. It will need to do sev­eral passes un­til it is able to ex­pire some en­tries. On the other hand, if you choose a very small value, the garbage col­lec­tor may re­move en­tries that were just added, even if there are older en­tries fur­ther in the hash table.

For a more in-depth cov­er­age of how the route cache works, look at chap­ter 33 of Un­der­stand­ing Linux Net­work In­ter­nals. Be aware that mul­ti­path route caching has been re­moved (and was never re­ally used) and asyn­chro­nous cleanup (rt_​periodic_​timer) does not ex­ist anymore.

Conclusion#

When tun­ing the route cache, rhash_​entries, net.​ipv4.​route.​gc_​elasticity, net.​ipv4.​route.​max_​size and net.​ipv4.​route.​gc_​threshold are re­lated and should not be mod­i­fied in­de­pen­dently. net.​ipv4.​route.​gc_​thresh should be be­low the prod­uct of net.​ipv4.​route.​gc_​elasticity and rhash_​entries while net.​ipv4.​route.​max_​size should be above this value.

Linux ex­poses sev­eral in­ter­est­ing met­rics re­lated to the route cache. Mon­i­tor­ing them al­lows one to watch the ef­fi­ciency of the route cache and may un­cover some anom­alies (garbage col­lec­tor run­ning too of­ten, dif­fi­culty to re­move routes from the cache, …).

The route cache sub­sys­tem still evolves and some old be­hav­iors have been dis­missed. The best doc­u­men­ta­tion is, un­for­tu­nately, still the code and other doc­u­men­ta­tion tends to be­come obsolete.

1. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=5e9965c15ba88319500284e590733f4a4629a288
2. https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux
3. https://www.oreilly.com/library/view/understanding-linux-network/0596002556/
4. https://www.rfc-editor.org/info/rfc3704
5. https://en.wikipedia.org/wiki/Hash_table
6. https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
7. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=3ee943728fff536edaf8f59faa58aaa1aa7366e3
8. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=349d2895cc8b7db1f5be677cd685209a3805d2ed
9. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=9f28a2fc0bd77511f649c0a788c7bf9a5fd04edb
10. https://elixir.bootlin.com/linux/v3.1/source/net/ipv4/route.c#L880
11. https://gist.github.com/vincentbernat/1460108
12. https://vincent.bernat.ch/en/blog/2017-ipv6-route-lookup-linux