[1240] in linux-net channel archive
Re: ip aliasing support ...
daemon@ATHENA.MIT.EDU (Rob Janssen reading Linux mailingl)
Wed Oct 25 00:05:53 1995
From: linux@pe1chl.ampr.org (Rob Janssen reading Linux mailinglist)
To: srb@cuci.nl (Stephen R. van den Berg)
Date: Tue, 24 Oct 1995 09:35:54 +0100 (MET)
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
Reply-To: linux-vger@wab-tis.rabobank.nl
According to Stephen R. van den Berg:
> I'm not saying that I'm using 7MB or bigger routing tables (someone tried
> it with a Linux box, sheer suicide with linear searches, of course) yet.
> But the current routing table I'm using already has 17 entries (and that
> does not include individual IPno's for dial up lines and virtual IP
> addresses for a multihomed host).
>
> 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.
>
> 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.
This is how KA9Q NOS does it. Or more closely: it uses an array of
hashed lists for 32 different netmasks.
Unfortunately, it is quite costly because one has to start searching
the 32-bit (host-specific entry) and then work back bit by bit until
a match is found. When the entry in the table is for a class-B net,
16 searches have to be done to find it.
Each search consists of masking the appropriate netmask off the address,
computing the hashvalue and searching the corresponding list. These
lists can be long on the level of host-specific entry, at least in
AMPRnet.
I have been looking at it, and also wanted to add capability to store
alternative routes (with different metric) and select between them.
However, I have not found a really better way to do it...
(and note the code not even covers non-contiguous netmasks...)
Having routes with different metrics also adds the complication of
assigning a priority to the metric and netmask of a route. Do you
prefer a metric-10 route with 24 specific bits over a metric-2 route
with 16 specific bits? (currently my code does, because it first
goes for the most specific match, and within that selects the lowest
metric route)
Having binary-searched arrays instead of the hashed lists could be
faster in lookups in some cases (I am not convinced), but certainly
is less efficient when updating the table.
To keep the process of route lookup efficient, NOS uses a route cache.
(originally one entry, I have extended it to have as many entries
as the hashed lists).
This means that frequent traffic to a certain host has less routing
lookup overhead, because the route to that host is in the cache.
The entire cache is cleared upon every change in the routing table,
forcing a new lookup.
Rob
--
+------------------------------------+--------------------------------------+
| Rob Janssen rob@knoware.nl | AMPRnet: rob@pe1chl.ampr.org |
| e-mail: pe1chl@wab-tis.rabobank.nl | AX.25 BBS: PE1CHL@PI8WNO.#UTR.NLD.EU |
+------------------------------------+--------------------------------------+
