From: David Lebrun <david.leb...@uclouvain.be> Date: Mon, 28 Nov 2016 21:16:19 +0100
> The advantage of my solution over RFC2992 is lowest possible disruption > and equal rebalancing of affected flows. The disadvantage is the lookup > complexity of O(log n) vs O(1). Although from a theoretical viewpoint > O(1) is obviously better, would O(log n) have an effectively measurable > negative impact on scalability ? If we consider 32 next-hops for a route > and 100 pseudo-random numbers generated per next-hop, the lookup > algorithm would have to perform in the worst case log2 3200 = 11 > comparisons to select a next-hop for that route. When I was working on the routing cache removal in ipv4 I compared using a stupid O(1) hash lookup of the FIB entries vs. the O(log n) fib_trie stuff actually in use. It did make a difference. This is a lookup that can be invoked 20 million times per second or more. Every cycle matters. We already have a lot of trouble getting under the cycle budget one has for routing at wire speed for very high link rates, please don't make it worse.
