]> git.baikalelectronics.ru Git - kernel.git/commit
[IPV4]: fib_trie root-node expansion
authorRobert Olsson <robert.olsson@its.uu.se>
Tue, 4 Oct 2005 20:01:58 +0000 (13:01 -0700)
committerDavid S. Miller <davem@davemloft.net>
Tue, 4 Oct 2005 20:01:58 +0000 (13:01 -0700)
commit99dccc702f0a7ebd9376217410e465942a208a4c
tree9cb766b5b66f700528722b2e92745a2a6dcc3288
parentac77a783649512b5dd240be67a578cdc1d53a5ed
[IPV4]: fib_trie root-node expansion

The patch below introduces special thresholds to keep root node in the trie
large. This gives a flatter tree at the cost of a modest memory increase.
Overall it seems to be gain and this was also proposed by one the authors
of the paper in recent a seminar.

Main table after loading 123 k routes.

Aver depth:     3.30
Max depth:      9
        Root-node size  12 bits
        Total size: 4044  kB

With the patch:
Aver depth:     2.78
Max depth:      8
        Root-node size  15 bits
        Total size: 4150  kB

An increase of 8-10% was seen in forwading performance for an rDoS attack.

Signed-off-by: Robert Olsson <robert.olsson@its.uu.se>
Signed-off-by: David S. Miller <davem@davemloft.net>
net/ipv4/fib_trie.c