This is an attempt to summarize the discussion I've been involved over the last couple of days regarding this topic.
Making the routing cache optional opens up a few new possibilities. One of them is integrating ematches into fib_lookup, e.g. we could use em_cmp/u32 to match on the flowlabel of ipv6 packets without having the routing code actually being aware of that field.
Another idea that came up in the last days was to use something like bloom filters to make the decision whether a certain flow has been seen before. I'm not quite sure who exactly came up with this idea but I've seen everyone talking about it. ;-> I'm not convinced by bloom filters yet but the general concept seems worth to follow. The idea is to have some kind of metric to figure out whether a fib_lookup is actually worth so we can just drop not yet seen flows under heavy pressure. The problem it gets down to is that we get yet another lookup in the fast path and nobody is actually sure that this helps at all. Actually this whole idea might be unnecessary with the concept described next.
Robert explained this idea to me this afternoon, the idea is to automatically adopt gc_elasticity to better handle the current situation/reason for new flows. A high rate of unintentional new flows is best addressed with a low gc_elasticity where a high rate of intentional new flows requires a higher gc_elasticity. Once we get rid of destination addresses in dst entries this idea is probably quite obsolete again though.
So to my understanding the best idea is to remove as much pressure as possible from the routing cache or to even make it optional. In case we really can't get rid of the routing cache and the cache misses are still an issue it might be worth to try something like Robert's pre route approach.