Subject: Re: patricia tries vs. hash for routing?

From: "David S. Miller" <[email-masked]>
Date: Thu, 18 Sep 2003 20:17:43 -0700

On Thu, 18 Sep 2003 10:29:10 -0700
Kristen Carlson <[email-masked]> wrote:

> I'm wondering if somebody has already written a patch that replaces the
> current routing algorithm (hash) with one that is based on a trie based
> algorithm?  I'm also wondering if anybody has done any performance 
> comparisons with very large route tables to see which one scales better?

Patricia trees aren't going to help, most of the overhead in
the routing lookup is in implementing the various fancy features
our routing code supports.  For example, equal cost multi-pathing
and other such things.

The front end routing cache is a straight hash and is thus the
fastest way to lookup a route.  In the presence of well behaved
traffic and routing tables that do not change too often, it is
optimal.