On Tue, Feb 13, 2018 at 8:34 AM, David Miller <da...@davemloft.net> wrote: > From: Roopa Prabhu <ro...@cumulusnetworks.com> > Date: Tue, 13 Feb 2018 08:19:35 -0800 > >> - Regardless of this series, I think we should optimize ip rules or >> have a new implementation of policy based routing. happy to hear about >> possible options here: >> - optimize the existing implementation (have there been >> previous discussions on possible options ?) >> - @netdev2.2, I did outline a possible option for tc to >> provide an l3 hook for policy based routing (people were ok with this >> and I was told more tc hooks were in the works). >> tc was a choice mainly because of all its existing match >> options (flower for example). Will that help ? >> - We should have an ebpf accelerated implementation >> regardless for people to use it if they want to scale rules > > The problem is that arbitrary prefixing in the rules. That prevents > O(1) algorithms from being used to maintain the table. > > If they were all just non-prefixed keys we could do a hash table or > similar.
ah, got it. > > I guess we could do a trie (on saddr) to a (on daddr) trie (like the > ipv6 subtrees do), but that's a lot of complexity just for fib rules. > agreed.