[1234] in linux-net channel archive
Re: ip aliasing support ...
daemon@ATHENA.MIT.EDU (Alan Cox)
Mon Oct 23 20:16:44 1995
From: Alan Cox <alan@cymru.net>
To: srb@cuci.nl (Stephen R. van den Berg)
Date: Mon, 23 Oct 1995 14:49:22 +0100 (BST)
Cc: alan@cymru.net, linux-net@vger.rutgers.edu
In-Reply-To: <199510231255.NAA20049@hera.cuci.nl> from "Stephen R. van den Berg" at Oct 23, 95 01:55:46 pm
> I'd strongly suggest something like a binary search be adopted (or
> at least optional), otherwise Linux will not be suitable for any heavy
> network routing operation.
For routing yes, for addresses/interface probably not. It does possible
also answer the interesting problem about the O(N) slowdown of
ip_chk_addr() though.
> I've already given it some thought, seems that one would need a separate
> binary search array for every different netmask.
> Then the binary search will have to start in the most specific table.
> Switching to the next more specific table upon every total miss, of course.
BSD uses a patricia tree. I can see a binary search without netmasks working
rather well to the same effect.
ie 0 the unused bits. Now when you binary search you can use the netmask
at the end
x=bin_search(addr)
do
{
if(!((addr^x->addr)&~mask))
return x;
x=x->parent;
}
while(x);
return NULL;
ie binary search from the bottom then walk up in generality.
However with a big routing table (going on for 7Mb of entries) you don't
want to bear the cost of an insertion into an array - so a patricia tree
should nayone care to write one will be good.
Alan
