Subject: works in progress: route cache invalidation, RADIX_MPATH
To: None <firstname.lastname@example.org>
From: David Young <email@example.com>
Date: 11/16/2006 13:33:30
Patches for two networking features I have in progress are at
<ftp://cuw.ojctech.com/cuw/netbsd-70b158cb/net-wip.patch>. The first
feature is route-cache invalidation. The second feature is RADIX_MPATH,
the multipath routing patches from KAME, with many of my own improvements.
Sorry the patches for both features are intermingled---anybody know a
good patch editor?
* Route-cache invalidation
BSD uses struct route to cache the results of forwarding-table
lookups. BSD embeds struct route in PCBs, in the table of IP
flows, in the IP forwarding cache (ipforward_rt), et cetera.
The ro_rt member caches the results of forwarding-table lookups.
BSD neither changes nor invalidates the caches when the forwarding
table changes, and that leads the kernel to use a stale cache,
which leads to broken routing. See kern/3508 for an example of
broken routing whose underlying cause is a stale cache.
My patch adds callbacks to 'struct domain' both for invalidating
a particular route cache (dom_rtflush), for adding a particular
route cache to the set of active caches (dom_rtcache), and for
invalidating all caches in the routing domain (dom_rtflushall).
I provide helper routines rtcache(struct route *), rtflush(struct
route *), and rtflushall(int family) for invoking the callbacks.
I add a couple of calls to rtflushall() in rtrequest1().
My patch only treats IPv4, but IPv6 and other networking domains
deserve similar treatment.
Christoph Badura discouraged me from my original plan for
invalidating the route caches, and set me on the path of chaining
all of the struct routes together, which ultimately proved a
lot easier than what I'd planned. Thanks, Christoph!
Beware, I have only just begun to test these patches. There may
be serious bugs.
The second feature is the RADIX_MPATH patches from KAME, with
significant modifications by me. RADIX_MPATH implements multipath
routing according to "Modulo-N Hash," described in RFC2991.
Beware: I have not run compiled or run my RADIX_MPATH patches
in a long time. I know there are bugs that cause crashes.
My mods make RADIX_MPATH work sensibly in the event that you
can reach the same destination both directly (i.e., it's on the
same link), and through an IP router---this is not the least
bit unusual on a wireless multihop network.
I encapsulate each route's preferability in a macro,
RADIX_MPATH_PREFERENCE(). Routes with greater preference
numbers are chosen with greater likelihood. Right now,
RADIX_MPATH_PREFERENCE() always evaluates to 1.
I also add a "wireless heuristic" to the code that selects
nexthops: if a destination is on the same link, but there is
a route through an IP router, the heuristic chooses the latter
route. The assumption is that a routing daemon has added the
longer path, knowing full well what it is doing! :-) This is
a pretty reasonable assumption in practice, but we need the
capability to turn the heuristic on and off.
* Et cetera
I retired a workaround in gif(4) for the old route-caching
I removed gre(4)'s ability to configure the same remote inner
IP as remote outer IP, per prior discussions on tech-net.
I made many cosmetic changes throughout the networking stacks.
David Young OJC Technologies
firstname.lastname@example.org Urbana, IL * (217) 278-3933