RARE user and assistance email list

[mc36 <>]

hi,

so after simon's suggestion, we moved to a trie data structure to store the 
fib in the p4emu (dpdk, pcap, etc) dataplanes...
if i have to simplify it then it means that i have to walk the prefix's bits 
from left to right...
if we have 0 bit then we try to move left, if we have a bit 1 then we try to 
move right...
once we cannot continue because we hit NULL, then we can finish the tree 
walking and we could execute the fib entry...
i do the performance measurements for a /64 and a /24 that known to perform 
the worst case (when the prefix exists)
because one have to do almost the full walk... in case of ipv6, think about 
the following fib:
::/0
2001:738:1234::/64
...
2001:738:ffff::/64

then i go for the dst=2001:738:4321::1234 so i find the termination point 
after 48 rounds
compared if i went for the dst=2806:10a8:4321::1234 which will terminate 4+1 
rounds because
the the first 4 bits could match, but when i reach the 8 i find the end of 
the tree quickly
pointing me back to the default route...

the algorithm is O(n) to the number of bits to walk, that is, 48cputime for 
ipv6 and 24cputime for ipv4

in contrast to this, when it comes to mpls, it's a simple divide-and-conquer 
kind of algorithm (binary search)
so it's a magnitude faster O(log n) where n is the number labels (router 
nodes in your network) you have,
which is 3 if you have a thousand of boxes...

when simon suggested the topic, i found a nice article describing what the 
linux kernel is doing:
https://vincent.bernat.ch/en/blog/2017-ipv6-route-lookup-linux
https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux
they measured it on a full view and found ipv6 10 times slower compared to 
ipv4 and not found
a similar comparison for mpls and it's not surprises me at all... :(

br,
cs




On 8/17/22 16:13, Tim Chown wrote:
> Hi,
>
> I   ve been off for 5 weeks, but back :).   So, why so relatively poor for 
> IPv6?
>
> Tim
>
> > On 22 Jul 2022, at 08:51, mc36 <> wrote:
> >
> > hihi,
> > yet another 15% boost from the previous one... it's almost 100gbps for ipv4, 
> > 61gbps for ipv6 and 170gbps for mpls...
> > (that latter again did not changed)... at this time, it was a table 
> > sctructure refactoring...
> > br,
> > cs
> >
> >
> > On 7/4/22 07:45, mc36 wrote:
> > > hihi,
> > > in the past weeks, some big improvements happened to the p4emu core forwarder:
> > > here is the historic snapshot: 
> > > https://twitter.com/rare_freerouter/status/1490693899786072067/photo/1
> > > attached the current one... in case of ipv4, it's 10%+, in case of ipv6, it's 
> > > 20%+,
> > > mpls did not changed as it was a tire structure (and lookup code) 
> > > refactoring...
> > > moreover, the dpdk packetio got a bugfix caused it to stop processing packets
> > > from a given nic, because the fwd2nic path could exhaust all of it's mbufs
> > > if the nic2fwd path was much faster somehow...
> > > br,
> > > cs
> > <2022-07-22-084324_1920x1080_scrot.png>