From mboxrd@z Thu Jan 1 00:00:00 1970 From: Hannes Frederic Sowa Subject: Re: [RFC PATCH net-next] ipv6: implement consistent hashing for equal-cost multipath routing Date: Wed, 30 Nov 2016 14:12:48 +0100 Message-ID: <1480511568.3649771.803688521.5B47BE8F@webmail.messagingengine.com> References: <1480017556-25988-1-git-send-email-david.lebrun@uclouvain.be> <20161128.112248.2198395724649783009.davem@davemloft.net> <583C9093.7060404@uclouvain.be> <20161128.153209.2135257061368558724.davem@davemloft.net> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Cc: netdev@vger.kernel.org To: David Miller , david.lebrun@uclouvain.be Return-path: Received: from out5-smtp.messagingengine.com ([66.111.4.29]:32911 "EHLO out5-smtp.messagingengine.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756170AbcK3NMt (ORCPT ); Wed, 30 Nov 2016 08:12:49 -0500 In-Reply-To: <20161128.153209.2135257061368558724.davem@davemloft.net> Sender: netdev-owner@vger.kernel.org List-ID: On Mon, Nov 28, 2016, at 21:32, David Miller wrote: > From: David Lebrun > 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. David, one question: do you remember if you measured with linked lists at that time or also with arrays. I actually would expect small arrays that entirely fit into cachelines to be actually faster than our current approach, which also walks a linked list, probably the best algorithm to trash cache lines. I ask because I currently prefer this approach more than having large allocations in the O(1) case because of easier code and easier management. Thanks, Hannes